6 ms·

Lucene's FuzzyQuery is 100 times faster in 4.0

92 points by amnigos 15y ago

mhp 15y ago
I'm torn between being happy that Lucene is getting a giant speed boost and my concern that the code is doing something magical which the programmers don't understand. If there's a bug and it has to do with the algorithm, how will they fix it?
- afsina 15y ago
  the way they did is exactly what you feared. They got a complex python code and converted it to Java using a converter tool AFAIK.
  - bluelu 15y ago
    "Realize, now, what a crazy position we were in."
  - andrewcooke 15y ago
    i'm amazed by the text in that post. in general i appreciate people admitting when they don't understand something, but the tone there goes beyond relaxed to, well, a celebration of ignorance (greek letters! oh noes!). is it a joke?
    - vmind 15y ago
      It's also confusing to note they don't mention whether they even contacted the authors of the paper to see if an implementation (even partial) had been made, or clarification could be provided on implementation details.
- rogerbraun 15y ago
  It seems they did some comprehensive testing to make sure there are no bugs. What else should they do?
  - lscharen 15y ago
    Understand their code.
    - rogerbraun 15y ago
      They understood it enough to: - implement it, although it is extremely complicated - test it - fix a bug in the algorithm - use it to make part of their software 100x faster
      - lscharen 15y ago
        I think I came away with almost the opposite impression from reading the article. From my perspective, they did not implement it. Mark Miller and Robert Muir were able to implement the algorithm for the N=1 case, but were stuck until they found the existing Moman code. They did not implement their own code using Moman as a reference implementation, but just used Moman's code to generate the required tables. From the article, "Not really understanding the Python code, and also neither the paper, we desperately tried to write our own Python code to tap into the various functions embedded in Moman's code". This sounds to me like they did not have a good understanding of the algorithms they were trying to implement. They did do a fair bit of testing and did uncover a bug in the Moman code base, but, again, they did not fix this bug themselves, but appealed to Jean-Phillipe who then quickly fixed his code -- in effect, they were relying on a third-party. And, yes, they did apply the end result to make fuzzy searching a lot faster, which is a good and practical end. It took a lot of effort on the Lucene's team part to get this feature implemented, but that does not mean that anyone has a good understanding of the end result. In short, I don't get the impression that anyone on the Lucene team could give a 1 hour talk on implementing the Klaus Schulz and Stoyan Mihov paper to a formal language and automata audience.
pragmatic 15y ago
Do users actually need to enter this syntax: The QueryParser syntax is term~ or term~N? After considering Lucene, I built my in house search engine. I wanted it to work a lot more like google than a "Full-text" library like search engine. Very few users will go beyond the basics. How many users will actually used Google advanced search? Even programmers? Very few. Users don't use advanced search features. Why? It's not their fault. They tried. They tried at the library - didn't work. They tried on the early search engines - didn't work. They tried on your Intranet app powered by database full text search - it doesn't work. We trained them. We showed them that (most) advanced searching isn't worth their time. Why is? Revisioning + speed. Make it easy to try different combos of search terms really fast. Correct spelling, suggest searches, add the ability to filter information. See: Information Architecture for the World Wide Web p. 185. Also available on Safari Books. See Also: Google
- vmind 15y ago
  A general idea is to 'compile' user queries to a lucene query with the various default options that give the best search, and not to use raw lucene queries from the user. The knobs need to be there for turning, whether you expose those knobs to the end user is a design decision.
- revorad 15y ago
  Can you tell us more about your search engine? I'm building an online store and search is going to be crucial for us. Currently, I'm evaluating Lucene (solr).
