Article

PRISM: indexing multi-dimensional data in P2P networks using reference vectors

Authors:

A. El AbbadiAuthors Info & Claims

MULTIMEDIA '05: Proceedings of the 13th annual ACM international conference on Multimedia

Pages 946 - 955

https://doi.org/10.1145/1101149.1101349

Published: 06 November 2005 Publication History

Abstract

Peer-to-peer (P2P) systems research has gained considerable attention recently with the increasing popularity of file sharing applications. Since these applications are used for sharing huge amounts of data, it is very important to efficiently locate the data of interest in such systems. However, these systems usually do not provide efficient search techniques. Existing systems offer only keyword search functionality through a centralized index or by query flooding. In this paper, we propose a scheme based on reference vectors for sharing multi-dimensional data in P2P systems. This scheme effectively supports a larger set of query operations (such as k-NN queries and content-based similarity search) than current systems, which generally support only exact key lookups and keyword searches.The basic idea is to store multiple replicas of an object's index at different peers based on the distances between the object's feature vector and the reference vectors. Later, when a query is posed, the system identifies the peers that are likely to store the index information about relevant objects using reference vectors. Thus the system is able to return accurate results by contacting a small fraction of the participating peers.

References

[1]

M. Bawa, G. S. Manku, and P. Raghavan. Sets: search enhanced by topic segmentation. In SIGIR pages 306--313, 2003.

Digital Library

[2]

M. W. Berry, Z. Drmac, and E. R. Jessup. Matrices, vector spaces,and information retrieval.SIAM Review 41(2): 335--362, 1999.

Digital Library

[3]

E. Binghamand H. Mannila. Randomprojection in dimensionality reduction:applications to image and text data. In SIGKDD pages 245--250,2001.

Digital Library

[4]

A. Crespo and H. Garcia-Molina. Routing indices for peer-to-peer systems. In ICDCS pages 23--32,2002.

Digital Library

[5]

F. M. Cuenca-Acuna, C. Peery, R. P. Martin, and T. D. Nguyen. Planetp: Using gossiping to build content addressable peer-to-peer information sharing communities. In HPDC-12 page 236, 2003.

Digital Library

[6]

S. Deerwester, S. T. Dumais, G. W. Furnas, T. K. Landauer, and R. Harshman. Indexing by latent semantic analysis. Journal of the American Society for Information Science 41(6):391--407,1990.

[7]

S. El-Ansary, L. O. Alima, P. Brand, and S. Haridi. Efficient broadcast in structured p2p networks. In IPTPS pages 304--314,2003.

[8]

C. Faloutsos and K.-I. Lin. FastMap: A fast algorithmfor indexing, data-mining and visualization of traditional and multimedia datasets. In SIGMOD pages 163--174,1995.

Digital Library

[9]

O. D. Gnawali. A eyword-set search system for peer-to-peer networks. Master 's thesis, Massachusetts Institute of Technology, 2002.

[10]

Gnutella. http://www.gnutella.com/.

[11]

I. Gupta, K. Birman, P. Linga, A. Demers, and R. van Renesse. Kelips: Building an efficient and stable P2P DHT through increased memory and bac ground overhead. In IPTPS pages 160--169, 2003.

[12]

M. Harren, J. M. Hellerstein, R. Huebsch, B. T. Loo, S. Shenker, and I. Stoica. Complex queries in DHT-based peer-to-peer networks. In IPTPS pages 242--259,2002.

Digital Library

[13]

P. Kalnis, W. Ng, B. Ooi, and K. Tan. Answering similarity queries in peer-to-peer networks. Information Systems 1(1):1-1,2005.

Digital Library

[14]

D. Karger and M. Ruhl. Simple efficient load balancing algorithms for peer-to-peer systems. In SPAA pages 36--43, 2004.

Digital Library

[15]

J. Li, B. T. Loo, J. Hellerstein, F. Kaashoek, D. R. Karger, and R. Morris. On the feasibility of peer-to-peer web indexing and search. In IPTPS pages 207--215,2003.

[16]

W. Muller and A. Henrich. Fast retrieval of high-dimensional feature vectors in p2p networks using compact peer data summaries. In MIR pages 79--86,2003.

