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: h13efb4090b66fc88
Venue: VLDB
Year: 2005
Pagerank: 8.6301365e-05
Overall Rank: 2,327 | 84.36%
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,816	A Scalable Data Platform for a Large Number of Small Applications	2009	CIDR	9.575848e-05
2,411	Towards Elastic Transactional Cloud Storage with Range Query Support	2010	VLDB	8.5108707e-05
3,260	P-Ring: An Efficient and Robust P2P Range Index Structure	2007	SIGMOD	7.4842462e-05
3,414	Angle-based Space Partitioning for Efficient Parallel Skyline Computation	2008	SIGMOD	7.3244819e-05
4,908	Speeding up Search in Peer-to-Peer Networks with A Multi-way Tree Structure	2006	SIGMOD	6.3599944e-05
5,462	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	6.1221387e-05
5,845	Effective Keyword-based Selection of Relational Databases	2007	SIGMOD	5.9729417e-05
7,153	Minuet: A Scalable Distributed Multiversion B-Tree	2012	VLDB	5.5979342e-05
7,970	Efficient B-tree Based Indexing for Cloud Data Processing	2010	VLDB	5.4150774e-05
8,192	TI: An Efficient Indexing Mechanism for Real-Time Search on Tweets	2011	SIGMOD	5.3804626e-05
8,824	Just-In-Time Query Retrieval Over Partially Indexed Data on Structured P2P Overlays	2008	SIGMOD	5.268676e-05
9,112	Delay Aware Querying with Seaweed	2006	VLDB	5.2278394e-05
9,768	A Framework for Supporting DBMS-like Indexes in the Cloud	2011	VLDB	5.1343627e-05
9,855	Cooperative XPath Caching	2008	SIGMOD	5.1191909e-05
12,712	Indexing Multi-dimensional Data in a Cloud System	2010	SIGMOD	4.9793485e-05
12,843	Paths to Stardom: Calibrating the Potential of a Peer-based Data Management System	2008	SIGMOD	4.9793485e-05
12,878	P3N: Profiling the Potential of a Peer-based Data Management System	2008	VLDB	4.9793485e-05
12,967	Peer-to-Peer Similarity Search in Metric Spaces	2007	VLDB	4.9793485e-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
229	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00023911856
1,471	Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems	2004	VLDB	0.00010559076
2,287	Approximate Range Selection Queries in Peer-to-Peer Systems	2003	CIDR	8.6931935e-05
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

Semantically Similar Papers

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