Predicting access to materialized methods by means of hidden Markov model

• Autorzy: Masewicz M. , Andrzejewski W. , Wrembel W. , Kró1ikowski Z.
• Języki publikacji: EN

Abstrakty

EN

Method materialization is a promising data access optimization technique for multiple applications, including, in particular object programming languages with persistence, object databases, distributed computing systems, object-relational data warehouses, multimedia data warehouses, and spatial data warehouses. A drawback of this technique is that the value of a materialized method becomes invalid when an object used for computing the value of the method is updated. As a consequence, a materialized value of the method has to be recomputed. The materialized value can be recomputed either immediately after updating the object or just before calling the method. The moment the method is recomputed bears a strong impact on the overall system performance. In this paper we propose a technique of predicting access to materialized methods and objects, for the purpose of selecting the most appropriate recomputation technique. The prediction technique is based on the Hidden Markov Model (HMM). The prediction technique was implemented and evaluated experimentally. Its performance characteristics were compared to: immediate recomputation, deferred recomputation, random recomputation, and to our previous prediction technique, called a PMAP.

Słowa kluczowe

EN

method materialization; hierarchical materialization; access prediction; hidden Markov model

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2009
• Tom: Vol. 38, no 1
• Strony: 127--152
• Opis fizyczny: Bibliogr. 44 poz., rys., wykr.

Twórcy

autor

Masewicz M.

autor

Andrzejewski W.

autor

Wrembel W.

autor

Kró1ikowski Z.

• Institute of Computing Science, Poznań University of Technology Poznań,

Bibliografia

