×

Maintaining range trees in secondary memory. Part I: Partitions. (English) Zbl 0672.68007

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.
Reviewer: M.H.M.Schmid

MSC:

68P05 Data structures
68P10 Searching and sorting
68P20 Information storage and retrieval of data
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bayer, R., McCreight, E.M.: Organisation and Maintenance of Large Ordered Indexes. Acta Inf. 1, 173-189 (1972) · Zbl 0226.68008 · doi:10.1007/BF00288683
[2] Bentley, J.L.: Decomposable Searching Problems. Inform. Proc. Lett. 8, 244-251 (1979) · Zbl 0404.68067 · doi:10.1016/0020-0190(79)90117-0
[3] Blum, N., Mehlhorn, K.: On the Average Number of Rebalancing Operations in Weight-Balanced Trees. Theor. Comput. Sci. 11, 303-320 (1980) · Zbl 0435.68051 · doi:10.1016/0304-3975(80)90018-3
[4] Comer, D.: The Ubiquitous B-tree. Comput. Surv. 11, 121-137 (1979) · Zbl 0419.68034 · doi:10.1145/356770.356776
[5] Graham, R.L., Knuth, D.E., Patashnik, O.: Concrete Mathematics. Reading, Mass.: Addison-Wesley 1989 · Zbl 0668.00003
[6] Hinrichs, K.: The Grid File System: Implementation and Case Studies of Applications. ETH Zürich: PhD Thesis 1985 · Zbl 0578.68021
[7] Hinrichs, K.: Implementation of the grid file: design concepts and experience. BIT 25, 569-592 (1985) · Zbl 0578.68021 · doi:10.1007/BF01936137
[8] Lueker, G.S.: A Data Structure for Orthogonal Range Queries. Proc. 19-th Annual IEEE Symp. on Foundations of Computer Science, pp. 28-34, 1978
[9] Nievergelt, J., Hinterberger, H., Sevcik, K.C.: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9, 38-71 (1984) · doi:10.1145/348.318586
[10] Nievergelt, J., Reingold, E.M.: Binary Search Trees of Bounded Balance. SIAM J. Comput. 2, 33-43 (1973) · Zbl 0262.68012 · doi:10.1137/0202005
[11] Overmars, M.H.: The Design of Dynamic Data Structures. Lect. Notes Comput. Sci., vol. 156. Berlin Heidelberg New York: Springer 1983 · Zbl 0545.68009
[12] Preparata, F.P., Shamos, M.I.: Computational Geometry, an Introduction. Berlin Heidelberg New York: Springer 1985 · Zbl 0575.68059
[13] Smid, M.H.M.: Dynamic Data Structures on Multiple Storage Media. University of Amsterdam: PhD Thesis 1989
[14] Smid, M.H.M., Overmars, M.H.: Maintaining Range Trees in Secondary Memory, Part II: Lower Bounds. Report FVI-87-15, University of Amsterdam, 1987. Acta Inf. 27, 429-456
[15] Smid, M.H.M., Torenvliet, L., van Emde Boas, P., Overmars, M.H.: Two Models for the Reconstruction Problem for Dynamic Data Structures. J. Inf. Process. Cybern. EIK 25, 131-155 (1989) · Zbl 0679.68038
[16] Willard, D.E., Lueker, G.S.: Adding Range Restriction Capability to Dynamic Data Structures. J. ACM 32, 597-617 (1985) · Zbl 0629.68097 · doi:10.1145/3828.3839
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.