Approximate Top-k Retrieval from Hidden Relations

Details Approximate Top-k Retrieval from Hidden Relations Approximate Top-k Retrieval from Hidden Relations

2010-08-30

arxiv.org/abs/1008.5057v1

Computer Science

Databases

Scientific paper

We consider the evaluation of approximate top-k queries from relations with a-priori unknown values. Such relations can arise for example in the context of expensive predicates, or cloud-based data sources. The task is to find an approximate top-k set that is close to the exact one while keeping the total processing cost low. The cost of a query is the sum of the costs of the entries that are read from the hidden relation. A novel aspect of this work is that we consider prior information about the values in the hidden matrix. We propose an algorithm that uses regression models at query time to assess whether a row of the matrix can enter the top-k set given that only a subset of its values are known. The regression models are trained with existing data that follows the same distribution as the relation subjected to the query. To evaluate the algorithm and to compare it with a method proposed previously in literature, we conduct experiments using data from a context sensitive Wikipedia search engine. The results indicate that the proposed method outperforms the baseline algorithms in terms of the cost while maintaining a high accuracy of the returned results.

Affiliated with

Also associated with

No associations

Rating

Approximate Top-k Retrieval from Hidden Relations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Approximate Top-k Retrieval from Hidden Relations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate Top-k Retrieval from Hidden Relations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-400786