On Using Histograms as Routing Indexes in Peer-to-Peer Systems
Lecture notes in computer sciencePublished 1 January 2005
Yannis Petrakis, Georgia Koloniari, Evaggelia Pitoura
Citations23
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work describes a decentralized procedure for clustering similar nodes based on histograms and shows that using histograms to cluster similar nodes and to route queries increases the number of results returned for a given number of nodes visited.
Abstract
Peer-to-peer systems offer an efficient means for sharing data among autonomous nodes. A central issue is locating the nodes with data matching a user query. A decentralized solution to this problem is based on using routing indexes which are data structures that describe the content of neighboring nodes. Each node uses its routing index to route a query towards those of its neighbors that provide the largest number of results. We consider using histograms as routing indexes. We describe a decentralized procedure for clustering similar nodes based on histograms. Similarity between nodes is defined based on the set of queries they match and related with the distance between their histograms. Our experimental results show that using histograms to cluster similar nodes and to route queries increases the number of results returned for a given number of nodes visited.
Keywords
Computer Science
Chord
9,645 Citations2001Ion Stoica, Robert Morris +3 more
Results from theoretical analysis, simulations, and experiments show that Chord is scalable, with communication cost and the state maintained by each node scaling logarithmically with the number of Chord nodes.
A scalable content-addressable network
6,407 Citations2001Sylvia Ratnasamy, Paul Francis +3 more
The concept of a Content-Addressable Network (CAN) as a distributed infrastructure that provides hash table-like functionality on Internet-like scales is introduced and its scalability, robustness and low-latency properties are demonstrated through simulation.
IEEE/ACM Transactions on NetworkingChord: a scalable peer-to-peer lookup protocol for internet applications
3,122 Citations2003Ion Stoica, Robert Morris +5 more
Results from theoretical analysis and simulations show that Chord is scalable: Communication cost and the state maintained by each node scale logarithmically with the number of Chord nodes.
Routing indices for peer-to-peer systems
781 Citations2003Ángel García-Crespo, Héctor García-Molina
This work introduces the concept of routing indices (RIs), which allow nodes to forward queries to neighbors that are more likely to have answers, and presents three RI schemes: the compound, the hop-count, and the exponential routing indices.
Peer-to-Peer Computing
705 Citations2002Dejan Milojičić, Vana Kalogeraki +6 more
Lecture notes in computer scienceSemantic Overlay Networks for P2P Systems
428 Citations2005Arturo Crespo, Héctor García-Molina
The results show that SONs can significantly improve query performance while at the same time allowing users to decide what content to put in their computers and to whom to connect.
Elsevier eBooksThe History of Histograms (abridged)
408 Citations2003Yannis Ioannidis
This paper compress their entire history (including their "future history" as currently anticipated) in the given/fixed space budget, mostly recording details for the periods, events, and results with the highest (personally-biased) interest.
Pattern RecognitionOn measuring the distance between histograms
386 Citations2002Sung-Hyuk Cha, Sargur N. Srihari
The proposed distance measure has the advantage over the traditional distance measures regarding the overlap between two distributions; it takes the similarity of the non-overlapping parts into account as well as that of overlapping parts.
Probabilistic location and routing
272 Citations2003Sean Rhea, John Kubiatowicz
A probabilistic location to enhance the performance of existing peer-to-peer location mechanisms in the case where a replica for the queried data item exists close to the query source, and introduces the attenuated Bloom filter, a lossy distributed index data structure.
One torus to rule them all
237 Citations2004Prasanna Ganesan, Beverly Yang +1 more
This work shows how to adapt two popular spatial-database solutions - kd-trees and space-filling curves - and experimentally compare their effectiveness and shows how such queries may be supported in a P2P system by adapting traditional spatial- database technologies with novel P1P routing networks and load-balancing algorithms.
SETS
171 Citations2003Mayank Bawa, Gurmeet Singh Manku +1 more
SETS is presented, an architecture for efficient search in peer-to-peer networks, building upon ideas drawn from machine learning and social network theory, and it is shown that SETS is efficient in network traffic and query processing load.
A peer-to-peer framework for caching range queries
127 Citations2004Özgür Şahin, Abhishek Gupta +2 more
This work proposes a method, which is based on the multidimensional CAN system, for efficiently evaluating range queries, where the answers of the range queries are cached at the peers and are used to answer future range queries.
Lecture notes in computer scienceSemantic Overlay Clusters within Super-Peer Networks
110 Citations2004Alexander Löser, Felix Naumann +3 more
This work introduces the concept of semantic overlay clusters (SOC) for super-peer networks enabling a controlled distribution of peers to clusters and allows a clustering of complex heterogeneous schemes known from relational databases and use advantages of super- peer networks, such as efficient search and broadcast of messages.
Enlighten: Publications (The University of Glasgow)Towards High Performance Peer-to-Peer Content and Resource Sharing Systems
96 Citations2003Peter Triantafillou, Chrysanni Xiruhaki +2 more
A novel architecture for this new class of applications, which differs drastically from what is either found currently in existing products or proposed in academia is proposed, to harness all available resources in the P2P network so that the users can access all available content efficiently.
Lecture notes in computer scienceTowards a Unifying Framework for Complex Query Processing over Structured Peer-to-Peer Data Networks
65 Citations2004Peter Triantafillou, Theoni Pitoura
This work proposes a unifying framework that consists of a modified DHT architecture, data placement and search algorithms, and provides efficient support for processing a variety of query types, including queries with one or more attributes, queries with selection operators, and queries with join operators.
EFFICIENT DISCOVERY OF IMPLICITLY FORMED PEER-TO-PEER COMMUNITIES #
40 Citations2002Mujtaba Khambatti, K.D. Ryu +1 more
This paper investigates the behavior of randomly created communities and model the complexity of discovery algorithms, which allow for quickly changing community structures (dynamic communities, failures, mobile nodes and so on).
Notes on numerical fluid mechanics and multidisciplinary designProcessing Queries in a Large Peer-to-Peer System
30 Citations2003Leonidas Galanis, Yuan Wang +2 more
This paper presents a performance study of a system that facilitates efficient searches of large numbers of independent data providers on the Internet by using small indices on each node in a large peer-to-peer system.
Lecture notes in computer scienceOn Constructing Small Worlds in Unstructured Peer-to-Peer Systems
8 Citations2004Yannis Petrakis, Evaggelia Pitoura
This paper proposes decentralized procedures for constructing small worlds based on routing indexes that describe the content of neighboring nodes, and shows that small-world peer-to-peer systems built with these procedures increase recall.