Recently, as increasing amounts of information are stored, exchanged, and presented using eXtensible Markup Language (XML), it becomes more and more important to adequately process XML streams. Meanwhile, the multicore architecture has been the norm for all computing systems in recent years as it provides the CPU-level support of parallelism. However, existing algorithms for processing XML streams do not fully take advantage of the facility since they have not been devised to run in parallel. They also show a degraded processing performance as the number of user queries increases. In this thesis, we propose several methods to parallelize the finite state automata(FSA)-based XML stream processing technique efficiently. We transform a large collection of XPath expressions into multiple FSA-based query indexes and then process XML streams in parallel by virtue of index-level parallelism. Each core works only with its own query index so that no synchronization issue occurs while filtering XML streams with multiple path patterns given by users. Moreover, proposed algorithm permits query processing to share input scans and path solutions to reduce redundant processing and save computations and I/Os. We also present an in-memory MapReduce model that enables to process a large collection of twig pattern joins over XML streams simultaneously. Twig pattern joins in our approach are performed by multiple H/W threads in a shared and balanced way. In addition, we address performance issues in the in-memory MapReduce by providing a sophisticated run-time workload balancing scheme. It is achieved by computing the cost of each twig pattern join operation before actual joining. Extensive experiments show that our algorithm outperforms conventional algorithms by up to ten times on an 8-core CPU for processing 10 million XPath expressions over XML streams. Through extensive experiments with synthetic XML dataset, we prove that our parallel algorithms are efficient and scalable.
최근 지속적으로 발생하는 데이터 량이 폭발적으로 증가함에 따라 데이터 스트림의 처리 요구가 크게 증가하고 있다. 특히, XML은 대표적인 계층 구조 데이터로 온라인 상에서 웹이나 과학과 같은 다양한 분야의 데이터를 저장하고 교환하는데 많이 이용되고 있어, 이를 처리하기 위한 XML 스트림 처리 연구가 많은 관심을 끌고있다. 특히 XML 스트림 처리에서는 지속적으로 입력되는 스트림을 다수의 질의에 대해 빠르게 처리하는 것이 중요하다. 한편, 프로세서 구조는 클락 속도 향상에 따른 전력 소모와 열 발산의 증가라는 물리적 제약에 따라 한 칩 안에 여러 코어를 담는 다중 프로세서, 즉 멀티 코어의 형태로 진화하였다. 하지만, 기존 XML 스트림 처리 알고리즘들은 대부분 직렬 알고리즘들로 멀티 코어의 병렬성을 충분히 활용하지 못하는 문제가 있다. 또한, 기존 알고리즘들은 사용자 질의 수의 증가에 따라 처리 성능이 저하되는 문제를 갖는다. 본 학위 논문에서는 XML 스트림 처리의 병렬화 문제를 해결하기 위하여 멀티 코어를 활용한 오토마타 기반 XML 스트림 병렬처리 기법을 제안한다. 제안하는 기법은 우선 단일 경로 패턴을 병렬처리하고 이 결과를 사용해 가지 패턴 조인 연산을 병렬처리 한다. 첫 번째로 단일 경로 패턴 처리는 인덱스-기반 병렬화 기법을 통해 다수의 사용자 질의들을 여러 개의 오토마타 질의 인덱스로 구축하여 각 코어에 분할하고, 같은 스트림에 대해 서로 다른 질의 처리를 수행한다. 인덱스 분할을 통해 각 코어 마다 자신만의 질의 인덱스를 이용하여 스트림 처리를 수행하므로, 코어 간의 동기화 문제가 발생하지 않는다. 또한, 제안하는 기법은 입력으로 주어진 데이터를 읽어 들이는 과정을 공유할 수 있으며, 질의들 사이에서 공통되는 단일 경로 패턴들의 결과들을 서로 공유할 수 있어 많은 입출력 비용을 절감 할 수 있다. 두번째로 인메모리 맵리듀스 모델을 이용하여 다수의 가지 패턴 조인 연산을 수행한다. 제안하는 방법은 기본적으로 맵리듀스 모델의 패러다임에 따라 대용량의 데이터를 분할해 서로 다른 노드에서 분할된 데이터를 처리한다. 또한, 가지 조인 연산을 동적으로 각 코어에 균등 분배하기 위한 기법을 제안한다. 단일 경로 패턴 작업을 통해 얻은 조인 연산의 비용을 이용하여 리듀서들의 연산 비용을 계산해 작업량을 균등분배한다. 수록된 다양한 실험 결과를 통해, 제안하는 방법은 1,000만개 이상의 질의에서도 기존 알고리즘에 비해 8- 코어 환경에서 약 10배 정도의 성능 증가를 보였다. 이러한 결과들은 제안하는 알고리즘이 멀티 코어를 활용하여 다수의 가지 패턴 질의에 대해 XML 스트림을 처리하는 데 있어 효과적이며 효율적임을 증명한다.
