Computer-implemented systems and methods for comparing and associating objects

• US 10,152,531 B2
• Filed: 02/25/2016
• Issued: 12/11/2018
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Palantir Technologies Incorporated
• Original Assignee: Palantir Technologies Incorporated
• Inventors: Elliot, Mark, Chang, Allen
• Primary Examiner(s): Le, Uyen
• Application Number:
  US15/053,305
• Publication Number:
  US 20160179927A1
• Time in Patent Office: 1,020 Days
• Field of Search: None
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/3346 using probabilistic model
• CPC Class Codes: G06F 16/335 Filtering based on additional data, e.g. user or group profiles filtering in web context G06F16/9535, G06F16/9536
• CPC Class Codes: G06F 16/35 Clustering; Classification
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06Q 50/26 Government or public services business processes related to the transportation industry G06Q50/40

Abstract

Computer-implemented systems and methods are disclosed for comparing and associating objects. In some embodiments, a method is provided for associating a first object with one or more objects within a plurality of objects, each object comprising a first plurality of properties, each property comprising data reflecting a characteristic of an entity represented by the object, the associated objects comprising matching data in corresponding properties for a second plurality of properties. The method may include executing, for each object within the plurality of objects and for the first object, the following: creating a slug for the object, the slug comprising the second plurality of properties from the object; and inputting the slug for the object into a Bloom filter. Further, the method may include creating for a bin within the Bloom filter corresponding to the slug for the first object, an association between objects whose slugs correspond to the bin if the slugs for those objects match.

Claims

1. An electronic device comprising:

one or more computer-readable storage media configured to store instructions; and

one or more processors configured to execute the instructions to cause the electronic device to;

execute, using the one or more processors, for each object within a plurality of objects, the following steps;

create a data structure of a first type comprising information for identifying one or more objects comprising a set of properties, wherein the data structure of a first type is created based at least in part on one or more properties associated with the object;

input the data structure of a first type into a software function, wherein the software function is configured to determine an association between the object and a second object, wherein the object comprises a first set of properties, and wherein the second object comprises a second set of properties; and

determine the association between the object and the second object based on the software function.

2. The electronic device in claim 1, wherein the software function determines the association between the object and the second object based at least in part on a data structure of a second type.

3. The electronic device of claim 1, wherein the software function determines the association between the object and the second object based at least in part on adding a data structure of a first type for the object and a data structure of a first type for the second object into a portion of a data structure of a second type.

4. The electronic device of claim 3, wherein the association between the object and the second object is the portion of the data structure of a second type.

5. The electronic device of claim 4, wherein the data structure of a first type is a slug, the data structure of a second type is a Bloom filter, and the portion of the data structure of a second type is a bin.

6. The electronic device of claim 4, wherein the one or more processors are further configured to execute the instructions to cause the electronic device to:

size the data structure of a second type based at least on an amount of objects within the plurality of objects.

7. The electronic device of claim 4, wherein the one or more processors are further configured to execute the instruction to cause the electronic device to:

cause the data structure of a second type to add each data structure of a first type into the portion of the data structure of a second type; and

for each portion of the data structure of a second type comprising two or more data structures of a first type;

add the two or more data structures of a first type to a multimap.

8. The electronic device of claim 7, wherein the one or more processors are further configured to execute the instructions to cause the electronic device to:

add two or more objects that correspond to the two or more data structures of a first type added to the multimap to the multimap; and

in response to the added two or more objects being different from each other, remove at least one of the two or more data structures of a first type from their respective portion of the data structure of a second type.

9. A method performed by at least one electronic device comprising one or more processors, the method comprising:

executing, using at least one processor, for each object within a plurality of objects, the following steps;

creating a data structure of a first type comprising information for identifying one or more objects comprising a set of properties, wherein the data structure of a first type is created based at least in part on one or more properties associated with the object;

inputting the data structure of a first type into a software function, wherein the software function is configured to determine an association between the object and a second object, wherein the object comprises a first set of properties, and wherein the second object comprises a second set of properties that include at least a portion of the first set of properties; and

determining the association between the object and the second object based on the software function.

10. The method of claim 9, wherein the software function determines the association between the object and the second object based at least in part on a data structure of a second type.

11. The method of claim 9, wherein the software function determines the association between the object and the second object based at least in part on adding a data structure of a first type for the object and a data structure of a first type for the second object into a portion of a data structure of a second type.

12. The method of claim 11, wherein the association between the object and the second object is the portion of the data structure of a second type.

13. The method of claim 12, wherein the data structure of a first type is a slug, the data structure of a second type is a Bloom filter, and the portion of the data structure of a second type is a bin.

14. The method of claim 12, wherein the method further comprises:

causing the data structure of a second type to add each data structure of a first type into the portion of the data structure of a second type; and

for each portion of the data structure of a second type comprising two or more data structures of a first type;

adding the two or more data structures of a first type to a multimap.

15. A non-transitory computer readable medium that stores a set of instructions that ae executable by at least one processor of an electronic device to cause the electronic device to perform a method for associating objects the method comprising:

executing, using at least one processor, for each object within a plurality of objects, the following steps;

creating a data structure of a first type comprising information for identifying one or more objects comprising a set of properties, wherein the data structure of a first type is created based at least in part on one or more properties associated with the object;

inputting the data structure of a first type into a software function, wherein the software function is configured to determine an association between the object and a second object, wherein the object comprises a first set of properties, and wherein the second object comprises a second set of properties that include at least a portion of the first set of properties; and

determining the association between the object and the second object based on the software function.

16. The non-transitory computer readable medium of claim 15, wherein the software function determines the association between the object and the second object based at least in part on a data structure of a second type.

17. The non-transitory computer readable medium of claim 15, wherein the software function determines the association between the object and the second object based at least in part on a data structure of a first type for the object and a data structure of a first type for the second object into a portion of a data structure of a second type.

18. The non-transitory computer readable medium of claim 17, wherein the association between the object and the second object is the portion of the data structure of a second type.

19. The non-transitory computer readable medium of claim 18, wherein the data structure of a first type is a slug, the data structure of a second type is a Bloom filter, and the portion of the data structure of a second type is a bin.

20. The non-transitory computer readable medium of claim 18, wherein the set of instructions that are executable by at least one processor of the electronic device to cause the electronic device to further perform:

causing the data structure of a second type to add each data structure of a first type into the portion of the data structure of a second type; and

for each portion of the data structure of a second type comprising two or more data structure of a first type;

adding the two or more data structures of a first type to a multimap.