오토마타 기반 XML 스트림 필터링 시스템에서 질의 처리는 인 메모리 기반으로 수행된다. 이에 따라, 캐싱이 필터링 시스템의 전체 성능을 결정하는 주요 요인이 된다. 하지만, 해시 테이블로 구현되는 오토마타라는 질의 인덱스 특성상 인덱스에 대한 접근 패턴은 메모리 내의 임의 접근이 될 수 밖에 없으며 그로 인해 많은 캐시 미스를 유발한다. 이 논문에서는 XML 스트림 필터링 과정에 있어 캐시 히트율을 높이는 것을 목적으로 한다. 이를 위해 높은 적재율과 상수 탐색 시간을 보장할 수 있도록 Splash 해시 테이블과 SIMD 명령어에 의한 탐색 병렬화 기법을 적용하였다. 또한 질의 인덱스에서 빈번하게 자주 접근되는 일련의 상태 전이들을 찾아 해시테이블 내에 같은 버켓에 저장함으로써 보다 캐시 히트율을 높이는 방안을 고안하였다.
The automata-based XML stream filtration has achieved recognition as an efficient solution for processing many queries over XML streaming data simultaneously. However, the current implementations of the automata-style query indexes, i.e. hash tables, have been reported to involve frequent random memory accesses, causing many cache misses. We focus on improving the hash tables for the automata-based XML stream filtration in this paper. We first adopt the Splash hash table which guarantees the high load factor and the constant lookup time. We also provide two optimization techniques that further improve the overall throughput of the XML stream filtration: 1) SIMD CPU commands for parallelizing hash lookups and 2) identifying and grouping the state transitions which frequently occur together into the same bucket.
