Finding matching locations, trajectories or attributes while maintaining privacy of non-matching information

• US 20040015706A1
• Filed: 07/18/2002
• Published: 01/22/2004
• Est. Priority Date: 07/18/2002
• Status: Active Grant

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Kirshenbaum, Evan R., Suermondt, Henri Jacques, Eshghi, Kave
• Granted Patent: US 8,560,512 B2
• Time in Patent Office: Days
• US Class Current: 713/189
• CPC Class Codes: H04L 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• CPC Class Codes: H04L 9/3239 involving non-keyed hash functions, e.g. modification detection codes [MDCs], MD5, SHA or RIPEMD
• CPC Class Codes: H04L 9/3271 using challenge-response

Abstract

A method and an apparatus for matching elements within sets of trajectories, locations or other attributes without revealing the entire sets. The elements are partitioned into segments. A rotating selection is made among the sets and one segment of each potentially matching element is newly disclosed from the selected set. Optionally, the sets are cryptographically hashed, using, for example, a MD5 hash or a SHA-1 hash. Optionally, the sets are represented as tries, and successively lower levels within the tries are newly disclosed from potentially matching elements as the disclosing set rotates. Optionally, the sets are encoded, using: a grid of longitude and latitude; a spatial temporal grid; a overlapping spatial grid; a temporal grid; a set of cities; a set of countries; a set of names of places; or a set of attributes. Optionally, the matching process is repeated while refining the encoding. Optionally, negotiations determine what encoding or cryptographic hash is used.

Claims

1. A method of finding elements that match across a plurality of sets, the method comprising:

partitioning a representation of each element of a plurality of sets into a series of segments; and

repeating a matching process comprising;

disclosing one of the segments from each element that is from a selected one of the sets and that is a potential match;

removing from the potential matches those elements that do not match the disclosed segment; and

rotating which among the sets is the selected set.

2. The method of claim 1, and further comprising encoding the elements, wherein the encoding is selected from the group consisting of:

a grid of longitude and latitude;

a grid of longitude and latitude with overlapping cells;

a spatial temporal grid;

a spatial grid;

a temporal grid;

a set of cities;

a set of countries;

a set of names of places; and

a set of attributes.

3. The method of claim 1, further comprising:

negotiating a particular encoding; and

encoding the elements, the encoding being in accordance with the particular encoding.

4. The method of claim 1, and further comprising applying a cryptographic hash to the elements.

5. The method of claim 4, wherein the cryptographic hash is selected from the group consisting of:

an MD2 hash;

an MD4 hash;

an MD5 hash;

a hash according to a version of an ISO/IEC 10118 standard; and

a hash according to a version of a FIPS 180 standard.

6. The method of claim 4, and further comprising negotiating the cryptographic hash.

7. The method of claim 1, and further comprising:

selecting within a plurality of ordered sequences of sets of elements those sets that have corresponding positions within the sequences; and

applying the partitioning and the matching to the sets with corresponding positions.

8. The method of claim 7, wherein each of the sequences represents a temporarily ordered trajectory of an object that corresponds to that sequence, and the partitioning and the matching determine when the objects have been in corresponding locations.

9. The method of claim 8, wherein each set represents at least one location which the corresponding object was near at a time corresponding to that set.

10. The method of claim 1, wherein the matching process further comprises specifying which of the segments is to be disclosed in a next repetition of the matching.

11. The method of claim 1, and further comprising:

representing each of the sets as a trie;

wherein the potentially matching segment that is disclosed corresponds to a node at a next lower level of the trie that represents the selected set.

12. The method of claim 1, and further comprising:

encoding, according to a particular encoding, each of the elements; and

after the matching process, refining the particular encoding, repeating the encoding according to the particular encoding as refined, and repeating the matching process.

13. The method of claim 12, and further comprising negotiating the particular encoding and the refining of the particular encoding.

14. A program storage medium readable by a computer, embodying a program of instructions executable by the computer for controlling a method of finding matching elements within a plurality of sets, the method comprising:

partitioning a representation of each element of a plurality of sets into a series of segments; and

repeating a matching process comprising;

disclosing one of the segments from each element that is from a selected one of the sets and that is a potential match;

removing from the potential matches those elements that do not match the disclosed segment; and

rotating which among the sets is the selected set.

15. The medium of claim 14, wherein the method further comprises encoding the elements, wherein the encoding is selected from the group consisting of:

a grid of longitude and latitude;

a grid of longitude and latitude with overlapping cells;

a spatial temporal grid;

a spatial grid;

a temporal grid;

