Evaluating the performance of distributed architectures for information retrieval using a variety of workloads

ABSTRACT

The information explosion across the Internet and elswhere offers access to an increasing number of document collections. In order for users to effectively access these collections, information retrieval (IR) systems must provide coordinated, concurrent, and distributed access. In this article, we explore how to achieve scalable performance in a distributed system for collection sizes ranging from 1GB to 128GB. We implement a fully functional distributed IR system based on a multithreaded version of the Inquery simulation model. We measure performance as a function of system parameters such as client command rate, number of document collections, ter ms per query, query term frequency, number of answers returned, and command mixture. Our results show that it is important to model both query and document commands because the heterogeneity of commands significantly impacts performance. Based on our results, we recommend simple changes to the prototype and evaluate the changes using the simulator. Because of the significant resource demands of information retrieval, it is not difficult to generate workloads that overwhelm system resources regardless of the architecture. However under some realistic workloads, we demonstrate system organizations for which response time gracefully degrades as the workload increases and performance scales with the number of processors. This scalable architecture includes a surprisingly small number of brokers through which a large number of clients and servers communicate.

REFERENCES

• 1: BAILEY, P. AND HAWKING, D. 1996. A parallel architecture for query processing over a terabyte of text. Tech. Rep. TR-CS-96-04. Department of Computer Science, Australian National Univ., Canberra, Australia.
• 2: David Bell , D. A. Bell , Jane Grimson, Distributed Database Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
• 3: BROWN, E. W. AND CHONG, H.A. 1998. The GURU system in TREC-7. In Proceedings of the 7th Text Retrieval Conference (TREC-7),
• 4: J. A. Brumfield , J. L. Miller , H. T. Chou, Performance modeling of distributed object-oriented database systems, Proceedings of the first international symposium on Databases in parallel and distributed systems, p.22-32, December 05-07, 1988, Austin, Texas, United States
• 5: Forbes J. Burkowski, Retrieval performance of a distributed text database utilizing a parallel processor document server, Proceedings of the second international symposium on Databases in parallel and distributed systems, p.71-79, July 02-04, 1990, Dublin, Ireland [doi>10.1145/319057.319065]
• 6: BURKOWSKI, F., CORMACK, G., CLARKE, C., AND GOOD, R. 1995. A global search architecture. Tech. Rep. CS-95-12. Computer Science Dept., University of Waterloo, Waterloo, Canada.
• 7: Brendon Cahoon , Kathryn S. McKinley, Performance evaluation of a distributed architecture for information retrieval, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.110-118, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243238]
• 8: James P. Callan , W. Bruce Croft , John Broglio, TREC and TIPSTER experiments with INQUERY, Information Processing and Management: an International Journal, v.31 n.3, p.327-343, May-June 1995
• 9: CALLAN, J. P., CROFT, W. B., AND HARDING, S. M. 1992. The INQUERY retrieval system. In Proceedings of the 3rd International Conference on Database and Expert System Applications (Valencia, Spain, Sept.),
• 10: 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]
• 11: T. R. Couvreur , R. N. Benzel , S. F. Miller , D. N. Zeitler , D. L. Lee , M. Singhal , N. Shivaratri , W. Y. P. Wong, An analysis of performance and cost factors in searching large text databases using parallel search systems, Journal of the American Society for Information Science, v.45 n.7, p.443-464, Aug. 1994 [doi>10.1002/(SICI)1097-4571(199408)45:7<443::AID-ASI1>3.0.CO;2-O]
• 12: J. K. Cringean , R. England , G. A. Manson , P. Willett, Parallel text searching in serial files using a processor farm, Proceedings of the 13th annual international ACM SIGIR conference on Research and development in information retrieval, p.429-453, September 05-07, 1990, Brussels, Belgium [doi>10.1145/96749.98249]
• 13: CROFT, W. B., COOK, R., AND WILDER, D. 1995. Providing government information on the Internet: Experiences with THOMAS. In Proceedings of the 2nd International Conference on Theory and Practice of Digital Libraries (DL '95, Austin, TX, June), 19-24.
• 14: CROWDER, G. AND NICHOLAS, C. 1995. An approach to large scale distributed information systems using statistical properties of text to guide agent search. In Proceedings of the CIKM Workshop on Intelligent Information Agents (Baltimore, MD, Dec.),
• 15: David DeWitt , Jim Gray, Parallel database systems: the future of high performance database systems, Communications of the ACM, v.35 n.6, p.85-98, June 1992 [doi>10.1145/129888.129894]
• 16: David J. DeWitt , Robert H. Gerber , Goetz Graefe , Michael L. Heytens , Krishna B. Kumar , M. Muralikrishna, GAMMA - A High Performance Dataflow Database Machine, Proceedings of the 12th International Conference on Very Large Data Bases, p.228-237, August 25-28, 1986
• 17: Fox, E.A. 1983. Characterization of two new experimental collections in computer and information science containing textual and bibliographic concepts. Tech. Rep. 83-561. Cornell University, Ithaca, NY.
• 18: Ophir Frieder , Hava Tova Siegelmann, On the allocation of documents in multiprocessor information retrieval systems, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.230-239, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122884]
• 19: Robert Brian Hagmann , Domenico Ferrari, Performance analysis of several back-end database architectures, ACM Transactions on Database Systems (TODS), v.11 n.1, p.1-26, March 1986 [doi>10.1145/5236.5242]
• 20: HARMAN, D. K., Ed. 1992. Proceedings of the 1st Text Retrieval Conference. (TREC-1, Gaithersburg, MD, Nov.). National Institute of Standards and Technology, Gaithersburg, MD. NIST Special Publication 500-217.
• 21: Donna Harman , Wayne McCoy , Robert Toense , Gerald Candela, Prototyping a distributed information retrieval system that uses statistical ranking, Information Processing and Management: an International Journal, v.27 n.5, p.449-459, 1991 [doi>10.1016/0306-4573(91)90062-Q]
• 22: David Hawking, Scalable Text Retrieval for Large Digital Libraries, Proceedings of the First European Conference on Research and Advanced Technology for Digital Libraries, p.127-145, September 01-03, 1997
• 23: HAWKING, D. AND THISTLEWAITE, P. 1997. Overview of the TREC-6 very large collection track. In Proceedings of the 6th Text Retreival Conference (TREC-6, Nov.), E. Voorhees and D. Harman, Eds.
• 24: HAWKING, D., CRASWELL, N., AND THISTLEWAITE, P. 1998. Overview of TREC-7 very large collection track. In Proceedings of the 7th Text Retrieval Conference (TREC-7),
• 25: Byeong-Soo Jeong , Edward Omiecinski, Inverted File Partitioning Schemes in Multiple Disk Systems, IEEE Transactions on Parallel and Distributed Systems, v.6 n.2, p.142-153, February 1995 [doi>10.1109/71.342125]
• 26: JUMP, J. R. 1993. YACSIM reference manual. Version 2.1.1. Rice University, Houston, TX.
• 27: Z. Lin , S. Zhou, Parallelizing I/O intensive applications for a workstation cluster: a case study, ACM SIGARCH Computer Architecture News, v.21 n.5, p.15-22, Dec. 1993 [doi>10.1145/165660.165664]
• 28: Zhihong Lu , Kathryn S. McKinley , Brendon Cahoon, The Hardware/Software Balancing Act for Information Retrieval on Symmetric Multiprocessors, Proceedings of the 4th International Euro-Par Conference on Parallel Processing, p.521-527, September 01-04, 1998
• 29: Lothar F. Mackert , Guy M. Lohman, R* optimizer validation and performance evaluation for local queries, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.84-95, May 28-30, 1986, Washington, D.C., United States
• 30: Ian A. Macleod , Patrick Martin , Brent Nordin , John R. Phillips, Strategies for building distributed information retrieval systems, Information Processing and Management: an International Journal, v.23 n.6, p.511-528, Sept. 2, 1987 [doi>10.1016/0306-4573(87)90056-2]
• 31: T. Patrick Martin , Judy I. Russell, Data caching strategies for distributed full text retrieval systems, Information Systems, v.16 n.1, p.1-11, 1991 [doi>10.1016/0306-4379(91)90045-B]
• 32: T. P. Martin , I. A. Macleod , J. I. Russell , K. Leese , B. Foster, A case study of caching strategies for a distributed full text retrieval system, Information Processing and Management: an International Journal, v.26 n.2, p.227-247, 1990 [doi>10.1016/0306-4573(90)90028-Z]
• 33: MOFFAT, n. AND ZOBEL, g. 1995. Information retrieval systems for large document collections. In Proceedings of the 3rd Text Retrieval Conference (TREC-3), D. Harman, Ed. National Institute of Standards and Technology, Gaithersburg, MD, 500-525.
• 34: POGUE, C. A. AND WILLETT, P. 1987. Use of text signatures for document retrieval in a highly parallel environment. Parallel Comput. 4, 3 (June), 259-268.
• 35: SCHATZ, B. R. 1990. Interactive retrieval in information spaces distributed across a wide-area network. TR 90-35. Department of Computer Science, University of Arizona, Tucson, AZ.
• 36: P. Simpson , R. Alonso, Data cashing in IR systems, Proceedings of the 10th annual international ACM SIGIR conference on Research and development in information retrieval, p.296-305, June 03-05, 1987, New Orleans, Louisiana, United States [doi>10.1145/42005.42038]
• 37: Craig Stanfill , Brewster Kahle, Parallel free-text search on the connection machine system, Communications of the ACM, v.29 n.12, p.1229-1239, Dec. 1986 [doi>10.1145/7902.7907]
• 38: C. Stanfill , R. Thau , D. Waltz, A parallel indexed algorithm for information retrieval, Proceedings of the 12th annual international ACM SIGIR conference on Research and development in information retrieval, p.88-97, June 25-28, 1989, Cambridge, Massachusetts, United States
• 39: STONEBRAKER, M., WOODFILL, J., RANSTROM, J., KALASH, J., ARNOLD, K., AND ANDERSON, E. 1983. Performance analysis of distributed data base systems. In Proceedings of the 3rd Symposium on Reliability in Distributed Software and Database Systems (Clearwater Beach, FL, Oct.),
• 40: Anthony Slavko Tomasic, Distributed queries and incremental updates in information retrieval systems, Princeton University, Princeton, NJ, 1994
• 41: TOMASIC, A. AND GARCIA-MOLINA, H. 1992. Caching and database scaling in distributed shared-nothing information retrieval systems. Tech. Rep. STAN-CS-92-1456. Stanford University, Stanford, CA.
• 42: Anthony Tomasic , Hector Garcia-Molina, Performance of inverted indices in shared-nothing distributed text document informatioon retrieval systems, Proceedings of the second international conference on Parallel and distributed information systems, p.8-17, January 1993, San Diego, California, United States
• 43: Charles L. Viles , James C. French, Dissemination of collection wide information in a distributed information retrieval system, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.12-20, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215327]
• 44: 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]
• 45: Dietmar Wolfram, Applying informetric characteristics of databases to IR system file design, Part I: informetric models, Information Processing and Management: an International Journal, v.28 n.1, p.121-133, Jan. 1992 [doi>10.1016/0306-4573(92)90098-K]
• 46: ZIPF, G. K. 1949. Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology. Addison-Wesley, Reading, MA.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Experimentation, Performance

Keywords:
distributed information retrieval architectures