Fast and accurate geomapping

Patent metadata

Field	Value
Publication number	US-2023161822-A1
Application number	US-202318150950-A
Country	US
Kind code	A1
Filing date	Jan 6, 2023
Priority date	Mar 31, 2014
Publication date	May 25, 2023
Grant date	—

Abstract

A system and method are provided for discovering k-nearest-neighbors to a given point within a certain distance d. The method includes constructing an index of geometries using geohashes of geometries as an indexing key to obtain an indexed set of geometries, and calculating a geohash representation of the given point with a resolution equal to a magnitude value of d. The method includes searching for a closest-prefix geometry from the indexed set using the geohash representation of the given point, and identifying geometries from the indexed set having a same prefix as the closest-prefix geometry. The method further includes calculating distances between the given point and the geometries identified from the indexed set having the same prefix as the closest-prefix geometry, and determining k geometries with respective shortest distances less than d from the geometries identified from the indexed set having the same prefix as the closest-prefix geometry.

First claim

What is claimed is:

1 . A computer-implemented method for discovering k-nearest-neighbors to a given object represented by a point within a certain linear, one-dimensional distance d, comprising:
obtaining an indexed set of geometries, and pruning a space of possible objects by gradually removing characters from one or more geocodes, the pruning enabling geomapping of the object represented by the point and minimizing a number of distance calculations by utilizing adaptive resolution properties of geohash; calculating a geohash representation of the point with an adaptive resolution equal to a magnitude value of the certain linear, one-dimensional distance d; searching for a closest-prefix geometry from the indexed set of geometries using the geohash representation of the point to identify all objects including at least a number of bits needed to encode accuracy of the distance d using the geohash representation; calculating linear, one-dimensional distances between the point and geometries identified from the indexed set of geometries that have a same prefix as the closest-prefix geometry; and determining k geometries with respective shortest linear, one-dimensional distances less than d from the geometries identified from the indexed set of geometries that have the same prefix as the closest-prefix geometry.

2 . The method of claim 1 , wherein the index of geometries is formed as a data structure supporting prefix-based string matching.

3 . The method of claim 1 , wherein the index of geometries is formed as at least one of a patricia trie, a binary tree, and a ternary tree.

4 . The method of claim 1 , wherein the geohash representation of the given point is one of a string of bits or a vector of bits.

5 . The method of claim 1 , wherein said searching and identifying steps use respective prefix-matching string operations of a data structure supporting prefix-based string matching to find the closest-prefix geometry and the geometries identified from the indexed set of geometries that have the same prefix as the closest-prefix geometry.

6 . The method of claim 5 , wherein the data structure is at least one of a patricia trie, a binary tree, and a ternary tree.

7 . The method of claim 1 , wherein different resolutions are used for representing longitudes versus latitudes.

8 . The method of claim 7 , further comprising:
dividing a respective rectangular geometry space for a respective geometry in the indexed set of geometries into a respective lat-lon box; encoding the respective lat-lon box into a ternary string; and supporting storage of and queries on the ternary string using a hardware accelerated ternary content-addressable memory.

9 . The method of claim 8 , wherein the geohash representation is extensible to multiple dimensions with a heterogeneous resolution.

10 . The method of claim 8 , wherein the multiple dimensions comprise longitude, latitude, and at least one of time and altitude.

11 . A computer readable storage medium comprising a computer readable program for discovering k-nearest-neighbors to a given object represented by a point within a certain linear, one-dimensional distance d, wherein the computer readable program when executed on a computer causes the computer to perform the steps of:
obtaining an indexed set of geometries, and pruning a space of possible objects by gradually removing characters from one or more geocodes, the pruning enabling geomapping of the object represented by the point and minimizing a number of distance calculations by utilizing adaptive resolution properties of geohash; calculating a geohash representation of the point with an adaptive resolution equal to a magnitude value of the certain linear, one-dimensional distance d; searching for a closest-prefix geometry from the indexed set of geometries using the geohash representation of the point to identify all objects including at least a number of bits needed to encode accuracy of the distance d using the geohash representation; calculating linear, one-dimensional distances between the point and geometries identified from the indexed set of geometries that have a same prefix as the closest-prefix geometry; and determining k geometries with respective shortest linear, one-dimensional distances less than d from the geometries identified from the indexed set of geometries that have the same prefix as the closest-prefix geometry.

12 . A system for discovering k-nearest-neighbors to a given object represented by a point within a certain linear, one-dimensional distance d, comprising:
a hardware processor operatively connected to a non-transitory computer-readable storage medium, the process being configured for:
obtaining an indexed set of geometries, and pruning a space of possible objects by gradually removing characters from one or more geocodes, the pruning enabling geomapping of the object represented by the point and minimizing a number of distance calculations by utilizing adaptive resolution properties of geohash;
calculating a geohash representation of the point with an adaptive resolution equal to a magnitude value of the certain linear, one-dimensional distance d;
searching for a closest-prefix geometry from the indexed set of geometries using the geohash representation of the point to identify all objects including at least a number of bits needed to encode accuracy of the distance d using the geohash representation;
calculating linear, one-dimensional distances between the point and geometries identified from the indexed set of geometries that have a same prefix as the closest-prefix geometry; and
determining k geometries with respective shortest linear, one-dimensional distances less than d from the geometries identified from the indexed set of geometries that have the same prefix as the closest-prefix geometry.

13 . The system of claim 12 , wherein the index of geometries is formed as a data structure supporting prefix-based string matching.

14 . The system of claim 12 , wherein the index of geometries is formed as at least one of a patricia trie, a binary tree, and a ternary tree.

15 . The system of claim 12 , wherein the geohash representation of the given point is one of a string of bits or a vector of bits.

16 . The system of claim 12 , wherein the geohash-representation-based searcher uses respective prefix-matching string operations of a data structure supporting prefix-based string matching to find the closest-prefix geometry and the geometries identified from the indexed set of geometries that have the same prefix as the closest-prefix geometry.

17 . The system of claim 16 , wherein the data structure is at least one of a patricia trie, a binary tree, and a ternary tree.

18 . The system of claim 12 , wherein different resolutions are used for representing longitudes versus latitudes.

19 . The system of claim 12 , wherein the geohash representation is extensible to multiple dimensions with a heterogeneous resolution.

20 . The system of claim 19 , wherein the multiple dimensions comprise longitude, latitude, and at least one of time and altitude.

Assignees

• IBM

Inventors

• Agrawal Dakshi
• Ganti Raghu K
• Srivatsa Mudhakar
• Zerfos Petros

Classifications

• G06F16/9014

  hash tables · CPC title

• G06F16/29

  Geographical information databases · CPC title

• G06F16/90344 Primary

  by using string matching techniques · CPC title