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.
