[PDF] [PDF] A Keyword-Set Search System for Peer to Peer Networks - PDOS-MIT

[PDF] A computer program for creating keyword indexes to textual data files

This keyword index program can be used to create either KWIC or KWOC indexes parameter on the DATA DD card will also need to be changed to reflect the 

[PDF] News-Oriented Automatic Chinese Keyword Indexing

Thus, automatically indexing keywords from text Keyword indexing can also be called keyword ex- traction date according to its feature values and choose

[PDF] A Keyword-Set Search System for Peer to Peer Networks - PDOS-MIT

A keyword partitioned index requires that the list of index entries for each keyword peer approach discussed in section 2 3 with a flexible parameter r However 

[PDF] Spatial Keyword Query Processing - VLDB Endowment

This makes it difficult to determine which indexing technique best supports arguments, where q ψ is a set of keywords, q ρ is a spatial query point, and q k is  

[PDF] Automatic indexing - CORE

In the experiment of this thesis the values were computed only to sin- index terms (or descriptors or keywords) are the elements of the indexing language

[PDF] Text Analysis and Automatic Indexing - SIGIR

tent identifiers, known as index terms, keywords, or descriptors, are repre ness of retrieval by using two parameters for each search known respectively

[PDF] CHAPTER 4 Indexing Procedures The function of indexing - SIGIR

It is assumed that all the keywords constitu- parameter determining precision in index performance parameters in indexing, exhaustivity and ^specificity

[PDF] Evaluating Spatial-Keyword Queries on Streaming Data - UCR CS

different spatial-keyword indexing techniques on streaming data, which is an essential index cell size, query weighting parameters, and number of Boolean

[PDF] Keyword-Advertising - lauterkeitsrechtliche Grenzen

[PDF] Keywords and phrases: ima g e c lassific ation , topolo g ic al

[PDF] keywords of the alphabetical index - Venice Commission

[PDF] Keywords Rank Mobile Rank URL Last Check kfz reperatur graz 1 1

[PDF] Keyy yo optimis se la VoIP pour l`acc cès Intern Commu net

[PDF] Keyyo Business annonce le lancement de ses offres d`accès SDSL

[PDF] Keyyo Business lance la 1 offre de téléphonie SIP en marque blanche - France

[PDF] Keyyo conclut avec Ingram Micro un accord pour la distribution de

[PDF] Keyyo publie ses API de convergence téléphonie

[PDF] Keziah Jones (NG/UK)

[PDF] Keziah Jones - jazz à carthage 2009 - France

[PDF] Keziah Jones - Taj Express

