Blind evaluation of nearest neighbor queries wherein locations of users are transformed into a transformed space using a plurality of keys

• US 8,099,380 B1
• Filed: 05/29/2008
• Issued: 01/17/2012
• Est. Priority Date: 05/29/2007
• Status: Active Grant

• Current Assignee: University of Southern California
• Original Assignee: University of Southern California
• Inventors: Shahabi, Cyrus, Khoshgozaran, Jaffar, Shirani-Mehr, Houtan
• Primary Examiner(s): Vincent, David
• Application Number:
  US12/129,629
• Time in Patent Office: 1,328 Days
• Field of Search: 455/404.2, 455/414.2, 455/440, 455/456.1, 455/456.2, 455/456.3, 455/456.4, 455/456.5, 455/456.6, 455/457, 706/12, 706 45- 48, 706/62
• US Class Current: 706/62
• CPC Class Codes: H04W 12/02 Protecting privacy or anonymity, e.g. protecting personally identifiable information [PII]
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds

Abstract

Systems and techniques are described for blind evaluation of nearest neighbor queries. Locations of multiple users in an original space are received. The locations in the original space are encoded into encoded locations in a transformed space. A relative proximity of the encoded locations in the transformed space is maintained after the encoding. Multiple keys corresponding to the multiple users are generated. Each key enables a reverse transformation of an encoded user location in the transformed space to an original user location in the original space. The multiple keys are provided to the corresponding multiple users, and the encoded locations in the transformed space are provided to a device. An order of computations required to reverse transform the encoded locations in the transformed space to the locations in the original space in the absence of a key is greater than a computational threshold.

Claims

1. A method comprising:

receiving locations of a plurality of users in an original space;

encoding, by a computer, the locations in the original space into encoded locations in a transformed space using a transformation parameter, wherein a relative proximity of the locations in the original space is maintained in the transformed space after the encoding;

generating a plurality of keys corresponding to the plurality of users, each key including the transformation parameter used to encode the locations and enabling a reverse transformation of an encoded user location in the transformed space to an original user location in the original space;

providing the plurality of keys to the corresponding plurality of users; and

providing the encoded locations in the transformed space to a device, wherein an order of computations required to reverse transform the encoded locations in the transformed space to the locations in the original space in the absence of one of the plurality of keys is greater than a computational threshold.

2. The method of claim 1, further comprising storing the encoded locations in the transformed space.

3. The method of claim 2, wherein providing the encoded locations in the transformed space to the device comprises providing the device access to the stored encoded locations.

4. The method of claim 1, wherein the relative proximity of the locations is maintained in the transformed space when a probability that a proximity of the encoded locations in the transformed space is the same as a proximity of the locations in the original space is high.

5. The method of claim 1, wherein providing the plurality of keys to the corresponding plurality of users comprises causing the plurality of keys to be stored in corresponding secure locations by the plurality of users.

6. The method of claim 1, wherein the plurality of keys is are multiple copies of the same key.

7. The method of claim 1, further comprising encoding the locations in the original space into encoded locations in the transformed space using Hilbert curves.

8. The method of claim 7, wherein the computational threshold is proportional to a curve order of the Hilbert curves.

9. The method of claim 7, further comprising generating the plurality of keys based on starting points, Hilbert curve orientation, Hilbert curve order, and Hilbert curve scale factor.

10. A system comprising:

means for receiving locations of a plurality of users in an original space;

means for encoding the locations in the original space into encoded locations in a transformed space using a transformation parameter, wherein a relative proximity of the locations in the original space is maintained in the transformed space after the encoding;

means for generating a plurality of keys corresponding to the plurality of users, each key including the transformation parameter used to encode the locations and enabling a reverse transformation of an encoded user location in the transformed space to an original user location in the original space;

means for providing the plurality of keys to the corresponding plurality of users; and

means for providing the encoded locations in the transformed space to a device, wherein an order of computations required to reverse transform the encoded locations in the transformed space to the locations in the original space in the absence of one of the plurality of keys is greater than a computational threshold.

11. The system of claim 10, further comprising means for storing the encoded locations in the transformed space.

12. The system of claim 11, wherein the means for providing the encoded locations in the transformed space to the device comprises means for providing the device access to the stored encoded locations.

13. The system of claim 10, wherein the relatively proximity of the locations is maintained in the transformed space when a probability that a proximity of the encoded locations in the transformed space is the same as a proximity of the locations in the original space is high.

14. The system of claim 10, wherein the means for providing the plurality of keys to the corresponding plurality of users comprises means for causing the plurality of keys to be stored in corresponding secure locations by the plurality of users.

15. The system of claim 10, wherein the plurality of keys are multiple copies of the same key.

16. The system of claim 10, further comprising means for encoding the locations in the original space into encoded locations in the transformed space using Hilbert curves.

17. The system of claim 16, wherein the computational threshold is proportional to a curve order of the Hilbert curves.

18. The system of claim 16, further comprising means for generating the plurality of keys based on starting points, Hilbert curve orientation, Hilbert curve order, and Hilbert curve scale factor.

25. The system of claim 17, wherein the Hilbert curve is shifted by one unit in both X and Y directions.

19. A system comprising:

an encoding device configured to

encode locations of a plurality of users in an original space into encoded locations in a transformed space using a transformation parameter,

generate a key that includes the transformation parameter used to encode the locations, the key to enable a reverse transformation of an encoded user location in the transformed space to an original user location in the original space,

provide the key to each user of the plurality of users, and

provide the encoded locations in the transformed space; and

a server configured to

receive the encoded locations in the transformed space,

receive a query from a user to identify one or more nearest users, the user and the one or more nearest users included in the plurality of users,

resolve the query to identify encoded locations in the transformed space of the one or more nearest users based on an encoded location in the transformed space of the user, and

provide the identified encoded locations to the user.

20. The system of claim 19, wherein the query is a K-nearest neighbor (KNN) query, and wherein the server is configured to resolve the KNN query using a Hilbert curve.

21. The system of claim 19, wherein the query is a two-dimensional (2-D) range query, and wherein the server is configured to resolve the 2-D range query by transforming the 2-D range query into a plurality of one-dimensional (1-D) ranges in the transformed space.

22. The system of claim 19, wherein the server is configured to resolve the query using a dual curve obtained by replicating a Hilbert curve.

23. The system of claim 22, wherein the Hilbert curve is rotated and shifted to obtain the dual curve.

24. The system of claim 23, wherein the Hilbert curve is rotated by 90 degrees.