1

I've read that space-filling curves such as the Peano curve are useful for maintaining cache-friendly data structures in a linear address space, since they maintain physical spatial locality.

However, I'm not sure how to actually use them. Do any of these curves have formulas for quickly translating a linear address into (x,y) coordinates and vice-versa? Otherwise, how do I determine where in memory to look when looking up a certain pair of coordinates? An example would be very helpful.

user541686
  • 205,094
  • 128
  • 528
  • 886
  • The [Z-order curve](http://en.wikipedia.org/wiki/Z-order_curve) has a pretty efficient mapping (just interleave the bits of the coordinates). I've only seen it used for locality-sensitive hashing though, not to actually lay out things in memory. –  Jan 11 '15 at 22:52
  • @delnan: Oh... is there any that's used to lay things out in memory? – user541686 Jan 11 '15 at 22:57
  • I never heard of *any* such curve being used to lay things out in memory. Skimming over the Wikipedia article, it appears some people actually did lay out matrices in this order for Strassen's algorithm. I just never heard of it before. I'm pretty skeptical about the benefits in most circumstances, too. –  Jan 11 '15 at 23:00

1 Answers1

1

As stated in the comment translate the co-ordinate to a binary and interleave it. Then treat it a base-4 number if you want a quadkey.

Micromega
  • 12,486
  • 7
  • 35
  • 72