Improving OLAP Analysis of Multidimensional Data Streams via Efficient Compression Techniques

Introduction

Data Stream Management Systems (DSMS) have captured the attention of large communities of both academic and industrial researchers. Data streams pose novel and previously-unrecognized research challenges due to the fact that traditional DBMS (Henzinger, Raghavan & Rajagopalan, 1998, Cortes, Fisher, Pregibon, Rogers & Smith, 2000), which are based on an exact and detailed representation of information, are not suitable in this context, as the whole information carried by streaming data cannot be stored within a bounded storage space (Babcock, Babu, Datar, Motwani & Widom, 2002). From this practical evidence, a plethora of recent research initiatives have been focused on the problem of efficiently representing, querying and mining data streams (Babu & Widom, 2001,Yao & Gehrke, 2003, Acharya, Gibbons, Poosala, & Ramaswamy, 1999, Avnur & Hellerstein, 2000).

Sensor networks (Bonnet, Gehrke & Seshadri, 2000, Bonnet, Gehrke & Seshadri, 2001) represent a leading case of data stream sources coming from real-life application scenarios. Sensors are non-reactive elements which are used to monitor real-life phenomena, such as live weather conditions, network traffic etc. They are usually organized into networks where their readings are transmitted using low level protocols (Gehrke & Madden, 2004, Madden & Franklin, 2002, Madden, Franklin, & Hellerstein, 2002, Madden, Szewczyk, Franklin & Culler, 2002). Under a broader vision, sensor networks represent a non-traditional source of information, as readings generated by sensors flow continuously, leading to an infinite, memory-unbounded stream of data.

A relevant problem in dealing with data streams consists in the fact that they are intrinsically multi-level and multidimensional in nature (Cai, Clutterx, Papex, Han, Welgex & Auvilx, 2004; Han, Chen, Dong, Pei, Wah, Wang & Cai, 2005), hence they require to be analyzed by means of a multi-level and a multi-resolution (analysis) model accordingly. Furthermore, it is a matter of fact to note that enormous data flows generated by a collection of stream sources like sensors naturally require to be processed by means of advanced analysis/mining models, beyond traditional solutions provided by primitive SQL-based DBMS interfaces. Consider, for instance, the application scenario drawn by a Supply Chain Management System (SCMS) (Gonzalez, Han, Li & Klabjan, 2006), which can be intended as a sort of sensor network distributed over a wide geographical area. Here, due to the characteristics of the particular application domain, data embedded in streams generated by supply providers (i.e., the sensors, in this case) are intrinsically multidimensional, and, in addition to this, correlated in nature. In more detail, multidimensionality of data is dictated by the fact that, in a typical supply chain scenario, the domain model is captured by several attributes like store region, warehouse region, location, product category, and so forth. Here, hierarchies of data naturally arise, as real-life data produced and processed by knowledge management processes are typically organized into weak or strong hierarchical relationships (e.g., StoreCountry → StoreRegion → Store). Correlation of data is instead due to the fact that, for instance, stock quotations strictly depend on the actual market trend, and market prices strictly depend on the actual capability of suppliers in delivering products timely. The same happens with the monitoring of environmental parameters, in the context of environmental sensor networks. Here, geographical coordinates naturally define a multidimensional space, and, consequentially, a multidimensional data model, very often enriched by additional metadata attributes, like in Geographical Information Systems (GIS). For what regards correlation of data, it is a matter of fact to note that temperature, pressure, and humidity of a given geographical area are very often correlated, even highly correlated.