Nordic Journal of Computing Bibliography

Béla Bollobás, Gautam Das, Dimitrios Gunopulos, and Heikki Mannila. Time-Series Similarity Problems and Well-Separated Geometric Sets. Nordic Journal of Computing, 8(4):409-423, Winter 2001.

Given a pair of nonidentical complex objects, defining (and determining) how similar they are to each other is a nontrivial problem. In data mining applications, one frequently needs to determine the similarity between two time series. We analyze a model of time-series similarity that allows outliers, different scaling functions, and variable sampling rates. We present several deterministic and randomized algorithms for computing this notion of similarity. The algorithms are based on nontrivial tools and methods from computational geometry. In particular, we use properties of families of well-separated geometric sets. The randomized algorithm has provably good performance and also works extremely efficiently in practice.

Categories and Subject Descriptors: H.2.8 [Database Management]: Database Applications; I.3.5 [Computer Graphics]: Computational Geometry and Object Modeling

Additional Key Words and Phrases: data mining, time-series, similarity measures, geometric sets

Selected references


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database