SYSTEM AND METHOD FOR IDENTIFYING RELATIONSHIPS IN A DATA GRAPH

• US 20160048517A1
• Filed: 08/12/2014
• Published: 02/18/2016
• Est. Priority Date: 08/12/2014
• Status: Active Grant

• Current Assignee: Ancestry.com Operations Inc. (Ancestry.com Incorporated)
• Original Assignee: Ancestry.com Operations Inc. (Ancestry.com Incorporated)
• Inventors: Jensen, Tyler S.
• Granted Patent: US 9,747,345 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/245 Query processing
• CPC Class Codes: G06F 16/2457 with adaptation to user needs
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

A graph database system is used to determine relationships between persons. The graph database system manages relationship data records having a compact data structure stored at a relationship database and accessed to find links or common relationships. For determining relationships between two people, the relationship records in the relationship paths for those two people are alternatively accessed and compared it to each other. Relationship records may include an identifier for a person having a relationship to a given individual, a relationship type, and a weight reflecting the confidence level or quality of the relationship.

Claims

1. A method for determining a relationship between at least two persons of interest, comprising:

storing, in a relationship database, a data structure representing relationship data records for a large population of persons, the relationship records having data only pertaining to the relationship between persons, each relationship record comprising, for one given person, relationship data identifying at least one other person having a relationship to the one given person;

accessing the stored relationship data records associated with a first person of interest;

accessing the stored relationship data records associated with a second person of interest;

comparing the accessed relationship records to determine if there is any person in common to both a relationship record associated with the first person of interest and relationship record associated with the second person of interest; and

identifying any person in common.

2. The method of claim 1, further comprising:

if comparing the accessed relationship records determines there is no person in common between the relationship records associated with the first person of interest in the second person of interest, then

accessing the relationship data records associated with each other person having a relationship to the first person of interest;

accessing the relationship data records associated with each other person having a relationship to the second person of interest; and

comparing the accessed relationship records associated with each other person having a relationship to the first person of interest and to the second person of interest, to determine if there is any person in common.

3. The method of claim 1, wherein each relationship record further comprises relationship type data identifying the type of the relationship between the one given person and the other person.

4. The method of claim 3, wherein the type of the relationship between the one given person and the other person comprises one of at least father, mother, son, daughter.

5. The method of claim 1, further comprising:

prior to accessing the stored relationship data records associated with a second person of interest, first comparing the accessed relationship records associated with a first person of interest with data identifying the second person of interest to determine if any of the at least one other person having a relationship to the first person of interest is the same as the second person of interest, and if not, then accessing the stored relationship data records associated with the second person of interest.

6. The method of claim 1, further comprising:

determining a weight associated with a relationship identified between the one given person and the at least one other person having a relationship to the one given person, based on the likely accuracy of that relationship; and

storing the weight in association with the relationship data identifying the at least one other person having a relationship to the one given person.

7. The method of claim 1, wherein accessing the stored relationship records is in response to a request from a user to locate any person in common, and wherein any identified person in common is provided to the user, and wherein the method further comprises:

aggregating each identified person in common in preparing an answer in response to the request from the user;

receiving a pre-established weight from the user in order to filter the answer; and

filtering the answer to remove an identified person in common based on the predetermined weight.

8. The method of claim 1, further comprising:

determining the relationship path between the first person of interest in the second person of interest based on the any identified person in common;

retrieving data from a genealogical database pertaining to any person in the relationship path between the first person of interest and the second person of interest; and

providing retrieved data from the genealogical database along with any identified person in common.

9. The method of claim 1, wherein the data structure stored in the relationship database is created by a graph server using data retrieved from genealogical records.

10. The method of claim 9, wherein accessing the stored relationship records, comparing the accessed relationship records, and identifying any person in common are performed by the graph server in response to receiving, at the graph sever, a request from a user to locate any person in common.

11. The method of claim 1, wherein a personal identifier is associated with each person in the population of persons, wherein the relationship data identifying at least one other person having a relationship to the one given person comprises the personal identifier for the one other person, and wherein the step of comparing the accessed relationship records comprises:

comparing, in the accessed relationship records, the personal identifier associated with each other person having a relationship to the first person of interest with the personal identifier associated with each other person having a relationship to the second person of interest.

12. A graph system for determining a relationship between at least two persons of interest, comprising:

a relationship database storing a data structure, the data structure representing relationship data records for a large population of persons, the relationship records having data only pertaining to the relationship between persons, each relationship record comprising, for one given person, relationship data identifying at least one other person having a relationship to the one given person;

a graph server comprising a processor and a memory, the memory storing instructions that are executable by the processor and configure the graph server to;

access, in the relationship database, the stored relationship data records associated with a first person of interest;

access, in the relationship database, the stored relationship data records associated with a second person of interest;

compare the accessed relationship records to determine if there is any person in common to both a relationship record associated with the first person of interest and relationship record associated with the second person of interest; and

identify any person in common.

13. The system of claim 12, wherein the graph server is further configured to:

if comparing the accessed relationship records determines there is no person in common between the relationship records associated with the first person of interest in the second person of interest, then

access the relationship data records associated with each other person having a relationship to the first person of interest;

access the relationship data records associated with each other person having a relationship to the second person of interest; and

compare the accessed relationship records associated with each other person having a relationship to the first person of interest and to the second person of interest, to determine if there is any person in common.

14. The system of claim 12, wherein each relationship record further comprises relationship type data identifying the type of the relationship between the one given person and the other person.

15. The system of claim 14, wherein the type of the relationship between the one given person and the other person comprises one of at least father, mother, son, daughter.

16. The system of claim 12, wherein the graph server is further configured to:

prior to accessing the stored relationship data records associated with a second person of interest, first compare the accessed relationship records associated with a first person of interest with data identifying the second person of interest to determine if any of the at least one other person having a relationship to the first person of interest is the same as the second person of interest, and if not, then access the stored relationship data records associated with the second person of interest.

17. The system of claim 12, wherein the graph server is further configured to:

determine a weight associated with a relationship identified between the one given person and the at least one other person having a relationship to the one given person, based on the likely accuracy of that relationship; and

store the weight in association with the relationship data identifying the at least one other person having a relationship to the one given person.

18. The system of claim 12, wherein accessing the stored relationship records is in response to a request from a user to locate any person in common, and wherein any identified person in common is provided to the user, and wherein the graph server is further configured to:

aggregate each identified person in common in preparing an answer in response to the request from the user;

receive a pre-established weight from the user in order to filter the answer; and

filter the answer to remove an identified person in common based on the predetermined weight.

19. The system of claim 12, wherein the graph server is further configured to:

determine the relationship path between the first person of interest in the second person of interest based on the any identified person in common;

retrieve data from a genealogical database pertaining to any person in the relationship path between the first person of interest and the second person of interest; and

provide retrieved data from the genealogical database along with any identified person in common.

20. The system of claim 12, wherein the data structure stored in the relationship database is created by the graph server using data retrieved from genealogical records.

21. The system of claim 20, wherein accessing the stored relationship records, comparing the accessed relationship records, and identifying any person in common are performed by the graph server in response to receiving, at the graph sever, a request from a user to locate any person in common.

22. The system of claim 12, wherein a personal identifier is associated with each person in the population of persons, wherein the relationship data identifying at least one other person having a relationship to the one given person comprises the personal identifier for the one other person, and wherein comparing the accessed relationship records comprises:

comparing, in the accessed relationship records, the personal identifier associated with each other person having a relationship to the first person of interest with the personal identifier associated with each other person having a relationship to the second person of interest

23. A method for creating a data structure maintained by a graph server for determining a relationship between at least two persons of interest, comprising:

accessing one or more genealogic databases having data pertaining to a large population of people;

retrieving data pertaining to the relationships between people in the large population of people;

storing, in a relationship database, relationship data records based on the retrieved data, the stored relationship data records only pertaining to the relationships between persons, each relationship record comprising, for one given person, relationship data identifying at least one other person having a relationship to the one given person, relationship type data identifying the type of the relationship between the one given person and the other person, and weight data associated with a relationship identified between the one given person and the at least one other person having a relationship to the one given person, the weight data representing the likely accuracy of that relationship.

24. A method for determining a relationship between at least two items of interest, comprising:

storing, in a relationship database, a data structure representing relationship data records for a large set of items, the relationship records having data only pertaining to the relationship between items, each relationship record comprising, for one given item, an item identifier identifying at least one other item that has a relationship to the one given item;

receiving, from a user, a request to determine the relationship between at least a first item of interest and at least a second item of interest;

in response to the request, accessing stored relationship data records associated with the first item of interest and the second item of interest;

comparing item identifiers in the accessed relationship records to determine if there is any item in common to both a relationship record associated with one item of interest and relationship record associated with the second item of interest; and

identifying any item in common.

retrieving, from the accessed data record, an identifier for any person reflected in the accessed data record as related to the first person of interest;

determining whether any person identified in the accessed relationship records as having a relationship to the first person of interest, is the same as or related to the second person of interest.