Inverted Indexing and Scalable Search techniques

Motivation

The amount of data is growing exponentially every day and the volume has increased incredibly over the last few years. With this accelerated growth of data, it has now become important to search collections quickly to serve business decisions and customer queries both offline and online. To process large document collections quickly, at the order of billions to trillions of word per second, the search concept of inverted indexing grew familiar. It stands as one of the fastest mechanisms of retrieving ranked information among many documents that contain certain words or flexible matching words/expressions. The advantages of inverted indexing are:

• Allow fast full text searches, even when the processing cost is high.

• Easier process to implement.

• Popular data structure used in distributed scalable document retrieval systems, as for example in search engines.

The blog is structured as follows:

• Stating the concept of inverted indexing and how it can be used to solve text based classification problems.

• Describing the architecture and system components to narrate how inverted indexing can be used, for e.g. search-engines and databases.

• Giving a short overview of Lucene and Solr with an understanding of how they differ from each other.

• Analyzing “TF-IDF” based Scoring Model where different scoring factors are explained that are used for querying or searching words in the document.

An inverted index consists of :

• “A detailed list of all the unique words that appear in any document.”
• “For each word, a list of the documents in which it appears”.

Steps to create Inverted Index

To create an inverted index, the text data of each document at first is splitted into separate words (termed as terms or tokens). The list of documents after tokenization needs further preprocessing (normalization, stemming, removal of stop-words) on each token to create a sorted list of all the unique terms. The inverted index is created by consolidating the entries from each document. The entries from each document consists of list of unique terms.

Apart from reverse indexing, search engines like Lucene is equipped to search on the basis of phrase queries, wildcard and proximity queries, along with sorting, ranking and grouping the searched results.

InvertedIndexing can be implemented in python using TfidfVectorizer from sklearn.feature_extraction.text library. Its used for text classification processes with supervised learning techniques (Boosting/Bagging/Stacking).

TfIdfVectorizer params:

documents = (
"Technology has made us ever more productive",
"As I have pointed out, technology may in fact have limits, but we do not know",
"Technology is simply the combining of other economic products in new ways.",
"This is because technology is cumulative.",
"Technology allowed us to peer deeper into the mysteries of the miniscule.")

from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics.pairwise import cosine_similarity

tfidf_vectorizer = TfidfVectorizer()
tfidf_matrix = tfidf_vectorizer.fit_transform(documents)
print (tfidf_matrix.shape)print(tfidf_vectorizer.vocabulary_)
print(tfidf_vectorizer.idf_)
print(cosine_similarity(tfidf_matrix[0:1], tfidf_matrix))

(5, 40)

#Vocabulary List
{‘we’: 39, ‘know’: 16, ‘of’: 25, ‘productive’: 30, ‘this’: 35, ‘ever’: 9, ‘limits’: 17, ‘because’: 2, ‘has’: 11, ‘in’: 13, ‘us’: 37, ‘peer’: 28, ‘cumulative’: 5, ‘into’: 14, ‘as’: 1, ‘do’: 7, ‘products’: 31, ‘have’: 12, ‘combining’: 4, ‘not’: 24, ‘allowed’: 0, ‘deeper’: 6, ‘miniscule’: 20, ‘ways’: 38, ‘other’: 26, ‘new’: 23, ‘simply’: 32, ‘economic’: 8, ‘the’: 34, ‘mysteries’: 22, ‘to’: 36, ‘out’: 27, ‘made’: 18, ‘is’: 15, ‘more’: 21, ‘may’: 19, ‘technology’: 33, ‘pointed’: 29, ‘but’: 3, ‘fact’: 10}

Tf-Idf score

[2.09861229 2.09861229 2.09861229 2.09861229 2.09861229 2.09861229
2.09861229 2.09861229 2.09861229 2.09861229 2.09861229 2.09861229
2.09861229 1.69314718 2.09861229 1.69314718 2.09861229 2.09861229
2.09861229 2.09861229 2.09861229 2.09861229 2.09861229 2.09861229
2.09861229 1.69314718 2.09861229 2.09861229 2.09861229 2.09861229
2.09861229 2.09861229 2.09861229 1. 1.69314718 2.09861229
2.09861229 1.69314718 2.09861229 2.09861229]

Cosine similarity

[[1. 0.02350305 0.02986958 0.03878472 0.10853509]]

