Unstructured Peer-to-Peer Networks: Topological Properties and Search Performance
Identifieur interne : 000578 ( Istex/Corpus ); précédent : 000577; suivant : 000579Unstructured Peer-to-Peer Networks: Topological Properties and Search Performance
Auteurs : L. Fletcher ; A. Sheth ; Katy BörnerSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2005.
Abstract
Abstract: Performing efficient decentralized search is a fundamental problem in Peer-to-Peer (P2P) systems. There has been a significant amount of research recently on developing robust self-organizing P2P topologies that support efficient search. In this paper we discuss four structured and unstructured P2P models (CAN, Chord, PRU, and Hypergrid) and three characteristic search algorithms (BFS, k-Random Walk, and GAPS) for unstructured networks. We report on the results of simulations of these networks and provide measurements of search performance, focusing on search in unstructured networks. We find that the proposed models produce small-world networks, and yet none exhibit power-law degree distributions. Our simulations also suggest that random graphs support decentralized search more effectively than the proposed unstructured P2P models. We also find that on these topologies, the basic breadth-first search algorithm and its simple variants have the lowest search cost.
Url:
DOI: 10.1007/11574781_2
Links to Exploration step
ISTEX:9662A0EB15066CA1C9647127542C380ABE4D65BFLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct:series"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Unstructured Peer-to-Peer Networks: Topological Properties and Search Performance</title><author><name sortKey="Fletcher, L" sort="Fletcher, L" uniqKey="Fletcher L" first="L." last="Fletcher">L. Fletcher</name><affiliation><mods:affiliation>Computer Science Department, Indiana University, Bloomington, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: gefletch@indiana.edu</mods:affiliation></affiliation></author><author><name sortKey="Sheth, A" sort="Sheth, A" uniqKey="Sheth A" first="A." last="Sheth">A. Sheth</name><affiliation><mods:affiliation>School of Informatics, Indiana University, Bloomington, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: hsheth@indiana.edu</mods:affiliation></affiliation></author><author><name sortKey="Borner, Katy" sort="Borner, Katy" uniqKey="Borner K" first="Katy" last="Börner">Katy Börner</name><affiliation><mods:affiliation>School of Library and Information Science, Indiana University, Bloomington, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: katy@indiana.edu</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:9662A0EB15066CA1C9647127542C380ABE4D65BF</idno><date when="2005" year="2005">2005</date><idno type="doi">10.1007/11574781_2</idno><idno type="url">https://api.istex.fr/document/9662A0EB15066CA1C9647127542C380ABE4D65BF/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000578</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Unstructured Peer-to-Peer Networks: Topological Properties and Search Performance</title><author><name sortKey="Fletcher, L" sort="Fletcher, L" uniqKey="Fletcher L" first="L." last="Fletcher">L. Fletcher</name><affiliation><mods:affiliation>Computer Science Department, Indiana University, Bloomington, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: gefletch@indiana.edu</mods:affiliation></affiliation></author><author><name sortKey="Sheth, A" sort="Sheth, A" uniqKey="Sheth A" first="A." last="Sheth">A. Sheth</name><affiliation><mods:affiliation>School of Informatics, Indiana University, Bloomington, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: hsheth@indiana.edu</mods:affiliation></affiliation></author><author><name sortKey="Borner, Katy" sort="Borner, Katy" uniqKey="Borner K" first="Katy" last="Börner">Katy Börner</name><affiliation><mods:affiliation>School of Library and Information Science, Indiana University, Bloomington, USA</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: katy@indiana.edu</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2005</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">9662A0EB15066CA1C9647127542C380ABE4D65BF</idno><idno type="DOI">10.1007/11574781_2</idno><idno type="ChapterID">2</idno><idno type="ChapterID">Chap2</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: Performing efficient decentralized search is a fundamental problem in Peer-to-Peer (P2P) systems. There has been a significant amount of research recently on developing robust self-organizing P2P topologies that support efficient search. In this paper we discuss four structured and unstructured P2P models (CAN, Chord, PRU, and Hypergrid) and three characteristic search algorithms (BFS, k-Random Walk, and GAPS) for unstructured networks. We report on the results of simulations of these networks and provide measurements of search performance, focusing on search in unstructured networks. We find that the proposed models produce small-world networks, and yet none exhibit power-law degree distributions. Our simulations also suggest that random graphs support decentralized search more effectively than the proposed unstructured P2P models. We also find that on these topologies, the basic breadth-first search algorithm and its simple variants have the lowest search cost.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>George H. L. Fletcher</name><affiliations><json:string>Computer Science Department, Indiana University, Bloomington, USA</json:string><json:string>E-mail: gefletch@indiana.edu</json:string></affiliations></json:item><json:item><name>Hardik A. Sheth</name><affiliations><json:string>School of Informatics, Indiana University, Bloomington, USA</json:string><json:string>E-mail: hsheth@indiana.edu</json:string></affiliations></json:item><json:item><name>Katy Börner</name><affiliations><json:string>School of Library and Information Science, Indiana University, Bloomington, USA</json:string><json:string>E-mail: katy@indiana.edu</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>OriginalPaper</json:string></originalGenre><abstract>Abstract: Performing efficient decentralized search is a fundamental problem in Peer-to-Peer (P2P) systems. There has been a significant amount of research recently on developing robust self-organizing P2P topologies that support efficient search. In this paper we discuss four structured and unstructured P2P models (CAN, Chord, PRU, and Hypergrid) and three characteristic search algorithms (BFS, k-Random Walk, and GAPS) for unstructured networks. We report on the results of simulations of these networks and provide measurements of search performance, focusing on search in unstructured networks. We find that the proposed models produce small-world networks, and yet none exhibit power-law degree distributions. Our simulations also suggest that random graphs support decentralized search more effectively than the proposed unstructured P2P models. We also find that on these topologies, the basic breadth-first search algorithm and its simple variants have the lowest search cost.</abstract><qualityIndicators><score>6.113</score><pdfVersion>1.3</pdfVersion><pdfPageSize>430 x 660 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>987</abstractCharCount><pdfWordCount>4457</pdfWordCount><pdfCharCount>27410</pdfCharCount><pdfPageCount>14</pdfPageCount><abstractWordCount>138</abstractWordCount></qualityIndicators><title>Unstructured Peer-to-Peer Networks: Topological Properties and Search Performance</title><chapterId><json:string>2</json:string><json:string>Chap2</json:string></chapterId><genre><json:string>conference</json:string></genre><serie><editor><json:item><name>David Hutchison</name><affiliations><json:string>Lancaster University, UK</json:string></affiliations></json:item><json:item><name>Takeo Kanade</name><affiliations><json:string>Carnegie Mellon University, Pittsburgh, PA, USA</json:string></affiliations></json:item><json:item><name>Josef Kittler</name><affiliations><json:string>University of Surrey, Guildford, UK</json:string></affiliations></json:item><json:item><name>Jon M. Kleinberg</name><affiliations><json:string>Cornell University, Ithaca, NY, USA</json:string></affiliations></json:item><json:item><name>Friedemann Mattern</name><affiliations><json:string>ETH Zurich, Switzerland</json:string></affiliations></json:item><json:item><name>John C. Mitchell</name><affiliations><json:string>Stanford University, CA, USA</json:string></affiliations></json:item><json:item><name>Moni Naor</name><affiliations><json:string>Weizmann Institute of Science, Rehovot, Israel</json:string></affiliations></json:item><json:item><name>Oscar Nierstrasz</name><affiliations><json:string>University of Bern, Switzerland</json:string></affiliations></json:item><json:item><name>C. Pandu Rangan</name><affiliations><json:string>Indian Institute of Technology, Madras, India</json:string></affiliations></json:item><json:item><name>Bernhard Steffen</name><affiliations><json:string>University of Dortmund, Germany</json:string></affiliations></json:item><json:item><name>Madhu Sudan</name><affiliations><json:string>Massachusetts Institute of Technology, MA, USA</json:string></affiliations></json:item><json:item><name>Demetri Terzopoulos</name><affiliations><json:string>New York University, NY, USA</json:string></affiliations></json:item><json:item><name>Dough Tygar</name><affiliations><json:string>University of California, Berkeley, CA, USA</json:string></affiliations></json:item><json:item><name>Moshe Y. Vardi</name><affiliations><json:string>Rice University, Houston, TX, USA</json:string></affiliations></json:item><json:item><name>Gerhard Weikum</name><affiliations><json:string>Max-Planck Institute of Computer Science, Saarbruecken, Germany</json:string></affiliations></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Lecture Notes in Computer Science</title><copyrightDate>2005</copyrightDate></serie><host><editor><json:item><name>Gianluca Moro</name><affiliations><json:string>Dept. of Electronics, Computer Science and Systems, University of Bologna, Via Venezia, 52, 47023, Cesena (FC), Italy</json:string><json:string>E-mail: gmoro@deis.unibo.it</json:string></affiliations></json:item><json:item><name>Sonia Bergamaschi</name><affiliations><json:string>Dept. of Science Engineering, University of Modena and Reggio-Emilia, via Vignolese, 905, 41100, Modena, Italy</json:string><json:string>E-mail: bergamaschi.sonia@unimo.it</json:string></affiliations></json:item><json:item><name>Karl Aberer</name><affiliations><json:string>School of Computer and Communication Sciences, École Polytechnique Fédérale de Lausanne (EPFL), CH-1015, Lausanne, Switzerland</json:string><json:string>E-mail: karl.aberer@epfl.ch</json:string></affiliations></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Artificial Intelligence (incl. Robotics)</value></json:item><json:item><value>Computer Communication Networks</value></json:item><json:item><value>Information Systems Applications (incl.Internet)</value></json:item><json:item><value>Information Storage and Retrieval</value></json:item><json:item><value>Computers and Society</value></json:item></subject><isbn><json:string>978-3-540-29755-0</json:string></isbn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Agents and Peer-to-Peer Computing</title><bookId><json:string>978-3-540-31657-2</json:string></bookId><volume>3601</volume><pages><last>27</last><first>14</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-540-31657-2</json:string></eisbn><copyrightDate>2005</copyrightDate><doi><json:string>10.1007/11574781</json:string></doi></host><publicationDate>2005</publicationDate><copyrightDate>2005</copyrightDate><doi><json:string>10.1007/11574781_2</json:string></doi><id>9662A0EB15066CA1C9647127542C380ABE4D65BF</id><score>0.12191912</score><fulltext><json:item><original>true</original><mimetype>application/pdf</mimetype><extension>pdf</extension><uri>https://api.istex.fr/document/9662A0EB15066CA1C9647127542C380ABE4D65BF/fulltext/pdf</uri></json:item><json:item><original>false</original><mimetype>application/zip</mimetype><extension>zip</extension><uri>https://api.istex.fr/document/9662A0EB15066CA1C9647127542C380ABE4D65BF/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/9662A0EB15066CA1C9647127542C380ABE4D65BF/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Unstructured Peer-to-Peer Networks: Topological Properties and Search Performance</title><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>Springer-Verlag Berlin Heidelberg, 2005</p></availability><date>2005</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Unstructured Peer-to-Peer Networks: Topological Properties and Search Performance</title><author xml:id="author-1"><persName><forename type="first">George</forename><surname>Fletcher</surname></persName><email>gefletch@indiana.edu</email><affiliation>Computer Science Department, Indiana University, Bloomington, USA</affiliation></author><author xml:id="author-2"><persName><forename type="first">Hardik</forename><surname>Sheth</surname></persName><email>hsheth@indiana.edu</email><affiliation>School of Informatics, Indiana University, Bloomington, USA</affiliation></author><author xml:id="author-3"><persName><forename type="first">Katy</forename><surname>Börner</surname></persName><email>katy@indiana.edu</email><affiliation>School of Library and Information Science, Indiana University, Bloomington, USA</affiliation></author></analytic><monogr><title level="m">Agents and Peer-to-Peer Computing</title><title level="m" type="sub">Third International Workshop, AP2PC 2004, New York, NY, USA, July 19, 2004, Revised and Invited Papers</title><idno type="pISBN">978-3-540-29755-0</idno><idno type="eISBN">978-3-540-31657-2</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="DOI">10.1007/11574781</idno><idno type="book-ID">978-3-540-31657-2</idno><idno type="book-title-ID">127372</idno><idno type="book-sequence-number">3601</idno><idno type="book-volume-number">3601</idno><idno type="book-chapter-count">23</idno><editor><persName><forename type="first">Gianluca</forename><surname>Moro</surname></persName><email>gmoro@deis.unibo.it</email><affiliation>Dept. of Electronics, Computer Science and Systems, University of Bologna, Via Venezia, 52, 47023, Cesena (FC), Italy</affiliation></editor><editor><persName><forename type="first">Sonia</forename><surname>Bergamaschi</surname></persName><email>bergamaschi.sonia@unimo.it</email><affiliation>Dept. of Science Engineering, University of Modena and Reggio-Emilia, via Vignolese, 905, 41100, Modena, Italy</affiliation></editor><editor><persName><forename type="first">Karl</forename><surname>Aberer</surname></persName><email>karl.aberer@epfl.ch</email><affiliation>School of Computer and Communication Sciences, École Polytechnique Fédérale de Lausanne (EPFL), CH-1015, Lausanne, Switzerland</affiliation></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2005"></date><biblScope unit="volume">3601</biblScope><biblScope unit="page" from="14">14</biblScope><biblScope unit="page" to="27">27</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">David</forename><surname>Hutchison</surname></persName><affiliation>Lancaster University, UK</affiliation></editor><editor><persName><forename type="first">Takeo</forename><surname>Kanade</surname></persName><affiliation>Carnegie Mellon University, Pittsburgh, PA, USA</affiliation></editor><editor><persName><forename type="first">Josef</forename><surname>Kittler</surname></persName><affiliation>University of Surrey, Guildford, UK</affiliation></editor><editor><persName><forename type="first">Jon</forename><forename type="first">M.</forename><surname>Kleinberg</surname></persName><affiliation>Cornell University, Ithaca, NY, USA</affiliation></editor><editor><persName><forename type="first">Friedemann</forename><surname>Mattern</surname></persName><affiliation>ETH Zurich, Switzerland</affiliation></editor><editor><persName><forename type="first">John</forename><forename type="first">C.</forename><surname>Mitchell</surname></persName><affiliation>Stanford University, CA, USA</affiliation></editor><editor><persName><forename type="first">Moni</forename><surname>Naor</surname></persName><affiliation>Weizmann Institute of Science, Rehovot, Israel</affiliation></editor><editor><persName><forename type="first">Oscar</forename><surname>Nierstrasz</surname></persName><affiliation>University of Bern, Switzerland</affiliation></editor><editor><persName><forename type="first">C.</forename><surname>Pandu Rangan</surname></persName><affiliation>Indian Institute of Technology, Madras, India</affiliation></editor><editor><persName><forename type="first">Bernhard</forename><surname>Steffen</surname></persName><affiliation>University of Dortmund, Germany</affiliation></editor><editor><persName><forename type="first">Madhu</forename><surname>Sudan</surname></persName><affiliation>Massachusetts Institute of Technology, MA, USA</affiliation></editor><editor><persName><forename type="first">Demetri</forename><surname>Terzopoulos</surname></persName><affiliation>New York University, NY, USA</affiliation></editor><editor><persName><forename type="first">Dough</forename><surname>Tygar</surname></persName><affiliation>University of California, Berkeley, CA, USA</affiliation></editor><editor><persName><forename type="first">Moshe</forename><forename type="first">Y.</forename><surname>Vardi</surname></persName><affiliation>Rice University, Houston, TX, USA</affiliation></editor><editor><persName><forename type="first">Gerhard</forename><surname>Weikum</surname></persName><affiliation>Max-Planck Institute of Computer Science, Saarbruecken, Germany</affiliation></editor><biblScope><date>2005</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="series-Id">558</idno></series><series><title level="s">Lecture Notes in Artificial Intelligence</title><editor><persName><forename type="first">David</forename><surname>Hutchison</surname></persName><affiliation>Lancaster University, UK</affiliation></editor><editor><persName><forename type="first">Takeo</forename><surname>Kanade</surname></persName><affiliation>Carnegie Mellon University, Pittsburgh, PA, USA</affiliation></editor><editor><persName><forename type="first">Josef</forename><surname>Kittler</surname></persName><affiliation>University of Surrey, Guildford, UK</affiliation></editor><editor><persName><forename type="first">Jon</forename><forename type="first">M.</forename><surname>Kleinberg</surname></persName><affiliation>Cornell University, Ithaca, NY, USA</affiliation></editor><editor><persName><forename type="first">Friedemann</forename><surname>Mattern</surname></persName><affiliation>ETH Zurich, Switzerland</affiliation></editor><editor><persName><forename type="first">John</forename><forename type="first">C.</forename><surname>Mitchell</surname></persName><affiliation>Stanford University, CA, USA</affiliation></editor><editor><persName><forename type="first">Moni</forename><surname>Naor</surname></persName><affiliation>Weizmann Institute of Science, Rehovot, Israel</affiliation></editor><editor><persName><forename type="first">Oscar</forename><surname>Nierstrasz</surname></persName><affiliation>University of Bern, Switzerland</affiliation></editor><editor><persName><forename type="first">C.</forename><surname>Pandu Rangan</surname></persName><affiliation>Indian Institute of Technology, Madras, India</affiliation></editor><editor><persName><forename type="first">Bernhard</forename><surname>Steffen</surname></persName><affiliation>University of Dortmund, Germany</affiliation></editor><editor><persName><forename type="first">Madhu</forename><surname>Sudan</surname></persName><affiliation>Massachusetts Institute of Technology, MA, USA</affiliation></editor><editor><persName><forename type="first">Demetri</forename><surname>Terzopoulos</surname></persName><affiliation>New York University, NY, USA</affiliation></editor><editor><persName><forename type="first">Dough</forename><surname>Tygar</surname></persName><affiliation>University of California, Berkeley, CA, USA</affiliation></editor><editor><persName><forename type="first">Moshe</forename><forename type="first">Y.</forename><surname>Vardi</surname></persName><affiliation>Rice University, Houston, TX, USA</affiliation></editor><editor><persName><forename type="first">Gerhard</forename><surname>Weikum</surname></persName><affiliation>Max-Planck Institute of Computer Science, Saarbruecken, Germany</affiliation></editor><editor><persName><forename type="first">Jaime</forename><forename type="first">G.</forename><surname>Carbonell</surname></persName><affiliation>Carnegie Mellon University, Pittsburgh, PA, USA</affiliation></editor><editor><persName><forename type="first">Jörg</forename><surname>Siekmann</surname></persName><affiliation>University of Saarland, Saarbrücken, Germany</affiliation></editor><editor><persName><forename type="first">Gianluca</forename><surname>Moro</surname></persName><email>gmoro@deis.unibo.it</email><affiliation>Dept. of Electronics, Computer Science and Systems, University of Bologna, Via Venezia, 52, 47023, Cesena (FC), Italy</affiliation></editor><editor><persName><forename type="first">Sonia</forename><surname>Bergamaschi</surname></persName><email>bergamaschi.sonia@unimo.it</email><affiliation>Dept. of Science Engineering, University of Modena and Reggio-Emilia, via Vignolese, 905, 41100, Modena, Italy</affiliation></editor><editor><persName><forename type="first">Karl</forename><surname>Aberer</surname></persName><email>karl.aberer@epfl.ch</email><affiliation>School of Computer and Communication Sciences, École Polytechnique Fédérale de Lausanne (EPFL), CH-1015, Lausanne, Switzerland</affiliation></editor><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><biblScope unit="seriesId">1244</biblScope></series><idno type="istex">9662A0EB15066CA1C9647127542C380ABE4D65BF</idno><idno type="DOI">10.1007/11574781_2</idno><idno type="ChapterID">2</idno><idno type="ChapterID">Chap2</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>2005</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: Performing efficient decentralized search is a fundamental problem in Peer-to-Peer (P2P) systems. There has been a significant amount of research recently on developing robust self-organizing P2P topologies that support efficient search. In this paper we discuss four structured and unstructured P2P models (CAN, Chord, PRU, and Hypergrid) and three characteristic search algorithms (BFS, k-Random Walk, and GAPS) for unstructured networks. We report on the results of simulations of these networks and provide measurements of search performance, focusing on search in unstructured networks. We find that the proposed models produce small-world networks, and yet none exhibit power-law degree distributions. Our simulations also suggest that random graphs support decentralized search more effectively than the proposed unstructured P2P models. We also find that on these topologies, the basic breadth-first search algorithm and its simple variants have the lowest search cost.</p></abstract><textClass><keywords scheme="Book-Subject-Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book-Subject-Group"><list><label>I</label><label>I21017</label><label>I13022</label><label>I18040</label><label>I18032</label><label>I24040</label><item><term>Computer Science</term></item><item><term>Artificial Intelligence (incl. Robotics)</term></item><item><term>Computer Communication Networks</term></item><item><term>Information Systems Applications (incl.Internet)</term></item><item><term>Information Storage and Retrieval</term></item><item><term>Computers and Society</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2005">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-09-22">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><original>false</original><mimetype>text/plain</mimetype><extension>txt</extension><uri>https://api.istex.fr/document/9662A0EB15066CA1C9647127542C380ABE4D65BF/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo SeriesType="Series" TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor AffiliationIDS="Aff1"><EditorName DisplayOrder="Western"><GivenName>David</GivenName><FamilyName>Hutchison</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff2"><EditorName DisplayOrder="Western"><GivenName>Takeo</GivenName><FamilyName>Kanade</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff3"><EditorName DisplayOrder="Western"><GivenName>Josef</GivenName><FamilyName>Kittler</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff4"><EditorName DisplayOrder="Western"><GivenName>Jon</GivenName><GivenName>M.</GivenName><FamilyName>Kleinberg</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff5"><EditorName DisplayOrder="Western"><GivenName>Friedemann</GivenName><FamilyName>Mattern</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff6"><EditorName DisplayOrder="Western"><GivenName>John</GivenName><GivenName>C.</GivenName><FamilyName>Mitchell</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff7"><EditorName DisplayOrder="Western"><GivenName>Moni</GivenName><FamilyName>Naor</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff8"><EditorName DisplayOrder="Western"><GivenName>Oscar</GivenName><FamilyName>Nierstrasz</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff9"><EditorName DisplayOrder="Western"><GivenName>C.</GivenName><FamilyName>Pandu Rangan</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff10"><EditorName DisplayOrder="Western"><GivenName>Bernhard</GivenName><FamilyName>Steffen</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff11"><EditorName DisplayOrder="Western"><GivenName>Madhu</GivenName><FamilyName>Sudan</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff12"><EditorName DisplayOrder="Western"><GivenName>Demetri</GivenName><FamilyName>Terzopoulos</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff13"><EditorName DisplayOrder="Western"><GivenName>Dough</GivenName><FamilyName>Tygar</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff14"><EditorName DisplayOrder="Western"><GivenName>Moshe</GivenName><GivenName>Y.</GivenName><FamilyName>Vardi</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff15"><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Weikum</FamilyName></EditorName></Editor><Affiliation ID="Aff1"><OrgName>Lancaster University</OrgName><OrgAddress><Country>UK</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgName>Carnegie Mellon University</OrgName><OrgAddress><City>Pittsburgh</City><State>PA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgName>University of Surrey</OrgName><OrgAddress><City>Guildford</City><Country>UK</Country></OrgAddress></Affiliation><Affiliation ID="Aff4"><OrgName>Cornell University</OrgName><OrgAddress><City>Ithaca</City><State>NY</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff5"><OrgName>ETH Zurich</OrgName><OrgAddress><Country>Switzerland</Country></OrgAddress></Affiliation><Affiliation ID="Aff6"><OrgName>Stanford University</OrgName><OrgAddress><City>CA</City><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff7"><OrgName>Weizmann Institute of Science</OrgName><OrgAddress><City>Rehovot</City><Country>Israel</Country></OrgAddress></Affiliation><Affiliation ID="Aff8"><OrgName>University of Bern</OrgName><OrgAddress><Country>Switzerland</Country></OrgAddress></Affiliation><Affiliation ID="Aff9"><OrgName>Indian Institute of Technology</OrgName><OrgAddress><City>Madras</City><Country>India</Country></OrgAddress></Affiliation><Affiliation ID="Aff10"><OrgName>University of Dortmund</OrgName><OrgAddress><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff11"><OrgName>Massachusetts Institute of Technology</OrgName><OrgAddress><City>MA</City><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff12"><OrgName>New York University</OrgName><OrgAddress><City>NY</City><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff13"><OrgName>University of California</OrgName><OrgAddress><City>Berkeley</City><State>CA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff14"><OrgName>Rice University</OrgName><OrgAddress><City>Houston</City><State>TX</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff15"><OrgName>Max-Planck Institute of Computer Science</OrgName><OrgAddress><City>Saarbruecken</City><Country>Germany</Country></OrgAddress></Affiliation></EditorGroup></SeriesHeader><SubSeries><SubSeriesInfo><SubSeriesID>1244</SubSeriesID><SubSeriesPrintISSN>0302-9743</SubSeriesPrintISSN><SubSeriesElectronicISSN>1611-3349</SubSeriesElectronicISSN><SubSeriesTitle Language="En">Lecture Notes in Artificial Intelligence</SubSeriesTitle></SubSeriesInfo><SubSeriesHeader><EditorGroup><Editor AffiliationIDS="Aff16"><EditorName DisplayOrder="Western"><GivenName>Jaime</GivenName><GivenName>G.</GivenName><FamilyName>Carbonell</FamilyName></EditorName></Editor><Editor AffiliationIDS="Aff17"><EditorName DisplayOrder="Western"><GivenName>Jörg</GivenName><FamilyName>Siekmann</FamilyName></EditorName></Editor><Affiliation ID="Aff16"><OrgName>Carnegie Mellon University</OrgName><OrgAddress><City>Pittsburgh</City><State>PA</State><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff17"><OrgName>University of Saarland</OrgName><OrgAddress><City>Saarbrücken</City><Country>Germany</Country></OrgAddress></Affiliation></EditorGroup></SubSeriesHeader></SubSeries><Book Language="En"><BookInfo BookProductType="Proceedings" ContainsESM="No" Language="En" MediaType="eBook" NumberingDepth="2" NumberingStyle="ContentOnly" OutputMedium="All" TocLevels="0"><BookID>978-3-540-31657-2</BookID><BookTitle>Agents and Peer-to-Peer Computing</BookTitle><BookSubTitle>Third International Workshop, AP2PC 2004, New York, NY, USA, July 19, 2004, Revised and Invited Papers</BookSubTitle><BookVolumeNumber>3601</BookVolumeNumber><BookSequenceNumber>3601</BookSequenceNumber><BookDOI>10.1007/11574781</BookDOI><BookTitleID>127372</BookTitleID><BookPrintISBN>978-3-540-29755-0</BookPrintISBN><BookElectronicISBN>978-3-540-31657-2</BookElectronicISBN><BookChapterCount>23</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2005</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I21017" Priority="1" Type="Secondary">Artificial Intelligence (incl. Robotics)</BookSubject><BookSubject Code="I13022" Priority="2" Type="Secondary">Computer Communication Networks</BookSubject><BookSubject Code="I18040" Priority="3" Type="Secondary">Information Systems Applications (incl.Internet)</BookSubject><BookSubject Code="I18032" Priority="4" Type="Secondary">Information Storage and Retrieval</BookSubject><BookSubject Code="I24040" Priority="5" Type="Secondary">Computers and Society</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup><BookContext><SeriesID>558</SeriesID><SubSeriesID>1244</SubSeriesID></BookContext></BookInfo><BookHeader><EditorGroup><Editor AffiliationIDS="Aff18"><EditorName DisplayOrder="Western"><GivenName>Gianluca</GivenName><FamilyName>Moro</FamilyName></EditorName><Contact><Email>gmoro@deis.unibo.it</Email></Contact></Editor><Editor AffiliationIDS="Aff19"><EditorName DisplayOrder="Western"><GivenName>Sonia</GivenName><FamilyName>Bergamaschi</FamilyName></EditorName><Contact><Email>bergamaschi.sonia@unimo.it</Email></Contact></Editor><Editor AffiliationIDS="Aff20"><EditorName DisplayOrder="Western"><GivenName>Karl</GivenName><FamilyName>Aberer</FamilyName></EditorName><Contact><Email>karl.aberer@epfl.ch</Email></Contact></Editor><Affiliation ID="Aff18"><OrgDivision>Dept. of Electronics, Computer Science and Systems</OrgDivision><OrgName>University of Bologna</OrgName><OrgAddress><Street>Via Venezia, 52</Street><Postcode>47023</Postcode><City>Cesena (FC)</City><Country>Italy</Country></OrgAddress></Affiliation><Affiliation ID="Aff19"><OrgDivision>Dept. of Science Engineering</OrgDivision><OrgName>University of Modena and Reggio-Emilia</OrgName><OrgAddress><Street>via Vignolese, 905</Street><Postcode>41100</Postcode><City>Modena</City><Country>Italy</Country></OrgAddress></Affiliation><Affiliation ID="Aff20"><OrgDivision>School of Computer and Communication Sciences</OrgDivision><OrgName>École Polytechnique Fédérale de Lausanne (EPFL)</OrgName><OrgAddress><Postcode>CH-1015</Postcode><City>Lausanne</City><Country>Switzerland</Country></OrgAddress></Affiliation></EditorGroup></BookHeader><Part ID="Part2"><PartInfo TocLevels="0"><PartID>2</PartID><PartSequenceNumber>2</PartSequenceNumber><PartTitle>Peer-to-Peer Network and Search Performance</PartTitle><PartChapterCount>4</PartChapterCount><PartContext><SeriesID>558</SeriesID><BookTitle>Agents and Peer-to-Peer Computing</BookTitle></PartContext></PartInfo><Chapter ID="Chap2" Language="En"><ChapterInfo ChapterType="OriginalPaper" ContainsESM="No" NumberingDepth="2" NumberingStyle="ContentOnly" TocLevels="0"><ChapterID>2</ChapterID><ChapterDOI>10.1007/11574781_2</ChapterDOI><ChapterSequenceNumber>2</ChapterSequenceNumber><ChapterTitle Language="En">Unstructured Peer-to-Peer Networks: Topological Properties and Search Performance</ChapterTitle><ChapterFirstPage>14</ChapterFirstPage><ChapterLastPage>27</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag Berlin Heidelberg</CopyrightHolderName><CopyrightYear>2005</CopyrightYear></ChapterCopyright><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><PartID>2</PartID><BookID>978-3-540-31657-2</BookID><BookTitle>Agents and Peer-to-Peer Computing</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff21"><AuthorName DisplayOrder="Western"><GivenName>George</GivenName><GivenName>H.</GivenName><GivenName>L.</GivenName><FamilyName>Fletcher</FamilyName></AuthorName><Contact><Email>gefletch@indiana.edu</Email></Contact></Author><Author AffiliationIDS="Aff22"><AuthorName DisplayOrder="Western"><GivenName>Hardik</GivenName><GivenName>A.</GivenName><FamilyName>Sheth</FamilyName></AuthorName><Contact><Email>hsheth@indiana.edu</Email></Contact></Author><Author AffiliationIDS="Aff23"><AuthorName DisplayOrder="Western"><GivenName>Katy</GivenName><FamilyName>Börner</FamilyName></AuthorName><Contact><Email>katy@indiana.edu</Email></Contact></Author><Affiliation ID="Aff21"><OrgDivision>Computer Science Department</OrgDivision><OrgName>Indiana University</OrgName><OrgAddress><City>Bloomington</City><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff22"><OrgDivision>School of Informatics</OrgDivision><OrgName>Indiana University</OrgName><OrgAddress><City>Bloomington</City><Country>USA</Country></OrgAddress></Affiliation><Affiliation ID="Aff23"><OrgDivision>School of Library and Information Science</OrgDivision><OrgName>Indiana University</OrgName><OrgAddress><City>Bloomington</City><Country>USA</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>Performing efficient decentralized search is a fundamental problem in Peer-to-Peer (P2P) systems. There has been a significant amount of research recently on developing robust self-organizing P2P topologies that support efficient search. In this paper we discuss four structured and unstructured P2P models (CAN, Chord, PRU, and Hypergrid) and three characteristic search algorithms (BFS, k-Random Walk, and GAPS) for unstructured networks. We report on the results of simulations of these networks and provide measurements of search performance, focusing on search in unstructured networks. We find that the proposed models produce small-world networks, and yet none exhibit power-law degree distributions. Our simulations also suggest that random graphs support decentralized search more effectively than the proposed unstructured P2P models. We also find that on these topologies, the basic breadth-first search algorithm and its simple variants have the lowest search cost.</Para></Abstract></ChapterHeader><NoBody></NoBody></Chapter></Part></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Unstructured Peer-to-Peer Networks: Topological Properties and Search Performance</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>Unstructured Peer-to-Peer Networks: Topological Properties and Search Performance</title></titleInfo><name type="personal"><namePart type="given">George</namePart><namePart type="given">H.</namePart><namePart type="given">L.</namePart><namePart type="family">Fletcher</namePart><affiliation>Computer Science Department, Indiana University, Bloomington, USA</affiliation><affiliation>E-mail: gefletch@indiana.edu</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Hardik</namePart><namePart type="given">A.</namePart><namePart type="family">Sheth</namePart><affiliation>School of Informatics, Indiana University, Bloomington, USA</affiliation><affiliation>E-mail: hsheth@indiana.edu</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Katy</namePart><namePart type="family">Börner</namePart><affiliation>School of Library and Information Science, Indiana University, Bloomington, USA</affiliation><affiliation>E-mail: katy@indiana.edu</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference" displayLabel="OriginalPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2005</dateIssued><copyrightDate encoding="w3cdtf">2005</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">Abstract: Performing efficient decentralized search is a fundamental problem in Peer-to-Peer (P2P) systems. There has been a significant amount of research recently on developing robust self-organizing P2P topologies that support efficient search. In this paper we discuss four structured and unstructured P2P models (CAN, Chord, PRU, and Hypergrid) and three characteristic search algorithms (BFS, k-Random Walk, and GAPS) for unstructured networks. We report on the results of simulations of these networks and provide measurements of search performance, focusing on search in unstructured networks. We find that the proposed models produce small-world networks, and yet none exhibit power-law degree distributions. Our simulations also suggest that random graphs support decentralized search more effectively than the proposed unstructured P2P models. We also find that on these topologies, the basic breadth-first search algorithm and its simple variants have the lowest search cost.</abstract><relatedItem type="host"><titleInfo><title>Agents and Peer-to-Peer Computing</title><subTitle>Third International Workshop, AP2PC 2004, New York, NY, USA, July 19, 2004, Revised and Invited Papers</subTitle></titleInfo><name type="personal"><namePart type="given">Gianluca</namePart><namePart type="family">Moro</namePart><affiliation>Dept. of Electronics, Computer Science and Systems, University of Bologna, Via Venezia, 52, 47023, Cesena (FC), Italy</affiliation><affiliation>E-mail: gmoro@deis.unibo.it</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Sonia</namePart><namePart type="family">Bergamaschi</namePart><affiliation>Dept. of Science Engineering, University of Modena and Reggio-Emilia, via Vignolese, 905, 41100, Modena, Italy</affiliation><affiliation>E-mail: bergamaschi.sonia@unimo.it</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Karl</namePart><namePart type="family">Aberer</namePart><affiliation>School of Computer and Communication Sciences, École Polytechnique Fédérale de Lausanne (EPFL), CH-1015, Lausanne, Switzerland</affiliation><affiliation>E-mail: karl.aberer@epfl.ch</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">2005</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I21017">Artificial Intelligence (incl. Robotics)</topic><topic authority="SpringerSubjectCodes" authorityURI="I13022">Computer Communication Networks</topic><topic authority="SpringerSubjectCodes" authorityURI="I18040">Information Systems Applications (incl.Internet)</topic><topic authority="SpringerSubjectCodes" authorityURI="I18032">Information Storage and Retrieval</topic><topic authority="SpringerSubjectCodes" authorityURI="I24040">Computers and Society</topic></subject><identifier type="DOI">10.1007/11574781</identifier><identifier type="ISBN">978-3-540-29755-0</identifier><identifier type="eISBN">978-3-540-31657-2</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">127372</identifier><identifier type="BookID">978-3-540-31657-2</identifier><identifier type="BookChapterCount">23</identifier><identifier type="BookVolumeNumber">3601</identifier><identifier type="BookSequenceNumber">3601</identifier><identifier type="PartChapterCount">4</identifier><part><date>2005</date><detail type="part"><title>Peer-to-Peer Network and Search Performance</title></detail><detail type="volume"><number>3601</number><caption>vol.</caption></detail><extent unit="pages"><start>14</start><end>27</end></extent></part><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2005</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">David</namePart><namePart type="family">Hutchison</namePart><affiliation>Lancaster University, UK</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Takeo</namePart><namePart type="family">Kanade</namePart><affiliation>Carnegie Mellon University, Pittsburgh, PA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Josef</namePart><namePart type="family">Kittler</namePart><affiliation>University of Surrey, Guildford, UK</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jon</namePart><namePart type="given">M.</namePart><namePart type="family">Kleinberg</namePart><affiliation>Cornell University, Ithaca, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Friedemann</namePart><namePart type="family">Mattern</namePart><affiliation>ETH Zurich, Switzerland</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">John</namePart><namePart type="given">C.</namePart><namePart type="family">Mitchell</namePart><affiliation>Stanford University, CA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moni</namePart><namePart type="family">Naor</namePart><affiliation>Weizmann Institute of Science, Rehovot, Israel</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Oscar</namePart><namePart type="family">Nierstrasz</namePart><affiliation>University of Bern, Switzerland</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">C.</namePart><namePart type="family">Pandu Rangan</namePart><affiliation>Indian Institute of Technology, Madras, India</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Bernhard</namePart><namePart type="family">Steffen</namePart><affiliation>University of Dortmund, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Madhu</namePart><namePart type="family">Sudan</namePart><affiliation>Massachusetts Institute of Technology, MA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Demetri</namePart><namePart type="family">Terzopoulos</namePart><affiliation>New York University, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Dough</namePart><namePart type="family">Tygar</namePart><affiliation>University of California, Berkeley, CA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moshe</namePart><namePart type="given">Y.</namePart><namePart type="family">Vardi</namePart><affiliation>Rice University, Houston, TX, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Weikum</namePart><affiliation>Max-Planck Institute of Computer Science, Saarbruecken, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">2005</copyrightDate><issuance>serial</issuance></originInfo><relatedItem type="constituent"><titleInfo><title>Lecture Notes in Artificial Intelligence</title></titleInfo><name type="personal"><namePart type="given">David</namePart><namePart type="family">Hutchison</namePart><affiliation>Lancaster University, UK</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Takeo</namePart><namePart type="family">Kanade</namePart><affiliation>Carnegie Mellon University, Pittsburgh, PA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Josef</namePart><namePart type="family">Kittler</namePart><affiliation>University of Surrey, Guildford, UK</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jon</namePart><namePart type="given">M.</namePart><namePart type="family">Kleinberg</namePart><affiliation>Cornell University, Ithaca, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Friedemann</namePart><namePart type="family">Mattern</namePart><affiliation>ETH Zurich, Switzerland</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">John</namePart><namePart type="given">C.</namePart><namePart type="family">Mitchell</namePart><affiliation>Stanford University, CA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moni</namePart><namePart type="family">Naor</namePart><affiliation>Weizmann Institute of Science, Rehovot, Israel</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Oscar</namePart><namePart type="family">Nierstrasz</namePart><affiliation>University of Bern, Switzerland</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">C.</namePart><namePart type="family">Pandu Rangan</namePart><affiliation>Indian Institute of Technology, Madras, India</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Bernhard</namePart><namePart type="family">Steffen</namePart><affiliation>University of Dortmund, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Madhu</namePart><namePart type="family">Sudan</namePart><affiliation>Massachusetts Institute of Technology, MA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Demetri</namePart><namePart type="family">Terzopoulos</namePart><affiliation>New York University, NY, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Dough</namePart><namePart type="family">Tygar</namePart><affiliation>University of California, Berkeley, CA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Moshe</namePart><namePart type="given">Y.</namePart><namePart type="family">Vardi</namePart><affiliation>Rice University, Houston, TX, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Weikum</namePart><affiliation>Max-Planck Institute of Computer Science, Saarbruecken, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jaime</namePart><namePart type="given">G.</namePart><namePart type="family">Carbonell</namePart><affiliation>Carnegie Mellon University, Pittsburgh, PA, USA</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Jörg</namePart><namePart type="family">Siekmann</namePart><affiliation>University of Saarland, Saarbrücken, Germany</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Gianluca</namePart><namePart type="family">Moro</namePart><affiliation>Dept. of Electronics, Computer Science and Systems, University of Bologna, Via Venezia, 52, 47023, Cesena (FC), Italy</affiliation><affiliation>E-mail: gmoro@deis.unibo.it</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Sonia</namePart><namePart type="family">Bergamaschi</namePart><affiliation>Dept. of Science Engineering, University of Modena and Reggio-Emilia, via Vignolese, 905, 41100, Modena, Italy</affiliation><affiliation>E-mail: bergamaschi.sonia@unimo.it</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Karl</namePart><namePart type="family">Aberer</namePart><affiliation>School of Computer and Communication Sciences, École Polytechnique Fédérale de Lausanne (EPFL), CH-1015, Lausanne, Switzerland</affiliation><affiliation>E-mail: karl.aberer@epfl.ch</affiliation><role><roleTerm type="text">editor</roleTerm></role></name><genre type="sub-series"></genre><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SubSeriesID">1244</identifier></relatedItem><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag Berlin Heidelberg, 2005</recordOrigin></recordInfo></relatedItem><identifier type="istex">9662A0EB15066CA1C9647127542C380ABE4D65BF</identifier><identifier type="DOI">10.1007/11574781_2</identifier><identifier type="ChapterID">2</identifier><identifier type="ChapterID">Chap2</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag Berlin Heidelberg, 2005</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag Berlin Heidelberg, 2005</recordOrigin></recordInfo></mods></metadata><enrichments><json:item><type>multicat</type><uri>https://api.istex.fr/document/9662A0EB15066CA1C9647127542C380ABE4D65BF/enrichments/multicat</uri></json:item><istex:refBibTEI uri="https://api.istex.fr/document/9662A0EB15066CA1C9647127542C380ABE4D65BF/enrichments/refBib"><teiHeader></teiHeader><text><front></front><body></body><back><listBibl><biblStruct xml:id="b0"><analytic><title level="a" type="main">Search in Power-Law Networks</title><author><persName><forename type="first">Lada</forename><surname>Adamic</surname></persName></author><author><persName><forename type="first">Rajan</forename><surname>Lukose</surname></persName></author><author><persName><forename type="first">Amit</forename><surname>Puniyani</surname></persName></author><author><persName><forename type="first">Bernardo</forename><surname>Huberman</surname></persName></author></analytic><monogr><title level="j">Physical Review E</title><imprint><biblScope unit="volume">64</biblScope><biblScope unit="issue">4</biblScope><biblScope unit="page" from="46135" to="46143"></biblScope><date type="published" when="2001"></date></imprint></monogr></biblStruct><biblStruct xml:id="b1"><analytic><title level="a" type="main">Small World Peer Networks in Distributed Web Search</title><author><persName><forename type="first">Ruj</forename><surname>Akavipat</surname></persName></author><author><persName><forename type="first">Le-Shin</forename><surname>Wu</surname></persName></author><author><persName><forename type="first">Filippo</forename><surname>Menczer</surname></persName></author></analytic><monogr><title level="m">Proc. ACM WWW2004</title><meeting>. ACM WWW2004</meeting><imprint><date type="published" when="2004"></date><biblScope unit="page" from="396" to="397"></biblScope></imprint></monogr></biblStruct><biblStruct xml:id="b2"><analytic><title level="a" type="main">Anthill: A Framework for the Development of Agent-Based Peer-to-Peer Systems</title><author><persName><forename type="first">Réka</forename><surname>Albert</surname></persName></author><author><persName><forename type="first">Albert-László</forename><surname>Barabási</surname></persName></author><author><persName><forename type="first">¨</forename><forename type="middle">O</forename></persName></author><author><persName><forename type="first">H</forename><surname>Meling</surname></persName></author><author><persName><forename type="first">A</forename><surname>Montresor</surname></persName></author></analytic><monogr><title level="m">Proc. IEEE ICDCS'02</title><meeting>. IEEE ICDCS'02</meeting><imprint><date type="published" when="2002"></date><biblScope unit="page" from="47" to="97"></biblScope></imprint></monogr></biblStruct><biblStruct xml:id="b3"><analytic><title level="a" type="main">Criticality-based Analysis and Design of Unstructured Peer-to-Peer Networks as " Complex Systems</title><author><persName><forename type="first">Farnoush</forename><surname>Banaei-Kashani</surname></persName></author><author><persName><forename type="first">Cyrus</forename><surname>Shahabi</surname></persName></author></analytic><monogr><title level="m">Proc. IEEE/ACM CCGRID'03</title><meeting>. IEEE/ACM CCGRID'03</meeting><imprint><date type="published" when="2003"></date><biblScope unit="page" from="351" to="358"></biblScope></imprint></monogr></biblStruct><biblStruct xml:id="b4"><monogr><title level="m" type="main">Pajek: Package for Large Network Analysis</title><author><persName><forename type="first">Vladimir</forename><surname>Batagelj</surname></persName></author><author><persName><forename type="first">Andrej</forename><surname>Mrvar</surname></persName></author><imprint></imprint></monogr></biblStruct><biblStruct xml:id="b5"><analytic><title level="a" type="main">Ucinet for Windows: Software for Social Network Analysis</title><author><persName><forename type="first">S</forename><forename type="middle">P</forename><surname>Borgatti</surname></persName></author><author><persName><forename type="first">M</forename><forename type="middle">G</forename><surname>Everett</surname></persName></author><author><persName><forename type="first">L</forename><forename type="middle">C</forename><surname>Freeman</surname></persName></author></analytic><monogr><title level="m">Harvard: Analytic Technologies</title><imprint><date type="published" when="2002"></date></imprint></monogr></biblStruct><biblStruct xml:id="b6"><analytic><title level="a" type="main">Middle-Agents for the Internet</title><author><persName><forename type="first">K</forename><surname>Decker</surname></persName></author><author><persName><forename type="first">K</forename><surname>Sycara</surname></persName></author><author><persName><forename type="first">M</forename><surname>Williamson</surname></persName></author></analytic><monogr><title level="m">Proc. IJCAI97</title><meeting>. IJCAI97</meeting><imprint><date type="published" when="1997"></date><biblScope unit="page" from="578" to="583"></biblScope></imprint></monogr></biblStruct><biblStruct xml:id="b7"><analytic><title level="a" type="main">A Peer-to-Peer Approach to Resource Discovery in Multi-Agent Systems</title><author><persName><forename type="first">Vassilios</forename><forename type="middle">V</forename><surname>Dimakopoulos</surname></persName></author><author><persName><forename type="first">Evaggelia</forename><surname>Pitoura</surname></persName></author></analytic><monogr><title level="m">Proc. CIA 2003</title><meeting>. CIA 2003</meeting><imprint><date type="published" when="2003"></date><biblScope unit="page" from="62" to="77"></biblScope></imprint></monogr></biblStruct><biblStruct xml:id="b8"><analytic><title level="a" type="main">On Power-Law Relationships of the Internet Topology</title><author><persName><forename type="first">M</forename><surname>Faloutsos</surname></persName></author><author><persName><forename type="first">P</forename><surname>Faloutsos</surname></persName></author><author><persName><forename type="first">C</forename><surname>Faloutsos</surname></persName></author></analytic><monogr><title level="m">Proc. ACM SIGCOMM</title><meeting>. ACM SIGCOMM</meeting><imprint><date type="published" when="1999"></date><biblScope unit="page" from="251" to="262"></biblScope></imprint></monogr></biblStruct><biblStruct xml:id="b9"><analytic><title level="a" type="main">Modeling Peer-to-Peer Network Topologies Through</title><author><persName><forename type="first">M</forename><surname>Jovanovi´jovanovi´c</surname></persName></author><author><persName><forename type="first">F</forename><surname>Annexstein</surname></persName></author><author><persName><forename type="first">K</forename><surname>Berman</surname></persName></author></analytic><monogr><title level="j">Small-World " Models and Power Laws. IX Telecommunications Forum TELFOR</title><imprint><date type="published" when="2001"></date></imprint></monogr></biblStruct><biblStruct xml:id="b10"><analytic><title level="a" type="main">A Local Search Mechanism for Peer-to-Peer Networks</title><author><persName><surname>Kalogeraki</surname></persName></author><author><persName><forename type="first">Dimitrios</forename><surname>Vana</surname></persName></author><author><persName><forename type="first">D</forename><surname>Gunopulos</surname></persName></author><author><persName><surname>Zeinalipour-Yazti</surname></persName></author></analytic><monogr><title level="m">Proc. ACM CIKM'02</title><meeting>. ACM CIKM'02</meeting><imprint><date type="published" when="2002-11"></date><biblScope unit="page" from="300" to="307"></biblScope></imprint></monogr></biblStruct><biblStruct xml:id="b11"><analytic><title level="a" type="main">Navigation in a Small World</title><author><persName><forename type="first">Jon</forename><surname>Kleinberg</surname></persName></author></analytic><monogr><title level="j">Nature</title><imprint><biblScope unit="volume">406</biblScope><biblScope unit="page">845</biblScope><date type="published" when="2000-08"></date></imprint></monogr></biblStruct><biblStruct xml:id="b12"><analytic><title level="a" type="main">Multi-Agent Systems and Peer-to-Peer Computing: Methods , Systems and Challenges</title><author><persName><forename type="first">Manolis</forename><surname>Koubarakis</surname></persName></author></analytic><monogr><title level="m">Proc. CIA 2003</title><meeting>. CIA 2003</meeting><imprint><date type="published" when="2003"></date><biblScope unit="page" from="46" to="61"></biblScope></imprint></monogr></biblStruct><biblStruct xml:id="b13"><analytic><title level="a" type="main">Search and Replication in Unstructured Peer-to-Peer Networks</title><author><persName><forename type="first">Qin</forename><surname>Lv</surname></persName></author></analytic><monogr><title level="m">Proc. ACM ICS'02</title><meeting>. ACM ICS'02</meeting><imprint><date type="published" when="2002"></date><biblScope unit="page" from="84" to="95"></biblScope></imprint></monogr></biblStruct><biblStruct xml:id="b14"><monogr><title level="m" type="main">The Swarm Simulation System, A Toolkit for Building Multi-Agent Simulations</title><author><persName><forename type="first">N</forename><surname>Minar</surname></persName></author><author><persName><forename type="first">R</forename><surname>Burkhart</surname></persName></author><author><persName><forename type="first">C</forename><surname>Langton</surname></persName></author><author><persName><forename type="first">M</forename><surname>Askenazi</surname></persName></author><imprint><date type="published" when="1996-06"></date><pubPlace>Swarm Development Group</pubPlace></imprint></monogr></biblStruct><biblStruct xml:id="b15"><monogr><title></title><author><persName><forename type="first">P2p</forename><surname>Unstructured</surname></persName></author><author><persName><surname>Networks</surname></persName></author><imprint><publisher>Topological Properties and Search Performance</publisher></imprint></monogr></biblStruct><biblStruct xml:id="b16"><monogr><title level="m" type="main">Peer-to-Peer Computing</title><author><persName><forename type="first">Dejan</forename><forename type="middle">S</forename><surname>Milojiči´milojiči´c</surname></persName></author><imprint><date type="published" when="2002"></date></imprint></monogr></biblStruct><biblStruct xml:id="b17"><analytic><title level="a" type="main">The Structure and Function of Complex Networks</title><author><persName><forename type="first">M</forename><forename type="middle">E J</forename><surname>Newman</surname></persName></author></analytic><monogr><title level="j">SIAM Review</title><imprint><biblScope unit="volume">45</biblScope><biblScope unit="issue">2</biblScope><biblScope unit="page" from="167" to="256"></biblScope><date type="published" when="2003"></date></imprint></monogr></biblStruct><biblStruct xml:id="b18"><analytic><title level="a" type="main">Building Low- Diameter Peer-to-Peer Networks</title><author><persName><forename type="first">G</forename><surname>Pandurangan</surname></persName></author><author><persName><forename type="first">Eli</forename><surname>Prabhakar Raghavan</surname></persName></author><author><persName><surname>Upfal</surname></persName></author></analytic><monogr><title level="j">IEEE J. Select. Areas Commun</title><imprint><biblScope unit="volume">21</biblScope><biblScope unit="issue">6</biblScope><biblScope unit="page" from="995" to="1002"></biblScope><date type="published" when="2003-08"></date></imprint></monogr></biblStruct><biblStruct xml:id="b19"><analytic><title level="a" type="main">A Scalable Content-Addressable Network</title><author><persName><forename type="first">Sylvia</forename><surname>Ratnasamy</surname></persName></author></analytic><monogr><title level="m">Proc. ACM SIGCOMM</title><meeting>. ACM SIGCOMM</meeting><imprint><date type="published" when="2001-08"></date><biblScope unit="page" from="161" to="172"></biblScope></imprint></monogr></biblStruct><biblStruct xml:id="b20"><analytic><title level="a" type="main">Beyond Anarchy: Self Organized Topology for Peer-to-Peer Networks</title><author><persName><forename type="first">Fabrice</forename><surname>Saffre</surname></persName></author><author><persName><forename type="first">Robert</forename><surname>Ghanea-Hercock</surname></persName></author></analytic><monogr><title level="j">Complexity</title><imprint><biblScope unit="volume">9</biblScope><biblScope unit="issue">2</biblScope><biblScope unit="page" from="49" to="53"></biblScope><date type="published" when="2003"></date></imprint></monogr></biblStruct><biblStruct xml:id="b21"><analytic><title level="a" type="main">Percolation Search in Power Law Networks: Making Unstructured Peer-to-Peer Networks Scalable</title><author><persName><forename type="first">Nima</forename><surname>Sarshar</surname></persName></author><author><persName><forename type="first">P</forename><forename type="middle">Oscar</forename><surname>Boykin</surname></persName></author><author><persName><forename type="first">Vwani</forename><surname>Roychowdhury</surname></persName></author></analytic><monogr><title level="m">Proc. IEEE P2P2004</title><meeting>. IEEE P2P2004</meeting><imprint><date type="published" when="2004"></date><biblScope unit="page" from="2" to="9"></biblScope></imprint></monogr></biblStruct><biblStruct xml:id="b22"><analytic><title level="a" type="main">A Scalable Agent Location Mechanism</title><author><persName><forename type="first">O</forename><surname>Shehory</surname></persName></author></analytic><monogr><title level="m">Proc. ATAL'99 Intelligent Agents VI</title><meeting>. ATAL'99 Intelligent Agents VI</meeting><imprint><date type="published" when="1999"></date><biblScope unit="page" from="162" to="172"></biblScope></imprint></monogr></biblStruct><biblStruct xml:id="b23"><analytic><title level="a" type="main">Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications</title><author><persName><forename type="first">Ion</forename><surname>Stoica</surname></persName></author></analytic><monogr><title level="j">IEEE/ACM Trans. on Networking</title><imprint><biblScope unit="volume">11</biblScope><biblScope unit="issue">1</biblScope><biblScope unit="page" from="17" to="32"></biblScope><date type="published" when="2003-02"></date></imprint></monogr></biblStruct><biblStruct xml:id="b24"><analytic><title level="a" type="main">A Comparison of Peer-to-Peer Search Methods</title><author><persName><forename type="first">Dimitrios</forename><surname>Tsoumakos</surname></persName></author><author><persName><forename type="first">Nick</forename><surname>Roussopoulos</surname></persName></author></analytic><monogr><title level="m">Proc. ACM WebDB</title><meeting>. ACM WebDB</meeting><imprint><date type="published" when="2003"></date><biblScope unit="page" from="61" to="66"></biblScope></imprint></monogr></biblStruct><biblStruct xml:id="b25"><analytic><title level="a" type="main">Adaptive Probabilistic Search for Peer-to-Peer Networks</title><author><persName><forename type="first">Dimitrios</forename><surname>Tsoumakos</surname></persName></author><author><persName><forename type="first">Nick</forename><surname>Roussopoulos</surname></persName></author></analytic><monogr><title level="m">Proc. IEEE P2P2003</title><meeting>. IEEE P2P2003</meeting><imprint><date type="published" when="2003"></date><biblScope unit="page" from="102" to="109"></biblScope></imprint></monogr></biblStruct><biblStruct xml:id="b26"><analytic><title level="a" type="main">Search in a Small World</title><author><persName><forename type="first">Toby</forename><surname>Walsh</surname></persName></author></analytic><monogr><title level="m">Proc. IJCAI99</title><meeting>. IJCAI99</meeting><imprint><date type="published" when="1999-08"></date><biblScope unit="page" from="1172" to="1177"></biblScope></imprint></monogr></biblStruct><biblStruct xml:id="b27"><analytic><title level="a" type="main">Collective Dynamics of 'Small-World' Networks</title><author><persName><forename type="first">Duncan</forename><surname>Watts</surname></persName></author><author><persName><forename type="first">Steven</forename><surname>Strogatz</surname></persName></author></analytic><monogr><title level="j">Nature</title><imprint><biblScope unit="volume">393</biblScope><biblScope unit="page" from="440" to="442"></biblScope><date type="published" when="1998-06"></date></imprint></monogr></biblStruct><biblStruct xml:id="b28"><analytic><title level="a" type="main">Improving Search in Peer-to-Peer Networks</title><author><persName><forename type="first">Beverly</forename><surname>Yang</surname></persName></author><author><persName><forename type="first">Hector</forename><surname>Garcia-Molina</surname></persName></author></analytic><monogr><title level="m">Proc. IEEE ICDCS'02</title><meeting>. IEEE ICDCS'02</meeting><imprint><date type="published" when="2002"></date><biblScope unit="page" from="5" to="14"></biblScope></imprint></monogr></biblStruct></listBibl></back></text></istex:refBibTEI><json:item><type>refBibs</type><uri>https://api.istex.fr/document/9662A0EB15066CA1C9647127542C380ABE4D65BF/enrichments/refBibs</uri></json:item></enrichments></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Ticri/CIDE/explor/CyberinfraV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000578 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 000578 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Ticri/CIDE
|area= CyberinfraV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:9662A0EB15066CA1C9647127542C380ABE4D65BF
|texte= Unstructured Peer-to-Peer Networks: Topological Properties and Search Performance
}}
| This area was generated with Dilib version V0.6.25. |  |