Relaxed Multi-Way Trees with Group Updates

Summary: Relaxed (a,b)-trees supporting insertion, deletion and group insertion with interspersed delayed rebalancing, achieving optimal amortized rebalancing bounds: O(1) per insert/delete and O(log g) for a group of size g. Also gives a binary-tree scheme with the same complexities, improving prior work. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1226
Venue: PODS
Year: 2001
Pagerank: -
Overall Rank: 14,013 | 3.86%
DOI: 10.1145/375551.375566

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Kim S. Larsen (Odense University; University of Southern Denmark)

BibTeX Citation

@inproceedings{larsen_pods01,
        address = {New York, NY, USA},
        series = {{PODS} '01},
        title = {{Relaxed Multi-Way Trees with Group Updates}},
        url = {https://dl.acm.org/doi/10.1145/375551.375566},
        doi = {10.1145/375551.375566},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Larsen, Kim S.},
        year = {2001}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,914	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD
2	8,657	An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs	2025	SIGMOD
3	14,500	A Discipline for Robustness or Storage Reduction in Binary Search Trees	1983	PODS
4	2,738	Utilization of B-trees with Inserts, Deletes and Modifies	1989	PODS
5	10,824	Efficient Concurrent Updates to Persistent Randomized Binary Search Trees	2025	VLDB
6	14,479	An Empirical Comparison of B-Trees, Compact B-Trees and Multiway Trees	1984	SIGMOD
7	13,274	Experiments With B-Tree Reorganization	1980	SIGMOD
8	13,175	Concurrency Control in Database Structures with Relaxed Balance	1987	PODS
9	13,103	Uncoupling Updating and Rebalancing in Chromatic Binary Search Trees	1991	PODS
10	12,901	Group Updates for Relaxed Height-Balanced Trees	1999	PODS