BACKGROUND

The amount of available information and digital content on the Internet and other electronic sources continues to grow rapidly. Given the vast amount of information, search engines have been developed to facilitate searching for electronic documents. In particular, users or computers may search for information and documents by submitting search queries, which may include, for instance, one or more words. After receiving a search query, a search engine identifies documents that are relevant based on the search query.

At a high level, search engines identify search results by ranking documents' relevance to a search query. Ranking is often based on a large number of document features. Given a large set of documents, it's not feasible to rank all documents for a search query as it would take an unacceptable amount of time. Therefore, search engines typically employ a pipeline that includes preliminary operations to remove documents from consideration for a final ranking process. This pipeline traditionally includes a matcher that filters out documents that don't have terms from the search query. The matcher operates using a search index that includes information gathered by crawling documents or otherwise analyzing documents to collect information regarding the documents. Search indexes are often comprised of posting lists (sometimes called an inverted index) for the various terms found in the documents. The posting list for a particular term consists of a list of the documents containing the term. When a search query is received, the matcher employs the search index to identify documents containing terms identified from the search query. The matching documents may then be considered by one or more downstream processes in the pipeline that further remove documents and ultimately return a set of ranked search results.

SUMMARY

This summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter.

The technology described herein provides for reducing the number of identified matching documents containing a term from a search query using a bit vector search index. The bit vector search index is a data structure that uses bit vectors to index information about terms contained in documents. Each bit vector comprises an array of bits that stores information for a collection of terms. Each bit position (or bit) in a bit vector indicates whether one or more documents contain one or more terms from a collection of terms. Additionally, a term can be included in multiple bit vectors. When a search query is received, a term is identified from the search query, and bit vectors corresponding to the term are identified. The identified bit vectors are intersected to identify matching documents. In particular, documents containing the term are identified as ones corresponding to a certain bit that is set in each of the bit vectors corresponding to the term. In some instances, a large number of matching documents may be returned. To address this, the technology described herein provide techniques to control the number of matching documents returned. In instances in which too many matching documents may be returned, one or more “strengthening row” bit vectors are used in addition to the bit vectors for the term to reduce the number of matching documents returned. Among other things, a strengthening row bit vector may be based on static rank of documents or a bit vector that identifies terms in non-body locations (e.g., title or anchor text) in documents (as opposed to any location in the documents).

