English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

P web search engines are very complex with the goal of returning fast and precise results. The result must be both effective and efficient. These search engines use techniques and algorithms of query processing, such as WAND algorithm, to return a set of ranked documents results named Top-k. These algorithms are executed on a data structure called inverted index [1]. Such structure gives for every term the set of documents in which it appears with additional information, like the term frequencies TF, the list of positions in every document, the format and the size in which it is written. Such construction generates a very large index. In fact, its size is larger than the set of original documents. As a consequence, traversing this index becomes the major bottleneck in query processing. In fact, it is not suitable, really not practical or impossible, to sweep all posting lists. An early termination algorithm is so recommended for such situation. It can return the exact Top-k without scanning the entire posting list. Note here, that a posting list is the part of the inverted index charged in the memory for treatment. We must note also here that the lists are ordered in an ascendant order according to documents numbers [2][3] or on descendant order on TF [4][5]. The choice is done according what the algorithm designer wants. In order to reduce the information representation in the posting lists, a set of compressing techniques have been proposed [6][7][8]. In information retrieval, two major and basic alternatives have been proposed for traversing the posting lists. It is about TAAT (TermAt-A-Time) and DAAT (Document-At-A-Time) strategies [9]. In fact, SAAT(Score At A Time), GAAT(Graph At A Time) and RAAT(Rank At A Time) and JASS(SAAT) are additional strategies which are proposed for remedying the first strategies weaknesses [10] [11][12]. Since the first works in the field of information retrieval [13], the stopping condition is an interesting part of every early termination algorithm. It consists in ending the execution if k responses are computed even if there are more important results with ranks greater than k. A document is considered relevant if its score is greater or equal to a certain bound. The threshold algorithm TA of Ronald Fagin [14] is one of the most popular algorithms in the context of databases. As information systems are so large and as search engines must deal with large dataset, the WAND algorithm has became unavoidable. It has been used in a number of commercial search engines [15]. It has the ability to skip in an intelligent manner some documents and parts of posting lists according to a precise test, as we will see in next sections. Really, the strongest weakness of early termination algorithms resides in the lack of precision in their responses. For Top-k and for a query q of length Lq, it is usual that WAND misses in Top-r, with r≤k, some documents which share a high number of terms with the query. It is about this ascertainment that we built our solution. In this paper, we focus on early termination and we propose a new extension to algorithm WAND. Our aims are: a) To return all totally relevant documents that contain query terms. b) To reduce the operations number in query processing. c) To ameliorate the results quality by ameliorating the responses precision. In particular, we propose new fine metrics to measure the relevance degree of the returned documents. Compared to the naive approach that contains at least one of the query terms, our approach returns the relevant documents ranked first, without any loss in precision or recall or in new proposed metrics. The reminder of the paper proceeds as follows: Section II gives a Keywords

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