Unified Framework for Top-k Query Processing in Peer-to-Peer Networks

Conner, William G.; Hwang, Seung-won; Nahrstedt, Klara

Permalink

https://hdl.handle.net/2142/11333 Copy

Description

Title

Unified Framework for Top-k Query Processing in Peer-to-Peer Networks

Author(s)

• Conner, William G.
• Hwang, Seung-won
• Nahrstedt, Klara

Issue Date

2007-05

Keyword(s)

• peer-to-peer networks
• networking

Abstract

Supporting queries over dispersed data stored in large-scale distributed systems, such as peer-to-peer networks, naturally calls for ranked retrieval in order to effectively focus on the most relevant (i.e., top-k) results. While top-k retrieval has been actively studied lately, existing algorithms are too restrictive due to their assumptions about how the data is partitioned amongst the various data sources. Unlike existing approaches that assume a single type of data partitioning, we generalize the application scenario to include peer-to-peer networks of a potentially large number of peers in which the data might be partitioned in various ways. More specifically, we develop a novel unified top-k query processing framework supporting various types of data partitioning. In order to support top-k queries in our unified framework, we have developed very efficient wavelet-based data synopses and algorithms that approximate the top-k results with most operations occurring in the wavelet coefficient domain. Our simulation and experimental results show that our framework yields low bandwidth consumption, high accuracy, and low latency for top-k retrieval in peer-to-peer networks.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11333

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections