Mixture model with multiple centralized retrieval algorithms for result merging in federated search

ABSTRACT

Result merging is an important research problem in federated search for merging documents retrieved from multiple ranked lists of selected information sources into a single list. The state-of-the-art result merging algorithms such as Semi-Supervised Learning (SSL) and Sample-Agglomerate Fitting Estimate (SAFE) try to map document scores retrieved from different sources to comparable scores according to a single centralized retrieval algorithm for ranking those documents. Both SSL and SAFE arbitrarily select a single centralized retrieval algorithm for generating comparable document scores, which is problematic in a heterogeneous federated search environment, since a single centralized algorithm is often suboptimal for different information sources. Based on this observation, this paper proposes a novel approach for result merging by utilizing multiple centralized retrieval algorithms. One simple approach is to learn a set of combination weights for multiple centralized retrieval algorithms (e.g., logistic regression) to compute comparable document scores. The paper shows that this simple approach generates suboptimal results as it is not flexible enough to deal with heterogeneous information sources. A mixture probabilistic model is thus proposed to learn more appropriate combination weights with respect to different types of information sources with some training data. An extensive set of experiments on three datasets have proven the effectiveness of the proposed new approach.

References

1. J. Arguello, J. Callan, and F. Diaz. Classification-based resource selection. Proceeding of the 18th ACM conference on Information and knowledge management, pages 1277--1286, 2009.
2. M. Baillie and M. Carman. A multi-collection latent topic model for federated search. Information Retrieval, 14(4):390--412, Aug. 2011.
3. M. Bergman. The deep web: surfacing the hidden value. Technical report, 2001.
4. J. Callan. Distributed information retrieval. Advances in Information Retrieval, pages 127--150, 2000.
5. J. Callan, W. B. Croft, and S. M. Harding. The inquery retrieval system. In Proceedings of the Third International Conference on Database and Expert Systems Applications, 1992.
6. N. Craswell, D. Hawking, and P. Thistlewaite. Merging results from isolated search engines. In Proceedings of the 10th Austrlasian Database Conference, 1999.
7. A. P. Dempster, N. M. Laird, and D. Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society, 39(B):1--38, 1977.
8. R. Fletcher. Practical methods of optimization, volume 1. Wiley, 1987.
9. L. Gravano, C.-C. K. Chang, H. Garcia-Molina, and A. Paepcke. Starts: Stanford proposal for internet meta-searching. In Proceedings of the ACM-SIGMOD International Conference on Management of Data (SIGMOD). ACM, 1997.
10. L. Gravano, H. Garcia-Molina, and A. Tomasic. Gloss: text-source discovery over the internet. ACM Transactions on Database Systems (TODS), 24(2):229--264, 1999.
11. J. Gross. Linear regression, volume 175. Springer Verlag, 2003.
12. C. He, D. Hong, and L. Si. A weighted curve fitting method for result merging in federated search. In Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval, SIGIR '11, pages 1177--1178, New York, NY, USA, 2011. ACM.
13. http://lemurproject.org/clueweb09/. The clueweb09 dataset.
14. http://www.lemurproject.org/. The lemur toolkit.
15. A. Kulkarni and J. Callan. Document allocation policies for selective searching of distributed indexes. Proceedings of the 19th ACM international conference on Information and knowledge management, pages 449--458, 2010.
16. J. Lafferty and C. Zhai. Document language models, query models, and risk minimization for information retrieval. Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, pages 111--119, 2001.
17. W. Meng and C. Yu. Advanced metasearch engine technology. Synthesis Lectures on Data Management, 2(1):1--129, 2010.
18. D. Metzler and W. B. Croft. Combining the language model and inference network approaches to retrieval. Information Processing and Management, 40(5):735--750, 2004.
19. Y. Rasolofo, F. Abbaci, and J. Savoy. Approaches to collection selection and results merging for distributed information retrieval. Proceedings of the tenth international conference on Information and knowledge management, pages 191--198, 2001.
20. S. Robertson, S. Walker, S. Jones, M. Hancock-Beaulieu, and M. Gatford. Okapi at trec-3. NIST SPECIAL PUBLICATION SP, pages 109--109, 1995.
21. G. Salton, E. Fox, and H. Wu. Extended boolean information retrieval. Communications of the ACM, 26(11):1022--1036, 1983.
22. M. Shokouhi. Central-rank-based collection selection in uncooperative distributed information retrieval. Advances in Information Retrieval, 2007.
23. M. Shokouhi and L. Si. Federated search. 2011.
24. M. Shokouhi and J. Zobel. Robust result merging using sample-based score estimates. ACM Transactions on Information Systems (TOIS), 27(3):1--29, 2009.
25. X. M. Shou and M. Sanderson. Experiments on data fusion using headline information. In Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, SIGIR '02, pages 413--414, New York, NY, USA, 2002. ACM.
26. L. Si and J. Callan. Relevant document distribution estimation method for resource selection. Proceedings of the 26th annual international ACM SIGIR conference on Research and development in information retrieval, pages 298--305, 2003.
27. L. Si and J. Callan. A semisupervised learning method to merge search engine results. ACM Transactions on Information Systems (TOIS), 21(4):457--491, 2003.
28. T. Strohman, D. Metzler, H. Turtle, and C. W. B. Indri: A language model-based search engine for complex queries. In Proceedings of the International Conference on Intelligence Analysis, 2004.
29. P. Thomas. Server selection in distributed information retrieval: a survey. To appear in: Journal of Information Retrieval, 2012.
30. M. Tsai, H. Chen, and Y. Wang. Learning a merge model for multilingual information retrieval. Information Processing & Management, 47(5):635--646, 2011.
31. Y. Wang and D. J. DeWitt. Computing pagerank in a distributed internet search system. In VLDB '04: Proceedings of the Thirtieth international conference on Very large data bases, pages 420--431. VLDB Endowment, 2004.
32. S. Wu, Y. Bi, and X. Zeng. The linear combination data fusion method in information retrieval. In Database and Expert Systems Applications, pages 219--233. Springer, 2011.
33. J. Xu and J. Callan. Effective retrieval with distributed collections. Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, pages 112--120, 1998.
34. J. Xu and W. B. Croft. Cluster-based language models for distributed retrieval. Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, pages 254--261, 1999.

Index Terms

• Information systems

  • Information retrieval

    • Retrieval models and ranking