Digital Library

[17]

Napster. http://www.napster.com/.

[18]

T. Quack, U. Monich, L. Thiele, and B. Manjunath. Cortina: A system for large-scale, content-based web image retrieval. In Multimedia 2004.

Digital Library

[19]

S. Ratnasamy, P. Francis, M. Handley, R. Karp, and S. Schenker. A scalable content-addressable network. In SIGCOMM pages 161--172,2001.

Digital Library

[20]

P. Reynolds and A. Vahdat. Efficient peer-to-peer keyword searching. In Middleware pages 21--40, 2003.

Digital Library

[21]

A. Rowstron and P. Druschel. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In Middleware pages 329--350,2001.

Digital Library

[22]

O. D. Sahin, F. Emekci, D. Agrawal, and A. E. Abbadi. Content-based similarity search over peer-to-peer systems. In DBISP2P pages 46--63,2004.

Digital Library

[23]

I. Stoica, R. Morris, D. Karger, M. F. Kaashoe, and H. Balakrishnan. Chord: A scalable peer-to-peer look up service for internet applications.In SIGCOMM pages 149--160,2001.

Digital Library

[24]

T. Suel, C. Mathur, J.-W. Wu, J. Zhang, A. Delis, M. Kharrazi, X. Long, and K. Shanmugasundaram. Odissea: A peer-to-peer architecture for scalable web search and information retrieval. In WebDB pages 67--72,2003.

[25]

C. Tang and S. Dwarkadas. Hybrid global-local indexing for efficient peer-to-peer information retrieval. In NSDI pages 211--224,2004.

Digital Library

[26]

C. Tang, Z. Xu, and S. Dwarkadas. Peer-to-peer information retrieval using self-organizing semantic overlay networks. In SIGCOMM pages 175--186,2003.

Digital Library

[27]

B. Yang and H. Garcia-Molina. Improving search in peer-to-peer netwoks. In ICDCS pages 5--14,2002.

Digital Library

[28]

B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz. Tapestry: A global-scale overlay for rapid service deployment. IEEE Journal on Selected Areas in Communications 22(1): 41--53,2004.

Digital Library

[29]

Y. Zhu, H. Wang, and Y. Hu. Integrating semantics-based access mechanisms with peer-to-peer file systems. In P2P pages 118--125,2003.

Digital Library

Cited By

Liao JYang DLi TQi QWang JSun H(2016)Fusion feature for LSH-based image retrieval in a cloud datacenterMultimedia Tools and Applications10.1007/s11042-015-2892-y75:23(15405-15427)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1007/s11042-015-2892-y
Zaragoza DCardinale YRukoz MChbeir RManolopoulos YMammana VModena ETraina ASalviano OBadr YAndres F(2015)SimSearchProceedings of the 7th International Conference on Management of computational and collective intElligence in Digital EcoSystems10.1145/2857218.2857233(90-97)Online publication date: 25-Oct-2015
https://dl.acm.org/doi/10.1145/2857218.2857233
Yang DLiao JQi QWang JSun HJiang S(2014)Combination feature for image retrieval in the distributed datacenter2014 20th IEEE International Conference on Parallel and Distributed Systems (ICPADS)10.1109/PADSW.2014.7097871(693-700)Online publication date: Dec-2014
https://doi.org/10.1109/PADSW.2014.7097871
Show More Cited By

Index Terms

PRISM: indexing multi-dimensional data in P2P networks using reference vectors
1. Information systems
  1. Information retrieval
    1. Retrieval models and ranking
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles
        Organizing principles for web applications

Recommendations

An Efficient Hybrid Peer-to-Peer System for Distributed Data Sharing

Peer-to-peer overlay networks are widely used in distributed systems. Based on whether a regular topology is maintained among peers, peer-to-peer networks can be divided into two categories: structured peer-to-peer networks in which peers are connected ...
On Optimizing Overlay Topologies for Search in Unstructured Peer-to-Peer Networks

Unstructured peer-to-peer (P2P) file-sharing networks are popular in the mass market. As the peers participating in unstructured networks interconnect randomly, they rely on flooding query messages to discover objects of interest and thus introduce ...
Using locality of reference to improve performance of peer-to-peer applications
WOSP '04: Proceedings of the 4th international workshop on Software and performance

Peer-to-peer, or simply P2P, systems have recently emerged as a popular paradigm for building distributed applications. One key aspect of the P2P system design is the mechanism used for content location. A number of different approaches are currently in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MULTIMEDIA '05: Proceedings of the 13th annual ACM international conference on Multimedia

November 2005

1110 pages

ISBN:1595930442

DOI:10.1145/1101149

General Chairs:
Hongjiang Zhang
Microsoft Research Asia, China
,
Tat-Seng Chua
National University of Singapore, Singapore
,
Program Chairs:
Ralf Steinmetz
Technische Universitat Darmstadt, Germany
,
Mohan Kankanhalli
National University of Singapore, Singapore
,
Lynn Wilcox
FXPAL

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

MM05

Sponsor:

MM05: 2005 13th Annual ACM International Conference on Multimedia

November 6 - 11, 2005

Hilton, Singapore

Acceptance Rates

MULTIMEDIA '05 Paper Acceptance Rate 49 of 312 submissions, 16%;

Overall Acceptance Rate 2,145 of 8,556 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
665
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Liao JYang DLi TQi QWang JSun H(2016)Fusion feature for LSH-based image retrieval in a cloud datacenterMultimedia Tools and Applications10.1007/s11042-015-2892-y75:23(15405-15427)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1007/s11042-015-2892-y
Zaragoza DCardinale YRukoz MChbeir RManolopoulos YMammana VModena ETraina ASalviano OBadr YAndres F(2015)SimSearchProceedings of the 7th International Conference on Management of computational and collective intElligence in Digital EcoSystems10.1145/2857218.2857233(90-97)Online publication date: 25-Oct-2015
https://dl.acm.org/doi/10.1145/2857218.2857233
Yang DLiao JQi QWang JSun HJiang S(2014)Combination feature for image retrieval in the distributed datacenter2014 20th IEEE International Conference on Parallel and Distributed Systems (ICPADS)10.1109/PADSW.2014.7097871(693-700)Online publication date: Dec-2014
https://doi.org/10.1109/PADSW.2014.7097871
Di Yang Jianxin Liao Qi Qi Jingyu Wang Tonghong Li (2014)An image retrieval framework for distributed datacenters39th Annual IEEE Conference on Local Computer Networks10.1109/LCN.2014.6925803(406-409)Online publication date: Sep-2014
https://doi.org/10.1109/LCN.2014.6925803
Yang DLiao JWang JQi QSun H(2014)Multiple features for image retrieval in distributed datacenterThe 16th Asia-Pacific Network Operations and Management Symposium10.1109/APNOMS.2014.6996543(1-4)Online publication date: Sep-2014
https://doi.org/10.1109/APNOMS.2014.6996543
Ghanem SIsmail MOmar S(2014)VITAL: Structured and clustered super-peer network for similarity searchPeer-to-Peer Networking and Applications10.1007/s12083-014-0304-08:6(965-991)Online publication date: 5-Aug-2014
https://doi.org/10.1007/s12083-014-0304-0
Lee JKeleher PSussman A(2014)Decentralized multi-attribute range search for resource discovery and load balancingThe Journal of Supercomputing10.1007/s11227-013-1071-z68:2(890-913)Online publication date: 1-May-2014
https://dl.acm.org/doi/10.1007/s11227-013-1071-z
Liao JYang DLi TWang JQi QZhu X(2014)A scalable approach for content based image retrieval in cloud datacenterInformation Systems Frontiers10.1007/s10796-013-9467-016:1(129-141)Online publication date: 1-Mar-2014
https://dl.acm.org/doi/10.1007/s10796-013-9467-0
Manjula S(2011)LIGHT: An efficient hash tree based indexing scheme over DHTs2011 3rd International Conference on Electronics Computer Technology10.1109/ICECTECH.2011.5941895(241-245)Online publication date: Apr-2011
https://doi.org/10.1109/ICECTECH.2011.5941895
Tang YZhou SXu J(2010)LIGHTIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2009.4722:1(59-75)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1109/TKDE.2009.47
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents