Methods and systems for indexing references to documents of a database and for locating documents in the database

• US 9,471,613 B2
• Filed: 08/19/2015
• Issued: 10/18/2016
• Est. Priority Date: 10/10/2013
• Status: Active Grant

• Current Assignee: Direct Cursus Technology LLC
• Original Assignee: Yandex Europe AG (Yandex N.V.)
• Inventors: Popov, Petr Sergeevich
• Primary Examiner(s): Bowen, Richard
• Application Number:
  US14/829,665
• Publication Number:
  US 20150356169A1
• Time in Patent Office: 426 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/316 Indexing structures
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

Methods and systems allow indexing references to documents of a database according to database reference profiles. Documents may then be located in the database using decoding protocols based on the database reference profiles. To this end, the documents are stored in the database and searchable terms extracted therefrom are associated with posting lists. Each posting list is divided into blocks of M database references. The blocks are encoded according to a pattern that depends on the M database references. A corresponding pointer to a table of encoding patterns is appended to each block. When a query is received for a searchable term, blocks are extracted from a posting list corresponding to the searchable term and a pointer for each block is used to extract a decoding protocol related to an encoding pattern for the block.

Claims

1. A method for indexing references to documents of a database, the method comprising:

receiving a document, at the database, from a server;

storing the document in the database;

extracting a searchable term from the document, the searchable term being associated with a posting list;

dividing the posting list into blocks, each block comprising M database references;

for each block;

determining an encoding pattern based on values of the M database references, the determining the encoding pattern comprises;

determining a number n of patches according to a number of references, among the M database references, that are greater than or equal to 2^b; and

if n>

0;

calculating, for each of n patches, a patch value v_k by deleting b least significant bits from a corresponding one of the M database references that are greater than or equal to 2^b, wherein k is in a range from 1 to n, and

determining, for each of the n patches, a patch position p_k corresponding to a position, in a range of 0 to M−

1, of the corresponding one of the M database references that are greater than or equal to 2^b;

wherein the encoding pattern comprises b, n, p₁ . . . p_n, v₁ . . . v_n;

locating an encoding pattern table entry corresponding to the encoding pattern;

inserting a pointer corresponding to the located encoding pattern table entry in a header for the block; and

inserting in the block a sequence of M truncated references, each truncated reference comprising b least significant bits of a corresponding one of the M database references.

2. The method of claim 1, wherein if n=0, the encoding pattern comprises b, n.

3. The method of claim 1, wherein M is equal to 4 and n is equal to 0 or to 1.

4. The method of claim 1, comprising:

calculating, for each block a patch length d as a length, in bits, of a largest one of the n patches;

wherein the encoding pattern comprises b, n, d, p₁ . . . p_n, v₁ . . . v_n.

5. The method of claim 1, wherein the header comprises an explicit value for at least one of b, n, p₁ . . . p_n, v₁ . . . v_n.

6. The method of claim 1, wherein determining an encoding pattern for a given block comprises:

identifying three largest database references among the M database references of the given block; and

selecting a value of b sufficient to encode a third largest of the M database references;

whereby n is not greater than 2.

7. The method of claim 1, comprising independently selecting a value of b for each block.

8. The method of claim 7, comprising selecting the value of b for a given block so that n is not greater than 2.

9. The method of claim 7, comprising selecting the value of b for a given block according to the largest of the M database references of the given block.

10. The method of claim 1, wherein an encoding pattern table comprises 256 encoding pattern table entries for 256 corresponding encoding patterns.

11. The method of claim 10, wherein:

a first subset of the 256 encoding patterns comprises a plurality of values of b; and

each encoding pattern of the first subset defines n=0.

12. The method of claim 11, wherein database references of a block corresponding to an encoding pattern of the first subset are not compressed.

13. The method of claim 11, wherein a second subset of the 256 encoding patterns comprises most frequently used encoding patterns.

14. The method of claim 13, wherein a majority of the encoding patterns of the second subset have smaller values of b than a majority of the encoding patterns of the first subset.

15. The method of claim 10, wherein the 256 encoding patterns comprise:

24 encoding patterns for 24 distinct values of b combined with n=0;

120 encoding patterns comprising b, n=1, p₁, v₁, each of the 120 encoding patterns having a single patch, one of 5 distinct values of b, one of 3 distinct patch values and one of 8 distinct patch positions; and

112 encoding patterns comprising b, n=2, p₁, p₂, 1, 1, each of the 112 encoding patterns having two patch values equal to 1, one of 4 distinct values of b, wherein p₁ and p₂ form 28 distinct combinations of patch positions for the two patches.

16. The method of claim 15, comprising:

sorting the 256 encoding patterns with positions in increasing order of a sum of b with a length of v; and

for a given sum, sorting further the encoding patterns with positions in increasing values of b;

wherein determining an encoding pattern for a given block comprises searching an encoding pattern by scanning through the sorted encoding patterns starting from a position corresponding to a length of a largest of the M database references of the given block.

17. A method for locating documents of a database that contain search terms, the method comprising:

receiving a search term, at the database, from a client, the search term being associated with a posting list, the posting list being arranged in blocks, each block comprising a header and M truncated references;

reading a pointer from a header of a current block of the posting list;

using the pointer to extract a decoding protocol from a decoding protocol table, wherein the decoding protocol defines an encoding pattern for the current block, the encoding pattern for the current block comprises;

a base length b of M truncated references in the current block;

a number n of patches in the current block;

if n>

0, one or more patch values v_k of the current block, wherein k is in a range from 1 to n;

if n>

0, one or more patch positions p_k in the current block, wherein p_k is in a range of 0 to M−

1.

18. The method of claim 17, wherein the decoding protocol table comprises a table of descriptors defining b, n, p₁ . . . p_n, v₁ . . . v_n for a plurality of encoding patterns.

19. The method of claim 17, wherein a length of the current block is defined by a length of the header and by the encoding pattern.

20. The method of claim 17, comprising:

decompressing the current block by;

reading, in the current block, b·

M bits comprising the M truncated references, wherein M−

n of the M truncated references are database references; and

if n>

0, for each patch from k=1 to n, calculating an expanded patch value as v₄·

2^b and adding the expanded patch value to a p_k^th of the M truncated reference numbered from 0 to M−

1 for providing n additional database references.

21. The method of claim 20, comprising:

reading a next pointer from a next header of a next current block of the posting list; and

using the next pointer to;

extract a next decoding protocol; and

decompress the next current block;

whereby a complete list of database references to documents of the database that contain the search term is obtained from reading the complete posting list.

22. The method of claim 20, wherein the decoding protocol comprises code instructions for executing the operation of decompressing the current block using b, n, p₁ . . . p_n, v₁ . . . v_n.

23. The method of claim 22, wherein a distinct set of code instructions is defined for each distinct encoding pattern.

24. The method of claim 22, wherein the decoding protocol table comprises the code instructions.

25. The method of claim 22, wherein the decoding protocol table comprises a table of references to the code instructions.

26. The method of claim 22, comprising:

defining 2 arrays, each array comprising M data fields of equal size;

inserting the M truncated references in the M data fields of a first array;

initializing the M data fields of the second array with all-zero values;

if n>

0, for each patch from k=1 to n, inserting a n^th expanded patch value to a p_k^th data field of the second array, wherein the M data fields of the second array are numbered from 0 to M−

1;

adding values of the second array to values of the first array; and

reading the M database references from the first array.

27. The method of claim 26, wherein the data fields of the first and second arrays each comprise L bytes.

28. The method of claim 27, wherein a given block having a database reference greater than 2^L·

8−

1 has an encoding pattern comprising b>

L·

8 and n=0.