Fractals for Fun and Profit

http://gideon.smdng.nl/2014/04/fractals-for-fun-and-profit/

by yiransheng • 12 years ago

70 7 12 years ago

gideon.smdng.nl

Excellent discussion - and the application area (cross-correlation of sensor network data) is actually quite a bit more popular than one might think! Avalanche/landslide detection, earthquakes, bridge monitoring, industrial settings...

On a tangent, if those cross-correlations are big-ish a frequency domain (FFT) correlation could be more efficient, assuming that hasn't already been tried. This would probably save storage memory as well, though I am not 100% sure. If you could get the sensors to send the FFTs directly that could be even better!

This also has echoes of a previous HN discussion on space filling curves [0], which led to the purchase of this book [1]. I still haven't dug into it yet, but maybe these are useful references for others who are interested.

[0] https://news.ycombinator.com/item?id=7480857

[1] http://www.amazon.com/Space-Filling-Curves-Introduction-Appl...

stygianguest2• 12 years ago

Original author here. Thanks for the spacial data structures link, I'll look into it.

The correlations are done in the frequency domain. And, although I didn't look into it, I suspect they have pretty good algorithms to compute the correlations themselves. At least they have very smart people working on that.

exabrial• 12 years ago

http://me.veekun.com/blog/2012/04/09/php-a-fractal-of-bad-de...

Ah crap... I will not troll anymore on HN. ::slap:: I will not troll anymore on HN. ::slap:: I will not troll anymore on HN. ::slap:: I will not troll anymore on HN. ::slap::

trhway• 12 years ago

looks very similar to fractal curve approximation of traveling salesman and fractal indexing.

jc_dntn• 12 years ago

http://fractalfoundation.org/

This is a bit unrelated, but Albuquerque has a great fractal community. Friday night 3d fractals in the planetarium is an amazing thing.

eliteraspberrie• 12 years ago

The pseudo-code for cross-correlation implements the naive method, which is O(M*N), M and N being the lengths of the arrays being correlated. I think it might just have been used to illustrate, but just in case, the proper way of computing the cross-correlation is with the FFT, as that is "linearithmic" in time. It's commonly called "multiplication in the frequency domain" or just frequency domain convolution. Basically, take the FFT of both input sequences, multiply them, and take the inverse FFT of the product.

If you're curious, the basis of this algorithm is the convolution theorem: https://en.wikipedia.org/wiki/Convolution_theorem

Here is an example implementation of cross-correlation using the FFT, with NumPy:

http://www.eliteraspberries.com/blog/2013/08/application-of-...

stygianguest2• 12 years ago

Original author here. They do this already, the pseudo function 'correlate' operates in the frequency domain. It doesn't negate the fact that you still correlate the signals of different stations pairwise.

Fractals for Fun and Profit

Related Stories