Method and system for information retrieval with clustering

• US 20080133479A1
• Filed: 11/30/2006
• Published: 06/05/2008
• Est. Priority Date: 11/30/2006
• Status: Active Grant

• Current Assignee: Oracle OTC Subsidiary LLC (Oracle Corporation)
• Original Assignee: Endeca Technologies Incorporated (Oracle Corporation)
• Inventors: Tzanov, Velin K., Saji, Michael Y., Zelevinsky, Vladimir V., Knabe, Frederick C., Tunkelang, Daniel
• Granted Patent: US 8,676,802 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/3325 Reformulation based on results of preceding query
• CPC Class Codes: G06F 16/338 Presentation of query results
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification

Abstract

Methods and systems that enable searching with clustering in information access systems are described. The methods of clustering operate on a collection of materials wherein each item in the collection may be associated with one or more properties. An original subset of materials is selected from the collection and relevant properties associated with the subset of materials are clustered into property clusters. Each property cluster generally contains properties that are more similar to each other than to properties in a different property cluster. The property clusters can be used to respond to the query. A mapping function can be used to identify a set of materials that correspond to each property cluster based on the associations between individual items and properties. The property clusters can also be used for iterative query refinement.

Claims

1. A computer program product, residing on a computer-readable medium, for use in accessing information associated with a collection of items, the computer program product comprising instructions for causing a computer to:

access a plurality of items and a first plurality of properties, each item being associated with one or more properties from the first plurality of properties;

obtain an original result set of at least one item from the plurality of items in response to a search query;

identify a second plurality of properties from the first plurality of properties, wherein each of the second plurality of properties is associated with at least one item in the original result set;

group a third plurality of properties selected from the second plurality of properties into one or more clusters of properties by applying a similarity measure to assign more similar properties to the same cluster and less similar properties to distinct clusters, wherein at least one cluster includes two or more properties; and

provide a response to the search query including a representation of at least one cluster of the one or more clusters of properties.

2. The computer program product of claim 1, wherein the search query includes a free-text component.

3. The computer program product of claim 1, wherein the search query includes a selection from a plurality of options.

4. The computer program product of claim 1, further comprising instructions for causing a computer to identify, for a particular cluster of properties of the one or more clusters of properties, one or more corresponding items from the plurality of items that correspond to the particular cluster of properties according to a mapping function, and wherein the instructions for causing a computer to provide a response to the search query include instructions for including one or more corresponding items for the at least one cluster in the response.

5. The computer program product of claim 4, wherein the instructions for causing a computer to identify, for a particular cluster of properties of the one or more clusters of properties, one or more corresponding items include instructions for causing a computer to map items to the particular cluster according to a partial match technique.

6. The computer program product of claim 4, wherein the instructions for causing a computer to identify, for a particular cluster of properties of the one or more clusters of properties, one or more corresponding items include instructions for causing a computer to map items to the particular cluster according to a match-all technique.

7. The computer program product of claim 4, wherein the instructions for causing a computer to identify, for a particular cluster of properties of the one or more clusters of properties, one or more corresponding items include instructions for causing a computer to map items to the particular cluster according to a match-any technique.

8. The computer program product of claim 4, wherein applying the mapping function is restricted to the items in the original result set.

9. The computer program product of claim 4, wherein the instructions for causing a computer to identify, for a particular cluster of properties of the one or more clusters of properties, one or more corresponding items include instructions for causing a computer to translate the particular cluster to a search expression that satisfies the mapping function.

10. The computer program product of claim 1, wherein the first plurality of properties are associated with the plurality of items and stored beforehand.

11. The computer program product of claim 1, wherein the first plurality of properties are associated with plurality of items at the time the search query is executed.

12. The computer program product of claim 1, wherein the items are documents that include text and the properties include salient terms extracted from the text.

13. The computer program product of claim 1, wherein the instructions for causing a computer to identify a second plurality of properties include instructions for causing a computer to compute the union of all properties that are associated with at least one item in the original result set.

14. The computer program product of claim 1, wherein the instructions for causing a computer to identify a second plurality of properties include instructions for causing a computer to compute the union of all properties that are associated with at least a threshold number of items in the original result set.

15. The computer program product of claim 1, wherein the instructions for causing a computer to identify a second plurality of properties include instructions for causing a computer to compute the union of all properties that are associated with at most a ceiling number of items in the original result set.

