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.
