publication . Preprint . 2004

The Persistent Buffer Tree : An I/O-efficient Index for Temporal Data

Dominic, Saju Jude; Sajith, G.;
Open Access English
  • Published: 14 Apr 2004
Abstract
In a variety of applications, we need to keep track of the development of a data set over time. For maintaining and querying this multi version data I/O-efficiently, external memory data structures are required. In this paper, we present a probabilistic self-balancing persistent data structure in external memory called the persistent buffer tree, which supports insertions, updates and deletions of data items at the present version and range queries for any version, past or present. The persistent buffer tree is I/O-optimal in the sense that the expected amortized I/O performance bounds are asymptotically the same as the deterministic amortized bounds of the (sin...
Subjects
free text keywords: Computer Science - General Literature, Computer Science - Databases, E.2, H.2.2, G.3
Download from

[1] A. Aggarwal and J. S. Vitter.: The input/output complexity of sorting and related problems. Communications of the ACM,31(9):1116-1127, 1988 [OpenAIRE]

[2] L. Arge.: The buffer tree, a new technique for optimal I/O algorithms. In Proceedings of the Fourth Workshop on Algorithms and Data Structures, pages 334-345, 1995.

[3] V. Kumar and E. J. Schwabe.: Improved algorithms and data structures for solving graph problems in external memory. In Proc. 8th IEEE SPDP, pages 169-76, 1996.

[4] B. Becker, S. Gschwind, T Ohler, B. Seeger and P. WidMayer.: An Asymptotically Optimal Multi-version B-Tree. VLDB Journal 5(4) , pages 264-275, 1996. [OpenAIRE]

[5] P. Varman and R. Verma.: An efficient multiversion access structure. IEEE Transactions on Knowledge and Data Engineering , 9(3), pages 391-409, 1997.

[6] B. Salzberg and V.J. Tsotras .: Comparison of access methods for time-evolving data. ACM Computing Surveys 31, pages 158-221. 1999.

[7] M.T. Goodrich, J. Tsay, D.E. Vengroff and J.S. Vitter.: External memory computational geometry. In Proc. IEEE Symp. on Foundations of Comp . Science, pages 714-723, 1993.

[8] Y. Chiang, M.T. Goodrich, R. Tamassia, D.E. Vengroff and J.S. Vitter.: External memory graph algorithms. In Proc. ACM -SIAM Symp. on Discrete Alg orithms, pages 139-149, 1995.

[9] L. Devroye.: On the height of the random m-ary tree. Random Structures and Alg orithms, Vol. 1, pages 191-203, 1990.

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue