Geohash question with varying square sizes

[ty]

I have read a few posts on how to do geohashing using the
zrangebyscore in this group. However, I am not sure how to approach
varying the square size for say a 10km to a 1km or vice versa. Is
there a way to apply a bit mask to the values then do a comparison or
is there some other method to accomplish a search with a specified
degree of resolution.

Best regards,

Ty

[Dvir Volk]

Hi, I'm just about to implement this in https://github.com/doat/geodis , and this is what I intend to do:

1. create a mapping of bit length to approximate sqare size (I guess the resolution would be 2 bits, since lat and lon are interleaved). I tried looking for such a mapping but couldn't find one, if anyone knows of such a map, let me know.

2. decide what bit resolutions I would like to approximate, and what's the maximum radius I'm going to allow (probably 100-200km), but let's keep it configurable.

3. create sub indexes of geohashes in each resolution using ZSETs (currently there is only one with the maximum resoltion.

4. given a location and a radius, I'd choose the right resolution to look in, calculate the current geohash in this resolution, and extrapolate the adjacent 8 bounding boxes to the box of the original location. 

5. then a simple ZRANGEBYSCORE would give you all the nodes in those 9 geo boxes.

6. You then apply a more accurate limitation function, be it a box or a radius limit, using the actual lat,lons stored in the values of each node.

--
You received this message because you are subscribed to the Google Groups "Redis DB" group.
To post to this group, send email to redi...@googlegroups.com.
To unsubscribe from this group, send email to redis-db+u...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/redis-db?hl=en.

--

Dvir Volk

System Architect, The Everything Project (formerly DoAT)

http://everything.me

[Josiah Carlson]

What I've found works very well in practice is actually
pre-partitioning the data into 1 degree by 1 degree 'squares', with
two ZSETs per box, one ordered by latitude, one by longitude. Between
the 45th parallels, you get about 111km N/S per box, and between 78
and 111km E/W. As such, most queries will involve 1-4 box queries.

Rather than fetch ranges, we pre-calculate all of the boxes that are
within the radius, then perform an automated sequence of [copy the lat
box, filter the lat box, copy the lon box, filter the lon box,
intersect the lat/lon boxes], which are then unioned with other boxes.
By including other filters that are defined via sets and zsets, we
then intersect further to filter down the items in the final zset,
which we can fetch fully or paginate through as necessary.

It's not nearly as computationally elegant as using geohashing, and it
does use twice as much space. But it is a lot easier to wrap your head
around.

Regards,
- Josiah

[ty]

I was hoping to find a way to work with one set of geohash values so
as to conserve the amount of space/entries needed. I tried working
with the new scripting in the hopes that I could use the bit32.band
function. However, this is only available in the standard lua 5.2 and
the scripting support in redis seems to use lua 5.1.

Perhaps I could look for or port the bit32 to 5.1 or just write a
custom extension for redis. I am new to redis so I would be grateful
if you have any guidance on these ideas.

Best regards,

Ty

[Dvir Volk]

You could try first just doing a ZRANGEBYSCORE between the top left corner geohash of your bounding box and your bottom right corner geohash.

If I'm not mistaken, haven't done the math or testing to prove this - it should give you a bit of false positives (points outside your box that will be recalled) but it will never give you false negatives (points inside your box that will not be recalled). So if you first do this range, then manually filter out the false positives by lat,lon - you should be fine.

This has the usual edge cases for geohash of course.

[ty]

I ended up adding the LuaBitOp C extension module (http://
bitop.luajit.org/) into a copy of the redis 2.6 source I pulled with
git. I just needed to modify a few files and compile. Now I can do
something like:

redis 127.0.0.1:6379> HSET g 100 7
(integer) 1
redis 127.0.0.1:6379> eval " local v = redis.call('hget','g',100);
return bit.band(v,4) " 0
(integer) 4

Best regards,

Ty

[Dan]

Ty-

Nice work. Can you make your modified version of redis available? I'd like to use bitop in some lua scripts inside redis 2.6, too.

Dan

[Dan]

Nevermind, got redis 2.6 working with lua's bitop library. See https://github.com/dbro/redis/compare/db-lua-bitop for details

On Tuesday, March 27, 2012 5:48:11 AM UTC-7, ty wrote: