On the feasibility of peer-to-peer web indexing and search

Jinyang Li; Boon Thau Loo; Joseph M. Hellerstein; M. Frans Kaashoek; David R. Karger; Robert Morris

doi:10.1007/978-3-540-45172-3_19

On the feasibility of peer-to-peer web indexing and search

Jinyang Li, Boon Thau Loo, Joseph M. Hellerstein, M. Frans Kaashoek, David R. Karger, Robert Morris

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Abstract

This paper discusses the feasibility of peer-to-peer full-text keyword search of the Web. Two classes of keyword search techniques are in use or have been proposed: flooding of queries over an overlay network (as in Gnutella), and intersection of index lists stored in a distributed hash table. We present a simple feasibility analysis based on the resource constraints and search workload. Our study suggests that the peer-to-peer network does not have enough capacity to make naive use of either of search techniques attractive for Web search. The paper presents a number of existing and novel optimizations for P2P search based on distributed hash tables, estimates their effects, on performance, and concludes that in combination these optimizations would bring the problem to within an order of magnitude of feasibility. The paper suggests a number of compromises that might achieve the last order of magnitude.

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Frans Kaashoek, Ion Stoica
Publisher	Springer Verlag
Pages	207-215
Number of pages	9
ISBN (Print)	3540407243
DOIs	https://doi.org/10.1007/978-3-540-45172-3_19
State	Published - 2003

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2735
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-45172-3_19

Cite this

Li, J., Loo, B. T., Hellerstein, J. M., Kaashoek, M. F., Karger, D. R., & Morris, R. (2003). On the feasibility of peer-to-peer web indexing and search. In F. Kaashoek, & I. Stoica (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 207-215). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2735). Springer Verlag. https://doi.org/10.1007/978-3-540-45172-3_19

On the feasibility of peer-to-peer web indexing and search. / Li, Jinyang; Loo, Boon Thau; Hellerstein, Joseph M. et al.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Frans Kaashoek; Ion Stoica. Springer Verlag, 2003. p. 207-215 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2735).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

Li, J, Loo, BT, Hellerstein, JM, Kaashoek, MF, Karger, DR & Morris, R 2003, On the feasibility of peer-to-peer web indexing and search. in F Kaashoek & I Stoica (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2735, Springer Verlag, pp. 207-215. https://doi.org/10.1007/978-3-540-45172-3_19

Li J, Loo BT, Hellerstein JM, Kaashoek MF, Karger DR, Morris R. On the feasibility of peer-to-peer web indexing and search. In Kaashoek F, Stoica I, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 207-215. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-45172-3_19

Li, Jinyang ; Loo, Boon Thau ; Hellerstein, Joseph M. et al. / On the feasibility of peer-to-peer web indexing and search. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Frans Kaashoek ; Ion Stoica. Springer Verlag, 2003. pp. 207-215 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{0dfe45be2a2f4e0dbdfdec44a2333ddd,

title = "On the feasibility of peer-to-peer web indexing and search",

abstract = "This paper discusses the feasibility of peer-to-peer full-text keyword search of the Web. Two classes of keyword search techniques are in use or have been proposed: flooding of queries over an overlay network (as in Gnutella), and intersection of index lists stored in a distributed hash table. We present a simple feasibility analysis based on the resource constraints and search workload. Our study suggests that the peer-to-peer network does not have enough capacity to make naive use of either of search techniques attractive for Web search. The paper presents a number of existing and novel optimizations for P2P search based on distributed hash tables, estimates their effects, on performance, and concludes that in combination these optimizations would bring the problem to within an order of magnitude of feasibility. The paper suggests a number of compromises that might achieve the last order of magnitude.",

author = "Jinyang Li and Loo, {Boon Thau} and Hellerstein, {Joseph M.} and Kaashoek, {M. Frans} and Karger, {David R.} and Robert Morris",

year = "2003",

doi = "10.1007/978-3-540-45172-3_19",

language = "English (US)",

isbn = "3540407243",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "207--215",

editor = "Frans Kaashoek and Ion Stoica",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

TY - CHAP

T1 - On the feasibility of peer-to-peer web indexing and search

AU - Li, Jinyang

AU - Loo, Boon Thau

AU - Hellerstein, Joseph M.

AU - Kaashoek, M. Frans

AU - Karger, David R.

AU - Morris, Robert

PY - 2003

Y1 - 2003

N2 - This paper discusses the feasibility of peer-to-peer full-text keyword search of the Web. Two classes of keyword search techniques are in use or have been proposed: flooding of queries over an overlay network (as in Gnutella), and intersection of index lists stored in a distributed hash table. We present a simple feasibility analysis based on the resource constraints and search workload. Our study suggests that the peer-to-peer network does not have enough capacity to make naive use of either of search techniques attractive for Web search. The paper presents a number of existing and novel optimizations for P2P search based on distributed hash tables, estimates their effects, on performance, and concludes that in combination these optimizations would bring the problem to within an order of magnitude of feasibility. The paper suggests a number of compromises that might achieve the last order of magnitude.

AB - This paper discusses the feasibility of peer-to-peer full-text keyword search of the Web. Two classes of keyword search techniques are in use or have been proposed: flooding of queries over an overlay network (as in Gnutella), and intersection of index lists stored in a distributed hash table. We present a simple feasibility analysis based on the resource constraints and search workload. Our study suggests that the peer-to-peer network does not have enough capacity to make naive use of either of search techniques attractive for Web search. The paper presents a number of existing and novel optimizations for P2P search based on distributed hash tables, estimates their effects, on performance, and concludes that in combination these optimizations would bring the problem to within an order of magnitude of feasibility. The paper suggests a number of compromises that might achieve the last order of magnitude.

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

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

U2 - 10.1007/978-3-540-45172-3_19

DO - 10.1007/978-3-540-45172-3_19

M3 - Chapter

AN - SCOPUS:35248880268

SN - 3540407243

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 207

EP - 215

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Kaashoek, Frans

A2 - Stoica, Ion

PB - Springer Verlag

ER -

On the feasibility of peer-to-peer web indexing and search

Abstract

Publication series

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this