Inverted indexing

Patent metadata

Field	Value
Publication number	US-2016147808-A1
Application number	US-201414552897-A
Country	US
Kind code	A1
Filing date	Nov 25, 2014
Priority date	Nov 25, 2014
Publication date	May 26, 2016
Grant date	—

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 doe 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 memory block that includes a most recently added document identifier corresponding to the value; and determining whether the memory block has available space for the new document identifier, wherein the new document identifier is inserted into the memory block if the memory block has available space for the new document identifier.

2 . The method of claim 1 , further comprising:
wherein if the memory block does not have available space for the document identifier:
a new memory block corresponding to the value is allocated, wherein the new document identifier is inserted into the new memory block; and
a pointer is generated, wherein the pointer points from the memory block that includes the most recently added document identifier to the to the new memory block.

3 . The method of claim 2 wherein the generating further comprises:
a second pointer is generated from the new memory block to the memory block that includes the most recently added document identifier.

4 . 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.

5 . The method of claim 4 , 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 a 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.

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

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

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 memory block that includes a most recently added document identifier corresponding to the value; and
determine whether the memory block has available space for the new document identifier, wherein the new document identifier is inserted into the memory block if the memory block has available space for the new document identifier.

9 . The system of claim 8 , wherein the processor is further configured to:
wherein if the memory block does not have available space for the document identifier:
allocate a new memory block into which to insert the new document identifier;
generate a pointer from the memory block that includes the most recently added document identifier to the to the new memory block; and insert the new document identifier into the new memory block.

10 . The system of claim 9 , wherein the processor is further configured to:
generate a second pointer from the new memory block to the memory block that includes the most recently added document identifier.

11 . 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.

12 . The system of claim 11 , 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 a 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.

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

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

15 . A tangible 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 memory block that includes a most recently added document identifier corresponding to the value; and determining whether the memory block has available space for the new document identifier, wherein the new document identifier is inserted into the memory block if the memory block has available space for the new document identifier.

16 . The computer-readable device of claim 15 , the operations further comprising:
wherein if the memory block does not have available space for the document identifier:
a new memory block is allocated, wherein the new document identifier is inserted into the new memory block;
a pointer is generated from the memory block that includes the most recently added document identifier to the to the new memory block.

17 . The computer-readable device of claim 16 , further comprising:
generating a second pointer from the new memory block to the memory block that includes the most recently added document identifier.

18 . The computer-readable device of claim 15 , 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.

19 . The computer-readable device of claim 18 , 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 a 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.

20 . The computer-readable device of claim 15 , 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

Inventors

• Schreter Ivan
• Gottipati Chaitanya
• Legler Thomas

Classifications

• G06F16/93 Primary

  Document management systems · CPC title

• G06F16/319

  Inverted lists · CPC title

• G06F17/30348

  Physics · mapped topic

• G06F17/30336 Primary

  Physics · mapped topic

• G06F17/30011

  Physics · mapped topic