From the cosine similarity score, we can compute the angle between the 2 vectors. Angle theta (θ) can be isolated by taking a cos inverse ( cos^-1) on the right hand side of the measured angle.

To compute similarity between first and last document, we substitute the scores obtained in the previous step in the equations. This gives us a cosine similarity as 0.10853509, as the first document has a similarity score of 1 when compared to itself.

import math
# This was already calculated on the previous step, so we just use the value
cos_sim = .10853509
angle_in_radians = math.acos(cos_sim)
print (math.degrees(angle_in_radians))

83.7691231864019

Inverted Indexing with Solr

Solr is an Apache licensed open source search engine. It has an exceptionally active developer community and continues to be the foremost search platform in most of the big data platforms. Solr is able to achieve fast search responses because, instead of searching the text directly, it searches an index instead, and stores it in the data directory.

As defined by Elasticsearch-

“An index consists of one or more Documents, and a Document consists of one or more Fields”.

Solr allows defining schemas to facilitate searching items through indexing. It allows us to state:

• What kinds of fields there are

• Which field can be used as unique/primary key

• Which fields are required

• How to index and search each field

When data is added to Solr, it goes through a series of transformations (lower-casing, removing word stems etc), popularly known as analysis before being added to the index. The end result of the analysis are a series of tokens which are then added to the index.

Solr and Lucene

Solr uses Lucene underneath. Lucene is a powerful search engine framework, which gives end-users define and add search capability. It exposes an easy-to-use API, where the abstraction hides all the search-related operations. Any application can use this library, not just Solr.

Solr is built around Lucene. It is not just an http-wrapper around Lucene but has been known to add more features to Lucene. Solr is ready-to-use web application that offers related infrastructure and a lot more features in addition to what Lucene offers.

“Lucene combines Boolean model (BM) of Information Retrieval with Vector Space Model (VSM) of Information Retrieval”.

VSM model uses term weighting scheme, and the retrieved documents could be sorted according to their relevancy degree.

In VSM, documents and queries share a common representation format i.e nothing but weighted vectors. These vectors are placed in a multi-dimensional space, each unique index term representing a dimension. If a term occurs in the document, its value in the vector representation is non-zero. Several different ways of computing the vector values (also known as (term) weights) exists, the one which we have discussed here is Tf-idf weighting.

VSM does not involve or necessitates weights to be Tf-idf values. However Tf-idf values widely plays an important role in produce search results. For given term t and document (or query) x, Tf(t, x) is dependent on the number of occurrences of term t in x (when one increases so does the other). idf(t) is dependent on the number of index documents containing the term t and also varies with it

VSM score of document d for query q is given by the Cosine Similarity of the weighted query vectors V(q) and V(d). The the cosine similarity between the query vector and a document vector serves as a measure of the score of the document for that query and is used to select the top-scoring documents for a query.

Lucene’s Practical Scoring Function 

It is given by score(q, d) stated below and represents a function of the query terms found in the specified document. Lucene’ Practical Scoring Function is given by :

