5 ms·

Onion Curve: A Space Filling Curve with Near-Optimal Clustering (2018)

86 points by espeed 7y ago

gefh 7y ago
I don't get it. It looks like a spiral. If your query is anywhere other than the center of the space, how is the locality maximized? For a large enough space, didn't this look just like striping rather vertically or horizontally?
- benrbray 7y ago
  From the abstract, it looks like they're optimizing for rectangular queries instead of single points. For a single point, I think you're right. > We present the onion curve, an SFC whose clustering performance is provably close to optimal for cube and nearcube shaped query sets (Edit: But on the other hand this paper has some signs of inexperienced authors, such as this sentence: "A search for applications of space filling curves yields more than a thousand citations on Google Scholar")
  - saalweachter 7y ago
    This is does seem like a trivial optimization over striping. If your target area is small relative to your potential search space -- imagine your grid is a million by million rows and you are selecting rectangles that are between 10 and 1000 units wide in either dimension -- you'll end up with height or width number of rows or columns to search, most of the time. Meanwhile, if your target area is large compared to your potential search space ... you also end up with height or width number of L-shaped segments to search along. You only end up with fewer segments if your search area happens to include the center. Also, not actually a space-filling curve.
pfedak 7y ago
I'm disappointed, I was looking forward to seeing a new fractal. The onion curve in 2d is just a spiral, as mentioned, but the word "spiral" doesn't appear at all. I think this paper is mostly without merit, unfortunately. Egregiously, the table comparing the (reasonably defined, I think) clustering metric of the spiral with the Hilbert curve is only for rectangular queries which ask for almost the entire space, with the query side length differing from the overall space's side length by a constant. An obvious advantage of the fractal nature of the Hilbert curve is that its clustering properties will be scale invariant, but the spiral will quickly degrade to a "space filling curve" that just goes row by row for small queries. Perhaps later the paper gives some reason to hope for the onion curve, but I'm disinclined to look.
- geophile 7y ago
  I was sure I was misunderstanding the paper, but my quick read matches yours. They seem to be analyzing just this one query. Another error is that just counting the number of times the curve passes in and out of the query is too simplistic. With z-order, and presumably with Hilbert curves, you can grow the query very slightly to greatly reduce this number. Then you just have to filter out the false positives. I've implemented all this using z-order, in a variety of systems, including a relational database query engine, it works really well.
