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

• US 9,307,360 B1
• Filed: 01/09/2015
• Issued: 04/05/2016
• 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:
  US14/593,947
• Time in Patent Office: 452 Days
• Field of Search: None
• US Class Current: 1/1
• 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:

storing, in the computing device, an identifier of a geographical region having a predefined geographical boundary;

storing, in the computing device, a set of cell identifiers, each of the cell identifiers identifying a cell that is determined to be within the predefined geographical boundary;

receiving, from a mobile device, a location of the mobile device;

converting, by the computing device, a set of coordinates of the location of the mobile device to a first cell identifier, wherein the set of coordinates includes longitude and latitude of the location, wherein the converting including

selecting digits from the longitude and the latitude of the location in accordance with a cell resolution level; and

combining the digits selected from the longitude and the latitude of the location into an integer representing the first cell identifier; and

determining, by the computing device, whether or not the location of the mobile device is within the geographical region based on searching the set of cell identifiers to determine whether or not the set has the first cell identifier;

wherein the selecting of the digits from the longitude and the latitude includes;

selecting digits from integer part of the longitude and a first number of digits from the longitude after the decimal point of the longitude to form an integer representation of the longitude at the cell resolution level; and

selecting digits from integer part of the latitude and the same first number of digits from the latitude after the decimal point of the latitude to form an integer representation of the longitude at the cell resolution level.

2. The method of claim 1, wherein the converting of the set of coordinates of the location includes:

generating two integers from longitude and latitude coordinates of the location according to a precision level; and

combining the two integers into the first cell identifier without using a floating point number computation.

3. The method of claim 2, wherein a cell identified by the first cell identifier is a rectangle area in a longitude latitude space of locations on the earth.

4. The method of claim 3, wherein a size of the cell is unambiguously determinable from the first cell identifier.

5. The method of claim 3, wherein longitude and latitude coordinates of a corner of the cell identified by the first cell identifier is unambiguously determinable from the first cell identifier itself.

6. The method of claim 1, wherein each respective cell identified by a corresponding cell identifiers in the set of cell identifiers is a square area in a longitude latitude space of locations on the earth.

7. The method of claim 6, wherein the set of cells identified by the set of cell identifiers has a plurality of cell sizes corresponding to a plurality of predetermined cell resolution levels.

8. The method of claim 7, wherein each cell resolution level of the plurality of predetermined cell resolution levels corresponds to a predetermined precision level of longitudes and latitudes of locations on the earth.

9. The method of claim 7, wherein each cell resolution level of the plurality of predetermined cell resolution levels corresponds to a precision to a predetermined digit after the decimal point in longitude and latitude coordinates of locations on the earth.

10. The method of claim 1, further comprising:

adding one to a digit of the integer representation of the latitude that corresponds to the tens digit of the latitude; and

providing a sign to the integer representation of the latitude according to the sign of the latitude.

11. The method of claim 10, further comprising:

providing a sign to the integer representation of the longitude according to the sign of the longitude; and

adding eighteen to digits of the integer representation of the longitude that corresponds to the hundreds digit and tens digit of the longitude, in view of the sign provided to the integer representation of the longitude.

12. The method of claim 11, further comprising:

adding one to the ones digit of the integer representation of the latitude without considering the sign of the integer representation of the latitude; and

adding one to the ones digit of the integer representation of the longitude without considering the sign of the integer representation of the longitude.

13. The method of claim 1, further comprising:

receiving data representing the predefined geographical boundary of the geographical region; and

identifying, in a hierarchy of cell grids, the set of cell identifiers that are determined to be within the predefined geographical boundary.

14. The method of claim 13, wherein each grid in the hierarchy of cell grids corresponds to a rectangle grid in longitude latitude space of locations on the earth with a predetermined resolution level.

15. The method of claim 14, wherein the predetermined resolution level corresponds to a precision level in a floating point representation of longitude and latitude coordinates.

16. A non-transitory computer storage medium storing instructions configured to instruct a computing device to perform a method, the method comprising:

storing, in the computing device, an identifier of a geographical region having a predefined geographical boundary;

storing, in the computing device, a set of cell identifiers, each of the cell identifiers identifying a cell that is determined to be within the predefined geographical boundary;

receiving, from a mobile device, a location of the mobile device;

converting, by the computing device, a set of coordinates of the location of the mobile device to a first cell identifier;

determining, by the computing device, whether or not the location of the mobile device is within the geographical region based on searching the set of cell identifiers to determine whether or not the set has the first cell identifier;

receiving data representing the predefined geographical boundary of the geographical region; and

identifying, in a hierarchy of cell grids, the set of cell identifiers that are determined to be within the predefined geographical boundary;

wherein each grid in the hierarchy of cell grids corresponds to a rectangle grid in longitude latitude space of locations on the earth with a predetermined resolution level; and

wherein the predetermined resolution level corresponds to a precision level in a floating point representation of longitude and latitude coordinates.

17. A computing device, comprising:

at least one microprocessor; and

memory storing instructions configured to instruct the at least one microprocessor to;

store, in the computing device, an identifier of a geographical region having a predefined geographical boundary;

store, in the computing device, a set of cell identifiers, each of the cell identifiers identifying a cell that is determined to be within the predefined geographical boundary;

receive, from a mobile device, a location of the mobile device;

convert, by the computing device, a set of coordinates of the location of the mobile device to a first cell identifier;

determine, by the computing device, whether or not the location of the mobile device is within the geographical region based on searching the set of cell identifiers to determine whether or not the set has the first cell identifier;

receive data representing the predefined geographical boundary of the geographical region; and

identify, in a hierarchy of cell grids, the set of cell identifiers that are determined to be within the predefined geographical boundary;

wherein each grid in the hierarchy of cell grids corresponds to a rectangle grid in longitude latitude space of locations on the earth with a predetermined resolution level; and

wherein the predetermined resolution level corresponds to a precision level in a floating point representation of longitude and latitude coordinates.