Locality Sensitive Hashing in Fourier Frequency Domain For Soft Set Containment Search

In many search applications related to passage retrieval, text entailment, and subgraph search, the query and each 'document' is a set of elements, with a document being relevant if it contains the query. These elements are not represented by atomic IDs, but by embedded representations, thereby extending set containment to soft set containment. Recent applications address soft set containment by encoding sets into fixed-size vectors and checking for elementwise vector dominance. This 0/1 property can be relaxed to an asymmetric hinge distance for scoring and ranking candidate documents. Here we focus on data-sensitive, trainable indices for fast retrieval of relevant documents. Existing LSH methods are designed for mostly symmetric or few simple asymmetric distance functions, which are not suitable for hinge distance. Instead, we transform hinge distance into a proposed dominance similarity measure, to which we then apply a Fourier transform, thereby expressing dominance similarity as an expectation of inner products of functions in the frequency domain. Next, we approximate the expectation with an importance-sampled estimate. The overall consequence is that now we can use a traditional LSH, but in the frequency domain. To ensure that the LSH uses hash bits efficiently, we learn hash functions that are sensitive to both corpus and query distributions, mapped to the frequency domain. Our experiments show that the proposed asymmetric dominance similarity is critical to the targeted applications, and that our LSH, which we call FOURIERHASHNET, provides a better query time vs. retrieval quality trade-off, compared to several baselines. Both the Fourier transform and the trainable hash codes contribute to performance gains. Asymmetric LSH (ALSH) In many applications, like the current setup (1), we have asymmetric similarity where sim(q, x) ̸ = sim(x, q). In such cases, we employ two different hash families G and H to determine the bucket of query and corpus respectively. Formally, we define ALSH as follows: Definition 2.2 (Asymmetric Locality Sensitive Hashing (ALSH) [33] ). An asymmetric LSH is (S 0 , cS 0 , p 1 , p 2 )-ALSH for a similarity function sim(•, •) over Q, X if we have two different distributions over mappings G and H such that, with p 1 > p 2 and c < 1, • if sim(q, x) ≥ S 0 then Pr g∼G,h∼H [g(q) = h(x)] ≥ p 1 • if sim(q, x) ≤ cS 0 then Pr g∼G,h∼H [g(q) = h(x)] ≤ p 2 . As an example, given ∥x∥ ≤ 1, consider sim(q, x) = q ⊤ x/||q|| 2 , which can be re-written as cos(α(q), β(x)), where α(q) = [0; q/∥q∥ 2 ], β(x) = [ 1 -∥x∥ 2 2 ; x]. Thus, we can apply random hyperplane hash on both α(x) and β(x) to construct g(q) = sign(w • α(q)) and h(x) = sign(w • β(x)) with w ∼ N (0, I). If ∥x∥ is unbounded, no ALSH exists for sim(q, x) = q ⊤ x/||q|| 2 [33] . In (S 0 , cS 0 , p 1 , p 2 )-ALSH, retrieval of items with similarity score more than S 0 out of a database of items having a similarity score less than cS 0 will admit time-complexity O(n ρ log n) and space complexity O(n 1+ρ ) where ρ = log p 1 / log p 2 [33] .