© 2019, Springer Japan KK, part of Springer Nature. This paper investigates the lead–lag relationships in high-frequency data. We propose multinomial dynamic time warping (MDTW) that deals with non-synchronous observation, vast data, and time-varying lead–lag. MDTW directly estimates the lead–lags without lag candidates. Its computational complexity is linear with respect to the number of observation and it does not depend on the number of lag candidates. The experiments adopting artificial data and market data illustrate the effectiveness of our method compared to the existing methods.