System and method for providing a trustworthy inverted index to enable searching of records

• US 7,765,215 B2
• Filed: 08/22/2006
• Issued: 07/27/2010
• Est. Priority Date: 08/22/2006
• Status: Expired due to Fees

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Mitra, Soumyadeb, Hsu, Windsor Wee Sun
• Primary Examiner(s): Mahmoudi; Tony
• Assistant Examiner(s): Truong; Dennis
• Application Number:
  US11/466,173
• Publication Number:
  US 20080059420A1
• Time in Patent Office: 1,435 Days
• Field of Search: 707/1, 707/100, 707/200, 707/3, 707/5, 707/104.1, 707/102
• US Class Current: 707/742
• 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 plurality of posting lists corresponds to at least one of the identified features;

maintaining, in a storage cache, a tail block of at least one of the plurality of posting lists to minimize random Input/Output to the inverted index;

creating a merged posting list by moving posting lists smaller than one cache block into a combined posting list for reducing the size of the inverted index with a reduction in the plurality of posting lists;

storing the plurality of posting lists in a write-once-read-many (WORM) storage;

storing tail blocks removed from the storage cache into one of the plurality of posting lists in the WORM storage;

maintaining an encoding of the identified features for the inverted index and a record identifier in each entry of the merged posting list;

determining a desired number of the plurality of 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;

ranking records in the plurality of posting lists for answering the query to the plurality of posting lists;

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

displaying the plurality of posting lists on a display device.

2. The method of claim 1, wherein determining the desired number of plurality 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 plurality of posting lists ranges between approximately 512 B and 64 KB.

4. The method of claim 1, wherein generating the plurality of posting lists comprises mapping multiple features randomly to the 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 plurality of 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 received queries.

11. The method of claim 1, wherein generating the plurality of 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 computer-implemented method of providing an index to enable searching of records, the method comprising:

generating an index structure for an increasing sequence of record identifiers and index features;

generating posting lists with the record identifiers and frequency of the index features;

creating a merged posting list by moving posting lists smaller than one block into combined posting lists for reducing the size of the index with a reduction in the number of the posting lists;

searching the combined posting lists in response to a query searching the records;

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

displaying the combined posting lists on a display device.

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 system for providing an inverted index to enable searching of records, the system 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 plurality of posting lists corresponds to at least one of the identified features;

a storage cache for maintaining a tail block of at least one of the plurality of posting lists to minimize random Input/Output to the inverted index;

a merge module for creating a merged posting list by moving posting lists smaller than one cache block into a combined posting list for reducing the size of the inverted index with a reduction in the plurality of posting lists, and for maintaining an encoding of the identified features for the inverted index and a record identifier in each entry of the merged posting list;

a write-once-read-many (WORM) storage for storing the plurality of posting lists, and storing tail blocks removed from the storage cache into one of the plurality of posting lists;

a strategy module for determining a desired number of the plurality of 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;

a ranking module for ranking records in the plurality of posting lists for answering the query to the plurality of posting lists;

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

a display module for displaying the plurality of posting lists on a display device.

20. The system of claim 19, wherein the strategy module determines the desired number of the plurality of posting lists based on the size of the storage cache by dividing an 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 plurality of posting lists ranges between approximately 512 B and 64 KB.

22. The system of claim 19, wherein the index insert module generates the plurality of posting lists by mapping multiple features randomly to the 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 plurality of posting lists are stored in WORM storage.

27. The system 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 plurality of posting lists;

and

wherein the query runtime module looks up the index structure.

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

an index insert module including a computer processor for generating an index structure for an increasing sequence of record identifiers and index features;

a generation module for generating posting lists with the record identifiers and frequency of the index features;

a merge module for creating a merged posting list by moving posting lists smaller than one block into combined posting lists for reducing the size of the index with a reduction in the number of the posting lists;

a search module for searching the combined posting lists in response to a query searching the records;

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;

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

a display module for displaying the combined posting lists on a display device.

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 system 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 system 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 system 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 system of claim 30, wherein the reference identifier is a largest identifier stored in the root node.

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

37. A computer product for providing an inverted index to enable searching of records, the computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

computer readable program code configured to process the records to identify features for indexing in the inverted index;

computer readable program code configured to generate a plurality of posting lists from the records, wherein each of the posting lists corresponds to at least one of the identified features;

computer readable program code configured to maintain in a storage cache a tail block of at least one of the plurality of posting lists to minimize random Input/Output to the inverted index;

computer readable program code configured to create a merged posting list by moving posting lists smaller than one cache block into a combined posting list for reducing the size of the inverted index with a reduction in the plurality of posting lists;

computer readable program code configured to store the plurality of posting lists in a write-once-read-many (WORM) storage;

computer readable program code configured to store tail blocks removed from the storage cache into one of the plurality of posting lists in the WORM storage;

computer readable program code configured to maintain an encoding of the identified features for the inverted index and a record identifier in each entry of the merged posting list;

computer readable program code configured to determine a desired number of the plurality of posting lists based on a desired level of any of an insertion performance, a query performance, and a size of the storage cache;

computer readable program code configured to receive a query that includes a search feature;

computer readable program code configured to rank records in the plurality of posting lists for answering the query to the plurality of posting lists;

computer readable program code configured to read a posting list corresponding to the search feature in the query, in order to identify records that include the search feature; and

computer readable program code configured to display the plurality of posting lists on a display device.

38. A computer product for providing an index to enable searching of records, the computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

computer readable program code configured to generate an index structure for an increasing sequence of record identifiers and index features;

computer readable program code configured to generate posting lists with the record identifiers and frequency of the index features;

computer readable program code configured to create a merged posting list by moving posting lists smaller than one block into combined posting lists for reducing the size of the index with a reduction in the number of the posting lists;

computer readable program code configured to search the combined posting lists in response to a query searching the records;

computer readable program code configured to insert 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, computer readable program code 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; and

computer readable program code configured to display the combined posting lists on a display device.