Dynamic pattern matching with multiple queries on large scale data streams

摘要

Similarity search in data streams is an important but challenging task in many practical areas where realtime pattern retrieval is required. Dynamic and fast updating data streams are often subject to outliers, noise and potential distortions in amplitude and time dimensions. Such conditions typically lead to a failure of existing pattern matching algorithms and to inability to retrieve required patterns from the stream. The main reason for such failures is the limitation of data normalization utilized in the majority of methods. Another reason is the lack of means to consider multiple examples of the same template to account for possible variations of the query signal. In this paper, we propose a dynamic normalization approach that allows bringing streaming signal subsequences to the scale of the query template. This significantly improves pattern retrieval capabilities, especially when sampling variance or time distortions are present. We further develop a pattern matching approach utilizing the proposed normalization mechanism and extend it for the case when multiple examples of a query template are available. Multiple synthetic and real data experiments demonstrate that this allows to considerably improve the pattern matching rate for distorted data streams, providing real time performance.