Systems and methods for search processing using superunits
First Claim
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.
9 Assignments
0 Petitions
Accused Products
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.
-
Citations
46 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28)
-
-
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. - View Dependent Claims (30, 31, 32, 33, 34, 35, 36, 37, 38, 39)
-
-
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. - View Dependent Claims (41)
-
-
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. - View Dependent Claims (43)
-
-
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. - View Dependent Claims (45, 46)
-
Specification