H*-tree/H*-cubing: 데이터 스트림의 OLAP를 위한 향상된 데이터 큐브 구조 및 큐빙 기법

데이터 큐브는 다차원 데이터 분석 및 멀티레벨 데이터 분석에 많이 사용되고 있는 중요한 데이터 구조이다. 최근 데이터 스트림의 온라인 분석에 대한 수요가 증가하면서 스트림 큐브, Flow 큐브, S-큐브 등의 다양한 데이터 큐브 구조와 기법이 제안되었다. 그러나 기존 기법들은 데이터 큐브 생성 시 고비용이 요구되는 단점을 가지고 있어 효과적인 데이터 구조, 질의 방법 및 알고리즘에 대한 연구가 필요하다. 스트림 큐브 기법에서는 H-큐빙 기법을 사용하여 큐보이드를 선택하고, 계산된 셀들을 인기 패스에 있는 큐보이드들로 구성된 H-트리에 저장한다. 그러나 스트림 큐브 기법에서는 H-트리에 데이터를 비순차적으로 삽입하기 때문에 H-큐빙 기법을 사용하여 질의를 처리할 때 제한성을 갖고 있다. 본 논문에서는 데이터의 트리 구조의 각 층에 대한 인덱스를 구축하여 스트림 데이터에 대한 빠른 삽입 연산을 지원하는 H*-tree 구조와, popular-path에 존재하지 않는 큐보이드를 빨리 계산하여 스트림 데이터에 대한 빠른 애드 혹 질의 응답을 지원하는 H*-cubing 기법을 제안한 다. 성능평가를 통하여 제안한 H*-tree 기법은 보다 적은 큐브 구축 시간을 지원하며, H*-cubing 기법이 stream cube 기법보다 빠른 애드 혹 질의 응답 시간을 소요하며, 보다 적은메모리를 사용함을 보여준다.