Prasanna Ganesan
Hector Garcia-Molina
ABSTRACT
Peer-to-peer systems enable access to data spread over an extremely large number of machines. Most P2P systems support only simple lookup queries. However, many new applications, such as P2P photo sharing and massively multi-player games, would benefit greatly from support for multidimensional range queries. We show how such queries may be supported in a P2P system by adapting traditional spatial-database technologies with novel P2P routing networks and load-balancing algorithms. We show how to adapt two popular spatial-database solutions - kd-trees and space-filling curves - and experimentally compare their effectiveness.
- M. Adler, E. Halperin, R. M. Karp, and V. V. Vazirani. A stochastic process on the hypercube with applications to peer-to-peer networks. In Proc. STOC, pages 575--584, June 2003. Google Scholar
Digital Library
- A. Silberschatz, H. F. Korth, and S. Sudarshan. "Database System Concepts", chapter 17. McGraw-Hill, 1997. Google ScholarDigital Library
- J. Aspnes and G. Shah. Skip graphs. In Proc. SODA, 2003. Google ScholarDigital Library
- C. Bohm, G. Klump, and H. Kriegel. Xz-ordering: A space-filling curve for objects with spatial extension. In Proc. Symposium on Large Spatial Databases, 1999. Google ScholarDigital Library
- G. Copeland, W. Alexander, E. Boughter, and T. Keller. Data placement in Bubba. In Proc. SIGMOD, 1988. Google ScholarDigital Library
- C. Faloutsos and P. Bhagwat. Declustering using fractals. In Proc. Intl. Conf. on Parallel and Distributed Information Systems, 1993. Google ScholarDigital Library
- P. Ganesan, M. Bawa, and H. Garcia-Molina. Online balancing of range-partitioned data with applications to peer-to-peer systems. Technical report, Stanford University, 2004.Google Scholar
- S. Ghandeharizadeh and D. J. DeWitt. A performance analysis of alternative multi-attribute declustering strategies. In Proc. SIGMOD, 1992. Google ScholarDigital Library
- N. J. A. Harvey, M. Jones, S. Saroiu, M. Theimer, and A. Wolman. Skipnet: A scalable overlay network with practical locality properties. In Proc. USITS, 2003. Google ScholarDigital Library
- H. Jagadish. Linear clustering of objects with multiple attributes. In Proc. SIGMOD, 1990. Google ScholarDigital Library
- D. R. Karger and M. Ruhl. Simple efficient load-balancing algorithms for peer-to-peer systems. In Proc. IPTPS, 2004. Google ScholarDigital Library
- G. Knutsson, H. Lu, W. Xu, and B. Hopkins. Peer-to-peer support for massively multiplayer games. In Proc. INFOCOM, 2004.Google ScholarCross Ref
- M. Naor and U. Wieder. Novel architectures for P2P applications: The continuous-discrete approach. In Proc. 15th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA 2003), pages 50--59, June 2003. Google ScholarDigital Library
- J. Orenstein and T. Merrett. A class of data structures for associative searching. In Proc. PODS, 1984. Google ScholarDigital Library
- S. Ratnasamy, P. Francis, M. Handley, and R. M. Karp. A scalable Content-Addressable Network. In Proc. SIGCOMM, 2001. Google ScholarDigital Library
- A. I. T. Rowstron and P. Druschel. Pastry: Scalable, distributed object location, and routing for large-scale peer-to-peer systems. In Proc. Middleware, 2001. Google ScholarDigital Library
- I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In Proc. SIGCOMM, 2001. Google ScholarDigital Library
Recommendations
One ring to rule them all: service discovery and binding in structured peer-to-peer overlay networks
EW 10: Proceedings of the 10th workshop on ACM SIGOPS European workshopSelf-organizing, structured peer-to-peer (p2p) overlay networks like CAN, Chord, Pastry and Tapestry offer a novel platform for a variety of scalable and decentralized distributed applications. These systems provide efficient and fault-tolerant routing, ...
Build One, Get One Free: Leveraging the Coexistence of Multiple P2P Overlay Networks
ICDCS '07: Proceedings of the 27th International Conference on Distributed Computing SystemsMany different P2P overlay networks providing various functionalities, targeting specific applications, have been proposed in the past five years. It is now reasonable to consider that multiple overlays may be deployed over a large set of nodes so that ...
Enabling P2P One-View Multiparty Video Conferencing
Multiparty video conferencing (MPVC) facilitates real-time group interaction between users. While P2P is a natural delivery solution for MPVC, a peer often does not have enough bandwidth to deliver her video to all other peers in the conference. Recently,...
Comments