Group updates for relaxed height-balanced trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Group updates for relaxed height-balanced trees

Full text

Pdf (1.19 MB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems table of contents

Philadelphia, Pennsylvania, United States

Pages: 358 - 367

Year of Publication: 1999

ISBN:1-58113-062-7

Authors

Lauri Malmi	Laboratory of Information Processing Science, Helsinki University of Technology, P.O. Box 5400, 02015 HUT, Espoo, Finland
Eljas Soisalon-Soininen	Laboratory of Information Processing Science, Helsinki University of Technology, P.O. Box 5400, 02015 HUT, Espoo, Finland

Sponsors

SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 19, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/303976.304011 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Mark R. Brown , Robert E. Tarjan, A Fast Merging Algorithm, Journal of the ACM (JACM), v.26 n.2, p.211-226, April 1979 [doi>10.1145/322123.322127]
	2	M.R. Brown, R.E. Tarjan, Design and analysis ot' a data structure for representing sorted lists. Siam Journal of Computing 9:3 (1980), 594-614.
	3	Hsi Chang , S. Sitharama Iyangar, Efficient algorithms to globally balance a binary search tree, Communications of the ACM, v.27 n.7, p.695-702, July 1984 [doi>10.1145/358105.358191]
	4	Alfonso F. Cárdenas, Analysis and performance of inverted data base structures, Communications of the ACM, v.18 n.5, p.253-263, May 1975 [doi>10.1145/360762.360766]
	5	C.S. Ellis, Concurrent search in AVL trees. IEEE Trans. on Computers C-29 (1980), 811-817.
	6	C. Faloutsos, S. Christodoulakis, Design of a signature file method that accounts for non-uniform occurrence and query frequencies. Proceedings of VLDB'85, Very Large Data Bases, pp. 165-170, 1985.
	7	Christos Faloutsos , H. V. Jagadish, Hybrid Index Organizations for Text Databases, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.310-327, March 23-27, 1992
	8	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	9	S D Lang , J R Driscoll , J H Jou, Batch insertion for tree structured file organizations—improving differential database representation, Information Systems, v.11 n.2, p.167-175, 1986 [doi>10.1016/0306-4379(86)90005-0]
	10	Kim S. Larsen , Eljas Soisalon-Soininen , Peter Widmayer, Relaxed Balance through Standard Rotations, Proceedings of the 5th International Workshop on Algorithms and Data Structures, p.450-461, August 06-08, 1997
	11	L. Malmi, On updating and balancing relaxed balanced search trees in main memory, PhD Thesis, Report TKO-A35, Helsinki University of Technology, Department of Computer Science and Engineering, Finland, 1997.
	12	Alistair Moffat , Ola Petersson , Nicholas C. Wormald, Sorting and/by Merging Finger Trees, Proceedings of the Third International Symposium on Algorithms and Computation, p.499-508, December 16-18, 1992
	13	C. Mohan , Inderpal Narang, Algorithms for creating indexes for very large tables without quiescing updates, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.361-370, June 02-05, 1992, San Diego, California, United States
	14	O. Nurmi , E. Soisalon-Soininen , D. Wood, Concurrency control in database structures with relaxed balance, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.170-176, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28677]
	15	O. Nurmi, E. Soisalon-Soininen, Chromatic binary trees: A structure for concurrent rebalancing. Acta Informatica 33 (1996), 547-557.
	16	Kerttu Pollari-Malmi , Eljas Soisalon-Soininen , Tatu Ylönen, Concurrency Control in B-Trees with Batch Updates, IEEE Transactions on Knowledge and Data Engineering, v.8 n.6, p.975-984, December 1996 [doi>10.1109/69.553166]
	17	M. Rossi, Concurrent full text database. Master's thesis, Department of Computer Science, Helsinki University of Technology, Finland, 1997.
	18	E. Soisalon-Soininen, P. Widmayer, Relaxed balancing in search trees. In: D.-Z. Du and K.-I.Ko, editors, Advances in Algorithms, Languages and Complexity: Essays in Honor of Ronald V. Book, Kluwer Academic Publishers, pp. 267-283, 1997.
	19	V. Srinivasan , Michael J. Carey, Performance of On-Line Index Construction Algorithms, Proceedings of the 3rd International Conference on Extending Database Technology: Advances in Database Technology, p.293-309, March 23-27, 1992
	20	Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
	21	Athanasios K Tsakalidis, AVL-trees for localized search, Information and Control, v.67 n.1-3, p.173-194, Oct./Nov./Dec. 1986 [doi>10.1016/S0019-9958(85)80034-6]
	22	T. Y15nen, An algorithm for full-text indexing. Report TKO-B75, Helsinki University of Technology, Deparment of Computer Science, 1992.

CITED BY 5

	Kim S. Larsen, Relaxed multi-way trees with group updates, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.93-101, May 2001, Santa Barbara, California, United States
	Eljas Soisalon-Soininen , Peter Widmayer, Single and bulk updates in stratified trees: an amortized and worst-case analysis, Computer science in perspective, Springer-Verlag New York, Inc., New York, NY, 2003
	Kim S. Larsen, Relaxed multi-way trees with group updates, Journal of Computer and System Sciences, v.66 n.4, p.657-670, 1 June 2003
	Heejin Park , Kunsoo Park , Yookun Cho, Deleting keys of B-trees in parallel, Journal of Parallel and Distributed Computing, v.64 n.9, p.1041-1050, September 2004
	Bin Lin , Jianwen Su, Handling frequent updates of moving objects, Proceedings of the 14th ACM international conference on Information and knowledge management, October 31-November 05, 2005, Bremen, Germany