- smanek 15y ago
  To get pretty good 'out of the box' search you should probably use solr (and see something http://wiki.apache.org/solr/SpellCheckComponent http://wiki.apache.org/solr/SpellCheckComponent). If you're using Lucene, it's not too difficult to write your own query parser that does exactly what you want, including fuzzy searches, spelling correction, term weighting, etc. My current employer has a rather involved one that can take advantage of lots of application specific data. Writing a custom query parser allows you to do as much hidden magic on the query as you want, and expose your own special operators if you really want to. Check out some of our user accessible operators at http://help.greplin.com/customer/portal/articles/15527-how-can-i-do-advanced-searches- http://help.greplin.com/customer/portal/articles/15527-how-c... Incidentally, I'd love to exchange notes and hear about your your search engine sometime. If you're interested, shoot me an email (address in profile).
mgkimsal 15y ago
This is not to pick on Lucene in particular - not 100% sure it even applies - but I'm always a bit mixed when massive speed improvements take place in projects. It tends to validate earlier criticisms about the speed of a particular project which were dismissed (and often countered) by community members. "Java is slow." "No, it's not - it's hella fast!" "But it takes 4 minutes to launch every Java app I ever use." "Dude, you're doing it wrong - everything I write and use in Java is so fast I have to sometimes wonder if Java didn't magically upgrade my CPU!" etc. Then a new JVM will come out with measurably faster performance, which validates the earlier view that something was indeed slow, but it's ignored/overlooked/glossedover by proponents. The other response often is "the code's open, fix it yourself", which generally does no one any good. Just because I'm qualified to determine that something is slow doesn't mean I have the foggiest clue how to fix it. Nor am I encouraged that you'll actually take my patches back (even if I could write them) because you (project team) don't seem to think there's a speed problem in the first place. This isn't to rag on Lucene's team - I've no idea if this applies to them in particular - it's just something that popped in to my head when I read the title. The article itself is interesting, describing how the speedup was implemented starting with Python - I won't spoil the rest of the story :)
- jbooth 15y ago
  Lucene has basically always been really fast for just-plain-indexing-and-search. Certain additional features are pretty expensive to do the obvious way and came in as "it works" first and "it's fast" later. Reading the blog entry, this seems to be the case for fuzzy searches. One thing to take note of is that you can't just change your index structure for one feature, that might make other features slower and not worth it.
  - mgkimsal 15y ago
    One thing I'd forgot to mention, and is probably applicable in this case, is that 'non-standard' approaches may in fact not be computationally feasibly when a project first starts out. Precomputing loads of tables of data makes sense when you're on 3ghz processors, but probably not if you're on 200mhz CPUs, for example.
- 15y ago
rivalis 15y ago
On the one hand, this does not inspire confidence. It is disturbing to have magic in one's software. On the other hand, the speed gains are really impressive: I'm sure there are times when it is reasonable to make a magic vs. utility tradeoff. Also, it's OSS: I'm sure someone will eventually want to make a well-understood and documented version, and the devs seem like people who would be willing to accept that.
- conover 15y ago
  I completely agree. There is, of course, always a balance to be struck but it's pretty difficult to ignore 100x speed up in something non-trivial. Also, I read part of the paper linked in the post. It doesn't seem completely inaccessible, just dense. I'm sure someone will eventually come up with a non-hacky version.
deleted 15y ago
[deleted]
aksbhat 15y ago
Interesting article! A lot of commenter here are scared of using Magik code. However note that Search/Information Retrieval is a hard problem. Unlike other problems, developing a generalized full text search engine is difficult. Testing search algorithms is even more difficult e.g. NIST organizes TREC conference http://trec.nist.gov/pubs/call2011.html http://trec.nist.gov/pubs/call2011.html in which a major emphasis is on evaluation of search algorithms. In fact Search is as what my advisor calls it, an AI-Complete problem, i.e. creating a perfect search engine would amount to creating a Human like artificial intelligence capable of understanding your query and the corpus.
quinndupont 15y ago
That's a pretty obscene performance gain. Either that new algorithm was magic, or the one before was pretty crappy. When else do you see this kind of performance gain in production code?
- lzm 15y ago
  As the article says, the previous one was a brute force implementation. And the 100x number is kind of nonsensical since the real speedup depends on the size of the input (the asymptotic complexity of the algorithm went from O(nmk) to something like O(n+mk) I believe).
