Inverted indexing

Patent metadata

Field	Value
Publication number	US-9971770-B2
Application number	US-201414552897-A
Country	US
Kind code	B2
Filing date	Nov 25, 2014
Priority date	Nov 25, 2014
Publication date	May 15, 2018
Grant date	May 15, 2018

Abstract

Disclosed herein are system, method, and computer program product embodiments for inverted indexing. An embodiment operates by receiving a request to add a new document identifier (doc ID) to an inverted index. A memory block corresponding to where the doc ID is to be added is determined or located, and the available space remaining in the memory block is determined. If the memory block has available space, the doc ID is added to the memory block.

First claim

What is claimed is:

1. A method, comprising:
receiving a request to add a new document identifier to an inverted index, wherein document identifiers in the inverted index correspond to documents that include a value;
determining a first memory block that includes a most recently added document identifier corresponding to the value;
determining that the first memory block does not have available space for the new document identifier;
allocating a new memory block of the inverted index corresponding to the value;
inserting the new document identifier into the new memory block of the inverted index, wherein the inverted index includes both the document identifiers of the first memory block and the new document identifier of the new memory block; and
generating a first pointer that points from the first memory block to the new document identifier in the new memory block and a second pointer that points from the new memory block to the first memory block, wherein both the first and new memory blocks of the inverted index comprise a continuous portion of memory that is allocated to store document identifiers corresponding to the value.

2. The method of claim 1 , wherein the document includes a plurality of fields, wherein inverted index is associated with a selected one of the fields, and wherein the field is associated with a plurality of values, each value corresponding to one or more memory blocks.

3. The method of claim 2 , further comprising:
determining that the field of the document corresponding to the new document identifier includes a value not included in the plurality of values;
creating the new memory block into which to insert the new document identifier, wherein the new memory block corresponds to the value not included in the plurality of values;
inserting the new document identifier into the new memory block.

4. The method of claim 1 , wherein inverted index includes a bitmap value corresponding to which documents of the document store include the value.

5. The method of claim 4 , wherein the inserting comprises adjusting the bitmap value to correspond to the new document identifier.

6. The method of claim 1 , wherein the first memory block includes a bitmap corresponding to one or more document identifiers correspond to value, and one or more document identifiers outside of the bitmap.

7. The method of claim 1 , wherein the first memory block includes a block count of how many document identifiers are stored in the particular memory block and corresponding to the value.

8. A system, comprising:
a memory; and
at least one processor coupled to the memory and configured to:
receive a request to add a new document identifier to an inverted index, wherein document identifiers in the inverted index correspond to documents that include a value;
determine a first memory block that includes a most recently added document identifier corresponding to the value;
determine that the first memory block does not have available space for the new document identifier;
allocate a new memory block of the inverted index corresponding to the value;
insert the new document identifier into the new memory block of the inverted index, wherein the inverted index includes both the document identifiers of the first memory block and the new document identifier of the new memory block; and
generate a first pointer that points from the first memory block to the new document identifier in the new memory block and a second pointer that points from the new memory block to the first memory block, wherein both the first and new memory blocks of the inverted index comprise a continuous portion of memory that is allocated to store document identifiers corresponding to the value.

9. The system of claim 8 , wherein the document includes a plurality of fields, wherein inverted index is associated with a selected one of the fields, and wherein the field is associated with a plurality of values, each value corresponding to one or more memory blocks.

10. The system of claim 9 , wherein the processor is further configured to:
determine that the field of the document corresponding to the new document identifier includes a value not included in the plurality of values;
create the new memory block into which to insert the new document identifier, wherein the new memory block corresponds to the value not included in the plurality of values;
insert the new document identifier into the new memory block.

11. The system of claim 8 , wherein inverted index includes a bitmap value corresponding to which documents of the document store include the value.

12. The system of claim 11 , wherein the processor configured to insert comprises a processor configured to adjust the bitmap value to correspond to the new document identifier.

13. A non-transitory computer-readable device having instructions stored thereon that, when executed by at least one computing device, causes the at least one computing device to perform operations comprising:
receiving a request to add a new document identifier to an inverted index, wherein document identifiers in the inverted index correspond to documents that include a value;
determining a first memory block that includes a most recently added document identifier corresponding to the value;
determining that the first memory block does not have available space for the new document identifier;
allocating a new memory block of the inverted index corresponding to the value;
inserting the new document identifier into the new memory block of the inverted index, wherein the inverted index includes both the document identifiers of the first memory block and the new document identifier of the new memory block; and
generating a first pointer that points from the first memory block to the new document identifier in the new memory block and a second pointer that points from the new memory block to the first memory block, wherein both the first and new memory blocks of the inverted index comprise a continuous portion of memory that is allocated to store document identifiers corresponding to the value.

14. The computer-readable device of claim 13 , wherein the document includes a plurality of fields, wherein inverted index is associated with a selected one of the fields, and wherein the field is associated with a plurality of values, each value corresponding to one or more memory blocks.

15. The computer-readable device of claim 14 , the operations further comprising:
determining that the field of the document corresponding to the new document identifier includes a value not included in the plurality of values;
creating the new memory block into which to insert the new document identifier, wherein the new memory block corresponds to the value not included in the plurality of values;
inserting the new document identifier into the new memory block.

16. The computer-readable device of claim 13 , wherein inverted index includes a bitmap value corresponding to which documents of the document store include the value.

Assignees

• Schreter Ivan
• Gottipati Chaitanya
• Legler Thomas
• Sap Se

Inventors

• Schreter Ivan
• Gottipati Chaitanya
• Legler Thomas

Classifications

• G06F16/93 Primary

  Document management systems · CPC title

• G06F16/319

  Inverted lists · CPC title

• G06F17/30011 Primary

  Physics · mapped topic

• G06F17/30622

  Physics · mapped topic