{"action":"created","issue":{"url":"https://api.github.com/repos/geotrellis/curve/issues/3","labels_url":"https://api.github.com/repos/geotrellis/curve/issues/3/labels{/name}","comments_url":"https://api.github.com/repos/geotrellis/curve/issues/3/comments","events_url":"https://api.github.com/repos/geotrellis/curve/issues/3/events","html_url":"https://github.com/geotrellis/curve/issues/3","id":59257444,"number":3,"title":"Design an architecture for dealing with general spaces (e.g. SpaceTime) to SFC indices. ","user":{"login":"lossyrob","id":2320142,"avatar_url":"https://avatars.githubusercontent.com/u/2320142?v=3","gravatar_id":"","url":"https://api.github.com/users/lossyrob","html_url":"https://github.com/lossyrob","followers_url":"https://api.github.com/users/lossyrob/followers","following_url":"https://api.github.com/users/lossyrob/following{/other_user}","gists_url":"https://api.github.com/users/lossyrob/gists{/gist_id}","starred_url":"https://api.github.com/users/lossyrob/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lossyrob/subscriptions","organizations_url":"https://api.github.com/users/lossyrob/orgs","repos_url":"https://api.github.com/users/lossyrob/repos","events_url":"https://api.github.com/users/lossyrob/events{/privacy}","received_events_url":"https://api.github.com/users/lossyrob/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":14,"created_at":"2015-02-27T16:18:12Z","updated_at":"2015-03-04T20:25:46Z","closed_at":null,"body":"This issue is for figuring out the architecture of an interface that supports the application of Space Filling Curves to a multitude of spaces.\r\n\r\nOne core idea is that we would have as a base a grid space, with dimension `N`, that would be made up of `Long`s. All SFC's would implement mappings from the `N` dimensional space to a lexicographically ordered one dimensional space of `Long` values, which represent the indexed curve through that space. This `N` dimensional space of `Long` values could be thought of as a grid space, so that rectangles in a 2 dimensional grid or cubes in a 3 dimensional grid would be mapped to the 1 dimensional index space (along with an inverse mapping).\r\n\r\nWhere it is required to map another type to the SFC index, say if we wanted to map Lat/Long values to a Z Curve index, then there would first be a mapping of the `(Double, Double)` type to the `(Long, Long)` grid cell. So it is the composition of mappings from some arbitrary space to an N dimensional grid space, and the the SFC implementation mapping the `N` dimensional grid space to the `Long` value of the index. For the inverse, we would take a `Long` index value and map it to the `N` dimensional grid space, and then map that value back to the arbitrary space.\r\n\r\nA more rigorous set of definitions:\r\n\r\nFirst let me here try to come up with a formulation on Space Filling Curves; feel free to comment or correct.\r\n\r\nFor the base implementations of space filling curves, we will be using transformations between spaces of N dimensions and 1 dimension on `Long`s. i.e., the \r\n\r\n`F`<sub>N</sub>: `L`<sup>N</sup> -> `L`\r\n`F`<sub>N</sub><sup>-1</sup>: `L` -> `L`<sup>N</sup>\r\n`R`<sub>N</sub>: (`L`<sup>N</sup>)<sup>N</sup> -> ℘(`L`<sup>2</sup>)\r\n\r\nWhere \r\n`L` = set of Long values\r\n`L`<sup>i</sup> = the `i` dimensional space of Longs. \r\n`N` = Dimensionality of the Domain of `F`. This is the dimensionality of the space which the curve fills.\r\n\r\n`N` is fixed for each implementation, such that a Space Filling Curve implementation will be specifically for `N` dimensions and a specific function `F` and `R`.\r\nIt's unclear to me if a inverse of `R` is needed.\r\n\r\nThe issue here is that we have a space of map coordinates, usually in WGS84 (EPSG:4326, lat\\lng), that we want to order using our Space Filling Curve. So a secondary invertible function, let's call it `M`<sub>2</sub>, must be introduced:\r\n\r\n`M`<sub>2</sub>: `D`<sup>2</sup> -> `L`<sup>2</sup>\r\n`M`<sub>2</sub><sup>-1</sup>: `L`<sup>2</sup> -> `D`<sup>2</sup>\r\n\r\nWhere\r\n`D`<sup>i</sup> = the `i` dimensional space of Doubles.\r\n\r\nso that the composition of `M`<sub>2</sub> and `F`<sub>2</sub> could yield a SFC implementation that uses the Double map coordinates:\r\n\r\n(`F`<sub>2</sub> ∘ `M`<sub>2</sub>): `D`<sup>2</sup> ->  `L`\r\n(`M`<sub>2</sub><sup>-1</sup> ∘ `F`<sub>2</sub><sup>-1</sup>): ->  `D`<sup>2</sup>\r\n\r\nAnd for\r\n`G`<sub>2</sub>: (D<sup>2</sup>)<sup>2</sup> -> (L<sup>2</sup>)<sup>2</sup> where `G`((`m`<sub>1</sub>,`m`<sub>2</sub>)) = (`M`<sub>2</sub>( `m`<sub>1</sub>), `M`<sub>2</sub>( `m`<sub>2</sub>))\r\n\r\nwe have the range function\r\n\r\n(`R`<sub>2</sub> ∘ `G`):  (`D`<sup>2</sup>)<sup>2</sup> -> ℘(`L`<sup>2</sup>)\r\n\r\nTo complicate things, we could also have a time component to our space, so that another function can be introduced,\r\n\r\n`T`: `DT` -> `L`\r\n`T`<sup>-1</sup>: `L` -> `DT`\r\n\r\nWhere\r\n`DT`: Set of `DateTime` values\r\n\r\nSo that our space might be a space of (`D` x `D` x `DT`), so that functions of more fine grained composition must be used to transform these coordinates to a space filling curve:\r\n\r\n`H`: (`D` x `D` x `DT`) -> L<sup>2</sup> \r\n`H`<sup>-1</sup>: L<sup>2</sup> -> (`D` x `D` x `DT`)\r\n\r\nHowever, it might be easier to formulate it with types we can already translate:\r\n\r\n`H`: `D`<sup>2</sup> x `DT` -> `L`<sup>2</sup> where `H`( ( (`m`<sub>1</sub>, `m`<sub>2</sub>), `dt` ) = ( (`M`<sub>2</sub>( `m`<sub>1</sub>), `M`<sub>2</sub>( `m`<sub>2</sub>)) , `T`(`dt`) )\r\n\r\nwhich is an invertible function.\r\n"},"comment":{"url":"https://api.github.com/repos/geotrellis/curve/issues/comments/77239705","html_url":"https://github.com/geotrellis/curve/issues/3#issuecomment-77239705","issue_url":"https://api.github.com/repos/geotrellis/curve/issues/3","id":77239705,"user":{"login":"dsmiley","id":377295,"avatar_url":"https://avatars.githubusercontent.com/u/377295?v=3","gravatar_id":"","url":"https://api.github.com/users/dsmiley","html_url":"https://github.com/dsmiley","followers_url":"https://api.github.com/users/dsmiley/followers","following_url":"https://api.github.com/users/dsmiley/following{/other_user}","gists_url":"https://api.github.com/users/dsmiley/gists{/gist_id}","starred_url":"https://api.github.com/users/dsmiley/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/dsmiley/subscriptions","organizations_url":"https://api.github.com/users/dsmiley/orgs","repos_url":"https://api.github.com/users/dsmiley/repos","events_url":"https://api.github.com/users/dsmiley/events{/privacy}","received_events_url":"https://api.github.com/users/dsmiley/received_events","type":"User","site_admin":false},"created_at":"2015-03-04T20:25:45Z","updated_at":"2015-03-04T20:25:45Z","body":"Responses to @chrisbennight:\r\n> One other item I'd toss out that we've talked about, but haven't implemented, is non-linear normalizations (i.e. the mapping of real value + min/max to a particular \"bucket\" on a dimension.\r\nSticking with univariate values here, if we have some information about the actual distribution of data we could end up with a more normal/uniform representation. This would, in general, have the effect of making the index, access, testing, etc. more efficient/quicker.\r\nThe gotcha is actually getting that distribution (and moreso ensuring it's not bivariate, which would probably be more common, but hurts my head trying to think through (well, doesn't work if we take a dimensions by itself).\r\n\r\nI'm not certain I grok this 100% but it sounds related in concept to an awesome new feature coming to Lucene that auto-prefxes the term data (could be SFC curve byte string or any byte string) on prefix data distribution.  So if hypothetically I index a geohash string for all of my point data, Lucene would recognize that there's a ton of data with a certain prefix and then it would auto-generate prefix (recursively).  It's awesome!  Currently I generate a prefix at every length, which is wasteful.  Ultimately, this feature means PrefixTree/Trie indexes that are ~half the size for the same query performance, or you can tune the other way and keep about the same size and double search speed.  (disclaimer: not committed yet; API details haven't been worked out but it's been benchmarked on numeric data) -- reference: https://issues.apache.org/jira/browse/LUCENE-5879\r\n\r\n> Re: Presentation on representing ranges as x -> y on a 2d index\r\nExactly. What are your thoughts on this performance wise?\r\n\r\nI'm really not sure how it'll shake out; I've thought about it and can see it being faster or slower -- I don't know.  But I do know that it means much smaller indexes.  Take the single dimensional case -- a number range.  Representing a 1D number range as a point in a 2D space will always mean one SFC byte string which has only so many levels to it (like ~8?).  But using a 1D tree means indexing the range fully decomposed -- an SFC for every cell (mini time interval) it covers.  My 1D date tree shows this and is exacerbated that my upper intervals are in millions and then thousands of years at the next level (1k subcells each), which means indexing a range that goes from one moment to the end of time can use a ton of cells (7k cells?  On that order).  So I think this is the leading factor.  But the natural 1D tree is great for analytics I do in which I have just one cell that represents a unit of time that I can aggregate into counts.  You made that kind of connection in your first message -- different encodings benefit different purposes (search vs analytics).\r\n\r\n> Re: capability to take an SFC and enumerate just the next (or selected levels)\r\n\r\nFor reference, in the SpatialPrefixTree API this is *the* way all decoding/encoding happens, even for a Point. So if I want to turn a Point into a single byte string, I call spatialPrefixTree.getTreeCellIterator(point, 12)  (target level is 12), which is an iterator-like thing.  I call .next() 12 times on it and the Cell it returns will have the resulting byte string.  The intermediate .next()'s can have a low cost if I don't actually call methods (to e.g. get the byte array) on the returned Cell (dependent on the implementation)."}}