Fast Time Sequence Indexing for Arbitrary Norms

Fast indexing in time sequence databases for similarity searching has attracted a lot of research recently. Most of the proposals, however, typically centered around the Euclidean distance and its derivatives. We examine the problem of multi-modal similarity search in which users can choose the best one from multiple similarity models for their needs. In this paper, we present a novel and fast indexing scheme for time sequences, when the distance function is any of arbitrary L p norms (p = 1; 2; : : :;1). One feature of the proposed method is that only one index structure is needed for all L p norms including the popular Euclidean distance (L 2 norm). Our scheme achieves signicant speedups over the state of the art: extensive experiments on real and synthetic time sequences show that the proposed method is up to 10 times faster than the best competitor.