MS-Index: Fast Top-k Subsequence Search for Multivariate Time Series under Euclidean Distance
Published in VLDB 2026 (Proceedings of the VLDB Endowment 19(2)), 2025
Modern applications frequently collect and analyze temporal data in the form of multivariate time series (MTS) - time series that contain multiple channels. A common task in this context is subsequence search, which involves identifying all MTS that contain subsequences highly similar to a query time series. In practical scenarios, not all channels of an MTS are relevant to every query. For instance, airplane sensors may gather data on a plethora of components and subsystems, but only a few of these are relevant to a specific query, such as identifying the cause of a malfunctioning landing gear, or a specific flight maneuver. Consequently, the relevant query channels are often specified at query time. In this work, we introduce the Multivariate Subsequence Index (MS-Index), a novel algorithm for nearest neighbor MTS subsequence search under Euclidean distance that supports ad-hoc selection of query channels. The algorithm is exact and demonstrates query performance that scales sublinearly to the number of query channels. We examine the properties of MS-Index with a thorough experimental evaluation over 34 datasets, and show that it outperforms the state-of-the-art one to two orders of magnitude for both raw and normalized subsequences.
Resources: camera-ready PDF, arXiv preprint, source code on GitHub (Java). The paper will be presented at VLDB 2026 in Boston. Our earlier, variable-length approach to the same problem is MULISSE.
Recommended citation: Jens E. d'Hondt, Teun Kortekaas, Odysseas Papapetrou, and Themis Palpanas. 2025. MS-Index: Fast Top-k Subsequence Search for Multivariate Time Series under Euclidean Distance. Proc. VLDB Endow. 19, 2, 99–112.
Download Paper