Approximate string matching for large-scale event processing

Event processing is an important technology to detect what happened in the real world from a large amount of sensor data. This article is trying to find a suitable method for event processing with huge data. The authors formalize event processing as a problem of approximate string matching and evaluate the processing time of the two algorithms for the problem, the shift-add algorithm and the FFT-based algorithm. The shift-add algorithm is efficient for matching with a short string, however the processing time is proportional to the length of the string. On the other hand, the processing time of the FFT-based algorithm depends on the logarithm of the length of the string. Their experimental result with a common computer shows that the FFT-based algorithm is faster than the shift-add algorithm for a string longer than about 4,000.