Unified Data Structures for Multi Metric Similarity Search

19 concepts11 papers1 proposal

When analyzing massive datasets—whether high-dimensional vectors, streaming network traffic, or time-series trajectories—we frequently need to evaluate similarity through multiple mathematical lenses. A network operator might need to track both flow cardinality and entropy to detect anomalies. A data scientist might want to query a vector database using Euclidean distance, Cosine similarity, or Inner Products depending on the specific downstream task.

Historically, this required a costly trade-off: deploying separate, specialized data structures (sketches or indices) for each individual metric. This approach scales linearly in memory overhead and ingestion latency. The core insight of multi-metric data summarization is that we can eliminate this redundancy. By identifying geometric invariants or preserving raw, unbiased state distributions, a single "statistic-agnostic" representation can support the simultaneous estimation of diverse metrics at query time.

The Geometric Common Denominator

How can a single representation satisfy multiple distinct geometric distance metrics? The trick lies in decomposing vectors into fundamental components that serve as a common denominator for various formulas.

For instance, in high-dimensional vector search, Euclidean distance, cosine similarity, and inner products seem computationally distinct. However, Wikor Pronobis et al. demonstrated in Sharing Hash Codes for Multiple Purposes that these metrics share a deep geometric link: the angular component of the vectors. By designing a Locality-Sensitive Hashing (LSH) framework that prioritizes this shared angular data and supplements it with minimal norm information, a single set of hash codes can approximate all three metrics at query time without re-indexing.

                  [ High-Dimensional Vector ]
                               |
            +------------------+------------------+
            |                                     |
    [ Angular Component ]                [ Minimal Norm Data ]
            |                                     |
            +------------------+------------------+
                               |
                     [ Shared Hash Code ]
                               |
        +----------------------+----------------------+
        |                      |                      |
[ Cosine Similarity ]  [ Inner Product ]  [ Euclidean Distance ]

Similarly, when dealing with the entire family of $L_p$ norms (such as Manhattan $L_1$, Euclidean $L_2$, and Maximum distance $L_\infty$), Byoung-Kee Yi et al. showed in Fast Time Sequence Indexing for Arbitrary Lp Norms that a simple "segmented means" feature extraction provides a mathematically guaranteed lower bound for all $L_p$ norms. This allows a single index structure to handle diverse distance definitions seamlessly.

This principle extends to complex, non-linear spaces. In Coordinated Local Metric Learning, Jakob Verbeek et al. showed that multiple local Mahalanobis metrics can be embedded into a single, unified global representation. This alignment allows standard Euclidean distance to perform cross-cluster comparisons, enabling high-speed retrieval techniques like product quantization.

Even when metrics are structurally disparate—such as shape-based Euclidean matching versus periodic structure matching—the authors of A Multi-metric Index for Euclidean and Periodic Matching showed that they can be multiplexed within a single hybrid tree structure (the MM-Tree), alternating metrics at different levels to save substantial storage and traversal time. A similar unified index approach was proposed by Michail Vlachos et al. in Indexing multi-dimensional time-series with support for multiple distance measures, which supports Longest Common Subsequence (LCSS), Dynamic Time Warping (DTW), and Euclidean distance simultaneously to handle noisy trajectory data without index restructuring.

Preserving Raw Distributions for Streaming Sets

In streaming data and set analytics, the challenge shifts from geometric vectors to tracking dynamic elements. Instead of building specialized sketches for cardinality (like HyperLogLog) or similarity (like MinHash), unified sketching relies on preserving a compact, unbiased sample of the underlying data distribution.

A prime example is Conditional Random Sampling (CRS), introduced by Ping Li et al. in Conditional Random Sampling: A Sketch-based Sampling Technique for Sparse Data and extended to dynamic streams in One sketch for all: Theory and Application of Conditional Random Sampling. By storing the raw values of sampled dimensions and conditioning on the maximum index of non-zero elements, CRS creates a single compressed sketch. Because it retains these raw sampled values, the same sketch can retrospectively estimate inner products, Jaccard similarity, Hamming distance, and various Minkowski distances.

This philosophy also powers network telemetry. In Counting distinct elements over sliding windows, Eran Assaf et al. introduced SWAMP, a protocol that maintains a single repository of short, raw fingerprints in a compact hash table. Rather than deploying separate mathematical sketches for set membership, per-flow counting, distinct elements, and entropy, all four metrics are derived simultaneously from this single shared state foundation.

By eliminating the additive memory overhead of standalone algorithms, this unified approach achieves a superior space-to-accuracy tradeoff. As network states fluctuate, systems can dynamically shift their analytical focus. For example, Kai-Cheng Yang et al. developed ChameleMon in ChameleMon: Shifting Measurement Attention as Network State Changes, utilizing a single data structure called a FermatSketch to simultaneously track flow counting and packet loss detection with sub-linear space complexity.

Mitigating Noise via Universal Sketching and Nesting

When scaling this unified approach to millions of distinct data subpopulations (e.g., tracking multiple metrics per user or per network sub-flow), a new problem emerges: combinatorial explosion. How do you keep the sketch compact without letting cross-talk or collisions destroy accuracy?

The authors of Enabling Efficient and General Subpopulation Analytics in Multidimensional Data Streams solved this with Hydra, a framework combining statistic-agnostic universal sketching with a nested 2D array structure.

Subpopulation Data Stream ---> [ Hashed 2D Sketch Array ] 
                                      |
                                      v
                        [ Shared Cells (Collisions) ]
                                      |
                                      v
                        [ Median-of-Rows Estimation ]
                                      |
                                      v
                        +-------------+-------------+
                        |                           |
                [ Entropy Estimate ]      [ Cardinality Estimate ]

Instead of allocating dedicated tracking structures for every subpopulation, Hydra intentionally hashes multiple subpopulations into shared cells. To protect against the resulting collision noise, the system computes the median of estimates across multiple rows. Because the underlying summaries are statistic-agnostic, operators can extract entirely new metrics (like entropy or cardinality) from the exact same memory footprint without changing the data ingestion pipeline.

This structural efficiency is mirrored in streaming set frameworks like SimCar, proposed by Wenhua Guo et al. in Generalized Sketches for Streaming Sets. SimCar leverages a single Order-Hashing sketch to simultaneously compute set cardinality, intersection cardinality, and Jaccard similarity.

Ultimately, these diverse frameworks demonstrate that the space efficiency gained from a shared underlying data structure routinely overcomes the traditional performance penalties of general-purpose designs. By decoupling data ingestion from the final analytical metric, unified distance estimation provides a flexible, future-proof foundation for large-scale data analytics.

Key Foundational Work

Fast Time Sequence Indexing for Arbitrary Lp Norms (2000) — contributed 2 concept elements to this direction.
Indexing multi-dimensional time-series with support for multiple distance measures (2003) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_unified_distance_estimation_9530e336,
  title = {unified distance estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/unified-distance-estimation/rdr_9530e336a4f645efa16f22d811cdf0b4},
  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_unified_distance_estimation_9530e336_v1,
  title = {unified distance estimation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/unified-distance-estimation/rdr_9530e336a4f645efa16f22d811cdf0b4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake