Microsoft Technology Licensing, LLC

Denis V Deyneko

Robert Lovejoy Goodwin

Michael Joseph Hopcroft

Utkarsh Jain

Fan Wang

Andrija Antonijevic

The technology described herein provides for identifying matching documents for a search query using a bit vector search index. When a search query is received, a term is identified from the search index, and a number of bit vectors corresponding to the term are identified. Each bit vector comprises an array of bits in which at least one bit in each bit vector indicates that a corresponding document includes the term. Each bit vector also includes other bits indicating other documents include other terms. A determination is made that an unacceptable number of possible matching documents is likely to be returned. In response to the determination, a strengthening row bit vector is selected to reduce the number of possible matching documents. The identified bit vectors and the selected strengthening row are intersected to identify matching documents that contain the term.

Reducing matching documents for a search query

The technology described herein provides for indexing information in a bit vector search index. The bit vector search index comprises a data structure for indexing data about terms from a corpus of documents. The data structure includes a number of bit vectors. Each bit vector comprises an array of bits and corresponds to a different set of terms. Bits in the bit vector are used to represent whether at least one document corresponding to the bit includes at least one term from the set of terms corresponding to the bit vector. The bit vector search index is stored by first indexing information about documents using bit vectors on a first accumulation buffer storage device. When a threshold is satisfied, the information is transferred to bit vectors on a subsequent storage device.

Updating a bit vector search index

The technology described herein provides for storing and retrieving data in a bit vector search index. The bit vector search index stores data about terms from documents using bit vectors. Each bit vector comprises an array of bits and corresponds to a different set of terms. Each bit in the bit vector is used to represent whether a document includes at least one term from the set of terms. A band table is used to store bit vector configurations for bands of terms having similar term characteristics. Each term is indexed in the bit vector search index according to a bit vector configuration for a band to which it belongs. When identifying bit vector storage locations for terms, explicit mappings are used for some terms and ad hoc approaches used for other terms. Explicit mappings provide specific locations for terms, while ad hoc approaches use mapping algorithms assigned to bands.

Growing community of inventors

Richmond, CA, United States of America

Denis V Deyneko