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

21–30 of 35 posts

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

#21

Post by m1el »

leni536 wrote: post #16
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.

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 funct…

But using the same set of instructions, z-order encoding and decoding is 8 instructions (5 if you exclude size conversion and return):

    zorder64_inv:
        movabsq $0x5555555555555555, %rax
        pextq   %rax, %rcx, %rdx
        shrq    %rcx
        pextq   %rax, %rcx, %rcx
        shlq    $32, %rcx
        movl    %edx, %eax
        orq     %rcx, %rax
        retq

    zorder64:
        movl    %ecx, %eax
        movabsq $0x5555555555555555, %r8
        pdepq   %r8, %rax, %rcx
        movl    %edx, %eax
        pdepq   %r8, %rax, %rax
        addq    %rax, %rax
        orq     %rcx, %rax
        retq

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

#22

Post by vanderZwan »

a_e_k wrote: post #18
vanderZwan wrote: post #17

Earlier quoted context omitted.

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

H-curves are not Hilbert curves! I know, the name is very confusing, but read the PDF: H-curves have better locality than Hilbert curves (possibly even optimal).

And I'm sure that constructing H-curves doesn't need to be as complicated as that linked academic code makes it look, but for now I don't know of any implementation.

Thanks for the link though :)

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

#23

Post by leni536 »

m1el wrote: post #21
leni536 wrote: post #16

Earlier quoted context omitted.

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 funct…

But using the same set of instructions, z-order encoding and decoding is 8 instructions (5 if you exclude size conversion and return): zorder64_inv: movabsq $0x5555555555555555, %rax pextq %rax, %rcx, %rdx shrq %rcx pextq %rax, %rcx, %rcx shlq $32, %rcx movl %edx, %eax orq %rcx, %rax retq zorder64: movl %ecx, %eax movabsq $0x5555555555555555, %r8 pdepq %r8, %rax, %rcx movl %edx, %eax pdepq %r8, %rax, %rax addq %rax,…

Nice! Now I wonder when 36 vs 8 machine instructions become a bottleneck. I have seen applications of space-filling curves in quasi Monte Carlo integration, it could be potentially significant there.

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

#25

Post by MarkMMullin »

dweekly wrote: post #14

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-... And 2015 HN thread: https://news.ycombinator.com/item?id=10066616

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

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

#26

Post by sp332 »

teddyh wrote: post #19

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

On a lark I plugged this into Google 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?

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

#27

Post by DocSavage »

jandrewrogers wrote: post #10
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 )

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 appetite. Are there no public reviews or papers covering discrete topology/sharding?

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

#29

Post by mmalone »

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.

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

#30

Post by mmalone »

leitasat wrote: post #28

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.

True, but it is much better at preserving closeness than the alternative he mentioned (lexicographical sort).
Post reply on HN