Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Waves: a fast multi-tier top-k query processing algorithm
Daoud C., Silva de Moura E., Fernandes D., Soares da Silva A., Rossi C., Carvalho A. Information Retrieval20 (3):292-316,2017.Type:Article
Date Reviewed: Dec 28 2017

Daoud and colleagues propose and demonstrate the effectiveness of their innovative waves algorithm, a fast multitier top-k query processing algorithm. In the waves algorithm, the entire document collection is divided into disjoint tiers and is processed one tier at a time. Index entries in tier i have greater impact than entries in tier j, for all j > i. At each moment while processing a query, the top-k documents with the highest scores are retained, and only the documents that score no less than the current top-k document are kept in a tier. Other documents are discarded. The advantage of the algorithm lies in the fact that each tier in the processing keeps only the documents that score above the threshold, thus reducing the total number of documents that have to complete the computations.

The authors compared the performance of the waves algorithm with other state-of-the-art algorithms using large datasets. The data used was TREC GOV2 with 426 gigabytes of text, about six billion index entries, and 45 million distinct terms. The experiments used the TREC 2006 efficiency track for the experiments, one containing 1,000 queries and the other containing 10,000 queries. The algorithms selected to assess the performance include BMWT, MBMWT, and BMW-CSP. The authors conducted detailed and careful experiments to study the performance of these algorithms. In all experiments, the authors compared the results of the top ten queries (small scale) and top 1,000 queries (larger scale). The results are convincing and easy to understand.

The paper contains detailed numerical results that convince readers of the effectiveness of the waves algorithm. The results and their discussions consist of about half of the paper, and provide a rich collection of information for readers to digest to help them come to their own conclusions.

Reviewer:  Xiannong Meng Review #: CR145736 (1802-0097)
Bookmark and Share
  Featured Reviewer  
 
Query Processing (H.2.4 ... )
 
 
Information Search And Retrieval (H.3.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Query Processing": Date
A correction of the termination conditions of the Henschen-Naqvi technique
Briggs D. Journal of the ACM 31(4): 711-719, 1984. Type: Article
Sep 1 1992
A compression technique to materialize transitive closure
Jagadish H. (ed) ACM Transactions on Database Systems 15(3): 558-598, 1990. Type: Article
Oct 1 1992
Efficient and optimal query answering on independent schemes
Atzeni P. (ed), Chan E. Theoretical Computer Science 77(3): 291-308, 1990. Type: Article
Nov 1 1991
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy