Modelling Search Engines Performance Using Coloured Petri Nets

• Autorzy: Gil-Costa, V. , Marin, M. , Inostrosa-Psijas, A. , Lobos, J. , Bonacic, C.
• Języki publikacji: EN

Abstrakty

EN

This paper proposes using Coloured Petri Nets to model performance of vertical search engines for Web search. In such systems, queries submitted by users or client systems are handled by different components implemented as services deployed on large clusters of dedicated processors. We propose models that represent key features of components running time cost at a suitable level of detail. A comprehensive evaluation study is presented to reveal good precision of models when compared against actual implementations and complex process-oriented simulators of the same search engine instances. A C++ class library is proposed to enable rapid model construction by using a hierarchical and scalable approach, and to enable transparent generation and efficient execution of respective simulation programs either sequentially or in parallel.

Słowa kluczowe

EN

web search engines; Petri net applications; performance evaluation; modelling

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 131, nr 1
• Strony: 139--166
• Opis fizyczny: Bibliogr. 40 poz., rys., tab., wykr.

Twórcy

autor

Gil-Costa, V.

• CONICET, University of San Luis, Argentina,
• Yahoo! Labs Santiago, Chile

autor

Marin, M.

• DIINF, University of Santiago, Chile
• Yahoo! Labs Santiago, Chile

autor

Inostrosa-Psijas, A.

• DIINF, University of Santiago, Chile

autor

Lobos, J.

• DINF, University of San Luis, Argentina

autor

Bonacic, C.

• DIINF, University of Santiago, Chile

Bibliografia

