31–35 of 35 posts
Can someone help explaining why this hash method could improve distance calculation for k-NN? What does it improve compared with Geohash or k-d tree structure?
> What does it improve compared with Geohash From what I can tell, it's the exact same algorithm used by Geohash.
Earlier quoted context omitted.
Hilbert curve is only useful if the sole goal is sequential storage of point data. Z-curves are superior in almost every other case in real systems due to their unique and efficient computational properties, which many computer scientists are only vaguely aware of. And since modern spatial database architectures don't sequentialize storage along the curve (because it doesn't make sense as a matter of engineering), th…
Could you elaborate on your comment about modern spatial databases not sequentializing storage along the curve? I would imagine parallel access across the curve, but wouldn't you want some reasonable sequential access at each cluster node to maximize IO speeds? I've read your blog entries on SpaceCurve ( http://www.jandrewrogers.com/2015/10/08/spacecurve/ ), found them very interesting but also just whetting the appe…
Most people know you can use Z/C-curve encodings to dynamically content address point data. There is a (very useful) generalization to hyper-rectangle types, perfect for content-addressing non-point geometries etc, but those types can't be meaningfully sequentialized at all in big systems. Most non-trivial spatial analytics involve non-point geometries, so being able to sequentialize points has limited utility.
Second, the computational cost of sorting along the curve, assuming you are using only points, is prohibitively high for negligible benefit. Modern storage engines use small shards, which are adaptively re-sharded as needed, and medium-sized pages. For insert, the content-addressing mechanic gets you to a single page; it would be significantly more expensive if you were sorting along the curve. For query, the typical selectivity on a shard is so high due to small adaptive shards, that you are better off treating it as an unsorted vector anyway. In short, much slower inserts and few (if any) query benefits.
As an optimization, it tends to only be applicable in cases where the architecture is significantly suboptimal anyway e.g. the use of gigantic shards. You'd get more benefit by fixing the architecture than trying to optimize poor architecture if at all possible.
Can someone help explaining why this hash method could improve distance calculation for k-NN? What does it improve compared with Geohash or k-d tree structure?
2. It won't be better than a k-d tree. Dimensionality reduction is usually done when you have really truly huge numbers of dimensions that are sparsely populated and you don't care much about some information loss (e.g., for machine learning) or, in this case, when you have an easy way to create a single dimensional index and you want to force multi-dimensional data into it. In the general case a k-d tree would be objectively better in terms of performance.
Can someone help explaining why this hash method could improve distance calculation for k-NN? What does it improve compared with Geohash or k-d tree structure?
1. A geohash is a z-curve. 2. It won't be better than a k-d tree. Dimensionality reduction is usually done when you have really truly huge numbers of dimensions that are sparsely populated and you don't care much about some information loss (e.g., for machine learning) or, in this case, when you have an easy way to create a single dimensional index and you want to force multi-dimensional data into it. In the general…
Earlier quoted context omitted.
Hilbert curves are used in a lot of graphics too. Heck, the old SGI Octane with Vpro graphics used a recursive Hilbert curve rasterizer. They show up a lot today in geospatial big-data since hilbert addresses make good shard keys.
I suspect that most production applications of Hilbert curve ordering would work just as well with Z order (a.k.a. Morton order), with the additional benefit of being simpler to reason about (just interleave/de-interleave the bits). I haven’t ever seen any convincing benchmarks or other analysis where the Hilbert curve created any notable performance advantage vs. Z order; the only time you really need it is if movin…
https://www.compuphase.com/riemer.htm
I suspect that error diffusion along the long jumps of a z-order curve could create strange undesired artifacts.