|
Abstract : |
Range trees can be 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 have to partition range trees into prts that can be stored in consecutive blocks in secondary memory. This pper, which is the first part in a series of two, 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(nl/t), such that each update requires at most k(2k + 1) disk accesses, and each query requires at most 4k(2k + 1)- 4 + 2t disk accesses, where t is the number of answers to the range query. In Part II of this paper, lower bounds are given, which show that many of our partition schemes are optimal., |
