Beyond Pairwise: Provably Fast Algorithms for Approximate k-Way Similarity Search

Anshumali Shrivastava, Ping Li

In the era of massive datasets, finding similar items is a fundamental task for search engines, recommendation systems, and data mining. Traditionally, similarity is viewed as a pairwise relationship: how similar is document A to document B? However, many real-world scenarios involve finding items that are similar to a group of queries simultaneously.

In their paper, "Beyond Pairwise: Provably Fast Algorithms for Approximate k-Way Similarity Search," Anshumali Shrivastava and Ping Li extend the popular Locality Sensitive Hashing (LSH) framework to handle these "higher-order" similarities. They provide the first algorithms with provable sub-linear time guarantees for $k$-way Jaccard similarity, demonstrating that searching for items similar to a group is not only theoretically sound but also significantly improves retrieval quality in practice.

The Challenge of k-Way Similarity

Most similarity search algorithms are optimized for one-to-one comparisons. But consider a "Google Sets" application: if a user inputs "Mazda" and "Honda," they aren't looking for things similar to just one of them. They want items that share the specific intersection of attributes defining both brands (e.g., "Toyota" or "Nissan").

Mathematically, this is captured by $k$-way Jaccard Similarity: $$R^{k-way} = \frac{|S_1 \cap S_2 \cap \dots \cap S_k|}{|S_1 \cup S_2 \cup \dots \cap S_k|}$$

A brute-force search for 3-way similarity across a database of $n$ items would typically require $O(n^2)$ or $O(n^3)$ time, which is computationally prohibitive for web-scale data. The authors set out to prove that these "group-similar" items can be found in sub-linear time—meaning search time grows much slower than the database size.

Extending Locality Sensitive Hashing (LSH)

The researchers build upon Minwise Hashing (MinHash), a standard technique for estimating pairwise Jaccard similarity. They prove a crucial property: the probability that the minimum hash value of $k$ different sets is identical is exactly equal to their $k$-way Jaccard similarity.

To make this searchable, they developed a novel indexing scheme. During preprocessing, every item in the database is hashed. At query time, the $k-1$ query items are combined using specific hash functions to identify a "bucket" of potential candidates. This theoretical framework shows that any similarity function expressible as a Probability Generating Function (PGF) of the $k$-way resemblance can be searched efficiently. Specifically, they prove that the query time for a 3-way near-neighbor search is $O(n^\rho \log n)$, where $\rho < 1$, ensuring practical feasibility.

Experimental Performance

The authors evaluated their approach using three distinct datasets: Wikipedia (for semantic word retrieval), MNIST (handwritten digits), and WEBSPAM (email features).

In quantitative tests on MNIST and WEBSPAM, 3-way and 4-way searches consistently outperformed pairwise searches. For example, on the MNIST dataset, the accuracy of finding a "top 1" candidate with the correct label improved from 94.20% using pairwise search to 97.70% using 4-way search.

Table showing the performance (top-k accuracy) on MNIST and WEBSPAM for Pairwise, 3-way, and 4-way nearest neighbor search.

Qualitative Superiority in Semantic Retrieval

The "aha moment" of the research is that $k$-way similarity acts as a refined filter. By looking for the intersection of multiple queries, the algorithm filters out "noise" that might be similar to just one query item but irrelevant to the group's context.

In the "Google Sets" experiment, the 3-way resemblance found highly specific matches. For the queries "finger" and "lakes," the 3-way search correctly identified names of specific lakes and cities in the Finger Lakes region of New York (e.g., Seneca, Cayuga). In contrast, simpler methods like standard Semantic Relatedness (SR) were often dominated by generic terms.

Qualitative comparison of semantic retrieval for word pairs across different methods.

Conclusion and Future Work

This work demonstrates that $k$-way similarity search is a powerful tool for improving retrieval quality without sacrificing computational efficiency. While the current study focuses on binary sparse data, it opens the door for future research into "One-permutation hashing" to reduce overhead and $k$-way sign random projections to handle dense, real-valued vectors. By moving beyond pairwise comparisons, we can build search systems that better understand the complex, multi-faceted relationships inherent in modern data.

Summary updated

Abstract

We go beyond the notion of pairwise similarity and look into search problems with $k$-way similarity functions. In this paper, we focus on problems related to \emph{3-way Jaccard} similarity: $\mathcal{R}^{3way}= \frac{|S_1 \cap S_2 \cap S_3|}{|S_1 \cup S_2 \cup S_3|}$, $S_1, S_2, S_3 \in \mathcal{C}$, where $\mathcal{C}$ is a size $n$ collection of sets (or binary vectors). We show that approximate $\mathcal{R}^{3way}$ similarity search problems admit fast algorithms with provable guarantees, analogous to the pairwise case. Our analysis and speedup guarantees naturally extend to $k$-way resemblance. In the process, we extend traditional framework of \emph{locality sensitive hashing (LSH)} to handle higher order similarities, which could be of independent theoretical interest. The applicability of $\mathcal{R}^{3way}$ search is shown on the Google sets" application. In addition, we demonstrate the advantage of $\mathcal{R}^{3way}$ resemblance over the pairwise case in improving retrieval quality."
BibTeX
@inproceedings{shrivastava2013beyond,
  author = {Anshumali Shrivastava and Ping Li},
  title = {{Beyond Pairwise: Provably Fast Algorithms for Approximate k-Way Similarity Search}},
  booktitle = {NeurIPS},
  year = {2013},
  url = {https://openreview.net/forum?id=LrldMZJUs0H},
}
Figure