Exploiting SIMD-Ified Bit-Parallelism for High-Performance Complex Event Matching

Tao Qiu

doi:10.1109/TKDE.2025.3639419

Exploiting SIMD-Ified Bit-Parallelism for High-Performance Complex Event Matching

2025-12-02

0

PRE

AI

DOI：10.1109/TKDE.2025.3639419

Original

Original request for help

Save

Abstract

En 中文

The advent of Single Instruction Multiple Data (SIMD) instructions in modern processors has revolutionized data processing by enabling simultaneous computation across multiple data elements. While database systems have extensively adopted SIMD for traditional operations, its potential for complex event pattern matching remains largely unexplored. This paper presents a novel approach that bridges this gap through bit-parallel processing enhanced with AVX-512 vectorization. Our approach encodes event streams into compact bit sequences, where each bit corresponds to a time slice, and an event’s presence is marked by a 1-bit when its timestamp falls within the respective slice. This representation enables the formulation of bit-parallel operations that natively enforce complex event constraints, including temporal window requirements and event ordering relationships. We develop a family of bit-parallel algorithms that leverage this representation for continuous event matching, and further optimize their performance through SIMD vectorization (AVX-512 instructions) to exploit modern hardware parallelism. Experimental evaluations on both real-world and synthetic datasets demonstrate the superiority of our method, achieving at least 35.7x improvement in query efficiency compared to state-of-the-art alternatives.

Keywords:

Complex event matching

bit-parallel algorithms

event streams

SIMD

Exploiting SIMD-Ified Bit-Parallelism for High-Performance Complex Event Matching

Abstract

Journal

Organization