Methods for information server selection

ABSTRACT

The problem of using a broker to select a subset of available information servers in order to achieve a good trade-off between document retrieval effectiveness and cost is addressed. Server selection methods which are capable of operating in the absence of global information, and where servers have no knowledge of brokers, are investigated. A novel method using Lightweight Probe queries (LWP method) is compared with several methods based on data from past query processing, while Random and Optimal server rankings serve as controls. Methods are evaluated, using TREC data and relevance judgments, by computing ratios, both empirical and ideal, of recall and early precision for the subset versus the complete set of available servers. Estimates are also made of the best-possible performance of each of the methods. LWP and Topic Similarity methods achieved best results, each being capable of retrieving about 60% of the relevant documents for only one-third of the cost of querying all servers. Subject to the applicable cost model, the LWP method is likely to be preferred because it is suited to dynamic environments. The good results obtained with a simple automatic LWP implementation were replicated using different data and a larger set of query topics.

REFERENCES

• 1: ALLAN, J., BALLESTEROS, L., CALLAN, J. P., CROFT, W. B., AND LU, Z. 1995. Recent experiments with INQUERY. In Proceedings of the 4th Text Retrieval Conference (TREC-4, Washington, D.C., Nov.), D. K. Harman, Ed. National Institute of Standards and Technology, Gaithersburg, MD, 49-63.
• 2: BUCKLEY, C., SINGHAL, A., AND MITRA, M. 1996. Using query zoning and correlation within SMART. In Proceedings of the 5th Text Retrieval Conference (TREC-5, Gaithersburg, MD, Nov.), E. M. Voorhees and D. K. Harman, Eds. National Institute of Standards and Technology, Gaithersburg, MD, 105-118.
• 3: BUCKLEY, C., SINGHAL, A., MITRA, M., AND SALTON, G. 1995. New retrieval approaches using SMART. In Proceedings of the 4th Text Retrieval Conference (TREC-4, Washington, D.C., Nov.), D. K. Harman, Ed. National Institute of Standards and Technology, Gaithersburg, MD, 25-48.
• 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: Anil S. Chakravarthy , Kenneth B. Haase, NetSerf: using semantic knowledge to find Internet information archives, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.4-11, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215326]
• 6: CLARKE, C. L. A., CORMACK, G. V., AND BURKOWSKI, F.J. 1995. Shortest substring ranking MultiText experiments for TREC-4. In Proceedings of the 4th Text Retrieval Conference (TREC-4, Washington, D.C., Nov.), D. K. Harman, Ed. National Institute of Standards and Technology, Gaithersburg, MD, 295-304.
• 7: R. Dolin , D. Agrawal , L. Dillon , A. E Abbadi, Pharos: A Scalable Distributed Architecture for Locating Heterogeneous Information Sources, University of California at Santa Barbara, Santa Barbara, CA, 1996
• 8: DUMAIS, S.T. 1992. LSI meets TREC: A status report. In Proceedings of the 1st Text Retrieval Conference (TREC-1, Gaithersburg, MD, Nov.), D. K. Harman, Ed. National Institute of Standards and Technology, Gaithersburg, MD, 137-152.
• 9: Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, July 1995
• 10: 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
• 11: Luis Gravano , Kevin Chang , Hector Garcia-Molina , Andreas Paepcke, STARTS: Stanford Protocol Proposal for Internet Retrieval and Search, Stanford University, Stanford, CA, 1997
• 12: HARMAN, D. K., Ed. 1995. Proceedings of the 4th Text Retrieval Conference. (TREC-4, Washington, D.C., Nov.). National Institute of Standards and Technology, Gaithersburg, MD.
• 13: HAWKING, D. AND BAILEY, P. 1997. Parallel document retrieval engine (PADRE) web page. Australian National University, Canberra, Australia. http://cap.anu.edu.au/cap/ projects/text_retrieval.
• 14: HAWKING, D. AND THISTLEWAITE, P. 1995. Proximity operators--So near and yet so far. In Proceedings of the 4th Text Retrieval Conference (TREC-4, Washington, D.C., Nov.), D. K. Harman, Ed. National Institute of Standards and Technology, Gaithersburg, MD, 131-143.
• 15: HAWKING, D. AND THISTLEWAITE, P. 1996. Relevance weighting using distance between term occurrences. Tech. Rep. TR-CS-96-08. Department of Computer Science, Australian National Univ., Canberra, Australia. Available via http://cs.anu.edu.au/techreports/1996/ index.html.
• 16: HAWKING, D., THISTLEWAITE, P., AND BAILEY, P. 1996. ANU/ACSys TREC-5 experiments. In Proceedings of the 5th Text Retrieval Conference (TREC-5, Gaithersburg, MD, Nov.), E. M. Voorhees and D. K. Harman, Eds. National Institute of Standards and Technology, Gaithersburg, MD, 359-376.
• 17: HORIE, T., ISHIHATA, H., SHIMIZU, T., AND IKESAKA, M. 1991. AP1000 architecture and performance of LU decomposition. In Proceedings of the 1991 International Conference on Parallel Processing. 634-635.
• 18: KIRK, T., LEVY, A. Y., SAGIV, Y., AND SRIVASTAVA, D. 1995. The information manifold. In Papers from the AAAI Spring Symposium on Information Gathering in Distributed Heterogenous Environments (Menlo Park, CA, Mar.), C. Knoblock and A. Levy, Eds. AAAI Press, Menlo Park, CA, 85-91.
• 19: Lu, Z., CALLAN, J. P., AND CROFT. W. B., 1996. Measures in collection ranking evaluation. Tech. Rep. TR96-39. Department of Computer Science, University of MassachuseAts, Amherst, MA.
• 20: George A. Miller, WordNet: a lexical database for English, Communications of the ACM, v.38 n.11, p.39-41, Nov. 1995 [doi>10.1145/219717.219748]
• 21: 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]
• 22: VOORHEES, E. M. AND HARMAN, D. K., Eds. 1996. Proceedings of the 5th Text Retrieval Conference. (TREC-5, Gaithersburg, MD, Nov.). National Institute of Standards and Technology, Gaithersburg, MD.
• 23: 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:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process; Selection process
      H.3.4 Systems and Software
          Subjects: Information networks
      H.3.6 Library Automation
          Subjects: Large text archives

General Terms:
Design, Experimentation, Performance

Keywords:
Lightweight Probe queries, information servers, network servers, server ranking, server selection, text retrieval