3 ms·
How does that help here? My query doesn't contain any directly-searchable strings, unless you start abstracting things by treating all alpha chars as the same,
by pc 17y ago
How does that help here? My query doesn't contain any directly-searchable strings, unless you start abstracting things by treating all alpha chars as the same, etc.
- deleted 17y ago[deleted]
- jaydub 17y agoIf I understand correctly (a big if) and the underlying structure is something along the lines of a giant suffix tree then searching for any particular string takes time asymtomtically equivalent to the length of the query string. What if there were another corresponding "meta-data" suffix-tree perhaps this would allow the fast abstract search. what if the nodes contained meta-data such as length/type etc instead of merely containing the data itself.
- fizx 17y agoA nice thing about regular expressions is that you always know where you are in the expression (no backtracking, at least in theory). Say your query is \d+(th|nd|rd), and your searchable text is "The 3rd planet from the sun is 20000000 miles away." Your tree search will hit 2, then fail on 20, then 3, then 3r, then 3rd, and then terminate successfully. So we followed 5 pointers, and tested another 20 or so for nullity. This was independent of the length of the searchable text (but not the number of found matches). It would have performed equally well on "The 3rd planet from the sun is 20000000 miles away. Lorem ipsum (insert 10mb of random Latin here)".
- nostrademons 17y agoHow much RAM do you think it'd take to store all the world's source code in a suffix tree, and how would you partition it across multiple machines?
- fizx 17y agoWell, there's always suffix arrays, so two 64-bit pointers, (plus the original char) per char? Assuming their claim of 116,000,000 matches for /./, and 5k mean document size, 70TB, uncompressed. Papers like "Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching" [1] lead me to believe that the state of the art could be as low as 4 bits/char, in which case the answer would be a much more tractable 270GB. As far as partitioning goes, now I'm getting really out of my league. At a first pass, I imagine that you could keep the root and neighbors on a primary server, and as big of subtrees as you can fit in RAM on a bunch of slaves. The first couple chars get processed in the master, and then however many subtrees are alive get delegated in parallel to the secondary servers. The secondary servers return the answers to the primary, which returns to the client. I feel like I'm answering hypothetical questions at a job interview :p [1] http://www.di.unipi.it/~grossi/PAPERS/sicomp05.pdf http://www.di.unipi.it/~grossi/PAPERS/sicomp05.pdf
- tlb 17y agoThe math doesn't work. 116,000,000 matches x 5k is 580 GB. It fits on one big disk, and with 5800 machines holding 100 Mb of plain text each you could search all of it naively in real time. (Grep searches 100 Mb in 50 mSec.) 5800 machines is practical for a real product. Hardware probably costs Google $40/month/CPU, so $230k / month, about equal to 10 engineers. So if a more clever solution needs a whole team to maintain it then it's probably better to just use grep.
- fizx 17y ago10 engineers to program one data structure? I'd be greatly surprised if 1 PhD and 2 engineers couldn't easily do the additional work beyond distributed grep in less than six months. Maybe one engineer to maintain it? That saves ~$200k/mo--more if you go over 20 queries/second it takes to max out the 5800cpu limit.