Method for generating a dataset structure for location-based services and method and system for providing location-based services to a mobile device
First Claim
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 and at least two of the tiles are associated to different ones of the servers, the consistent hashing function providing at least one unique link between each of the tiles and the at least one of the servers,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, andstoring, for each of the tiles, the first and second datasets at the at least one of the servers associated to the tile based on the at least one unique link.
3 Assignments
0 Petitions
Accused Products
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.
17 Citations
20 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 and at least two of the tiles are associated to different ones of the servers, the consistent hashing function providing at least one unique link between each of the tiles and the at least one of the servers, 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 based on the at least one unique link. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. 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 tile, 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, the consistent hashing function providing at least one unique link between each tile of the plurality of tiles and at least one of the plurality of servers, wherein at least two of the tiles are associated to different ones of the servers and 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 based on the at least one unique link, 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. - View Dependent Claims (9, 10, 11, 12, 13, 14)
-
-
15. 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 the 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 and at least two of the tiles are associated to different ones of the servers, and one or more hardware processors, which alone or in combination, are configured to provide for execution of the following steps; 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, based on the consistent hashing function, a server associated with the current tile, the consistent hashing function providing at least one unique link between each tile of the plurality of tiles and at least one of the plurality of servers, and determining location changes of the mobile client according to the previous location and the current location based on the first and second datasets and the at least one unique link. - View Dependent Claims (16, 17, 18, 19, 20)
-
Specification