APPARATUS, SYSTEMS, AND METHODS FOR GROUPING DATA RECORDS

• US 20140279757A1
• Filed: 03/14/2014
• Published: 09/18/2014
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Foursquare Labs, Inc.
• Original Assignee: Factual Incorporated (Foursquare Labs, Inc.)
• Inventors: POLOVETS, Leonid, SHIMANOVSKY, Boris, LAGANG, Manuel
• Granted Patent: US 10,831,725 B2
• Time in Patent Office: Days
• US Class Current: 706/12
• CPC Class Codes: G05B 13/0265 the criterion being a learning criterion
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/235 Update request formulation
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/2386 Bulk updating operations data conversion details G06F16/258
• CPC Class Codes: G06F 16/24564 Applying rules; Deductive queries
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/337 Profile generation, learning or modification
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/022 Knowledge engineering; Knowledge acquisition
• CPC Class Codes: G06Q 10/101 Collaborative creation, e.g. joint development of products or services
• CPC Class Codes: G06Q 30/0261 based on user location
• CPC Class Codes: G06Q 30/0282 Rating or review of business operators or products
• CPC Class Codes: G06Q 50/01 : Social networking
• CPC Class Codes: H04L 41/14 : Network analysis or design
• CPC Class Codes: H04W 16/00 : Network planning, e.g. coverage or traffic planning tools; Network deployment, e.g. resource partitioning or cells structures
• CPC Class Codes: H04W 16/24 : Cell structures
• CPC Class Codes: H04W 16/30 : Special cell shapes, e.g. doughnuts or ring cells
• CPC Class Codes: H04W 16/32 : Hierarchical cell structures
• CPC Class Codes: H04W 4/02 : Services making use of location information
• CPC Class Codes: H04W 4/021 : Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/025 : using location based information parameters
• CPC Class Codes: H04W 4/029 : Location-based management or tracking services
• CPC Class Codes: H04W 4/50 : Service provisioning or reconfiguring
• CPC Class Codes: H04W 64/00 : Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 64/003 : locating network equipment
• CPC Class Codes: H04W 76/38 : triggered by timers
• CPC Class Codes: H04W 8/08 : Mobility data transfer
• CPC Class Codes: H04W 8/16 : selectively restricting mobility data tracking
• CPC Class Codes: H04W 8/18 : Processing of user or subscriber data, e.g. subscribed services, user preferences or user profiles; Transfer of user or subscriber data
• CPC Class Codes: H04W 88/00 : Devices specially adapted for wireless communication networks, e.g. terminals, base stations or access point devices
• CPC Class Codes: H04W 88/02 : Terminal devices

Abstract

The present application relates to apparatus, systems, and methods for grouping data records based on entities referenced by the data records. The disclosed grouping mechanism can include determining a pair-wise similarity between a large number of data records, and clustering a subset of the data records based on their pair-wise similarity.

Claims

1. An apparatus comprising:

a processor configured to run one or more modules stored in memory, wherein the one or more modules are configured to;

identify at least one pair of data records for which to determine a similarity value;

determine the similarity value for the at least one pair of data records based, at least in part, on a plurality of attributes associated with the at least one pair of data records; and

associate the at least one pair of data records with one or more clusters, each associated with a unique entity, based on the similarity value for the at least one pair of data records.

2. The apparatus of claim 1, wherein the one or more modules are further configured to identify one or more pairs of data records for which a similarity value need not be determined based on a predetermined set of attributes that are likely to be shared by related data records.

3. The apparatus of claim 2, wherein the one or more modules are configured to adjust the predetermined set of attributes based on association of data records to clusters from a previous iteration.

4. The apparatus of claim 1, wherein the one or more modules are configured to determine the similarity value based on a similarity function learned from training data records.

5. The apparatus of claim 4, wherein the similarity function is designed to infer an importance of a particular component associated with a particular attribute of a data record, wherein the similarity function is learned by:

determining differences between components associated with the particular attribute of the training data records, wherein the training data records are known belong to the same cluster; and

determining the importance of the particular component based on a number of times the particular component appears in the differences.

6. The apparatus of claim 4, wherein the similarity function is designed to infer a likelihood of interchanging a first component in a particular attribute of a data record with a second component, wherein the similarity function is learned by:

determining differences between components associated with the particular attribute of the training data records, wherein the training data records are known belong to the same cluster; and

