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.5978068e-05
Overall Rank: 2,343 | 84.30%
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,826	A Scalable Data Platform for a Large Number of Small Applications	2009	CIDR	9.5417732e-05
2,419	Towards Elastic Transactional Cloud Storage with Range Query Support	2010	VLDB	8.4818595e-05
3,274	P-Ring: An Efficient and Robust P2P Range Index Structure	2007	SIGMOD	7.4559863e-05
3,425	Angle-based Space Partitioning for Efficient Parallel Skyline Computation	2008	SIGMOD	7.2968417e-05
4,934	Speeding up Search in Peer-to-Peer Networks with A Multi-way Tree Structure	2006	SIGMOD	6.3359647e-05
5,480	Distributed Query Evaluation with Performance Guarantees	2007	SIGMOD	6.0991082e-05
5,855	Effective Keyword-based Selection of Relational Databases	2007	SIGMOD	5.9516101e-05
7,179	Minuet: A Scalable Distributed Multiversion B-Tree	2012	VLDB	5.5769584e-05
7,992	Efficient B-tree Based Indexing for Cloud Data Processing	2010	VLDB	5.3946231e-05
8,215	TI: An Efficient Indexing Mechanism for Real-Time Search on Tweets	2011	SIGMOD	5.3601329e-05
8,851	Just-In-Time Query Retrieval Over Partially Indexed Data on Structured P2P Overlays	2008	SIGMOD	5.2489348e-05
9,140	Delay Aware Querying with Seaweed	2006	VLDB	5.2082006e-05
9,804	A Framework for Supporting DBMS-like Indexes in the Cloud	2011	VLDB	5.1149679e-05
9,897	Cooperative XPath Caching	2008	SIGMOD	5.0998483e-05
12,761	Indexing Multi-dimensional Data in a Cloud System	2010	SIGMOD	4.9605343e-05
12,892	Paths to Stardom: Calibrating the Potential of a Peer-based Data Management System	2008	SIGMOD	4.9605343e-05
12,926	P3N: Profiling the Potential of a Peer-based Data Management System	2008	VLDB	4.9605343e-05
13,015	Peer-to-Peer Similarity Search in Metric Spaces	2007	VLDB	4.9605343e-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
230	A Study of Index Structures for Main Memory Database Management Systems	1986	VLDB	0.00023845485
1,477	Online Balancing of Range-Partitioned Data with Applications to Peer-to-Peer Systems	2004	VLDB	0.00010520204
2,302	Approximate Range Selection Queries in Peer-to-Peer Systems	2003	CIDR	8.6605971e-05
2,603	RP*: A Family of Order-Preserving Scalable Distributed Data Structures	1994	VLDB	8.2151528e-05
3,518	Towards Self-Tuning Data Placement in Parallel Database Systems	2000	SIGMOD	7.2204376e-05

Semantically Similar Papers

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