Using a graph database to match entities by evaluating boolean expressions

• US 9,390,195 B2
• Filed: 01/02/2013
• Issued: 07/12/2016
• Est. Priority Date: 01/02/2013
• Status: Active Grant

• Current Assignee: Research Now Group LLC
• Original Assignee: Research Now Group, Inc (Dynata)
• Inventors: Harter, James Sterling Shapiro, Herfield, Eric Steven, Stuart, Nicholas Alexander, Lee, Nien-Chung
• Primary Examiner(s): Ruiz, Angelica
• Application Number:
  US13/733,069
• Publication Number:
  US 20140188941A1
• Time in Patent Office: 1,287 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2458 Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries
• CPC Class Codes: G06F 16/28 Databases characterised by their database models, e.g. relational or object models
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A method of matching a first entity to a second entity by evaluating Boolean expressions includes identifying a set of criteria vertices for a second entity vertex by traversing a graph database in a manner constrained to fact vertices identified for the second entity. The graph database relates fact vertices to the criteria vertices by edges corresponding to Boolean expressions for satisfying criteria for matching first entities to second entities. The method additionally includes selecting one of the first entities based on the criteria vertices of the set. The method further includes matching the first entity to the second entity based on the selection.

Claims

1. A method of matching a first entity to a second entity by evaluating Boolean expressions, the method comprising:

identifying one or more fact vertices for the second entity;

generating a first set of criteria vertices by traversing a graph database constrained to the fact vertices identified for the second entity,

wherein the graph database relates fact vertices to criteria vertices by edges corresponding to a Boolean expression for matching the first entity to the second entity; and

for a first criteria vertex in the first set of criteria vertices;

determining whether the first criteria vertex matches a first fact vertex among the fact vertices identified for the second entity,

in response to determining the first criteria vertex matches the first fact vertex, assembling a second set of criteria vertices by adding the first criteria vertex to the second set of criteria vertices, or in response to determining the first criteria vertex does not match a fact vertex among the fact vertices identified for the second entity, retaining the second set of criteria vertices,

determining whether the second set of criteria vertices completes the Boolean expression, and

in response to determining the second set of criteria vertices completes the Boolean expression, completing the assembly of the second set of criteria vertices, or in response to determining the second set of criteria vertices does not complete the Boolean expression, processing a second criteria vertex in the first set of criteria vertices,

wherein completion of an include criteria of the Boolean expression is determined separately from completion of an exclude criteria of the Boolean expression.

2. The method of claim 1, wherein the first entity corresponds to a market research project, the second entity corresponds to a panelist, the fact vertices correspond to profile parameter vertices representing profile parameter values identified for the panelist, and the criteria vertices represent quota cells of market research projects.

3. The method of claim 2, wherein identifying a set of quota cells includes traversing edges of the graph database from a panelist vertex to all profile parameter value vertices of the graph database representing profile parameter values that have been identified for a panelist represented by the panelist vertex.

4. The method of claim 3, wherein identifying the set of quota cells further includes traversing the graph database to identify a set of quota cell vertices each having at least one includes type of edge that encounters at least one of the profile parameter value vertices identified for the panelist, and that do not have at least one excludes type of edge that encounters at least one of the profile parameter value vertices identified for the panelist.

5. The method of claim 4, wherein identifying the set of quota cells further comprises determining an incomplete match to a quota cell in response to an edge of the quota cell vertex for the quota cell encountering a profile parameter value vertex representing a value of a profile parameter that is not determined for the panelist.

6. The method of claim 5, further comprising eliminating all quota cells from the set that belong only to projects having at least one quota group not matched to at least one of the identified quota cells.

7. The method of claim 5, further comprising:

determining whether matches are complete for each quota cell of the set associated with the project and, if not, obtaining additional information from the panelist with respect to each of the incompletely matched quota cells and determining whether a fit exists based on the additional information; and

responding to a determination that a fit does not exist by eliminating all quota cells from the set that are associated with the incompletely matched project, and selecting another one of the quota cells of the set.

8. The method of claim 2, wherein selecting one of the quota cells further comprises selecting one of the quota cells from the set at random.

