Systems and methods for search processing using superunits

• US 20050080795A1
• Filed: 03/09/2004
• Published: 04/14/2005
• Est. Priority Date: 10/09/2003
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Joshi, Deepa, Parikh, Jignashu, Kapur, Shyam
• Granted Patent: US 7,346,629 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9532 Query formulation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

In a search processing system, a concept network is generated from a set of queries by parsing the queries into units and defining various relationships between the units based in part on patterns of units that appear together in queries. Units in the concept network that have some similar characteristic(s) are grouped into superunits. For each superunit, there is a corresponding signature that defines the similar characteristic of the group. A query is processed by identifying constituent units, determining the superunit membership of some or all of the constituent units, and using that information to formulate a response to the query.

Claims

1. A computer-implemented method for generating superunits from a concept network, the concept network including a plurality of units and a plurality of relationships defined between pairs of the plurality of units, wherein each relationship has an associated edge weight, the method comprising the acts of:

identifying a superunit seed comprising at least one member unit, wherein each member unit is one of the plurality of units of the concept network;

defining a signature for the superunit seed, the signature including one or more signature units, wherein each signature unit has a relationship in the concept network with at least a minimum number of the member units;

expanding the superunit seed by adding one or more new member units from the concept network, wherein each new member unit satisfies a match criterion based on the signature;

modifying the signature based on the expanded superunit seed;

repeating the acts of expanding and modifying until a convergence criterion is satisfied, wherein a final superunit and a final signature are formed once the convergence criterion is satisfied; and

storing superunit membership information for each member unit of the final superunit.

2. The method of claim 1, wherein the concept network is generated from a set of previous search queries.

3. The method of claim 1, wherein the act of storing the superunit membership information includes the acts of:

computing a membership weight for each member unit of the final superunit, wherein the membership weight is based on the relationships in the concept network between the member unit and the signature units of the final signature,

wherein the stored superunit membership information includes the membership weight.

4. The method of claim 1, further comprising the act of generating the concept network from the previous queries.

5. The method of claim 1, further comprising the acts of:

subsequently to the act of modifying the signature and prior to the step of repeating, purging the superunit seed by removing a member unit that does not satisfy the match criterion based on the modified signature,

wherein the act of purging is repeated subsequently to repeating the step of modifying.

6. The method of claim 1, wherein the convergence criterion is satisfied if, as a result of the act of repeating, membership of the superunit seed changes by no more than a maximum number of units.

7. The method of claim 1, wherein the convergence criterion is satisfied if, as a result of the act of repeating, membership of the signature changes by no more than a maximum number of units.

8. The method of claim 1, wherein the act of identifying the superunit seed includes the act of forming a cluster of two or more units as the superunit seed, wherein each unit in the cluster has at least one neighbor unit in common with a base unit of the cluster.

9. The method of claim 8, wherein the act of forming the cluster includes the acts of:

selecting a base unit and a candidate unit from the concept network;

identifying a plurality of neighbor units of the base unit, wherein each neighbor unit has a relationship in the concept network to the base unit;

identifying at least one of the neighbor units as a matched unit, wherein each matched unit has a relationship in the concept network to the candidate unit;

computing a clustering weight for the candidate unit based on the plurality of neighbor units including the at least one matched unit; and

based on the clustering weight, determining whether to include the candidate unit in a cluster with the base unit.

10. The method of claim 1, wherein the act of identifying the superunit seed includes forming a clique of two or more closely related units.

11. The method of claim 1, wherein the act of identifying the superunit seed includes the act of receiving a list of units from an external source, the list of units being usable as a superunit seed.

12. The method of claim 11, wherein the external source comprises a web page.

13. The method of claim 11, wherein the act of identifying the superunit seed further includes the act of pruning the list of units to remove a unit that is not in the concept network.

14. The method of claim 1, wherein the act of identifying the superunit seed includes the acts of:

receiving user behavior data related to the previous queries; and

detecting similarities in the user behavior data related to previous queries containing different units.

15. The method of claim 14, wherein the user behavior data includes click through information for the previous queries.

16. The method of claim 1, wherein the act of identifying the superunit seed includes the acts of:

detecting occurrences of units of the concept network in a source document; and

generating a superunit seed based on the detected occurrences.