ollysb 15y ago
A few years back I worked on a project that had switched to autonomy from lucene. They'd had problems getting good enough results from automony so decided to plough some money into the problem and go for what was considered the best solution at the time. My impression now is that lucene has come a very long way, does anyone know how they compare today?
siculars 15y ago
I have some interest in various edit distance implementations. The problem with the basic edit distance is that you need to match each string against all stored strings. This becomes an unbearable computational cost as the size of your corpus increases. It seems that what they have done here is create a rainbow table of sorts that houses all the possible edits at distance 1 and 2. 3 is possible but requires more space to store and more time to scan. This is a very interesting problem and has application in many, many areas. I always felt like there was more work to be done here and it looks like there may still be yet. For example, an area that edit distance was initially applied to was in person deduplication. When merging lists of names it is important to identify duplicates and merge then appropriately. This is a problem for me in medical informatics and is more devious than it sounds on first blush.
- nkurz 15y ago
  A "rainbow table" works in a somewhat similar manner, but is based on doing a full calculation then saving only certain starting points. I think what they are doing is actually more like creating a regular expression that matches all words a particular Levenshtein distance from the target. Here's more about what how they are doing it: http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levensht... This article has a very good overview of the options: http://stevehanov.ca/blog/index.php?id=114 http://stevehanov.ca/blog/index.php?id=114
kilburn 15y ago
My short summary of what the article is about... Lucene's previous approach to fuzzy matching was to check the distance between the input word and every word in the dictionary. Let's assume that their implementation to compute the distance between two words was linear-time on the size of the largest word being compared. Then, the complexity of this method is O(nm), where n is the average length of all words and m is the number of words on the dictionary. The new algorithm uses some precomputed tables that define a parametrized deterministic finite state machine. Then, when the user inputs a word, the word is used to fix the parameters (this is, setting the rules on how to traverse the states defined in the precomputed tables). From the given information, it is unclear to me what the complexity of this parameter fixing step is, but the paper states that its linear, so we'll say O(m). Then, discovering all the words in the dictionary that are within a fixed distance "d" has a complexity of O(k+m), where k is the length of the longest word in the dictionary. Complexity wise, it is very clear that you can gain an X-fold increase in performance by moving from one algorithm to the other, by simply growing the dictionary until you get to your desired X. Finally, I really dislike the author stating that "Unfortunately, the paper was nearly unintelligible!". I've taken a quick look at it, and it is immediately clear that the authors put a great deal of effort into it. Further, it looks quite packed, but perfectly organized and written in a clear-enough language...
- xyzzyz 15y ago
  Finally, I really dislike the author stating that "Unfortunately, the paper was nearly unintelligible!". I've taken a quick look at it, and it is immediately clear that the authors put a great deal of effort into it. Further, it looks quite packed, but perfectly organized and written in a clear-enough language... It does not matter how much effort is put or how clearly is a paper written, to a someone without proper background it will always sound unintelligible. Put yourself in a position of a person who never studied formal languages theory and try to read it. It is utterly impossible. I do not say that it is a bad thing (had researchers needed to put everything in layman's terms, they would not have much time for actual research left), it is just understandable.
  - kilburn 15y ago
ballard 15y ago
http://www.slideshare.net/rboulton/comparing-open-source-search-engines http://www.slideshare.net/rboulton/comparing-open-source-sea... http://www.osnews.com/story/21782/Open_Source_Search_Engine_Benchmarks http://www.osnews.com/story/21782/Open_Source_Search_Engine_... Also there's holumbus http://holumbus.fh-wedel.de/ http://holumbus.fh-wedel.de/, an active OSS search engine written in haskell.
markrmiller 15y ago
Heh - Mike was exaggerating when he said unintelligible. While we are not masters of that paper, we worked through it and understood the algorithm. We could take a simple example and apply the steps - this is a very different understanding than someone who studies and focuses on this field, yes. Given time, we could have done the implementation without the python code - Mike's recollection of the early part of this story is heavily 2nd hand. However, even understanding the algorithm (if not masters of all the concepts behind it), there was still a large gap to implementation. The solution that was used allowed us to focus on pieces of that problem and accelerate development fantastically. Lucene has some of the best tests in open source software IMO. We are confident in this code - whether it takes 2 or 3 people to properly maintain or not. The option before was a completely non scalable joke fuzzy query or nothing. Now you have this option. Great. A little magic? Sure. Great :)

