Structured relevance—a mechanism to reveal how data is related
View Patent ↗A machine receives a description of the relationships among members of a data set. The machine constructs a graph that represents the relationships among the members of the data set, organizing the members of the data set into groups. The groups are analyzed to determine their relative strengths. Unbalanced groups can be balanced by splitting off heavy sub-trees that include too large a percentage of the nodes in the group. The machine can then use the graph to answer queries about members of the data set.
1. An apparatus, comprising:
a machine;
an input port to receive a description of relationships among a plurality of members of a data set and to receive a query;
a graph constructor to construct a graph representing said relationships among said plurality of members of said data set; and
a query results module to use said graph representing said relationships among said plurality of members of said data set to group together possible results of said query and the query results module produces query results and identifies a particular data set to which a best member for responding to the query belongs, the best member includes a best member identifier and a group identifier that identifies a particular group to which the best member belongs, the particular group including particular members that are positioned as more responsive to the query than other members of the data set belonging to other groups and the particular group is given a strength that includes its order, weight, and distance compared to other groups, the order includes a total number of nodes in that particular group, the weight is a depth of a deepest sub-tree in that particular group, and the distance is a geometric average from each node within the particular group to that node's nearest neighboring node within the particular group.
2. An apparatus according to claim 1 , wherein the graph constructor is configured to identify, for each member of said data set, a nearest neighbor of that member of said data set.
3. An apparatus according to claim 1 , wherein the graph constructor is configured to allocate each member of said data set to a group.
4. An apparatus according to claim 3 , wherein the query results module includes:
the best member identifier to identify a member of said data set that best satisfies said query;
the group identifier to identify a group to which said member of said data set that best satisfies said query belongs; and
the query results module is configured to return said member of said data set that best satisfies the query and at least one other member of said group to which said member of said data set that best satisfies said query belongs.
5. An apparatus according to claim 4 , wherein the query results module is configured to return said at least one other member of said group to which said member of said data set that best satisfies said query belongs sorted by a distance between said at least one other member and said member of said data set that best satisfies said query.
6. An apparatus according to claim 3 , further comprising a group balance determiner to determine whether said group is balanced.
7. An apparatus according to claim 6 , further comprising a heavy sub-tree splitter to determine that a heavy sub-tree of said group includes a threshold percentage of a total number of nodes in said group and to split said heavy sub-tree off said core of said group.
8. A method for organizing data, comprising:
using a processor, identifying a plurality of members of a data set;
identifying relationships among the plurality of members of the data set from the plurality of members of the data set; and
constructing a graph representing the relationships among the plurality of members of the data set and producing results for a particular query that identifies a particular data set having a particular member that best satisfies the particular query the particular member includes a best member identifier and a group identifier that identifies a particular group to which the particular member belongs, the particular group including particular members that are positioned as more responsive to the particular query than other members of the data set belonging to other groups and the particular group is given a strength that includes its order, weight, and distance compared to other groups, the order includes a total number of nodes in that particular group, the weight is a depth of a deepest sub-tree in that particular group, and the distance is a geometric average from each node within the particular group to that node's nearest neighboring node within the particular group.
9. A method according to claim 8 , further comprising using the graph representing the relationships among the plurality of members of the data set to identify possible results of a query.
10. A method according to claim 9 , wherein identifying relationships among the plurality of members of the data set includes identifying, for each member of the data set, a nearest neighbor of that member of the data set.
11. A method according to claim 10 , wherein identifying, for each member of the data set, another member of the data set that is its nearest neighbor includes identifying, for each member of the data set, the distance between that member of the data set and its nearest neighbor.
12. A method according to claim 9 , wherein constructing a graph representing the relationships among the plurality of members of the data set includes allocating each member of the data set to a group.
13. An article comprising a non-transitory storage medium, said non-transitory storage medium having stored thereon instructions, that, when executed by a machine, result in:
using a processor, identifying a plurality of members of a data set;
identifying relationships among the plurality of members of the data set from the plurality of members of the data set; and
constructing a graph representing the relationships among the plurality of members of the data set and producing results for a particular query that identifies a particular data set having a particular member that best satisfies the particular query, the particular member includes a best member identifier and a group identifier that identifies a particular group to which the particular member belongs, the particular group including particular members that are positioned as more responsive to the particular query than other members of the data set belonging to other groups and the particular group is given a strength that includes its order, weight, and distance compared to other groups, the order includes a total number of nodes in that particular group, the weight is a depth of a deepest sub-tree in that particular group, and the distance is a geometric average from each node within the particular group to that node's nearest neighboring node within the particular group.
14. An article according to claim 13 , said non-transitory storage medium having stored thereon further instructions, that, when executed by the machine, result in using the graph representing the relationships among the plurality of members of the data set to identify possible results of a query.
15. An article according to claim 14 , wherein identifying relationships among the plurality of members of the data set includes identifying, for each member of the data set, a nearest neighbor of that member of the data set.
16. An article according to claim 14 , wherein constructing a graph representing the relationships among the plurality of members of the data set includes allocating each member of the data set to a group.