Formal model of time point-based sequential data for OLAP-like analysis

• Autorzy: Bębel B. , Morzy T. , Królikowski Z. , Wrembel R.

Identyfikatory

DOI

10.2478/bpasts-2014-0032

• Języki publikacji: EN

Abstrakty

EN

Numerous nowadays applications generate huge sets of data, whose natural feature is order, e.g,. sensor installations, RFID devices, workflow systems, Website monitors, health care applications. By analyzing the data and their order dependencies one can acquire new knowledge. However, nowadays commercial BI technologies and research prototypes allow to analyze mostly set oriented data, neglecting their order (sequential) dependencies. Few approaches to analyzing data of sequential nature have been proposed so far and all of them lack a comprehensive data model being able to represent and analyze sequential dependencies. In this paper, we propose a formal model for time point-based sequential data. The main elements of this model include an event and a sequence of events. Measures are associated with events and sequences. Measures are analyzed in the context set up by dimensions in an OLAP-like manner by means of the set of operations. The operations in our model are categorized as: operations on sequences, on dimensions, general operations, and analytical functions.

Słowa kluczowe

EN

OLAP; sequential data; formal model

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2014
• Tom: Vol. 62, nr 2
• Strony: 331--340
• Opis fizyczny: Bibliogr. 35 poz., tab., rys.

Twórcy

autor

Bębel B.

• Institute of Computing Science, Poznan University of Technology, 3a Piotrowo St., 90-965 Poznań, Poland

autor

Morzy T.

• Institute of Computing Science, Poznan University of Technology, 3a Piotrowo St., 90-965 Poznań, Poland

autor

Królikowski Z.

• Institute of Computing Science, Poznan University of Technology, 3a Piotrowo St., 90-965 Poznań, Poland

autor

Wrembel R.

• Institute of Computing Science, Poznan University of Technology, 3a Piotrowo St., 90-965 Poznań, Poland

Bibliografia