• [1] M. Al-Fares, A. Loukissas, and A. Vahdat. A scalable, commodity data center network architecture. SIGCOMM, 38:63–74, 2008.
• [2] M. Arlitt, D. Krishnamurthy, and J. Rolia. Characterizing the scalability of a large web-based shopping system. J. of ACM Trans. Internet Technol., 1:44–69, 2001.
• [3] C. S. Badue, J. M. Almeida, V. Almeida, R. A. Baeza-Yates, B. A. Ribeiro-Neto, A. Ziviani, and N. Ziviani. Capacity planning for vertical search engines. CoRR, abs/1006.5059, 2010.
• [4] C. S. Badue, R. A. Baeza-Yates, B. A. Ribeiro-Neto, A. Ziviani, and N. Ziviani. Modeling performancedriven workload characterization of web search systems. In CIKM, 2006.
• [5] R. A. Baeza-Yates, A. Gionis, F. Junqueira, V. Murdock, V. Plachouras, and F. Silvestri. Design trade-offs for search engine caching. TWEB, 2(4), 2008.
• [6] C. Bonacic, C. Garcıa, M. Mar´ın, M. Prieto-Mat´ıas, and F. Tirado. Building efficient multi-threaded search nodes. In CIKM, 2010.
• [7] A. Z. Broder, D. Carmel,M. Herscovici, A. Soffer, and J. Y. Zien. Efficient query evaluation using a two-level retrieval process. In CIKM, 2003.
• [8] F. Cacheda, V. Carneiro, V. Plachouras, and I. Ounis. Performance analysis of distributed information retrieval architectures using an improved network simulation model. IPM, 43(1):204–224, 2007.
• [9] B. Cahoon, K. S. McKinley, and Z. Lu. Evaluating the performance of distributed architectures for information retrieval using a variety of workloads. ACM TOIS., 18:1–43, 2000.
• [10] A. Chowdhury and G. Pass. Operational requirements for scalable search systems. In CIKM, 2003.
• [11] T. R. Couvreur, R. N. Benzel, S. F. Miller, D. N. Zeitler, D. L. Lee, M. Singhal, N. G. Shivaratri, andW. Y. P. Wong. An analysis of performance and cost factors in searching large text databases using parallel search systems. JASIST, 45:443–464, 1994.
• [12] R. Fujimoto. Parallel discrete event simulation. Comm. ACM, 33(10):30–53, Oct. 1990.
• [13] R. Fujimoto. Parallel and Distributed Simulation Systems. Wiley Interscience, 2000.
• [14] Q. Gan and T. Suel. Improved techniques for result caching in web search engines. In WWW, 2009.
• [15] V. Gil-Costa, J. Lobos, A. Inostrosa-Psijas, and M. Mar´ın. Capacity planning for vertical search engines: An approach based on coloured petri nets. In Petri Nets, 2012.
• [16] S. Jafer and G. A. Wainer. A performance evaluation of the conservative devs protocol in parallel simulation of devs-based models. In SpringSim (TMS-DEVS), 2011.
• [17] K. Jensen and L. Kristensen. Coloured Petri Nets. Springer-Verlag Berlin Heidelberg, 2009.
• [18] G. Jiang, H. Chen, and K. Yoshihira. Profiling services for resource optimization and capacity planning in distributed systems. J. Cluster Computing, 2008.
• [19] S. Kounev, K. Bender, F. Brosig, N. Huber, and R. Okamoto. Automated simulation-based capacity planning for enterprise data fabrics. In SIMUTools, 2011.
• [20] W. Lin, Z. Liu, C. H. Xia, and L. Zhang. Optimal capacity allocation for web systems with end-to-end delay guarantees. Perform. Eval., 2005.
• [21] J. Liu and R. Rong. Hierarchical composite synchronization. In PADS, 2012.
• [22] X. Long and T. Suel. Three-level caching for efficient query processing in large web search engines. WWW, 2006.
• [23] B. Lu and A. Apon. Capacity Planning of a Commodity Cluster in an Academic Environment: A Case Study, 2008.
• [24] A. MacFarlane, J. McCann, and S. Robertson. Parallel search using partitioned inverted files. In SPIRE, 2000.
• [25] M. Marin. Time Warp on BSP computers. In ESM, 1998.
• [26] M. Marin, F. Ferrarotti, M. Mendoza, C. Gomez-Pantoja, and V. Gil-Costa. Location cache for web queries. In CIKM, 2009.
• [27] M. Marin and V. Gil-Costa. High-performance distributed inverted files. In CIKM, 2007.
• [28] M. Marin, V. Gil-Costa, and C. Gomez-Pantoja. New caching techniques for web search engines. In HPDC, 2010.
• [29] D. A. Menasce, V. A. Almeida, and L. W. Dowdy. Performance by Design: Computer Capacity Planning. Prentice Hall, 2004.
• [30] A. Moffat, W. Webber, J. Zobel, and R. Baeza-Yates. A pipelined architecture for distributed text query evaluation. Information Retrieval, 10(3):205–231, 2007.
• [31] R. Ozcan, I. S. Altingövde, B. B. Cambazoglu, F. P. Junqueira, and ¨O. Ulusoy. A five-level static cache architecture for web search engines. IPM, 48(5):828–840, 2012.
• [32] S. Tatikonda, F. Junqueira, B. B. Cambazoglu, and V. Plachouras. On efficient posting list intersection with multicore processors. In SIGIR, 2009.
• [33] L. Valiant. A bridging model for parallel computation. Comm. ACM, 33:103–111, Aug. 1990.
• [34] W. van der Aalst and C. Stahl. Modeling Business Processes A Petri Net-Oriented Approach. MIT Press, 2011.
• [35] H. Wang and K. C. Sevcik. Experiments with improved approximate mean value analysis algorithms. Perform. Eval., 39:189–206, 2000.
• [36] L. Wells. Performance analysis using CPN tools. In VALUETOOLS, 2006.
• [37] L. Wells, S. Christensen, L. M. Kristensen, and K. H. Mortensen. Simulation based performance analysis of web servers. In PNPM, 2001.
• [38] D. A. Zaitsev. Switched LAN simulation by Colored Petri Nets. Math. Comput. Simul., 65(3):245–249, 2004.
• [39] C. Zhang, R. N. Chang, C.-s. Perng, E. So, C. Tang, and T. Tao. An optimal capacity planning algorithm for provisioning cluster-based failure-resilient composite services. In SCC, 2009.
• [40] J. Zhang and T. Suel. Optimized inverted list assignment in distributed search engine architectures. IPDPS, 2007.

Identyfikatory

DOI

10.3233/FI-2014-1007