Operational requirements for scalable search systems

ABSTRACT

Prior research into search system scalability has primarily addressed query processing efficiency [1, 2, 3] or indexing efficiency [3], or has presented some arbitrary system architecture [4]. Little work has introduced any formal theoretical framework for evaluating architectures with regard to specific operational requirements, or for comparing architectures beyond simple timings [5] or basic simulations [6, 7]. In this paper, we present a framework based upon queuing network theory for analyzing search systems in terms of operational requirements. We use response time, throughput, and utilization as the key operational characteristics for evaluating performance. Within this framework, we present a scalability strategy that combines index partitioning and index replication to satisfy a given set of requirement.

REFERENCES

• 1: Dirk Bahle , Hugh E. Williams , Justin Zobel, Efficient phrase querying with an auxiliary index, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564415]
• 2: Falk Scholer , Hugh E. Williams , John Yiannis , Justin Zobel, Compression of inverted indexes For fast query evaluation, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564416]
• 3: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 4: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 5: A. Arvind, C. Junghoo, G. Hector, P. Andreas, R. Sriram, "Searching the Web", Stanford Technical Report, Dec. 2000, http://dbpubs.stanford.edu/pub/2000-37.
• 6: B. Cahoon, K. McKinley, "Evaluating the Performance of Distributed Architectures for Information Retrieval using a Variety of Workloads", ACM Transactions on Information Systems, (1997).
• 7: Z. Lu , K. S. McKinley, Partial Collection Replication for Information Retrieval TITLE2:, University of Massachusetts, Amherst, MA, 1999
• 8: Dik Kun Lee , Liming Ren, Document ranking on weight-partitioned signature files, ACM Transactions on Information Systems (TOIS), v.14 n.2, p.109-137, April 1996 [doi>10.1145/226163.226164]
• 9: N. Goharian, T. El-Ghazawi, D. Grossman, A. Chowdhury, "On the Enhancements of a Sparse Matrix Information Retrieval Approach", PDPTA, Las Vegas, Nevada, 2000.
• 10: H. Williams, J. Zobel, P. Anderson, "What's Next? Index Structures for Efficient Phrase Querying", Australasian Database Conference 1999: 141-152.
• 11: D. Bahle, H. Williams, J. Zobel, "Compaction Techniques for Nextword Indexes", SPIRE 2001: 33--45.
• 12: Dirk Bahle , Hugh E. Williams , Justin Zobel, Efficient phrase querying with an auxiliary index, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564415]
• 13: Justin Zobel , Hugh E. Williams, Compact In-Memory Models for Compression of Large Text Databases, Proceedings of the String Processing and Information Retrieval Symposium & International Workshop on Groupware, p.224, September 21-24, 1999
• 14: H. Williams, J. Zobel, "Compressing Integers for Fast File Access". The Computer Journal 42(3): 193--201 (1999).
• 15: Falk Scholer , Hugh E. Williams , John Yiannis , Justin Zobel, Compression of inverted indexes For fast query evaluation, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564416]
• 16: 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
• 17: 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]
• 18: 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]
• 19: Peter B. Danzig , Jongsuk Ahn , John Noll , Katia Obraczka, Distributed indexing: a scalable mechanism for distributed information retrieval, Proceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval, p.220-229, October 13-16, 1991, Chicago, Illinois, United States [doi>10.1145/122860.122883]
• 20: 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 ]
• 21: 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
• 22: A. Moffat, J. Zobel: "Information Retrieval Systems for Large Document Collections". TREC 1994.
• 23: Luis Gravano , Héctor García-Molina , Anthony Tomasic, The effectiveness of GIOSS for the text database discovery problem, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.126-137, May 24-27, 1994, Minneapolis, Minnesota, United States
• 24: 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
• 25: Luis Gravano , Héctor García-Molina , Anthony Tomasic, GlOSS: text-source discovery over the Internet, ACM Transactions on Database Systems (TODS), v.24 n.2, p.229-264, June 1999 [doi>10.1145/320248.320252]
• 26: 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]
• 27: 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]
• 28: A. Bestavros, Demand-based document dissemination to reduce traffic and balance load in distributed information systems, Proceedings of the 7th IEEE Symposium on Parallel and Distributeed Processing, p.338, October 25-28, 1995
• 29: 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]
• 30: Charles Lowell Viles , James C. French, Maintaining retrieval effectiveness in distributed, dynamic information retrieval systems, 1996
• 31: Peter Bailey and David Hawking, A Parallel Architecture for Query Processing Over a Terabyte of Text, Department of Computer Science, Technical Report TR-CS-96-04, (June 1996).
• 32: 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]
• 33: B. Cahoon K. McKinley, "Evaluating the Performance of Distributed Architectures for Information Retrieval using a Variety of Workloads", ACM Transactions on Information Systems, (1997).
• 34: Berthier A. Ribeiro-Neto , Ramurti A. Barbosa, Query performance for tightly coupled distributed digital libraries, Proceedings of the third ACM conference on Digital libraries, p.182-190, June 23-26, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276675.276695]
• 35: Owen de Kretser , Alistair Moffat , Tim Shimmin , Justin Zobel, Methodologies for Distributed Information Retrieval, Proceedings of the The 18th International Conference on Distributed Computing Systems, p.66, May 26-29, 1998
• 36: 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
• 37: Zhihong Lu , Kathryn S. McKinley, Partial replica selection based on relevance for information retrieval, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.97-104, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312662]
• 38: Zhihong Lu , Kathryn S. McKinley, Partial collection replication versus caching for information retrieval systems, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.248-255, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345591]
• 39: R. Jain, "The Art of Computer Systems Performance Analysis: Techniques for Experimental Design, Measurement, Simulation, and Modeling," Wiley- Interscience, New York, NY, April 1991.
• 40: Rajan Suri, Robustness of queuing network formulas, Journal of the ACM (JACM), v.30 n.3, p.564-594, July 1983 [doi>10.1145/2402.2995]
• 41: Y. C. Tay , Rajan Suri, Error bounds for performance prediction in queuing networks, ACM Transactions on Computer Systems (TOCS), v.3 n.3, p.227-254, Aug. 1985 [doi>10.1145/3959.3960]
• 42: Zhen Liu , Philippe Nain, Sensitivity results in open, closed and mixed product form queueing networks, Performance Evaluation, v.13 n.4, p.237-251, Nov. 15, 1991 [doi>10.1016/0166-5316(91)90048-8]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Design, Performance, Theory

Keywords:
operational requirements, search scalability