Fast component enumeration in graphs with implicit edges

• US 10,642,899 B2
• Filed: 03/12/2018
• Issued: 05/05/2020
• Est. Priority Date: 01/20/2009
• Status: Active Grant

• Current Assignee: Kount Incorporated (Equifax, Inc.)
• Original Assignee: Kount Incorporated (Equifax, Inc.)
• Inventors: Barber, Timothy P.
• Primary Examiner(s): Amini, Javid A
• Application Number:
  US15/919,203
• Publication Number:
  US 20180203945A1
• Time in Patent Office: 785 Days
• Field of Search: 345440
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06T 11/20 Drawing from basic elements, e.g. lines or circles
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs

Abstract

A method and system for graphical enumeration. The method includes creating an ordered set of vertices for a graph such that each vertex is associated with a corresponding index, and wherein each vertex in the ordered set of vertices includes information. A plurality of keys is created for defining the information. A plurality of lists of vertices is created, each of which is associated with a corresponding key such that vertices in a corresponding list include information associated with the corresponding key. For a first list of vertices, a least valued index is determined from a group of associated vertices based on vertices in the first list and vertices pointed to by the vertices in the first list. Also, all associated vertices are pointed to a root vertex associated with the least valued index.

Claims

1. A method for enumerating a graph, the method comprising:

creating a graph for a set of data records, each data record represented as a vertex in the graph, each data record comprising one or more data elements; and

pointing each vertex in the graph in a database to a corresponding root vertex based on the one or more data elements of the data record represented by the vertex, wherein pointing each vertex in the graph to a corresponding root vertex comprises creating a key for each unique value of each data element represented by the vertices in the graph, each key representing an implicit edge in the graph, wherein two vertices sharing a key implicitly share an edge.

2. The method of claim 1, wherein pointing each vertex in the graph to a corresponding root vertex comprises:

creating a plurality of lists of vertices, each list comprising a plurality of vertices in the graph, the vertices in a list sharing a same key.

3. The method of claim 2, further comprising:

deleting a list of vertices that share a key that expired under a predetermined condition, the predetermined condition comprising whether a period of time has expired.

4. The method of claim 2, wherein pointing each vertex in the graph to a corresponding root vertex further comprises:

for each list of vertices;

determining a vertex with a least valued index in the list based on the vertices in the list and vertices pointed to by the vertices in the list; and

associating all vertices in a list of vertices with a vertex having the least valued index.

5. The method of claim 4, wherein the corresponding root vertex is the vertex having the least valued index.

6. The method of claim 2, further comprising:

grouping one or more lists of vertices that point to a same root vertex with a component of the graph.

7. The method of claim 1, further comprising:

deleting a vertex in the graph responsive to the vertex being expired under a predetermined condition, the predetermined condition comprising whether a period of time has expired.

8. The method of claim 7, further comprising:

responsive to the expired vertex being a root vertex, determining a new root vertex for one or more lists associated with the expired vertex.

9. The method of claim 1, wherein the data records are consumer transaction records.

10. The method of claim 9, wherein the one or more data elements include at least one of:

credit card number, device fingerprint, Internet protocol (IP) address, electronic mail address, and hypertext transmission protocol (HTTP) cookie.

11. A non-transitory computer-readable storage medium storing executable computer program instructions, the computer program instructions comprising instructions for:

creating a graph for a set of data records, each data record represented as a vertex in the graph, each data record comprising one or more data elements; and

pointing each vertex in the graph in a database to a corresponding root vertex based on the one or more data elements of the data record represented by the vertex, wherein pointing each vertex in the graph to a corresponding root vertex comprises creating a key for each unique value of each data element represented by the vertices in the graph, each key representing an implicit edge in the graph, wherein two vertices sharing a key implicitly share an edge.

12. The non-transitory computer-readable storage medium of claim 11, wherein the instructions for pointing each vertex in the graph to a corresponding root vertex comprise instructions for:

creating a plurality of lists of vertices, each list comprising a plurality of vertices in the graph, the vertices in a list sharing a same key.

13. The non-transitory computer-readable storage medium of claim 12, further comprising instructions for:

deleting a list of vertices that share a key that expired under a predetermined condition, the predetermined condition comprising whether a period of time has expired.

14. The non-transitory computer-readable storage medium of claim 12, wherein the instructions for pointing each vertex in the graph to a corresponding root vertex comprise instructions for:

for each list of vertices;

determining a vertex with a least valued index in the list based on the vertices in the list and vertices pointed to by the vertices in the list; and

associating all vertices in a list of vertices with a vertex having the least valued index.

15. The non-transitory computer-readable storage medium of claim 14, wherein the corresponding root vertex is the vertex having the least valued index.

16. The non-transitory computer-readable storage medium of claim 12, further comprising instructions for:

grouping one or more lists of vertices that point to a same root vertex with a component of the graph.

17. The non-transitory computer-readable storage medium of claim 11, further comprising instructions for:

deleting a vertex in the graph responsive to the vertex being expired under a predetermined condition, the predetermined condition comprising whether a period of time has expired.

18. The non-transitory computer-readable storage medium of claim 17, further comprising instructions for:

responsive to the expired vertex being a root vertex, determining a new root vertex for one or more lists associated with the expired vertex.

19. The non-transitory computer-readable storage medium of claim 11, wherein the data records are consumer transaction records.

20. The non-transitory computer-readable storage medium of claim 19, wherein the one or more data elements include at least one of:

credit card number, device fingerprint, Internet protocol (IP) address, electronic mail address, and hypertext transmission protocol (HTTP) cookie.