Efficiently Querying Phrases in a Huge Document Collection

user_1663215 0
Viewed 116

In an interview, I have received a question that asks me to design a search engine for an online library that contains thousands of documents with millions of words. Initially, the interviewer only asked me to search for single words, clarifying:

  • Search for exact keywords ("overflow" returns true while "overflo" does not)
  • Case-sensitivity can be ignored

My answer was to use a crawler algorithm that runs through each document and creates a lookup table that stores the information in which documents a given word is used, prior to any query executed. Then once a query is executed, all the algorithm have to do is to find the word in the lookup table and return the list of the documents that the word is used.

On the second step, they asked me what would I do if they wanted to search multiple words (not necessarily consecutive) and my answer was to make a new query for each word and find the intersection of the results.

Finally, the interviewer asked me what would I do if they wanted me to query consecutive words or phrases (eg. "stack overflow"). At this point, my lookup table failed since there are no connection between consecutive words and I couldn't come up with a solution in this approach. How can I handle these kind of queries? Are there any problems with my initial answers and design? I have searched on the Internet but couldn't find anything noteworthy.

search text algorithm
1 Answers

For the second case, generate the map such that every key is a word and every value is a set of objects that have the following properties

{
  string document name : location/document_name,
  integer index : index, //location in document,
  toString : hash the object
}

Then when you need to find results for "stack overflow"

For all elements in set 1, does that value exist in set 2 but modified with the item_index + 1.

Get the results for two words but just return the doc names. If there are three words, do the same process you did for two words, but for the third word, check only the matches that passed word 1 and word 2 for word 2, and check to see if those items exist in set 3 with item_index + 1.

user_48307180
Related