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,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.
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.
34 Citations
19 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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. - View Dependent Claims (8, 9, 10, 11, 12, 13)
-
-
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. - View Dependent Claims (15, 16, 17, 18, 19)
-
Specification