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

Summary: BATON overlays a balanced tree on a P2P network, supporting exact and range queries in O(log N) with approximately uniform node load. Sideways routing tables provide fault-tolerant repair despite single tree paths; updates cost amortized O(log N). (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 9536
Venue: VLDB
Year: 2005
Pagerank: 8.8160706e-05
Overall Rank: 2,278 | 84.38%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. H.V. Jagadish (National University of Singapore; University of Michigan)
2. Beng Chin Ooi (National University of Singapore; Singapore-MIT Alliance)
3. Quang Hieu Vu (Singapore-MIT Alliance)

BibTeX Citation

@article{jagadish_vldb05,
        title = {{BATON: A Balanced Tree Structure for Peer-to-Peer Networks}},
        author = {Jagadish, H.V. and Ooi, Beng Chin and Vu, Quang Hieu},
        journal = {PVLDB},
        series = {{VLDB} '05},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,800	A Scalable Data Platform for a Large Number of Small Applications	2009	CIDR	9.7290813e-05
2,411	Towards Elastic Transactional Cloud Storage with Range Query Support	2010	VLDB	8.6126258e-05
3,187	P-Ring: An Efficient and Robust P2P Range Index Structure	2007	SIGMOD	7.6555242e-05
3,429	Angle-based Space Partitioning for Efficient Parallel Skyline Computation	2008	SIGMOD	7.4203247e-05
4,791	Speeding up Search in Peer-to-Peer Networks with A Multi-way Tree Structure	2006	SIGMOD	6.5059395e-05
5,336	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	6.2612462e-05
5,732	Effective Keyword-based Selection of Relational Databases	2007	SIGMOD	6.1064568e-05
7,016	Minuet: A Scalable Distributed Multiversion B-Tree	2012	VLDB	5.7253247e-05
7,827	Efficient B-tree Based Indexing for Cloud Data Processing	2010	VLDB	5.5361352e-05
8,033	TI: An Efficient Indexing Mechanism for Real-Time Search on Tweets	2011	SIGMOD	5.5039566e-05
8,664	Just-In-Time Query Retrieval Over Partially Indexed Data on Structured P2P Overlays	2008	SIGMOD	5.3887668e-05
8,953	Delay Aware Querying with Seaweed	2006	VLDB	5.3458888e-05
9,589	A Framework for Supporting DBMS-like Indexes in the Cloud	2011	VLDB	5.2521633e-05
9,679	Cooperative XPath Caching	2008	SIGMOD	5.2365126e-05
12,421	Indexing Multi-dimensional Data in a Cloud System	2010	SIGMOD	5.093636e-05
12,553	Paths to Stardom: Calibrating the Potential of a Peer-based Data Management System	2008	SIGMOD	5.093636e-05
12,588	P3N: Profiling the Potential of a Peer-based Data Management System	2008	VLDB	5.093636e-05
12,677	Peer-to-Peer Similarity Search in Metric Spaces	2007	VLDB	5.093636e-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
219	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00024293529
1,438	Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems	2004	VLDB	0.00010787388
2,237	Approximate Range Selection Queries in Peer-to-Peer Systems	2003	CIDR	8.8901709e-05
2,552	RP*: A Family of Order-Preserving Scalable Distributed Data Structures	1994	VLDB	8.4284603e-05
3,454	Towards Self-Tuning Data Placement in Parallel Database Systems	2000	SIGMOD	7.4001286e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,594	Distributed Query Processing and Catalogs for Peer-to-Peer Systems	2003	CIDR
2	12,588	P3N: Profiling the Potential of a Peer-based Data Management System	2008	VLDB
3	8,657	An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs	2025	SIGMOD
4	9,712	Indexing data-oriented overlay networks	2005	VLDB
5	3,187	P-Ring: An Efficient and Robust P2P Range Index Structure	2007	SIGMOD
6	2,237	Approximate Range Selection Queries in Peer-to-Peer Systems	2003	CIDR
7	1,438	Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems	2004	VLDB
8	14,548	On B-Trees: Routing Schemes And Concurrency	1980	SIGMOD
9	2,001	A Practical Scalable Distributed B-Tree	2008	VLDB
10	4,791	Speeding up Search in Peer-to-Peer Networks with A Multi-way Tree Structure	2006	SIGMOD