News for hackers. Stuff that matters.
Re:Greplin opensources Lucene Utils and Bloom Filters by dabeeeenster on Wednesday April 13, 2011 @03:49PM (#2443851)
A query that matches phrase prefixes - for example "Epic w" will match both "Epic win" and "Epic wonder". This is particularly useful for implementing Google Instant style searches

This is really useful and painfully lacking from Lucene. Great stuff.

Re:Greplin opensources Lucene Utils and Bloom Filters by sigil on Wednesday April 13, 2011 @06:49PM (#2444585)
I was curious how they implemented prefix matching, so I went and looked at the code [1]. Unfortunately, this is just a simple linear scan that calls .startswith(). It is possible to do fast (log N) prefix matching with radix / critbit trees.

[1] https://github.com/Greplin/greplin-lucene-utils/blob/master/...

Re:Greplin opensources Lucene Utils and Bloom Filters by nostrademons on Wednesday April 13, 2011 @08:28PM (#2444873)
Radix trees are O(k), where k is the length of the query string.

Anyway, for prefix matching, you want to take careful note of the size and shape of your data, because it matters for which algorithm is fastest. If your data all fits in RAM (or better yet, all fits in L2 cache), then I've had very good results with binary search (O(log N)) to find the first matching result, and then linear scan to find all possible suffixes. This is a lot more cache-friendly than radix trees, which have better theoretical performance but often touch memory that's all over the place.

Re:Greplin opensources Lucene Utils and Bloom Filters by sigil on Wednesday April 13, 2011 @08:36PM (#2444892)
> Radix trees are O(k)

Yes, thank you.

Re:Greplin opensources Lucene Utils and Bloom Filters by techtalsky on Wednesday April 13, 2011 @07:56PM (#2444767)
Luckily it does exist in Solr in the form of prefixed term queries. I'm surprised to find out it's not in vanilla Lucene.