HASHED INDEXING

• US 20070294235A1
• Filed: 08/30/2007
• Published: 12/20/2007
• Est. Priority Date: 03/03/2006
• Status: Active Grant

• Current Assignee: Perfect Search Corporation
• Original Assignee: Perfect Search Corporation
• Inventors: Millett, Ronald
• Granted Patent: US 8,266,152 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2264 Multidimensional index structures

Abstract

Indexing data items into an index. A method includes identifying a parameter pattern for a data item stored in a data store record of a data store. The data store record has a data store location identifier. The method further includes identifying a hash of the parameter pattern. The data store location identifier is correlated to at least a portion of the hash in the index. The index includes index entries where each index entry includes at least a portion of a hash and one or more references to data store records by reference to data store location identifiers.

Claims

1. In a computing environment including a data store, the data store including data items stored in records in the data store, a method of indexing data items as parameter patterns into an index, the method comprising:

identifying a parameter pattern for a data item stored in a data store record of a data store, the data store record having a data store location identifier;

identifying a hash of the parameter pattern; and

correlating the data store location identifier to at least a portion of the hash in the index, wherein the index includes index entries, each index entry including at least a portion of a hash and one or more references to data store records by reference to data store location identifiers.

2. The method of claim 1, wherein hashes are indexed in numeric ascending or descending order in the index.

3. The method of claim 1, further comprising:

after identifying the hash of the parameter pattern, referencing an offset correlation table, the offset correlation table comprising portions of hash codes correlated to index entry addresses; and

based on referencing the offset correlation table, either;

determining that the hash is not presently included in an index entry without directly referencing the index and thereafter creating an index entry for the hash and data store record identifier;

or

determining an index entry address to begin searching for an index entry that includes the hash.

4. The method of claim 3, wherein the index comprises a linked list including pointers to previous and next index entries to accomplish numeric ordering of hashes in the index, wherein if determining an index entry address to begin searching for an index entry that includes the hash is performed, the method further comprises following one or more of the pointers to search for an index entry including the calculated hash.

5. The method of claim 3, further comprising generating the offset correlation table when a pre-specified number of entries are included in the index.

6. The method of claim 3, further comprising re-generating the offset correlation table when the index has grown by a pre-determined amount.

7. The method of claim 3, wherein determining that the hash is not presently included in an index entry comprises determining that a portion of the hash of the parameter pattern is not correlated to an index entry address in the offset correlation table, and after creating an index entry for the hash and data store record identifier, thereafter correlating in the offset correlation table an index entry address for the index entry to the portion of the hash of the parameter pattern.

8. The method of claim 3, further comprising:

determining that the hash is not presently included in an index entry by directly referencing the index;

thereafter creating an index entry for the hash and data store record identifier;

determining that a portion of the hash correlated to an index entry address is included in the offset correlation table as a result of the hash being in a group where at least one member of the group is already indexed;

determining that the index entry for the is prior to any index entry of any previously indexed member of the group; and

thereafter correlating in the offset correlation table an index entry address for the index entry for the hash to the portion of the hash of the parameter pattern.

9. The method of claim 1, wherein identifying a hash comprises calculating a hash.

10. The method of claim 9, wherein calculating a hash is performed during a parse phase of the data store.

11. The method of claim 10, wherein the parse phase comprises indexing parameter patterns into an abbreviated index, the abbreviated index including a field, wherein the field comprises a first plurality of binary bits, each binary bit corresponding to a hash corresponding to a parameter pattern, and wherein when the bit is set, the parameter pattern is included in the abbreviated index.

12. In a computing environment including a data store, the data store including data items stored in records in the data store, a computer readable medium storing computer executable instructions that when executed by a processor cause the following acts to be performed:

identifying a parameter pattern for a data item stored in a data store record of a data store, the data store record having a data store location identifier;

identifying a hash of the parameter pattern; and

correlating the data store location identifier to at least a portion of the hash in the index, wherein the index includes index entries, each index entry including at least a portion of a hash and one or more references to data store records by reference to data store location identifiers.

13. In a computing environment including a data store, the data store including data items stored in records in the data store, a system for indexing data items as parameter patterns into an index, system comprising:

one or more processors;

a computer readable memory coupled to the one or more processors, the computer readable memory storing computer executable instructions that when executed by the one or more processors cause the following acts to be performed;

identifying a parameter pattern for a data item stored in a data store record of a data store, the data store record having a data store location identifier;

identifying a hash of the parameter pattern; and

correlating the data store location identifier to at least a portion of the hash in the index, wherein the index includes index entries, each index entry including at least a portion of a hash and one or more references to data store records by reference to data store location identifiers.