Unified Framework for Flexible and Efficient Top-k Retrieval in Peer-to-Peer Networks

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

Permalink

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

Description

Title

Unified Framework for Flexible and Efficient Top-k Retrieval in Peer-to-Peer Networks

Author(s)

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

Issue Date

2006-12

Keyword(s)

peer-to-peer networks

Abstract

As more and more data from distributed data sources becomes accessible, supporting queries over peer-to-peer networks of such data sources becomes a more convincing application scenario. In such an application scenario, a large scale of accessible data from multiple peers naturally calls for ranked retrieval in order to effectively focus the retrieval on the most relevant, say top-k results. While top-k retrieval has been actively studied lately, existing algorithms are too restrictive due to their assumptions about the predicates and scoring functions used. These restrictive assumptions limit the flexibility of individual users to issue personalized queries. In contrast, we present efficient algorithms that support top-k retrieval customized to the specific predicates and scoring functions desired by the users. Also, unlike existing approaches that only consider a single type of data partitioning, we generalize the application scenario to include peer-to-peer networks of a potentially large number of peers that might partition the data in various ways. More specifically, we develop a unified top-k query processing framework to cover the following types of data partitioning: (1) vertical partitioning where each peer stores partial scores of an identical set of data objects, (2) horizontal partitioning where each peer stores complete scores of a disjoint set of data objects, and (3) mixed partitioning where each peer stores partial scores of a disjoint set of data objects. In particular, we customize queries from users by transforming data synopses on a per-query basis. We also reduce bandwidth consumption by using heuristics to schedule the order in which predicates are evaluated. Our results validate the efficiency and effectiveness of our framework by considering the bandwidth consumption, delay, and correctness of our algorithms.

Type of Resource

text

Permalink

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

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