Abstract
In this paper we develop a technique for transforming an internal memory tree data structure into an external storage structure. We show how the technique can be used to develop a search-tree-like structure, a priority-queue, a (one-dimensional) range-tree and a segment-tree, and give examples of how these structures can be used to develop efficient I/O-algorithms. All our algorithms are either extremely simple or straightforward generalizations of known internal memory algorithms — given the developed external data structures.
This work was partially supported by the ESPRIT II Basic Research Actions Program of the EC under contract No. 7141 (project ALCOM II) and by Aarhus University Research Foundation.
Part of this work was done at the Department of Computer Science, Duke University.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. Aggarwal, J.S. Vitter: The I/O Complexity of Sorting and Related Problems. In Proc. of 14th ICALP (1987), LNCS 267, 467–478, and: The Input/Output Complexity of Sorting and Related Problems. Communications of the ACM, Vol 31 (9) (1988), 1116–1127.
L. Arge: External-Storage Data Structures for Plane-Sweep Algorithms. BRICS Report Series RS-94-16, University of Aarhus, June 1994.
L. Arge, M. Knudsen, K. Larsen: A General Lower Bound on the I/O-Complexity of Comparison-based Algorithms. In Proc. of 3rd WADS (1993), LNCS 709, 83–94.
L. Arge, D.E. Vengroff, J.S. Vitter: External-Memory Algorithms for Processing Line Segments in Geographic Information Systems. Manuscript.
J.L. Bentley, D. Wood: An Optimal Worst Case Algorithm for Reporting Intersections of Rectangles. IEEE Transactions on Computers 29 (1980), 571–577.
Y-J. Chiang: Experiments on the Practical I/O Efficiency of Geometric Algorithms: Distribution Sweep vs. Plane Sweep. These Proceedings.
Y-J. Chiang, M.T. Goodrich, E.F. Grove, R. Tamassia, D.E. Vengroff, J.S. Vitter: External-Memory Graph Algorithms. In Proc. of 6th ACM-SIAM SODA (1995), 139–149.
M.T. Goodrich, J. Tsay, D.E. Vengroff, J.S. Vitter: External-Memory Computational Geometry. In Proc. of 34th IEEE FOCS (1993), 714–723.
S. Huddleston, K. Mehlhorn: A New Data Structure for Representing Sorted Lists. Acta Informatica 17 (1982), 157–184.
Ch. Icking, R. Klein, Th. Ottmann: Priority Search Trees in Secondary Memory. In Proc. of 1987 Graph-Theoretic Concepts in Computer Science, LNCS 314, 84–93.
P.C. Kanellakis, S. Ramaswamy, D.E. Vengroff, J.S. Vitter: Indexing for Data Models with Constraints and Classes. In Proc. 12th ACM PODS (1993), 233–243.
D.E. Knuth: The Art of Computer Programming, Vol 3: Sorting and Searching, Addison-Wesley (1973).
M.H. Nodine, J.S. Vitter: Deterministic Distribution Sort in Shared and Distributed Memory Multiprocessors. In Proc. of 5th ACM SPAA (1993).
S. Ramaswamy, S. Subramanian: Path Caching: A Technique for Optimal External Searching. In Proc. 13th ACM PODS (1994), 25–35.
S. Subramanian, S. Ramaswamy: The P-range Tree: A New Data Structure for Range Searching in Secondary Memory. In Proc. 6th ACM-SIAM SODA (1995), 378–387.
N.P. Yale: The I/O Subsystem — A Candidate for Improvement. Guest Editor's Introduction in IEEE Computer 27 (3) (1994), 15–16.
F. Preparata, M. Shamos: Computational Geometry, An Introduction. Text and Monographs in Computer Science, Springer-Verlag 1985.
C. Ruemmler, J. Wilkes: An Introduction to Disk Drive Modeling. IEEE Computer 27 (3) (1994).
M. Smid: Dynamic Data Structures on Multiple Storage Media. Ph.D thesis University of Amsterdam 1989.
D.E. Vengroff: A Transparent Parallel I/O Environment. In Proc. of 1994 DAGS Symposium on Parallel Computation.
J.S. Vitter: Efficient Memory Access in Large-Scale Computation (invited paper). In Proc. of 8th STACS (1991), LNCS 480, 26–41.
J.S. Vitter, E.A.M. Shriver: Algorithms for Parallel Memory I: Two-Level Memories. Algorithmica, 12 (2) (1994).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Arge, L. (1995). The buffer tree: A new technique for optimal I/O-algorithms. In: Akl, S.G., Dehne, F., Sack, JR., Santoro, N. (eds) Algorithms and Data Structures. WADS 1995. Lecture Notes in Computer Science, vol 955. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60220-8_74
Download citation
DOI: https://doi.org/10.1007/3-540-60220-8_74
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60220-0
Online ISBN: 978-3-540-44747-4
eBook Packages: Springer Book Archive