9. The method of claim 8, wherein selecting one of the quota cells at random further comprises weighting random selection of the quota cells according to priorities assigned to the quota cells.

10. The method of claim 9, wherein the priorities are calculated as a function of percentage of progress of the project, elapsed effective field time for completion of the project, and scarcity of the quota cell criteria.

11. The method of claim 9, wherein weighting random selection of the quota cells according to priorities assigned to the quota cells includes:

associating the quota cells with segments of a segmented bell curve based on the priorities;

randomly selecting a segment of the bell curve, wherein a segment associated with quota cells of higher priority than those of another segment has a greater chance of being selected than the other segment; and

randomly selecting a quota cell of the selected segment of the bell curve.

12. An apparatus for matching a first entity to a second entity by evaluating Boolean expressions, the apparatus comprising:

means for identifying one or more fact vertices for the second entity;

means for generating a first set of criteria vertices by traversing a graph database constrained to the fact vertices identified for the second entity,

wherein the graph database relates fact vertices to criteria vertices by edges corresponding to a Boolean expression for matching the first entity to the second entity; and

for a first criteria vertex in the first set of criteria vertices;

means for determining whether the first criteria vertex matches a first fact vertex among the fact vertices identified for the second entity,

in response to determining the first criteria vertex matches the first fact vertex, means for assembling a second set of criteria vertices by adding the first criteria vertex to the second set of criteria vertices, or in response to determining the first criteria vertex does not match a fact vertex among the fact vertices identified for the second entity, means for retaining the second set of criteria vertices,

means for determining whether the second set of criteria vertices completes the Boolean expression, and

in response to determining the second set of criteria vertices completes the Boolean expression, means for completing the assembly of the second set of criteria vertices, or in response to determining the second set of criteria vertices does not complete the Boolean expression, means for processing a second criteria vertex in the first set of criteria vertices,

wherein completion of an include criteria of the Boolean expression is determined separately from completion of an exclude criteria of the Boolean expression.

13. The apparatus of claim 12, wherein the first entity corresponds to a market research project, the second entity corresponds to a panelist, the fact vertices correspond to profile parameter vertices representing profile parameter values identified for the panelist, and the criteria vertices represent quota cells of market research projects.

14. The apparatus of claim 13, wherein a means for identifying a set of quota cells includes means for traversing edges of the graph database from a panelist vertex to all profile parameter value vertices of the graph database representing profile parameter values that have been identified for a panelist represented by the panelist vertex.

15. The apparatus of claim 14, wherein the means for identifying the set of quota cells further includes means for traversing the graph database to identify a set of the quota cell vertices each having at least one includes type of edge that encounters at least one of the profile parameter value vertices identified for the panelist, and that do not have at least one excludes type of edge that encounters at least one of the profile parameter value vertices identified for the panelist.

16. The apparatus of claim 15, wherein the means for identifying the set of quota cells further comprises means for determining an incomplete match to a quota cell in response to an edge of a quota cell vertex for the quota cell encountering a profile parameter value vertex representing a value of a profile parameter that is not determined for the panelist.

17. The apparatus of claim 16, further comprising means for eliminating all quota cells from the set that belong only to projects having at least one quota group not matched to at least one of the identified quota cells.

18. The apparatus of claim 16, further comprising:

means for determining whether matches are complete for each quota cell of the set associated with the project and, if not, obtaining additional information from the panelist with respect to each of the incompletely matched quota cells and determining whether a fit exists based on the additional information; and

means for responding to a determination that a fit does not exist by eliminating all quota cells from the set that are associated with the incompletely matched project, and selecting another one of the quota cells of the set.

19. The apparatus of claim 13, wherein a means for selecting one of the quota cells comprises means for selecting one of the quota cells from the set at random.

20. The apparatus of claim 19, wherein the means for selecting one of the quota cells from the set at random further comprises means for weighting random selection of the quota cells according to priorities assigned to the quota cells.

21. The apparatus of claim 20, further comprising means for assigning the priorities based on percentage of progress of the project, elapsed effective field time for completion of the project, and scarcity of the quota cell criteria.

22. The apparatus of claim 20, wherein the means for weighting random selection of the quota cells according to priorities assigned to the quota cells includes:

