Streaming Similarity Self-Join

Gianmarco De Francisci Morales, Aristides Gionis

Abstract

Finding similar items in a continuous data stream is a significant challenge due to the theoretically infinite nature of streams. This paper introduces a novel framework for streaming similarity self-joins that incorporates a "forgetting factor," where similarity between items decays exponentially over time. We propose two algorithmic frameworks: MiniBatch (MB) and Streaming (STR). Central to our approach is the L2 index, a lightweight indexing technique that prioritizes local geometric bounds over complex global statistics. Experimental results on large-scale real-world datasets demonstrate that the STR framework is up to 4x faster and significantly more scalable than traditional minibatch methods.

Introduction: The Challenge of Infinite Streams

Similarity self-join—the task of finding all pairs of objects in a dataset that are "close" to each other—is well-understood for static databases. However, in a streaming context, the problem becomes intractable because storing every item indefinitely to check for future similarities leads to unbounded memory usage.

To address this, the authors introduce time-dependent similarity. They argue that in most real-world applications, such as detecting trending topics or filtering near-duplicate news, users primarily care about items that are both content-similar and arrive within a reasonable time window of each other.

Figure 1: Illustration of documents arriving over a timeline, where similarity is assessed based on both content and temporal proximity.

Methodology

Time-Decaying Similarity

The core innovation is a similarity function that decays exponentially as the time gap between two items increases. This creates a "time horizon" ($\tau$): if two items arrive further apart than $ au$, they can never be considered similar, allowing the system to safely prune old data from memory.

Algorithmic Frameworks: MB vs. STR

The paper compares two primary approaches:

  1. MiniBatch (MB): A "black-box" approach that processes the stream in static chunks using existing high-performance indexes.
  2. Streaming (STR): A "white-box" approach that updates the index item-by-item and uses "lazy" time-filtering to remove expired entries during search operations, minimizing overhead.

The L2 Index

While state-of-the-art static indexes like L2AP use global statistics (Prefix bounds) to prune candidates, these statistics change constantly in a stream, necessitating expensive re-indexing. The proposed L2 index ignores these global bounds, relying solely on local $\ell_2$ (Euclidean) bounds. This makes the index more robust and computationally efficient for volatile streaming data.

Experimental Evaluation

The algorithms were evaluated on four diverse datasets: WebSpam, RCV1 (news), Blogs (WordPress), and Tweets. The evaluation focused on scalability and processing speed under varying similarity thresholds.

Key Results

  • Scalability: The STR framework successfully processed the largest datasets (Blogs and Tweets), whereas the MiniBatch approach frequently timed out or exhausted memory resources. As shown in the performance comparison, STR maintained high throughput where MB performance dropped significantly.
  • Efficiency: On the RCV1 dataset, the STR algorithm was up to 4x faster than the MiniBatch approach. Furthermore, STR typically traversed only 65% of the index entries compared to MB, proving that integrated time-filtering is superior to processing discrete chunks.
  • Pruning Advantage: Surprisingly, the L2 index—despite using fewer pruning bounds than L2AP—performed better in streaming environments. The computational cost of maintaining complex global bounds outweighed their pruning benefits in a high-velocity stream.

Conclusion and Future Work

The "Streaming Similarity Self-Join" framework effectively transforms an $O(n^2)$ problem with infinite memory requirements into a manageable windowed task. By integrating time directly into the similarity function and utilizing lightweight local indexing, the STR framework provides a robust solution for real-time data analysis. Future research directions include exploring hardware acceleration (GPUs) and specialized dimension ordering for inverted indexes in streaming contexts.

Summary updated

BibTeX
@article{morales2016streaming,
  author = {Gianmarco De Francisci Morales and Aristides Gionis},
  title = {{Streaming Similarity Self-Join}},
  journal = {Proc. VLDB Endow.},
  year = {2016},
  doi = {10.14778/2977797.2977805},
}
Figure