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

• US 8,560,512 B2
• Filed: 07/18/2002
• Issued: 10/15/2013
• Est. Priority Date: 07/18/2002
• Status: Expired due to Fees

• Current Assignee: Micro Focus LLC (Open Text Corporation)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Eshghi, Kave, Suermondt, Henri Jacques, Kirshenbaum, Evan R.
• Primary Examiner(s): Saeed, Usmaan
• Assistant Examiner(s): Kim, Paul
• Application Number:
  US10/199,664
• Publication Number:
  US 20040015706A1
• Time in Patent Office: 4,107 Days
• Field of Search: 707/100, 701/209, 713/182, 340/988
• US Class Current: 707/706
• CPC Class Codes: H04L 2209/80 Wireless
• 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 of global positioning system (GPS) data, the method comprising:

gathering the plurality of sets of the GPS data with two handheld portable electronic devices while users carry the two handheld portable electronic devices;

partitioning a representation of each element of a plurality of sets of the GPS data into a series of segments;

repeating a matching process to determine if the users carrying the two handheld portable electronic devices were previously at a common geographical location comprising;

exchanging portions of the GPS data between the two handheld portable electronic devices by 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;

revealing results of the matching process at the two handheld portable electronic devices.

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 non-transitory 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 of global positioning system (GPS) data, the method comprising:

storing portions of the plurality of sets of the GPS data in two portable electronic devices that are handheld;

partitioning a representation of each element of a plurality of sets of the GPS data into a series of segments;

exchanging portions of the GPS data between the two portable electronic devices to determine if users transporting the two portable electronic devices have matching GPS data gathered over a common time period by;

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;

informing a user when the two portable electronic devices have matching GPS data gathered over the common time period.

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 handheld portable electronic device comprising:

a processor configured to partition into a series of segments a representation of each element of a set of global positioning system (GPS) data; and

a communications coupling;

wherein the processor (1) discloses to a second handheld portable electronic device via the communications coupling one of the segments from each of the elements that is a potential match with GPS data stored in the second handheld portable electronic device, (2) receives a disclosed segment of GPS data from the second handheld portable electronic device, and (3) removes from the potential matches those elements that do not match the disclosed segment of GPS data from the second handheld portable electronic device in order to determine if a user carrying the second handheld portable electronic device and a user carrying the handheld portable electronic device have matching GPS data for a common geographical location and time.

25. The handheld portable electronic device of claim 24, wherein the portable electronic device is selected from the group consisting of:

a global positioning system (GPS) receiver/recorder;

a personal digital assistant (PDA); and

a portable computing device.

26. The handheld portable electronic device of claim 24, 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.

27. The handheld portable electronic device of claim 24, wherein the portable electronic 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.

28. The handheld portable electronic device of claim 24, wherein the portable electronic device is further configured to apply a cryptographic hash to the elements.

29. The handheld portable electronic device of claim 28, 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.

30. The handheld portable electronic device of claim 25, wherein the portable electronic 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.

31. The handheld portable electronic device of claim 30, 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.

32. The handheld portable electronic device of claim 31, wherein each set represents at least one location which the corresponding object was near at a time corresponding to that set.

33. The handheld portable electronic device of claim 24, wherein the communication further includes specifying which of the segments is to be disclosed in a next repetition of the matching process.

34. The handheld portable electronic device of claim 24, 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.

35. The handheld portable electronic device of claim 24 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.

36. A method, comprising:

recording first global positioning system data points (GPS DP) during a time period in which a user carries a first portable electronic device (PED);

recording second GPS DP during the time period in which a user carries a second portable electronic device (PED);

transferring (1) a portion of the first GPS DP from the first PED to the second PED and (2) a portion of the second GPS DP from the second PED to the first PED to determine if the first and second portable electronic devices were at a common location during the time period; and

informing a user whether the first and second portable electronic devices were at the common location during the time period.

37. The method of claim 36 further comprising, determining if a match exists between the portion of the first GPS DP and the portion of the second GPS DP before exchanging more GPS data points between the first and second portable electronic devices.

38. The method of claim 36 further comprising, exchanging GPS data points between the first and second portable electronic devices to determine a city name for the common location and a calendar date for the time period.