Using inverted indexes for contextual personalized information retrieval

• US 8,024,329 B1
• Filed: 06/01/2007
• Issued: 09/20/2011
• Est. Priority Date: 06/01/2006
• Status: Active Grant

• Current Assignee: Monster Worldwide Incorporated (Randstad NV)
• Original Assignee: Monster Worldwide Incorporated (Randstad NV)
• Inventors: Rennison, Earl
• Primary Examiner(s): Kim; Paul
• Application Number:
  US11/757,199
• Time in Patent Office: 1,572 Days
• Field of Search: 707/723, 707/706
• US Class Current: 707/723
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/3332 Query translation
• CPC Class Codes: G06F 16/3334 Selection or weighting of terms from queries, including natural language queries
• CPC Class Codes: G06F 16/3335 Syntactic pre-processing, e.g. stopword elimination, stemming
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536
• CPC Class Codes: G06F 16/906 Clustering; Classification
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

Information retrieval systems face challenging problems with delivering highly relevant and highly inclusive search results in response to a user'"'"'s query. Contextual personalized information retrieval uses a set of integrated methodologies that can combine automatic concept extraction/matching from text, a powerful fuzzy search engine, and a collaborative user preference learning engine to provide accurate and personalized search results. The system can include constructing a search query to execute a search of a database. The system can parse an input query from a user conducting the search of the database into sub-strings, and can match the sub-strings to concepts in a semantic concept network of a knowledge base. The system can further map the matched concepts to criteria and criteria values that specify a set of constraints on and scoring parameters for the matched concepts.

Claims

1. A method for using indexes to search a knowledge base in at least one computer system, the method executed by the computer system and comprising:

accessing a knowledge base comprising a semantic network of relationships among concepts, each concept having a set of values associated with it, wherein each concept is an instance of a category and each value is an instance of an attribute and wherein categories and attributes form a knowledge base schema;

receiving, from a user searching for one or more target concepts, a query represented as criteria and criteria values that specify constraints on the categories and the attributes;

executing a search of the concepts and the values of the knowledge base to retrieve the one or more target concepts using indexes selected from a group consisting of;

a) one or more transitive indexes that index transitive relationships from concepts in a first category through at least one second category to concepts in a third category and b) one or more transitive closure indexes that index transitive closure relationships amongst concepts within a category; and

retrieving a result subset of the target concepts and the values that satisfies the criteria and criteria values.

2. The method of claim 1, wherein the search is a search for resumes of job applicants.

3. The method of claim 1, wherein the search is a search for job descriptions.

4. The method of claim 1, wherein at least one of the indexes is an attribute index of single concepts referring to a single value.

5. The method of claim 1, wherein at least one of the indexes is an attribute index of single concepts referring to a set of multiple values.

6. The method of claim 5, wherein at least one of the indexes is an attribute index of single concepts referring to two or more sets of multiple correlated values.

7. The method of claim 6, wherein the single concepts refer to one or more sets of string values broken down into sets of sub-string values and integer values, the integer values comprising positions where the string values occur within a string.

8. The method of claim 1, wherein at least one of the indexes is an attribute index of a concept referring to a single concept.

9. The method of claim 1, wherein at least one of the indexes is an attribute index of a concept referring to a set of multiple concepts.

10. The method of claim 1, wherein at least one of the indexes is an attribute index of a concept referring to a set of multiple concepts within the same category forming a parent-child relationship, the index comprising computing transitive closure along a specified direction in the parent-child relationship for indexing all reachable concepts moving in the specified direction given a specific concept in the category.

11. The method of claim 10, wherein the parent-child relationship is a hierarchy including a single parent-multiple child relationship.

12. The method of claim 10, wherein the parent-child relationship is a directed acyclic graph including a multiple parent-multiple child relationship.

13. The method of claim 10, wherein the parent-child relationship is a graph including a multiple parent-multiple child relationship, the graph having cycles.

14. The method of claim 1, further comprising merging two or more indexes that correlate to attributes along an attribute path to form a single index.

15. The method of claim 14, wherein the two or more of the merged indexes are indexes of concept-to-concept relationships between different categories of concepts.

16. The method of claim 14, wherein one index of the merged indexes is connected to the other index through a plurality of concept-to-concept relationships defined by concept attributes of multiple categories.

17. The method of claim 14, wherein one index of the merged indexes is connected to the other index through an arbitrarily large number of concept-to-concept relationships defined by concept attributes of multiple categories.

18. The method of claim 1, further comprising dynamically updating each of the indexes, the updates including insertions or deletions.

19. The method of claim 1, wherein the executing further comprises using a combination of non-hierarchical, hierarchical, directed acyclic graph and graph inverted indexes constructed in a concept cube.

20. The method of claim 1, wherein the search is a fuzzy search of the semantic network of the knowledge base.

21. The method of claim 1, wherein executing further comprises using a plurality of indexes that index the concepts and the values.

22. The method of claim 1, wherein given a first set of concepts that refers to a second set of one or more values or concepts and given a referred value or concept from the second set, the index returns a set of concepts that referenced to that referred value or concept.

49. The method of claim 1, wherein executing a search further comprises executing a search using a) one or more transitive indexes that index transitive relationships from concepts in a first category through at least one second category to concepts in a third category.

50. The method of claim 1, wherein executing a search further comprises executing a search using b) one or more transitive closure indexes that index transitive closure relationships amongst concepts within a category.

51. The method of claim 1, wherein executing a search further comprises executing a search using a combination of both a) and b).

