System and Method for Providing a Trustworthy Inverted Index to Enable Searching of Records

• US 20080059420A1
• Filed: 08/22/2006
• Published: 03/06/2008
• Est. Priority Date: 08/22/2006
• Status: Active Grant

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Hsu, Windsor Wee Sun, Mitra, Soumyadeb
• Granted Patent: US 7,765,215 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/328 Management therefor
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures

Abstract

A trustworthy inverted index system processes records to identify features for indexing, generates posting lists corresponding to features in a dictionary, maintains in a storage cache a tail of at least one of the posting lists to minimize random I/Os to the index, determines a desired number of the posting lists based on a desired level of insertion performance, a query performance, or a size of the storage cache, and reads a posting list corresponding to a search feature in a query to identify records that comprise the search feature. The system maps the features in the dictionary to the desired number of posting lists. The system uses a jump pointer to point from one entry to the next in the posting lists based on increasing values of entries in the posting lists.

Claims

1. A processor-implemented method of providing an inverted index to enable searching of records, the method comprising:

processing the records to identify features for indexing in the inverted index;

generating a plurality of posting lists from the records, wherein each of the posting lists corresponds to at least one of the identified features;

maintaining, in a storage cache, a tail of at least one of the posting lists to minimize random I/Os to the inverted index;

determining a desired number of the posting lists based on a desired level of any of an insertion performance, a query performance, and a size of the storage cache;

receiving a query that includes a search feature; and

reading a posting list corresponding to the search feature in the query, in order to identify records that include the search feature.

2. The method of claim 1, wherein determining the desired number of posting lists based on the size of the storage cache comprises dividing an available size of the storage cache by an allowed size for each one of the posting lists.

3. The method of claim 2, wherein the allowed size of each of the posting lists ranges between approximately 512 B and 64KB.

4. The method of claim 1, wherein generating the posting lists comprises mapping multiple features to a merged posting list.

5. The method of claim 4, wherein the multiple features mapped to the merged posting list comprise the features that occur infrequently in the processed records.

6. The method of claim 4, wherein the multiple features mapped to the merged posting list comprise the features that occur infrequently in queries.

7. The method of claim 4, wherein the multiple features mapped to the merged posting list are determined based on a hash of the multiple features.

8. The method of claim 1, wherein the posting lists are stored in WORM storage.

9. The method of claim 1, wherein processing the records includes updating statistics associated with the records processed.

10. The method of claim 1, wherein receiving a query includes parsing the query to extract a feature, and updating statistics associated with the receive queries.

11. The method of claim 1, wherein generating the posting lists includes generating an index structure including the entries in the posting lists;

and

wherein reading the posting list includes looking up the index structure.

12. A method of providing an index to enable searching of records, the method comprising:

generating an index structure for an increasing sequence of identifiers;

inserting an identifier for a new record into the index structure beginning at a root node of the index structure;

wherein inserting the identifier of the new record comprises comparing the identifier of the new record and a reference identifier at the root node of the index structure; and

upon a determination that inserting the identifier of the new record is unsuccessful, identifying a target node in the index structure based on a jump pointer that points to the target node, and recursively repeating the step of inserting the identifier of the new record starting at the target node, until the identifier of the new record is successfully inserted into the index structure.

13. The method of claim 12, wherein the inserted identifier is not relocated and the path through the index structure to the identifier is immutable.

14. The method of claim 12, further comprising generating a new node if the target node does not exist and updating a jump pointer to point to the new node.

15. The method of claim 12, wherein the jump pointer is identified using a mathematical difference between the identifier and the reference identifier of a current node.

16. The method of claim 12, wherein the jump pointer is identified using a logarithm of a mathematical difference between the identifier and the reference identifier of a current node.

17. The method of claim 12, wherein the reference identifier is a largest identifier stored in the node.

18. The method of claim 12, wherein the index structure is tree-like.

19. A processor-implemented method of providing an inverted index to enable searching of records, the method comprising:

a record ingest module for processing the records to identify features for indexing in the inverted index;

an index insert module for generating a plurality of posting lists from the records, wherein each of the posting lists corresponds to at least one of the identified features;

a storage cache for maintaining a tail of at least one of the posting lists to minimize random I/Os to the inverted index;

a strategy module for determining a desired number of the posting lists based on a desired level of any of an insertion performance, a query performance, and a size of the storage cache;

a query interface for receiving a query that includes a search feature; and

a query runtime module for reading a posting list corresponding to the search feature in the query, in order to identify records that include the search feature.

20. The system of claim 19, wherein the strategy module determines the desired number of posting lists based on the size of the storage cache by dividing as available size of the storage cache by an allowed size for each one of the posting lists.

21. The system of claim 20, wherein the allowed size of each of the posting lists ranges between approximately 512 B and 64 KB.

22. The system of claim 19, wherein the index insert module generates the posting lists by mapping multiple features to a merged posting list.

23. The system of claim 22, wherein the multiple features mapped to the merged posting list comprise the features that occur infrequently in the processed records.

24. The system of claim 22, wherein the multiple features mapped to the merged posting list comprise the features that occur infrequently in queries.

25. The system of claim 22, wherein the multiple features mapped to the merged posting list are determined based on a hash of the multiple features.

26. The system of claim 19, wherein the posting lists are stored in WORM storage.

27. The method of claim 19, further comprising a statistics manager for updating statistics associated with the records processed.

28. The system of claim 19, further comprising:

a query runtime module for parsing the query in order to extract a feature; and

a statistics manager for updating statistics associated with the received queries.

29. The system of claim 19, wherein the index insert module generates an index structure that includes the entries in the posting lists;

and

wherein the query runtime module looks up the index structure.

30. A processor-implemented system for providing an index to enable searching of records, the system comprising:

an index insert module for generating an index structure for an increasing sequence of identifiers;

the index insert module inserting an identifier for a new record into the index structure beginning at a root node of the index structure by comparing the identifier of the new record and a reference identifier at the root node of the index structure; and

upon a determination by the index insert module that inserting the identifier of the new record is unsuccessful, the index insert module identifies a target node in the index structure based on a jump pointer that points to a target node, and recursively repeats the insertion of the identifier of the new record starting at the target node, until the identifier of the new record is successfully inserted into the index structure.

31. The system of claim 30, wherein the inserted identifier is not relocated and the path through the index structure to the identifier is immutable.

32. The method of claim 30, further comprising the index insert module generating a new node if the target node does not exist and updating a jump pointer to point to the new node.

33. The method of claim 30, wherein the jump pointer is identified using a mathematical difference between the identifier and the reference identifier of a current node.

34. The method of claim 30, wherein the jump pointer is identified using a logarithm of a mathematical difference between the identifier and the reference identifier of a current node.

35. The method of claim 30, wherein the reference identifier is a largest identifier stored in the node.

36. The method of claim 30, wherein the index structure is tree-like.

37. A computer product including a plurality of executable instruction codes stored on a computer-usable medium, for providing an inverted index to enable searching of records, the system comprising:

a set of instruction codes for processing the records to identify features for indexing in the inverted index;

a set of instruction codes for generating a plurality of posting lists from the records, wherein each of the posting lists corresponds to at least one of the identified features;

a storage cache for maintaining a tail of at least one of the posting lists to minimize random I/Os to the inverted index;

a set of instruction codes for determining a desired number of the posting lists based on a desired level of any of an insertion performance, a query performance, and a size of the storage cache;

a set of instruction codes for receiving a query that includes a search feature; and

a set of instruction codes for reading a posting list corresponding to the search feature in the query, in order to identify records that include the search feature.

38. A computer product including a plurality of executable instruction codes stored on a computer-usable medium, for providing an index to enable searching of records, the system comprising:

a set of instruction codes for generating an index structure for an increasing sequence of identifiers;

a set of instruction codes for inserting an identifier for a new record into the index structure beginning at a root node of the index structure by comparing the identifier of the new record and a reference identifier at the root node of the index structure; and

upon a determination that inserting the identifier of the new record is unsuccessful, a set of instruction codes identifies a target node in the index structure based on a jump pointer that points to the target node, and recursively repeats the insertion of the identifier of the new record starting at the target node, until the identifier of the new record is successfully inserted into the index structure.