System and method for employing a grid index for location and precision encoding
First Claim
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;
computing a one-dimensional grid index series wherein each location entity is represented as a series of grids that incorporate the location of each location entity; and
outputting said grid index series to a database.
2 Assignments
0 Petitions
Accused Products
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, ssmall, does not seek matches at a large grid size, slarge. Similar calculations can be performed for a finite area A.
-
Citations
27 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; computing a one-dimensional grid index series wherein each location entity is represented as a series of grids that incorporate the location of each location entity; and outputting said grid index series to a database. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
23. A computer-readable storage medium having a 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; computing a one-dimensional grid index series wherein each location entity is represented as a series of grids that incorporate the location of each location entity; and using the grid index series to perform a query of the location entities such that any query that seeks a match of a location entity at a small grid size does not seek a match of a location entity at a larger grid size than said small grid size. - View Dependent Claims (24, 25, 26, 27)
-
Specification