Computer-implemented systems and methods for comparing and associating objects

• US 8,924,388 B2
• Filed: 12/06/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/099,661
• Publication Number:
  US 20140280155A1
• Time in Patent Office: 389 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 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 that includes at least some of the first plurality of properties, the method comprising the following operations performed by one or more processors:

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; and

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.

2. The method of claim 1, further comprising:

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

3. The method of claim 1, further comprising:

reading the plurality of objects from at least one database.

4. The method of claim 3, further comprising determining if the slugs within the bin corresponding to the slug for the first object match the slug for the first object comprises the following operations performed by one or more processors:

inputting for each slug in the bin corresponding to the slug for the first object, the each slug and its corresponding object into a multimap, wherein the slug for the each object is a key to the multimap and its corresponding object is a value to the multimap; and

associating objects in the multimap whose key matches the slug for the first object.

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

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

7. The method of claim 5, 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.

8. 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.

9. 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.

10. A method for associating objects within one or more groups of 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 within a group of objects comprising matching data in corresponding properties for a second plurality of properties that includes at least some of the first plurality of properties, 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 the second plurality of properties from the object; and

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

inputting 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

associating the objects stored as values for each multimap key with two or more corresponding values.

11. The method of claim 10, further comprising:

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

12. The method of claim 11, further comprising:

reading the plurality of objects from at least one database.

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

14. The method of claim 13, wherein each 2-bit counter is a saturation counter.

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

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

17. The method of claim 15, 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.

18. The method of claim 15, wherein the number of properties in the first plurality of properties equals the number of properties in the second plurality of properties.

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

20. A system 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 that includes at least some of the first plurality of properties, 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;

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; and

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.