92 points by amnigos 15y ago

mhp 15y ago

I'm torn between being happy that Lucene is getting a giant speed boost and my concern that the code is doing something magical which the programmers don't understand. If there's a bug and it has to do with the algorithm, how will they fix it?

afsina 15y ago
the way they did is exactly what you feared. They got a complex python code and converted it to Java using a converter tool AFAIK.
- bluelu 15y ago
  "Realize, now, what a crazy position we were in."
- andrewcooke 15y ago
  i'm amazed by the text in that post. in general i appreciate people admitting when they don't understand something, but the tone there goes beyond relaxed to, well, a celebration of ignorance (greek letters! oh noes!). is it a joke?
  - vmind 15y ago
    It's also confusing to note they don't mention whether they even contacted the authors of the paper to see if an implementation (even partial) had been made, or clarification could be provided on implementation details.
rogerbraun 15y ago
It seems they did some comprehensive testing to make sure there are no bugs. What else should they do?
- lscharen 15y ago
  Understand their code.
  - rogerbraun 15y ago
    They understood it enough to: - implement it, although it is extremely complicated - test it - fix a bug in the algorithm - use it to make part of their software 100x faster
    - lscharen 15y ago
      I think I came away with almost the opposite impression from reading the article. From my perspective, they did not implement it. Mark Miller and Robert Muir were able to implement the algorithm for the N=1 case, but were stuck until they found the existing Moman code. They did not implement their own code using Moman as a reference implementation, but just used Moman's code to generate the required tables. From the article, "Not really understanding the Python code, and also neither the paper, we desperately tried to write our own Python code to tap into the various functions embedded in Moman's code". This sounds to me like they did not have a good understanding of the algorithms they were trying to implement. They did do a fair bit of testing and did uncover a bug in the Moman code base, but, again, they did not fix this bug themselves, but appealed to Jean-Phillipe who then quickly fixed his code -- in effect, they were relying on a third-party. And, yes, they did apply the end result to make fuzzy searching a lot faster, which is a good and practical end. It took a lot of effort on the Lucene's team part to get this feature implemented, but that does not mean that anyone has a good understanding of the end result. In short, I don't get the impression that anyone on the Lucene team could give a 1 hour talk on implementing the Klaus Schulz and Stoyan Mihov paper to a formal language and automata audience.

pragmatic 15y ago

Do users actually need to enter this syntax: The QueryParser syntax is term~ or term~N? After considering Lucene, I built my in house search engine. I wanted it to work a lot more like google than a "Full-text" library like search engine. Very few users will go beyond the basics. How many users will actually used Google advanced search? Even programmers? Very few. Users don't use advanced search features. Why? It's not their fault. They tried. They tried at the library - didn't work. They tried on the early search engines - didn't work. They tried on your Intranet app powered by database full text search - it doesn't work. We trained them. We showed them that (most) advanced searching isn't worth their time. Why is? Revisioning + speed. Make it easy to try different combos of search terms really fast. Correct spelling, suggest searches, add the ability to filter information. See: Information Architecture for the World Wide Web p. 185. Also available on Safari Books. See Also: Google

