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 Retrieval 20 (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
Web log analysis: a review of a decade of studies about information acquisition, inspection and interpretation of user interaction
Agosti M., Crivellari F., Di Nunzio G.  Data Mining and Knowledge Discovery 24(3): 663-696, 2020. Type: Article
Jan 11 2022
Querying graphs
Bonifati A., Fletcher G., Voigt H., Yakovets N.,  Morgan&Claypool Publishers, San Rafael, CA, 2018. 184 pp. Type: Book (978-1-681734-30-9)
Nov 21 2019
Decomposing federated queries in presence of replicated fragments
Montoya G., Skaf-Molli H., Molli P., Vidal M.  Journal of Web Semantics 42 1-18, 2017. Type: Article
Oct 25 2017
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2022 ThinkLoud, Inc.
Terms of Use
| Privacy Policy