determining the likelihood of interchanging the first component with the second component based on a number of times the first component and the second component appears in the differences at the same time.

7. The apparatus of claim 4, wherein the similarity function is designed to determine a conditional likelihood that a missing attribute of a data record has a particular component, wherein the conditional likelihood is determined by:

determining a combination of known attributes corresponding to a particular entity;

determining all variations of a missing attribute amongst data records of the particular entity having the combination of known attributes; and

determining a conditional probability, based on the variations of the missing attribute, that the missing attribute has a particular component given that the data record has the particular combination of known attributes.

8. The apparatus of claim 1, wherein the one or more modules are configured to:

represent the plurality of data records as a plurality of nodes in a graph;

represent the similarity value for the at least one pair of data records as at least one edge between nodes, in the graph, corresponding to the at least one pair of data records; and

determine the one or more clusters from based on the graph.

9. The apparatus of claim 8, wherein the one or more modules are configured to determine the one or more clusters based on the graph using a graph clustering technique.

10. The apparatus of claim 1, wherein the one or more modules are configured to receive a clustering directive requiring the one or more modules to associate two data records with the same cluster.

11. The apparatus of claim 1, wherein the one or more modules are configured to

associate at least one of the plurality of data records to one or more clusters using a clustering technique;

and

adjust a parameter for the clustering technique for each of the one or more clusters independently, based on data records in the one or more clusters.

12. The apparatus of claim 1, wherein the one or more modules are configured to determine the similarity value for the at least one pair of data records by receiving the similarity value for the at least one pair of data records from another computing device.

13. The apparatus of claim 1, wherein the one or more modules are configured to:

receive, from a plurality of computing devices, a plurality of sub-clusters independently identified at the plurality of computing devices; and

perform a union-find operation on the plurality of sub-clusters to identify the one or more clusters.

14. A method for clustering a plurality of data records into at least one cluster, the method comprising:

identifying, at a candidate reduction module in a computing device, at least one pair of the plurality of data records for which to determine a similarity value;

determining, at a similarity computation module residing in the computing device, in communication with the candidate reduction module, the similarity value for the at least one pair based, at least in part, on a plurality of attributes associated with the at least one pair of data records; and

associating, at a clustering computation module residing in the computing device, in communication with the similarity computation module, the at least one pair of data records with one or more clusters, each associated with a unique entity, based on the similarity value for the at least one pair of data records.

15. The method of claim 14, further comprising identifying, at the candidate reduction module, one or more pairs of the plurality of data records for which a similarity value need not be determined based on a predetermined set of attributes that are likely to be shared by related data records.

16. The method of claim 15, further comprising adjusting, at the candidate reduction module, the predetermined set of attributes based on association of data records to clusters from a previous iteration.

17. The method of claim 14, further comprising determining, at the similarity computation module, the similarity value based on a similarity function learned from training data records.

18. The method of claim 17, wherein the similarity function is designed to infer an importance of a particular component associated with a particular attribute of a data record.

19. The method of claim 17, wherein the similarity function is designed to infer a likelihood of interchanging a first component in a particular attribute of a data record with a second component.

20. A computer program product, tangibly embodied in a non-transitory computer-readable storage medium, the computer program product including instructions operable to cause a data processing system to:

identify at least one pair of data records for which to determine a similarity value;

determine the similarity value for the at least one pair of data records based, at least in part, on a plurality of attributes associated with the at least one pair of data records; and

associate the at least one pair of data records with one or more clusters, each associated with a unique entity, based on the similarity value for the at least one pair of data records.

21. The computer program product of claim 20, wherein the executable instructions are operable to cause the data processing apparatus to identify one or more pairs of the plurality of data records for which a similarity value need not be determined based on a predetermined set of attributes that are likely to be shared by related data records.

22. The computer program product of claim 21, wherein the executable instructions are operable to cause the data processing apparatus to adjust the predetermined set of attributes based on association of data records to clusters from a previous iteration.

23. The computer program product of claim 20, wherein the executable instructions are operable to cause the data processing apparatus to determine the similarity value based on a similarity function learned from training data records.

24. The computer program product of claim 23, wherein the similarity function is designed to infer an importance of a particular component associated with a particular attribute of a data record.

25. The computer program product of claim 23, wherein the similarity function is designed to infer a likelihood of interchanging a first component in a particular attribute of a data record with a second component.