Method for generating a dataset structure for location-based services and method and system for providing location-based services to a mobile device
원문보기
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-007/00
G06F-017/30
H04W-004/02
H04L-029/08
출원번호
US-0423158
(2013-04-09)
등록번호
US-9996552
(2018-06-12)
국제출원번호
PCT/EP2013/057403
(2013-04-09)
국제공개번호
WO2014/166527
(2014-10-16)
발명자
/ 주소
Dobre, Dan
Vieira Dos Santos, Nuno Filipe
출원인 / 주소
NEC Corporation
대리인 / 주소
Leydig, Voit & Mayer, Ltd.
인용정보
피인용 횟수 :
0인용 특허 :
3
초록▼
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.
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.
대표청구항▼
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
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. 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 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 provide 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, andadding, for each of the determined tiles, the new area of interest to the first and second datasets. 7. The method according to claim 1, wherein based on one of the servers being removed, adapting the consistent hashing function and re-assigning tiles of the removed server using the adapted hashing function. 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, anddetermining location changes based on the current set and the previous location. 9. The method according to claim 8, 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 not being contained in an area of interest of the first or second datasets. 10. The method according to claim 8, 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. 11. The method according to claim 10, 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, andcalculating the set Exited by subtracting the current set from the previous set, wherein the set Exited contains each area of interest of the previous set which is not contained in the current set. 12. The method according to claim 10, wherein the previous location does not fall on the current tile, and 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 based on the previous set. 13. The method according to claim 12, 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 not being contained in a part of the area of interest contained in the first or second datasets stored at the previous server. 14. The method according to claim 8, wherein the method further comprises triggering a location-related action based on the determined location changes. 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, andone 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, anddetermining 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. 16. The system according to claim 15, wherein the one or more hardware processors are further configured to provide for execution of the following steps: determining a previous tile, wherein the previous tile is one of the plurality of tiles and contains the previous location,determining one of the servers associated with the previous tile based on the consistent hashing function, andcalculating location changes of the mobile client according to the previous location and the current location based on the first and second datasets. 17. The system according to claim 15, wherein the servers are organized in a ring. 18. The system according to claim 17, 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. 19. The system according to claim 15, wherein, based on one of the servers being removed, one or more of the tiles associated with the removed server is associated, based on the consistent hashing function, with at least one of the other servers. 20. The system according to claim 15, wherein the previous location and the current location are transmitted to the one or more hardware processors by the mobile client.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (3)
Kellermeier, Dirk; Lautenbach, Frank; Lorenz, Simon, Infrastructure and method for geography based vehicle alert.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.