4 ms·

Can somebody who read the paper in depth comment on whether the result is practical or not? Since it's a TCS paper, it's hard to gauge whether the constant fact

by pzh 9y ago

Can somebody who read the paper in depth comment on whether the result is practical or not? Since it's a TCS paper, it's hard to gauge whether the constant factors are palatable or not, and there are many theoretical CS papers that give asymptotically optimal or significantly improved algorithms that have astronomical constant factors (e.g. matrix multiplication, etc.)

JPLeRouzic 9y ago
As long as you can express some information as lists of symbols, you need to search patterns in it and to store in a compressed form, particularely for biological molecules which are incredibly long (your DNA is nanometers large and meters long!) There are already bioinformatics tools such as BowTie that use the Burrows-Wheeler transform. https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf... I think the important thing here is that the running time is deterministic, which is important if your query usually runs for days or even weeks! (edited)
eggie 9y ago
The compressed suffix tree (CST) supports a number of search algorithms that run in the order of the query length irrespective of the size of the corpus which is being searched. That the suffix tree is compressed allows it use space that is often not much larger than the input sequence, and this effect is improved in the case of inputs with internal repetitions, which seems to be the norm in the case of naturally-arising data (i.e. almost anywhere that Zipf's law holds). As the authors point out, existing algorithms for the construction of the compressed suffix tree require space that is proportional to the alphabet size. When we work with limited alphabets, like DNA, this factor is small and we tend to not worry about it. Many real-world data sets do have larger alphabet sizes, and so there is a need to efficiently generate the CST for them. Removing the alphabet-size bound on the space required for construction is a big deal. Existing methods require huge amounts of space to construct the CST or CSA (compressed suffix array) for large alphabets, and are barely practical to use. In practice results of this kind have proceeded implementations that are usable by a year or more. Libraries like sdsl-lite have accelerated the rate at which implementations get into the hands of compressed data structure researchers in much the same way that R did for statistical models, so hopefully we can see benefits of this result sooner. Unfortunately, it will take a deeper reading of the paper by someone who is more intimately involved in this research to be able to describe exactly why this result may not be practical. A quick read does not suggest any obvious problems, the authors have a good track record and are very positive about many follow-on results (see conclusions).
- lorenzhs 9y ago
  SDSL-lite is a fantastic library, Simon (the main author) is one of my colleagues and spends a lot of time on making it easy to use: https://github.com/simongog/sdsl-lite https://github.com/simongog/sdsl-lite Without having read the paper in detail, SODA (the conference where it was presented) papers do have a reputation for being very theoretical, though, so it may not be implemented any time soon.
  - cletus 9y ago
    That does look fantastic. Great docs too. Sadly GOL :(. This can severely restrict where it can be used.
    - lorenzhs 9y ago
      I'm assuming you meant GPL? I've got good news for you then, the next version is going to be under a BSD license: https://github.com/xxsds/sdsl-lite https://github.com/xxsds/sdsl-lite (currently unstable!)

by pzh 9y ago

JPLeRouzic 9y ago

As long as you can express some information as lists of symbols, you need to search patterns in it and to store in a compressed form, particularely for biological molecules which are incredibly long (your DNA is nanometers large and meters long!) There are already bioinformatics tools such as BowTie that use the Burrows-Wheeler transform. https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform https://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transf... I think the important thing here is that the running time is deterministic, which is important if your query usually runs for days or even weeks! (edited)

eggie 9y ago

The compressed suffix tree (CST) supports a number of search algorithms that run in the order of the query length irrespective of the size of the corpus which is being searched. That the suffix tree is compressed allows it use space that is often not much larger than the input sequence, and this effect is improved in the case of inputs with internal repetitions, which seems to be the norm in the case of naturally-arising data (i.e. almost anywhere that Zipf's law holds). As the authors point out, existing algorithms for the construction of the compressed suffix tree require space that is proportional to the alphabet size. When we work with limited alphabets, like DNA, this factor is small and we tend to not worry about it. Many real-world data sets do have larger alphabet sizes, and so there is a need to efficiently generate the CST for them. Removing the alphabet-size bound on the space required for construction is a big deal. Existing methods require huge amounts of space to construct the CST or CSA (compressed suffix array) for large alphabets, and are barely practical to use. In practice results of this kind have proceeded implementations that are usable by a year or more. Libraries like sdsl-lite have accelerated the rate at which implementations get into the hands of compressed data structure researchers in much the same way that R did for statistical models, so hopefully we can see benefits of this result sooner. Unfortunately, it will take a deeper reading of the paper by someone who is more intimately involved in this research to be able to describe exactly why this result may not be practical. A quick read does not suggest any obvious problems, the authors have a good track record and are very positive about many follow-on results (see conclusions).

lorenzhs 9y ago
SDSL-lite is a fantastic library, Simon (the main author) is one of my colleagues and spends a lot of time on making it easy to use: https://github.com/simongog/sdsl-lite https://github.com/simongog/sdsl-lite Without having read the paper in detail, SODA (the conference where it was presented) papers do have a reputation for being very theoretical, though, so it may not be implemented any time soon.
- cletus 9y ago
  That does look fantastic. Great docs too. Sadly GOL :(. This can severely restrict where it can be used.
  - lorenzhs 9y ago
    I'm assuming you meant GPL? I've got good news for you then, the next version is going to be under a BSD license: https://github.com/xxsds/sdsl-lite https://github.com/xxsds/sdsl-lite (currently unstable!)