4 ms·

I feel like using a straight bloom filter will get you some false positives and may not be a right fit, but it is an interesting take & might be good for a firs

by cetra3 6y ago

I feel like using a straight bloom filter will get you some false positives and may not be a right fit, but it is an interesting take & might be good for a first-pass. mdbook (https://github.com/rust-lang/mdBook https://github.com/rust-lang/mdBook) uses elasticlunr (http://elasticlunr.com/ http://elasticlunr.com/) as an inverted index and is generated statically. The same is done for zola (https://www.getzola.org/documentation/content/search/ https://www.getzola.org/documentation/content/search/).

memexy 6y ago
Thanks for the links and descriptions.
johanvts 6y ago
I think a few false positives should be fine for the use case. Those files can then just be downloaded and searched in full, still cuts out almost all the traffic as wanted.
inertiatic 6y ago
Lunr and elasticlunr are awesome projects. I was part of a search team and we were banging our heads against the wall trying to figure a way to serve a new feature request (basically some advanced autocomplete functionality) in a way that fit in with what we were currently maintaining. It took me literally half an hour to implement this using elasticlunr on the browser. We will went with the backend solution as it felt more extendable, but this got me thinking there's some abuse of ES for things you could easily do that way.
- acidbaseextract 6y ago
  What's your feeling on the status of elasticlunr as a project? I've been eying the the functionality for a project, but it hasn't received updates in quite a few years.
  - lukevp 6y ago
    I have yet to see development of a js search engine continue for the long term. Used FlexSearch in a recent project but it too appears to have been abandoned. Mini search seems nice and it’s a bit newer. It has a focus on low memory usage so it may also work well for this scenario of a static index.
  - inertiatic 6y ago
    Sorry, I don't have an opinion, I haven't kept up with them, and you put more research into this that I have.
luu 6y ago
It's possible to use a bloom filter variant of this for text search (for example, Bing does this, see https://danluu.com/bitfunnel-sigir.pdf https://danluu.com/bitfunnel-sigir.pdf for details). If you wanted a very small bundle to use with a static site, I don't think it's obvious that a bloom filter variant is a bad approach. I mean, yeah, this thing that the author said "made for a fun hour of Saturday night hacking" is probably not the optimal solution, but that would've been true whether or not the author chose to build something based on bloom filters or an inverted index.
StavrosK 6y ago
That's very interesting, thank you. I'm hearing about Zola a lot and it all sounds good, do you have experience with it? The only thing that worries me about it is that e.g. with Lektor, I can just write a small Python template filter if I need something, whereas Zola isn't extensible at all (as far as I know). Has that been a problem in practice?
- cetra3 6y ago
  Yes, my personal blog is written with zola: https://cetra3.github.io/ https://cetra3.github.io/. Source code to the blog is on github: https://github.com/cetra3/cetra3.github.io https://github.com/cetra3/cetra3.github.io I haven't had a need to customise zola itself, as the template language it uses (tera) is quite usable with macros etc...
  - StavrosK 6y ago
    That's a great example, thank you! I love how fast Zola is, Lektor takes forever.
dspillett 6y ago
> I feel like using a straight bloom filter will get you some false positives That is exactly the property of bloom filter searches (unless I'm misunderstanding) - you should never get a false negative but can expect false positives. The design of the filter will define how many false positives are likely for a given lookup in a given dataset. > might be good for a first-pass. Exactly. If the number of false positives is low then you can perform an exhaustive search on the few results to exclude the wrong ones. You won't miss anything as there are no false negatives. Of course defining the bloom filter such that the number of false positives is low enough to "win" by a significant margin might not be easy, particularly for growing rather than static data, just like choosing an optimal hash function often isn't.

by cetra3 6y ago

memexy 6y ago

Thanks for the links and descriptions.

johanvts 6y ago

I think a few false positives should be fine for the use case. Those files can then just be downloaded and searched in full, still cuts out almost all the traffic as wanted.

inertiatic 6y ago

Lunr and elasticlunr are awesome projects. I was part of a search team and we were banging our heads against the wall trying to figure a way to serve a new feature request (basically some advanced autocomplete functionality) in a way that fit in with what we were currently maintaining. It took me literally half an hour to implement this using elasticlunr on the browser. We will went with the backend solution as it felt more extendable, but this got me thinking there's some abuse of ES for things you could easily do that way.

acidbaseextract 6y ago
What's your feeling on the status of elasticlunr as a project? I've been eying the the functionality for a project, but it hasn't received updates in quite a few years.
- lukevp 6y ago
  I have yet to see development of a js search engine continue for the long term. Used FlexSearch in a recent project but it too appears to have been abandoned. Mini search seems nice and it’s a bit newer. It has a focus on low memory usage so it may also work well for this scenario of a static index.
- inertiatic 6y ago
  Sorry, I don't have an opinion, I haven't kept up with them, and you put more research into this that I have.

luu 6y ago

It's possible to use a bloom filter variant of this for text search (for example, Bing does this, see https://danluu.com/bitfunnel-sigir.pdf https://danluu.com/bitfunnel-sigir.pdf for details). If you wanted a very small bundle to use with a static site, I don't think it's obvious that a bloom filter variant is a bad approach. I mean, yeah, this thing that the author said "made for a fun hour of Saturday night hacking" is probably not the optimal solution, but that would've been true whether or not the author chose to build something based on bloom filters or an inverted index.

StavrosK 6y ago

That's very interesting, thank you. I'm hearing about Zola a lot and it all sounds good, do you have experience with it? The only thing that worries me about it is that e.g. with Lektor, I can just write a small Python template filter if I need something, whereas Zola isn't extensible at all (as far as I know). Has that been a problem in practice?

cetra3 6y ago
Yes, my personal blog is written with zola: https://cetra3.github.io/ https://cetra3.github.io/. Source code to the blog is on github: https://github.com/cetra3/cetra3.github.io https://github.com/cetra3/cetra3.github.io I haven't had a need to customise zola itself, as the template language it uses (tera) is quite usable with macros etc...
- StavrosK 6y ago
  That's a great example, thank you! I love how fast Zola is, Lektor takes forever.

dspillett 6y ago

> I feel like using a straight bloom filter will get you some false positives That is exactly the property of bloom filter searches (unless I'm misunderstanding) - you should never get a false negative but can expect false positives. The design of the filter will define how many false positives are likely for a given lookup in a given dataset. > might be good for a first-pass. Exactly. If the number of false positives is low then you can perform an exhaustive search on the few results to exclude the wrong ones. You won't miss anything as there are no false negatives. Of course defining the bloom filter such that the number of false positives is low enough to "win" by a significant margin might not be easy, particularly for growing rather than static data, just like choosing an optimal hash function often isn't.