Speeding up Search in Peer-to-Peer Networks with A Multi-way Tree Structure

Summary: BATON*, a multi-way tree P2P search structure, achieves O(log_m N) search with fanout m; update cost is linear in m. Experimental analysis shows the trade-off between search and update costs, and BATON* adds multi-attribute query support. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h55b17d6720b1770f
Venue: SIGMOD
Year: 2006
Pagerank: 6.3599944e-05
Overall Rank: 4,908 | 67.01%
DOI: 10.1145/1142473.1142475

Incoming Non-self Citations Over Time

Authors

1. H. V. Jagadish (University of Michigan)
2. Beng Chin Ooi (National University of Singapore)
3. Kian-Lee Tan (National University of Singapore)
4. Quang Hieu Vu (National University of Singapore)
5. Rong Zhang (Fudan University)

BibTeX Citation

@inproceedings{jagadish_sigmod06,
        title = {{Speeding up Search in Peer-to-Peer Networks with A Multi-way Tree Structure}},
        author = {Jagadish, H. V. and Ooi, Beng Chin and Tan, Kian-Lee and Vu, Quang Hieu and Zhang, Rong},
        series = {{SIGMOD} '06},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1142473.1142475},
        url = {https://dl.acm.org/doi/10.1145/1142473.1142475},
        year = {2006}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,260	P-Ring: An Efficient and Robust P2P Range Index Structure	2007	SIGMOD	7.4842462e-05
7,970	Efficient B-tree Based Indexing for Cloud Data Processing	2010	VLDB	5.4150774e-05
12,711	Load-Balanced Query Dissemination in Privacy-Aware Online Communities	2010	SIGMOD	4.9793485e-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,922	HomeViews: Peer-to-Peer Middleware for Personal Data Sharing Applications	2007	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2,287	Approximate Range Selection Queries in Peer-to-Peer Systems	2003	CIDR	8.6931935e-05
2,327	BATON: A Balanced Tree Structure for Peer-to-Peer Networks	2005	VLDB	8.6301365e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	282	FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs	2010	SIGMOD
2	4,695	Distributed Query Processing and Catalogs for Peer-to-Peer Systems	2003	CIDR
3	13,063	An Indexing Framework for Peer-to-Peer Systems	2004	SIGMOD
4	6,584	Efficient Search of Multidimensional B-Trees	1995	VLDB
5	2,287	Approximate Range Selection Queries in Peer-to-Peer Systems	2003	CIDR
6	7,355	Efficient Search in Very Large Databases	1988	VLDB
7	8,824	Just-In-Time Query Retrieval Over Partially Indexed Data on Structured P2P Overlays	2008	SIGMOD
8	6,269	Enhancing P2P File-Sharing with an Internet-Scale Query Processor	2004	VLDB
9	4,163	Distributing a Search Tree Among a Growing Number of Processors	1994	SIGMOD
10	2,327	BATON: A Balanced Tree Structure for Peer-to-Peer Networks	2005	VLDB