• [1] S. Chaudhuri, U. Dayal, and V. Narasayya, “An overview of business intelligence technology”, Communications ACM 54 (8), 88–98 (2011).
• [2] H. Gonzalez, J. Han, and X. Li, “FlowCube: constructing RFID flowcubes for multi-dimensional analysis of commodity flows”, Proc. Int. Conf. on Very Large Data Bases (VLDB) 1, 834–845 (2006).
• [3] “Smart card alliance latin america & the caribbean”, http://latinamerica.smartcardalliance.org/ (2012).
• [4] “Smart card alliance”, http://www.smartcardalliance.org (2012).
• [5] “Octopus card”, http://hong-kong-travel.org/Octopus/(2012).
• [6] E. Lo, B. Kao, W.-S. Ho, S.D. Lee, C.K. Chui, and D.W. Cheung, “OLAP on sequence data”, Proc. ACM SIGMOD Int. Conf. on Management Data 1, 649–660 (2008).
• [7] M. Gorawski, P. Marks, and M. Gorawski, “Collecting data streams from a distributed radio-based measurement system”, Lecture Notes in Computer Science 4947, 702–705 (2008).
• [8] M. Gorawski, “Multiversion spatio-temporal telemetric data warehouse”, ADBIS Workshops 1, 63–70 (2009).
• [9] M. Gorawski, “Extended cascaded star schema and ECOLAP operations for spatial data warehouse”, Lecture Notes in Computer Science 5788, 251–259 (2009).
• [10] S. Szczepański, M. Wójcikowski, B. Pankiewicz, M. Kłosowski, and R. Żaglewski, “FPGA and ASIC implementation of the algorithm for traffic monitoring in urban areas”, Bull. Pol. Ac.: Tech. 59 (2), 137–140 (2011).
• [11] Z. Opilski, G. Konieczny, T. Pustelny, A. Gacek, R. Kustosz, and M. Gawlikowski, “Noninvasive acoustic blood volume measurement system for the POLVAD prosthesis”, Bull. Pol. Ac.: Tech. 59 (4), 429–433 (2011).
• [12] C. Dyreson, F. Grandi, W. K¨afer, N. Kline, N. Lorentzos, Y. Mitsopoulos, A. Montanari, D. Nonen, E. Peressi, B. Pernici, J.F. Roddick, N.L. Sarda, M.R. Scalas, A. Segev, R.T. Snodgrass, M.D. Soo, A. Tansel, P. Tiberio, and G. Wiederhold, “A consensus glossary of temporal database concepts”, SIGMOD Record 23 (1), 52–64 (1994).
• [13] F.M¨orchen, “Unsupervised pattern mining from symbolic temporal data”, SIGKDD Explor. Newsl. 9 (1), 41–55 (2007).
• [14] B. Bębel, P. Krzyżagórski, M. Kujawa, M. Morzy, and T. Morzy, “Formal model for sequential OLAP”, Information Technology and its Applications 1, 1–11, ISBN 978-83-89529-82-4 (2011).
• [15] C.K. Chui, B. Kao, E. Lo, and D. Cheung, “S-OLAP: an OLAP system for analyzing sequence data”, Proc. ACM SIGMOD Int. Conf. on Management of Data 1, 1131–1134 (2010).
• [16] C.K. Chui, E. Lo, B. Kao, and W.-S. Ho, “Supporting ranking pattern-based aggregate queries in sequence data cubes”, Proc. ACM Conf. on Information and Knowledge Management (CIKM) 1, 997–1006 (2009).
• [17] M. Liu, E. Rundensteiner, K. Greenfield, C. Gupta, S. Wang, I. Ari, and A. Mehta, “E-cube: multi-dimensional event sequence analysis using hierarchical pattern query sharing”, Proc. ACM SIGMOD Int. Conf. on Management of Data 1, 889–900 (2011).
• [18] H. Gonzalez, J. Han, X. Li, and D. Klabjan, “Warehousing and analyzing massive RFID data sets”, Proc. Int. Conf. on Data Engineering (ICDE) 1, 83–92 (006).
• [19] B. Bebel, M. Morzy, T. Morzy, Z. Królikowski, and R. Wrembel, “OLAP-Like analysis of time point-based sequential data”, ER Workshops Lecture Notes in Computer Science 7518, 153–161 (2012).
• [20] A.P. Buchmann and B. Koldehofe, “Complex event processing”, Information Technology 51 (5), 241–242 (2009).
• [21] M. K. Chandy, “Event-driven applications: costs, benefits and design approaches”, http://www.infospheres.caltech.edu/node/38 (2012).
• [22] A.J. Demers, J. Gehrke, B. Panda, M. Riedewald, V. Sharma, and W.M. White, “Cayuga: a general purpose event monitoring system”, CIDR 1, 412–422 (2007).
• [23] E. Wu, Y. Diao, and S. Rizvi, “High-performance complex event processing over streams”, Proc. ACM SIGMOD Int. Conf. on Management of Data 1, 407–418 (2006).
• [24] J. Han, Y. Chen, G. Dong, J. Pei, B.W. Wah, J. Wang, and Y.D. Cai, “Stream cube: an architecture for multi-dimensional analysis of data streams”, Distributed and Parallel Databases 18 (2), 173–197 (2005).
• [25] R. Ramakrishnan, D. Donjerkovic, A. Ranganathan, K.S. Beyer, and M. Krishnaprasad, “SRQL: Sorted Relational Query Language”, Proc. Int. Conf. on Scientific and Statistical Database Management (SSDBM) 1, 84–95 (1998).
• [26] P. Seshadri, M. Livny, and R. Ramakrishnan, “Sequence query processing”, SIGMOD Record 23 (2), 430–441 (1994).
• [27] P. Seshadri, M. Livny, and R. Ramakrishnan, “The design and implementation of a sequence database system”, Proc. Int. Conf. on Very Large Data Bases (VLDB) 1, 99–110 (1996).
• [28] R. Sadri, C. Zaniolo, A. Zarkesh, and J. Adibi, “Optimization of sequence queries in database systems”, Proc. ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS) 1, 71–81(2001).
• [29] S.S. Chawathe, V. Krishnamurthy, S. Ramachandran, and S. Sarma, “Managing RFID data”, Proc. Int. Conf. on Very Large Data Bases (VLDB) 1, 1189–1195 (2004).
• [30] J.-W. Han, J. Pei, and X.-F. Yan, “From sequential pattern mining to structured pattern mining: a pattern-growth approach”, J. Comput. Sci. Technol. 19 (3), 257–279 (2004).
• [31] N.R. Mabroukeh and C.I. Ezeife, “A taxonomy of sequential pattern mining algorithms”, ACM Comput. Surv. 43 (1), 3:1–3:41 (2010).
• [32] F. Masseglia, M. Teisseire, and P. Poncelet, “Sequential pattern mining”, in Encyclopedia of Data Warehousing and Mining, pp. 1800–1805, IGI Global, London, 2009.
• [33] A.Marascu and F.Masseglia, “Mining sequential patterns from data streams: a centroid approach”, J. Intell. Inf. Syst. 27 (3), 291–307 (2006).
• [34] L.F. Mendes, B. Ding, and J. Han, “Stream sequential pattern mining with precise error bounds”, Proc. IEEE Int. Conf. on Data Mining (ICDM) 1, 941–946 (2008).
• [35] Q. Zheng, K. Xu, and S. Ma, “When to update the sequential patterns of stream data?”, Proc. Pacific-Asia Conf. on Advances in Knowledge Discovery and Data Mining (PAKDD) 1, 545–550 (2003).