System and method for providing proximity information

• US 9,351,116 B2
• Filed: 05/30/2013
• Issued: 05/24/2016
• Est. Priority Date: 05/30/2013
• Status: Active Grant

• Current Assignee: Hong Kong Baptist University
• Original Assignee: Hong Kong Baptist University
• Inventors: Xu, Jianliang, Hu, Haibo
• Primary Examiner(s): MELTON, TODD M
• Application Number:
  US13/905,456
• Publication Number:
  US 20140357299A1
• Time in Patent Office: 1,090 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 3/048 Interaction techniques based on graphical user interfaces [GUI]
• CPC Class Codes: G06F 3/0484 for the control of specific functions or operations, e.g. selecting or manipulating an object, an image or a displayed text element, setting a parameter value or selecting a range
• CPC Class Codes: G06Q 50/01 Social networking
• 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
• CPC Class Codes: H04W 4/21 for social networking applications

Abstract

A method for privacy-preserving proximity detection comprising a grid-and-hashing paradigm, an optimal grid overlay and multi-level grids, which increases the detection accuracy while saving the wireless bandwidth. Furthermore, the present invention also provided a client-side location update scheme and the server-side update handling procedure for continuous proximity detection. The present invention is efficient and scalable under various system parameters and user moving speeds, in mobile geo-social networks.

Claims

1. A method for providing proximity information comprising the step of:

processing a location data set having locations of a plurality of objects in a network space by applying a grid and hashing paradigm to the locations of the plurality of objects generating and continuously updating a proximity set arranged to represent one or more proximity relationships between the plurality of objects in the network space;

wherein the grid and hashing paradigm is arranged to transform the locations of the plurality of objects in the network space onto an optimal multi-layered grid model that is arranged to model the network space so as to generate a plurality of signatures each associated with a respective object in the optimal multi-layered grid model;

wherein the optimal multi-layered grid model includes two or more independent grid layers each having a plurality of cells representing a partition of the network space, the two or more grid layers being overlaid into multiple layers and onto the network space for modeling the network space;

wherein a dimension of the cells and/or a number of the two or more grid layers in the optimal multi-layered grid model is determined based on a desired level of service.

2. A method for providing proximity information in accordance with claim 1, wherein the plurality of signatures are compared to identify one or more proximity relationships between the plurality of objects in the network space.

3. A method for providing proximity information in accordance with claim 2, wherein the plurality of signatures are transformed from the location data set such that the locations of the plurality of objects in the network space are removed.

4. A method for providing proximity information in accordance with claim 3, wherein the grid and hashing paradigm includes a one way hashing function arranged to encode the locations of the plurality of objects in the network space into the plurality of signatures.

5. A method for providing proximity information in accordance with claim 4, wherein the plurality of signatures are arranged to be transmitted to a service provider from each of the plurality of objects operating within the network space.

6. A method for providing proximity information in accordance with claim 5, wherein the service provider is prevented from processing the plurality of signatures to determine the locations of the plurality of objects.

8. A method for providing proximity information in accordance with claim 1, wherein the two or more layers are overlaid randomly and/or are shifted with respect to each other along an X-axis and a Y-axis.

9. A method for providing proximity information in accordance with claim 8, wherein the two or more layers are shifted in accordance with one or more desired accuracy variables.

10. A method for providing proximity information in accordance with claim 9, wherein the plurality of cells are dynamically dimensioned based on the one or more desired accuracy variables.

11. A method for providing proximity information in accordance with claim 10, wherein the one or more desired accuracy variables include a maximum false-negative threshold or a resource usage factor.

12. A method for providing proximity information in accordance with claim 1, further comprising a step of:

updating the location data set to capture movements of the plurality of objects in the network space, wherein the step of updating the location data set includes;

scanning the plurality of signatures to determine a change of the one or more proximity relationships; and

whereupon the scan detects a change of the one or more proximity relationships, updating the location data set by requesting for an updated signature from one or more of the plurality of objects detected to be associated with the change.

13. A method for providing proximity information in accordance with claim 12, wherein the optimal multi-layered grid model includes a lowest level grid layer being initially placed with objects having no proximity relationships and one or more grid layers above the lowest level grid layer which are initially placed with objects having one or more proximity relationships.

14. A method for providing proximity information in accordance with claim 13, wherein a dimension of the cells of the grid layers increases from the lowest level grid layer to a top level grid layer.

15. A method for providing proximity information in accordance with claim 14, wherein the plurality of cells in the top level grid layer is merged into a single cell that is dimensioned to cover the entire network space.

16. A method for providing proximity information in accordance with claim 15, wherein the location data set is updated when the scan detects a change of the one or more proximity relationships between the plurality of objects in an upper non-common layer of the optimal multi-layered grid model, the upper non-common layer being one grid layer below a layer of the optimal multi-layered grid model in which there is one or more proximity relationships between the plurality of objects.

17. A method for providing proximity information in accordance with claim 16, wherein the location data set is updated when the scan detects a change of the one or more proximity relationships between the plurality of objects in a common social group.

7. A method for providing proximity information in accordance with 1, wherein the placement of the two or more grid layers onto the network space is unknown to a service provider operating within the network space.

18. A system for providing proximity information comprising

a processor for processing a location data set having locations of a plurality of objects in a network space by applying a grid and hashing paradigm to the locations of the plurality of objects and for generating and continuously updating a proximity set arranged to represent one or more proximity relationships between the plurality of objects in the network space;

wherein the grid and hashing paradigm is arranged to transform the locations of the plurality of objects in the network space onto an optimal multi-layered grid model arranged to model the network space so as to generate a plurality of signatures each associated with a respective object in the optimal multi-layered grid model;

wherein the optimal multi-layered grid model includes two or more independent grid layers each having a plurality of cells representing a partition of the network space, the two or more grid layers being overlaid into multiple layers and onto the network space for modeling the network space;

wherein a dimension of the cells and/or a number of the two or more grid layers in the optimal multi-layered grid model is determined based on a desired level of service.