reverse Geocode

[thstart]

1) from my device I can get latitude/longitude

2) a DB table with latitude/longitude/POI

I want to find the closest match of 1) with 2) in order to get POI

This is basically reverse a Geocode.

How is the best way to do this in Golang?

[Martin Schnabel]

if you can choose the db use PostgreSQL + PostGIS, then its one select
statement. if you use it on a phone SQLite + SpatiaLite might work for you.

otherwise wrap a geospatial c lib or implement the geometries,
projections and distance calculation yourself.

hope that helps

[John Nagle]

Find some online service which will do reverse geocoding and
call it. See

https://developers.google.com/maps/documentation/geocoding/#ReverseGeocoding


John Nagle

[thstart]

I have an access to the raw database and want to build my own service

[John Nagle]

On 1/18/2013 1:03 PM, thstart wrote:
> I have an access to the raw database and want to build my own service

Most of the major SQL databases have some degree of spatial
processing. In most cases, all they really can do efficiently is
decide whether a point is in a rectangle; there are indices to
support that. But that's good enough to eliminate all faraway
points. You can get, say, all points of interest within a
latitude/longitude range around your location. (Properly
handling the poles and the 180 degree meridian requires extra
work.) Then you can eliminate some of those based on actual
distance.

See

http://dev.mysql.com/doc/refman/5.0/en/spatial-extensions.html

for MySQL. This is a standard part of a MySQL installation.

There's PostGIS for PostGres, but it's separate from the main
PostGres effort. SQLite has a 2D index type, RTree, but
not a full set of spacial extensions like the big guys.
Any of those will probably work for you.

John Nagle

[thstart]

Thank you, John - will look at this info. 

The nature of the project requires to use NoSQL and Golang under Ubuntu.

Additionally it would be accessed as a web service.

This narrows down the possible solutions. 

[John Nagle]

On 1/18/2013 2:00 PM, thstart wrote:
> The nature of the project requires to use NoSQL and Golang under Ubuntu.
> Additionally it would be accessed as a web service.

Both MongoDB and CouchDB have some kind of 2D index capability.

If it's a web service, this is easy. There are lots of database
options there. Your original question said that it had to work on
"my device", which implied cramming the data onto a phone or tablet
or GPS receiver. That's harder, and there are fewer off the shelf
solutions.

John Nagle

[Constantine Vasil]

"my device" is giving the lat/long which needs to be send to the

ws for reverse geocode. the database should live on the server.

I ruled out MongoDb and CouchDb - the DB should be based on 

LevelDB. With LevelDB there is possibility for a range lookup. 

Probably simulating this query will make the job done. 

Or using Geo Hashing.

Bounding Box Query

The following query returns a collection of points within a rectangular bounding box centered around San Francisco (37.46, -122.50).

SELECT
year, month,
AVG(mean_temp) avg_temp,
MIN(min_temperature) min_temp,
MAX(max_temperature) max_temp
FROM
[weather_geo.table]
WHERE
/* Return values between a pair of Lat/Long coordinate */
lat / 1000 > 37.46 AND lat / 1000 < 37.65
AND long / 1000 > -122.50 AND long / 1000 < -122.30
GROUP BY
year, month
ORDER BY
year, month ASC;

[pphalen]

Sorry, I find your question a little ambiguous, but maybe take a look at rtreego and see it helps you along. It's a nice in memory database written in Go, using R*-Trees. Supports bounding box contains/intersection, and k-nearest-neighbor for points and rectangles.

[Constantine Vasil]

I took a look at rtreego but it is in-memory database. I am looking for disk based on - 

the data size is close to 50GB.

[John Nagle]

On 1/18/2013 4:40 PM, Constantine Vasil wrote:
> "my device" is giving the lat/long which needs to be send to the
> ws for reverse geocode. the database should live on the server.
>
> I ruled out MongoDb and CouchDb - the DB should be based on
> LevelDB.

You've rejected three SQL and two non-SQL databases that
offer 2D indices, and settled on one that doesn't support 2D indices.

> SELECT year, month,
> AVG(mean_temp) avg_temp,
> MIN(min_temperature) min_temp,
> MAX(max_temperature) max_temp
> FROM
> [weather_geo.table]
> WHERE
> /* Return values between a pair of Lat/Long coordinate */
> lat / 1000 > 37.46 AND lat / 1000 < 37.65
> AND long / 1000 > -122.50 AND long / 1000 < -122.30
> GROUP BY
> year, month
> ORDER BY

