MWAND: A New Early Termination Algorithm for Fast and Efficient Query Evaluation

TitleMWAND: A New Early Termination Algorithm for Fast and Efficient Query Evaluation
Publication TypeJournal Article
Year of Publication2019
AuthorsMansouria, Z. I., Z. Lougmiri, and S. Mohamed
JournalInternational Journal of Interactive Multimedia and Artificial Intelligence
IssueRegular Issue
Date Published12/2019

Nowadays, current information systems are so large and maintain huge amount of data. At every time, they process millions of documents and millions of queries. In order to choose the most important responses from this amount of data, it is well to apply what is so called early termination algorithms. These ones attempt to extract the Top-K documents according to a specified increasing monotone function. The principal idea behind is to reach and score the most significant less number of documents. So, they avoid fully processing the whole documents. WAND algorithm is at the state of the art in this area. Despite it is efficient, it is missing effectiveness and precision. In this paper, we propose two contributions, the principal proposal is a new early termination algorithm based on WAND approach, we call it MWAND (Modified WAND). This one is faster and more precise than the first. It has the ability to avoid unnecessary WAND steps. In this work, we integrate a tree structure as an index into WAND and we add new levels in query processing. In the second contribution, we define new fine metrics to ameliorate the evaluation of the retrieved information. The experimental results on real datasets show that MWAND is more efficient than the WAND approach.

KeywordsEvaluation, Information Retrieval, Inverted List, Query Processing, Top-k, WAND
IJIMAI20195_7_6.pdf2.04 MB