Digital Symposium Collection 2000

Group Updates for Relaxed Height-Balanced Trees Lauri Malmi and Eljas Soisalon-Soininen   View Paper (PDF)   Return to Indexing Abstract A group update of a search tree means that a set of insertions or deletions are collected into a group in sorted order, and t.his group is brought into the tree as a single transaction. In this paper we present an efficient group-update algorithm for height-balanced binary search trees. The presented algorithm has two steps: First, the operations in the underlying group are performed without any balancing except for subgroups between two consecutive keys in the original tree. In this way the updates are made available as soon as possible without sacrif:ycing the logarithmic search time. In the second step the tree will be balanced, i.e., transformed into a tree satisfying the (local) balance criteria of height-balanced trees. Balancing is designed as a background process allowing the concurrent use of the structure. The balancing time is comparable with earlier results in cases when balancing is strictly connected with individual updates. References Note: References link to DBLP on the Web. [1] Mark R. Brown , Robert Endre Tarjan : A Fast Merging Algorithm. JACM 26(2) : 211-226(1979) [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) [3] Hsi Chang , S. Sitharama Iyengar : Efficient Algorithms to Globally Balance a Binary Search Tree. CACM 27(7) : 695-702(1984) [4] Alfonso F. Cardenas : Analysis and Performance of Inverted Data Base Structures. CACM 18(5) : 253-263(1975) [5] Carla Schlatter Ellis : Concurrent Search and Insertion in AVL Trees. IEEE Transactions on Computers 29(9) : 811-817(1980) [6] Christos Faloutsos , Stavros Christodoulakis : Design of a Signature File Method that Accounts for Non-Uniform Occurrence and Query Frequencies. VLDB 1985 : 165-170 [7] Christos Faloutsos , H. V. Jagadish : Hybrid Index Organizations for Text Databases. EDBT 1992 : 310-327 [8] Donald E. Knuth : The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X [9] Sheau-Dong Lang , James R. Driscoll , Jiann H. Jou : Batch Insertion for Tree Structured File Organizations - Improving Differential Database Reprensentation. IS 11(2) : 167-175(1986) [10] Kim S. Larsen , Eljas Soisalon-Soininen , Peter Widmayer : Relaxed Balance through Standard Rotations. WADS 1997 : 450-461 [11] ... [12] ... [13] C. Mohan , Inderpal Narang : Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates. SIGMOD Conference 1992 : 361-370 [14] Otto Nurmi , Eljas Soisalon-Soininen , Derick Wood : Concurrency Control in Database Structures with Relaxed Balance. PODS 1987 : 170-176 [15] Otto Nurmi , Eljas Soisalon-Soininen : Chromatic Binary Search Trees. A Structure for Concurrent Rebalancing. Acta Informatica 33(6) : 547-557(1996) [16] Kerttu Pollari-Malmi , Eljas Soisalon-Soininen , Tatu Ylönen : Concurrency Control in B-Trees with Batch Updates. TKDE 8(6) : 975-984(1996) [17] ... [18] ... [19] V. Srinivasan , Michael J. Carey : Performance of On-Line Index Construction Algorithms. EDBT 1992 : 293-309 [20] ... [21] Athanasios K. Tsakalidis : AVL-Trees for Localized Search. Information and Control 67(1-3) : 173-194(1985) [22] ... BIBTEX @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},    crossref  = {DBLP:conf/pods/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM