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: he26eae160e34e85f
Venue: SIGMOD
Year: 1993
Pagerank: 8.1636113e-05
Overall Rank: 2,658 | 82.14%
DOI: 10.1145/170035.170085

Incoming Non-self Citations Over Time

Authors

1. Theodore Johnson (University of Florida)
2. Padmashree Krishna (University of Florida)

BibTeX Citation

@inproceedings{johnson_sigmod93,
        title = {{Lazy Updates for Distributed Search Structure}},
        author = {Johnson, Theodore and Krishna, Padmashree},
        series = {{SIGMOD} '93},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/170035.170085},
        url = {https://dl.acm.org/doi/10.1145/170035.170085},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,592	RP*: A Family of Order-Preserving Scalable Distributed Data Structures	1994	VLDB	8.2460099e-05
3,511	Towards Self-Tuning Data Placement in Parallel Database Systems	2000	SIGMOD	7.244841e-05
4,163	Distributing a Search Tree Among a Growing Number of Processors	1994	SIGMOD	6.7683361e-05
4,467	Distributed File Organization with Scalable Cost/Performance	1994	SIGMOD	6.5865346e-05
5,556	Guaranteeing Correctness and Availability in P2P Range Indices	2005	SIGMOD	6.0858703e-05
9,112	Delay Aware Querying with Seaweed	2006	VLDB	5.2278394e-05
13,257	Finding Data in the Neighborhood	1997	VLDB	4.9793485e-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
471	Concurrent Operations on B-Trees with Overtaking	1985	PODS	0.0001769727
2,791	Utilization of B-trees with Inserts, Deletes and Modifies	1989	PODS	8.009544e-05
5,661	A Framework for the Performance Analysis of Concurrent B-tree Algorithms	1990	PODS	6.0475065e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,093	Lazy Evaluation of Transactions in Database Systems	2014	SIGMOD
2	9,029	Lazy XML Updates: Laziness as a Virtue of Update and Structural Join Efficiency	2005	SIGMOD
3	6,272	Replication and Consistency: Being Lazy Helps Sometimes	1997	PODS
4	3,176	Extendible Hashing for Concurrent Operations and Distributed Data	1983	PODS
5	11,237	FB+-tree: A Memory-Optimized B+-tree with Latch-Free Update	2025	VLDB
6	11,232	Efficient Concurrent Updates to Persistent Randomized Binary Search Trees	2025	VLDB
7	13,465	Concurrency Control in Database Structures with Relaxed Balance	1987	PODS
8	2,529	Update Propagation Protocols For Replicated Databases	1999	SIGMOD
9	4,163	Distributing a Search Tree Among a Growing Number of Processors	1994	SIGMOD
10	1,168	Fast Algorithms for Maintaining Replica Consistency in Lazy Master Replicated Databases	1999	VLDB