Computer-implemented systems and methods for comparing and associating objects

• US 8,924,389 B2
• Filed: 12/24/2013
• Issued: 12/30/2014
• 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/140,415
• Publication Number:
  US 20140280252A1
• Time in Patent Office: 371 Days
• Field of Search: None
• US Class Current: 707/737
• 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. A method for identifying unique 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 method comprising the following operations performed by one or more processors:

executing, for each object within the plurality of objects, the following;

creating a slug for the object, the slug comprising a second plurality of properties from the object that includes at least some of the first plurality of properties; and

inputting the slug for the object into a counting Bloom filter;

identifying for each created slug whose corresponding bin within the counting Bloom filter has a count value equal to 1, the object associated with the slug as unique within the plurality of objects;

inputting, using at least one processor, for each created slug, the slug and its corresponding object into a multimap, if a bin within the counting Bloom filter corresponding to the slug has a count value greater than 1, wherein the slug is a key to the multimap and the object is a value to the multimap; and

identifying for each multimap key with one value, the object associated with the slug stored as the key as unique within the plurality of objects.

2. The method of claim 1, further comprising:

sizing the counting Bloom filter for a predetermined error rate and number of objects within the plurality of objects.

3. The method of claim 2, further comprising:

reading the plurality of objects from at least one database.

4. The method of claim 3, wherein each entry in the counting Bloom filter comprises a 2-bit counter.

5. The method of claim 4, wherein each 2-bit counter is a saturation counter.

6. The method of claim 5, wherein the number of properties in the first plurality of properties equals the number of properties in the second plurality of properties.

7. The method of claim 5, wherein the number of properties in the first plurality of properties is greater than the number of properties in the second plurality of properties.

8. The method of claim 1, wherein the slug comprises a concatenation of two or more strings separated by a delimiter between each concatenated string.

9. The method of claim 8, wherein the delimiter comprises a character that is not otherwise present in the strings that were concatenated.

10. The method of claim 8, wherein the delimiter comprises a sequence of two or more characters and the sequence of two or more characters is not present in any of the two or more strings that were concatenated.

11. A system for identifying unique 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 system comprising:

a memory device that stores a set of instructions; and

at least one processor that executes the set of instructions to perform the following operations;

execute, for each object within the plurality of objects, the following;

create a slug for the object, the slug comprising a second plurality of properties from the object that includes at least some of the first plurality of properties; and

input the slug for the object into a counting Bloom filter;

identify, for each created slug whose corresponding bin within the counting Bloom filter has a count value equal to 1, the object associated with the slug as unique within the plurality of objects;

input, for each created slug, the slug and its corresponding object into a multimap, if a bin within the counting Bloom filter corresponding to the slug has a count value greater than 1, wherein the slug is a key to the multimap and the object is a value to the multimap; and

identify, for each multimap key with one value, the object associated with the slug stored as the key as unique within the plurality of objects.

12. The system of claim 11, wherein the at least one processor further executes the set of instructions to perform the following operation:

sizing the counting Bloom filter for a predetermined error rate and number of objects within the plurality of objects.

13. The system of claim 12, wherein the at least one processor further executes the set of instructions to perform the following operation:

reading the plurality of objects from at least one database.

14. The system of claim 13, wherein each entry in the counting Bloom filter comprises a 2-bit counter.

15. The system of claim 14, wherein each 2-bit counter is a saturation counter.

16. The system of claim 15, wherein the slug comprises a concatenation of two or more strings separated by a delimiter between each concatenated string.

17. The system of claim 16, wherein the delimiter comprises a character that is not otherwise present in the strings that were concatenated.

18. The system of claim 16, wherein the delimiter comprises a sequence of two or more characters and the sequence of two or more characters is not present in any of the two or more strings that were concatenated.

19. The system of claim 16, wherein the number of properties in the first plurality of properties equals the number of properties in the second plurality of properties.

20. The system of claim 16, wherein the number of properties in the first plurality of properties is greater than the number of properties in the second plurality of properties.