Computer-implemented systems and methods for comparing and associating objects

• US 9,286,373 B2
• Filed: 11/24/2014
• Issued: 03/15/2016
• 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 T
• Application Number:
  US14/552,336
• Publication Number:
  US 20150106379A1
• Time in Patent Office: 477 Days
• Field of Search: None
• US Class Current: 1/1
• 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; and

input the data structure of a first type into a data structure of a second type configured to determine objects associated with the data structure of a first type; and

create, using the one or more processors, an association between a first object and a second object based at least in part on adding a data structure of a first type for the first object and a data structure of a first type for the second object into a same bin in the data structure of a second type, wherein the first 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.

2. The electronic device of claim 1, 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.

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

cause the data structure of a second type to add each data structure of a first type into a bin in the data structure of a second type, the bin being one of a plurality of bins in the data structure of a second type; and

for each bin comprising two or more data structures of a first type;

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

4. The electronic device of claim 3, 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 bin of the plurality of bins.

5. The electronic device of claim 1, wherein the data structure of a first type structure is a slug, and the data structure of a second type is a bloom filter.

6. The electronic device of claim 1, wherein the one or more properties associated with the object are based at least in part on an environment associated with the object.

7. The electronic device of claim 1, wherein the one or more properties associated with the object are based at least in part on information that uniquely identifies the object.

8. The electronic device of claim 1, wherein the data structure of a second type exists on each of the one or more processors;

and

the data structure of a second type is executed on each of the one or more processors.

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

20. The non-transitory computer readable medium of claim 5, wherein the one or more properties associated with the object are based at least in part on an environment associated with the object.

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 for the object, wherein the data structure of a first type is created based at least in part on one or more properties associated with the object; and

inputting the data structure of a first type for the object into a data structure of a second type; and

creating, using at least one processor, an association between a first object and a second object based at least in part on a data structure of a first type for the first object and a data structure of a first type for the second object corresponding to a same bin in the data structure of a second type, wherein the first 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.

10. The method of claim 9, further comprising:

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

11. The method of claim 9, further comprising:

causing the data structure of a second type to add each data structure of a first type into a bin in the data structure of a second type, the bin being one of a plurality of bins in the data structure of a second type; and

for each bin comprising two or more data structures of a first type;

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

12. The method of claim 11, further comprising:

adding 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, removing at least one of the two or more data structures of a first type from their respective bin of the plurality of bins.

13. The method of claim 9, wherein the data structure of a first type is a slug, and the data structure of a second type is a bloom filter.

14. The method of claim 9, wherein the one or more properties associated with the object are based at least in part on an environment associated with the object.

15. A non-transitory computer readable medium that stores a set of instructions that are 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 for the object, wherein the data structure of a first type is created based at least in part on one or more properties associated with the object; and

inputting the data structure of a first type for the object into a data structure of a second type; and

creating, using at least one processor, an association between a first object and a second object based at least in part on a data structure of a first type for the first object and a data structure of a first type for the second object corresponding to a same bin in the data structure of a second type, wherein the first 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.

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

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

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

causing the data structure of a first type to add each of the data structures of a first type into a bin in the data structure of a second type, the bin being one of a plurality of bins in the data structure of a second type; and

for each bin comprising two or more data structures of a first type;

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

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

adding 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, removing at least one of the two or more data structures of a first type from their respective bin of the plurality of bins.