Re: [go-nuts] Re: How to implement Segment Tree in key/value datastore to use Google S2 geometry?

2018-01-15 Thread Jesper Louis Andersen 
My intuition is that this screams S2 at the top of its lungs, provided that
you can hook into the structure.

It is simply storing a radix tree (PATRICIA) of S2 cells and attaching
information about box bounding to all of these. This yields a compressed
trie-like structure that you can probably maintain in memory even for
fairly large sets of bounding boxes. The path compression means that you
need considerably fewer than the 30-cell lookup depth that would normally
happen. If they haven't this built-in I don't know why, as it seems rather
obvious to me, givien that you know the internal structure of S2[0].

The alternative ideas are just quad-tree'ing the whole world, but then you
are getting close to an R-tree solution anyway. Another solution is to just
brute-force everything on two hash-table maps. Uber did this in a blog
post, but I wouldn't recommend that solution since it won't really scale.
Finally, you can just stuff everything into PostGIS in Postgres, which
contains many of these algorithms already. If you need to link to other
relational data, you shouldn't rule out such a solution I think.

[0] If you've never looked into this, do it. It is awfully brilliantly
designed. Hilbert curves and all.

On Sun, Jan 14, 2018 at 7:50 PM Constantine Vassilev 
wrote:

> Thanks for the suggestion and the link.
>
> The question is how it will be searched. Also I liked the Google S2's
> Golang implementation.
>
> From the documentation if the link I see:
> --
> Queries
>
> Bounding-box and k-nearest-neighbors queries are supported.
>
> Bounding-box queries require a search *Rect. It returns all objects that
> touch the search rectangle.
>
> --
>
> What I need is having location's lat/lon to find the polygon around it.
>
> Also how the index would be created and stored as key/value.
>
> On Saturday, January 13, 2018 at 11:21:48 PM UTC-8, Tamás Gulácsi wrote:
>>
>>
>> 2018. január 14., vasárnap 5:48:11 UTC+1 időpontban Constantine Vassilev
>> a következőt írta:
>>>
>>> I need to implement the following:
>>>
>>> 1) I have a database of ~100 mil records.
>>>
>>> Each record is of type key/value.
>>>
>>> The key is an internal ID of type: "123456789".
>>> The value is a kml with geographic boundary in form of lat/lon
>>> coordinates:
>>>
>>>  
>>>  http://www.opengis.net/kml/2.2\;>
>>>
>>>
>>>  
>>>  
>>>
>>>
>>> -117.587174583104,33.6437620515745
>>>
>>> -117.587083176312,33.6437891755388
>>>
>>> -117.587016626677,33.6438098355405
>>>
>>> -117.586923617992,33.6435949397585
>>>
>>> -117.587051757569,33.643539681552
>>>
>>> -117.587079610599,33.6435348310862
>>>
>>> -117.587174583104,33.6437620515745
>>>
>>>  
>>>   
>>> 
>>> 
>>>   
>>>
>>>
>>> 2) Input values are of type lat/lon like -117.1,33.
>>>
>>> The usage is having an input lat/lon to find the boundary in which it is
>>> located and return the key (the internal ID).
>>>
>>> The closest solution I found is using Google S2 geometry library:
>>> https://github.com/golang/geo
>>> and this library:
>>> https://github.com/akhenakh/regionagogo
>>>
>>> This implementation is using an in memory index with Segment Tree
>>>  datastructure:
>>> github.com/Workiva/go-datastructures/augmentedtree
>>> and BoltDB.
>>>
>>>
>> Why not R-tree (https://github.com/dhconnelly/rtreego) ?
>> You want poligon bounded inclusion, don't you?
>> With segmented tree, you'll need to implement some other data structure
>> that holds the slices (say, you slice the globe vertically and each slice
>> holds a segment tree of the vertically sliced poligons),
>> I think
>>
>>
>> I need to create persistent  key/value database on the disk (it would be
>>> big like ~100GB) using
>>> RocksDB key/value store with key Segment Tree
>>>  datastructure.
>>>
>>> It should get CellID from lat/lon and find the S2 interval where it
>>> resides.
>>>
>>> How is the best way to implement it?
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> --
> You received this message because you are subscribed to the Google Groups
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-nuts+unsubscr...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[go-nuts] Re: How to implement Segment Tree in key/value datastore to use Google S2 geometry?

2018-01-14 Thread Constantine Vassilev 
Thanks for the suggestion and the link.

The question is how it will be searched. Also I liked the Google S2's 
Golang implementation.

>From the documentation if the link I see:
--
Queries

Bounding-box and k-nearest-neighbors queries are supported.

Bounding-box queries require a search *Rect. It returns all objects that 
touch the search rectangle.

--

What I need is having location's lat/lon to find the polygon around it.

Also how the index would be created and stored as key/value.

On Saturday, January 13, 2018 at 11:21:48 PM UTC-8, Tamás Gulácsi wrote:
>
>
> 2018. január 14., vasárnap 5:48:11 UTC+1 időpontban Constantine Vassilev a 
> következőt írta:
>>
>> I need to implement the following:
>>
>> 1) I have a database of ~100 mil records.
>>
>> Each record is of type key/value.
>>
>> The key is an internal ID of type: "123456789".
>> The value is a kml with geographic boundary in form of lat/lon 
>> coordinates:
>>
>>  
>>  http://www.opengis.net/kml/2.2\;>
>>
>>
>>  
>>  
>>
>>   
>> -117.587174583104,33.6437620515745 
>>   
>> -117.587083176312,33.6437891755388 
>>   
>> -117.587016626677,33.6438098355405 
>>   
>> -117.586923617992,33.6435949397585 
>>   
>> -117.587051757569,33.643539681552 
>>   
>> -117.587079610599,33.6435348310862 
>>   
>> -117.587174583104,33.6437620515745
>>
>>
>>   
>>   
>> 
>>   
>>
>>
>> 2) Input values are of type lat/lon like -117.1,33.
>>
>> The usage is having an input lat/lon to find the boundary in which it is 
>> located and return the key (the internal ID).
>>
>> The closest solution I found is using Google S2 geometry library:
>> https://github.com/golang/geo
>> and this library:
>> https://github.com/akhenakh/regionagogo
>>
>> This implementation is using an in memory index with Segment Tree 
>>  datastructure:
>> github.com/Workiva/go-datastructures/augmentedtree
>> and BoltDB.
>>
>>
> Why not R-tree (https://github.com/dhconnelly/rtreego) ? 
> You want poligon bounded inclusion, don't you?
> With segmented tree, you'll need to implement some other data structure 
> that holds the slices (say, you slice the globe vertically and each slice 
> holds a segment tree of the vertically sliced poligons),
> I think
>
>
> I need to create persistent  key/value database on the disk (it would be 
>> big like ~100GB) using
>> RocksDB key/value store with key Segment Tree 
>>  datastructure.
>>
>> It should get CellID from lat/lon and find the S2 interval where it 
>> resides.
>>
>> How is the best way to implement it?
>>
>>
>>
>>
>>
>>
>>
>>

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[go-nuts] Re: How to implement Segment Tree in key/value datastore to use Google S2 geometry?

2018-01-13 Thread Tamás Gulácsi 

2018. január 14., vasárnap 5:48:11 UTC+1 időpontban Constantine Vassilev a 
következőt írta:
>
> I need to implement the following:
>
> 1) I have a database of ~100 mil records.
>
> Each record is of type key/value.
>
> The key is an internal ID of type: "123456789".
> The value is a kml with geographic boundary in form of lat/lon coordinates:
>
>  
>  http://www.opengis.net/kml/2.2\;>
>
>
>  
>  
>
>   
> -117.587174583104,33.6437620515745 
>   
> -117.587083176312,33.6437891755388 
>   
> -117.587016626677,33.6438098355405 
>   
> -117.586923617992,33.6435949397585 
>   
> -117.587051757569,33.643539681552 
>   
> -117.587079610599,33.6435348310862 
>   
> -117.587174583104,33.6437620515745
>
>
>   
>   
> 
>   
>
>
> 2) Input values are of type lat/lon like -117.1,33.
>
> The usage is having an input lat/lon to find the boundary in which it is 
> located and return the key (the internal ID).
>
> The closest solution I found is using Google S2 geometry library:
> https://github.com/golang/geo
> and this library:
> https://github.com/akhenakh/regionagogo
>
> This implementation is using an in memory index with Segment Tree 
>  datastructure:
> github.com/Workiva/go-datastructures/augmentedtree
> and BoltDB.
>
>
Why not R-tree (https://github.com/dhconnelly/rtreego) ? 
You want poligon bounded inclusion, don't you?
With segmented tree, you'll need to implement some other data structure 
that holds the slices (say, you slice the globe vertically and each slice 
holds a segment tree of the vertically sliced poligons),
I think


I need to create persistent  key/value database on the disk (it would be 
> big like ~100GB) using
> RocksDB key/value store with key Segment Tree 
>  datastructure.
>
> It should get CellID from lat/lon and find the S2 interval where it 
> resides.
>
> How is the best way to implement it?
>
>
>
>
>
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to golang-nuts+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.