Sublinear querying of realistic timeseries and its application to human motion

This paper introduces a novel hashing algorithm for large timeseries databases, which can improve the querying of human motion. Timeseries that represent human motion come from many sources, in particular, videos and motion capture systems. Motion-related timeseries have features which are not commonly present in traditional types of vector data and that create additional indexing challenges: high and variable dimensionality, no Euclidean distance without normalization, and a metric space not fully defined. New techniques are needed to index motion-related timeseries. The algorithm that we present in this paper generalizes the dot product operator to hash timeseries of variable dimensionality without assuming constant dimensionality or requiring dimensionality normalization, unlike other approaches. By avoiding normalization, our hashing algorithm preserves more timeseries information and improves retrieval accuracy, and by hashing achieves sublinear computation time for most searches. Additionally, we show how to further improve the hashing by partitioning the search space using timeseries within the index. This paper also reports the results of experiments that show that the algorithm performs well in the querying of real human motion datasets.