means for associating the quota cells with segments of a segmented bell curve based on the priorities;

means for randomly selecting a segment of the bell curve, wherein a segment associated with quota cells of higher priority than those of another segment has a greater chance of being selected than the other segment; and

means for randomly selecting a quota cell of the selected segment of the bell curve.

23. A computer program product, comprising:

a non-transitory computer-readable medium, comprising;

code for identifying one or more fact vertices for the second entity;

code for generating a first set of criteria vertices by traversing a graph database constrained to the fact vertices identified for the second entity,

wherein the graph database relates fact vertices to criteria vertices by edges corresponding to a Boolean expression for matching the first entity to the second entity; and

for a first criteria vertex in the first set of criteria vertices;

code for determining whether the first criteria vertex matches a first fact vertex among the fact vertices identified for the second entity,

in response to determining the first criteria vertex matches the first fact vertex, code for assembling a second set of criteria vertices by adding the first criteria vertex to the second set of criteria vertices, or in response to determining the first criteria vertex does not match a fact vertex among the fact vertices identified for the second entity, code for retaining the second set of criteria vertices,

code for determining whether the second set of criteria vertices completes the Boolean expression, and

in response to determining the second set of criteria vertices completes the Boolean expression, code for completing the assembly of the second set of criteria vertices, or in response to determining the second set of criteria vertices does not complete the Boolean expression, code for processing a second criteria vertex in the first set of criteria vertices,

wherein completion of an include criteria of the Boolean expression is determined separately from completion of an exclude criteria of the Boolean expression.

24. The computer program product of claim 23, wherein the first entity corresponds to a market research project, the second entity corresponds to a panelist, the fact vertices correspond to profile parameter vertices representing profile parameter values identified for the panelist, and the criteria vertices represent quota cells of market research projects.

25. The computer program product of claim 24, wherein a code for identifying a set of quota cells includes code for traversing edges of the graph database from a panelist vertex to all profile parameter value vertices of the graph database representing profile parameter values that have been identified for a panelist represented by the panelist vertex.

26. The computer program product of claim 25, wherein the code for identifying the set of quota cells further includes code for traversing the graph database to identify a set of the quota cell vertices each having at least one includes type of edge that encounters at least one of the profile parameter value vertices identified for the panelist, and that do not have at least one excludes type of edge that encounters at least one of the profile parameter value vertices identified for the panelist.

27. The computer program product of claim 26, wherein the code for identifying the set of quota cells further comprises code for determining an incomplete match to a quota cell in response to an edge of a quota cell vertex for the quota cell encountering a profile parameter value vertex representing a value of a profile parameter that is not determined for the panelist.

28. The computer program product of claim 27, wherein the non-transitory computer-readable medium further comprises code for eliminating all quota cells from the set that belong only to projects having at least one quota group not matched to at least one of the identified quota cells.

29. The computer program product of claim 27, wherein the non-transitory computer-readable medium further comprises:

code for determining whether matches are complete for each quota cell of the set associated with the project and, if not, obtaining additional information from the panelist with respect to each of the incompletely matched quota cells and determining whether a fit exists based on the additional information; and

code for responding to a determination that a fit does not exist by eliminating all quota cells from the set that are associated with the incompletely matched project, and selecting another one of the quota cells of the set.

30. The computer program product of claim 24, wherein a code for selecting one of the quota cells comprises code for selecting one of the quota cells from the set at random.

31. The computer program product of claim 30, wherein the code for selecting one of the quota cells from the set at random further comprises code for weighting random selection of the quota cells according to priorities assigned to the quota cells.

32. The computer program product of claim 31, wherein the non-transitory computer-readable medium further comprises code for assigning the priorities based on percentage of progress of the project, elapsed effective field time for completion of the project, and scarcity of the quota cell criteria.

33. The computer program product of claim 31, wherein the code for weighting random selection of the quota cells according to priorities assigned to the quota cells includes:

code for associating the quota cells with segments of a segmented bell curve based on the priorities;

code for randomly selecting a segment of the bell curve, wherein a segment associated with quota cells of higher priority than those of another segment has a greater chance of being selected than the other segment; and

code for randomly selecting a quota cell of the selected segment of the bell curve.