- colanderman 7y ago
  Agreed. It's not even clear to me how this spiral qualifies as "space-filling". Where's the bijection between ℝ×ℝ and ℝ? Obviously if the curve were space-filling, the mapping is a function of the distance from the center, but this isn't bijective. I'm exiting my area of expertise here, but Wikipedia claims that "no differentiable space-filling curve can exist." [1] A trivial modification of this curve – rounding the corners – would be differentiable without changing anything about it (it doesn't need the corners to cover all the space), so something doesn't smell right. [1] https://en.wikipedia.org/wiki/Space-filling_curve#Properties https://en.wikipedia.org/wiki/Space-filling_curve#Properties
  - alkonaut 7y ago
    I'm even further from my armchair comfort zone but I'll try: You can round the corners of the Hilbert curve too? I think what's implied by the non-differentiabilty statement is that it must apply generally for infinitesimal cells. So you can round the turns but that needs space, and for general differentiability of the SFC you need to be able to do a rounded turn in (almost) no space at all. The mapping does appear to be bijective - but I agree they should have presented the inverse in more detail! They state an SFC is a bijective function, but don't make the case for why O(i,j) is bijective? Again, I may be reading this wrong, I get a mild impostor syndrome attack every time I read a scientific article.
    - afiori 7y ago
      > I'm even further from my armchair comfort zone but I'll try: You can round the corners of the Hilbert curve too? This is supposed to be close to my area of expertise, I will try to give a precise answer. The usual finite Hilbert curve is not space filling. the property of the Hilbert curve is that successive iterations converge to a continuous space filling curve. There are well known techniques to transform continuous function in differentiable functions (https://en.wikipedia.org/wiki/Convolution#Differentiation https://en.wikipedia.org/wiki/Convolution#Differentiation) furthermore you can "smooth" the finite Hilbert curves so that the limit remains the same. But the true Hilbert curve (that is the limit of the finite approximations) will not be differentiable even if built as a limit of differentiable functions.
vlmutolo 7y ago
I immediately thought of xkcd's post on Rolle's Theorem. https://xkcd.com/2042/ https://xkcd.com/2042/
- geophile 7y ago
  I think you are confusing common sense and nonsense.
miga 7y ago
The metric seems misleading, as it is one-sided. It only checks how many clusters we look through, but not how much of the unnecessary data one needs to examine. Most indices optimize the amount of data that does not need to be browsed when querying, this index seems to maximize the amount of data that needs to be looked in a linear part of the processing.
goodmachine 7y ago
Slightly off-topic, but if you're interested in SFC's in general (in any number of dimensions) then Herman Haverkort's work should definitely be of interest, includes a new scheme for curve classification. Sixteen space-filling curves and traversals for d-dimensional cubes and simplices (2018) https://arxiv.org/abs/1711.04473 https://arxiv.org/abs/1711.04473 BTW, Haverkort has fascinating application: he uses SFC traversals to generate music. To my ear, they sound surprisingly good. http://herman.haverkort.net/doku.php?id=sound_of_space-filling_curves http://herman.haverkort.net/doku.php?id=sound_of_space-filli...
graphpapa 7y ago
I assumed this was a joke paper
bhl 7y ago
On a related note, does anyone know of a good reference of applying space filling curves as a method of dimensionality reduction? It seems like an intuitive idea since Hilbert curves [1] map points from a higher to a lower dim space but tries to preserve distance as well. [1] 3Blue1Brown video on Hilbert curves: https://www.youtube.com/watch?v=3s7h2MHQtxc https://www.youtube.com/watch?v=3s7h2MHQtxc
muxator 7y ago
> [...] an SFC is critical to the efficiency of multi-dimensional indexes [...] Apart from spatial databases, could anyone give some examples about advanced applications of Space Filling Curves for indexing?
enriquto 7y ago
I would not call that a space-filling curve. The hilbert curves that are drawn are iterations towards a limit. These spirals do not converge to a limiting curve that fills the space.
mcnamaratw 7y ago
It looks homebrewed. But I'm going to buck the trend and say I think there is net value here for engineers. (I have no idea whether the paper is original research or not.) Weaknesses: (W1) They should say "spiral." (W2) "Optimal" seems a little enthusiastic. They should talk mostly about queries that aren't chosen to be optimal for the spiral. Value: (V1) The central idea of the paper becomes clear in a few minutes. That's a very small investment for the reader. (V2) They show that copying the "magic" Hilbert curve can be worse than just thinking and picking something for yourself. That seems to be true even for box-shaped queries that don't enclose the center of the spiral. But I think the value here is not "use a spiral." It's "consider a bunch of different scan shapes."

86 points by espeed 7y ago

gefh 7y ago

I don't get it. It looks like a spiral. If your query is anywhere other than the center of the space, how is the locality maximized? For a large enough space, didn't this look just like striping rather vertically or horizontally?

benrbray 7y ago
From the abstract, it looks like they're optimizing for rectangular queries instead of single points. For a single point, I think you're right. > We present the onion curve, an SFC whose clustering performance is provably close to optimal for cube and nearcube shaped query sets (Edit: But on the other hand this paper has some signs of inexperienced authors, such as this sentence: "A search for applications of space filling curves yields more than a thousand citations on Google Scholar")
- saalweachter 7y ago
  This is does seem like a trivial optimization over striping. If your target area is small relative to your potential search space -- imagine your grid is a million by million rows and you are selecting rectangles that are between 10 and 1000 units wide in either dimension -- you'll end up with height or width number of rows or columns to search, most of the time. Meanwhile, if your target area is large compared to your potential search space ... you also end up with height or width number of L-shaped segments to search along. You only end up with fewer segments if your search area happens to include the center. Also, not actually a space-filling curve.

pfedak 7y ago

I'm disappointed, I was looking forward to seeing a new fractal. The onion curve in 2d is just a spiral, as mentioned, but the word "spiral" doesn't appear at all. I think this paper is mostly without merit, unfortunately. Egregiously, the table comparing the (reasonably defined, I think) clustering metric of the spiral with the Hilbert curve is only for rectangular queries which ask for almost the entire space, with the query side length differing from the overall space's side length by a constant. An obvious advantage of the fractal nature of the Hilbert curve is that its clustering properties will be scale invariant, but the spiral will quickly degrade to a "space filling curve" that just goes row by row for small queries. Perhaps later the paper gives some reason to hope for the onion curve, but I'm disinclined to look.

geophile 7y ago
I was sure I was misunderstanding the paper, but my quick read matches yours. They seem to be analyzing just this one query. Another error is that just counting the number of times the curve passes in and out of the query is too simplistic. With z-order, and presumably with Hilbert curves, you can grow the query very slightly to greatly reduce this number. Then you just have to filter out the false positives. I've implemented all this using z-order, in a variety of systems, including a relational database query engine, it works really well.
colanderman 7y ago
Agreed. It's not even clear to me how this spiral qualifies as "space-filling". Where's the bijection between ℝ×ℝ and ℝ? Obviously if the curve were space-filling, the mapping is a function of the distance from the center, but this isn't bijective. I'm exiting my area of expertise here, but Wikipedia claims that "no differentiable space-filling curve can exist." [1] A trivial modification of this curve – rounding the corners – would be differentiable without changing anything about it (it doesn't need the corners to cover all the space), so something doesn't smell right. [1] https://en.wikipedia.org/wiki/Space-filling_curve#Properties https://en.wikipedia.org/wiki/Space-filling_curve#Properties
- alkonaut 7y ago
  I'm even further from my armchair comfort zone but I'll try: You can round the corners of the Hilbert curve too? I think what's implied by the non-differentiabilty statement is that it must apply generally for infinitesimal cells. So you can round the turns but that needs space, and for general differentiability of the SFC you need to be able to do a rounded turn in (almost) no space at all. The mapping does appear to be bijective - but I agree they should have presented the inverse in more detail! They state an SFC is a bijective function, but don't make the case for why O(i,j) is bijective? Again, I may be reading this wrong, I get a mild impostor syndrome attack every time I read a scientific article.
  - afiori 7y ago
    > I'm even further from my armchair comfort zone but I'll try: You can round the corners of the Hilbert curve too? This is supposed to be close to my area of expertise, I will try to give a precise answer. The usual finite Hilbert curve is not space filling. the property of the Hilbert curve is that successive iterations converge to a continuous space filling curve. There are well known techniques to transform continuous function in differentiable functions (https://en.wikipedia.org/wiki/Convolution#Differentiation https://en.wikipedia.org/wiki/Convolution#Differentiation) furthermore you can "smooth" the finite Hilbert curves so that the limit remains the same. But the true Hilbert curve (that is the limit of the finite approximations) will not be differentiable even if built as a limit of differentiable functions.

vlmutolo 7y ago

I immediately thought of xkcd's post on Rolle's Theorem. https://xkcd.com/2042/ https://xkcd.com/2042/

geophile 7y ago
I think you are confusing common sense and nonsense.

miga 7y ago

The metric seems misleading, as it is one-sided. It only checks how many clusters we look through, but not how much of the unnecessary data one needs to examine. Most indices optimize the amount of data that does not need to be browsed when querying, this index seems to maximize the amount of data that needs to be looked in a linear part of the processing.

goodmachine 7y ago

Slightly off-topic, but if you're interested in SFC's in general (in any number of dimensions) then Herman Haverkort's work should definitely be of interest, includes a new scheme for curve classification. Sixteen space-filling curves and traversals for d-dimensional cubes and simplices (2018) https://arxiv.org/abs/1711.04473 https://arxiv.org/abs/1711.04473 BTW, Haverkort has fascinating application: he uses SFC traversals to generate music. To my ear, they sound surprisingly good. http://herman.haverkort.net/doku.php?id=sound_of_space-filling_curves http://herman.haverkort.net/doku.php?id=sound_of_space-filli...

graphpapa 7y ago

I assumed this was a joke paper

bhl 7y ago

On a related note, does anyone know of a good reference of applying space filling curves as a method of dimensionality reduction? It seems like an intuitive idea since Hilbert curves [1] map points from a higher to a lower dim space but tries to preserve distance as well. [1] 3Blue1Brown video on Hilbert curves: https://www.youtube.com/watch?v=3s7h2MHQtxc https://www.youtube.com/watch?v=3s7h2MHQtxc

muxator 7y ago

> [...] an SFC is critical to the efficiency of multi-dimensional indexes [...] Apart from spatial databases, could anyone give some examples about advanced applications of Space Filling Curves for indexing?

enriquto 7y ago

I would not call that a space-filling curve. The hilbert curves that are drawn are iterations towards a limit. These spirals do not converge to a limiting curve that fills the space.

mcnamaratw 7y ago

It looks homebrewed. But I'm going to buck the trend and say I think there is net value here for engineers. (I have no idea whether the paper is original research or not.) Weaknesses: (W1) They should say "spiral." (W2) "Optimal" seems a little enthusiastic. They should talk mostly about queries that aren't chosen to be optimal for the spiral. Value: (V1) The central idea of the paper becomes clear in a few minutes. That's a very small investment for the reader. (V2) They show that copying the "magic" Hilbert curve can be worse than just thinking and picking something for yourself. That seems to be true even for box-shaped queries that don't enclose the center of the spiral. But I think the value here is not "use a spiral." It's "consider a bunch of different scan shapes."