A practical use for space-filling curves
www2.isye.gatech.edu
www2.isye.gatech.edu
http://www.devmaster.net/forums/showthread.php?t=10125
http://en.wikipedia.org/wiki/Z-order_curve
From distant memory - switching to a variant of this from simple row major order textures gave > 20% increase in a scene rendering benchmark (software pipe, full scene, no game logic). Prior to that I had been doing daft things like having textures stored in column or row major order depending on their 'usual' orientation.
A good book: Foundations of Multidimensional and Metric Data Structures by Hanan Samet 2006
A good paper: Interactive SPH Simulation and Rendering on the GPU by Goswami
I remember using Morton Order for memory layout of dense matrix operations. Very handy and much better than row or column major order. At the time, I was using this for wavelet operations.
Some of the nastiest C code I ever wrote from a readability perspective. The experience permanently scarred me - prior to doing it, I wrote nice, clean C. After, I couldn't read my own code after a week . . .
It's useful any time you are accessing higher-rank arrays in a spatially coherent manner without any directional bias.
Bit interleaving only works with power-of-two dimensions. That's limiting. But for the cache benefits you don't need self-similarity at all levels. For less regularly sized arrays, you can play this trick with only some slices of lower bits, and then it's usually called tiling.
Scientific computing people also do this whenever they want to lay out a matrix in memory so that it efficiently supports both row-coherent and column-coherent access, which is required for basic operations like matrix multiplication. You can formulate tiled matrix multiplication in terms of smaller tile vs tile multiplications.
The earliest GPUs supported only square power-of-two-sized textures using swizzling. Later ones like the GeForce FX supported non-square, non-power-of-two textures using a simple memory unit with tiling. But the total number of tiles in use was a limited and non-scaleable resource, and once you exceeded the limit you fell off a performance cliff. Finally, the last two generations of GPUs (starting with the G80 microarchitecture in NVIDIA's case) have a more scaleable multi-level tiling approach that combines benefits of both swizzling and tiling although with higher hardware complexity than either of them.
My coworker wrote a great blog post on fast multi-level tiling in software: http://fgiesen.wordpress.com/2011/01/17/texture-tiling-and-s...
Or, of course, use one of the thousands of other heuristics, most of which will likely provide as good an answer in as short a time as this heuristic. I mean, why provide comparisons to comparable heuristics? That would be like doing science.
http://www.google.com/search?q=comparison+of+heuristics+for+...
It depends on what you actually want, but here are two links that might be the sort of thing you're looking for:
http://www.agent.ai/doc/upload/200302/stut00.pdf
http://www.psych.lancs.ac.uk/people/uploads/TomOrmerod200712...
But let me just say that I found your reply to be unnecessarily nasty in its tone - snippy and snarky. You seem simply to be criticising the authors because they produced a brief paper describing a particular heuristic, and you seem simply to be demanding that they do go further than they have in this paper. Perhaps they already have, perhaps it's work in process.
I find it frustrating when people criticise a link largely because it is what it is and isn't something else. If you want something on comparisons, go find it. Or alternatively, do the work yourself. Then regardless, come and share your results.
Apart from the claim that it beats competitors, it's a really interesting post, though; light-weight heuristics based on clever connections are interesting in their own right. (So I sort of agree on the tone.)
If so, remember that HN readers tend to be a lot more critical of the article than towards other comments.
Anyway, the article didn't really claim to be the fastest heuristic, just an elegant one with some nice properties. It's O(n log n) - what more do people want? O(n)? O(1)? n log n is almost always fast enough.
user: RiderOfGiraffes created: 822 days ago karma: 18098
I'm not the author, not connected with the author, and don't know the author. I found the "paper" and thought "That's neat and elegant."
Yes, we could do with a complete analysis of all existing algorithms and heuristics, finding the strengths and weaknesses, and for each one, finding and characterising cases where they do well and cases where they do badly.
But personally, I like to see papers like this, papers that can be considered to be a "work in progress." I don't want only to read about studies that are exhaustive, complete, and answer all the questions. I think there is value in seeing descriptions of algorithms, along with a simple comparison to known algorithms largely for the purpose of understanding the detail and the potential.
This is an invitation to explore, not a closed and completed "job done." This is an invitation to Google for other heuristics to enhance my understanding of the field. This is an invitation to wonder if my unique range of experience and skills might find a better heuristic.
Full analysis is the work of a Ph.D. and more. Don't expect it in a paper on the web.
While this is cute, I strongly believe that any simple algorithms will compare. Also they seem to hint there is a lack of parallelisable algorithms. Many people have already done work on parallelising TSP by space partitioning.
The team behind that effort has made their software available (CONCORDE - http://www.tsp.gatech.edu//concorde/index.html), and includes a few standard heuristics that are already quite fast:
- for the record, the space-filling curve approach takes less than a second and produces a tour 33% larger than the optimal, which is roughly 1573084*4/3=2097445
- the "greedy" heuristic takes less than a second and computes a solution with length 1803479, which is already better than the space-filling curve
- the "quick boruva" heuristic is even faster and produces a solution with length 1789519 (less than 14% larger than optimal)
- the "Lin Kernighan" heuristic takes a few minutes and produces a solution with length 1577339 (less than 0.3% larger than optimal)
So, while this is an interesting application of space-filling curves, it cannot really be considerered to be competitive with the state-of-the-art in TSP heuristics.
I'm using this right now to visualize sequence coverage depth across the human genome (an integer vector of length 3 billion).
Is this a property or mere probability? What are the random point sets for TSP testing? Given n points in a plane , the number of Hamiltonian paths can be drawn is (n-1)!. One of these is minimum, and our optimum solution to TSP. If we distribute the frequencies of the lengths of these graphs, (is there a particular name for this graph?) we will find the probability of a particular length-range occurring. This graph, should be different for different complete graphs. So an improvement might simply be that the 'high ridges' on such graph of input of random sets given , lay towards the left sides of 'peak'.
>A useful property of a spacefilling curve is that it tends to visit all the points in a region once it has entered that region. Thus points that are close together in the plane will tend to be close together in appearance along the curve.
Or very far! Like points around averaged areas (like middle lines, etc) and spacefilling curves do generate averaged areas. Eg yellow points around blue middle lines here http://i.imgur.com/Dl7Vo.gif
NB: I do not mean to criticize. asking questions.
A reason for my reasoning: they visit things in a certain order. It's therefore possible to design a path that falls directly on non-optimal points along a certain order of that curve; I'd guess you could get multiple times the shortest length, instead of just 25% greater. But you can get a new path by simply increasing / decreasing the order of the curve, so running through a few iterations could probably get you an exceptionally-good result for the sort of speed it provides.
(And, of course, IP addresses: http://xkcd.com/195/)
Modeling how (they think) human vision works, they made a heuristic based on clustering and top-down refinement. The map is clustered into a small handful of groups, and these groups are placed in a shortest tour. Each cluster is then clustered in turn into another handful of sub-groups, and these sub-groups are inserted into the tour at the position of their parent.
The pyramid algorithm is highly parallel with, IIRC, the same time characteristics as the space-filling curve algorithm.
What made the connection in my mind was that the simplest implementation of the pyramid algorithm is to cluster by simply dividing the map into quadrants; when you do so, you end up with the same space-filling curve they use at the top of the page.