52. The method of claim 1, wherein executing a search further comprises executing a search using a combination of b) one or more transitive closure indexes that index transitive closure relationships amongst concepts within a category with c) one or more transitive indexes that index transitive relationships from concepts in a first category to concepts in a second category.

23. A computer program product having a computer-readable medium having computer program instructions recorded thereon for using indexes to search a knowledge base, the computer program instruction comprising instructions for:

accessing a knowledge base comprising a semantic network of relationships among concepts, each concept having a set of values associated with it, wherein each concept is an instance of a category and each value is an instance of an attribute and wherein categories and attributes form a knowledge base schema;

receiving, from a user searching for one or more target concepts, a query represented as criteria and criteria values that specify constraints on the categories and the attributes;

executing a search of the concepts and the values of the knowledge base to retrieve the one or more target concepts using indexes selected from a group consisting of;

a) one or more transitive indexes that index transitive relationships from concepts in a first category through at least one second category to concepts in a third category and b) one or more transitive closure indexes that index transitive closure relationships amongst concepts within a category; and

retrieving a result subset of the target concepts and the values that satisfies the criteria and criteria values.

24. The computer program product of claim 23, wherein the search is selected from a group consisting of:

a search for resumes of job applicants and a search for job descriptions.

25. The computer program product of claim 23, wherein at least one of the indexes is an attribute index of single concepts referring to a single value.

26. The computer program product of claim 23, wherein at least one of the indexes is an attribute index of single concepts referring to a set of multiple values.

27. The computer program product of claim 26, wherein at least one of the indexes is an attribute index of single concepts referring to two or more sets of multiple correlated values.

28. The computer program product of claim 27, wherein the single concepts refer to one or more sets of string values broken down into sets of sub-string values and integer values, the integer values comprising positions where the string values occur within a string.

29. The computer program product of claim 23, wherein at least one of the indexes is an attribute index of a concept referring to a single concept.

30. The computer program product of claim 23, wherein at least one of the indexes is an attribute index of a concept referring to a set of multiple concepts.

31. The computer program product of claim 23, wherein at least one of the indexes is an attribute index of a concept referring to a set of multiple concepts within the same category forming a parent-child relationship, the index comprising computing transitive closure along a specified direction in the parent-child relationship for indexing all reachable concepts moving in the specified direction given a specific concept in the category.

32. The computer program product of claim 31, wherein the parent-child relationship is a hierarchy including a single parent-multiple child relationship.

33. The computer program product of claim 31, wherein the parent-child relationship is a directed acyclic graph including a multiple parent-multiple child relationship.

34. The computer program product of claim 31, wherein the parent-child relationship is a graph including a multiple parent-multiple child relationship, the graph having cycles.

35. The computer program product of claim 23, further comprising merging two or more indexes that correlate to attributes along an attribute path to form a single index.

36. The computer program product of claim 35, wherein the two or more of the merged indexes are indexes of concept-to-concept relationships between different categories of concepts.

37. The computer program product of claim 35, wherein one index of the merged indexes is connected to the other index through an arbitrarily large number of concept-to-concept relationships defined by concept attributes of multiple categories.

38. The computer program product of claim 23, wherein the executing further comprises using a combination of non-hierarchical, hierarchical, directed acyclic graph and graph inverted indexes constructed in a concept cube.

39. The computer program product of claim 23, wherein given a first set of concepts that refers to a second set of one or more values or concepts and given a referred value or concept from the second set, the index returns a set of concepts that referenced to that referred value or concept.

40. A system for using indexes to search a knowledge base, the system comprising:

at least one computer system;

a computer-readable storage medium storing software modules for execution by the at least one computer system, the software modules comprising;

a knowledge base comprising a semantic network of relationships among concepts, each concept having a set of values associated with it, wherein each concept is an instance of a category and each value is an instance of an attribute and wherein categories and attributes form a knowledge base schema;

a search engine for receiving, from a user searching for one or more target concepts, a query represented as criteria and criteria values that specify constraints on the categories and the attributes;

a dynamic query and analytics engine for executing a search of the concepts and the values of the knowledge base to retrieve the one or more target concepts using indexes selected from a group consisting of;

a) one or more transitive indexes that index transitive relationships from concepts in a first category through at least one second category to concepts in a third category and b) one or more transitive closure indexes that index transitive closure relationships amongst concepts within a category; and

the search engine for retrieving a result subset of the target concepts and the values that satisfies the criteria and criteria values.

41. The system of claim 40, wherein the search is selected from a group consisting of:

a search for resumes of job applicants and a search for job descriptions.

42. The system of claim 40, further comprising a concept cube for:

building the index; and

dynamically updating the index.

43. The system of claim 40, wherein at least one of the indexes is an attribute index of single concepts referring to a single value.

44. The system of claim 40, wherein at least one of the indexes is an attribute index of single concepts referring to a set of multiple values.

45. The system of claim 44, wherein at least one of the indexes is an attribute index of single concepts referring to two or more sets of multiple correlated values.

46. The system of claim 40, wherein at least one of the indexes is an attribute index of a concept referring to a set of multiple concepts within the same category forming a parent-child relationship, the index comprising computing transitive closure along a specified direction in the parent-child relationship for indexing all reachable concepts moving in the specified direction given a specific concept in the category.

47. The system of claim 40, wherein two or more indexes that correlate to attributes along an attribute path are merged together to form a single index.

48. The system of claim 40, wherein given a first set of concepts that refers to a second set of one or more values or concepts and given a referred value or concept from the second set, the index returns a set of concepts that referenced to that referred value or concept.