UM  > 科技學院
Efficient All Top-k Computation - A Unified Solution for All Top-k, Reverse Top-k and Top-m Influential Queries
Ge, S1; U, LH2; Mamoulis, N1; Cheung, DW1
2013
Source PublicationIEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
ISSN1041-4347
Volume25Issue:5Pages:1015-1027
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-minfluential queries. We show that our batch processing technique for these complex queriesoutperform the state-of-the-art by orders of magnitude.

KeywordAll Top-k Queries View-based Index
DOIhttp://doi.org/10.1109/TKDE.2012.34
Indexed BySCI
Language英语
WOS Research AreaComputer Science ; Engineering
WOS SubjectComputer Science, Artificial Intelligence ; Computer Science, Information Systems ; Engineering, Electrical & Electronic
WOS IDWOS:000316755100005
Fulltext Access
Citation statistics
Cited Times [WOS]:17   [WOS Record]     [Related Records in WOS]
Document TypeJournal article
CollectionFaculty of Science and Technology
DEPARTMENT OF COMPUTER AND INFORMATION SCIENCE
Affiliation1.Univ Hong Kong, Dept Comp Sci, Hong Kong, Hong Kong, Peoples R China
2.Univ Macau, Dept Comp & Informat Sci, Taipa, Peoples R China
Recommended Citation
GB/T 7714
Ge, S,U, LH,Mamoulis, N,et al. Efficient All Top-k Computation - A Unified Solution for All Top-k, Reverse Top-k and Top-m Influential Queries[J]. IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,2013,25(5):1015-1027.
APA Ge, S,U, LH,Mamoulis, N,&Cheung, DW.(2013).Efficient All Top-k Computation - A Unified Solution for All Top-k, Reverse Top-k and Top-m Influential Queries.IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,25(5),1015-1027.
MLA Ge, S,et al."Efficient All Top-k Computation - A Unified Solution for All Top-k, Reverse Top-k and Top-m Influential Queries".IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 25.5(2013):1015-1027.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Google Scholar
Similar articles in Google Scholar
[Ge, S]'s Articles
[U, LH]'s Articles
[Mamoulis, N]'s Articles
Baidu academic
Similar articles in Baidu academic
[Ge, S]'s Articles
[U, LH]'s Articles
[Mamoulis, N]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[Ge, S]'s Articles
[U, LH]'s Articles
[Mamoulis, N]'s Articles
Terms of Use
No data!
Social Bookmark/Share
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.