Maintaining range trees in secondary memory. Part I: Partitions

Data structures (68P05) Searching and sorting (68P10) Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25)

Review text

Range trees are used for solving the orthogonal range searching problem, a problem that has applications in e.g. databases and computer graphics. We study the problem of storing range trees in secondary memory. To this end, we partition range trees into parts that are stored in consecutive blocks in secondary memory. This paper gives a number of partition schemes that limit the part-sizes and the number of disk accesses necessary to perform updates and queries. We show e.g., that for each fixed positive integer k, there is a partition of a two-dimensional range tree into parts of size \(O(n^{1/k})\), such that each update requires at most \(k(2k+1)\) disk accesses, and each query requires at most \(8k^ 2+2k+2t\) disk accesses, where t is the number of answers to the range query.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: Maintaining range trees in secondary memory. Part I: Partitions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1120266)