Overmars, Mark H.; Smid, Michiel H. M.; de Berg, Mark T.; van Kreveld, Marc J. Maintaining range trees in secondary memory. Part I: Partitions. (English) Zbl 0672.68007 Acta Inf. 27, No. 8, 423-452 (1990). 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 Cited in 1 ReviewCited in 3 Documents MSC: 68P05 Data structures 68P10 Searching and sorting 68P20 Information storage and retrieval of data 68Q25 Analysis of algorithms and problem complexity Keywords:partition of range tree; partition schemes; range trees; orthogonal range searching problem; databases; computer graphics PDFBibTeX XMLCite \textit{M. H. Overmars} et al., Acta Inf. 27, No. 8, 423--452 (1990; Zbl 0672.68007) 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.