Approximate Top-K Retrieval from Hidden Relations

No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
Faculty of Information and Natural Sciences |
Date
2010
Major/Subject
Mcode
Degree programme
Language
en
Pages
29
Series
TKK reports in information and computer science, 36
Abstract
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.
Description
Keywords
query processing, nearest neighbor search, machine learning, Information search and retrieval
Citation
Permanent link to this item
https://urn.fi/urn:nbn:fi:tkk-013190