We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A deterministic skip list for k-dimensional range search.
- Authors
Lamoureux, Michael; Nickerson, Bradford
- Abstract
This paper presents a new data structure for multi-dimensional point data which is based on an extension of the deterministic skip list data structureprojectedinto k dimensions. The structure is labeled the k-d Range Deterministic Skip List and it supports fast insertions, deletions, and range search. The k-d Range Deterministic Skip List is optimal (i.e.t) to locate and report t ofndata points in range) for k-dimensional range search, assuming that our data points are elements of a commutative semigroup with set union as the commutative and associative addition operation. A dynamic data structure is defined to be optimally balanced if the product of its worst case cost functions for k-dimensional range search, insertion, deletion, storage, and preprocessing is minimal. The k-d Range Deterministic Skip List is found to be optimally balanced based on this definition.
- Subjects
MULTIDIMENSIONAL databases; ABELIAN semigroups; SEMIGROUPS (Algebra); DATA structures; ELECTRONIC data processing
- Publication
Acta Informatica, 2005, Vol 41, Issue 4/5, p221
- ISSN
0001-5903
- Publication type
Article
- DOI
10.1007/s00236-004-0157-8