SYSTEM AND METHOD FOR PROVIDING PROXIMITY INFORMATION

• US 20140357299A1
• Filed: 05/30/2013
• Published: 12/04/2014
• 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
• Granted Patent: US 9,351,116 B2
• Time in Patent Office: Days
• US Class Current: 455/456.2
• 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 so as to generate a proximity set arranged to represent one or more proximity relationships between the one or more 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 a multi-layered grid model arranged to model the network space so as to generate a plurality of signatures each associated with each of the plurality of objects in the multi-layered grid model.

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 one or more 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 objects in the network space into the plurality of signatures.

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

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

7. A method for providing proximity information in accordance with claim 1, wherein the multi-layered grid model includes one or more grid layers each having a plurality of cells to represent one or more partitions of the network space and are overlaid onto the network space so as to model the network space.

14. 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 objects in the network space,

wherein the step of updating the location data includes;

scanning the plurality of signatures associated with each of the plurality of objects in the multi-layered grid model to determine one or more changes with the one or more proximity relationships; and

whereupon the scan detects one or more changes between the one or more proximity relationships between the one or more objects in the multi-layered grid model, updating the location data set by requesting for an updated signature from the one or more objects detected to have one or more changes between the one or more proximity relationships of the one or more objects.

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

16. A method for providing proximity information in accordance with claim 15, wherein a dimension of each cell of each grid overlay increases at each grid overlay layer from the lowest level grid overlay to a top level grid overlay.

17. A method for providing proximity information in accordance with claim 16, wherein the top level grid overlay includes a single cell dimensioned to cover the entire network space.

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

19. A method for providing proximity information in accordance with claim 18, wherein the location data set is updated when upon the scan detects the one or more changes between the one or more proximity relationships between the one or more objects in a common social group.

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

9. A method for providing proximity information in accordance with claim 8, wherein the one or more grids are overlaid into multiple layers to define the multi-layered grid model.

10. A method for providing proximity information in accordance with claim 9, wherein the one or more grids are overlaid randomly or by shifting one or more grids on X-axis and Y-axis to form multiple layers of the one or more grids.

11. A method for providing proximity information in accordance with claim 10, wherein the one or more grids are shifted in accordance with one or more desired accuracy variables.

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

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

20. 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 so as to generate a proximity set arranged to represent one or more proximity relationships between the one or more 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 a multi-layered grid model arranged to model the network space so as to generate a plurality of signatures each associated with each of the plurality of objects in the multi-layered grid model.