Investigation of a Dynamic K-D Search Skip List Requiring O(kn) Space
| dc.contributor.author | Pan, Yunlan | |
| dc.date.accessioned | 2023-03-01T18:30:53Z | |
| dc.date.available | 2023-03-01T18:30:53Z | |
| dc.date.issued | 1997 | |
| dc.description.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. | |
| dc.description.copyright | Copyright @ Yunlan Pan, 1997. | |
| dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/15020 | |
| dc.rights | http://purl.org/coar/access_right/c_abf2 | |
| dc.subject.discipline | Computer Science | |
| dc.title | Investigation of a Dynamic K-D Search Skip List Requiring O(kn) Space | |
| dc.type | technical report |
Files
Original bundle
1 - 1 of 1