News for hackers. Stuff that matters.
Re:Z-order curve usage to decrease dimensionality to 1 by mcphage on Monday June 12, 2017 @10:09PM (#14542470)
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)
Re:Z-order curve usage to decrease dimensionality to 1 by jandrewrogers on Monday June 12, 2017 @11:26PM (#14542690)
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.

Re:Z-order curve usage to decrease dimensionality to 1 by DocSavage on Tuesday June 13, 2017 @10:47AM (#14545107)
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 by jandrewrogers on Tuesday June 13, 2017 @12:25PM (#14545986)
There are two design factors that most people overlook:

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.

Re:Z-order curve usage to decrease dimensionality to 1 by hex12648430 on Monday June 12, 2017 @10:33PM (#14542536)
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 by leni536 on Tuesday June 13, 2017 @03:28AM (#14543357)
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 by m1el on Tuesday June 13, 2017 @07:13AM (#14543989)
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 by leni536 on Tuesday June 13, 2017 @08:28AM (#14544250)
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 by oppositelock on Monday June 12, 2017 @11:29PM (#14542701)
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 by jacobolus on Tuesday June 13, 2017 @12:13AM (#14542816)
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 by leni536 on Tuesday June 13, 2017 @03:58PM (#14548071)
There is an error-diffusion dithering algorithm based on the Hilbert-curve called Riemersma dither.

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.

Re:Z-order curve usage to decrease dimensionality to 1 by vanderZwan on Tuesday June 13, 2017 @05:17AM (#14543676)
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 by a_e_k on Tuesday June 13, 2017 @05:53AM (#14543771)
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

Re:Z-order curve usage to decrease dimensionality to 1 by vanderZwan on Tuesday June 13, 2017 @08:21AM (#14544217)
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 by yarg on Monday June 12, 2017 @10:17PM (#14542489)
Moore curves are also worth considering.