Group Updates for Relaxed Height-Balanced Trees

Summary: Two-phase algorithm for sorted batch updates into height-balanced BSTs: eagerly apply updates without global rebalancing (only local subgroups between adjacent original keys) to keep O(log n) searches. Background local rebalancing restores height-balance with comparable cost. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1188
Venue: PODS
Year: 1999
Pagerank: 5.093636e-05
Overall Rank: 12,901 | 11.49%
DOI: 10.1145/303976.304011

Incoming Non-self Citations Over Time

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

Authors

1. Lauri Malmi (Helsinki University of Technology)
2. Eljas Soisalon-Soininen (ETH Zurich; Helsinki University of Technology; Max Planck Institute)

BibTeX Citation

@inproceedings{malmi_pods99,
        address = {New York, NY, USA},
        series = {{PODS} '99},
        title = {{Group Updates for Relaxed Height-Balanced Trees}},
        url = {https://dl.acm.org/doi/10.1145/303976.304011},
        doi = {10.1145/303976.304011},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Malmi, Lauri and Soisalon-Soininen, Eljas},
        year = {1999}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
924	Algorithms for Creating Indexes for Very Large Tables Without Quiescing Updates	1992	SIGMOD	0.00013185068
3,929	Design of a Signature File Method that Accounts for Non-Uniform Occurrence and Query Frequencies.	1985	VLDB	7.0104302e-05
13,175	Concurrency Control in Database Structures with Relaxed Balance	1987	PODS	5.093636e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,559	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB
2	10,674	Parallel kd-tree with Batch Updates	2025	SIGMOD
3	2,605	Lazy Updates for Distributed Search Structure	1993	SIGMOD
4	9,234	On Optimal Node Splitting for R-trees	1998	VLDB
5	464	Concurrent Operations on B-Trees with Overtaking	1985	PODS
6	13,175	Concurrency Control in Database Structures with Relaxed Balance	1987	PODS
7	14,500	A Discipline for Robustness or Storage Reduction in Binary Search Trees	1983	PODS
8	10,824	Efficient Concurrent Updates to Persistent Randomized Binary Search Trees	2025	VLDB
9	13,103	Uncoupling Updating and Rebalancing in Chromatic Binary Search Trees	1991	PODS
10	14,013	Relaxed Multi-Way Trees with Group Updates	2001	PODS