Z-order curve usage to decrease dimensionality to 1
ssahinkoc.blogspot.com
Z-order curve usage to decrease dimensionality to 1
1–10 of 35 posts
Re: Z-order curve usage to decrease dimensionality to 1
#2Can 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?
Re: Z-order curve usage to decrease dimensionality to 1
#3AKA a geohash (for the lat/lon example), but can easily be extended to other bounded dimensions.
Re: Z-order curve usage to decrease dimensionality to 1
#4As the first commenter on the site pointed out, the Hilbert Curve is probably a better choice (https://en.m.wikipedia.org/wiki/Hilbert_curve)
Re: Z-order curve usage to decrease dimensionality to 1
#5As the first commenter on the site pointed out, the Hilbert Curve is probably a better choice ( https://en.m.wikipedia.org/wiki/Hilbert_curve )
Moore curves are also worth considering.
Re: Z-order curve usage to decrease dimensionality to 1
#6As the first commenter on the site pointed out, the Hilbert Curve is probably a better choice ( https://en.m.wikipedia.org/wiki/Hilbert_curve )
The big advantage of Z-order curves is that the addressing computation is very cheap, which is why it's used a lot in computer graphics.
Re: Z-order curve usage to decrease dimensionality to 1
#7Space-filling curves have been studied as a way to reduce N-dimensional space to 1-D. They are very useful for applications like maximizing sequential access in a N-D datastore. A recent SIGMOD paper analyzed space-filling curves impact on data access:
http://dl.acm.org/authorize.cfm?key=N37709
QUILTS: Multidimensional Data Partitioning Framework Based on Query-Aware and Skew-Tolerant Space-Filling Curves Shoji Nishimura (NEC Corporation); Haruo Yokota (Tokyo Institute of Technology)
It discusses C-Curve, Z-Curve, and Hilbert curves.
Re: Z-order curve usage to decrease dimensionality to 1
#8Usually a Morton ordering is used for things like improving average memory locality of N-dimensional data (e.g., loop iteration order, data layout, ...). But it is average locality that is being improved, because of huge jumps between many neighbors.
In a small number of dimensions, without knowing what search algorithm is being used, this is just more work than comparing the original values. It doesn't mention what "k-NN algorithm" is being used, beyond brute force search.
Lossily compressing N-dimensional data (from 2 to 1000s of dimensions) into a representation that requires fewer bits can be done via quantization as well, either scalar quantization, vector quantization (aka k-means) or product quantization, if your data has known statistics.
It also matters if you are building a static data structure that is queried many times, versus one that needs continual updating.
Re: Z-order curve usage to decrease dimensionality to 1
#9Can 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.
Re: Z-order curve usage to decrease dimensionality to 1
#10As the first commenter on the site pointed out, the Hilbert Curve is probably a better choice ( https://en.m.wikipedia.org/wiki/Hilbert_curve )
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), the sole selling point of Hilbert curves is moot. You shouldn't design most systems in a way that could exploit the benefits of a Hilbert curve.