System and method for employing a grid index for location and precision encoding

• US 20040225665A1
• Filed: 09/26/2003
• Published: 11/11/2004
• Est. Priority Date: 05/09/2003
• Status: Active Grant

• Current Assignee: Planeteye Company ULC
• Original Assignee: Microsoft Corporation
• Inventors: Toyama, Kentaro, Logan, Ron
• Granted Patent: US 7,966,301 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 16/84 Mapping; Conversion

Abstract

A system and method for combining the precision estimate of a database entry'"'"'s coordinate value such that the precision information is included as part of the one-dimensional index. This is done by constructing a hierarchical index in which the size of the grid is related to the precision of the coordinate value. A grid index is a gridding of an n-dimensional space into a regular partition of the grid space into grid units, for which for a point in space, x, there is a function index (x), which retrieves a unique integer value for the grid that contains Point x, and a function coordinate(y, s), which returns a point associated with the index y at scale s. A hierarchical grid index is effectively a number of grid indices overlaid on the same space, with grid units of different sizes. In this case, each of the functions employs an additional argument that specifies the size of the grid unit to use. Thus, assuming that the grid size, s, is drawn from a set of grid sizes, S, Index (x,s) returns a unique integer value for the grid of size s that contains Point x. Hierarchical indexes may be used to enhance the performance of database queries. A query that seeks results from a small grid size, s_small, does not seek matches at a large grid size, s_large. Similar calculations can be performed for a finite area A.

Claims

1. A computer-implemented process for combining a precision estimate of a database entry'"'"'s coordinate value with the coordinate value into a single index, comprising the process actions of:

inputting one or more location entities; and

computing a grid index series wherein each location entity is represented as a series of grids that incorporate the location of each location entity.

2. The computer-implemented process of claim 1 further comprising the process action of outputting said grid index series to a database.

3. The computer-implemented process of claim 1 wherein a location entity is a point.

4. The computer-implemented process of claim 1 wherein a location entity is an area.

5. The computer-implemented process of claim 4 wherein said area is defined by a center latitude and longitude and a width and a height, each measured from the center latitude and longitude and along lines of latitude and longitude.

6. The computer-implemented process of claim 1 wherein equirectangular projection is used to input latitude and longitude values of said one or more location entities as x-y pairs on a Euclidean coordinate system.

7. The computer-implemented process of claim 1 wherein the process action of computing a grid index series comprises:

gridding the globe at a prescribed number of resolutions;

indexing each grid in raster scan order; and

mapping the latitude and longitude coordinates of each location entity to the index.

8. The computer-implemented process of claim 7 wherein the prescribed number of resolutions is 20.

9. The computer-implemented process of claim 7 wherein the process action of indexing each grid in raster scan order comprises:

for each grid,

determining the longitudinal span, D, in degrees that three standard deviations corresponds to, where a standard deviation σ

is the measurement error of a given latitude, longitude coordinate; and

determining the degree-scale of precision, R, to be the discrete unit of resolution just larger than D.

10. The computer-implemented process of claim 9 wherein the longitudinal span in degrees that 3σ

meters corresponds to is d=[180(3σ

) cos(latitude)]/kπ

is determined, where k is the circumference of the earth in meters.

11. The computer-implemented process of claim 9 wherein the process action of determining the degree-scale of precision, R, to be the discrete unit of resolution just larger than D comprises setting r=|−

log₂d/20|.

12. The computer-implemented process of claim 7 wherein the globe is gridded with overlapping grids at each scale in order to increase accuracy.

13. The computer-implemented process of claim 12 wherein coordinates of location entities are mapped to the square whose center is closest.

14. The computer-implemented process of claim 1 wherein the location entity is geographic location data.

15. The computer-implemented process of claim 1 wherein the location entity is described in terms of latitude and longitude.

16. The computer-implemented process of claim 15 wherein the latitude and longitude values are taken as straight x-y pairs on a Euclidean coordinate system.

17. The computer-implemented process of claim 1 wherein the location entity is described in terms of latitude, longitude and altitude.

18. The computer-implemented process of claim 17 wherein the latitude, longitude and altitude values are taken as (x,y,z) pairs on a Euclidean coordinate system.

19. The computer-implemented process of claim 7 wherein the location entity'"'"'s coordinates in latitude (lat) and longitude (long) is mapped to the index by

20. The computer-implemented process of claim 19 wherein to recover the latitude and longitude values, the latitude (lat) and longitude (long) is calculated as:

21. The computer-implemented process of claim 2 wherein the database comprises a location entity identifier and a scale index for one or more scales each corresponding to a different grid.

22. The computer-implemented process of claim 2 wherein a query of the database comprises the following process actions:

querying which location entities are in a given grid cell at a given grid scale;

searching in the data of the given grid scale for the values of the given grid cell; and

returning said values of the given grid cell at the given grid scale.

23. A system for indexing a multi-dimensional space with a one dimensional value, the system comprising:

a general purpose computing device; and

a computer program comprising program modules executable by the computing device, wherein the computing device is directed by the program modules of the computer program to,

construct a hierarchical grid index from a number of grid indices overlaid on the same space with grid units of different sizes wherein the size of each grid is related to the precision of the coordinate values of a database entry.

24. The system of claim 23 wherein the database entry is a geographic location.

25. The system of claim 23 wherein the database entry is a time.

26. A computer-readable medium having computer-executable instructions for combining a precision estimate of a database entry'"'"'s coordinate value with the coordinate value into a single index, said computer executable instructions comprising:

inputting one or more location entities; and

computing a grid index series wherein each location entity is represented as a series of grids that incorporate the location of each location entity.

27. The computer-readable medium of claim 26 wherein the instruction computing a grid index series uses an equirectangular projection.

28. The computer-readable medium of claim 26 wherein the series of grids grid the globe at twenty different resolutions, with “

square”

units whose sides correspond to 20×

(½

)^r degrees, for 0≦

r<

20.

29. The computer-readable medium of claim 26 wherein the series of grids is a hierarchical series of equilateral polygons embedded within a Platonic solid.

30. The computer-readable medium of claim 26 wherein the series of grids is a hierarchical series of polygons that grids the globe.