17. The method of claim 1, wherein the relationships between the units of the concept network include one or more of an association relationship, an extension relationship, and an alternative relationship.

18. The method of claim 1, wherein the act of defining the signature includes the acts of:

identifying as the signature units a plurality of units in the concept network that have a specified relationship with at least a minimum number of the member units of the associated superunit seed; and

establishing a threshold number,

wherein the step of expanding the superunit seed includes;

selecting a candidate unit from the concept network; and

adding the candidate unit to the superunit seed in the event that the candidate unit has the specified relationship with at least the threshold number of the signature units.

19. The method of claim 18, wherein the threshold number is established relative to a total number of signature units by reference to a predetermined fraction.

20. The method of claim 1, wherein defining the signature includes the acts of:

identifying as the signature units a plurality of units in the concept network that have a specified relationship with at least a minimum number of the member units of the associated superunit seed;

establishing an edge weight range for each signature unit; and

establishing a threshold number,

wherein the step of expanding the superunit seed includes;

selecting a candidate unit from the concept network;

determining a first number equal to a number of the signature units with which the candidate unit has the specified relationship and has an edge weight within the edge weight range for that signature unit; and

adding the candidate unit to the superunit seed in the event that the first number is equal to or greater than the threshold number.

21. The method of claim 1, further comprising, subsequently to the act of storing, the acts of:

receiving a current query;

parsing the current query into one or more constituent units;

retrieving the stored superunit membership information for one or more of the constituent units; and

formulating a response to the current query based at least in part on the retrieved superunit membership information.

22. The method of claim 21, wherein the act of formulating the response includes the act of using the superunit membership information to suggest a related search query.

23. The method of claim 22, wherein the related search query includes a first unit that is one of the member units of the superunit, wherein the first unit is not a constituent unit of the current query.

24. The method of claim 22, wherein the related search query includes a first unit that is one of the signature units of the superunit, wherein the first unit is not a constituent unit of the current query.

25. The method of claim 21, wherein the act of formulating the response includes the act of using the superunit membership information to suggest a web site for a sideways search.

26. The method of claim 21, wherein one of the constituent units is a member of more than one superunit and wherein the act of formulating the response includes the act of using the superunit membership information to group response data according to the superunits to which the one of the constituent units belongs.

27. The method of claim 21, wherein the act of formulating the response includes the act of using the superunit information to resolve an ambiguity of a first one of the constituent units based on comparing another of the constituent units to signature units for one or more superunits of which the first constituent unit is a member.

28. The method of claim 21, wherein the act of formulating the response includes the act of using the superunit information to select sponsored content to be displayed.

29. A system for generating superunits from user search queries, the system comprising:

a concept network builder module configured to generate a concept network from a plurality of previous queries, the concept network including a plurality of units and a plurality of relationships defined between pairs of the plurality of units, wherein each relationship has an associated edge weight;

a superunit seed module configured to identify a superunit seed comprising at least one member unit, wherein each member unit is one of the plurality of units of the concept network;

a superunit builder module configured to construct superunits and signatures starting with the superunit seeds, wherein each superunit includes a plurality of member units and wherein each signature is associated with one of the superunits, wherein each signature includes one or more signature units, wherein each signature unit has a relationship in the concept network with at least a minimum number of the member units of the associated superunit; and

a storage module configured to store superunit membership information for the member units, wherein the superunit membership information is provided by the superunit builder module.

30. The system of claim 29, wherein the superunit builder module is further configured to define a signature for each superunit seed, to expand the superunit seed by adding one or more new member units from the concept network, wherein each new member unit satisfies a match criterion based on the signature, to modify the signature based on the expanded superunit seed, and to repeat the steps of expanding and modifying until a convergence criterion is satisfied, wherein a final superunit and a final signature are formed once the convergence criterion is satisfied.

31. The system of claim 30, wherein the superunit builder module is further configured to compute a membership weight for each member unit of the final superunit, wherein the membership weight is based on the relationships in the concept network between the member unit and the signature units of the final signature, and to store the membership weight in the storage module.

32. The system of claim 30, wherein the convergence criterion is satisfied if, during the repetition, membership of the superunit seed changes by less than a maximum number of units.

33. The system of claim 30, wherein the convergence criterion is satisfied if, during the repetition, membership of the signature changes by less than a maximum number of units.