34. An apparatus for matching a first entity to a second entity by evaluating Boolean expressions, the apparatus comprising:

a memory that stores a graph database relating fact vertices to criteria vertices by edges corresponding to a Boolean expression for matching the first entity to the second entity; and

a processor configured to;

identify one or more fact vertices for the second entity;

generate a first set of criteria vertices by traversing a graph database constrained to the fact vertices identified for the second entity; and

for a first criteria vertex in the first set of criteria vertices;

determine whether the first criteria vertex matches a first fact vertex among the fact vertices identified for the second entity,

in response to determining the first criteria vertex matches the first fact vertex, assemble a second set of criteria vertices by adding the first criteria vertex to the second set of criteria vertices, or in response to determining the first criteria vertex does not match a fact vertex among the fact vertices identified for the second entity, retain the second set of criteria vertices, determine whether the second set of criteria vertices completes the Boolean expression, and

in response to determining the second set of criteria vertices completes the Boolean expression, complete the assembly of the second set of criteria vertices, or in response to determining the second set of criteria vertices does not complete the Boolean expression, process a second criteria vertex in the first set of criteria vertices,

wherein completion of an include criteria of the Boolean expression is determined separately from completion of an exclude criteria of the Boolean expression.

35. The apparatus of claim 34, wherein the first entity corresponds to a market research project, the second entity corresponds to a panelist, the fact vertices correspond to profile parameter vertices representing profile parameter values identified for the panelist, and the criteria vertices represent quota cells of market research projects.

36. The apparatus of claim 35, wherein said processor is configured to identify a set of quota cells by traversing edges of the graph database from a panelist vertex to all profile parameter value vertices of the graph database representing profile parameter values that have been identified for a panelist represented by the panelist vertex.

37. The apparatus of claim 36, wherein said processor is configured to identify the set of quota cells by traversing the graph database to identify a set of quota cell vertices each having at least one includes type of edge that encounters at least one of the profile parameter value vertices identified for the panelist, and that do not have at least one excludes type of edge that encounters at least one of the profile parameter value vertices identified for the panelist.

38. The apparatus of claim 37, wherein said processor is configured to identifying the set of quota cells by determining an incomplete match to a quota cell in response to an edge of the quota cell vertex for the quota cell encountering a profile parameter value vertex representing a value of a profile parameter that is not determined for the panelist.

39. The apparatus of claim 38, wherein said processor is configured to eliminate all quota cells from the set that belong only to projects having at least one quota group not matched to at least one of the identified quota cells.

40. The apparatus of claim 38, wherein said processor is configured to:

determine whether matches are complete for each quota cell of the set associated with the project and, if not, obtain additional information from the panelist with respect to each of the incompletely matched quota cells and determine whether a fit exists based on the additional information; and

respond to a determination that a fit does not exist by eliminating all quota cells from the set that are associated with the incompletely matched project, and selecting another one of the quota cells of the set.

41. The apparatus of claim 35, wherein said processor is configured to select one of the quota cells by selecting one of the quota cells from the set at random.

42. The apparatus of claim 41, wherein said processor is configured to select one of the quota cells at random by weighting random selection of the quota cells according to priorities assigned to the quota cells.

43. The apparatus of claim 42, wherein said processor is configured to calculate the priorities as a function of percentage of progress of the project, elapsed effective field time for completion of the project, and scarcity of the quota cell criteria.

44. The apparatus of claim 42, wherein said processor is configured to weighting random selection of the quota cells according to priorities assigned to the quota cells by:

associating the quota cells with segments of a segmented bell curve based on the priorities;

randomly selecting a segment of the bell curve, wherein a segment associated with quota cells of higher priority than those of another segment has a greater chance of being selected than the other segment; and

randomly selecting a quota cell of the selected segment of the bell curve.

45. The apparatus of claim 38, wherein said processor is configured to weighting random selection of the quota cells according to priorities assigned to the quota cells by:

associating the quota cells with segments of a segmented bell curve based on the priorities;

randomly selecting a segment of the bell curve, wherein a segment associated with quota cells of higher priority than those of another segment has a greater chance of being selected than the other segment; and

randomly selecting a quota cell of the selected segment of the bell curve.