vmind 15y ago
A general idea is to 'compile' user queries to a lucene query with the various default options that give the best search, and not to use raw lucene queries from the user. The knobs need to be there for turning, whether you expose those knobs to the end user is a design decision.
revorad 15y ago
Can you tell us more about your search engine? I'm building an online store and search is going to be crucial for us. Currently, I'm evaluating Lucene (solr).
smanek 15y ago
To get pretty good 'out of the box' search you should probably use solr (and see something http://wiki.apache.org/solr/SpellCheckComponent http://wiki.apache.org/solr/SpellCheckComponent). If you're using Lucene, it's not too difficult to write your own query parser that does exactly what you want, including fuzzy searches, spelling correction, term weighting, etc. My current employer has a rather involved one that can take advantage of lots of application specific data. Writing a custom query parser allows you to do as much hidden magic on the query as you want, and expose your own special operators if you really want to. Check out some of our user accessible operators at http://help.greplin.com/customer/portal/articles/15527-how-can-i-do-advanced-searches- http://help.greplin.com/customer/portal/articles/15527-how-c... Incidentally, I'd love to exchange notes and hear about your your search engine sometime. If you're interested, shoot me an email (address in profile).

mgkimsal 15y ago

This is not to pick on Lucene in particular - not 100% sure it even applies - but I'm always a bit mixed when massive speed improvements take place in projects. It tends to validate earlier criticisms about the speed of a particular project which were dismissed (and often countered) by community members. "Java is slow." "No, it's not - it's hella fast!" "But it takes 4 minutes to launch every Java app I ever use." "Dude, you're doing it wrong - everything I write and use in Java is so fast I have to sometimes wonder if Java didn't magically upgrade my CPU!" etc. Then a new JVM will come out with measurably faster performance, which validates the earlier view that something was indeed slow, but it's ignored/overlooked/glossedover by proponents. The other response often is "the code's open, fix it yourself", which generally does no one any good. Just because I'm qualified to determine that something is slow doesn't mean I have the foggiest clue how to fix it. Nor am I encouraged that you'll actually take my patches back (even if I could write them) because you (project team) don't seem to think there's a speed problem in the first place. This isn't to rag on Lucene's team - I've no idea if this applies to them in particular - it's just something that popped in to my head when I read the title. The article itself is interesting, describing how the speedup was implemented starting with Python - I won't spoil the rest of the story :)

jbooth 15y ago
Lucene has basically always been really fast for just-plain-indexing-and-search. Certain additional features are pretty expensive to do the obvious way and came in as "it works" first and "it's fast" later. Reading the blog entry, this seems to be the case for fuzzy searches. One thing to take note of is that you can't just change your index structure for one feature, that might make other features slower and not worth it.
- mgkimsal 15y ago
  One thing I'd forgot to mention, and is probably applicable in this case, is that 'non-standard' approaches may in fact not be computationally feasibly when a project first starts out. Precomputing loads of tables of data makes sense when you're on 3ghz processors, but probably not if you're on 200mhz CPUs, for example.
15y ago

rivalis 15y ago

On the one hand, this does not inspire confidence. It is disturbing to have magic in one's software. On the other hand, the speed gains are really impressive: I'm sure there are times when it is reasonable to make a magic vs. utility tradeoff. Also, it's OSS: I'm sure someone will eventually want to make a well-understood and documented version, and the devs seem like people who would be willing to accept that.

conover 15y ago
I completely agree. There is, of course, always a balance to be struck but it's pretty difficult to ignore 100x speed up in something non-trivial. Also, I read part of the paper linked in the post. It doesn't seem completely inaccessible, just dense. I'm sure someone will eventually come up with a non-hacky version.

deleted 15y ago

[deleted]

aksbhat 15y ago

Interesting article! A lot of commenter here are scared of using Magik code. However note that Search/Information Retrieval is a hard problem. Unlike other problems, developing a generalized full text search engine is difficult. Testing search algorithms is even more difficult e.g. NIST organizes TREC conference http://trec.nist.gov/pubs/call2011.html http://trec.nist.gov/pubs/call2011.html in which a major emphasis is on evaluation of search algorithms. In fact Search is as what my advisor calls it, an AI-Complete problem, i.e. creating a perfect search engine would amount to creating a Human like artificial intelligence capable of understanding your query and the corpus.

quinndupont 15y ago

That's a pretty obscene performance gain. Either that new algorithm was magic, or the one before was pretty crappy. When else do you see this kind of performance gain in production code?

lzm 15y ago
As the article says, the previous one was a brute force implementation. And the 100x number is kind of nonsensical since the real speedup depends on the size of the input (the asymptotic complexity of the algorithm went from O(nmk) to something like O(n+mk) I believe).

ollysb 15y ago

A few years back I worked on a project that had switched to autonomy from lucene. They'd had problems getting good enough results from automony so decided to plough some money into the problem and go for what was considered the best solution at the time. My impression now is that lucene has come a very long way, does anyone know how they compare today?

siculars 15y ago

