Abstract
Range trees can be used for solving a number of problems in databases and other applications. We study the problem of storing range trees in secondary memory. To this end, we have to partition range trees into parts that can be stored in consecutive blocks in secondary memory. A number of partition schemes will be presented that limit the part sizes and the number of disk accesses necessary for performing updates and queries. Matching lower bounds will be proven as well.
Preview
Unable to display preview. Download preview PDF.
References
J.L. Bentley. Decomposable Searching Problems. Inform. Proc. Lett. 8 (1979), pp. 244–251.
N. Blum and K. Mehlhorn. On the Average Number of Rebalancing Operations in Weight-Balanced Trees. Theor. Comp. Sci. 11 (1980), pp. 303–320.
G.S. Lueker. A Data Structure for Orthogonal Range Queries. Proc. 19-th Annual IEEE Symp. on Foundations of Computer Science, 1978, pp. 28–34.
M.H. Overmars. The Design of Dynamic Data Structures. Springer Lecture Notes in Computer Science, Vol. 156, Springer Verlag, 1983.
M.H. Overmars, M.H.M. Smid, M.T. de Berg and M.J. van Kreveld. Maintaining Range Trees in Secondary Memory, Part I: Partitions. Techn. Report FVI 87-14, Computer Science Department, University of Amsterdam, 1987.
F.P. Preparata and M.I. Shamos. Computational Geometry, an Introduction. Springer Verlag, 1985.
M.H.M. Smid and M.H. Overmars. Maintaining Range trees in Secondary Memory, Part II: Lower Bounds. Techn. Report FVI 87-15, Computer Science Department, University of Amsterdam, 1987.
M.H.M. Smid, L. Torenvliet, P. van Emde Boas and M.H. Overmars. Two Models for the Reconstruction Problem for Dynamic Data Structures. Techn. Report FVI 87-13, Computer Science Department, University of Amsterdam, 1987.
D.E. Willard and G.S. Lueker. Adding Range Restriction Capability to Dynamic Data Structures. Journal of the ACM 32 (1985), pp. 597–617.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1988 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Overmars, M.H., Smid, M.H.M. (1988). Maintaining range trees in secondary memory. In: Cori, R., Wirsing, M. (eds) STACS 88. STACS 1988. Lecture Notes in Computer Science, vol 294. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0035830
Download citation
DOI: https://doi.org/10.1007/BFb0035830
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-18834-6
Online ISBN: 978-3-540-48190-4
eBook Packages: Springer Book Archive