Title
Query workload-aware overlay construction using histograms
Abstract
Peer-to-peer(p2p) systems over an efficient means of data sharing among a dynamically changing set of a large number of a tonomous nodes.Each node in a p2p system is connected with a small number of other nodes thus creating an overlay network of nodes. A query posed at a node is routed through the overlay network towards nodes hosting data items that satisfy it. In this paper, we consider building overlays that exploit the query workload so that nodes are clustered based on their results to a given query workload. The motivation is to create overlays where nodes that match a large number of similar queries are a fewlinks apart. Query frequency is also taken into account so that popular queries have a greater effect on the formation of the overlay than unpopular ones. We focus on range selection queries and se histograms to estimate the query results of each node. Then, nodes are clustered based on the similarity of their histograms. To this end,we introd ce a workload-aware edit distance metric between histograms that takes into account the query workload. Our experimental results show that workload-aware overlays increase the percentage of query results returned for a given number of nodes visited as compared to both random (i.e., unclustered)overlays and non workload-aware clustered overlays (i.e., overlays that cluster nodes based solely on the nodes' content).
Year
DOI
Venue
2005
10.1145/1099554.1099717
CIKM
Keywords
Field
DocType
similar query,non workload-aware,range selection query,query frequency,query result,overlay network,large number,popular query,small number,query workload,query workload-aware overlay construction,satisfiability,clustering,edit distance,range query,range queries
Edit distance,Query optimization,Web search query,Data mining,Computer science,Workload,Range query (data structures),Computer network,Web query classification,Overlay,Overlay network,Distributed computing
Conference
ISBN
Citations 
PageRank 
1-59593-140-6
7
0.60
References 
Authors
21
4
Name
Order
Citations
PageRank
Georgia Koloniari122016.49
Yannis Petrakis2292.38
evaggelia pitoura31968321.56
Thodoris Tsotsos470.60