GESS: a scalable similarity-join algorithm for mining large data sets in high dimensional spaces

Jens-Peter Dittrich, Bernhard SeegerKDD 2001 · DOI

TL;DR

This paper introduces GESS, a novel algorithm for efficiently performing similarity joins on high-dimensional datasets. GESS significantly reduces computational costs and memory requirements compared to existing methods like MSJ by employing a controlled data replication strategy and an efficient duplicate removal technique.

What Problem Does This Paper Address?

The paper tackles the challenge of performing "similarity joins" on large, high-dimensional datasets. Imagine you have two massive collections of complex objects, like images or documents, each represented by a "feature vector" in a space with many dimensions. A similarity join aims to find all pairs of objects, one from each collection, whose feature vectors are "close" to each other, meaning their distance is within a specified threshold (ε). This operation is fundamental for tasks like content-based retrieval, clustering, and data mining.

Existing algorithms, such as the Multidimensional-Spatial Join (MSJ), struggle with high-dimensional data due to excessive CPU usage (from too many distance calculations), high memory demands, and significant I/O costs. These limitations make them impractical for the massive datasets common in real-world applications.

Methods

GESS introduces a new approach called "Generic External Space Sweep" (GESS). Its core innovation lies in a controlled data replication strategy. Instead of avoiding replication entirely (like MSJ), GESS strategically replicates data to reduce the number of expensive distance computations. This replication is managed by a flexible "replication engine."

To handle the duplicates introduced by replication, GESS employs an inexpensive and efficient Reference Point Method (RPM) for duplicate removal. RPM cleverly uses a "reference point" within the intersection of two hypercubes to ensure each valid join result is reported exactly once.

GESS also proposes a new I/O strategy that aims to be more efficient than MSJ, even without replication. The paper also introduces a cost model to analyze the trade-offs between replication rate and computational savings.

Datasets

The paper evaluates GESS using both synthetic and real-world datasets.

  • Synthetic Data: Uniformly distributed hypercubes were generated to test the analytical models and simulations.
  • Real-world Data:
    • CAD: Fourier-vectors of CAD-parts.
  • CAD10: A sample of the CAD dataset.

The paper does not introduce new benchmark datasets but uses existing ones to compare GESS against MSJ.

Key Insights and Ideas

  • Replication is not always bad: While MSJ avoids replication to minimize duplicates, GESS shows that a controlled amount of replication can drastically reduce computational cost and memory usage.
  • The "curse of dimensionality" is real, but manageable: High dimensionality makes distance calculations and indexing difficult. GESS's approach of strategic replication and efficient duplicate handling offers a way to mitigate this.
  • Duplicate removal can be cheap: The Reference Point Method (RPM) is a clever, low-overhead technique that avoids costly sorting or hashing for duplicate elimination.
  • I/O efficiency matters: GESS's I/O strategy is shown to be superior to MSJ, offering a significant improvement independent of replication.

Key Results

  • Distance Computations: GESS can reduce the number of distance computations by several orders of magnitude (e.g., a factor of 10⁷ predicted analytically) compared to MSJ, especially with a modest replication rate (less than 15% replication was sufficient).
  • Memory Requirements: GESS requires significantly less main memory (several orders of magnitude lower) than MSJ, making it much more scalable for large datasets.
  • I/O Cost: GESS generally requires half the I/O operations compared to MSJ, an improvement independent of replication.
  • Experimental Speedup: In experiments, GESS achieved speedups of up to 45x over MSJ for similarity joins on real-world CAD data. For a sample dataset, GESS was 8 times faster.

Limitations and Future Work

  • Replication Strategy Optimization: The paper suggests that finding an "optimal" replication strategy that dynamically adapts to data distribution is an area for future research.
  • Compressed Representations: The authors plan to investigate the applicability of compressed feature vector representations.
  • Fractal Dimension Integration: Integrating the fractal dimension into cost models is another avenue for future work.
  • Dynamic and Adaptable Replication: The paper mentions ongoing work on dynamic and adaptable replication strategies.

Summary updated

BibTeX
@inproceedings{dittrich2001gess,
  author = {Jens-Peter Dittrich and Bernhard Seeger},
  title = {{GESS: a scalable similarity-join algorithm for mining large data sets in high dimensional spaces}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2001},
  doi = {10.1145/502512.502524},
}
Figure