Abstract
In recent years, many theoretically I/O-efficient algorithms and data structures have been developed. The TPIE project at Duke University was started to investigate the practical importance of these theoretical results. The goal of this ongoing project is to provide a portable, extensible, flexible, and easy to use C++ programming environment for efficiently implementing I/O-algorithms and data structures. The TPIE library has been developed in two phases. The first phase focused on supporting algorithms with a sequential I/O pattern, while the recently developed second phase has focused on supporting on-line I/O-efficient data structures, which exhibit a more random I/O pattern. This paper describes the design and implementation of the second phase of TPIE.
Supported in part by the National Science Foundation through ESS grant EIA- 9870734, RI grant EIA-9972879, CAREER grant CCR-9984099, ITR grant EIA- 0112849, and U.S.-Germany Cooperative Research Program grant INT-0129182.
Supported in part by the National Science Foundation through ESS grant EIA- 9870734 and RI grant EIA-9972879.
Supported in part by the National Science Foundation through research grants CCR-9877133 and EIA-9870734 and by the Army Research Office through MURI grant DAAH04-96-1-0013.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
P.K. Agarwal, L. Arge, and S. Govindarajan. CRB-tree: An optimal indexing scheme for 2d aggregate queries. Manuscript, 2002.
P.K. Agarwal, L. Arge, O. Procopiuc, and J. S. Vitter. A framework for index bulk loading and dynamization. In Proc. 28th Intl. Colloq. Automata, Languages and Programming (ICALP), 2001.
A. Aggarwal and J. S. Vitter. The Input/Output complexity of sorting and related problems. Communications of the ACM, 31(9):1116–1127, 1988.
L. Arge. External memory data structures. In J. Abello, P.M. Pardalos, and M.G.C. Resende, editors, Handbook of Massive Data Sets, pages 313–358. Kluwer Academic Publishers, 2002.
L. Arge, A. Danner, and S.-M. Teh. I/O-efficient point location using persistent B-trees. Manuscript, 2002.
L. Arge, K. H. Hinrichs, J. Vahrenhold, and J. S. Vitter. Efficient bulk operations on dynamic R-trees. Algorithmica, 33(1):104–128, 2002.
L. Arge, O. Procopiuc, S. Ramaswamy, T. Suel, J. Vahrenhold, and J. S. Vitter. A unified approach for indexed and non-indexed spatial joins. In Proc. Conference on Extending Database Technology, pages 413–429, 1999.
L.A. Arge and J. Vahrenhold. I/O-efficient dynamic planar point location. In Proc. ACM Symp. Computational Geometry, 2000.
B. Becker, S. Gschwind, T. Ohler, B. Seeger, and P. Widmayer. An asymptotically optimal multiversion B-tree. VLDB Journal, 5(4):264–275, 1996.
N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: An efficient and robust access method for points and rectangles. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 322–331, 1990.
J. L. Bentley. Multidimensional binary search trees used for associative searching. Commun. ACM, 18(9):509–517, Sept. 1975.
D. Comer. The ubiquitous B-tree. ACM Comput. Surv., 11:121–137, 1979.
A. Crauser and K. Mehlhorn. LEDA-SM: Extending LEDA to secondary memory. In Proc. Workshop on Algorithm Engineering, 1999.
S. Huddleston and K. Mehlhorn. A new data structure for representing sorted lists. Acta Informatica, 17:157–184, 1982.
K. Mehlhorn and S. Näher. LEDA: A Platform for Combinatorial and Geometric Computing. Cambridge University Press, Cambridge, UK, 2000.
M.H. Overmars. The Design of Dynamic Data Structures, volume 156 of Lecture Notes Comput. Sci. Springer-Verlag, Heidelberg, West Germany, 1983.
O. Procopiuc, P.K. Agarwal, L. Arge, and J. S. Vitter. Bkd-tree: A dynamic scalable kd-tree. Manuscript, 2002.
J.T. Robinson. The K-D-B-tree: A search structure for large multidimensional dynamic indexes. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 10–18, 1981.
D.E. Vengro. and J. S. Vitter. Supporting I/O-efficient scientific computation in TPIE. In Proc. IEEE Symp. on Parallel and Distributed Computing, pages 74–77, 1995.
J. S. Vitter. External memory algorithms and data structures: Dealing with MASSIVE data. ACM Computing Surveys, 33(2):209–271, 2001.
J. S. Vitter and E.A. M. Shriver. Algorithms for parallel memory, I: Two-level memories. Algorithmica, 12(2–3):110–147, 1994.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Arge, L., Procopiuc, O., Scott Vitter, J. (2002). Implementing I/O-efficient Data Structures Using TPIE. In: Möhring, R., Raman, R. (eds) Algorithms — ESA 2002. ESA 2002. Lecture Notes in Computer Science, vol 2461. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45749-6_12
Download citation
DOI: https://doi.org/10.1007/3-540-45749-6_12
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44180-9
Online ISBN: 978-3-540-45749-7
eBook Packages: Springer Book Archive