Efficient subspace search in data streams. Issue 97 (March 2021)

• Record Type: Journal Article
• Authors: Fouché, Edouard; Kalinke, Florian; Böhm, Klemens
• Is Part Of: Information systems. Issue 97(2021)
• Publication Date: 2021-03
• Subjects: Subspace search -- Data stream monitoring -- Outlier detection; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2020.101705
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: In the real world, data streams are ubiquitous — think of network traffic or sensor data. Mining patterns, e.g., outliers or clusters, from such data must take place in real time. This is challenging because (1) streams often have high dimensionality, and (2) the data characteristics may change over time. Existing approaches tend to focus on only one aspect, either high dimensionality or the specifics of the streaming setting. For static data, a common approach to deal with high dimensionality – known as subspace search – extracts low-dimensional, 'interesting' projections (subspaces), in which patterns are easier to find. In this paper, we address both Challenge (1) and (2) by generalising subspace search to data streams. Our approach, Streaming Greedy Maximum Random Deviation (SGMRD), monitors interesting subspaces in high-dimensional data streams. It leverages novel multivariate dependency estimators and monitoring techniques based on bandit theory. We show that the benefits of SGMRD are twofold: (i) It monitors subspaces efficiently, and (ii) this improves the results of downstream data mining tasks, such as outlier detection. Our experiments, performed against synthetic and real-world data, demonstrate that SGMRD outperforms its competitors by a large margin. Highlights: A general framework, SGMRD, to monitor subspaces in high-dimensional data streams. SGMRD leverages multivariate dependency estimators and bandit algorithms. SGMRD is efficient and helps with downstream mining tasks, e.g., outlier detection. The experiments show the superiority of SGMRD w.r.t. the existing work.