An Asymptotically Optimal Multiversion B-Tree.

@article{DBLP:journals/vldb/BeckerGOSW96,
  author    = {Bruno Becker and
               Stephan Gschwind and
               Thomas Ohler and
               Bernhard Seeger and
               Peter Widmayer},
  title     = {An Asymptotically Optimal Multiversion B-Tree},
  journal   = {VLDB J.},
  volume    = {5},
  number    = {4},
  year      = {1996},
  pages     = {264-275},
  ee        = {db/journals/vldb/BeckerGOSW96.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Key Words

Copyright © 1996 by Springer, Berlin, Heidelberg. Permission to make digital or hard copies of the abstract is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice along with the full citation.

Online Edition (Springer)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An4-1 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[Barghouti and Kaiser 1991]

Naser S. Barghouti, Gail E. Kaiser: Concurrency Control in Advanced Database Applications. ACM Comput. Surv. 23(3): 269-317(1991) BibTeX

[Becker et al. 1993]

Bruno Becker, Stephan Gschwind, Thomas Ohler, Bernhard Seeger, Peter Widmayer: On Optimal Multiversion Access Structures. SSD 1993: 123-141 BibTeX

[Beckmann et al. 1990]

Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331 BibTeX

[Bentley 1977]

...

[Bernstein et al. 1987]

Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX

[Clifford and Ariav 1986]

...

[Driscoll et al. 1989]

James R. Driscoll, Neil Sarnak, Daniel Dominic Sleator, Robert Endre Tarjan: Making Data Structures Persistent. J. Comput. Syst. Sci. 38(1): 86-124(1989) BibTeX

[Easton 1986]

Malcolm C. Easton: Key-Sequence Data Sets on Inedible Storage. IBM Journal of Research and Development 30(3): 230-241(1986) BibTeX

[Elmasri et al. 1990]

Ramez Elmasri, Gene T. J. Wuu, Yeong-Joon Kim: The Time Index: An Access Structure for Temporal Data. VLDB 1990: 1-12 BibTeX

[Elmasri et al. 1991]

Ramez Elmasri, Yeong-Joon Kim, Gene T. J. Wuu: Efficient Implementation Techniques For the Time Index. ICDE 1991: 102-111 BibTeX

[Freeston 1987]

Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269 BibTeX

[Gonnet and Baeza-Yates 1991]

...

[Greene 1989]

Diane Greene: An Implementation and Performance Analysis of Spatial Data Access Methods. ICDE 1989: 606-615 BibTeX

[Günther and Bilmes 1991]

Oliver Günther, Jeff Bilmes: Tree-Based Access Methods for Spatial Databases: Implementation and Performance Evaluation. IEEE Trans. Knowl. Data Eng. 3(3): 342-356(1991) BibTeX

[Guttman 1984]

Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX

[Huddleston and Mehlhorn 1982]

Scott Huddleston, Kurt Mehlhorn: A New Data Structure for Representing Sorted Lists. Acta Inf. 17: 157-184(1982) BibTeX

[Kanellakis et al. 1993]

Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter: Indexing for Data Models with Constraints and Classes. PODS 1993: 233-243 BibTeX

[Katz 1990]

Randy H. Katz: Towards a Unified Framework for Version Modeling in Engineering Databases. ACM Comput. Surv. 22(4): 375-408(1990) BibTeX

[Kolovson and Stonebraker 1989]

Curtis P. Kolovson, Michael Stonebraker: Indexing Techniques for Historical Databases. ICDE 1989: 127-137 BibTeX

[Kolovson and Stonebraker 1991]

Curtis P. Kolovson, Michael Stonebraker: Segment Indexes: Dynamic Indexing Techniques for Multi-Dimensional Interval Data. SIGMOD Conference 1991: 138-147 BibTeX

[Lanka and Mays 1991]

Sitaram Lanka, Eric Mays: Fully Persistent B+-trees. SIGMOD Conference 1991: 426-435 BibTeX

[Lomet and Salzberg 1989]

David B. Lomet, Betty Salzberg: Access Methods for Multiversion Data. SIGMOD Conference 1989: 315-324 BibTeX

[Lomet and Salzberg 1990]

David B. Lomet, Betty Salzberg: The Performance of a Multiversion Access Method. SIGMOD Conference 1990: 353-363 BibTeX

[Mehlhorn and Tsakalidis 1990]

Kurt Mehlhorn, Athanasios K. Tsakalidis: Data Structures. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A) 1990: 301-342 BibTeX

[Sedgewick 1988]

Robert Sedgewick: Algorithms, 2nd Edition. Addison-Wesley 1988, ISBN 0-201-06673-4
BibTeX

[Segev and Gunadhi 1989]

Arie Segev, Himawan Gunadhi: Event-Join Optimization in Temporal Relational Databases. VLDB 1989: 205-215 BibTeX

[Tansel et al. 1993]

Abdullah Uz Tansel, James Clifford, Shashi K. Gadia, Sushil Jajodia, Arie Segev, Richard T. Snodgrass (Eds.): Temporal Databases: Theory, Design, and Implementation. Benjamin/Cummings 1993, ISBN 0-8053-2413-5
Contents BibTeX

[Vitter 1991]

Jeffrey Scott Vitter: Efficient Memory Access in Large-Scale Computation. STACS 1991: 26-41 BibTeX

Referenced by

1. Peter Muth, Patrick E. O'Neil, Achim Pick, Gerhard Weikum: The LHAM Log-Structured History Data Access Method. VLDB J. 8(3-4): 199-221(2000)
2. Simonas Saltenis, Christian S. Jensen, Scott T. Leutenegger, Mario A. Lopez: Indexing the Positions of Continuously Moving Objects. SIGMOD Conference 2000: 331-342
3. Pankaj K. Agarwal, Lars Arge, Jeff Erickson: Indexing Moving Points. PODS 2000: 175-186
4. Jochen Van den Bercken, Martin Schneider, Bernhard Seeger: Plug&Join: An easy-to-use Generic Algorithm for Efficiently Processing Equi and Non-Equi Joins. EDBT 2000: 495-509
5. Andrew U. Frank, Stéphane Grumbach, Ralf Hartmut Güting, Christian S. Jensen, Manolis Koubarakis, Nikos A. Lorentzos, Yannis Manolopoulos, Enrico Nardelli, Barbara Pernici, Hans-Jörg Schek, Michel Scholl, Timos K. Sellis, Babis Theodoulidis, Peter Widmayer: Chorochronos: A Research Network for Spatiotemporal Database Systems. SIGMOD Record 28(3): 12-21(1999)
6. George Kollios, Dimitrios Gunopulos, Vassilis J. Tsotras: On Indexing Mobile Objects. PODS 1999: 261-272
7. Anil Kumar, Vassilis J. Tsotras, Christos Faloutsos: Designing Access Methods for Bitemporal Databases. IEEE Trans. Knowl. Data Eng. 10(1): 1-20(1998)
8. Vassilis J. Tsotras, Christian S. Jensen, Richard T. Snodgrass: An Extensible Notation for Spatiotemporal Index Queries. SIGMOD Record 27(1): 47-53(1998)
9. Peter Muth, Patrick E. O'Neil, Achim Pick, Gerhard Weikum: Design, Implementation, and Performance of the LHAM Log-Structured History Data Access Method. VLDB 1998: 452-463
10. Yannis Theodoridis, Timos K. Sellis, Apostolos Papadopoulos, Yannis Manolopoulos: Specifications for Efficient Indexing in Spatiotemporal Databases. SSDBM 1998: 123-132
11. Jeffrey Scott Vitter: External Memory Algorithms. PODS 1998: 119-128
12. Jochen Van den Bercken, Bernhard Seeger, Peter Widmayer: A Generic Approach to Bulk Loading Multidimensional Index Structures. VLDB 1997: 406-415