Encoding and accessing position data

• US 9,507,827 B1
• Filed: 06/30/2011
• Issued: 11/29/2016
• Est. Priority Date: 03/25/2010
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Excalibur IP, LLC (Acacia Research Corporation)
• Inventors: Poutanen, Tomi
• Primary Examiner(s): Hershley, Mark E
• Application Number:
  US13/173,532
• Time in Patent Office: 1,979 Days
• Field of Search: 707/727
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/93 Document management systems

Abstract

In one embodiment, a data structure comprises: a primary index comprising one or more position-block references; and one or more position blocks sequentially following the primary index, wherein: each one of the position-block references corresponds to one of the position blocks; and each one of the position blocks comprises: a secondary index comprising one or more position-data references; and one or more sets of positions sequentially following the secondary index, wherein each one of the position-data references corresponds to of one of the sets of positions in the position block. In one embodiment, an instance of the data structure is stored in a computer-readable memory and accessible by an application executed by a process.

Claims

1. A machine-readable non-transitory medium storing a data structure for access by an application executed by a process, the data structure comprising:

a primary index comprising a plurality of position-block references; and

a plurality of position blocks sequentially following each other and starting from an end position of the primary index, wherein;

each of the position-block references corresponds to a position-block offset equal to an offset from a beginning memory location of the data structure to a beginning memory location of a corresponding position block; and

each of the position blocks comprises;

a secondary index comprising a plurality of position-data references; and

a plurality of position data fields sequentially following each other and starting from an end position of the secondary index, wherein;

each of the plurality of position data fields comprises a first position and one or more subsequent positions,

the first position is equal to an offset from a beginning memory location of the position data field to a beginning memory location of the first position, and

each of the one or more subsequent positions is equal to a difference between a beginning memory location of the subsequent position and a beginning memory location of another position immediately preceding the subsequent position in the position data field.

2. The medium of claim 1, wherein an instance of the data structure is used to encode position data of a token for one or more documents in which the token appears, wherein:

the token comprises one or more alphabetical letters, numerical digits, or symbols;

the position data of the token comprises all of the position data fields in all of the position blocks; and

each one of the position data fields comprises one or more positions at which the token appears in one of the documents.

3. The medium of claim 2, wherein for each one of the position data fields, each one of the positions is encoded using a same number of bits that equals the minimum number of bits necessary to encode the largest one of the positions.

4. The medium of claim 2, wherein for each one of the position blocks, the position block further comprises one or more padding bits following one or more of the position data fields in the position block.

5. The medium of claim 1, wherein each one of the position-block offsets in the primary index references a memory location at the beginning of the corresponding one of the position blocks.

6. The medium of claim 1, wherein each one of the position-data lengths in the secondary index in each one of the position blocks is encoded using one byte.

7. The medium of claim 1, wherein:

each one of the position blocks, except the last one of the position blocks, comprises a same number of position data fields; and

the last one of the position blocks comprises the same number or less than the number of position data fields contained in other ones of the position blocks.

8. The medium of claim 7, wherein:

each one of the position blocks, except the last one of the position blocks, comprises sixteen position data fields; and

the last one of the position blocks comprises sixteen or less than sixteen position data fields.