Metrics for measuring the tradeoff between efficiency and effectiveness in Information Retrieval

Question

I'm comparing several methods for building inverted indexes (n-grams, hash boundaries, etc.). Given a set of queries, these indexes perform differently. On one hand, I get performances metrics (efficiency) such as the time needed to execute the query. On the other hand, I get metrics such as precision and recall (effectiveness) by checking the relevance of the results. Depending on the method I use, there is a tradeoff between efficiency and effectiveness. For example, some methods loose a little in term of effectiveness for a huge gain in term of efficiency.

Are there some metrics which puts the effectiveness (precision, recall, etc.) in perspective with the efficiency (throughput, memory, etc.)?

Answer 1

I assume that your question is being put in the context of boolean retrieval. It seems that there is not a single metric that takes into account both efficiency and effectiveness and provide a theoretical framework for IR evaluation.

This is mainly because these two issues can sometimes be quite independent between each other. We use certain methods to build inverted indexes in order to mitigate memory issues that arise when we try to index large collections of documents. Some of these methods (such as hash tables) provide fast access to the dictionary (in $O(1)$ time) but fail to accomodate proximity queries (the sort of "find documents that have the word "Beatles" near the word "Animals"). Moreover there are implications arising if we are to index a collection that might change in size and content. Usage of B-trees can overcome these issues as these structures permit an ordering of their contents.

On the other hand some other methods (such as k-gram auxiliary indexes) charge us with additional processing time but offer a more broad range of queries that can be computed (complex wildcard queries such "co*ter*ed"). In general this results in a more powerful IR system in the sense of a wider capability in answering queries.

There is of course the "user happines" measure that takes into account the extent to which the user's information need is satisfied by the system but this is not always the case as users tend to take into consideration several other factors like the user interface which is independent of the system's performance.

In my humble opinion the issue of the relation between effectiveness and efficiency is something that can be examined more thoroughly in the "real" context of an implemented IR system. It is in this setting that more concrete conclusions can be extracted about the effect that different indexing methods have on the performance of the IR system.

An excellent resource in these topics is the following book by Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze http://nlp.stanford.edu/IR-book/information-retrieval-book.html