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: 3797
Venue: SIGMOD
Year: 2006
Pagerank: 6.5059395e-05
Overall Rank: 4,791 | 67.14%
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,187	P-Ring: An Efficient and Robust P2P Range Index Structure	2007	SIGMOD	7.6555242e-05
7,827	Efficient B-tree Based Indexing for Cloud Data Processing	2010	VLDB	5.5361352e-05
12,420	Load-Balanced Query Dissemination in Privacy-Aware Online Communities	2010	SIGMOD	5.093636e-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,632	HomeViews: Peer-to-Peer Middleware for Personal Data Sharing Applications	2007	SIGMOD	5.093636e-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,237	Approximate Range Selection Queries in Peer-to-Peer Systems	2003	CIDR	8.8901709e-05
2,278	BATON: A Balanced Tree Structure for Peer-to-Peer Networks	2005	VLDB	8.8160706e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,677	Peer-to-Peer Similarity Search in Metric Spaces	2007	VLDB
2	4,594	Distributed Query Processing and Catalogs for Peer-to-Peer Systems	2003	CIDR
3	12,773	An Indexing Framework for Peer-to-Peer Systems	2004	SIGMOD
4	6,451	Efficient Search of Multidimensional B-Trees	1995	VLDB
5	2,237	Approximate Range Selection Queries in Peer-to-Peer Systems	2003	CIDR
6	8,664	Just-In-Time Query Retrieval Over Partially Indexed Data on Structured P2P Overlays	2008	SIGMOD
7	7,342	Efficient Search in Very Large Databases	1988	VLDB
8	6,140	Enhancing P2P File-Sharing with an Internet-Scale Query Processor	2004	VLDB
9	4,075	Distributing a Search Tree Among a Growing Number of Processors	1994	SIGMOD
10	2,278	BATON: A Balanced Tree Structure for Peer-to-Peer Networks	2005	VLDB