k-dimensional orthogonal range search with tries

Simple item page
dc.contributor.authorNickerson, Bradford, G.
dc.contributor.authorBu, Lingke
dc.date.accessioned2023-03-01T18:27:59Z
dc.date.available2023-03-01T18:27:59Z
dc.date.issued2002
dc.description.abstractWe present an algorithm using tries to solve the orthogonal range search problem on k dimensions. The algorithm reports all k-d hyper-rectangles intersecting a k-d axis-aligned query hyper-rectangle W, and supports dynamic operations. For the input data set D and W drawn from a uniform, random distribution, we analyse the expected time for orthogonal range search. We show that the storage S(n, k) =O(nk), and the expected preprocessing time P(n, k) = O(nk) for a trie containing n k-d hyper-rectangles.
dc.description.copyrightCopyright @ Bradford G. Nickerson and Lingke Bu, 2002.
dc.identifier.urihttps://unbscholar.lib.unb.ca/handle/1882/14804
dc.rightshttp://purl.org/coar/access_right/c_abf2
dc.subject.disciplineComputer Science
dc.titlek-dimensional orthogonal range search with tries
dc.typetechnical report

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
item.pdf
Size:
2.81 MB
Format:
Adobe Portable Document Format
Download

Collections

Research Reports