7 ms·

Z-order curve usage to decrease dimensionality to 1

105 points by delidumrul 9y ago

zocoi 9y ago
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?
- imron 9y ago
  > What does it improve compared with Geohash From what I can tell, it's the exact same algorithm used by Geohash.
  - mmalone 9y ago
    Yep. Geohash is just a fancy name for a z-curve.
- mmalone 9y ago
  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 case a k-d tree would be objectively better in terms of performance.
  - AstralStorm 9y ago
    And in very many or highly sparse dimensions with few or lazy updates, R-tree or derivatives.
aeroevan 9y ago
AKA a geohash (for the lat/lon example), but can easily be extended to other bounded dimensions.
mcphage 9y ago
As the first commenter on the site pointed out, the Hilbert Curve is probably a better choice (https://en.m.wikipedia.org/wiki/Hilbert_curve https://en.m.wikipedia.org/wiki/Hilbert_curve)
- yarg 9y ago
  Moore curves are also worth considering.
- hex12648430 9y ago
  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.
  - oppositelock 9y ago
    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.
    - jacobolus 9y ago
      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 moving along the linearized coordinate must never have jumps in the multidimensional coordinates, but I’m not convinced there are many if any real-world cases where that is important (note that in either case small movements in the multidimensional coordinates are associated with large jumps in the linearized coordinate). If the only goal is to minimize memory fetches, etc. then the Z ordering works just fine. (If you know any good comparisons where the Hilbert curve comes out ahead, I’d be curious to read them.)
DocSavage 9y ago
Space-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 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.
jhj 9y ago
Usually 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.
albipenne 9y ago
Here's a great write up on how you can use Z-curves to do multidimensional sorting using redis otherwise 1 dimensional sorted set datastructure. It's one of the best hands on examples on a way to solve real problems using this tech within your stack. https://redis.io/topics/indexes https://redis.io/topics/indexes
dweekly 9y ago
Here is a writeup on Google's S2 library for considering addressing the surface of the Earth as 1D, using Hilbert Curves. http://blog.christianperone.com/2015/08/googles-s2-geometry-on-the-sphere-cells-and-hilbert-curve/?a=2 http://blog.christianperone.com/2015/08/googles-s2-geometry-... And 2015 HN thread: https://news.ycombinator.com/item?id=10066616 https://news.ycombinator.com/item?id=10066616
- MarkMMullin 9y ago
  My favorite has always been Serpinski curve - the math behind Philip Jose Farmer's Riverworld :-) Here, you can print one yourself :-) https://www.thingiverse.com/thing:622627 https://www.thingiverse.com/thing:622627
minflynn 9y ago
I've used Z-order curves and related curves in Neuroevolution research. It allows conversion of an adjacency matrix to a spatial subtrate representation that preserves locality as it grows (Thus going from 1 dimension to 2 or 3). This technique is an alternative for HyperNEAT or ES-HyperNEAT and experiments demonstrate higher performance that ES-HyperNEAT on the modular retina task problem.
teddyh 9y ago
So how would https://xkcd.com/195/ https://xkcd.com/195/ look using a z-curve instead?
- VMG 9y ago
  I'd imagine it would look less continuous: some of the areas would be ripped apart and spread across the map.
- sp332 9y ago
  On a lark I plugged this into Google https://encrypted.google.com/search?num=20&hl=en&q=https%3A%2F%2Fxkcd.com%2F195%2F+z-order+curve https://encrypted.google.com/search?num=20&hl=en&q=https%3A%... and if you peer at the results, you can see that Google is highlighting "Hilbert curve" as if it were matching one of my search terms. I guess that its algorithm has "learned" that Hilbert curve is a synonym for z-order curve?
Joboman555 9y ago
This stuff mostly goes over my head, but I'd like to understand it. In the original method, why is op concatenating the two positions into one number, rather than just storing the lat/lon pair and using something like Euclidean distance?
leitasat 9y ago
As the commentators on the website mentioned, this method does not preserve the closeness of the points (when going from 2D to 1D), so it is unclear how can it help the author.
- mmalone 9y ago
  True, but it is much better at preserving closeness than the alternative he mentioned (lexicographical sort).
mmalone 9y ago
If you're tempted to use space filling curves (z-curves, hilbert curves, etc.) you should take a look at simple multi-dimensional data structures as an alternative. As a couple of people have mentioned in this thread, space filling curves aren't great at preserving locality (i.e., two points that are "close together" in two dimensional space might end up being "far apart" in one dimensional space, and vice versa). A k-d tree is easy to code up and, in general, will be more efficient for queries like k-NN than dimensionality reduction because it's better at preserving locality. There are also good libraries for multi-dimensional data structures for pretty much any mainstream language.

105 points by delidumrul 9y ago

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?

imron 9y ago
> What does it improve compared with Geohash From what I can tell, it's the exact same algorithm used by Geohash.
- mmalone 9y ago
  Yep. Geohash is just a fancy name for a z-curve.
mmalone 9y ago
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 case a k-d tree would be objectively better in terms of performance.
- AstralStorm 9y ago
  And in very many or highly sparse dimensions with few or lazy updates, R-tree or derivatives.

aeroevan 9y ago

AKA a geohash (for the lat/lon example), but can easily be extended to other bounded dimensions.

mcphage 9y ago

As the first commenter on the site pointed out, the Hilbert Curve is probably a better choice (https://en.m.wikipedia.org/wiki/Hilbert_curve https://en.m.wikipedia.org/wiki/Hilbert_curve)

yarg 9y ago
Moore curves are also worth considering.
hex12648430 9y ago
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.
- oppositelock 9y ago
  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.
  - jacobolus 9y ago
    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 moving along the linearized coordinate must never have jumps in the multidimensional coordinates, but I’m not convinced there are many if any real-world cases where that is important (note that in either case small movements in the multidimensional coordinates are associated with large jumps in the linearized coordinate). If the only goal is to minimize memory fetches, etc. then the Z ordering works just fine. (If you know any good comparisons where the Hilbert curve comes out ahead, I’d be curious to read them.)

DocSavage 9y ago

Space-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 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.

jhj 9y ago

Usually 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.

albipenne 9y ago

Here's a great write up on how you can use Z-curves to do multidimensional sorting using redis otherwise 1 dimensional sorted set datastructure. It's one of the best hands on examples on a way to solve real problems using this tech within your stack. https://redis.io/topics/indexes https://redis.io/topics/indexes

dweekly 9y ago

Here is a writeup on Google's S2 library for considering addressing the surface of the Earth as 1D, using Hilbert Curves. http://blog.christianperone.com/2015/08/googles-s2-geometry-on-the-sphere-cells-and-hilbert-curve/?a=2 http://blog.christianperone.com/2015/08/googles-s2-geometry-... And 2015 HN thread: https://news.ycombinator.com/item?id=10066616 https://news.ycombinator.com/item?id=10066616

MarkMMullin 9y ago
My favorite has always been Serpinski curve - the math behind Philip Jose Farmer's Riverworld :-) Here, you can print one yourself :-) https://www.thingiverse.com/thing:622627 https://www.thingiverse.com/thing:622627

minflynn 9y ago

I've used Z-order curves and related curves in Neuroevolution research. It allows conversion of an adjacency matrix to a spatial subtrate representation that preserves locality as it grows (Thus going from 1 dimension to 2 or 3). This technique is an alternative for HyperNEAT or ES-HyperNEAT and experiments demonstrate higher performance that ES-HyperNEAT on the modular retina task problem.

teddyh 9y ago

So how would https://xkcd.com/195/ https://xkcd.com/195/ look using a z-curve instead?

VMG 9y ago
I'd imagine it would look less continuous: some of the areas would be ripped apart and spread across the map.
sp332 9y ago
On a lark I plugged this into Google https://encrypted.google.com/search?num=20&hl=en&q=https%3A%2F%2Fxkcd.com%2F195%2F+z-order+curve https://encrypted.google.com/search?num=20&hl=en&q=https%3A%... and if you peer at the results, you can see that Google is highlighting "Hilbert curve" as if it were matching one of my search terms. I guess that its algorithm has "learned" that Hilbert curve is a synonym for z-order curve?

Joboman555 9y ago

This stuff mostly goes over my head, but I'd like to understand it. In the original method, why is op concatenating the two positions into one number, rather than just storing the lat/lon pair and using something like Euclidean distance?

leitasat 9y ago

As the commentators on the website mentioned, this method does not preserve the closeness of the points (when going from 2D to 1D), so it is unclear how can it help the author.

mmalone 9y ago
True, but it is much better at preserving closeness than the alternative he mentioned (lexicographical sort).

mmalone 9y ago

If you're tempted to use space filling curves (z-curves, hilbert curves, etc.) you should take a look at simple multi-dimensional data structures as an alternative. As a couple of people have mentioned in this thread, space filling curves aren't great at preserving locality (i.e., two points that are "close together" in two dimensional space might end up being "far apart" in one dimensional space, and vice versa). A k-d tree is easy to code up and, in general, will be more efficient for queries like k-NN than dimensionality reduction because it's better at preserving locality. There are also good libraries for multi-dimensional data structures for pretty much any mainstream language.