1
$\begingroup$

Consider a system that indexes documents based on vector space model and a simple query, such as qwe asd. When searching we assign weights to both words qwe and asd based on how often they appear in the index. The idea being that if word exists in larger number of documents then it should have smaller impact on relevance. This works well because for each word we usually store statistics: number of occurrences of a given word in the whole index and number of occurrences of a given word in each document (possibly after normalization).

Now consider another query: "qwe asd" zxcrty. We have two parts here: a phrase and a simple word. For the word we have the above mentioned statistics, but for the phrase we do not. This poses a question: how to rank documents against phrase searches? If we find a one document that contains the phrase (qwe asd) and another that contains the single word (zxcrty) which one should be ranked higher?

I somehow doubt that there is one and ultimate solution to this question but would like to know about what approaches are used in existing search engines, whether other models solve the issue and other information that can be useful in analysing the problem.

$\endgroup$
  • $\begingroup$ Your question seems to be, essentially, how to deal with searching for phrases, rather than single words. I know very little about information retrieval but that seems like an extremely broad question, to me. $\endgroup$ – David Richerby Apr 16 '15 at 11:15
  • $\begingroup$ Also, I removed the tag [search-algorithms] since, to me, that normally refers to searching graphs, state spaces and similar things. But if people feel the tag was appropriate, please reinstate it. $\endgroup$ – David Richerby Apr 16 '15 at 11:18
1
$\begingroup$

As you state in your comment, you could use a variety of different approaches. Your question isn't limited to the vector space model. Various language models rely on these concepts as well. Here are two approaches:

N-Grams

One popular approach is the use of n-grams. This approach involves treating adjacent words as one word. For instance, "big house" would be stored in your controlled vocabulary as "big," "house," and "big house" if you chose to use 2-grams (bigrams). Probabilities would be computed per n-gram

Pros: accurately keep track of probabilities of n-grams occuring, easy to extend from unigram model (just follow same ranking functions for unigrams such as tf-idf or Okapi BM25)

Cons: exponentially larger memory usage, many bigrams will only occur once

Inverted Index per Document

This approach requires storing an inverted index within each document in addition to an inverted index of the whole corpus. This would mean that you wouldn't need to store n-grams. Of course, you wouldn't have important information such as the term frequency or document frequency of an n-gram. The idea is that you look up the first word in the n-gram and find it in the document. You compare succeeding words to see if there is an n-gram present there.

Pros: less memory usage (no need to keep track of n-grams in documents), more flexibility (such as ignoring words that don't match)

Cons: less information stored (no TF, DF, etc.), more space needed per document (for inverted index), additional lookup needed, ranking this may be difficult

If we find a one document that contains the phrase (qwe asd) and another that contains the single word (zxcrty) which one should be ranked higher?

This completely depends on the ranking function and how you choose to weight each thing. How common are qwe and asd? How common is zxcrty? Would you want to give additional weight to larger n-grams? These are all important considerations.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.