16. The computer program product of claim 1, wherein the instructions for causing a computer to identify a second plurality of properties include instructions for causing a computer to sample the original result set.

17. The computer program product of claim 1, wherein the instructions for causing a computer to group the third plurality of properties into one or more clusters of properties include instructions for causing a computer to use a pair-wise similarity measure.

18. The computer program product of claim 17, wherein the instructions for causing a computer to group the third plurality of properties into one or more clusters of properties include instructions for causing a computer to, for each pair of properties in the third plurality of properties, compute a number of items associated with both properties.

19. The computer program product of claim 17, wherein the instructions for causing a computer to group the third plurality of properties into one or more clusters of properties include instructions for causing a computer to, for each pair of properties in the third plurality of properties, compute a number of items associated with both properties relative to a number of items associated with at least one of the properties.

20. The computer program product of claim 17, wherein the instructions for causing a computer to group the third plurality of properties into one or more clusters of properties include instructions for causing a computer to, for each pair of properties in the third plurality of relevant properties, compute a number of items associated with both properties relative to a number of items associated with a more frequent property of the two properties.

21. The computer program product of claim 1, further comprising instructions for causing a computer to present at least one option for using one or more particular clusters from the one or more clusters to generate a second search query.

22. The computer program product of claim 21, wherein the at least one option includes combining the search query with at least one of the one or more particular clusters.

23. The computer program product of claim 22, wherein the at least one option includes conjunctively combining the search query with at least one of the one or more particular clusters.

24. The computer program product of claim 22, wherein the at least one option includes disjunctively combining the search query with at least one of the one or more the particular clusters.

25. The computer program product of claim 21, wherein the at least one option includes a lateral query formed from at least one of the one or more particular clusters without using the search query.

26. The computer program product of claim 21, further comprising instructions for causing a computer to accept a selection of one option for using one or more particular clusters to generate a second search query, and to execute the second search query.

27. The computer program product of claim 1, further comprising instructions for causing a computer to translate a particular cluster of the one or more clusters into a search expression.

28. The computer program product of claim 27, wherein the search expression matches all of the properties in the particular cluster.

29. The computer program product of claim 27, wherein the search expression matches at least one of the properties in the particular cluster.

30. The computer program product of claim 27, wherein the search expression matches at least one but not all of the properties in the particular cluster.

31. The computer program product of claim 27, wherein the search expression assigns relative weights to the properties in the particular cluster.

32. The computer program product of claim 1, wherein the third plurality of properties includes fewer properties than the second plurality of properties.

33. A computer-implemented method for accessing information associated with a database including a plurality of items and a first plurality of properties, each item being associated with one or more properties from the first plurality of properties, comprising:

obtaining a result set of items from the plurality of items for the search query;

identifying a second plurality of properties from the plurality of properties, wherein each property in the second plurality of properties is associated with at least one item in the result set;

grouping a third plurality of properties selected from the second plurality of properties into one or more clusters of properties by applying a similarity measure to assign more similar properties to the same cluster and less similar properties to distinct clusters, wherein at least one cluster includes two or more properties; and

providing a response to the search query including at least one cluster of properties.

34. The method of claim 33, wherein the search query includes a free-text component.

35. The method of claim 33, wherein the search query includes a selection from a plurality of options.

36. The method of claim 33, further comprising identifying for the at least one cluster of properties one or more corresponding items from the plurality of items that correspond to the particular cluster of properties according to a mapping function and including one or more corresponding items for the at least one cluster in the response.

37. The method of claim 36, wherein identifying for the at least one cluster of properties one or more corresponding items includes mapping items to the at least one cluster according to a partial match technique.

38. The method of claim 36, wherein identifying for the at least one cluster of properties one or more corresponding items includes mapping items to the at least one cluster according to a match-all technique.

39. The method of claim 36, wherein identifying for the at least one cluster of properties one or more corresponding items includes mapping items to the at least one cluster according to a match-any technique.

40. The method of claim 36, wherein applying the mapping function is restricted to the items in the original result set.

41. The method of claim 36, wherein identifying for the at least one cluster of properties one or more corresponding items includes translating the at least one cluster to a search expression that satisfies the mapping function.

42. The method of claim 33, wherein the first plurality of properties are associated with the plurality of items and stored beforehand.

