BATON: A Balanced Tree Structure for Peer-to-Peer Networks

Summary: BATON: a balanced-tree overlay for P2P networks enabling exact and range queries in O(log N). Achieves near-uniform load and fault-tolerant repair via sideways routing tables, while maintaining amortized O(log N) updates and validated by experiments. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9345
Venue: VLDB
Year: 2005
Pagerank: 9.2201128e-05
Overall Rank: 2,240 | 84.42%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,713	A Scalable Data Platform for a Large Number of Small Applications	2009	CIDR	0.0001080383
2,261	Towards Elastic Transactional Cloud Storage with Range Query Support	2010	VLDB	9.1629995e-05
3,165	P-Ring: An Efficient and Robust P2P Range Index Structure	2007	SIGMOD	7.4539655e-05
3,621	Angle-based Space Partitioning for Efficient Parallel Skyline Computation	2008	SIGMOD	6.9078084e-05
4,871	Speeding up Search in Peer-to-Peer Networks with A Multi-way Tree Structure	2006	SIGMOD	5.8613852e-05
5,317	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	5.5719038e-05
5,672	Effective Keyword-based Selection of Relational Databases	2007	SIGMOD	5.3784128e-05
6,841	Minuet: A Scalable Distributed Multiversion B-Tree	2012	VLDB	4.9105477e-05
7,661	Just-In-Time Query Retrieval Over Partially Indexed Data on Structured P2P Overlays	2008	SIGMOD	4.6862657e-05
7,923	Efficient B-tree Based Indexing for Cloud Data Processing	2010	VLDB	4.6155204e-05
7,999	TI: An Efficient Indexing Mechanism for Real-Time Search on Tweets	2011	SIGMOD	4.6100392e-05
8,662	Delay Aware Querying with Seaweed	2006	VLDB	4.4722862e-05
9,349	A Framework for Supporting DBMS-like Indexes in the Cloud	2011	VLDB	4.3526413e-05
9,532	Cooperative XPath Caching	2008	SIGMOD	4.3270626e-05
12,226	Indexing Multi-dimensional Data in a Cloud System	2010	SIGMOD	4.1945683e-05
12,360	Paths to Stardom: Calibrating the Potential of a Peer-based Data Management System	2008	SIGMOD	4.1945683e-05
12,394	P3N: Profiling the Potential of a Peer-based Data Management System	2008	VLDB	4.1945683e-05
12,484	Peer-to-Peer Similarity Search in Metric Spaces	2007	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
233	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00032021526
1,347	Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems	2004	VLDB	0.00012456657
1,680	Approximate Range Selection Queries in Peer-to-Peer Systems	2003	CIDR	0.00010931115
2,353	RP*: A Family of Order-Preserving Scalable Distributed Data Structures	1994	VLDB	8.9752351e-05
3,401	Towards Self-Tuning Data Placement in Parallel Database Systems	2000	SIGMOD	7.1400085e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,858	Distributed Query Processing and Catalogs for Peer-to-Peer Systems	2003	CIDR	6.6913167e-05
12,394	P3N: Profiling the Potential of a Peer-based Data Management System	2008	VLDB	4.1945683e-05
9,641	An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs	2025	SIGMOD	4.3109001e-05
9,545	Indexing data-oriented overlay networks	2005	VLDB	4.3263737e-05
3,165	P-Ring: An Efficient and Robust P2P Range Index Structure	2007	SIGMOD	7.4539655e-05
1,680	Approximate Range Selection Queries in Peer-to-Peer Systems	2003	CIDR	0.00010931115
1,347	Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems	2004	VLDB	0.00012456657
14,347	On B-Trees: Routing Schemes And Concurrency	1980	SIGMOD	-
1,985	A Practical Scalable Distributed B-Tree	2008	VLDB	9.8569956e-05
4,871	Speeding up Search in Peer-to-Peer Networks with A Multi-way Tree Structure	2006	SIGMOD	5.8613852e-05