Updating a bit vector search index

• US 10,733,164 B2
• Filed: 06/17/2016
• Issued: 08/04/2020
• Est. Priority Date: 06/23/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Hopcroft, Michael Joseph, Goodwin, Robert Lovejoy, Wang, Fan, Antonijevic, Andrija, Deyneko, Denis V., Jain, Utkarsh
• Primary Examiner(s): Wilson, Kimberly L
• Application Number:
  US15/186,219
• Publication Number:
  US 20160378808A1
• Time in Patent Office: 1,509 Days
• Field of Search: 707745
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/328 Management therefor
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

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.

Claims

1. A method of indexing information about documents in a bit vector search index, the method comprising:

indexing information about a plurality of documents using bit vectors on a first accumulation buffer storage device, each bit vector on the first accumulation buffer storage device comprising an array of bits in which each bit represents whether one or more documents from the plurality of documents includes one or more terms; and

when a threshold is satisfied, indexing the information about the plurality of documents using bit vectors on a subsequent storage device based on the information indexed in the first accumulation buffer storage device, each bit vector on the subsequent storage device comprising an array of bits in which each bit represents whether one or more documents from a set of documents larger than the plurality of documents includes one or more terms.

2. The method of claim 1, wherein the threshold comprises a threshold number of documents and the threshold is satisfied when the plurality of documents satisfies the threshold number of documents.

3. The method of claim 1, wherein the threshold comprises a time threshold and the threshold is satisfied when a period of time has passed that satisfies the time threshold.

4. The method of claim 1, wherein the threshold comprises a storage consumption threshold and the threshold is satisfied when the storage consumption for the information about the plurality of documents on the first accumulation buffer storage device satisfies the storage consumption threshold.

5. The method of claim 1, wherein the information about the plurality of documents is indexed on the first accumulation buffer storage device one document at a time.

6. The method of claim 1, wherein the information about the plurality of documents is indexed on the first accumulation buffer storage device by collectively indexing at least a portion of the information from a second accumulation buffer storage device.

7. The method of claim 1, wherein the information about the plurality of documents are stored in consecutive bits on the first accumulation buffer storage device and wherein indexing the plurality of documents using bit vectors on the subsequent storage device comprises storing the information about the plurality of documents in non-consecutive bits on the subsequent storage device.

8. The method of claim 1, wherein the method further comprises:

indexing information about a second plurality of documents using bit vectors on the first accumulation buffer storage device; and

when the threshold is satisfied again, indexing the information about the second plurality of documents using bit vectors on the subsequent storage device based on the information about the second plurality of documents indexed in the first accumulation buffer storage device.

9. The method of claim 1, wherein the method is repeated until a second threshold is satisfied.

10. One or more computer storage media storing computer-useable instructions that, when used by one or more computing devices, cause the one or more computing devices to perform operations comprising:

adding term information about a plurality of documents to bit vectors on a first accumulation buffer storage device until a threshold is satisfied, each bit vector on the first accumulation buffer storage device corresponding with one or more terms from a set of terms and each bit in each bit vector on the first accumulation buffer storage device identifying whether one or more documents corresponding with the bit contains at least one of the one or more terms corresponding with the bit vector on the first accumulation buffer storage device; and

when the threshold is satisfied, adding the term information about the documents to bit vectors on a subsequent storage device, each bit vector on the subsequent storage device corresponding with one or more terms from the set of terms and each bit in each bit vector on the subsequent storage device identifying whether one or more documents corresponding with the bit contains at least one of the one or more terms corresponding with the bit vector on the subsequent storage device.

11. The one or more computer storage media of claim 10, wherein the threshold comprises a threshold number of documents and the threshold is satisfied when the plurality of documents satisfies the threshold number of documents.

12. The one or more computer storage media of claim 10, wherein the threshold comprises a time threshold and the threshold is satisfied when a period of time has passed that satisfies the time threshold.

13. The one or more computer storage media of claim 10, wherein the threshold comprises a storage consumption threshold and the threshold is satisfied when the storage consumption for the term information about the plurality of documents on the first accumulation buffer storage device satisfies the storage consumption threshold.

14. The one or more computer storage media of claim 10, wherein the term information about the plurality of documents is added to the first accumulation buffer storage device one document at a time.

15. The one or more computer storage media of claim 10, wherein the term information about the plurality of documents is added to the first accumulation buffer storage device by collectively indexing at least a portion of the information from a second accumulation buffer storage device.

16. The one or more computer storage media of claim 10, wherein the term information about the plurality of documents are stored in consecutive bits on the first accumulation buffer storage device and wherein adding the term information about the documents to bit vectors on the subsequent storage device comprises storing the information about the plurality of documents in non-consecutive bits on the subsequent storage device.

17. The one or more computer storage media of claim 10, wherein the operations further comprise:

adding term information about a second plurality of documents using bit vectors on the first accumulation buffer storage device; and

when the threshold is satisfied again, adding the term information about the second plurality of documents using bit vectors on the subsequent storage device based on the term information about the second plurality of documents indexed in the first accumulation buffer storage device.

18. The one or more computer storage media of claim 10, wherein the operations are repeated until a second threshold is satisfied.

19. One or more computer storage media storing computer-useable instructions that, when used by one or more computing devices, cause the one or more computing devices to perform operations comprising:

identifying a plurality of terms contained within a document;

identifying a bit corresponding to the document in each of a plurality of bit vectors stored on a storage device, a first bit vector from the plurality of bit vectors comprising an array of bits with each bit of the first bit vector corresponding to all terms from a plurality of terms assigned to the first bit vector and each bit representing whether at least one of one or more documents contains any term from the plurality of terms assigned to the first bit vector; and

setting bits identified for the document in bit vectors corresponding with terms contained within the document.

20. The one or more computer storage media of claim 19, wherein identifying the plurality of terms contained within a document includes identifying a location of each term in the document.