4 ms·
to quote http://infolab.stanford.edu/~backrub/google.html http://infolab.stanford.edu/~backrub/google.html Indexing Documents into Barrels -- After each docume
by johngunderman 17y ago
to quote http://infolab.stanford.edu/~backrub/google.html http://infolab.stanford.edu/~backrub/google.html
Indexing Documents into Barrels -- After each document is parsed, it is encoded into a number of barrels. Every word is converted into a wordID by using an in-memory hash table -- the lexicon. New additions to the lexicon hash table are logged to a file. Once the words are converted into wordID's, their occurrences in the current document are translated into hit lists and are written into the forward barrels. The main difficulty with parallelization of the indexing phase is that the lexicon needs to be shared. Instead of sharing the lexicon, we took the approach of writing a log of all the extra words that were not in a base lexicon, which we fixed at 14 million words. That way multiple indexers can run in parallel and then the small log file of extra words can be processed by one final indexer.
So we have a hash table of words/searches -> results
Because we have this, we can regex search the keys, and end up with the result pages.
we do have other options though. It could be:
a) magic
b) a trade secret (think PidgeonRank :-) )
- tumult 17y agoQuote is unrelated to what you are saying! use MapReduce to expand the regex over the keys So we have a hash table of words/searches -> results Because we have this, we can regex search the keys, and end up with the result pages. ... Looking forward to further explanations!
- inerte 17y agoImagine the following code: money = 5; Could be tokenized and mapped to a few regex keywords, with one or another as key-value in a datastore. Since Google is big on MapReduce, which could be seen as computation on sets: [a-z] = (DOCID_14566, DOCID_15999, DOCID_888) \d{5} = (DOCID_15, DOCID_15999, DOCID_552) Then when someone searchs for a "number with five digits", the value for the \d{5} key is retrived, and it has the documents where the search appears, and this set/list is combined with the other set/list that match other search keywords, and you have your results. On a normal web search, the document is split into words and you can make these words into keys, so know where they appear, right? (the key's values). Well, if you think that the user will type a regex expression "\d{5}", then you can map it to documents too. It's like pre-processing the possible regex that would match a document token, and searching these regexes instead of words like a normal web search. It's "just" an extra step, splitting words (tokens) from a document, and assigning possible regexes for these tokens. Not saying Google does it :p But I guess that's what the OP meant... Edited: Before anyone notices how inefficient my example is, I wouldn't implement every possible \d as a key, or [a-b], [a-c], [a-d] etc as another key, this is just an example of how sets of precomputed regexs (from any depth) can be (ab)used.
- tumult 17y agoThis makes sense and it could work :) I imagine you would have to spend time tuning the tokens you map out. I think this would break down pretty quickly with moderate or complicated regexes, but those might not be the majority of searches. Is there any trickery you could do with the inner nodes on the b+trees? I spent a few minutes thinking about tokens mapped out and intermediate reductions but didn't come up with anything.
- johngunderman 17y agoHey, its all postulation :)