[HN Gopher] Wavelet Trees: An Introduction (2011)
       ___________________________________________________________________
        
       Wavelet Trees: An Introduction (2011)
        
       Author : Tomte
       Score  : 45 points
       Date   : 2025-05-15 15:27 UTC (7 hours ago)
        
 (HTM) web link (www.alexbowe.com)
 (TXT) w3m dump (www.alexbowe.com)
        
       | JohnKemeny wrote:
       | Discussed here 12 years ago.
       | https://news.ycombinator.com/item?id=5526991 (7 comments)
        
       | jdonaldson wrote:
       | I think what's changed since this was posted in 2011 is the
       | emergence of embeddings and the need to take advantage of its
       | higher dimensional space. While embeddings expose more underlying
       | structure that can be used for tensor math, ranking systems often
       | are still good ol' trees. This project to me points at a new
       | major "hinge" of information architecture.
        
         | bawolff wrote:
         | What does this have to do with wavelet trees?
         | 
         | (Sorry for being a dick if im wrong) - was this an AI generated
         | comment that got confused by the domain specific meaning of the
         | word "rank" in this context?
        
           | jdonaldson wrote:
           | That is a pretty badly overloaded word for it, and I didn't
           | even pay much attention to the notion of "rank" anyways. I'm
           | mainly interested in how the text is represented with bit
           | vectors. It's very reminiscent of how vector math plays out
           | in other ML domains, but I would bet that many people working
           | with text have never heard of it.
        
             | 29ebJCyy wrote:
             | Can you explain how this is useful for those problems
             | though? I'm struggling to come up with a way to use rank
             | queries on embeddings in order to get back useful
             | information.
        
             | bawolff wrote:
             | > It's very reminiscent of how vector math plays out in
             | other ML domains
             | 
             | How so?
        
           | quantadev wrote:
           | You weren't wrong. Wavelet Trees have no relationship
           | whatsoever to vector embeddings.
        
       | quantadev wrote:
       | 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".
        
         | jltsiren wrote:
         | "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.
        
           | quantadev wrote:
           | You're seriously nit picking what "collective label" means?
           | It means that name was accepted by the community.
        
             | bawolff wrote:
             | Doesn't really seem like a nitpick to me. Your description
             | of the situation feels a bit misleading.
        
               | quantadev wrote:
               | Sounds like you haven't quite found a mistake yet. Keep
               | thinking. Maybe you'll think of something.
        
       | montag wrote:
       | I think the site just went down.
        
       ___________________________________________________________________
       (page generated 2025-05-15 23:00 UTC)