Fast component enumeration in graphs with implicit edges

• US 9,916,393 B2
• Filed: 06/02/2015
• Issued: 03/13/2018
• 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:
  US14/728,499
• Publication Number:
  US 20150294027A1
• Time in Patent Office: 1,015 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, 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;

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; and

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

2. The method of claim 1, wherein the predetermined condition is a predetermined period of time.

3. The method of claim 2, wherein the predetermined period of time is set based on a data type of the expired key.

4. The method of claim 3, wherein the data type is one of:

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

5. The method of claim 1, further comprising:

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.

6. The method of claim 1, further comprising:

associating each list of vertices of the plurality of lists of vertices to a root vertex; and

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.

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;

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; and

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

12. The non-transitory computer-readable storage medium of claim 11, wherein the predetermined condition is a predetermined period of time.

13. The non-transitory computer-readable storage medium of claim 12, wherein the predetermined period of time is set based on a data type of the expired key.

14. The non-transitory computer-readable storage medium of claim 13, wherein the data type is one of:

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

15. The non-transitory computer-readable storage medium of claim 11, further comprising 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.

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

associating each list of vertices of the plurality of lists of vertices to a root vertex; and

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.

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.