You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format. However, this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the Department of Computer Science of the University of Maryland at College Park under terms that include this permission. All other rights are reserved by the author(s).
Bradford G. Nickerson. April, 1994.
Skip List Data Structures for Multidimensional Data. May 1994.
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) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
Last Generated Fri Aug 11 04:01:01 EDT 2000