On efficiently searching trajectories and archival data for historical similarities

Reza Sherkat, Davood RafieiPVLDB 2008 · DOI · OpenReview

TL;DR

This paper introduces a novel approach for efficiently searching large collections of historical data (time series or trajectories), especially when dealing with high-dimensional data (more than 3 dimensions). They propose two summary techniques, HSums and MBR approximations, that allow for faster filtering and retrieval of similar historical records, outperforming existing methods in both speed and scalability.

What Problem Does This Paper Address?

The core challenge this paper tackles is the efficient retrieval of similar historical data, which can be represented as d-dimensional time series or trajectories. While existing methods work well for low-dimensional data (d ≤ 3), they struggle to scale to higher dimensions due to the exponential increase in complexity. This is a significant problem because many real-world applications, such as analyzing financial data, medical records, or environmental sensor readings, involve high-dimensional histories. The paper aims to bridge this gap by developing techniques that can efficiently handle these complex, high-dimensional datasets.

Methods

The authors propose a two-tiered summarization approach:

  • HSums (History Summaries): These are compact, one-dimensional time series representations of the original histories. They are derived using a "kernel function" that maps each d-dimensional point to a single real number. A key property of these HSums is that distances calculated between HSums provide a lower bound for the distances between the original histories. This allows for efficient pruning of dissimilar histories. Furthermore, HSums can be indexed using existing time-series indexing techniques, enabling fast initial filtering.
  • uDAE-based MBR Approximations (Minimum Bounding hyper-Rectangles): For histories that pass the initial HSum filtering, a finer level of approximation is used. This involves segmenting the history and representing each segment with a Minimum Bounding hyper-Rectangle (MBR). The novelty here lies in the optimization criterion: instead of minimizing the total volume of MBRs (a common approach), they minimize the "upper bound of distance approximation error" (uDAE). This criterion is designed to be query-independent and aims to provide tighter bounds for similarity calculations, further reducing false positives. They also introduce adaptive splitting strategies (Variable Splitting and Superimposed Encoding) to further optimize MBR representation, especially for correlated or varying dimensional changes.

Datasets

The paper evaluates their methods on a combination of real and synthetic datasets:

  • Real Datasets:
    • ASL, Marine, VT1, VT2, Word, Web: These are described as 2-4 dimensional histories, with the "Web" dataset being 17-dimensional. The "Web" dataset is constructed from Internet Archive data of web pages, representing their content overlap with categories as a 17-dimensional history.
  • UCR Time Series Archive: A collection of 41 real datasets, each containing 50 time series of length 512.
  • Synthetic Datasets:
    • Constructed from the "Web" dataset by applying operations like permutation, time shifting, compression, and insertion to generate larger datasets with varying numbers of histories (1k, 2k, 4k, 8k) to test scalability.

Key Insights and Ideas

  • Lower-Bounding with HSums is Crucial: The core idea that distances between summarized histories (HSums) provide a lower bound for the original distances is fundamental. This allows for efficient pruning without missing any relevant results.
  • uDAE Outperforms Volume for Pruning: Minimizing the upper bound of distance approximation error (uDAE) leads to more effective pruning than minimizing MBR volume, especially in high-dimensional or sparse data where dimensions might not change uniformly.
  • Adaptive Splitting for High Dimensions: For high-dimensional data, fixed splitting policies are often inefficient. Adaptive strategies like Variable Splitting and Superimposed Encoding can better allocate resources (MBRs) to dimensions that exhibit more significant changes or correlations, leading to improved approximations.
  • Scalability for High Dimensions: The proposed methods demonstrate significant improvements in efficiency and scalability for high-dimensional histories, a gap not adequately addressed by prior work.

Key Results

  • Improved Efficiency and Scalability: The proposed HSum and uDAE-based MBR approximation methods significantly outperform existing approaches (like VHGK) in terms of pruning power, running time, and scalability, especially for 17-dimensional histories.
  • Faster Query Processing: Experiments show that the algorithm achieves strong pruning power, leading to much faster query processing times compared to linear scans, even for large datasets.
  • Tighter Lower Bounds: uDAE-based splitting consistently provides tighter lower bounds for distance calculations compared to volume-based splitting, which is crucial for effective pruning.
  • Adaptive Splitting Benefits: Adaptive splitting techniques (VS and SE) showed notable uDAE reduction (up to 7.2% for SE on the Web dataset) and improved tightness of lower bounds (up to 25% for uDAE-based fixed splitting and 33% for volume-based fixed splitting).

Limitations and Future Work

  • Computational Cost of Optimal Splitting: While uDAE provides a better criterion, finding the truly optimal splitting for uDAE can be computationally intensive, especially for very high dimensions. The paper uses heuristics and dynamic programming to mitigate this.
  • Kernel Function Choice: The effectiveness of HSums depends on the choice of the kernel function. While they identify a class of suitable kernels, selecting the optimal one for a specific dataset might require further investigation.
  • Future Work:
    • Data Mining Tasks: Exploring how HSum and uDAE approximations can improve efficiency in other data mining tasks like clustering and pattern recognition.
  • Generalizing to Other Data Types: Extending the HSum and uDAE concepts to other types of historical data, such as time-stamped market-basket data.
  • Subspace Analysis: Investigating how to support history summaries extracted from a subspace of points, which could be beneficial for very high-dimensional data.

Summary updated

BibTeX
@article{sherkat2008efficiently,
  author = {Reza Sherkat and Davood Rafiei},
  title = {{On efficiently searching trajectories and archival data for historical similarities}},
  journal = {Proc. VLDB Endow.},
  year = {2008},
  doi = {10.14778/1453856.1453953},
}
Figure