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 <thst...@gmail.com> 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: >>> >>> <?xml version=\"1.0\" encoding=\"UTF-8\"?> >>> <kml xmlns=\"http://www.opengis.net/kml/2.2\";> >>> <Placemark> >>> <Polygon> >>> <outerBoundaryIs> >>> <LinearRing> >>> <coordinates> >>> >>> -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 >>> </coordinates> >>> </LinearRing> >>> </outerBoundaryIs> >>> </Polygon> >>> </Placemark> >>> </kml> >>> >>> >>> 2) Input values are of type lat/lon like -117.11111,33.2222 >>> >>> 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 >>> <https://en.wikipedia.org/wiki/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 >>> <https://en.wikipedia.org/wiki/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.
