Squid: Enabling search in DHT-based systems

Cristina Schmidt; Manish Parashar

doi:10.1016/j.jpdc.2008.02.003

Squid: Enabling search in DHT-based systems

Cristina Schmidt, Manish Parashar

Research output: Contribution to journal › Article › peer-review

56 Scopus citations

Abstract

A fundamental problem in large scale, decentralized distributed systems is the efficient discovery of information. This paper presents Squid, a peer-to-peer information discovery system that supports flexible searches and provides search guarantees. The fundamental concept underlying the approach is the definition of multi-dimensional information spaces and the maintenance of locality in these spaces. The key innovation is a dimensionality reducing indexing scheme that effectively maps the multi-dimensional information space to physical peers while preserving lexical locality. Squid supports complex queries containing partial keywords, wildcards and ranges. Analytical and simulation results show that Squid is scalable and efficient.

Original language	English (US)
Pages (from-to)	962-975
Number of pages	14
Journal	Journal of Parallel and Distributed Computing
Volume	68
Issue number	7
DOIs	https://doi.org/10.1016/j.jpdc.2008.02.003
State	Published - Jul 2008

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Hardware and Architecture
Computer Networks and Communications
Artificial Intelligence

Keywords

Distributed hash table
Information discovery
Peer-to-peer

Access to Document

10.1016/j.jpdc.2008.02.003

Cite this

@article{efe8f229d3864c7b87cfc75fb9af8266,

title = "Squid: Enabling search in DHT-based systems",

abstract = "A fundamental problem in large scale, decentralized distributed systems is the efficient discovery of information. This paper presents Squid, a peer-to-peer information discovery system that supports flexible searches and provides search guarantees. The fundamental concept underlying the approach is the definition of multi-dimensional information spaces and the maintenance of locality in these spaces. The key innovation is a dimensionality reducing indexing scheme that effectively maps the multi-dimensional information space to physical peers while preserving lexical locality. Squid supports complex queries containing partial keywords, wildcards and ranges. Analytical and simulation results show that Squid is scalable and efficient.",

keywords = "Distributed hash table, Information discovery, Peer-to-peer",

author = "Cristina Schmidt and Manish Parashar",

note = "Funding Information: Manish Parashar is Professor of Electrical and Computer Engineering at Rutgers University, where he also is Director of the NSF Center for Autonomic Computing and The Applied Software Systems Laboratory. He received a BE degree in Electronics and Telecommunications from Bombay University, India and MS and Ph.D. degrees in Computer Engineering from Syracuse University. His research interests include autonomic computing, parallel & distributed computing (including peer-to-peer and Grid computing), scientific computing, and software engineering. Manish received the Rutgers University Board of Trustees Award for Excellence in Research (2004-2005), the NSF CAREER Award (1999), TICAM, University of Texas at Austin, Distinguished Fellowship (1999-2001), Enrico Fermi Scholarship, Argonne National Laboratory (1996). Funding Information: This work is supported in part by the National Science Foundation through grants numbers ACI 9984357, EIA 0103674, EIA 0120934, ANI 0335244, CNS 0305495, CNS 0426354 and IIS 0430826. ",

year = "2008",

month = jul,

doi = "10.1016/j.jpdc.2008.02.003",

language = "English (US)",

volume = "68",

pages = "962--975",

journal = "Journal of Parallel and Distributed Computing",

issn = "0743-7315",

publisher = "Academic Press Inc.",

number = "7",

}

TY - JOUR

T1 - Squid

T2 - Enabling search in DHT-based systems

AU - Schmidt, Cristina

AU - Parashar, Manish

N1 - Funding Information: Manish Parashar is Professor of Electrical and Computer Engineering at Rutgers University, where he also is Director of the NSF Center for Autonomic Computing and The Applied Software Systems Laboratory. He received a BE degree in Electronics and Telecommunications from Bombay University, India and MS and Ph.D. degrees in Computer Engineering from Syracuse University. His research interests include autonomic computing, parallel & distributed computing (including peer-to-peer and Grid computing), scientific computing, and software engineering. Manish received the Rutgers University Board of Trustees Award for Excellence in Research (2004-2005), the NSF CAREER Award (1999), TICAM, University of Texas at Austin, Distinguished Fellowship (1999-2001), Enrico Fermi Scholarship, Argonne National Laboratory (1996). Funding Information: This work is supported in part by the National Science Foundation through grants numbers ACI 9984357, EIA 0103674, EIA 0120934, ANI 0335244, CNS 0305495, CNS 0426354 and IIS 0430826.

PY - 2008/7

Y1 - 2008/7

N2 - A fundamental problem in large scale, decentralized distributed systems is the efficient discovery of information. This paper presents Squid, a peer-to-peer information discovery system that supports flexible searches and provides search guarantees. The fundamental concept underlying the approach is the definition of multi-dimensional information spaces and the maintenance of locality in these spaces. The key innovation is a dimensionality reducing indexing scheme that effectively maps the multi-dimensional information space to physical peers while preserving lexical locality. Squid supports complex queries containing partial keywords, wildcards and ranges. Analytical and simulation results show that Squid is scalable and efficient.

AB - A fundamental problem in large scale, decentralized distributed systems is the efficient discovery of information. This paper presents Squid, a peer-to-peer information discovery system that supports flexible searches and provides search guarantees. The fundamental concept underlying the approach is the definition of multi-dimensional information spaces and the maintenance of locality in these spaces. The key innovation is a dimensionality reducing indexing scheme that effectively maps the multi-dimensional information space to physical peers while preserving lexical locality. Squid supports complex queries containing partial keywords, wildcards and ranges. Analytical and simulation results show that Squid is scalable and efficient.

KW - Distributed hash table

KW - Information discovery

KW - Peer-to-peer

UR - http://www.scopus.com/inward/record.url?scp=44449088822&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=44449088822&partnerID=8YFLogxK

U2 - 10.1016/j.jpdc.2008.02.003

DO - 10.1016/j.jpdc.2008.02.003

M3 - Article

AN - SCOPUS:44449088822

SN - 0743-7315

VL - 68

SP - 962

EP - 975

JO - Journal of Parallel and Distributed Computing

JF - Journal of Parallel and Distributed Computing

IS - 7

ER -

Squid: Enabling search in DHT-based systems

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this