Fast Concept Drift Detection Exploiting Product Quantization

To analyze data streams with machine learning, it is significant to detect concept drifts that deteriorate the performance of the classification model as the data characteristics change over time. IBDD (Image-Based Drift Detector) is known as one of the fastest unsupervised drift detectors for high-dimensional multivariate data streams. It expresses a sliding window as an image and detect drifts from the difference between the newest image presenting the current window and the reference image that corresponds to the initial window. Our research proposes a new algorithm PQIBDD that runs much faster than IBDD almost without affecting the classification accuracy. PQIBDD evaluates the similarity between the two images faster than IBDD by incorporating the PQ (Product Quantization) method that is originally designed for Approximate Near-Neighbor search in the Euclidean space. In addition, we equip PQIBDD an option that mitigates a drawback of IBDD to over-detect drifts by using two kinds of image distances jointly.