Group Updates for Relaxed Height-Balanced Trees.

@inproceedings{DBLP:conf/pods/MalmiS99,
  author    = {Lauri Malmi and
               Eljas Soisalon-Soininen},
  title     = {Group Updates for Relaxed Height-Balanced Trees},
  booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1999},
  isbn      = {1-58113-062-7},
  pages     = {358-367},
  ee        = {http://doi.acm.org/10.1145/303976.304011, db/conf/pods/MalmiS99.html},
  crossref  = {DBLP:conf/pods/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1999 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD DiSC

• 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/DISC001 or /cdrom

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 DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[1]

Mark R. Brown, Robert Endre Tarjan: A Fast Merging Algorithm. J. ACM 26(2): 211-226(1979) BibTeX

[2]

Mark R. Brown, Robert Endre Tarjan: Design and Analysis of a Data Structure for Representing Sorted Lists. SIAM J. Comput. 9(3): 594-614(1980) BibTeX

[3]

Hsi Chang, S. Sitharama Iyengar: Efficient Algorithms to Globally Balance a Binary Search Tree. Commun. ACM 27(7): 695-702(1984) BibTeX

[4]

Alfonso F. Cardenas: Analysis and Performance of Inverted Data Base Structures. Commun. ACM 18(5): 253-263(1975) BibTeX

[5]

Carla Schlatter Ellis: Concurrent Search and Insertion in AVL Trees. IEEE Trans. Computers 29(9): 811-817(1980) BibTeX

[6]

Christos Faloutsos, Stavros Christodoulakis: Design of a Signature File Method that Accounts for Non-Uniform Occurrence and Query Frequencies. VLDB 1985: 165-170 BibTeX

[7]

Christos Faloutsos, H. V. Jagadish: Hybrid Index Organizations for Text Databases. EDBT 1992: 310-327 BibTeX

[8]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX

[9]

Sheau-Dong Lang, James R. Driscoll, Jiann H. Jou: Batch Insertion for Tree Structured File Organizations - Improving Differential Database Reprensentation. Inf. Syst. 11(2): 167-175(1986) BibTeX

[10]

Kim S. Larsen, Eljas Soisalon-Soininen, Peter Widmayer: Relaxed Balance through Standard Rotations. WADS 1997: 450-461 BibTeX

[11]

...

[12]

...

[13]

C. Mohan, Inderpal Narang: Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates. SIGMOD Conference 1992: 361-370 BibTeX

[14]

Otto Nurmi, Eljas Soisalon-Soininen, Derick Wood: Concurrency Control in Database Structures with Relaxed Balance. PODS 1987: 170-176 BibTeX

[15]

Otto Nurmi, Eljas Soisalon-Soininen: Chromatic Binary Search Trees. A Structure for Concurrent Rebalancing. Acta Inf. 33(6): 547-557(1996) BibTeX

[16]

Kerttu Pollari-Malmi, Eljas Soisalon-Soininen, Tatu Ylönen: Concurrency Control in B-Trees with Batch Updates. IEEE Trans. Knowl. Data Eng. 8(6): 975-984(1996) BibTeX

[17]

...

[18]

...

[19]

V. Srinivasan, Michael J. Carey: Performance of On-Line Index Construction Algorithms. EDBT 1992: 293-309 BibTeX

[20]

...

[21]

Athanasios K. Tsakalidis: AVL-Trees for Localized Search. Information and Control 67(1-3): 173-194(1985) BibTeX

[22]

...