3 ms·

First, you both are being annoying about the whole thing. From the sounds of it you are both in agreement. tptacek and you are just coming at the same solution

First, you both are being annoying about the whole thing. From the sounds of it you are both in agreement. tptacek and you are just coming at the same solution from different directions. But it's clear that HN is full of brilliant people both in technology and business. Second and OT. I'm interested in anything you can share regarding "given a set of a large number of search terms with a lower cardinality bound of 1 million, how can we scan a set of strings against this search set without exhaustively scanning for every search term in the string set while preserving lemmas on the search set? How can we do this phonetically? How can we do this probabilistically in a weighted n-space?" It sounds like this maps to a particular problem set I'm working on now. Any papers? We've looked into PLSs, numeric hash buckets, independent dispatch of search tests across large distributed systems, etc. All are either no better than a linear exhaustive search in the worst case, too network intensive, too memory intensive or too processor intensive for the applications we're interested in.

elblanco 17y ago
We're dealing with an issue where we have a large corpus of documents to search, and a very large number of search terms to search against this corpus. For example, say you had every comment ever posted in HN and you wanted to search them for every city/state/village/town/etc. The set of places has a cardinality that is very large, and the set of documents to search is also very large. So to do a linear scan (naive search) of a single source document for each search term gives you some terrible O(n^2) or some such. You can try different techniques like: 1) Turn the document into a n-gram lex-trie where n is some value from 1 to some other single digit n. This effectively compresses all the word combinations down to some very fast per-character search usually a O(logn) I think (or better). 2) Tokenize the document into an overlapping n-gram hash which is basically the same as 1, but you eat up less memory if you pre-compute and keep the document hash-sets someplace else (like in a relational dB) but then you get very I/O bound on searches against the hashsets particularly in worst cases with lots of collisions. Plus this makes adding/removing documents more complicated for our purposes since we already compute various indexes and things for other purposes. Keeping half a dozen different kind of indexes really does start to eat up disk space after a while. 3) We thought about compiling the search list down into a lex-trie, doing the same with the documents, and using some kind of tree comparator algorithm to trim the searchterm lex-trie down, but that would be HUGE in memory usage, and driving it off of disk would probably turn us onto non-trie solutions like b+ trees or b* trees so we can page out the sub tree parts without too much performance hit, but at that point we may as well just be using indexed hash sets and the comparator algorithms get all funky since bx trees do all that balancing business, their morphology is mutable. 4) The best solution we've come up with so far is to set n to our maximum search term token length. Tokenize the document into an overlapping set of n-grams (New York City becomes New, New York, New York City, York, York City, City, etc.). We also have taken the search list and turned it into a big indexed hash, in one test we just shoved it all into a SQLite table (brilliant software). Each document token is simply searched against the table. If we get a result, it's good, if not, it's not a search term. It basically searches the document against the search set, inverting the problem. So far it's hideously fast and all of our tests for the above 4 cases were single threaded. Once we multithread out the algorithm it should become even faster. Right now in our test C++ code, we run about 1/10 of a second per document (avg 1k/doc) on a search set of 30million terms. We also haven't developed our metrics for when a search list is "long enough" for this kind of thing to kick in vs. the naive search. Sure you can index the documents down and just do a variation of the naive search, that's what we were advised to do, but it still reduces down to doing 30 million searches/document. Over a corpus of 10 million documents, that's gonna take a while even if a single term search against the index takes 1/100 of a second.

elblanco 17y ago

We're dealing with an issue where we have a large corpus of documents to search, and a very large number of search terms to search against this corpus. For example, say you had every comment ever posted in HN and you wanted to search them for every city/state/village/town/etc. The set of places has a cardinality that is very large, and the set of documents to search is also very large. So to do a linear scan (naive search) of a single source document for each search term gives you some terrible O(n^2) or some such. You can try different techniques like: 1) Turn the document into a n-gram lex-trie where n is some value from 1 to some other single digit n. This effectively compresses all the word combinations down to some very fast per-character search usually a O(logn) I think (or better). 2) Tokenize the document into an overlapping n-gram hash which is basically the same as 1, but you eat up less memory if you pre-compute and keep the document hash-sets someplace else (like in a relational dB) but then you get very I/O bound on searches against the hashsets particularly in worst cases with lots of collisions. Plus this makes adding/removing documents more complicated for our purposes since we already compute various indexes and things for other purposes. Keeping half a dozen different kind of indexes really does start to eat up disk space after a while. 3) We thought about compiling the search list down into a lex-trie, doing the same with the documents, and using some kind of tree comparator algorithm to trim the searchterm lex-trie down, but that would be HUGE in memory usage, and driving it off of disk would probably turn us onto non-trie solutions like b+ trees or b* trees so we can page out the sub tree parts without too much performance hit, but at that point we may as well just be using indexed hash sets and the comparator algorithms get all funky since bx trees do all that balancing business, their morphology is mutable. 4) The best solution we've come up with so far is to set n to our maximum search term token length. Tokenize the document into an overlapping set of n-grams (New York City becomes New, New York, New York City, York, York City, City, etc.). We also have taken the search list and turned it into a big indexed hash, in one test we just shoved it all into a SQLite table (brilliant software). Each document token is simply searched against the table. If we get a result, it's good, if not, it's not a search term. It basically searches the document against the search set, inverting the problem. So far it's hideously fast and all of our tests for the above 4 cases were single threaded. Once we multithread out the algorithm it should become even faster. Right now in our test C++ code, we run about 1/10 of a second per document (avg 1k/doc) on a search set of 30million terms. We also haven't developed our metrics for when a search list is "long enough" for this kind of thing to kick in vs. the naive search. Sure you can index the documents down and just do a variation of the naive search, that's what we were advised to do, but it still reduces down to doing 30 million searches/document. Over a corpus of 10 million documents, that's gonna take a while even if a single term search against the index takes 1/100 of a second.