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

• US 10,169,388 B2
• Filed: 11/10/2015
• Issued: 01/01/2019
• 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): Richardson, James E
• Application Number:
  US14/936,880
• Publication Number:
  US 20160070734A1
• Time in Patent Office: 1,148 Days
• 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 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, the M being an integer, each block having been compressed into a compressed block by encoding content of each block using an encoding pattern, the encoding pattern for each block having been determined based on values of the M truncated references in each block;

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 the encoding pattern for the current block, the encoding pattern of 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;

decompressing the current block based on the decoding protocol 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_k·

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; and

the decompressing comprises identifying M database references based on the decoding protocol and the M truncated references within the current block.

2. The method of claim 1, 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.

3. The method of claim 1, wherein the decoding protocol comprises code instructions for executing the operation of decompressing the current block using b, n, p_i . . . P_n, v₁ . . . V_n.

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

5. The method of claim 3, wherein the decoding protocol table comprises the code instructions.

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

7. The method of claim 3, 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.

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

9. The method of claim 8, 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.

10. A database system for locating documents that contain search terms, the system comprising:

a database for storing a plurality of documents;

a memory containing;

a decoding protocol table; and

an inverted index comprising a plurality of posting lists, each posting list being arranged in blocks, each block comprising a header and M truncated binary references, M being an integer, each block having been compressed into a compressed block by encoding content of each block using an encoding pattern, during the encoding of the content of each block M binary database references having been truncated such that to become corresponding M truncated binary references, each one of the M truncated binary references being a portion of a corresponding one of the M binary database references, each one of the M binary database references being a binary representation of one of (i) a document number of a corresponding document of the database and (ii) a delta reference of the corresponding document of the database, the encoding pattern for each block having been determined based on values of the M truncated binary references in each block;

an input for receiving a search term from a client; and

a processor, operably connected to the input, to the database and to the memory, for;

selecting in the memory a posting list associated with the search term;

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

using the pointer to extract a decoding protocol from the decoding protocol table, wherein the decoding protocol defines the encoding pattern for the current block, the encoding pattern for the current block having been determined based on values of the M truncated binary references within the current block, the encoding pattern of the current block comprises;

a base length b of M binary 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 ; and

decompressing the current block based on the decoding protocol by;

reading, in the current block, b·

M bits comprising the M binary truncated references, wherein M−

n of the M binary truncated references are database references; and

if n>

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

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

1 for providing n additional database references,

the decompressing comprises identifying M corresponding binary database references based on the decoding protocol and the M truncated binary references within the current block.