cient Search in Short Documents

Abstract

This work is about reasonable choice of the component algorithms for the implementation of Okapi BM25. It describes important aspects of building search engines and focuses on the e cient and implementation of Okapi BM25 for k-grams. This extended abstract should be treated as a part of Master's thesis in System Analysis and Control Theory. Since Okapi BM25 requires the usage of several general-purpose algorithms, it is important to choose the best version of the existing algorithms in order to squeeze every bit of the hardware.

Keywords

• TF-IDF
• Okapi BM25
• Inverted index
• Information Retrieval
• ngrams

Introduction

1. Binary independence model.

2. Bayesian network approaches. 3. Okapi BM25 [ 4 ].

Problems of classical Okapi BM25 BM25 is a bag-of-words retrieval function that ranks a set of documents based on the query terms appearing in each document.

score(D; Q) = n X IDF(qi) i=1 IDF(qi) = log

f (qi; D) (k1 + 1) f (qi; D) + k1 1 b + b jDj avgdl N

n(qi) + 0:5 n(qi) + 0:5 ; (1) (2) k1 = 1:5 and b = 0:75 - parameters, jDj - length of the document in words, avgdll - average document length in the text collection, n(qi) - number of documents which contain term qi, f (qi; D) - term frequency in the document D [ 4 ]. document id 1 2 3 4 5 6

Title Search query Score Why C++ is better than Rust Why C++ is better than Rust 0.85 Why Rust is better than C++ Why C++ is better than Rust 0.85

Programming in C++ Why C++ is better than Rust 0.08

Programin in Rust Why C++ is better than Rust 0.07

Samsung 8 Why C++ is better than Rust 0

Good life Why C++ is better than Rust 0

Improvement of Okapi BM25

Counting term frequencies First of all, words from original Okapi BM 25 would replaced by 3-grams and 4-grams. For e ciency they could be encoded and would be encoded as 32 bit integers.

Important algorithms for Okapi BM25:

1. sorting 2. nding frequences 3. linear search

Data structures:

1. inverted index

2. posting list 3. hash table This change would decrease number of comparisons and speed up sorting and hashing.

It is important to choose an e cient algorithm for term frequency counting and hash table [ 3 ] is not the best option. Let's apply the following algorithm on sequence s, which is represented by pair of 2 iterators [f irst; last) and the target is represented by output iterator out: 1. Sort sequence [f irst; last), go to step 2. 2. If f irst equals last, return out. Otherwise go to step 3. 3. Store the data from f irst at tmp. 4. Find the rst element which is not equal to tmp. 5. Assign o set to the count, assign the position of the rst element to f irst which does not equal to tmp. Write pair tmp; count to the output iterator, increment out, go to step 2.

For more information about iterators, read an article about Generic Programming [ 6 ]. The whole point is to choose faster algorithm for short relatively short sequences. Let's compare described algorithm with hash tables on the following con guration: Intel Core i7 7700HQ, RAM Hynix SODIMM 2 x 8GB, 2400MHz, compiler GCC 7.3.1.

Size Insertion into hash table Straight sort and counting

mean std mean std 50 2.63757 8.22384 0.387384 3.76955 100 6.63765 25.1815 0.903355 6.90381 200 15.129 45.2746 2.51254 22.8 2000 158.216 132.655 101.99 334.018 4000 325.473 282.319 220.108 354.548 32000 2287.54 4274.93 2240.9 935.053 64000 3843.75 5391.52 4799.71 1170.27 1. The list of stopwords is stored as a sorted sequence of 32-bits integers. 2. Stopwords should be removed from the sequence. 3. Posting lists are encoded by varint-G8IU [ 5 ]. 4. Search query is treated as a sequence of bytes. For example, phrase "Search query" would be treated as a sequence "sea", "ear", "arc", "rch", "ch ", " qu", "que", "uer", "ery". 5. Inverted index is updated by batches. 6. Retrieval of k most relevant documents is done by selecting n k frequences from posting lists.

Conclusion

We've got simple robust e cient search engine. In this article, we've got advanSearch query The most relevant document Samsung Galaxy Samsung Galaxy Tab 7.7 john ernst bnson John Ernest Benson

john cole John Cole ( priest ) johny burns John Burns ( audio engineer ) tages from fast CPU operations on 32-bit integers. It allows us to use binary search, which is faster than hash maps for certain input sizes. Since IDF is never getting less than zero, it is possible to get use it on 3-grams for short texts.

It is important to remember that bag-of-words model, does not depend on the order of terms. Text queries, which contain same terms, have the same scores. Further work: 1. Compare di erent data structures for posting lists: arrays, b-trees, red-black trees. 2. Compare di erent top K document retrieval heuristics for di erent structure of posting lists. 3. Use persistant storage. 4. Combine probabalistic retrieval with topic modeling. 5. Extend search query by applying vector space model.

References

1. Bm25 the next generation of lucene relevance . https://opensourceconnections.com/blog/2015/10/16/bm25-the -next-generationof-lucene-relevation/.

2. wikipedia test10k.txt. https://s3.amazonaws.com/fair-data/starspace/ wikipedia_devtst.tgz.

3. Thomas H. Cormen , Charles E. Leiserson, Ronald L. Rivest , and Cli ord Stein . Introduction to Algorithms, Third Edition . The MIT Press, 3rd edition , 2009 .

4. Christopher D. Manning and Hinrich Schutze. Foundations of Statistical Natural Language Processing . MIT Press, Cambridge, MA, 1999 .

5. Alexander A. Stepanov , Anil R. Gangolli, Daniel E. Rose, Ryan J. Ernst , and Paramjit S. Oberoi . Simd-based decoding of posting lists . In Proceedings of the 20th ACM International Conference on Information and Knowledge Management , CIKM '11 , pages 317 { 326 , New York, NY, USA, 2011 . ACM.

6. Alexander A . Stepanov and Daniel E. Rose. From Mathematics to Generic Programming. Addison-Wesley Professional, 1st edition , 2014 .