34. The system of claim 29, wherein the superunit seed module is further configured to identify a cluster of two or more units as the superunit seed, wherein each unit in the cluster has at least one neighbor unit in common.

35. The system of claim 34, wherein the superunit seed module is further configured to select at least two candidate units from the concept network, to identify a plurality of neighbor units of the candidate units, wherein each neighbor unit has a relationship in the concept network to one or more of the candidate units, to compute a clustering weight for the candidate units based on the plurality of neighbor units, and to determine, based on the clustering weight, whether to form a cluster from the candidate units.

36. The system of claim 34, wherein the superunit seed module is further configured to receive a list of units from an external source, the list of units being usable as a superunit seed.

37. The system of claim 34, wherein the superunit seed module is further configured to receive user behavior data related to the previous queries and to detect similarities in the user behavior data related to previous queries containing different units.

38. The system of claim 34, wherein the superunit seed module is further configured to detect occurrences of units of the concept network in a source document and to generate a superunit seed based on the detected occurrences.

39. The system of claim 29, further comprising:

a query response module coupled to the storage module and configured to receive a current query, to parse the current query into one or more constituent units, to retrieve from the storage module the superunit membership information for one or more of the constituent units, and to formulate a response to the current query based at least in part on the retrieved superunit membership information.

40. A computer program product comprising a computer readable medium encoded with program code, the program code including:

program code for identifying a superunit seed comprising at least one member unit, wherein each member unit is one of a plurality of units of a concept network, the concept network including a plurality of units and a plurality of relationships defined between pairs of the plurality of units, wherein each relationship has an associated edge weight;

program code for defining a signature for the superunit seed, the signature including one or more signature units, wherein each signature unit has a relationship in the concept network with at least a minimum number of the member units;

program code for expanding the superunit seed by adding one or more new member units from the concept network, wherein each new member unit satisfies a match criterion based on the signature;

program code for modifying the signature based on the expanded superunit seed;

program code for repeating the steps of expanding and modifying until a convergence criterion is satisfied, wherein a final superunit and a final signature are formed once the convergence criterion is satisfied; and

program code for storing superunit membership information for each member unit of the final superunit.

41. The computer program product of claim 40, wherein the program code further includes:

program code for receiving a current query;

program code for parsing the current query into one or more constituent units;

program code for retrieving the stored superunit membership information for one or more of the constituent units; and

program code for formulating a response to the current query based at least in part on the retrieved superunit membership information.

42. A computer-implemented method for forming a cluster from a concept network, the concept network including a plurality of units and a plurality of relationships defined between the units, wherein each relationship has a associated edge weight, the method comprising the acts of:

selecting a base unit and a candidate unit from the concept network;

identifying a plurality of neighbor units of the base unit, wherein each neighbor unit has a relationship in the concept network to the base unit;

identifying at least one of the neighbor units as a matched unit, wherein the matched unit has a relationship in the concept network to the candidate unit;

computing a clustering weight for the candidate unit based on the plurality of neighbor units including the at least one matched unit; and

based on the clustering weight, determining whether to include the candidate unit in a cluster with the base unit.

43. The method of claim 42, further comprising the acts of:

selecting a second candidate unit; and

using the second candidate unit repeating the acts of identifying at least one of the neighbor units as a matched unit, computing a clustering weight, and determining, thereby determining whether to include the second candidate unit in the cluster.

44. A computer-implemented method for forming a clique from a concept network, the concept network including a plurality of units and a plurality of relationships defined between the units, wherein each relationship has an associated edge weight, the method comprising the acts of:

forming a plurality of clusters, wherein each cluster includes at least a base unit;

selecting one of the plurality of clusters as a starting cluster;

initializing a clique to include only the base unit of the starting cluster; and

for each member unit u of the starting cluster, adding the member unit u to the clique in the event that;

(a) the fraction of current members of the clique that are also members of the one of the clusters that has member unit u as the base unit is equal to or greater than a first threshold value; and

(b) the fraction of clusters having current clique members as base units that also include member unit u is equal to or greater than a second threshold value.

45. The method of claim 44, wherein the first threshold value and the second threshold value are each equal to 100%.

46. The method of claim 44, wherein the first threshold value and the second threshold value are each equal to about 70%.