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.
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.
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