University of Illinois Urbana-Champaign

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

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

Content Files
Unified Framework for Flexible and Efficient Top-k Retrieval in Peer-to-Peer Networks.pdf

Permalink

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

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
Date of Ingest
2009-04-21T19:26:31Z
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
Genre of Resource
Technical Report
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

Research and Tech Reports - Computer Science PRIMARY