Loading...
Please wait, while we are loading the content...
Similar Documents
Efficient all top-k computation - a unified solution for all top-k, reverse top-k and top-m influential queries
| Content Provider | CiteSeerX |
|---|---|
| Author | Ge, Shen Leong Hou, U. Mamoulis, Nikos Cheung, David W. |
| Abstract | Abstract—Given a set of objects P and a set of ranking functions F over P, an interesting problem is to compute the top ranked objects for all functions. Evaluation of multiple top-k queries finds application in systems, where there is a heavy workload of ranking queries (e.g., online search engines and product recommendation systems). The simple solution of evaluating the top-k queries one-by-one does not scale well; instead, the system can make use of the fact that similar queries share common results to accelerate search. This paper is the first, to our knowledge, thorough study of this problem. We propose methods that compute all top-k queries in batch. Our first solution applies the block indexed nested loops paradigm, while our second technique is a view-based algorithm. We propose appropriate optimization techniques for the two approaches and demonstrate experimentally that the second approach is consistently the best. Our approach facilitates evaluation of other complex queries that depend on the computation of multiple top-k queries, such as reverse top-k and top-m influential queries. We show that our batch processing technique for these complex queries outperform the state-of-the-art by orders of magnitude. Index Terms—all top-k queries, view-based index F 1 |
| File Format | |
| Journal | IEEE Trans. Knowl. Data Eng |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Top-m Influential Query Top-k Computation Reverse Top-k Unified Solution Top-k Query Complex Query Multiple Top-k Query Loop Paradigm Second Approach Top-k Query One-by-one Batch Processing Technique View-based Index Product Recommendation System Simple Solution Top Ranked Object Appropriate Optimization Technique Heavy Workload Online Search Engine Index Term Interesting Problem Abstract Given Second Technique Similar Query Share Common Result First Solution Block Indexed View-based Algorithm |
| Content Type | Text |
| Resource Type | Article |