43. The method of claim 33, wherein the first plurality of properties are associated at the time the search query is executed.

44. The method of claim 33, wherein the items are documents that include text and the properties include salient terms extracted from the text.

45. The method of claim 33, wherein identifying a second plurality of properties includes computing the union of all properties that are associated with at least one item in the original result set.

46. The method of claim 33, wherein identifying a second plurality of properties includes computing the union of all properties that are associated with at least a threshold number of items in the original result set.

47. The method of claim 33, wherein identifying a second plurality of properties includes computing the union of all properties that are associated with at most a ceiling number of items in the original result set.

48. The method of claim 33, wherein identifying a second plurality of properties includes sampling the original result set.

49. The method of claim 33, wherein grouping the third plurality of properties into one or more clusters of properties includes using a pair-wise similarity measure.

50. The method of claim 49, wherein grouping the third plurality of properties into one or more clusters of properties includes, for each pair of properties in the third plurality of properties, computing a number of items associated with both properties.

51. The method of claim 49, wherein grouping the third plurality of properties into one or more clusters of properties includes, for each pair of properties in the third plurality of properties, computing a number of items associated with both properties relative to a number of items associated with at least one of the properties.

52. The method of claim 49, wherein grouping the third plurality of properties into one or more clusters of properties includes, for each pair of properties in the third plurality of properties, computing a number of items associated with both properties relative to a number of items associated with a more frequent property of the two properties.

53. The method of claim 33, further comprising presenting at least one option for using one or more particular clusters from the one or more clusters to generate a second search query.

54. The method of claim 53, wherein the at least one option includes combining the search query with at least one of the one or more particular clusters.

55. The method of claim 54, wherein the at least one option includes conjunctively combining the search query with at least one of the one or more particular clusters.

56. The method of claim 54, wherein the at least one option includes disjunctively combining the search query with at least one of the one or more the particular clusters.

57. The method of claim 53, wherein the at least one option includes a lateral query formed from at least one of the one or more particular clusters without using the search query.

58. The method of claim 53, further comprising accepting a selection of one option for using one or more particular clusters to generate a second search query, and executing the second search query.

59. The method of claim 58, further comprising translating at least one cluster of the one or more particular clusters into a search expression to generate the second search query.

60. The method of claim 59, wherein the search expression matches all of the properties in the at least one cluster of the one or more particular clusters.

61. The method of claim 59, wherein the search expression matches at least one of the properties in the at least one cluster of the one or more particular clusters.

62. The method of claim 59, wherein the search expression matches at least one but not all of the properties in the at least one cluster of the one or more particular clusters.

63. The method of claim 59, wherein the search expression assigns relative weights to the properties in the at least one cluster of the one or more particular clusters.

64. The method of claim 33, wherein the third plurality of properties includes fewer properties than the second plurality of properties.

65. A computer program product, residing on a computer-readable medium, for use in accessing information associated with a collection of items, the computer program product comprising instructions for causing a computer to:

access a plurality of items and a first plurality of properties, wherein the properties are information-bearing values, each item being associated with one or more properties from the first plurality of properties, wherein the one or more properties associated with a item are contained in or describe the item;

obtain an original result set of at least one item from the plurality of items in response to a search query;

identify a second plurality of properties from the first plurality of properties, wherein each of the second plurality of properties is associated with at least one item in the original result set;

group a third plurality of properties selected from the second plurality of properties into one or more clusters of properties by applying a similarity measure to assign more similar properties to the same cluster and less similar properties to distinct clusters, wherein at least one cluster includes two or more properties; and

provide a response to the search query including a representation of at least one cluster of the one or more clusters of properties.

66. An information access system, comprising:

a first stored collection including a plurality of materials;

a second stored collection including a first plurality of properties, wherein each item in the plurality of materials is associated with at least one property from the first plurality of properties;

logic to perform a search against the first stored collection to obtain a result set of materials from the collection that match the search query;

logic to derive a second plurality of properties from the second stored collection wherein each property in the second plurality of properties is associated with at least one item in the result set;

logic to group a third plurality of properties into one or more clusters of properties by applying a similarity measure to assign more similar properties to the same cluster and less similar properties to distinct clusters, wherein at least one cluster includes two or more properties; and

logic to provide a response to the search query including at least one cluster of the one or more clusters of properties.