Asymmetric Mappings for Efficient Similarity Search

This direction is split into other directions: asymmetric hashing. Its last version stays readable and citable here.

Version 1 of 152 papers80 conceptsfrozen 2026-10-04

In the traditional approach to similarity search, we treat queries and database items as two sides of the same coin. We design a single hash function $h(x)$ and apply it to everything. The intuition is straightforward: if two items are similar, they should end up with the same "fingerprint." However, a growing body of research suggests that this symmetry is a self-imposed constraint that limits both the efficiency and the expressivity of our retrieval systems.

By decoupling the transformation of the query from the transformation of the database—using two distinct functions, $h_q(q)$ and $h_d(d)$—we can solve problems that are mathematically impossible in a symmetric world.

Breaking the Metric Barrier

The most significant limitation of symmetric hashing is its reliance on metric properties. Standard Locality-Sensitive Hashing (LSH) is designed for distances (like Euclidean or Jaccard) that satisfy the triangle inequality. But many modern applications, from recommender systems to object detection, rely on Maximum Inner Product Search (MIPS).

As Anshumali Shrivastava and Ping Li demonstrated in Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS), inner products do not behave like distances. For example, a vector's inner product with itself depends on its magnitude, whereas the distance to itself is always zero.

Asymmetric hashing solves this by "padding" the vectors differently. By applying distinct mathematical transformations to the query and the data, we can map the inner product into a higher-dimensional space where it does look like a standard Euclidean distance. This allows us to use sublinear-time indexing structures originally designed for spatial metrics to solve non-metric search problems. This "asymmetric trick" has been extended to even more complex scenarios, such as Sublinear Time Nearest Neighbor Search over Generalized Weighted Space, where Yifan Lei and colleagues use trigonometric mappings to handle arbitrary query weights.

The Representational Power of Two Functions

Even when the underlying similarity measure is symmetric, using two different hash functions provides a massive boost in representational power. In The Power of Asymmetry in Binary Hashing, Behnam Neyshabur and Nathan Srebro proved that asymmetry allows for much shorter binary codes.

The intuition here is about degrees of freedom. A symmetric hash function must satisfy $h(x) \approx h(y)$ for all similar pairs. An asymmetric scheme only requires $h_q(x) \approx h_d(y)$. This relaxation allows the model to capture complex data distributions that would require exponentially more bits to represent symmetrically. As Xiaoshuang Shi notes in Asymmetric Discrete Graph Hashing, this extra flexibility is particularly effective at preserving similarity information in extremely short bit lengths, which is critical for large-scale retrieval.

Bridging the Domain Gap

In many real-world tasks, the query and the database item are fundamentally different types of data. Consider searching for a long, prose-heavy document using a short, keyword-heavy query. As Bing Bai and Jason Weston argue in Polynomial Semantic Indexing, these inputs have different statistical properties. Using distinct transformation matrices allows the model to project these heterogeneous inputs into a shared semantic space more effectively than a single shared mapping.

This concept is central to Cross-Modal Hashing. When searching for images using text (or vice versa), the "semantic gap" is vast. Fengling Li and Lei Zhu proposed Task-adaptive Asymmetric Deep Cross-modal Hashing to address this. By learning independent hash functions for different retrieval directions (e.g., image-to-text vs. text-to-image), the system can capture the unique semantic nuances of each modality without forcing them into a single, restrictive latent space.

Customizing Collision Profiles

Finally, asymmetry allows us to move beyond "closest is best." In Distance-sensitive hashing, Rasmus Pagh and his co-authors show that asymmetric functions can decouple collision probability from the requirement of maximum similarity at zero distance.

This means we can design hash functions where the probability of a match peaks at a specific non-zero distance. This is useful for "annulus queries"—finding items that are similar but not identical. Similarly, Indradyumna Roy uses asymmetric neural networks in FourierHashNet to model directional relationships like set containment, where a document contains a query's concepts but not necessarily the other way around.

By embracing asymmetry, researchers have transformed hashing from a simple compression tool into a flexible mathematical framework capable of handling the complex, non-linear, and heterogeneous nature of modern data.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_asymmetric_mappings_for_efficient_simila_697df489,
  title = {Asymmetric Mappings for Efficient Similarity Search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/asymmetric-mappings-for-efficient-similarity-search/rdr_697df489f4114ae983baff64cc28c402},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_asymmetric_mappings_for_efficient_simila_697df489_v1,
  title = {Asymmetric Mappings for Efficient Similarity Search},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/asymmetric-mappings-for-efficient-similarity-search/rdr_697df489f4114ae983baff64cc28c402/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}