News for hackers. Stuff that matters.

A comment on Why and how to search two years back in your Elastic search logs [pdf].

Re:Why and how to search two years back in your Elastic sear... by hinkley on Tuesday February 25, 2020 @01:39PM (#22415850)
I was trying to refresh my memory of the BWT algorithm for compression the other day and stumbled on a guy doing a tutorial on how they use it for gene analysis/searches. One of his assertions was that suffix trees and BWT aren't that far apart, and it has me wondering.

Compressing text and searching text are both about identifying patterns. How much R&D have we done on trying to do both at the same time? Is searching for text in a compressed file in log(n) to sqrt(n) time a solved problem?

[ Parent | on HN ]
Re:Why and how to search two years back in your Elastic sear... by rolling_roland on Tuesday February 25, 2020 @01:47PM (#22415940)
There's literature on this topic, it is called succinct data structures. Wikipedia got you covered as usual: https://en.wikipedia.org/wiki/Succinct_data_structure
[ Parent | on HN ]