a set of cities;

a set of countries;

a set of names of places; and

a set of attributes.

16. The medium of claim 14, wherein the method further comprises applying a cryptographic hash to the elements.

17. The medium of claim 16, wherein the cryptographic hash is selected from the group consisting of:

an MD2 hash;

an MD4 hash;

an MD5 hash;

a hash according to a version of an ISO/IEC 10118 standard; and

a hash according to a version of a FIPS 180 standard.

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

forming a plurality of ordered sequences of sets of elements; and

applying the partitioning and the matching to the sets having corresponding positions within each of the sequences.

19. The medium of claim 18 wherein each of the sequences represents a temporarily ordered trajectory of an object that corresponds to that sequence, and the partitioning and the matching determine when the objects have been in corresponding locations.

20. The medium of claim 19, wherein each set represents at least one location which the corresponding object was near at a time corresponding to that set.

21. The medium of claim 14, wherein the matching process further comprises specifying which of the segments is to be disclosed in a next repetition of the matching.

22. The medium of claim 14, wherein the method further comprises representing each of the sets as a trie, and wherein the potentially matching segment that is disclosed corresponds to a node at a next lower level of the trie that represents the selected set.

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

encoding, according to a particular encoding, each of the elements; and

after the matching process, refining the particular encoding, repeating the encoding according to the particular encoding as refined, repeating the initialization and repeating the matching process.

24. A means for participating in a process to find matching elements within a plurality of sets, the means comprising:

a processing means for partitioning into a series of segments a representation of each element of a set that corresponds to the processing means; and

a means for communicating to and from the processing means;

wherein processing means is further a means for, when the processing means is a selected processing means, disclosing via the communications means one of the segments from each of the elements that is a potential match, and further a means for, when the processing means is not the selected processing means, removing from the potential matches those elements that that do not match a disclosed segment received via the communications means.

25. A device configured to participate in a process to find matching elements within a plurality of sets, the system comprising:

a processor configured to partition into a series of segments a representation of each element of a set that corresponds to the processor; and

a communications coupling;

wherein the processor is further configured to disclose, when the processor is a selected processor, via the communications coupling one of the segments from each of the elements that is a potential match, and to remove, when the processor is not the selected processor, from the potential matches those elements that do not match a disclosed segment received via the communications coupling.

26. The system of claim 25, wherein the device is selected from the group consisting of:

a global positioning system (GPS) receiver/recorder;

a personal computer (PC);

a personal digital assistant (PDA);

a portable computing device;

a server; and

a computer system.

27. The system of claim 25, wherein the coupling is selected from the group consisting of:

the Internet;

a private intranet;

an infrared (IR) communications channel;

a wireless communications channel;

a serial bus;

a parallel bus;

a local area network (LAN);

a wide area network (WAN);

a modem;

a public telephone switch network (PSTN); and

a server.

28. The system of claim 25, wherein the device is further configured to encode the elements, the encoding being selected from the group consisting of:

a grid of longitude and latitude;

a grid of longitude and latitude with overlapping cells;

a spatial temporal grid;

a spatial grid;

a temporal grid;

a set of cities;

a set of countries;

a set of names of places; and

a set of attributes.

29. The system of claim 25, wherein the device is further configured to apply a cryptographic hash to the elements.

30. The system of claim 29, wherein the cryptographic hash is selected from the group consisting of:

an MD2 hash;

an MD4 hash;

an MD5 hash;

a hash according to a version of an ISO/IEC 10118 standard; and

a hash according to a version of a FIPS 180 standard.

31. The system of claim 26, wherein the device is further configured to:

form a plurality of ordered sequences of sets of elements; and

apply the partitioning and the matching to the sets having corresponding positions within each of the sequences.

32. The system of claim 31, wherein each of the sequences represents a temporarily ordered trajectory of an object that corresponds to that sequence, and the partitioning and the matching determine when the objects have been in corresponding locations.

33. The system of claim 32, wherein each set represents at least one location which the corresponding object was near at a time corresponding to that set.

34. The system of claim 25, wherein the communication further includes specifying which of the segments is to be disclosed in a next repetition of the matching process.

35. The system of claim 25, wherein the devices are further configured to represent each of the sets as a trie and wherein the potentially matching segment that is disclosed corresponds to a node at a next lower level of the trie that represents the selected set.

36. The system of claim 25 wherein the devices are further configured to encode, according to a particular encoding, each of the elements and, after the matching process, to refine the particular encoding, to repeat the encoding according to the particular encoding as refined, and to repeat the matching process.