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,826 | 3.91%
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
4,864	A General Solution of the n-dimensional B-tree Problem	1995	SIGMOD	6.5381219e-05
9,625	An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs	2025	SIGMOD	5.3018378e-05
14,313	A Discipline for Robustness or Storage Reduction in Binary Search Trees	1983	PODS	-
2,714	Utilization of B-trees with Inserts, Deletes and Modifies	1989	PODS	8.2738666e-05
10,565	Efficient Concurrent Updates to Persistent Randomized Binary Search Trees	2025	VLDB	5.1725247e-05
14,292	An Empirical Comparison of B-Trees, Compact B-Trees and Multiway Trees	1984	SIGMOD	-
13,086	Experiments With B-Tree Reorganization	1980	SIGMOD	5.1725247e-05
12,988	Concurrency Control in Database Structures with Relaxed Balance	1987	PODS	5.1725247e-05
12,918	Uncoupling Updating and Rebalancing in Chromatic Binary Search Trees	1991	PODS	5.1725247e-05
12,717	Group Updates for Relaxed Height-Balanced Trees	1999	PODS	5.1725247e-05