Fast component enumeration in graphs with implicit edges

• US 9,075,896 B2
• Filed: 05/30/2013
• Issued: 07/07/2015
• 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:
  US13/905,952
• Publication Number:
  US 20130254169A1
• Time in Patent Office: 768 Days
• Field of Search: 345/440
• US Class Current: 1/1
• 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, by a processor, a graph for a set of data records, each data record represented as a vertex in the graph, each data record comprising a unique index and one or more data elements;

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;

partitioning the vertices in the graph into a plurality of subsets, each subset comprising a list of vertices, wherein vertices in a list share a same key; and

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.

2. The method of claim 1, further comprising:

determining repeatedly one by one for each list of vertices of the plurality of subsets a vertex with a least valued index among vertices pointed to by the vertices in the list until a root vertex that points to itself is found.

3. The method of claim 2, further comprising:

associating the list of vertices to the root vertex.

4. The method of claim 3, further comprising:

storing the graph, the plurality of list of vertices and the corresponding root vertex for each list of vertices in a database.

5. The method of claim 3, further comprising:

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

6. The method of claim 1, further comprising:

deleting a corresponding list of vertices that share a key that expired under a predetermined condition.

7. The method of claim 1, further comprising:

deleting a vertex in the graph responsive to the vertex being expired under a predetermined condition.

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 for providing electronic money transfer, the computer program instructions comprising instructions for:

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

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;

partitioning the vertices in the graph into a plurality of subsets, each subset comprising a list of vertices, wherein vertices in a list share a same key; and

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.

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

determining repeatedly one by one for each list of vertices of the plurality of subsets, a vertex with a least valued index among vertices pointed to by the vertices in the list until a root vertex that points to itself is found.

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

associating the list of vertices to the root vertex.

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

storing the graph, the plurality of list of vertices and the corresponding root vertex for each list of vertices in a database.

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

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

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

deleting a list of vertices in the graph responsive to a key being expired under a predetermined condition, the list of vertices sharing the expired key.

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.

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.