Systems and methods to identify a predefined geographical region in which a mobile device is located

• US 10,149,094 B2
• Filed: 08/14/2017
• Issued: 12/04/2018
• Est. Priority Date: 01/09/2015
• Status: Active Grant

• Current Assignee: InMarket Media, LLC
• Original Assignee: NinthDecimal, Inc. (InMarket Media, LLC)
• Inventors: Zhyshko, Yury
• Primary Examiner(s): Mizrahi, Diane
• Application Number:
  US15/676,871
• Publication Number:
  US 20170347231A1
• Time in Patent Office: 477 Days
• CPC Class Codes: H04W 16/18 Network planning tools
• CPC Class Codes: H04W 16/24 Cell structures
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/025 using location based information parameters
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

Systems and methods including a mobile device determining the coordinates of its location using a location determination system, such as a global positioning system. A database stores the identifiers of cells representative of predefined regions in a hierarchical grid system. A server computer or the mobile device converts the coordinates of the location to one or more cell identifiers at different grid resolution levels and searches the database to find a match between the cell identifiers representing the regions and the cell identifiers representing the location of the mobile device to determine one or more regions in which the mobile device is located. For example, the hierarchical grid system can be constructed in a longitude latitude space of location coordinates, with resolution levels aligned with decimal precision levels of the location coordinates; and the cell identifiers can be constructed from the digits of the longitude and latitude coordinates.

Claims

1. A method implemented in a computing device, the method comprising:

receiving, in the computing device, a set of coordinates of a location of a mobile device; and

determining, by the computing device, whether the set of coordinates of the location of the mobile device is within a predefined geographical boundary of a geographical region by;

converting, independent of the predefined geographical boundary of the geographical region, the set of coordinates into an identifier of a cell in a grid reference system, wherein convertibility of the set of coordinates to the identifier of the cell indicates that the location identified by the set of coordinates is within the cell in the grid reference system;

storing, in the computing device, a set of cell identifiers, each of the cell identifiers identifying a corresponding cell in the grid reference system that is within the predefined geographical boundary; and

determining, by the computing device, whether the set of cell identifiers stored for the geographical region includes the identifier of the cell converted from the set of coordinates, wherein the set of coordinates of the location of the mobile device is determined to be within the predefined geographical boundary of the geographical region in response to a determination that the set of cell identifiers stored for the geographical region includes the identifier of the cell converted from the set of coordinates.

2. The method of claim 1, wherein the set of coordinates of the location of the mobile device is determined to be not within the predefined geographical boundary of the geographical region in response to a determination that the set of cell identifiers stored for the geographical region does not include the identifier of the cell converted from the set of coordinates.

3. The method of claim 1, wherein the converting of the set of coordinates of the location into the identifier of the cell is performed without using a floating point number computation.

4. The method of claim 3, wherein the converting of the set of coordinates of the location into the identifier of the cell includes:

extracting a first integer from a longitude coordinate of the location according to a precision level;

extracting a second integer from a latitude coordinate of the location according to the precision level; and

combining the first integer and the second integer into the identifier of the cell.

5. The method of claim 4, wherein the precision level corresponds to a count of digits following a decimal point;

and the first integer is extracted to include digits of the longitude coordinate preceding the decimal point of the longitude coordinate and the count of digits of the longitude coordinate following the decimal point of the longitude coordinate.

6. The method of claim 4, wherein the precision level corresponds to a count of digits following a decimal point;

and the second integer is extracted to include digits of the latitude coordinate preceding the decimal point of the latitude coordinate and the count of digits of the latitude coordinate following the decimal point of the latitude coordinate.

7. The method of claim 1, wherein cells at a precision level in the grid reference system cover a surface area of the earth in columns according to longitude and in rows according to latitude.

8. The method of claim 7, wherein the converting of the set of coordinates of the location into the identifier of the cell includes:

converting, according to the precision level, a longitude coordinate of the location into a column identifier of the cells at the precision level in the grid reference system;

converting, according to the precision level, a latitude coordinate of the location into a row identifier of the cells at the precision level in the grid reference system; and

combining the column identifier and the row identifier into the identifier of the cell.

9. The method of claim 8, wherein the precision level corresponding to a number of digits following a decimal point;

and the column identifier is generated from digits of the longitude coordinate preceding a digit that is the number of digits after the decimal point in the longitude coordinate.

