Skip List Data Structures for Multidimensional Data
Files
Publication or External Link
Date
Authors
Advisor
Citation
DRUM DOI
Abstract
This report presents four new data structures for multidimensional data.
All of these data structures are based on the deterministic skip list.
Explanations are provided for the 2-d search skip list and three different
versions of the k-d skip list. These structures support fast insertion and
deletion. The third version of the k-d skip list and the 2-d search skip
list require only O(n) space. The 2-d search skip list allows semi-infinite
range searches of type ([L1:H1],[L2:infinity]), or of type
([L1:H1],[-infinity:H2]) in time O(t + log n). The third version of the
k-d skip list seems well-suited for range search using parallel processing.
Algorithms for building, insertion, deletion and range search for all four
data structures are given, along with proofs of worst case complexity for
these operations. Complete C code for range search, insertion and deletion
in the 2-d search skip list is also presented.
(Also cross-referenced as UMIACS-TR-94-52)