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: 1227
Venue: PODS
Year: 2001
Pagerank: -
Overall Rank: 13,812 | 3.92%
DOI: -

Incoming Non-self Citations Over Time

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

Authors

1. Kim S. Larsen

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	Pagerank
282	Concurrent Operations on B-Trees with Overtaking	1985	PODS	0.00029057817
9,641	An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs	2025	SIGMOD	4.3109001e-05
14,299	A Discipline for Robustness or Storage Reduction in Binary Search Trees	1983	PODS	-
2,975	Utilization of B-trees with Inserts, Deletes and Modifies	1989	PODS	7.7893243e-05
10,556	Efficient Concurrent Updates to Persistent Randomized Binary Search Trees	2025	VLDB	4.1945683e-05
14,278	An Empirical Comparison of B-Trees, Compact B-Trees and Multiway Trees	1984	SIGMOD	-
13,073	Experiments With B-Tree Reorganization	1980	SIGMOD	4.1945683e-05
12,977	Concurrency Control in Database Structures with Relaxed Balance	1987	PODS	4.1945683e-05
12,908	Uncoupling Updating and Rebalancing in Chromatic Binary Search Trees	1991	PODS	4.1945683e-05
12,708	Group Updates for Relaxed Height-Balanced Trees	1999	PODS	4.1945683e-05