METHOD FOR GENERATING A DATASET STRUCTURE FOR LOCATION-BASED SERVICES AND METHOD AND SYSTEM FOR PROVIDING LOCATION-BASED SERVICES TO A MOBILE DEVICE

• US 20150227553A1
• Filed: 04/09/2013
• Published: 08/13/2015
• Est. Priority Date: 04/09/2013
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Europe Ltd
• Inventors: Dobre, Dan, Vieira Dos Santos, Nuno Filipe
• Granted Patent: US 9,996,552 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences

Abstract

A method for generating a dataset structure for location-based services includes partitioning a geographical area, including areas of interest, into tiles. The tiles are associated with servers, wherein each of the tiles is associated with at least one server based on a consistent hashing function. For each of the tiles, a first dataset is generated which includes the areas of interest intersecting the tile. The areas of interest of the first dataset are trimmed by edges of the tile or completely contained in the tile. For each of the tiles, a second dataset is generated which includes overflowed parts. Each of the overflowed parts is part of an areas of interest of the first dataset, is trimmed by an edge of the tile and is located outside of the tile. For each of the tiles, the first and second datasets are stored at the server(s) associated to the tile.

Claims

1. A method for generating a dataset structure for location-based services, comprising:

partitioning a geographical area, including a plurality of areas of interest, into a plurality of tiles,

associating the tiles with a plurality of servers, wherein each of the tiles is associated with at least one of the servers based on a consistent hashing function,

generating, for each of the tiles, a first dataset of the dataset structure including the areas of interest intersecting the tile, wherein the areas of interest of the first dataset are trimmed by edges of the tile or completely contained in the tile,

generating, for each of the tiles, a second dataset of the dataset structure including overflowed parts, wherein each of the overflowed parts is part of one of the areas of interest of the first dataset, is trimmed by an edge of the tile and is located outside of the tile, and

storing, for each of the tiles, the first and second datasets at the at least one of the servers associated to the tile.

2. The method according to claim 1, wherein the areas of interest are geofences and the location-based services are provided by a geofencing system using based on the first and second datasets of the dataset structure.

3. The method according to claim 1, wherein the tiles are quadratic, rectangular, hexagonal, octagonal or have another polygonal shape.

4. The method according to claim 1, wherein the consistent hashing function employs a load balancing scheme.

5. The method according to claim 1, wherein a plurality of hashing functions are used, to associate a tile with two or more servers to allow replicas of elements of the first and second datasets.

6. The method according to claim 1, further comprising inserting an new area of interest to the geographical area, the inserting comprises:

determining each tile of the plurality of tiles which intersects the new area of interest,

mapping the new area of interest to the determined tiles, and

adding, for each of the determined tiles, the new area of interest to the first and second datasets.

7. A method for providing location-based services to a mobile client within a geographical area, based on a dataset structure generated at a plurality of servers, wherein the geographical area comprises a plurality of areas of interest and is partitioned into a plurality of tiles, wherein the dataset structure includes a first dataset including the areas of interest intersecting each tile, wherein the areas of interest of the first dataset are trimmed by edges of each tile or completely contained in each tile, and a second dataset of the dataset structure including overflowed parts, wherein each of the overflowed parts is part of one of the areas of interest of the first dataset, is trimmed by an edge of the tile and is located outside of the file, comprising:

receiving location information of the mobile client, wherein the location information comprises a previous location and a current location of the mobile client determined at two consecutive location updates,

determining a current tile, wherein the current tile is one of the plurality of tiles and contains the current location,

determining a current server associated with the current tile based on a consistent hashing function, wherein the current server is one of the plurality of servers,

accessing, at the current server, the first and second datasets of the dataset structure,

determining, by the current server, a current set of areas of interest, wherein the current set comprises each of the areas of interest of the first dataset which contain the current location, and

determining location changes based on the current set and the previous location.

8. The method according to claim 7, wherein the determining location changes includes determining a set Entered, wherein the set Entered comprises each of the areas of interest which is entered by the mobile client moving from the previous location to the current location, wherein the determining the set Entered comprises:

adding one of the areas of interest of the current set to the set Entered based on the previous location being not contained in a part of the area of interest contained in the first or second datasets.

9. The method according to claim 7,wherein the determining location changes includes determining a set Exited, wherein the set Exited comprises each of the areas of interest which is exited by the mobile client moving from the previous location to the current location.

10. The method according to claim 9, wherein, based on the previous location falling on the current tile, the determining the set Exited is performed by the current server, comprising:

determining a previous set of areas of interest, wherein the previous set comprises each of the areas of interest of the first dataset which contain the previous location and

calculating the set Exited by subtracting the current set from the previous set, wherein the set Exited contains each of the areas of interest of the previous set which are not contained in the current set.

11. The method according to claim 9, wherein, based on the previous location not falling on the current tile, the determining the set Exited comprises:

determining a previous tile, wherein the previous tile is one of the plurality of tiles and contains the previous location,

determining, based on the consistent hashing function, a previous server associated with the previous tile,

receiving the previous location and the current location at the previous server,

accessing, at the previous server, the first and second datasets of the dataset structure,

determining, by the previous server, a previous set of areas of interest, wherein the previous set comprises each of the areas of interest of the first dataset which contain the previous location, and determining the set Exited using said the previous set.

12. The method according to claim 11, wherein the determining the set Exited comprises:

adding one of the areas of interest of the previous set to the set Exited, based on the current location being not contained in a part of the area of interest contained in the first or second datasets stored at the previous server.

13. The method according to claim 7, wherein the method further comprises triggering a location-related action based on the determined location changes.

14. A system for providing location-based services to a mobile client within a geographical area, based on a dataset structure generated, wherein the geographical area comprises a plurality of areas of interest and is partitioned into a plurality of tiles, wherein the dataset structure includes a first dataset including the areas of interest intersecting each tile, wherein the areas of interest of the first dataset are trimmed by edges of each tile or completely contained in each tile, and a second dataset of the dataset structure including overflowed parts, wherein each of the overflowed parts is part of one of he areas of interest of the first dataset, is trimmed by an edge of the tile and is located outside of the tile, the system comprising:

a plurality of servers, wherein each of the servers is associated with at least one tile of the plurality of tiles based on a consistent hashing function,

means for receiving location information of the mobile client, wherein the location information comprises a previous location and a current location of the mobile client determined at two consecutive location update,

means for determining a current tile, wherein the current tile is one of the plurality of tiles and contains the current location,

means for determining, based on the consistent hashing function, a server associated with the current tile, and

means for determining location changes of the client using the previous location and the current location based the first and second datasets.

15. The system according to claim 14, further comprising:

means for determining a previous tile, wherein the previous tile is one of the plurality of tiles and contains the previous location,

means for determining a server associated with the previous tile using the consistent hashing function, and

means for calculating location changes of the client using the previous location and the current location based on the first and second datasets.

16. The system according to claim 14, wherein the servers are organized in a ring.

17. The system according to claim 16, wherein the servers are configured such that, at adding a new server to the ring, several of the tiles associated with one or both neighboring servers, are re-assigned with the new server.

18. The system according to claim 14, wherein, based on one of the servers being removed, one or more of the tiles associated with the removed server is associated, using the consistent hashing function, with at least one of the other servers.

19. The system according to claim 14, wherein the previous location and the current location are transmitted to the means for receiving location information by the mobile client.