Deterministic skip lists for k-dimensional range search

dc.contributor.authorLamoureux, Michael, G.
dc.contributor.authorNickerson, Bradford, G.
dc.description.abstractThis report presents a new data structure for multidimensional data which is based on an extension of the deterministic skip list data structure projected into k-dimensions. The data structure is labeled the k -d Range DSL and it allows for efficient multidimensional range search on point data. This structure supports fast insertions, deletions, and search and the k-d Range DSL is shown to be opthual (i.e. O(lgkn + t) to find t points in range) for k-d range search on n points in a dynamic environment with a pointer based memory model where we impose restrictions on worst-case search time, dynamic operations, and storage. The structure is extendible and it does pennit for multidimensional semi-infinite range queries in an equivalent !hue. The k-d Range DSL, by nature of the skip list structure, is well suited for range search in a parallel processing environment. Algorithms for building, insertion, deletion, and range search are provided for the data structure along with proofs of validity and worst-case complexity for these operations. Also, complete working code in (Borland's Turbo) Pascal is provided in the appendices. Keywords: dynamic data structures, algorithms, range search, orthogonal range query, multidimensional data, skip lists, searching, worst-case complexity
dc.description.copyrightCopyright @ Michael G. Lamoureux and Bradford G. Nickerson, 1995.
dc.subject.disciplineComputer Science
dc.titleDeterministic skip lists for k-dimensional range search
dc.typetechnical report


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
2.63 MB
Adobe Portable Document Format