R. Manmatha
ABSTRACT
In this paper the score distributions of a number of text search engines are modeled. It is shown empirically that the score distributions on a per query basis may be fitted using an exponential distribution for the set of non-relevant documents and a normal distribution for the set of relevant documents. Experiments show that this model fits TREC-3 and TREC-4 data for not only probabilistic search engines like INQUERY but also vector space search engines like SMART for English. We have also used this model to fit the output of other search engines like LSI search engines and search engines indexing other languages like Chinese.
It is then shown that given a query for which relevance information is not available, a mixture model consisting of an exponential and a normal distribution can be fitted to the score distribution. These distributions can be used to map the scores of a search engine to probabilities. We also discuss how the shape of the score distributions arise given certain assumptions about word distributions in documents. We hypothesize that all 'good' text search engines operating on any language have similar characteristics.
This model has many possible applications. For example, the outputs of different search engines can be combined by averaging the probabilities (optimal if the search engines are independent) or by using the probabilities to select the best engine for each query. Results show that the technique performs as well as the best current combination techniques.
- 1.A. Arampatzis, J. Beney, C. H. A. Koster, and T. P. van der Weide. Incrementality, half-life and threshold optimization for adaptive document filtering. In Proc. of the 9th Text Retrieval Conference (TREC-9). NIST, Nov 2000, To be published in late 2001.Google Scholar
- 2.J. A. Aslam, , and M. Montague. Bayes optimal metasearch: A probabilistic model for combining the results of multiple retrieval systems. In the Proc. of the 23rd ACM SIGIR conf. on Research and Developement in Information Retrieval, pages 379-381, 2000. Google ScholarDigital Library
- 3.C. M. Bishop. Neural Networks for Pattern Recognition. Oxford University Press, 1995. Google ScholarDigital Library
- 4.A. Bookstein. When the most Pertinent document should not be retrieved - an analysis of the Swets model. Information Processing and Management, 13:377-383, 1977.Google ScholarCross Ref
- 5.J. Callan, Z. Lu, and W. B. Croft. TREC and TIPSTER experiments with INQUERY. In the Proc. of the 18th ACM SIGIR conf. on Research and Developement in Information Retrieval, pages 21-28, 1995. Google ScholarDigital Library
- 6.K. W. Church and W. A. Gale. Poisson mixtures. Natural Language Engineering, 1(2):163-190, 1995.Google Scholar
- 7.W. B. Croft. Combining approaches to information retrieval. In W. B. Croft, editor, Advances in Information Retrieval, pages 1-36. Kluwer Academic Publishers, 2000.Google Scholar
- 8.R. Fagin. Fuzzy queries in multimedia database systems. In the Proc. of the 17th ACM Conference on Prnciples of Database Systems (PODS), pages 1-10, 1998. Google ScholarDigital Library
- 9.M. Flickner, H. S. Sawhney, J. Ashley, Q. Huang, B. Dom, M. Gorkani, J. Hafner, D. Lee, D. Petkovic, D. Steele, and P. Yanker. Query by image and video content: The QBIC system. IEEE Computer Magazine, 28(9):23-30, Sept. 1995. Google ScholarDigital Library
- 10.E. Fox and J. Shaw. Combination of multiple searches. In the Proc. of the 2nd Text Retrieval Conference (TREC-2), pages 243-252. National Institute of Standards and Technology Special Publications 500-215, 1994.Google Scholar
- 11.W. Greiff. The use of exploratory data analysis in information retrieval research. In W. B. Croft, editor, Advances in Information Retrieval, pages 37-72. Kluwer Academic Publishers, 2000.Google Scholar
- 12.S. P. Harter. A probabilistic approach to automatic keyword indexing. Journal of the American Society for Information Science, 20:197-206, 1975.Google ScholarCross Ref
- 13.J. H. Lee. Combining multiple evidence form different properties of weighting schemes. In the Proc. of the 18th Intl. Conf. on Research and Development in Information Retrieval (SIGIR'95), pages 180-188, 1995. Google ScholarDigital Library
- 14.J. H. Lee. Analyses of multiple evidence combination. In the Proc. of the 20th Intl. Conf. on Research and Development in Information Retrieval (SIGIR'97), pages 267-276, 1997. Google ScholarDigital Library
- 15.G. McLachlan and D. Peel. Finite Mixture Models. John Wiley, 2000.Google ScholarCross Ref
- 16.F. Mosteller and D. Wallace. Inference and Disputed Authorship: The Federalist. Addison Weseley, 1964.Google Scholar
- 17.S. E. Robertson and S. Walker. Some simple effective approximations to the 2-poisson model for probabilistic weighted retrieval. In the Proc. of the 17th ACM SIGIR conf. on Research and Developement in Information Retrieval, pages 232-241, 1994. Google ScholarDigital Library
- 18.J. A. Swets. Information retrieval systems. Science, 141:245-250, 1963.Google Scholar
- 19.K. Tumer and J. Ghosh. Linear and order statistics combiners for pattern clasification. In A. Sharkey, editor, Combining Artificial Neural Networks, pages 127-162. Springer-Verlag, 1999.Google Scholar
- 20.C. J. van Rijsbergen. Information Retrieval. Butterworths, 1979. Google ScholarDigital Library
- 21.C. Vogt and G. Cottrell. Predicting the performance of linearly combined IR systems. In the Proc. of the 21st ACM SIGIR conf. on Research and Developement in Information Retrieval, pages 190-196, 1998. Google ScholarDigital Library
- 22.E. Voorhees, N. Gupta, and B. Johnson-Laird. Learning collection fusion strategies. In the Proc. of the 18th ACM SIGIR conf. on Research and Developement in Information Retrieval, pages 172-179, 1995. Google ScholarDigital Library
Index Terms
- Modeling score distributions for combining the outputs of search engines
Recommendations
Overlap Among Major Web Search Engines
ITNG '06: Proceedings of the Third International Conference on Information Technology: New GenerationsOur study examined the overlap among results retrieved by three major Web search engines for a large set of more than 10,316 queries. Previous smaller studies have discussed the lack of overlap in results returned by Web search engines for the same ...
A study of results overlap and uniqueness among major web search engines
The performance and capabilities of Web search engines is an important and significant area of research. Millions of people world wide use Web search engines very day. This paper reports the results of a major study examining the overlap among results ...
Comments