Efficient and effective metasearch for text databases incorporating linkages among documents

ABSTRACT

Linkages among documents have a significant impact on the importance of documents, as it can be argued that important documents are pointed to by many documents or by other important documents. Metasearch engines can be used to facilitate ordinary users for retrieving information from multiple local sources (text databases). There is a search engine associated with each database. In a large-scale metasearch engine, the contents of each local database is represented by a representative. Each user query is evaluated against he set of representatives of all databases in order to determine the appropriate databases (search engines) to search (invoke) In previous word, the linkage information between documents has not been utilized in determining the appropriate databases to search. In this paper, such information is employed to determine the degree of relevance of a document with respect to a given query. Specifically, the importance (rank) of each document as determined by the linkages is integrated in each database representative to facilitate the selection of databases for each given query. We establish a necessary and sufficient condition to rank databases optimally, while incorporating the linkage information. A method is provided to estimate the desired quantities stated in the necessary and sufficient condition. The estimation method runs in time linearly proportional to the number of query terms. Experimental results are provided to demonstrate the high retrieval effectiveness of the method.

REFERENCES

• 1: Christoph Baumgarten, A probabilistic model for distributed information retrieval, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.258-266, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 2: Christoph Baumgarten, A probabilistic solution to the selection and fusion problem in distributed information retrieval, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.246-253, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312685]
• 3: N. J. Belkin , P. Kantor , E. A. Fox , J. A. Shaw, Combining the evidence of multiple query representations for information retrieval, Information Processing and Management: an International Journal, v.31 n.3, p.431-448, May-June 1995
• 4: James P. Callan , Zhihong Lu , W. Bruce Croft, Searching distributed collections with inference networks, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.21-28, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215328]
• 5: Y. Fan, and S. Gauch. Adaptive Agents for Information Gathering from Multiple, Distributed Information Sources. 1999 AAAI Symposium on Intelligent Agents in Cyberspace, Stanford University, March 1999.
• 6: Luis Gravano , Hector Garcia-Molina, Generalizing GlOSS to Vector-Space Databases and Broker Hierarchies, Proceedings of the 21th International Conference on Very Large Data Bases, p.78-89, September 11-15, 1995
• 7: Luis Gravano , Hector Garcia-Molina, Merging Ranks from Heterogeneous Internet Sources, Proceedings of the 23rd International Conference on Very Large Data Bases, p.196-205, August 25-29, 1997
• 8: A. Howe, and D. Dreilinger. SavvySearch: A Meta-Search Engine that Learns Which Search Engines to Query. AI Magazine, 18(2), 1997.
• 9: Bernard J. Jansen , Amanda Spink , Judy Bateman , Tefko Saracevic, Real life information retrieval: a study of user queries on the Web, ACM SIGIR Forum, v.32 n.1, p.5-17, Spring 1998 [doi>10.1145/281250.281253]
• 10: B. Kahle, and A. Medlar. An Information System for Corporate Users: Wide Area information Servers. Technical Report TMC199, Thinking Machine Corporation, April 1991.
• 11: T. Kirk, A. Levy, Y. Sagiv, and D. Srivastava. The Information Manifold. AAAI Spring Symposium on Information Gathering in Distributed Heterogeneous Environments. 1995.
• 12: Steven Kirsch, Infoseek's experiences searching the internet, ACM SIGIR Forum, v.32 n.2, p.3-7, Sept. 1998 [doi>10.1145/305110.305112]
• 13: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 14: Martijn Koster, ALIWEB—Archie-like indexing in the WEB, Computer Networks and ISDN Systems, v.27 n.2, p.175-182, Nov. 1994
• 15: Erika F. de Lima , Jan O. Pedersen, Phrase recognition and expansion for short, precision-biased queries based on a query log, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.145-152, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312669]
• 16: King-Lup Liu , Clement Yu , Weiyi Meng , Wensheng Wu , Naphtali Rishe, A Statistical Method for Estimating the Usefulness of Text Databases, IEEE Transactions on Knowledge and Data Engineering, v.14 n.6, p.1422-1437, November 2002 [doi>10.1109/TKDE.2002.1047777]
• 17: U. Manber, and P. Bigot. The Search Broker. USENIX Symposium on Internet Technologies and Systems (NSITS'97), Monterey, California, 1997, pp. 231-239.
• 18: Weiyi Meng , King-Lup Liu , Clement T. Yu , Xiaodong Wang , Yuhsi Chang , Naphtali Rishe, Determining Text Databases to Search in the Internet, Proceedings of the 24rd International Conference on Very Large Data Bases, p.14-25, August 24-27, 1998
• 19: Estimating the Usefulness of Search Engines, Proceedings of the 15th International Conference on Data Engineering, p.146, March 23-26, 1999
• 20: W. Meng, C. Yu, and K. Liu. Building Efficient and Effective Metasearch Engines, Technical Report, Dept. of CS, SUNY at Binghamton, 2000.
• 21: L. Page, S. Brin, R. Motwani, and Terry Winograd. The PageRank Citation Ranking: Bring Order to the Web. Technical Report, Stanford University, 1998.
• 22: Allison L. Powell , James C. French , Jamie Callan , Margaret Connell , Charles L. Viles, The impact of database selection on distributed searching, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.232-239, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345584]
• 23: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 24: E. Selberg, and O. Etzioni. The MetaCrawler Architecture forResource Aggregation on the Web. IEEE Expert, 1997.
• 25: Amit Singhal , Chris Buckley , Mandar Mitra, Pivoted document length normalization, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.21-29, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243206]
• 26: Ellen M. Voorhees , Narendra K. Gupta , Ben Johnson-Laird, Learning collection fusion strategies, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.172-179, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215357]
• 27: Zonghuan Wu , Weiyi Meng , Clement Yu , Zhuogang Li, Towards a highly-scalable and effective metasearch engine, Proceedings of the 10th international conference on World Wide Web, p.386-395, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372093]
• 28: Jinxi Xu , Jamie Callan, Effective retrieval with distributed collections, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.112-120, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290974]
• 29: Jinxi Xu , W. Bruce Croft, Cluster-based language models for distributed retrieval, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.254-261, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312687]
• 30: Clement T. Yu , Weiyi Meng, Principles of database query processing for advanced applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 31: Clement Yu , King-Lup Liu , Wensheng Wu , Weiyi Meng , Naphtali Rishe, Finding the Most Similar Documents across Multiple Text Databases, Proceedings of the IEEE Forum on Research and Technology Advances in Digital Libraries, p.150, March 19-21, 1999
• 32: Clement Yu , King-Lup Liu , Weiyi Meng , Zonghuan Wu , Naphtali Rishe, A Methodology to Retrieve Text Documents from Multiple Databases, IEEE Transactions on Knowledge and Data Engineering, v.14 n.6, p.1347-1361, November 2002 [doi>10.1109/TKDE.2002.1047772]
• 33: Clement Yu , Weiyi Meng , King-Lup Liu , Wensheng Wu , Naphtali Rishe, Efficient and effective metasearch for a large number of text databases, Proceedings of the eighth international conference on Information and knowledge management, p.217-224, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/319950.320005]
• 34: Budi Yuwono , Dik Lun Lee, Server Ranking for Distributed Text Retrieval Systems on the Internet, Proceedings of the Fifth International Conference on Database Systems for Advanced Applications (DASFAA), p.41-50, April 01-04, 1997

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

General Terms:
Design, Documentation, Experimentation, Management, Measurement, Performance, Theory, Verification

Keywords:
distributed collection, information retrieval, linkages among documents, metasearch