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.6260609e-05
Overall Rank: 2,330 | 84.35%
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.5713615e-05
2,412	Towards Elastic Transactional Cloud Storage with Range Query Support	2010	VLDB	8.5070443e-05
3,261	P-Ring: An Efficient and Robust P2P Range Index Structure	2007	SIGMOD	7.4807048e-05
3,414	Angle-based Space Partitioning for Efficient Parallel Skyline Computation	2008	SIGMOD	7.3210151e-05
4,909	Speeding up Search in Peer-to-Peer Networks with A Multi-way Tree Structure	2006	SIGMOD	6.3569837e-05
5,466	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	6.1192481e-05
5,846	Effective Keyword-based Selection of Relational Databases	2007	SIGMOD	5.9701759e-05
7,156	Minuet: A Scalable Distributed Multiversion B-Tree	2012	VLDB	5.5953223e-05
7,974	Efficient B-tree Based Indexing for Cloud Data Processing	2010	VLDB	5.4125153e-05
8,200	TI: An Efficient Indexing Mechanism for Real-Time Search on Tweets	2011	SIGMOD	5.3779156e-05
8,833	Just-In-Time Query Retrieval Over Partially Indexed Data on Structured P2P Overlays	2008	SIGMOD	5.2661819e-05
9,121	Delay Aware Querying with Seaweed	2006	VLDB	5.2253958e-05
9,773	A Framework for Supporting DBMS-like Indexes in the Cloud	2011	VLDB	5.1319322e-05
9,862	Cooperative XPath Caching	2008	SIGMOD	5.1167675e-05
12,718	Indexing Multi-dimensional Data in a Cloud System	2010	SIGMOD	4.9769913e-05
12,849	Paths to Stardom: Calibrating the Potential of a Peer-based Data Management System	2008	SIGMOD	4.9769913e-05
12,884	P3N: Profiling the Potential of a Peer-based Data Management System	2008	VLDB	4.9769913e-05
12,973	Peer-to-Peer Similarity Search in Metric Spaces	2007	VLDB	4.9769913e-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.00023915204
1,471	Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems	2004	VLDB	0.00010554122
2,289	Approximate Range Selection Queries in Peer-to-Peer Systems	2003	CIDR	8.6890827e-05
2,594	RP*: A Family of Order-Preserving Scalable Distributed Data Structures	1994	VLDB	8.2421304e-05
3,511	Towards Self-Tuning Data Placement in Parallel Database Systems	2000	SIGMOD	7.2414794e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,697	Distributed Query Processing and Catalogs for Peer-to-Peer Systems	2003	CIDR
2	12,884	P3N: Profiling the Potential of a Peer-based Data Management System	2008	VLDB
3	8,828	An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs	2025	SIGMOD
4	9,892	Indexing data-oriented overlay networks	2005	VLDB
5	3,261	P-Ring: An Efficient and Robust P2P Range Index Structure	2007	SIGMOD
6	2,289	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,851	On B-Trees: Routing Schemes And Concurrency	1980	SIGMOD
9	2,018	A Practical Scalable Distributed B-Tree	2008	VLDB
10	4,909	Speeding up Search in Peer-to-Peer Networks with A Multi-way Tree Structure	2006	SIGMOD