SFCurve is a Scala library for the creation, transformation, and querying of space-filling curves
@jnh5y @elahrvivaz So recalling from the the context for zdivide as I understood it: You have some z-range (probably it it intersects the decomposed ranges of your bbox) you drop a point somewhere in the middle. You have couple of cases: the point can be in the middle of a your bounding box, basically noop; the point can be outside of your bounding box, in which case it can compute binmin, the starting point of the next range up the z-curve, and little max, the ending point of the previous range down the z-curve, allowing you to drop all points in between those two points.
you can check pretty easily to see if it's in the bbox, but then i'm not sure of an easy way to get one outside the bbox and still within the z-values
anyway, i think we have a different way of accomplishing the same thing, so we should be good
being efficient is always nice though :)
so we were doing something like: zdivide(min.mid(max), min, max)
which mostly worked, so it was confusing
but it left out some values
in the resulting ranges
actually it was
(min.z + max.z) / 2 - mid would always be in the query box i believe
I’ll have to hack on it to double check. Just looking over the paper the case of “xd is in bbox” is mentioned but not expounded upon. I suspect your reasoning is spot on, they’re doing a table scan until they get to a point outside the range, then they need to skip. I recall that I was able to do a decomposition with z-divide. AFAIR there is a case for bigmin and litmax calculation that you can safely check for, but maybe it was me missinterpreting the paper.
Thinking ahead…I’m kind of regreting the choice to keep at
Longs and not using an array of bytes to represent the index
it seems like the lack of precision contraints is also good
but it also would allow for the ideas of periodicity and sharding to be introduced
which is something I’m interested in adding to GeoTrellis, which GeoMesa and GeoWave already have, and I’d like to be able to code our version of it in a way that’s in the common lib instead of just another copy of that type of logic in GeoTrellis
so I guess I’m proposing two major refactors/features:
- moving from Longs to Array[Byte], which would make GeoMesa code like this (https://github.com/locationtech/geomesa/blob/cc97b68ef3b5a765be0fe213bdc4f9758b903f2a/geomesa-accumulo/geomesa-accumulo-datastore/src/main/scala/org/locationtech/geomesa/accumulo/index/z3/XZ3WritableIndex.scala#L76) change from having to use
Longs.toByteArrayto just using the byte array - Looking through the GeoMesa and GeoWave binning/periodicity code, respectivly, and the split/partitioning code, respectively, to decide how to best implement those features in
sfcurve, putting that feature in, and having GeoTrellis implement those features
Thoughts?
GeoWave made the choice to use byte arrays and allow for arbitrarily high precision curves, and I'm happy with the decision...and regarding partitioning and periodicity, we have a higher level concept of a "numeric index strategy" that contains one or more sfcs, rather than rolling that into the definition of an sfc which I'd prefer, albeit that higher level strategy can still fit in
sfcurve
a couple questions, would
sfcurve like to include GeoWave, and probably the more difficult question would sfcurve consider including java?
I think the ideal goal is that all 3 projects eventually depend on sfcurve
I feel like in GeoMesa those things are option-based when they could be composition-based; GeoWave has the Composite index, which tbh was a somewhat tricky API to navigate, though we figured it out: https://github.com/lossyrob/geowave-geomesa-comparative-analysis/blob/rob/gdelt/empirical-data/geowave/src/main/scala/com/azavea/ingest/geowave/Ingest.scala#L183
I guess the confusing part was with the Index vs IndexStrategy vs IndexModel
however, as GeoMesa started to emphasize being a run-time only dependency, we needed to tunnel index options through the geotools API (admittedly quite stringly-typed)
there's no reason we couldn't have both in sfcurve though - something a la composition if a user wants to use the programmatic api and maybe a typesafe config based constructor if a user wanted to set index options through a config file
as far as composed SFCs, i think @cne1x and @jnh5y have lots of ideas
I totally understand your answer, but we couldn't really port code if we were trying to keep java out of the core
oh and regarding Index v Index Strategy v Index Model - quick explanation might help, the only one of those that is in the geowave core index module is the index strategy...perhaps confusing naming, but the "store" module uses the Index Model as a way to provide common readers and writers across the index as basically the only reasonable way to comingle data of multiple types, formats, etc. and query across them all with the ability to still run the filtering on the server - and Index just wraps the index strategy and the index model together...overloaded "index" perhaps, but really the only pertinent component to sfcurve is GeoWave's index strategy, the others introduce commonalities in storage of types that seem completely out of scope of sfcurve
so it is the index strategy that can be composed with another index strategy, where an index strategy can be purely a wrapper around an SFC - partitioning or periodicity isn't an SFC but just contribute to an index strategy...anyways I actually think we're saying the exact same thing, maybe in a different way
As we work out the ideas around composition, etc, I think it would be good to have one project for that
@lossyrob, I think using byte arrays makes some sense. It might help provide more general precision.
that said, I'd want to understand any performance changes; it might make sense to keep Longs around for some specific uses
I think the ideas of composition and the abstraction in geowave are something we should def draw on.
But we prob would’t take it verbatim, or just import the geowave code into sfcurve…when we make the switch to sfcurve we’re going to have to adapt a bunch of our code, and I can imagine that’s true across all the projects that use it
the math outside of java primitives is definitely costly, our attempt to minimize the impact is using an interface with primitive and biginteger/decimal math implementations and then choose the optimal implementation based on required precision (interestingly enough, query decomposition and get ID have different metrics for fitting within java primitives so you may end up using a mix of implementations)