• ALI, M.A., FERNANDES, A.A.A. and PATON, N. (2000) Incremental maintenance of materialized oql views. Proceedings of ACM Int. Workshop on Data Warehousing and OLAP (DOLAP). ACM Press, 41-48.
• ARIGON, A.M., TCHOUNIKINE, A. and MARYVONNE, M. (2006) Handling multiple points of view in a multimedia data warehouse. ACM Transactions on Multimedia Computing, Communications and Applications 2 (3), 199-218.
• BẾDARD, Y., RIVEST, S. and PROULX, M. J. (2007) Spatial on-line analytical processing (solap): Concepts, architectures and solutions from a geomatics engineering perspective. In: R. Wrembel and C. Koncilia, eds., Data Warehouses and OLAP: Concepts, Architectures and Solutions, 298-319. Idea Group Inc.
• BERTINO, E. (1991) Method precomputation in object-oriented databases. SIGOS Bulletin 12 (2,3), 199-212.
• BĘBEL, B. and WREMBEL, R. (2001) Hierarchical materialisation of methods in oo views: Design, maintenance, and experimental evaluation. Proceedings of ACM Int. Workshop on Data Warehousing and OLAP (DOLAP). ACM Press, 77-84.
• BUKHRES, O.A. and ELMAGARMID, A. (1995) Object-Oriented Multidatabase Systems: A Solution for Advanced Applications. Prentice Hall.
• CATTELL, R.G.G., BARRY, D., BERLER, M., EASTMAN, J., JORDAN, D., RUSSEL, C., SHADOW, O., STANIENDA, T., and VELEZ, F. (2000) Object Database Standard: ODMG 3.0. Morgan Kaufmann Publishers.
• CZEJDO, B., EDER, J., MORZY, T. and WREMBEL, R. (2001a) Design of a data warehouse over object-oriented and dynamically evolving data sources. DEXA Workshop on Parallel and Distributed Databases. IEEE Computer Society, 128-132.
• CZEJDO, B., EDER, J., MORZY, T. and WREMBEL, R. (2001b) Designing and implementing an object-relational data warehousing system. IFIP WG 6.1 International Working Conference on Distributed Applications and Interoperable Systems (DAIS). Kluwer, 311-316.
• DENG, X. and ALI, H. (2004) A hidden Markov model for gene function prediction from sequential expression data. Proceedings of IEEE Computational Systems Bioinformatics Conference (CSB). IEEE Computer Society, 670-671.
• DONGSHAN, X. and JUNYI, S. (2002) A new Markov model for web access prediction. Computing in Science and Engineering 4 (6), 34-39.
• DRTON, M., MARZBAN, C., GUTTORP, P. and SCHAEFER, J.T. (2003) A Markov chain model of tornadic activity. AMS Journals Online. Monthly Weather Review 131 (12), 2941-2953.
• EDER, J., FRANK, H. and LIEBHART, W. (1994) Optimization of object-oriented queries by inverse methods. Int. East/West Database Workshop. Workshops in Computing. Springer Verlag, 109-121.
• FANKHAUSER, P., GARDARIN,G., LOPEZ, M., MUNOZ, J. and TOMASIC, A. (1998) Experiences in federated databases: From iro-db to miro-web. Proceedings of Int. Conference on Very Large Data Bases (VLDB). Morgan Kaufmann, 655-658.
• GARDARIN, G., SHA, F. and TANG, Z.H. (1996) Calibrating the query optimizer cost model of iro-db, an object-oriented federated database system. Proceedings of Int. Conference on Very Large Data Bases (VLDB). Morgan Kaufman, 378-389.
• GOPALKRISHNAN, V., LI,Q. and KARLAPALEM, K. (2000) Efficient query processing with associated horizontal class partitioning in an object relational data warehousing environment. Proceedings of Int. Workshop on Design and Management of Data Warehouses (DMDW). CEUR-WS.org.
• GORAWSKI, M., and KAMIŃSKI, M. (2006) On-line balancing of horizontally-range-partitioned data in distributed spatial telemetric data warehouse. DEXA Workshops. IEEE Computer Society, 273-280.
• GORAWSKI, M. and MALCZOK, R. (2005) Updating aggregation tree in distributed spatial telemetric data warehouse. Euromicro Workshop on Parallel, Distributed and Network-Based Processing (PDF). IEEE Computer Society, 329-336.
• HUYNH, T.N., MANGISENGI, O. and TJOA, A.M. (2000) Metadata for object-relational data warehouse. Proceedings of Int. Workshop on Design and Management of Data Warehouses (DMDW). CEUR-WS.org.
• JEZIERSKI, J., MASEWICZ, M. and WREMBEL, R. (2004) Prototype system for method materialisation and maintenance in object-oriented databases. Proc. of ACM Symposium on Applied Computing (SAC). ACM Press, 1323-1327.
• JEZIERSKI, J., MASEWICZ, M., WREMBEL, R. and CZEJDO, B. (2003) Designing storage structures for management of materialised methods in object-oriented databases. Int. Conference on Object-Oriented Information Systems (OOIS). LNCS 2817, Springer Verlag, 202-213,
• JHINGRAN, A. (1991) Precomputation in a complex object environment. Proceedings of Int. Conference on Data Engineering (ICDE). IEEE Computer Society, 652-659.
• KANDASWAMY, V. (2006) Object relational data warehousing: Viewing linked data. Retrieved September 10, 2006, from http://www. datawarehouse. com/article/?articleid=3134.
• KAXIRAS, S. and YOUNG, C. (2000) Coherence communication prediction in shared-memory multiprocessors. Int. Symposium on High-Performance Computer Architecture (HPCA). IEEE Computer Society, 156-167.
• KEMPER, A., KILGER, C. and MOERKOTTE, G. (1994) Function materialization in object bases: Design, realization, and evaluation. KDE 6 (4), 587-608.
• KEMPER, A. and MOERKOTTE, G. (1994) Object-Oriented Database Management: Applications in Engineering and Computer Science. Prentice Hall.
• KHANNA, R. and LIU, H. (2006) System approach to intrusion detection using hidden Markov model. Proceedings of Int. Conference on Wireless Communications and Mobile Computing. ACM Press, 349-354.
• KIM, H.H. and PARK, S.S. (2003) Building a web-enabled multimedia data warehouse. Web and Communication Technologies and Internet-Related Social Issues (HSI). LNCS 2713, Springer Verlag, 594-600.
• KONOVALOV, A. (2002) Object-oriented data model for data warehouse. Proc. of East European Conference Advances in Databases and Information Systems (ADBIS). LNCS 2435, Springer Verlag, 319-325.
• KRATKY, M., STOLFA, S., SNASEL, V. and VONDRAK, I. (2005) Efficient searching in large inheritance hierarchies. Proceedings of Int. Conference on Database and Expert Systems Applications (DEXA). LNCS 3588, Springer Verlag, 940-952.
• KUNO, H.A. and RUNDENSTEINER, E.A. (1998) Incremental maintenance of materialized object-oriented views in multiview: Strategies and performance evaluation. IEEE Transactions on Knowledge and Data Engineering (TKDE) 10 (5), 768-792.
• LIU, Y. and TEITELBAUM, T. (1995) Caching intermediate results for program improvement. ACM SIGPLAN Symposium on Partial Evaluation and Semantics-Based Program Manipulation, ACM Press, 190-201.
• LIU, Y.A., STOLLER, S.D. and TEITELBAUM, T. (1998) Static caching for incremental computation. ACM Transactions on Programing Languages and Systems 20 (3), 546-585.
• LOOMIS, M.E.S. (1995) Object Database the Essentials. Addison-Wesley.
• LOOMIS, M.E.S. and CHAUDHRI, A.B. (1998) Object Databases in Practice. Prentice Hall.
• MASEWICZ, M., WREMBEL, R., STABNO, M. and STANISZEWSKI, R. (2006) Pmap: Framework to predicting method access patterns for materialized methods. Proceedings of Int. Conference on Advances in Information Systems (ADVIS). LNCS 4243, Springer Verlag, 14-323.
• MESSAOUD, B.R., BOUSSAID, O. and RABASEDA, S. (2004) A new olap aggregation based on the ahc technique. Proceedings of ACM Int. Workshop on Data Warehousing and OLAP (DOLAP). ACM Press, 65-72.
• OMG (2006) Corba. Retrieved November 10, 2006 from http://www.omg.org/technology/'documents/formal/corba_ 2. htm.
• ORAL, M. and KETTANI, O. (1989) A mathematical programming model for market share prediction. International Journal of Forecasting 5 (1), 59-68.
• PÂRIS, J.F., AMER, A. and LONG, D.D.E. (2003) A stochastic approach to file access prediction. Proceedings of the Int. Workshop on Storage Network Architecture and Parallel I/Os. ACM Press, 36-40.
• PUGH, W. and TEITELBAUM, T. (1989) Incremental computation via function caching. ACM Principles of Programming Languages (POPL). ACM Press, 315-328.
• RABINER, L.R. (1989) A tutorial on hidden Markov models and selected applications in speech recognition. Proc. of the IEEE 77 (2), 257-286.
• VERSANT (2006) Fast()objects t7. Retrieved May 30, 2006, from http://www.versant.com/developer/resources/fastobjects/overview.
• YU, S., ATLURI, V. and ADAM, N. (2006) Preview: Optimizing view materialization cost in spatial data warehouses. Proceedings of Int. Conference on Data Warehousing and Knowledge Discovery (DaWaK). LNCS 4081, Springer Verlag, 45-64,