3 ms·

1.65ms for what kind of queries? Also, is that 1M blog posts, all weighting 500mb in total size(characters)?

ethanwillis 9y ago
I wonder if they're using succint data structures. I'm in bioinformatics and the first time I implemented a wavelet tree to reduce the size of genomes in memory.. It was just breathtaking.
- ausjke 9y ago
  very interesting, can you elaborate and on it a little more? I need quick fuzzy search on a low-end embedded device that has limited storage(both RAM and HDD), was thinking about putting the index on a server with plenty RAM then do websocket or RPC for that.
  - ethanwillis 9y ago
    There's a very good blog post for the implementation details here: http://alexbowe.com/wavelet-trees/ http://alexbowe.com/wavelet-trees/ I had a decent implementation in Python, but it's on my old macbook that I would need to dig up. If you're interested you can add me on telegram: @rightcheek. Now to go with Wavelet trees you may or may not need to know about suffix arrays and optimal suffix array construction. Take a look at this: https://en.wikipedia.org/wiki/Suffix_array https://en.wikipedia.org/wiki/Suffix_array This is what's going to give you space efficiency in combination with a wavelet tree. And the wavelet tree also gives you good rank/select efficiency. Edit: Here's a suffix array construction algorithm implementation I did (not sure if it's fully correct) https://github.com/ethanwillis/comp7295_final/blob/master/saca.py https://github.com/ethanwillis/comp7295_final/blob/master/sa... It is based on this paper: https://local.ugene.unipro.ru/tracker/secure/attachment/12144/Linear+Suffix+Array+Construction+by+Almost+Pure+Induced-Sorting.pdf https://local.ugene.unipro.ru/tracker/secure/attachment/1214...
- dogruck 9y ago
  Neat, TIL about wavelet trees. https://en.m.wikipedia.org/wiki/Wavelet_Tree https://en.m.wikipedia.org/wiki/Wavelet_Tree
- jagger27 9y ago
  That's a beautiful structure. Thanks for sharing.
fizx 9y ago
FWIW, a few years back, I was averaging <5ms for a benchmark of live traffic (many thousands of queries per second) on Pinterest queries against their full dataset on a single EC2 box with a weeks worth of customization on top of Lucene. The existing stuff isn't slow.
- markpapadakis 9y ago
  Trinity - depending on the execution mode - is over 100% faster for certain queries compared to Lucene, and Lucene is already very fast. It all comes down to the postings ling codecs, and the iterators design/impl anyway.

I wonder if they're using succint data structures. I'm in bioinformatics and the first time I implemented a wavelet tree to reduce the size of genomes in memory.. It was just breathtaking.

ausjke 9y ago
very interesting, can you elaborate and on it a little more? I need quick fuzzy search on a low-end embedded device that has limited storage(both RAM and HDD), was thinking about putting the index on a server with plenty RAM then do websocket or RPC for that.
- ethanwillis 9y ago
  There's a very good blog post for the implementation details here: http://alexbowe.com/wavelet-trees/ http://alexbowe.com/wavelet-trees/ I had a decent implementation in Python, but it's on my old macbook that I would need to dig up. If you're interested you can add me on telegram: @rightcheek. Now to go with Wavelet trees you may or may not need to know about suffix arrays and optimal suffix array construction. Take a look at this: https://en.wikipedia.org/wiki/Suffix_array https://en.wikipedia.org/wiki/Suffix_array This is what's going to give you space efficiency in combination with a wavelet tree. And the wavelet tree also gives you good rank/select efficiency. Edit: Here's a suffix array construction algorithm implementation I did (not sure if it's fully correct) https://github.com/ethanwillis/comp7295_final/blob/master/saca.py https://github.com/ethanwillis/comp7295_final/blob/master/sa... It is based on this paper: https://local.ugene.unipro.ru/tracker/secure/attachment/12144/Linear+Suffix+Array+Construction+by+Almost+Pure+Induced-Sorting.pdf https://local.ugene.unipro.ru/tracker/secure/attachment/1214...
dogruck 9y ago
Neat, TIL about wavelet trees. https://en.m.wikipedia.org/wiki/Wavelet_Tree https://en.m.wikipedia.org/wiki/Wavelet_Tree
jagger27 9y ago
That's a beautiful structure. Thanks for sharing.

fizx 9y ago

FWIW, a few years back, I was averaging <5ms for a benchmark of live traffic (many thousands of queries per second) on Pinterest queries against their full dataset on a single EC2 box with a weeks worth of customization on top of Lucene. The existing stuff isn't slow.

markpapadakis 9y ago
Trinity - depending on the execution mode - is over 100% faster for certain queries compared to Lucene, and Lucene is already very fast. It all comes down to the postings ling codecs, and the iterators design/impl anyway.