System and method for fast component enumeration in graphs with implicit edges

• US 8,462,161 B1
• Filed: 02/06/2009
• Issued: 06/11/2013
• 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:
  US12/367,180
• Time in Patent Office: 1,586 Days
• Field of Search: 345/440, 345/440.2, 345/441
• US Class Current: 345/440
• 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 system for performing graphical enumeration, comprising:

a non-transitory computer readable storage medium storing executable program code comprising code for;

creating an ordered set of vertices for a graph, each vertex comprising a unique index and a plurality of keys, wherein each key defines an element of information associated with the vertex and the vertices are ordered based on the unique index;

creating a plurality of lists of vertices, each list associated with a key such that vertices in a list share a same element of information defined by the key;

for each list of vertices;

determining a least-valued index from vertices in the list;

pointing all vertices in the list to a root vertex associated with the least-valued index;

determining a least-valued index from vertices pointed to by the vertices in each list; and

updating the root vertex with a vertex associated with the newly determined least-valued index; and

a processor for executing the program code.

2. A method of graphical enumeration, comprising:

creating, by a processor, an ordered set of vertices for a graph, each vertex comprising a unique index and a plurality of keys, wherein each key defines an element of information associated with the vertex and the vertices are ordered based on the unique index;

creating a plurality of lists of vertices, each list associated with a key such that vertices in a list share a same element of information defined by the key;

for each list of vertices;

determining a least-valued index from vertices in the list;

pointing all vertices in the list to a root vertex associated with the least-valued index;

determining a least-valued index from vertices pointed to by the vertices in each list; and

updating the root vertex with a vertex associated with the newly determined least-valued index.

3. The method of claim 2, further comprising:

determining repeatedly a least-valued index among all the vertices in the list and vertices pointed to by the vertices in the list; and

updating the root vertex with vertex associated the determined least-valued index until the root vertex dose not point to another vertex.

4. The method of claim 2, wherein updating the root vertex comprises:

pointing each vertex in the list to the root vertex associated with the newly determined least-valued index.

5. A method of graphical enumeration, comprising:

creating, by a processor, an ordered set of vertices for a graph, each vertex comprising a unique index and a plurality of keys, wherein each key defines an element of information associated with the vertex and the vertices are ordered based on the unique index;

storing the ordered set of vertices in a database;

creating a plurality of lists of vertices, each list associated with a key such that vertices in a list share a same element of information defined by the key;

for each list of vertices;

determining a least-valued index from vertices in the list;

pointing all vertices in the list to a root vertex associated with the least-valued index;

determining a least-valued index from vertices pointed to by the vertices in each list; and

updating the root vertex with a vertex associated with the newly determined least-valued index; and

storing in the database the corresponding least-valued index with each vertex in each list.

6. The method of claim 5, further comprising wherein:

determining repeatedly a least-valued index among all the vertices in the list and vertices pointed to by the vertices in the list; and

updating the root vertex with vertex associated the determined least-valued index until the root vertex dose not point to another vertex.

7. The method of claim 5, wherein updating the root vertex comprises:

pointing each vertex in the list to the root vertex associated with the newly determined least-valued index.

8. The method of claim 5, further comprising:

repeating for each of the lists of vertices in order;

determining a least-valued index;

pointing all vertices in each list to a root vertex associated with the least-valued index; and

storing the least-valued index with each vertex in each list.

9. The method of claim 8, further comprising:

associating all vertices that point to the same root vertex with a component of the graph.

10. The method of claim 9, wherein said associating all vertices comprises:

associating consumer transactions corresponding to vertices in the component.

11. The method of claim 9, further comprising:

storing the vertices associated with the component in the storage in relation to the component.

12. The method of claim 5, further comprising:

storing the plurality of lists of vertices in the database.

13. The method of claim 5, wherein the element of information includes at least one of:

a credit card number, a machine fingerprint, an internet protocol address, electronic mail address, and hypertext transmission protocol (HTTP) cookie.

14. The method of claim 5, further comprising:

after a condition is satisfied, allowing a conditioned vertex in the graph to expire;

deleting the expired conditioned vertex; and

deleting pointing references to the expired conditioned vertex.

15. The method of claim 5, further comprising:

after a condition is satisfied, allowing a key in the graph to expire; and

deleting a corresponding list of vertices associated with the expired key.

16. A method of graphical enumeration of claim 5, further comprising:

receiving information related to at least one consumer transaction from at least one source.

17. A system for performing graphical enumeration, comprising:

a processor;

a receiver for receiving information related to at least one consumer transaction from at least one source;

a graph definer for creating an ordered set of vertices for a graph, each vertex comprising a unique index and a plurality of keys, wherein each key defines an element of information associated with the vertex and the vertices are ordered based on the unique index;

a list creator for creating a plurality of lists of vertices, each list associated with a key such that vertices in a list share a same element of information defined by the key; and

a component generator for;

for each list of vertices;

determining a least-valued index from vertices in the list;

pointing all vertices in the list to a root vertex associated with the least-valued index;

determining a least-valued index from vertices pointed to by the vertices in each list; and

updating the root vertex with a vertex associated with the newly determined least-valued index.

18. The system of claim 17, further comprising:

a database for storing the ordered set of vertices and for storing the corresponding least-valued index with each vertex in each list.

19. The system of claim 18, further comprising:

the database for storing in relation to a component vertices that are associated with the component, wherein vertices associated with the component point to the same root vertex.