score(q,d) = coord(q,d) .queryNorm(q) . Sum (tf(t in d -Square (idf(t)) -t.getBoost().norm(t,d)), where the sum ranges from t in q

The different scoring factors of “TF-IDF” based Scoring Model are given below.

tf (t in d) directly correlates to the term’s frequency. It refers to the number of times term t appears in the currently scored document d. As its is a positive correlation, documents with more occurrences of a given term exhibits a higher score. As its occurrence is demonstrated twice in both the query and the document, hence it is squared in the equation. tf(t in d) is given by:

idf(t) stands for Inverse Document Frequency, used in NLP — in text mining, search queries and summarization.. This value correlates to the inverse of docFreq (the number of documents in which the term t appears). As it is an inverse metric, it is obvious that rarer terms give higher contribution to the total score. Its is represented by taking the natural log (normalization) of the inverse document frequencies as given below:

coord(q, d) is a score factor based on how many of the query terms are found in the specified document. Documents containing more of the query’s terms will receive a higher score than another document with fewer query terms.

queryNorm(q) is a normalizing factor used to assign scores to queries and make them comparable. As all documents are multiplied by the same factor, it does not affect the overall document ranking scores. This is given by:

The sum of squared weights (of the query terms) is computed by the query Weight object.

t.getBoost() is a search time boost of term t in the query q as specified in the query text, or as set by application calls using setBoost().

norm(t, d) evaluated for each document-term encapsulates a few (indexing time) boost and length factors:

• Index-time boost — to increase the scores for certain documents that match a certain query, index-time boosts can be used. Index-time boosts can be specified per-field to impart extra boost to queries matching on that specific field. An Index-time boost applies to a multiValued field and refers to all values for that field.

• Field boost — set by calling field.setBoost() prior to updating the field to a document. Queries can include “boosts” based on specific attributes of documents, or by using a function on the value of a numeric field.

• lengthNorm — measures of the importance of a term according to the total number of terms in the field. It is computed when the document is added to the index in accordance with the number of tokens of this field in the document, enabling shorter fields to add more to the score.

When a document is added to the index, all the above factors are multiplied as given below. Document with multiple fields of same name, get their boosts are multiplied together:

Architecture

Inverted Indexing Components : The following figure shows the system architecture (including Elastic Search , MongoDB, SOLR) where reverse indexing can be used to facilitate fast search on multiple documents.

Solr Index Retrieval

An application using Solr for search and indexing retrieves the indexes in step by step manner.

• When an user runs a search in Solr, the search query is processed by a request handler. The search request handler is an easy to integrate plugin module that defines the logic to be used when Solr processes a request. Solr supports a variety of request handlers. In addition, applications can be configured to allow users to override the default handlers in preference of a custom request handler.

• The search request handler issues the query with the help of a query parser and returns the result back via a response writer. First the request handler issues the query, then it calls a query parser that is responsible for parsing the textual query. It is also responsible for converting it into corresponding Lucene query objects. Different query parsers support different syntax. Solr, uses Lucene’s standard query parser for greater precision in searches.

• The search engine creates internal requests to randomly chosen replicas of every shard. The individual shards in the collection-set form the answers , coordinates the responses, issues any subsequent internal requests as needed (to refine facets values, or to request additional stored fields), and constructs the final response for the client.

• The response writer component builds the query response object in the required format for the final presentation, generally an XML/JSON/PHP object is returned.

• Solr is deployed in a has the cloud infrastructure with distributed capabilities. The system architecture partitions data into multiple instances, or shards, that can be hosted on multiple machines, with replicas providing redundancy for both scalability and fault tolerance. In addition, a ZooKeeper server that helps manage the overall structure so that both indexing and search requests routed are in sync.

Inverted Indexing with Map Reduce: Apache Blur provides distributed search functionality built on the top of Apache Hadoop, Apache Lucene, Apache ZooKeeper, and Apache Thrift.

It allows indexing documents in map-reduce architectural framework where one or more documents are distributed to a mapper. The word counts deduced by each mapper can be further aggregated by one or more reducers to create inverted index of the input documents. The final index list stored in HDFS clusters, contains list of words in the files and the set of files that contain each terms and the word frequency in each of the files.

Indexing databases with SolrIndexing MongoDB Data in Apache SolrIndexing data for fast and efficient retrieval is one of the data preparation tasks in data science. MongoDB is the…blog.toadworld.com

Conclusion

• Apache Solr is an agile search engine. Its also an open source licensed by Apache and hence codes can be changed whenever required by the user.

• Apache Solr analyses data and creates inverted indexes into its system.

• Solr is responsible for copying indexes into different servers to handle auto failover and distribute indexes into multiple machine to balance the load.

• Solr on integration with Hadoop provides a robust, efficient, and flexible platform to build such smart recommending engines.

• In collaboration with Apache Lucene, Apache Solr is in-built with excellent matching capabilities comprising joins, groupings, wildcards and phrases and various other data types.

• The extensive real-time search ability built into Apache Solr has made it one of the most popular online search engines. It is used widely in the E-commerce and telecom space.

• Solr framework allows easy creation of low-cost plugins based on business requirements. For example, plugins can be created for search and filter operations that operate on a result set of a query.

References

1. https://nlp.stanford.edu/IR-book/html/htmledition/a-first-take-at-building-an-inverted-index-1.html
2. https://lucene.apache.org/core/4_0_0/core/org/apache/lucene/search/similarities/TFIDFSimilarity.html
3. http://www.lucenetutorial.com/advanced-topics/scoring.html
4. https://www.happiestminds.com/whitepapers/using-apache-solr-for-ecommerce-search-applications.pdf