H*-tree/H*-cubing: 데이터 스트림의 OLAP를 위한 향상된 데이터 큐브 구조 및 큐빙 기법
H*-tree/H*-cubing: Improved Data Cube Structure and Cubing Method for OLAP on Data Stream
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
데이터 큐브는 다차원 데이터 분석 및 멀티레벨 데이터 분석에 많이 사용되고 있는 중요한 데이터 구조이다. 최근 데이터 스트림의 온라인 분석에 대한 수요가 증가하면서 스트림 큐브, Flow 큐브, S-큐브 등의 다양한 데이터 큐브 구조와 기법이 제안되었다. 그러나 기존 기법들은 데이터 큐브 생성 시 고비용이 요구되는 단점을 가지고 있어 효과적인 데이터 구조, 질의 방법 및 알고리즘에 대한 연구가 필요하다. 스트림 큐브 기법에서는 H-큐빙 기법을 사용하여 큐보이드를 선택하고, 계산된 셀들을 인기 패스에 있는 큐보이드들로 구성된 H-트리에 저장한다. 그러나 스트림 큐브 기법에서는 H-트리에 데이터를 비순차적으로 삽입하기 때문에 H-큐빙 기법을 사용하여 질의를 처리할 때 제한성을 갖고 있다. 본 논문에서는 데이터의 트리 구조의 각 층에 대한 인덱스를 구축하여 스트림 데이터에 대한 빠른 삽입 연산을 지원하는 H*-tree 구조와, popular-path에 존재하지 않는 큐보이드를 빨리 계산하여 스트림 데이터에 대한 빠른 애드 혹 질의 응답을 지원하는 H*-cubing 기법을 제안한다. 성능평가를 통하여 제안한 H*-tree 기법은 보다 적은 큐브 구축 시간을 지원하며, H*-cubing 기법이 stream cube 기법보다 빠른 애드 혹 질의 응답 시간을 소요하며, 보다 적은메모리를 사용함을 보여준다.
Abstract
Data cube plays an important role in multi-dimensional, multi-level data analysis. Meeting on-line analysis requirements of data stream, several cube structures have been proposed for OLAP on data stream, such as stream cube, flowcube, S-cube. Since it is costly to construct data cube and execute ad-hoc OLAP queries, more research works should be done considering efficient data structure, query method and algorithms. Stream cube uses H-cubing to compute selected cuboids and store the computed cells in an H-tree, which form the cuboids along popular-path. However, the H-tree layoutis disorderly and H-cubing method relies too much on popular path.In this paper, first, we propose H*-tree, an improved data structure, which makes the retrieval operation in tree structure more efficient. Second, we propose an improved cubing method, H*-cubing, with respect to computing the cuboids that cannot be retrieved along popular-path when an ad-hoc OLAP query is executed. H*-tree construction and H*-cubing algorithms are given. Performance study turns out that during the construction step, H*-tree outperforms H-tree with a more desirable trade-off between time and memory usage, and H*-cubing is better adapted to ad-hoc OLAP querieswith respect to the factors such as time and memory space.
참고문헌 (13)
- B. Babcock, "Models and Issues in Data Stream Systems", Proc. ACM Symposium on Principles of Database Systems (PODS), pp.1~16 (2002)
- "Providing OLAP (On-line Analytical Processing) to User-Analysts: An IT Mandate"[URL]
- J. Han, "Stream Cube: An Architecture for Multi-Dimensional Analysis of Data Streams", Distributed and Parallel Databases Journal, 18(2), pp.173~197 (2005)
- J. Gray, "Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab and Sub-Totals", Data Mining and Knowledge Discovery Journal, 1(1), pp.29~53 (1997)
- Y. Chen, "Online Analytical Processing Data stream: Is It Feasible?", ACM SIGMOD InternationalWorkshop on Research Issues on Data Mining and Knowledge Discovery (DMKD) (2002)
- J. Han, "Efficient computation of iceberg cubes with complex measures", Proc. ACM SIGMOD International Conference on Management of Data, pp.1~12 (2001)
- Y. Chen, "Multi-Dimensional Regression Analysis of Time-Series Data Streams", Proc. ACM VLDB International Conference on Very Large Data Bases, pp.323~334 (2002)
- M. Cho, "Answering Ad-hoc Aggregate Queries from Data Streams Using Prefix Aggregate Trees", Knowledge and Information Systems Journal, 12(3), pp.301~329 (2009)
- H. Gonzalez, "FlowCube: Constructing RFID FlowCubes for Multi-Dimensional Analysis of Commodity Flows", Proc. ACM VLDB International Conference on Very Large Data Bases, pp.834~845 (2006)
- H. Gonzalez, "Warehousing and Analysis of Massive RFID Data Sets", Proc. IEEE ICDE International Conference onData Engineering, pp.83~ (2006)
- E. Lo, "OLAP on Sequence Data", Proc. ACM SIGMOD International Conference on Management of Data, pp.649~660 (2008)
- Y. Cai, "MAIDS: Mining Alarming Incidents from Data Streams", Proc. ACM SIGMOD International Conference on Management of Data, pp.919~920 (2004)
- "NGSIM (Next Generation SIMulation)"[URL]