> year, month ASC;*

On a database without 2D indices, the database engine
will have to do a linear scan of all the entries for
either "lat" or "long".

This isn't really a Go question; ask in a database forum.

John Nagle

[Kevin Gillette]

Which is where geohashing can possibly help, since two hashes will have relative sorting properties. At the very least, it would be absolutely trivial to do a prefix check to narrow the number of scanned rows to a small number of candidates.

[Constantine Vasil]

I researched this one:

https://github.com/the42/cartconvert/tree/master/cartconvert

any other supporting geohashing?

[Johann Höchtl]

Author here. I tested the geohash implementation against an online service of the inventor, who is a Goer himself, and it returned the same results. It's also covered by tests. Simply strip bits from the right to reduce precission. If you intend to use it in a tight loop I would have to revise it to use bitwise ops on integers.

[Constantine Vasil]

bitwise ops would be great for speed

[Kevin Gillette]

iirc, you must strip an even number of bits to reduce precision, and for some geohashing formats, you may have to strip and partially reinterpolate the right-most bytes to strip sub-byte precision.

[Constantine Vasil]

where there is more info how to do that? this is especially important

when the lat/lon comes from mobile device which is not precise and

when a lookup in POI should be made one has to begin with wide range and

gradually narrow it.

if 

.0000 precision in the database is related to 40 feets

.00000 precision to 4 feets

.000000 to .4 feets

one should begin with .0000 and gradually goes to .000000.

Now the question is how to do that with geohashing?

[Constantine Vasil]

got an issue in geohash coding:

lat              lon                  geohash

1)  7.980015    -66.602341  de0wk3jthvxp   

2) 17.980030    -66.290580  de0y790tm88 

de0wk3jthvxp - 12 chars

de0y790tm88 - 11 chars

so when latitude AND longitude ends with 0 geohash is coded to 11 chars

If gradually increasing the resolution in this case it will not work. Needs a padding

in geohash string.

On Sunday, January 20, 2013 11:37:33 AM UTC-8, Johann Höchtl wrote:

[Johann Höchtl]

Am Sonntag, 20. Januar 2013 21:45:14 UTC+1 schrieb Kevin Gillette:

iirc, you must strip an even number of bits to reduce precision

This is correct

[Johann Höchtl]

Am Sonntag, 20. Januar 2013 23:04:03 UTC+1 schrieb Constantine Vasil:

got an issue in geohash coding:

lat              lon                  geohash

1)  7.980015    -66.602341  de0wk3jthvxp   

2) 17.980030    -66.290580  de0y790tm88 

de0wk3jthvxp - 12 chars

BTW the service you cited is online. I implemented the exact algorithm as stated by the Wikipedia Article and I get the same results:

http://cartconvert.allowed.org/api/latlong/.json?lat=17.980030%C2%B0&long=-66.290580%C2%B0&outputformat=geohash

[Matthew Zimmerman]

I am not a Geohash expert by any means - I just ported someone else's
code - but I can't understand what "reverse geocode" is - it's a hash
- you don't reverse it, that's the point. Your use case confuses me.

github.com/mzimmerman/geobox

> --
>
>

[thstart]

geohash + LevelDB is solving this task very nicely. 

[Kevin Gillette]

GeoHashes are not proper hash functions: they're precision-configurable encoders, and they are indeed reversible (capable of being decoded back into a lat-lon pair). If not for the reversibility, they'd be considerably less useful.

Oddly, though, many of the implementations I've seen do only have an encoder.

[thstart]

I was able to generate my key/value db with key=geohash, value-POI. 

having an input lat/lon converted to geohash I can seek for key=de0yn*

to get a list:

de0yn7cypgbq:  17.951338  - -66.167918 

de0yn7cwcu1t:  17.951468  - -66.168517  

de0ynk1390rq:   17.951920  - -66.168885   

de0ynk1389ke:   17.951925  - -66.168910  

Now the question is following:

if input is close (but not exact) to an entry in the db:

 17.951338   -66.167918 

say

 17.951345   -66.167924 

e.g last 2 significant digits are different

and needed accuracy of:

4 decimal places - 37 feet, 11.1 m

how you will make a proximity search?