Using triangle inequality to efficiently process continuous queries on high-dimensional streaming time series

摘要

In many applications, it is important to quickly find, from a database of patterns, the nearest neighbors of high-dimensional query points that come into the system in a streaming form. Treating each query point as a separate one is inefficient. Consecutive query points are often neighbors in the high-dimensional space, and intermediate results in the processing of one query should help the processing of the next. This paper extends the KD tree with triangle inequality to deal with high-dimensional streaming time series. More specifically, the distances calculated for earlier query points (to patterns) are used to filter out patterns that are not possible to be the nearest neighbor of the current one. Experiments show that this extension works well.