Fast and accurate geomapping

Patent metadata

Field	Value
Publication number	US-2016171027-A1
Application number	US-201414230676-A
Country	US
Kind code	A1
Filing date	Mar 31, 2014
Priority date	Mar 31, 2014
Publication date	Jun 16, 2016
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 method for discovering k-nearest-neighbors to a given point within a certain distance d, the method comprising the steps of:
constructing an index of geometries using geohashes of geometries as an indexing key to obtain an indexed set of geometries; calculating a geohash representation of the given point with a resolution equal to a magnitude value of the certain distance d; searching for a closest-prefix geometry from the indexed set of geometries using the geohash representation of the given point; identifying geometries from the indexed set of geometries that have a same prefix as the closest-prefix geometry; calculating distances between the given point and the geometries identified from the indexed set of geometries that have 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 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 point within a certain distance d, wherein the computer readable program when executed on a computer causes the computer to perform the steps of:
constructing an index of geometries using geohashes of geometries as an indexing key to obtain an indexed set of geometries; calculating a geohash representation of the given point with a resolution equal to a magnitude value of the certain distance d; searching for a closest-prefix geometry from the indexed set of geometries using the geohash representation of the given point; identifying geometries from the indexed set of geometries that have a same prefix as the closest-prefix geometry; calculating distances between the given point and the geometries identified from the indexed set of geometries that have 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 of geometries that have the same prefix as the closest-prefix geometry.

12 . A system for discovering k-nearest-neighbors to a given point within a certain distance d, the system comprising:
an index constructor constructs an index of geometries using geohashes of geometries as an indexing key to obtain an indexed set of geometries; a geohash representation calculator calculates a geohash representation of the given point with a resolution equal to a magnitude value of the certain distance d; a geohash-representation-based searcher searches for a closest-prefix geometry from the indexed set of geometries using the geohash representation of the given point, and identifies geometries from the indexed set of geometries that have a same prefix as the closest-prefix geometry; a prefix-based distance calculator calculates distances between the given point and the geometries identified from the indexed set of geometries that have the same prefix as the closest-prefix geometry; and a top-k nearest-neighbors determiner determines k geometries with respective shortest 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

• G06F17/30321 Primary

  Physics · mapped topic

• G06F17/30241

  Physics · mapped topic

• G06F17/30985

  Physics · mapped topic

• G06F16/9014

  hash tables · CPC title

• G06F16/29

  Geographical information databases · CPC title