Hacker News Reader

Interestingly, this algo has absolutely nothing whatsoever to do with "Wavelets" or even waves. The name "wavelet" stuck to it mostly only because it uses a recursive decomposition approach which happens to be something that Wavelet does in actual wave processing. It got collectively labeled "Wavelet" when what was really meant was just "Recursive".

View on HN

The name derives from an analogy with the wavelet transform for signals, which recursively decomposes a signal into low-frequency and high-frequency components (Wikipedia).

"Wavelet tree" is not just a collective label but the name explicitly given by the authors of the paper where the data structure was first described in. At least Vitter had worked in image/video compression, where wavelet transforms and similar techniques are common. I believe the original idea was adapting those techniques for representing strings, and the wavelet tree data structure was the final outcome.

You're seriously nit picking what "collective label" means? It means that name was accepted by the community.

Doesn't really seem like a nitpick to me. Your description of the situation feels a bit misleading.

Sounds like you haven't quite found a mistake yet. Keep thinking. Maybe you'll think of something.

Reply on news.ycombinator.com