Uncoupling Updating and Rebalancing in Chromatic Binary Search Trees.
Otto Nurmi, Eljas Soisalon-Soininen:
Uncoupling Updating and Rebalancing in Chromatic Binary Search Trees.
PODS 1991: 192-198@inproceedings{DBLP:conf/pods/NurmiS91,
author = {Otto Nurmi and
Eljas Soisalon-Soininen},
title = {Uncoupling Updating and Rebalancing in Chromatic Binary Search
Trees},
booktitle = {Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on
Principles of Database Systems, May 29-31, 1991, Denver, Colorado},
publisher = {ACM Press},
year = {1991},
isbn = {0-89791-430-9},
pages = {192-198},
ee = {http://doi.acm.org/10.1145/113413.113430, db/conf/pods/NurmiS91.html},
crossref = {DBLP:conf/pods/91},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
In order to gain maximal efficiency of the concurrent use of search trees
the number of nodes to be locked at a time should be as small as possible,
and the locks should be released aa soon aa possible. We propose a new
rebalancing method for binary search treea that allows rebalancing to be
uncoupled from updating, so as to make updating faster. The trees we use
are obtained by relaxing the balance conditions of red-black trees.
When not involved with updating, the rebalancing task can be performed
as a shadow process being active all the time, or it can be performed
outside rush hours, at night, for example.
Copyright © 1991 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.
Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98.
and ...
Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings.
and ...
BibTeX
Printed Edition
Proceedings of the Tenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 29-31, 1991, Denver, Colorado.
ACM Press 1991, ISBN 0-89791-430-9
Contents BibTeX
[Index Terms]
[Full Text in PDF Format, 707 KB]
References
- [1]
- ...
- [2]
- Rudolf Bayer:
Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms.
Acta Inf. 1: 290-306(1972) BibTeX
- [3]
- Edsger W. Dijkstra, Leslie Lamport, Alain J. Martin, Carel S. Scholten, Elisabeth F. M. Steffens:
On-the-Fly Garbage Collection: An Exercise in Cooperation.
Commun. ACM 21(11): 966-975(1978) BibTeX
- [4]
- ...
- [5]
- Carla Schlatter Ellis:
Concurrent Search and Insertion in 2-3 Trees.
Acta Inf. 14: 63-86,(1980) BibTeX
- [6]
- Leonidas J. Guibas, Robert Sedgewick:
A Dichromatic Framework for Balanced Trees.
FOCS 1978: 8-21 BibTeX
- [7]
- Joep L. W. Kessels:
On-the-Fly Optimization of Data Structures.
Commun. ACM 26(11): 895-901(1983) BibTeX
- [8]
- H. T. Kung, Philip L. Lehman:
Concurrent Manipulation of Binary Search Trees.
ACM Trans. Database Syst. 5(3): 354-382(1980) BibTeX
- [9]
- Udi Manber, Richard E. Ladner:
Concurrency Control In a Dynamic Search Structure.
ACM Trans. Database Syst. 9(3): 439-455(1984) BibTeX
- [10]
- Edward M. McCreight:
Priority Search Trees.
SIAM J. Comput. 14(2): 257-276(1985) BibTeX
- [11]
- Otto Nurmi, Eljas Soisalon-Soininen, Derick Wood:
Concurrency Control in Database Structures with Relaxed Balance.
PODS 1987: 170-176 BibTeX
- [12]
- Neil Sarnak, Robert Endre Tarjan:
Planar Point Location Using Persistent Search Trees.
Commun. ACM 29(7): 669-679(1986) BibTeX
- [13]
- Quentin F. Stout, Bette L. Warren:
Tree Rebalancing in Optimal Time and Space.
Commun. ACM 29(9): 902-908(1986) BibTeX
- [14]
- Robert Endre Tarjan:
Updating a Balanced Search Tree in O(1) Rotations.
Inf. Process. Lett. 16(5): 253-257(1983) BibTeX
- [15]
- ...
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:03 2009