I have some interest in various edit distance implementations. The problem with the basic edit distance is that you need to match each string against all stored strings. This becomes an unbearable computational cost as the size of your corpus increases. It seems that what they have done here is create a rainbow table of sorts that houses all the possible edits at distance 1 and 2. 3 is possible but requires more space to store and more time to scan. This is a very interesting problem and has application in many, many areas. I always felt like there was more work to be done here and it looks like there may still be yet. For example, an area that edit distance was initially applied to was in person deduplication. When merging lists of names it is important to identify duplicates and merge then appropriately. This is a problem for me in medical informatics and is more devious than it sounds on first blush.

nkurz 15y ago
A "rainbow table" works in a somewhat similar manner, but is based on doing a full calculation then saving only certain starting points. I think what they are doing is actually more like creating a regular expression that matches all words a particular Levenshtein distance from the target. Here's more about what how they are doing it: http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levensht... This article has a very good overview of the options: http://stevehanov.ca/blog/index.php?id=114 http://stevehanov.ca/blog/index.php?id=114

kilburn 15y ago

My short summary of what the article is about... Lucene's previous approach to fuzzy matching was to check the distance between the input word and every word in the dictionary. Let's assume that their implementation to compute the distance between two words was linear-time on the size of the largest word being compared. Then, the complexity of this method is O(nm), where n is the average length of all words and m is the number of words on the dictionary. The new algorithm uses some precomputed tables that define a parametrized deterministic finite state machine. Then, when the user inputs a word, the word is used to fix the parameters (this is, setting the rules on how to traverse the states defined in the precomputed tables). From the given information, it is unclear to me what the complexity of this parameter fixing step is, but the paper states that its linear, so we'll say O(m). Then, discovering all the words in the dictionary that are within a fixed distance "d" has a complexity of O(k+m), where k is the length of the longest word in the dictionary. Complexity wise, it is very clear that you can gain an X-fold increase in performance by moving from one algorithm to the other, by simply growing the dictionary until you get to your desired X. Finally, I really dislike the author stating that "Unfortunately, the paper was nearly unintelligible!". I've taken a quick look at it, and it is immediately clear that the authors put a great deal of effort into it. Further, it looks quite packed, but perfectly organized and written in a clear-enough language...

xyzzyz 15y ago
Finally, I really dislike the author stating that "Unfortunately, the paper was nearly unintelligible!". I've taken a quick look at it, and it is immediately clear that the authors put a great deal of effort into it. Further, it looks quite packed, but perfectly organized and written in a clear-enough language... It does not matter how much effort is put or how clearly is a paper written, to a someone without proper background it will always sound unintelligible. Put yourself in a position of a person who never studied formal languages theory and try to read it. It is utterly impossible. I do not say that it is a bad thing (had researchers needed to put everything in layman's terms, they would not have much time for actual research left), it is just understandable.
- kilburn 15y ago

ballard 15y ago

http://www.slideshare.net/rboulton/comparing-open-source-search-engines http://www.slideshare.net/rboulton/comparing-open-source-sea... http://www.osnews.com/story/21782/Open_Source_Search_Engine_Benchmarks http://www.osnews.com/story/21782/Open_Source_Search_Engine_... Also there's holumbus http://holumbus.fh-wedel.de/ http://holumbus.fh-wedel.de/, an active OSS search engine written in haskell.

markrmiller 15y ago

Heh - Mike was exaggerating when he said unintelligible. While we are not masters of that paper, we worked through it and understood the algorithm. We could take a simple example and apply the steps - this is a very different understanding than someone who studies and focuses on this field, yes. Given time, we could have done the implementation without the python code - Mike's recollection of the early part of this story is heavily 2nd hand. However, even understanding the algorithm (if not masters of all the concepts behind it), there was still a large gap to implementation. The solution that was used allowed us to focus on pieces of that problem and accelerate development fantastically. Lucene has some of the best tests in open source software IMO. We are confident in this code - whether it takes 2 or 3 people to properly maintain or not. The option before was a completely non scalable joke fuzzy query or nothing. Now you have this option. Great. A little magic? Sure. Great :)