3 ms·

I'm only using on a pretty small scale – around 500-600 blog posts. It takes about 10 seconds to build the index from scratch (including tokenising and stemming

by mattdw 17y ago

I'm only using on a pretty small scale – around 500-600 blog posts. It takes about 10 seconds to build the index from scratch (including tokenising and stemming everything), and queries are effectively instantaneous.

joe_the_user 17y ago
So it basically isn't using B-trees or whatever fancy data structures Lucene and company would use?
- brehaut 17y ago
  The top level index is a clojure map (a persistent hash-map by default i believe) of strings (stems) to another map of key to weighting. The hash-map is implemented as a Bagwell Trie under the hood. Check out http://blog.higher-order.net/2009/09/08/understanding-clojures-persistenthashmap-deftwice/ http://blog.higher-order.net/2009/09/08/understanding-clojur... for a lot of detail on the implementation, and http://en.wikipedia.org/wiki/Trie http://en.wikipedia.org/wiki/Trie for a general overview of how Tries differ from Trees.
- brehaut 17y ago
  For some additional information about the performance of caponia, heres some details about the pain points: The particular pathological case for this system is query where the search stems occur in the majority of documents (there is a small exclusion list that helps, but its not a panacea) because the merging of stem results is at best a linear operation (:or queries are currently much simpler than :and queries) The other difficult case for this system is updating or removing a document from the index; removal is fairly easy: generate the stems for the current state and update those stems in the index. To update (an existing document in the index) efficiently you need the set of stems in both old and new versions of the document; For the stems that are in new set you can just add them to the index as normal. For the difference of the old set and the new set (ie, those stems only in the old set - clojure's difference function is not symmetric i believe) you then need to remove the document id from those stems in the index. edit: clarified meaning of update.

by mattdw 17y ago

joe_the_user 17y ago

So it basically isn't using B-trees or whatever fancy data structures Lucene and company would use?

brehaut 17y ago
The top level index is a clojure map (a persistent hash-map by default i believe) of strings (stems) to another map of key to weighting. The hash-map is implemented as a Bagwell Trie under the hood. Check out http://blog.higher-order.net/2009/09/08/understanding-clojures-persistenthashmap-deftwice/ http://blog.higher-order.net/2009/09/08/understanding-clojur... for a lot of detail on the implementation, and http://en.wikipedia.org/wiki/Trie http://en.wikipedia.org/wiki/Trie for a general overview of how Tries differ from Trees.
brehaut 17y ago
For some additional information about the performance of caponia, heres some details about the pain points: The particular pathological case for this system is query where the search stems occur in the majority of documents (there is a small exclusion list that helps, but its not a panacea) because the merging of stem results is at best a linear operation (:or queries are currently much simpler than :and queries) The other difficult case for this system is updating or removing a document from the index; removal is fairly easy: generate the stems for the current state and update those stems in the index. To update (an existing document in the index) efficiently you need the set of stems in both old and new versions of the document; For the stems that are in new set you can just add them to the index as normal. For the difference of the old set and the new set (ie, those stems only in the old set - clojure's difference function is not symmetric i believe) you then need to remove the document id from those stems in the index. edit: clarified meaning of update.