Investigation of a Dynamic K-D Search Skip List Requiring O(kn) Space
Loading...
Files
Date
1997
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A new dynamic k-d data structure (supporting insertion and deletion) labeled the k-d Search Skip List is developed and analyzed. The time for k-d semi-infinite range search on n k-d data points without space restriction is shown to be O(klog n) and O(kn + kt), and there is a space-time trade-off represented as (log T' +log log n) = O(n(log n)[superscript k-O]), where O=1 for k =2, O = 2 fork >3, and T' is the scaled query time. The dynamic update time for the k-d Search Skip List is O(klog n).
We consider the problem of reporting all points in a positive half-space h * (bounded by a query hyper plane h) from a set F of n points in k-dimensional space E[superscript k]; that is, find and report Snh*. Previous dynamic solutions (supporting insertion and deletion of points) are simplified, and the previously best known dynamic update time is improved. For t = Snh* we show that with O(knlog n) preprocessing time and O(kn) space, the k-d halfspace searching problem can be solved in O(kn) time with dynamic update time of O(klogn).
Experimentally for a random data set of 100,000 points, an average of 1048 milliseconds was required to report 50,000 points in range for a 10-d orthogonal range
search; about 800 milliseconds was required to report 50,000 points in range for a 10-d semi-infinite range search; and 106 milliseconds was required to report 50,000 in range for a 10-d half-space range search.