Tries for spatial data range search
| dc.contributor.author | Bu, Linke | |
| dc.date.accessioned | 2023-03-01T18:28:28Z | |
| dc.date.available | 2023-03-01T18:28:28Z | |
| dc.date.issued | 2003 | |
| dc.description.abstract | Orthogonal range search finds and reports all objects falling in a specific query window. An algorithm to solve orthogonal range search problem on k dimensions using tries is developed and analyzed. Two hyper-rectangles intersect if and only if their sides on every dimension in the data space intersect. The algorithm reports the set HR (HR C input data set D, HR = A, D = n) or k-dimensional (k-d) hyper-rectangles intersecting a k-d axis-aligned query hyper-rectangle W, and supports dynamic operations. We assume that the input data set D and query hyper-rectangle W drawn from a uniform, random distribution. The storage S(n,k) = 0(kBn) and the expected preprocessing time P(n, k) = 0(kBn) for a trie containing n k-d hyper-rectangles where B is the number of bits for representing a coordinate value. The expected orthogonal range search time Q(n, k) = O(n[superscript a]) for 0.5 < & < 1 and & a complicated function of n and k. Experimental research with randomly generated data and query hyper-rectangles (and various values of k and n up to 10 and 100,000 respectively) is used to empirically validate the expected range search time. Our algorithm compares favorably to the existing dynamic orthogonal range search algorithm when k is large. | |
| dc.description.copyright | Copyright @ Linke Bu, 2003. | |
| dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/14848 | |
| dc.rights | http://purl.org/coar/access_right/c_abf2 | |
| dc.subject.discipline | Computer Science | |
| dc.title | Tries for spatial data range search | |
| dc.type | technical report |
Files
Original bundle
1 - 1 of 1