[PDF] KEZO AMOUR LE PARFUM 50 ml VAPO PARFUM:75€ (BOTELLA - Anciens Et Réunions

[PDF] KF 1280 ND

[PDF] KF Entry List

AKeyword-SetSearchSystemforPeer-to-Peer

Networks

by

OmprakashDGnawali

Science

atthe

MASSACHUSETTSINSTITUTEOFTECHNOLOGY

June2002

c inwholeorinpart.

May28,2002

M.FransKaashoek

ProfessorofComputerScienceandEngineering

ThesisSupervisor

ArthurC.Smith

2 by

OmprakashDGnawali

onMay28,2002,inpartialful¯llmentofthe requirementsforthedegreeof

Abstract

ThesisSupervisor:M.FransKaashoek

3 4

Acknowledgments

especiallyhissuggestionforexperiments. forbootstrappingmyeducation. 5 6

Contents

1Introduction11

2RelatedWork17

3KSSDesignOverview25

7

4UsingKSS35

5SystemArchitecture43

6ExperimentalFindings49

8

7FutureWorkandConclusions61

9 10

Chapter1

Introduction

algorithms. 11

¯lesattractive.

nodes.

1.1DistributedInvertedIndexing

12 thepositionfortheword. isunhelpfulinmakingaP2Psearche±cient. 13

1.2KSS:Keyword-SetSearchSystem

queryaredoc1anddoc2. 14 requirenosigni¯cantcommunication. canbeusedfor¯letransfers.

1.3Contribution

1.4ThesisOverview

15 futureworkinchapter7. 16

Chapter2

RelatedWork

2.1Napster

Client

Client

Client

Client

Metadata

uploadMetadata upload File

File download

downloadQuery

ResponseNapsterMetadata

upload

Server

downloadedfrompeers. 17

2.2Gnutella

Peer Peer Peer Peer Peer Peer Peer

QueryQuery

Query

QueryQuery

Query

Response

ResponseDownload

18 highbandwidth.

2.3FastTrackP2PStack

19

Supernode

Supernode

Peer1Peer2Peer3

Supernode

Query: File2b

MetadatauploadMetadata

uploadPeer2: File2a, File2b

Peer3: File3a, File3b

GET File File2b

File2a, File2bFile3a, File3b

Answer: Peer2

anddownloadsaredonefromthepeers resultsinworsequerylatency.

Grokster[10]areFastTrackapplications.

2.4JXTASearch

20 inJXTA.

2.5IterativeDeepeningandDirectedBFS

2.6LocalIndices

21
withinD¡rhopsstillneedtobequeried.

2.7RoutingIndices

documentswiththeleastnumberofhops.

2.8DiscoverQueryRouting

22

2.9DistributedJoinusingBloomFilters

Server sAServer sB

Client

(1) RequestA : 1 2 3 4

B : 3 4 5 6(2) F(A)

1 2 3 4

3 4 6

(3) B F(A) U (4) A BU 3 4 N 23
24

Chapter3

KSSDesignOverview

entriesarefetched. whenadocumentisinsertedintothenetwork. 25
availabletothepeers. andChord. keywordsinthequery.

3.1KSSdistributedindex

oftheindex. 26
Key hash(AB) hash(BC) hash(MN)URL http://18.175.6.2/a.mp3 http://18.175.6.2/a.mp3 http://18.175.6.2/b.html

Figure3-1:StructureoftheKSSindex

n-worddocumentisgivenbyC(n;k)=n! 27

3.2KSSExample

indextoreplytouserqueries. wordset: fortheentryABinthedistributedindex. 28
cosumed. N keyformedbyhashingABCD.

3.3Storingmetadataintheindexentry

29
hash(AB)http://18.175.6.2/a.mp3 http://18.175.6.2/a.mp3hash(BC) hash(MN)http://18.175.6.2/b.htmlKey

X Y ZMetadata

X Y Z

O P Q RURL

N matchingindexentries. 30

3.4KSSProperties

KSSsystem.

3.4.1InsertOverhead

asmallinsertoverhead.

QueryOverhead

31
them. q nextkwordsinthequery.Thus,thereareq khops,henceaboutqklistsneedtobe fetchedfromacrossthenetwork.

StorageOverhead

32
entry.

KSSOverheadwithmetadata

regardlessofthequeryalgorithm. 33
34

Chapter4

UsingKSS

adaptittospeci¯capplicationneeds.

4.1Meta-dataSearch

ineachentry. onmorethantwokeywordsmoree±cient. 35
thelistofentrieswiththematchingkeys. entriese±cient.

¯eldID,metaID):

word[0..n]=meta-datafield for(i=0;i) entriesinthedistributedhash aregenerated: 36

¯lesystemsuchasCFS.

searchapplication.

4.2Full-textindexing

documents. 37
unlimitedw. threewords:A,BandC. orACthancontainanyofA,B,orC. 38

4.3KSSCon¯guration

4.3.1ContentsofIndexentry

39
spaceblowupistoomuch.

4.3.3Storagerequirement

40
forwardingthequerytoonenode.

4.3.4Documentranking

theonesappearinginthemiddleofaparagraph. 41
42

Chapter5

SystemArchitecture

Chord

DHashKSS

Chord

DHashKSS

Chord

DHashKSS

5.1TheChordLayer

43

O(logN).

5.2TheDHashLayer

IDasthekey.

44

ThefollowingisasummaryofDHashAPI:

key. anewentrywiththegivenkeyanddatavalue.

5.2.1Availability

5.2.2Caching

fulllookup.

5.2.3LoadBalance

45
alotofbandwidthanddiskspacetospare.

5.3KSSLayer

query. entries,andstoretheminthenetwork. andreturntheintersectedlistofdocuments.

5.4ImplementationStatus

supportsthefollowingcommands: 46
47
48

Chapter6

ExperimentalFindings

preliminary¯ndingsfromourexperiments.

6.1E±ciencyinFull-textsearch

6.1.1AnalysisMethodology

49
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

010002000300040005000

Percentage of pages

Number of index entries generated per page

Standard Inverted Index

KSS with window size of five

KSS with window size of ten

scheme. doc1)>. theactualusersontheLCSwebsite. 50
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1

02004006008001000120014001600

Percentage of files

KB transferred during a query

Standard Inverted Index

KSS with window size 5

6.1.2InsertOverhead

51
0 50
100
150
200
250

123456

Mean KB transferred

Number of words in the query

KSS with window size 5

Standard Inverted Index scheme

(x-axis). insert.

Standardinvertedindex12.1million480MB

KSSwithwindowsizeof¯ve92.5million4GB

KSSwithwindowsizeoften169.6million7GB

thestandardinvertedindexscheme. 52

123456789100.00

0.05 0.10quotesdbs_dbs17.pdfusesText_23