10. The method of claim 8, wherein the precision level corresponding to a number of digits following a decimal point;

and the row identifier is generated from digits of the latitude coordinate preceding a digit that is the number of digits after the decimal point in the latitude coordinate.

11. A non-transitory computer storage medium storing instructions which, when executed by a computing device, instruct the computing device to perform a method, the method comprising:

receiving, in the computing device, a set of coordinates of a location of a mobile device; and

determining, by the computing device, whether the set of coordinates of the location of the mobile device is within a predefined geographical boundary of a geographical region by;

converting, independent of the predefined geographical boundary of the geographical region, the set of coordinates into an identifier of a cell in a grid reference system, wherein convertibility of the set of coordinates to the identifier of the cell indicates that the location identified by the set of coordinates is within the cell in the grid reference system;

storing, in the computing device, a set of cell identifiers, each of the cell identifiers identifying a corresponding cell in the grid reference system that is within the predefined geographical boundary; and

determining, by the computing device, whether the set of cell identifiers stored for the geographical region includes the identifier of the cell converted from the set of coordinates, wherein the set of coordinates of the location of the mobile device is determined to be within the predefined geographical boundary of the geographical region in response to a determination that the set of cell identifiers stored for the geographical region includes the identifier of the cell converted from the set of coordinates.

12. The non-transitory computer storage medium of claim 11, wherein the converting of the set of coordinates of the location into the identifier of the cell is performed without using a floating point number computation.

13. The non-transitory computer storage medium of claim 12, wherein the converting of the set of coordinates of the location into the identifier of the cell includes:

extracting a first integer from a longitude coordinate of the location according to a precision level;

extracting a second integer from a latitude coordinate of the location according to the precision level; and

combining the first integer and the second integer into the identifier of the cell.

14. The non-transitory computer storage medium of claim 13, wherein the precision level corresponds to a count of digits following a decimal point;

and the first integer is extracted to include digits of the longitude coordinate preceding the decimal point of the longitude coordinate and the count of digits of the longitude coordinate following the decimal point of the longitude coordinate.

15. The non-transitory computer storage medium of claim 13, wherein the precision level corresponds to a count of digits following a decimal point;

and the second integer is extracted to include digits of the latitude coordinate preceding the decimal point of the latitude coordinate and the count of digits of the latitude coordinate following the decimal point of the latitude coordinate.

16. A computing device, comprising:

at least one microprocessor;

memory storing instructions which, executed by the at least one microprocessor, instruct the computing device to;

receive, in the computing device, a set of coordinates of a location of a mobile device; and

determine, by the computing device, whether the set of coordinates of the location of the mobile device is within a predefined geographical boundary of a geographical region by;

convert, independent of the predefined geographical boundary of the geographical region, the set of coordinates into an identifier of a cell in a grid reference system, wherein convertibility of the set of coordinates to the identifier of the cell indicates that the location identified by the set of coordinates is within the cell in the grid reference system;

store, in the computing device, a set of cell identifiers, each of the cell identifiers identifying a corresponding cell in the grid reference system that is within the predefined geographical boundary; and

determine, by the computing device, whether the set of cell identifiers stored for the geographical region includes the identifier of the cell converted from the set of coordinates, wherein the set of coordinates of the location of the mobile device is determined to be within the predefined geographical boundary of the geographical region in response to a determination that the set of cell identifiers stored for the geographical region includes the identifier of the cell converted from the set of coordinates.

17. The computing device of claim 16, wherein cells at a precision level in the grid reference system cover a surface area of the earth in columns according to longitude and in rows according to latitude.

18. The computing device of claim 17, wherein the set of coordinates of the location are converted into the identifier of the cell by:

converting, according to the precision level, a longitude coordinate of the location into a column identifier of the cells at the precision level in the grid reference system;

converting, according to the precision level, a latitude coordinate of the location into a row identifier of the cells at the precision level in the grid reference system; and

combining the column identifier and the row identifier into the identifier of the cell.

19. The computing device of claim 18, wherein the precision level corresponding to a number of digits following a decimal point;

and the column identifier is generated from digits of the longitude coordinate preceding a digit that is the number of digits after the decimal point in the longitude coordinate.

20. The computing device of claim 18, wherein the precision level corresponding to a number of digits following a decimal point;

and the row identifier is generated from digits of the latitude coordinate preceding a digit that is the number of digits after the decimal point in the latitude coordinate.