Lazy Updates for Distributed Search Structure

Summary: Lazy updates for distributed search structures enable scalable, low-overhead replication and high concurrency. Avoids synchronization unlike eager updates, easing implementation; demonstrated on the dB-tree (distributed B+ tree) with a general correctness framework. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2654
Venue: SIGMOD
Year: 1993
Pagerank: 9.2209967e-05
Overall Rank: 2,238 | 84.44%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Theodore Johnson
2. Padmashree Krishna

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,353	RP*: A Family of Order-Preserving Scalable Distributed Data Structures	1994	VLDB	8.9752351e-05
2,963	Distributed File Organization with Scalable Cost/Performance	1994	SIGMOD	7.8097631e-05
3,401	Towards Self-Tuning Data Placement in Parallel Database Systems	2000	SIGMOD	7.1400085e-05
3,804	Distributing a Search Tree Among a Growing Number of Processors	1994	SIGMOD	6.7525564e-05
3,962	Guaranteeing Correctness and Availability in P2P Range Indices	2005	SIGMOD	6.5876809e-05
8,662	Delay Aware Querying with Seaweed	2006	VLDB	4.4722862e-05
12,773	Finding Data in the Neighborhood	1997	VLDB	4.1945683e-05

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
282	Concurrent Operations on B-Trees with Overtaking	1985	PODS	0.00029057817
2,975	Utilization of B-trees with Inserts, Deletes and Modifies	1989	PODS	7.7893243e-05
5,239	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS	5.6106291e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,605	Lazy Evaluation of Transactions in Database Systems	2014	SIGMOD	6.9281695e-05
8,641	Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency	2005	SIGMOD	4.4785985e-05
5,524	Replication and Consistency: Being Lazy Helps Sometimes	1997	PODS	5.4601032e-05
1,901	Extendible Hashing for Concurrent Operations and Distributed Data	1983	PODS	0.00010159096
10,562	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB	4.1945683e-05
10,556	Efficient Concurrent Updates to Persistent Randomized Binary Search Trees	2025	VLDB	4.1945683e-05
12,977	Concurrency Control in Database Structures with Relaxed Balance	1987	PODS	4.1945683e-05
2,609	Update Propagation Protocols For Replicated Databases	1999	SIGMOD	8.4582324e-05
3,804	Distributing a Search Tree Among a Growing Number of Processors	1994	SIGMOD	6.7525564e-05
796	Fast Algorithms for Maintaining Replica Consistency in Lazy Master Replicated Databases	1999	VLDB	0.00016595815