Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Z-order curve usage to decrease dimensionality to 1

ssahinkoc.blogspot.com

Post reply on HN
Print view View original

11–20 of 35 posts

Re: Z-order curve usage to decrease dimensionality to 1

#11

Post by oppositelock »

hex12648430 wrote: post #6
mcphage wrote: post #4

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 )

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.

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.

Re: Z-order curve usage to decrease dimensionality to 1

#12

Post by jacobolus »

oppositelock wrote: post #11
hex12648430 wrote: post #6

Earlier quoted context omitted.

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.

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

Re: Z-order curve usage to decrease dimensionality to 1

#13

Post by albipenne »

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

Re: Z-order curve usage to decrease dimensionality to 1

#15

Post by minflynn »

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.

Re: Z-order curve usage to decrease dimensionality to 1

#16

Post by leni536 »

hex12648430 wrote: post #6
mcphage wrote: post #4

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 )

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.

While I agree that Z-order curves are simpler, but it's fast to calculate Hilbert curves on modern CPUs too. Just to self plug:

https://github.com/leni536/fast_hilbert_curve

I only implemented the index->XY calculation yet. It compiles to 36 instructions without any branches and takes up 86 bytes.

https://github.com/leni536/fast_hilbert_curve/wiki/How-effic...

I think I can apply the same tricks for the inverse function too.

Re: Z-order curve usage to decrease dimensionality to 1

#17

Post by vanderZwan »

mcphage wrote: post #4

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 )

H-curves are probably optimal with regards to locality, but good luck finding an implementation:

http://www.akt.tu-berlin.de/fileadmin/fg34/publications-akt/...

https://www.reddit.com/r/ProgrammerHumor/comments/4xzi9a/oh_...

Re: Z-order curve usage to decrease dimensionality to 1

#18

Post by a_e_k »

vanderZwan wrote: post #17
mcphage wrote: post #4

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 )

H-curves are probably optimal with regards to locality, but good luck finding an implementation: http://www.akt.tu-berlin.de/fileadmin/fg34/publications-akt/... https://www.reddit.com/r/ProgrammerHumor/comments/4xzi9a/oh_...

It doesn't need to be that complicated at all. The book "Hacker's Delight" gives some nice, fairly simple implementations. Here's one:

http://www.hackersdelight.org/hdcodetxt/hilbert/lams.c.txt

Post reply on HN