Skip List Data Structures for Multidimensional Data

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)