[Short Paper] U-HNSW: An Efficient Graph-based Solution to ANNS Under Universal 𝐿𝑝 Metrics Huayi Wang
Jingfan Meng
Jun Xu
arXiv:2605.02030v1 [cs.DB] 3 May 2026
{hwang762, jmeng40}@gatech.edu, [email protected] Georgia Institute of Technology, Atlanta, USA
Abstract
1.1
Approximate nearest neighbor search under universal 𝐿𝑝 metrics (ANNS-U-𝐿𝑝 ) is an important and challenging research problem, as it requires answering queries under all possible 𝑝 (0.5 < 𝑝 ≤ 2) values simultaneously without building an index for each possible 𝑝 value. The state-of-the-art solution, called MLSH, is a LocalitySensitive Hashing (LSH)-based ANNS method with barely acceptable query performance. In contrast, graph-based ANNS methods, which offer significantly improved query efficiency on the ANNS𝐿𝑝 problem (with a fixed 𝑝-value), cannot be naively extended to the ANNS-U-𝐿𝑝 problem. In this paper, we propose U-HNSW, the first graph-based method for ANNS-U-𝐿𝑝 . Our scheme uses HNSW graph indexes built on two base metrics (𝐿1 and 𝐿2 ) to generate promising NN candidates, and then verifies these candidates with an early-termination strategy that substantially reduces the number of expensive 𝐿𝑝 distance computations. Experimental results show that U-HNSW not only achieves up to 2670 times shorter query times than the original MLSH implementation running on a RAM disk (up to 15 times shorter than the idealized MLSH), but also outperforms the original HNSW on the ANNS-𝐿𝑝 problem (with a fixed 𝑝 value), except for a few special 𝑝 values.
In this work, we attack a fundamentally different variant of the ANNS problem. In this problem, like in other ANNS problems, we need to answer queries over a dataset D that lies in a 𝑑-dimensional space. However, unlike traditional ANNS formulations that assume a fixed distance metric, each query in our problem specifies its own distance metric parameter 𝑝. Specifically, the 𝑖-th query is a tuple (𝑞®𝑖 , 𝑝𝑖 ), where 𝑞®𝑖 is the query vector and 𝑝𝑖 determines the 𝐿𝑝 metric used to measure distances. The objective is to find 𝑥® ∈ D that is closest to 𝑞®𝑖 under the 𝐿𝑝𝑖 distance. Because the value of 𝑝𝑖 can vary from one query to the next, we refer to this problem as ANNS under universal 𝐿𝑝 metrics, or ANNS-U-𝐿𝑝 for short. While the 𝐿2 metric is undoubtedly the most widely used and influential distance measure in ANNS [7, 17, 21, 22], other 𝐿𝑝 metrics are also important, as they can often yield more insightful and discriminative results in data mining, image retrieval, and genomic data search [11, 15, 27]. Accordingly, the ANNS problem under a general 𝐿𝑝 metric (ANNS-𝐿𝑝 ) has been studied extensively in the literature [5, 12]. However, an ANNS-𝐿𝑝 query engine built for a fixed value of 𝑝 is often inadequate for many modern ML applications, where the most discriminative choice of 𝑝 can vary across datasets or tasks and must be tuned per application [27]. For example, in 𝑘NN classification, [27] shows that the optimal 𝑝 differs across datasets: 𝑝 = 0.5 achieves the highest accuracy on a physical signal dataset, 𝑝 = 0.6 is optimal on an image dataset, while 𝑝 = 1.0 is optimal on a text dataset. Since the best 𝑝 cannot be known in advance and must be determined empirically, an efficient query engine that supports arbitrary 𝐿𝑝 metrics without rebuilding the index is essential. In contrast, an efficient query engine for ANNS under universal 𝐿𝑝 metrics (ANNS-U-𝐿𝑝 ) would be ideal for such applications, as it enables adaptive exploration of the dataset D under different 𝐿𝑝 metrics—allowing each application to identify the most suitable, task-specific 𝑝 value dynamically. The ANNS-U-𝐿𝑝 problem is particularly challenging because it demands high query efficiency and accuracy across a continuum of 𝐿𝑝 metrics. A straightforward approach is to construct, for each possible 𝑝𝑖 value, a dedicated ANNS index (e.g., using 𝑝-stable Locality-Sensitive Hashing [5]) to handle ANNS-𝐿𝑝𝑖 queries. However, this naive solution is clearly impractical, as it would require building and maintaining a large number of separate indexes for the full range of 𝑝 values in (0.5, 2], even after discretizing or quantizing the space of possible 𝑝 values. For example, a coarse discretization of 𝑝 at intervals of 0.1 (as used in prior work [20, 27]) would require 20 separate indexes.
ACM Reference Format: Huayi Wang Jingfan Meng Jun Xu . 2027. [Short Paper] U-HNSW: An Efficient Graph-based Solution to ANNS Under Universal 𝐿𝑝 Metrics. In Proceedings of 30th International Conference on Extending Database Technology (EDBT ’27). ACM, New York, NY, USA, 8 pages. https://doi.org/ XXXXXXX.XXXXXXX
1
Introduction
Approximate nearest neighbor search (ANNS), also known as similarity search, is a fundamental algorithmic problem arising in many areas of computer science, such as large language models [6, 26], computer vision [14], and information retrieval [19]. In these applications, data items in a dataset D are represented by vectors in a high-dimensional (say 𝑑-dimensional) space. Given a query point 𝑞, ® the goal of ANNS is to find one or more points in D that are among the closest to 𝑞® according to a certain distance metric, such as the Euclidean (𝐿2 ) distance. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]. EDBT ’27, Lille, France © 2027 Copyright held by the owner/author(s). Publication rights licensed to ACM. ACM ISBN 978-1-4503-XXXX-X/2018/06 https://doi.org/XXXXXXX.XXXXXXX
1.2
ANNS-U-𝐿𝑝 : Application and Challenges
Existing Solutions
LazyLSH [27] represents the first practical attempt to address the ANNS-U-𝐿𝑝 problem without building multiple indexes. It is built
EDBT ’27, April 06–09, 2027, Lille, France
upon the 𝑝-stable LSH framework [5] and aims to reuse a single index constructed for the 𝐿1 metric (called the base metric in [27]) to answer queries under various 𝐿𝑝 metrics for 0.5 ≤ 𝑝 ≤ 1. The key insight is that two points 𝑥® and 𝑦® that are close under the 𝐿1 metric are also likely to be close under the 𝐿𝑝 metric, provided that 𝑝 is not too far from 1. However, as 𝑝 deviates further from 1 (e.g., toward 0.5), this correlation between 𝐿1 -closeness and 𝐿𝑝 -closeness diminishes, leading to a noticeable degradation in query accuracy, as observed in [20]. Multi-Metric LSH (MLSH) [20], the current state-of-the-art solution for the ANNS-U-𝐿𝑝 problem, addresses this limitation by introducing an additional LSH index for the 𝐿0.5 metric “at the other end.” Specifically, given an ANNS-U-𝐿𝑝 query (𝑞®𝑖 , 𝑝𝑖 ), MLSH selects which index to use based on the value of 𝑝𝑖 : when 𝑝𝑖 is closer to 0.5 than to 1, it relies on the 𝐿0.5 index instead of the 𝐿1 index to find the nearest neighbors (NNs) of 𝑞®𝑖 . However, the overall query performance of MLSH remains constrained by the inherent inefficiency of the LSH framework, which is known to incur relatively long query times in practice [17, 22].
1.3
Our Graph-based Solution to ANNS-U-𝐿𝑝
For ANNS-𝐿𝑝 with a fixed 𝑝, graph-based methods such as Hierarchical Navigable Small World (HNSW) [22] have been shown to deliver substantially better query efficiency than LSH-based approaches. As a result, graph-based ANNS methods have become one of the most widely adopted approaches in modern industrial vector database systems [2, 3]. We are hence motivated to explore whether a graph-based ANNS-𝐿𝑝 solution can be extended to handle the ANNS-U-𝐿𝑝 problem. However, a naive approach—constructing a separate graph index for every possible 𝑝 value—clearly fails to scale, as it would require maintaining a large number of distinct graph indexes in memory. Moreover, building even a single high-quality graph index is computationally expensive and timeconsuming, as noted in [17]. These challenges likely explain why, despite the appeal of graph-based methods, no prior work has successfully extended them to support efficient ANNS under universal 𝐿𝑝 metrics—until this work. Another challenge posed by ANNS-U-𝐿𝑝 is that, even for the much simpler ANNS-𝐿𝑝 problem (with a fixed 𝑝), directly applying HNSW is much less efficient (except for a few special 𝑝 values) than its well-known performance for ANNS-𝐿2 . This is because the dominant cost in HNSW query processing arises from query-to-data (Q2D) distance computations, and the algorithm needs to evaluate Q2D distances for a large number of intermediate points. When the target metric is a general 𝐿𝑝 , each such Q2D computation is substantially more expensive than under 𝐿2 (as analyzed in Section 2.1), which can significantly increase the query time. To address the above challenges, we propose Universal HNSW (U-HNSW)—the first graph-based method that extends the widely adopted HNSW algorithm for solving the ANNS-U-𝐿𝑝 problem. Unlike a naive approach that simply replaces the LSH indexes in MLSH with HNSW graphs, U-HNSW is enabled by two key observations: first, 𝐿1 /𝐿2 distance computation is over an order of magnitude faster than general 𝐿𝑝 via SIMD; second, 𝐿1 /𝐿2 distance ordering is a highly effective filter for 𝐿𝑝 nearest neighbors, so a
Wang, Meng, and Xu
small candidate set already achieves high recall. Specifically, instead of constructing a large number of separate graph indexes for different 𝑝 values, U-HNSW maintains only two graph indexes: 𝐺 1 , an HNSW index built under the 𝐿1 metric, and 𝐺 2 , an HNSW index built under the 𝐿2 metric. During query processing, given a query (𝑞, ® 𝑝), U-HNSW first selects the base index—either 𝐺 1 or 𝐺 2 —whose underlying metric is closer to the query metric 𝐿𝑝 (with a slight weighting adjustment). It then searches for ANNs of 𝑞® using the selected graph (say 𝐺 1 for 𝐿1 ). This step is computationally efficient because the dominant cost in HNSW query processing arises from Q2D distance evaluations, and computing 𝐿1 or 𝐿2 distances is relatively inexpensive (Section 2.1). Next, each candidate point returned from the base-metric search—ordered by its base distance (e.g., 𝐿1 )—is vetted by computing its exact Q2D distance under the query metric 𝐿𝑝 . U-HNSW performs these 𝐿𝑝 distance evaluations progressively and terminates once the estimated recall is found to exceed the target threshold, thereby avoiding unnecessary and expensive 𝐿𝑝 distance computations. This early-termination strategy is crucial for achieving both high speed and high accuracy, as detailed in Section 3.1. As demonstrated in Section 4, U-HNSW not only achieves a substantial performance improvement over MLSH, but also significantly outperforms the original HNSW when applied to fixed-metric ANNS-𝐿𝑝 problems, except for a few special 𝑝 values. In summary, this work makes three main contributions. First, we present U-HNSW, the first practical graph-based solution to the ANNS-U-𝐿𝑝 problem, which efficiently supports queries under arbitrary 𝐿𝑝 metrics without requiring a separate index for each possible value of 𝑝. Second, we develop an adaptive candidate checking framework that reduces the number of expensive 𝐿𝑝 distance computations, allowing U-HNSW to outperform its baseline HNSW even for fixed-metric ANNS-𝐿𝑝 tasks. Third, through extensive experiments, we show that U-HNSW not only achieves up to 2670 times shorter query times than the original MLSH implementation running on a RAM disk (up to 15 times shorter than the idealized MLSH), but also outperforms the original HNSW on the ANNS-𝐿𝑝 problem (with a fixed 𝑝-value), except for a few special 𝑝 values (e.g., 𝑝 = 0.5, 1.5) where the 𝐿𝑝 Q2D distance computations can be accelerated by SIMD instructions.
2
Background and Related Work
In this section, we provide some essential background for our work. We first define the problem of ANNS under universal 𝐿𝑝 metrics (ANNS-U-𝐿𝑝 ) and explain how the computational cost of 𝐿𝑝 distance varies significantly with 𝑝, in Section 2.1. Finally, we describe HNSW, which serves as the baseline for our U-HNSW scheme, in Section 2.2.
2.1
ANNS under Universal 𝐿𝑝 Metrics
Given a query tuple (𝑞, ® 𝑝), the goal of ANNS-U-𝐿𝑝 is to retrieve the top-𝐾 nearest neighbors of the query point 𝑞® in D according to the 𝐿𝑝 metric at a high recall value (say 90%) in as little query time as possible. In the sequel, unless specifically mentioned, we assume that the given 𝑝 value ranges from 0.5 to 2, which covers the commonly evaluated range of 𝑝 values used in previous ANNS-U𝐿𝑝 works [20, 27]. We follow the convention adopted in prior ANNS
[Short Paper] U-HNSW: An Efficient Graph-based Solution to ANNS Under Universal 𝐿𝑝 Metrics
literature [8, 9, 12, 17, 20, 22, 27] of focusing on 𝑝 ≤ 2, since 𝐿𝑝 metrics with 𝑝 > 2 are rarely used in practical ANNS applications. The 𝐿𝑝 (distance) metric ||𝑥® − 𝑦|| ® 𝑝 between two 𝑑-dimensional vectors 𝑥® = (𝑥 1, 𝑥 2, · · · 𝑥𝑑 ) and 𝑦® = (𝑦1, 𝑦2, · · · 𝑦𝑑 ) is defined as Í 1/𝑝 𝑑 𝑝 . When 𝑑 is not small, the computation time of 𝑖=1 |𝑥𝑖 − 𝑦𝑖 | this 𝐿𝑝 distance can vary significantly for different values of 𝑝, as follows. • 𝑝 = 1 or 2 (fastest). The computation of the 𝐿1 or 𝐿2 metric involves only basic arithmetic operations (add/subtract/multiply), which can be performed in a computationally efficient manner using SIMD instructions such as _mm512_sub_ps and _mm512_add_ps. As shown in Figure 1, the 𝐿1 or 𝐿2 metric is the fastest to compute across different dimensionalities. • 𝑝 = 0.5 or 1.5 (quite fast). In addition to basic arithmetic operations, the computation of the 𝐿0.5 or 𝐿1.5 metric involves the square root operation, which can also be computed efficiently with SIMD instructions such as _mm512_sqrt_ps. As shown in Figure 1, the computation of the 𝐿0.5 or 𝐿1.5 metric is slightly (1.4 to 2.1 times) slower than that of the 𝐿1 or 𝐿2 metric across different 𝑑 values. • Other 𝑝 values (slow). For 𝐿𝑝 metrics with other 𝑝 values, power operations are needed in their computations, which are not SIMDfriendly and are much more expensive computationally than the aforementioned basic and square root operations. Since all such 𝑝 values require power operations, their computation times are nearly identical to each other. As a result, computation time of a general 𝐿𝑝 metric is more than an order of magnitude slower than that of the 𝐿1 or 𝐿2 metric as shown in Figure 1. Computation time ( s)
▲
General 𝐿𝑝
■
𝐿0.5 /𝐿1.5
• 𝐿1 /𝐿2
cost of longer construction time. If two nodes are close to each other in the 𝐿𝑝 metric, there is an edge connecting them in the proximity graph. Given a query point 𝑞, ® HNSW uses the following greedy search strategy to find the top-𝐾 NNs: starting from a pre-defined entry point, HNSW traverses the proximity graph along these edges. When reaching a previously unvisited node 𝑣®, HNSW adds 𝑣® to the NN candidate set C, if 𝑣® has a smaller Q2D distance than the farthest point in C. The size of C is controlled by efSearch: a larger efSearch leads to higher recall at the cost of longer query time. The most expensive part of HNSW query processing is to compute the Q2D distances between all traversed nodes and the query point 𝑞: ® as reported in [18], this computation accounts for more than 83% of the total query time. This is because other computations in HNSW, such as traversing nodes along the edges, can be performed very efficiently, as the graph index resides in memory. Now we explain why conventional HNSW must build a separate graph index for every possible 𝑝-value (𝐿𝑝 metric) in order to answer ANNS-U-𝐿𝑝 queries. As just explained, the HNSW index is constructed by connecting data points (by proximity edges) based on their closeness (proximity) under a given 𝐿𝑝 metric. Let 𝑝 1 and 𝑝 2 be two distinct 𝑝 values that are not very close to each other. Then the set of proximity edges in the graph index built for the 𝐿𝑝 1 metric can differ significantly from that in the graph index built for the 𝐿𝑝 2 metric. Since the “soul" of a graph index is these proximity edges, using the index built for 𝐿𝑝 1 to search for NNs under 𝐿𝑝 2 cannot guarantee high query accuracy. For this reason, HNSW and other graph-based methods [7, 21, 22] all specify a single target distance metric (usually the 𝐿2 metric) and evaluate performance only under that metric.
101 100
2.3
10 1 102
103
Dimension d
Figure 1: Average computation times (in microseconds) of each 𝐿𝑝 distance instance on our workstation described in Section 4.1 (both axes in log scale). 𝐿1 and 𝐿2 metric computations are faster than general 𝐿𝑝 metric computation by more than one order of magnitude.
2.2
EDBT ’27, April 06–09, 2027, Lille, France
Hierarchical Navigable Small World Graph
Hierarchical Navigable Small World (HNSW) graph [22] is an efficient and widely recognized graph-based solution to ANNS-𝐿𝑝 for a fixed 𝑝 value (0.5 ≤ 𝑝 ≤ 2). HNSW organizes the dataset into a multi-layer proximity graph, where each node represents a data point. The graph is built incrementally by inserting data points one by one: each new point is connected to its 𝑀 closest neighbors in the graph (where 𝑀 is a key construction parameter), and the quality of these connections is controlled by efConstruction, the size of the dynamic candidate list maintained during insertion. Larger 𝑀 and efConstruction yield higher-quality graphs at the
Product Quantization ANNS Methods
Besides LSH-based and graph-based methods, product quantization (PQ) based methods [8, 9, 13] are another widely used family of ANNS methods. These methods quantize the data in D to a small set of designated points and the search is performed over those points in D that are quantized to the same designated point as the query point, and to the nearby designated points. However, these PQbased solutions usually focus on the ANNS-𝐿2 problem and it is not clear how they can be extended to solve the ANNS-U-𝐿𝑝 problem, for the following reasons. For the recent state-of-the-art PQ-based method RaBitQ [8], it normalizes vectors onto the unit hypersphere to convert 𝐿2 distance to inner products—a technique fundamentally tied to 𝐿2 that cannot be extended to arbitrary 𝐿𝑝 distances. Other PQ methods such as Optimized Product Quantization (OPQ) [9] could in principle be adapted to a fixed 𝐿𝑝 metric. However, like graph-based methods, the set of designated points in a PQ index built for 𝐿𝑝 1 can differ significantly from that built for 𝐿𝑝 2 , when 𝑝 1 and 𝑝 2 are not close to each other. Using an index built for 𝐿𝑝 1 to search for NNs under 𝐿𝑝 2 would therefore introduce significant errors. To supporting ANNS-U-𝐿𝑝 query, OPQ would thus still require building a separate index for each possible 𝑝 value—the scalability problem described in Section 1.1. For these reasons, we do not compare with PQ-based methods in our evaluation.
EDBT ’27, April 06–09, 2027, Lille, France
3
Scheme Description
In this section, we present our novel solution U-HNSW for the ANNS-U-𝐿𝑝 problem. We first describe the overall procedure of the algorithm, including candidate generation and verification in Section 3.1. Then, we explain the rationale behind using graph indexes on the 𝐿1 and 𝐿2 metrics to generate the candidate set for universal 𝐿𝑝 metrics and analyze how to set parameters to minimize the number of expensive 𝐿𝑝 distance computations in Section 3.2. In this section, we focus on the general case where 𝑝 ∉ {1, 2}; when 𝑝 = 1 (or 𝑝 = 2), the query reduces to standard ANNS under the 𝐿1 (or 𝐿2 ) metric, and we can directly search the corresponding graph index 𝐺 1 (or 𝐺 2 ) for 𝐾-NNs.
Wang, Meng, and Xu
Input: Query tuple (𝑞, ® 𝑝); integer 𝐾 Output: Top-𝐾 NNs of 𝑞® under 𝐿𝑝 2 Parameters: 𝑡 = 300, 𝜏 = 0.92, 𝜅 = 𝐾 3 if 𝑝 ≤ 1.4 then 4 𝐶 ← 𝐺 1 .KnnSearch(𝑞, ® 𝑡) 5 else 6 𝐶 ← 𝐺 2 .KnnSearch(𝑞, ® 𝑡) 1
𝑅 ← first 𝐾 points of 𝐶 foreach batch of 𝜅 points 𝑅 ′ of 𝐶 do 9 𝑅𝑛𝑒𝑤 ← top-𝐾 points by 𝐿𝑝 Q2D distance in 𝑅 ∪ 𝑅 ′ 10 if |𝑅𝑛𝑒𝑤 ∩ 𝑅|/𝐾 ≥ 𝜏 then return 𝑅𝑛𝑒𝑤 ; 11 𝑅 ← 𝑅𝑛𝑒𝑤 7 8
Algorithm 1: U-HNSW Query for ANNS-U-𝐿𝑝
Algorithm Description
0.995 0.990 0.985
■
1.00 50-NN Recall
As mentioned earlier, U-HNSW extends HNSW for ANNS-U-𝐿𝑝 . To this end, U-HNSW builds and uses two HNSW indexes, namely 𝐺 1 for the 𝐿1 metric and 𝐺 2 for the 𝐿2 metric. Algorithm 1 shows how U-HNSW processes an ANNS-U-𝐿𝑝 query (𝑞, ® 𝑝), to arrive at the 𝐾 NNs of 𝑞® under the 𝐿𝑝 metric. It consists of the following two steps. Candidate generation. U-HNSW first selects a graph index according to the 𝑝 value specified in the query as follows. If 𝑝 ≤ 1.4, the graph index 𝐺 1 is selected; otherwise, the graph index 𝐺 2 is used. We use 1.4 as the default cutoff value, which approximately equals the crossover point as shown in Figure 2. The performance is not sensitive to small perturbations around this value. Then, UHNSW runs the standard KnnSearch procedure in HNSW to return a large candidate set 𝐶 containing the 𝑡-NNs (𝑡 > 𝐾), sorted in the ascending order of their Q2D distances (as specified in the HNSW code manual [1]), under the corresponding base metric (Line 3 and Line 5). The NN candidate set 𝐶 is indeed nearly complete due to the following observation: if two points 𝑥® and 𝑦® are close under the 𝐿1 metric, they are likely to remain close under the 𝐿𝑝 metric for 0.5 ≤ 𝑝 ≤ 1.4; and if 𝑥® and 𝑦® are close under the 𝐿2 metric, they are likely to remain close under the 𝐿𝑝 metric for 1.4 < 𝑝 ≤ 2. This observation extends the aforementioned observation of LazyLSH (described in Section 1.2) to a wider range of 𝑝 values. This extension is justified by the well-known norm equivalence in finite dimensions [16]. As we will show in Section 3.2, we make 𝑡 large enough to ensure that all K-NNs of 𝑞® under the 𝐿𝑝 metric are included in 𝐶 so that a high recall can be achieved with high probability. We will explain how to set the parameter 𝑡 in Section 3.2. Candidate verification. The candidate set 𝐶 contains 𝑡 (𝑡 > 𝐾) points sorted by 𝐿1 or 𝐿2 distance, not by the target 𝐿𝑝 distance. Although 𝐶 contains the true top-𝐾 NNs (in 𝐿𝑝 distance) with high probability, they are not necessarily among the first 𝐾 points of 𝐶 under the base metric ordering. Therefore, we must re-rank 𝐶 by exact 𝐿𝑝 Q2D distances to identify the true top-𝐾, as described as follows. First, we pop the first 𝐾 points from the candidate set 𝐶, and initialize them as (a set) 𝑅. Then, we iteratively pop a batch of 𝜅 (𝜅 > 1) points from 𝐶 (denoted as 𝑅 ′ ), and find the 𝐾 points (denoted as 𝑅𝑛𝑒𝑤 ) with the smallest 𝐿𝑝 Q2D distances in the union 𝑅 ∪ 𝑅 ′ . The iteration stops once the intersection ratio |𝑅 ∩ 𝑅new |/𝐾 is above a pre-defined threshold 𝜏, indicating that the result will not significantly improve with further iterations. This early-termination
• 𝐺1 ( base metric 𝐿1 )
1.000 50-NN Recall
3.1
1.2
1.4 p
1.6
𝐺 2 (base metric 𝐿2 )
0.99 0.98 1.2
(a) SIFT
1.4 p
1.6
(b) GIST
Figure 2: Recall under the target 𝐿𝑝 metric when the candidate set is the true top-𝑡 NNs on GIST and SIFT datasets in Table 1. We set 𝑡 = 300 as described in Section 3.2. The crossover point appears around 1.4, motivating our default cutoff 1.4. strategy ensures that as few expensive 𝐿𝑝 distance computations as needed (to achieve the desired recall) are performed. The early-termination parameter 𝜏 can be viewed as an estimator of the recall for the query 𝑞. ® To make this estimator accurate, the batch size 𝜅 must be sufficiently large so that the intersection cardinality |𝑅new ∩ 𝑅| reflects how many candidates in 𝑅new are likely to be among the true top-𝐾 NNs of 𝑞. ® If 𝜅 is too small, U-HNSW may terminate prematurely before examining all potential true top-𝐾 NNs. We find that setting 𝜅 to K/2 empirically achieves a good trade-off between query accuracy and query speed.
3.2
Parameter Tuning
In this subsection, we describe how to tune the parameters in UHNSW to achieve a short query time while maintaining a good query accuracy (measured by the recall). As mentioned earlier, in UHNSW, the total query time 𝑇query consists of two parts: the time for candidate generation (𝑁𝑏 𝑇𝑏 ) and the time for candidate verification (𝑁𝑝 𝑇𝑝 ). That is, 𝑇query = 𝑁𝑏 𝑇𝑏 + 𝑁𝑝 𝑇𝑝 ,
(1)
where 𝑁𝑏 and 𝑁𝑝 denote the number of Q2D distance computations under the base metric and under the 𝐿𝑝 metric, respectively; and 𝑇𝑏 and 𝑇𝑝 are the average time per Q2D distance computation under the base metric and under the 𝐿𝑝 metric, respectively. In U-HNSW, we primarily tune two parameters: 𝑡 and 𝜏. As we will elaborate next, 𝑡 determines the number of base-metric distance computations 𝑁𝑏 in Equation 1, and 𝜏 determines the number of 𝐿𝑝 distance computations 𝑁𝑝 in Equation 1. We now explain how to set these parameters 𝑡 and 𝜏.
[Short Paper] U-HNSW: An Efficient Graph-based Solution to ANNS Under Universal 𝐿𝑝 Metrics
4
Evaluation
In this section, we conduct an extensive study using six widely used publicly available datasets of diverse dimensions, sizes (number of points) and types. We first evaluate the query performance of U-HNSW and compare it with MLSH’s on the ANNS-U-𝐿𝑝 problem in Section 4.2. Then we evaluate the query performance of U-HNSW on ANNS-𝐿𝑝 (with fixed 𝑝) and compare it with that of HNSW. Our results show conclusively that U-HNSW not only outperforms the state-of-the-art ANNS-U-𝐿𝑝 solution MLSH by a factor of up to 15.0 in terms of query efficiency, but also is much faster than its baseline HNSW on ANNS-𝐿𝑝 , except for a few special 𝑝 values.
GIST
1.0
SIFT
0.95
0.9
50-NN Recall
50-NN Recall
As described in Section 3.1, given the number of NNs 𝐾, we set 𝑡 sufficiently large to achieve the target recall 𝑟 = 0.9 (the value used throughout Section 4). For 𝐾 = 50 (the setting used in Section 4), we find that using a single default 𝑡 = 300 across datasets is large enough to meet the target recall. Figure 3(a) reports the recall obtained when using the true top-𝑡 NNs under the base metric (𝐿1 ) as the candidate set. We evaluate the most demanding setting (𝑝 = 0.5) with 𝐾 = 50 on both the SIFT and GIST datasets in Table 1. These two datasets are chosen as representatives because they span a wide range of dimensionalities (128 and 960, respectively), and the parameter tuning results on other datasets are similar. As 𝑡 increases, the recall quickly approaches saturation, so much so that 𝑡 = 300 already achieves a recall close to 1. Since Figure 3(a) measures recall using the true top-𝑡 as the candidate set, while U-HNSW’s candidate generation retrieves an approximate top-𝑡 via KnnSearch, we set 𝑡 = 300 rather than a smaller value: the resulting margin above the target 0.9 absorbs the small gap between the true top-𝑡 and HNSW’s approximate top-𝑡. Using 𝑡 = 300, which may be larger than necessary on some datasets, only incurs a small additional overhead in the total query time, for the following reason. 𝑁𝑏 grows sub-linearly with 𝑡 when 𝑡 is within a few hundreds [22], and 𝑇𝑏 is more than an order of magnitude smaller than 𝑇𝑝 (as explained in Section 2.1). As a result, the term 𝑁𝑏𝑇𝑏 remains small in Equation 1 even if 𝑡 is larger than necessary. The threshold parameter 𝜏 controls the early-stopping criterion in U-HNSW’s candidate verification step. As mentioned in Section 3.1, 𝜏 can be viewed as an estimate of the query recall value. Given a target recall 𝑟 (e.g., 𝑟 = 0.9 in Section 4), we set 𝜏 = 𝑟 + 𝛿 to leave a small safety margin, where 𝛿 is a small constant (0.02 by default in our experiments).The default 𝛿 = 0.02 is empirically validated in Figure 3(b): 𝜏 = 𝑟 + 𝛿 = 0.92 is the smallest 𝜏 that consistently meets the target recall 0.9 on both datasets. Increasing 𝛿 (and hence 𝜏) further raises recall but lengthens query time, since more candidates must be verified before early termination triggers. If a higher recall value is required, we can increase 𝜏 accordingly, which allows U-HNSW to meet the new target recall while keeping 𝑁𝑝 small, so that the term 𝑁𝑝𝑇𝑝 remains small in Equation 1. Similar to the analysis of 𝑡, we provide empirical evidence from two real-world datasets GIST and SIFT in Figure 3(b). Figure 3(b) clearly shows that setting 𝜏 = 0.92 (target 0.9 plus a small margin) consistently meets the target recall (0.9) on both datasets while avoiding unnecessary 𝐿𝑝 computations.
EDBT ’27, April 06–09, 2027, Lille, France
0.90
0.8
= 0.92
0.85
0.7 100
200
300 t
400
500
(a) Recall under different 𝑡 .
0.80
0.75
0.80
0.85
0.90
0.95
(b) Recall under different 𝜏
Figure 3: Empirical evidence for tuning 𝑡 and 𝜏 on GIST and SIFT datasets in Table 1. We use 𝑝 = 0.5, which represents the most demanding setting due to its large mismatch to the base metric (𝐿1 ).
4.1
Evaluation Settings
4.1.1 Evaluation Datasets. We use six widely used publicly available datasets of diverse dimensions, sizes (number of points), and types. The SIFT dataset contains 2 million points sampled uniformly at random from the 1 billion points contained in SIFT1B [4]. We cannot use SIFT1B instead because constructing the HNSW graph index for it would not fit into the 128 GB main memory of our workstation. For each of the six datasets, Table 1 shows its size 𝑛, its dimension 𝑑, and its type. For each of the six datasets, the query set contains 1,000 points sampled uniformly at random from the set of query points associated with the corresponding dataset. Dataset Sun [25] Trevi [24] GIST [4] Deep [17] GloVe [23] SIFT [4]
𝑛 78,306 99,100 1,000,000 1,000,000 1,191,714 2,000,000
𝑑 512 4096 960 256 100 128
Type Image Image Image Image Text Image
Table 1: Evaluation datasets summary. 4.1.2 Performance Metrics. We evaluate the performance of UHNSW, HNSW and MLSH in three aspects: index scalability, query efficiency, and query accuracy. To measure index scalability, we use index size (excluding the size of the original dataset D). To measure query efficiency, we use query time. To measure query accuracy, we use recall, which is defined as follows. Denote by S ∗ the set of true top-𝐾 NNs under the 𝐿𝑝 metric and by S the set of 𝐾 approximate NNs in the result. The top-𝐾 query recall is equal to |S ∗ ∩ S|/𝐾. Throughout our evaluation, unless otherwise stated, we use 𝐾 = 50; using any other value of 𝐾 ranging from 10 to 100 (commonly used in the ANNS literature [12, 20–22]) results in similar query performance. Each query time or recall value presented in this section is the average over all queries. 4.1.3 Implementation Details. We implement U-HNSW in C++ based on the widely used open-source HNSW implementation called HNSWlib [1]. For MLSH, we use the C++ source code provided by its authors. We optimize the 𝐿1 , 𝐿2 , 𝐿0.5 and 𝐿1.5 distance computations using the SIMD instructions described in Section 2.1 and general 𝐿𝑝 distance computations using the optimized implementation in NMSLIB [] (a popular ANNS library used in Amazon
EDBT ’27, April 06–09, 2027, Lille, France
Wang, Meng, and Xu
Elasticsearch service). We compile all C++ source code using g++ 13.3 with -O3. All experiments are done on a workstation running Ubuntu 22.04 with an Intel Core i7—9800X CPU @ 3.80 GHz and 128 GB RAM. Our code is available in Anonymous GitHub [].
excludes all other expensive CPU computations. As we will elaborate next, even using such an extremely favorable idealized estimate for MLSH, U-HNSW still achieves significantly shorter query times while maintaining comparable or better recall.
4.1.4 Benchmark Algorithms. In our evaluation, we compare UHNSW against the original HNSW and MLSH. We do not compare against LazyLSH since MLSH outperforms LazyLSH as shown in [20]. The settings of benchmark algorithms are described as follows: U-HNSW. For U-HNSW, we first describe the parameter settings of the 𝐺 1 and 𝐺 2 graph indexes. For these two graph indexes, we set their parameters so that they can achieve a very high recall when searching for nearest neighbors under the base metric. Specifically, we use 𝑀 = 32 and efConstruction = 500 for both 𝐺 1 and 𝐺 2 . Then we set the parameter 𝜏 = 0.92 which is slightly higher than the target recall value 0.9 as described in Section 3.2. Such a setting ensures that most queries achieve a recall value larger than 0.9. As for the parameter 𝑡, we set it to 300 according to the parameter tuning strategy described in Section 3.2. HNSW. We compare U-HNSW with the original HNSW on the ANNS-𝐿𝑝 problem with a fixed 𝑝 value. For 𝑝 = 1 and 𝑝 = 2, the “original HNSW” baseline directly reuses 𝐺 1 and 𝐺 2 , respectively. For other 𝑝 values, we build a separate HNSW graph index under the corresponding 𝐿𝑝 metric using 𝑀 = 32 and efConstruction = 200, the recommended defaults from the HNSW code manual [1]. These parameter settings ensure that the original HNSW can achieve an average recall value greater than 0.9 on the evaluated ANNS-𝐿𝑝 problem. MLSH. We use the parameter settings and the original implementation of MLSH provided by its authors. For our in-memory evaluation (with the MLSH index stored on a RAM disk), the measured query time of MLSH is extremely high: For example, on the Sun and GloVe datasets, the original MLSH implementation takes approximately 4.67 seconds and 5.35 seconds per query, respectively, making U-HNSW 2670 and 890 times faster on these two datasets. However, one may argue that directly comparing against the original MLSH implementation could be unfair for the following two reasons. First, the 𝐿𝑝 distance computations in MLSH are not optimized using the SIMD instructions described in Section 2.1 and the 𝐿𝑝 metric optimization in NMSLIB described in Section 4.1.3, which makes each Q2D 𝐿𝑝 computation in MLSH substantially slower than that in U-HNSW. Second, MLSH is built upon QALSH (Query Aware LSH [12]), which is designed for external-memory operations and thus aims to minimize the number of sequential I/Os. As an inherent trade-off, its CPU computation time, other than that for distance computations, can be extremely large, as observed in [10]. To make the comparison implementation-agnostic and extremely favorable to MLSH, we report, for MLSH, the idealized query time that accounts only for query-to-data (Q2D) 𝐿𝑝 distance computations, calculated as 𝑁𝑝𝑇𝑝 , where 𝑁𝑝 is the number of Q2D 𝐿𝑝 distance computations performed by MLSH query processing (as reported by the MLSH program), and 𝑇𝑝 is the same average per Q2D distance computation time as achieved in U-HNSW (using SIMD-optimized 𝐿𝑝 implementation). This idealized estimate accounts only for the Q2D 𝐿𝑝 distance computations in MLSH and
4.2
Comparison against MLSH
In this subsection, we compare U-HNSW against MLSH, the stateof-the-art solution to the ANNS-U-𝐿𝑝 problem. Since MLSH can solve this problem only for 𝑝 ≤ 1, we restrict 𝑝 to values between 0.5 and 1. Accordingly, we report only the size of 𝐺 1 (the graph index built on the 𝐿1 metric) as the index size of U-HNSW, because the graph index 𝐺 2 is not used (since 𝑝 ≤ 1) in this experiment. Following [20], the 𝑝 value in the query tuple (𝑞, ® 𝑝) is uniformly randomly selected from the following set: {0.5, 0.6, 0.7, 0.8, 0.9}. Table 2 clearly shows that U-HNSW significantly outperforms the idealized MLSH, achieving up to 15.0 times shorter query times while providing higher recall and requiring smaller index sizes across all six datasets. Specifically, U-HNSW achieves between 4.4 and 15.0 times shorter query times than the idealized MLSH on all datasets. Dataset Sun Trevi GIST Deep GloVe SIFT
Recall
Query Time (ms)
Index Size (MB)
U-HNSW MLSH U-HNSW MLSH U-HNSW MLSH 0.969 0.976 0.939 0.951 0.926 0.953
0.942 0.951 0.917 0.943 0.921 0.942
1.75 8.72 9.58 6.34 6.01 1.71
13.75 131.22 66.83 29.39 26.48 9.12
21.3 26.0 260.2 260.2 309.4 985.0
119.5 151.2 1525.9 1525.9 1818.4 3051.8
Table 2: Evaluation results of query times (in milliseconds), recall and index sizes (in megabytes). Numbers in boldface are the best in each group.
4.3
Comparison with the Original HNSW
In this subsection, we compare U-HNSW’s query performance with the original HNSW on ANNS-𝐿𝑝 with a fixed 𝑝 value. The goal of this subsection is to demonstrate that our U-HNSW can achieve better query performance than the original HNSW even on the ANNS-𝐿𝑝 problem, except for a few special 𝑝 values. As for the index size, U-HNSW’s index size is twice that of the original HNSW because U-HNSW uses two HNSW graph indexes (𝐺 1 and 𝐺 2 ). The evaluated 𝑝 range is [0.5, 1.9]. We report the average query performance of all query points for each 𝑝 value. Figure 4 shows the query times of U-HNSW versus those of the original HNSW for different 𝑝 values when both schemes achieve similar recall values higher than 0.9. As shown in Figure 4, query times of U-HNSW are 4.2 to 11.5 times shorter than those of the original HNSW on all datasets across a wide range of 𝑝 values, except for 𝑝 = 0.5 and 1.5. At these two values, the query times of HNSW are 1.5 to 3.4 times shorter than those of U-HNSW on all datasets except GloVe, where their query performances are comparable. This is because for 𝑝 = 0.5 and 1.5, the 𝐿0.5 and 𝐿1.5 distances can be efficiently computed using SIMD instructions as described in Section 2.1, making their computation cost close to that of the
[Short Paper] U-HNSW: An Efficient Graph-based Solution to ANNS Under Universal 𝐿𝑝 Metrics
base metric (𝐿1 or 𝐿2 ). In such a case, on the one hand, the main advantage of U-HNSW, which is to significantly reduce the number of (presumably expensive) 𝐿𝑝 distance computations, becomes blunted. On the other hand, U-HNSW still has to perform additional base-metric distance computations during the candidate generation step as described in Section 3.2. As a result, the overall query time of U-HNSW becomes longer than that of HNSW under these special 𝑝 values. For general 𝐿𝑝 metrics that do not benefit from the SIMD instructions, however, U-HNSW consistently delivers faster query performance than the original HNSW for ANNS-𝐿𝑝 queries. U-HNSW HNSW
5
0.5 0.7 0.9 1.1 1.3 1.5 1.7 1.9
20
0.5 0.7 0.9 1.1 1.3 1.5 1.7 1.9
p value
4
20
10
2
10
5
0.5 0.7 0.9 1.1 1.3 1.5 1.7 1.9
p value
(d) Deep
(c) GIST 6
30
15
p value
(b) Trevi Query time (ms)
20
0.5 0.7 0.9 1.1 1.3 1.5 1.7 1.9
p value
(a) Sun Query time (ms)
40
Query time (ms)
10
Query time (ms)
80 60 40 20
Query time (ms)
Query time (ms)
15
0.5 0.7 0.9 1.1 1.3 1.5 1.7 1.9
p value
(e) GloVe
0.5 0.7 0.9 1.1 1.3 1.5 1.7 1.9
p value
(f) SIFT
Figure 4: The query times (in milliseconds) of U-HNSW versus HNSW with different 𝑝 values across all datasets. Both methods’ recall values are nearly identical and thus omitted. U-HNSW is faster than HNSW on ANNS-𝐿𝑝 with a fixed 𝑝 value, except for 𝑝 = 0.5 or 1.5.
5
Conclusion
In this paper, we propose U-HNSW, the first graph-based solution for approximate nearest neighbor search under universal 𝐿𝑝 metrics. U-HNSW leverages two base graph indexes built on two base metrics (𝐿1 and 𝐿2 ) to generate high-recall candidates and then verifies these candidates with an early-termination strategy that substantially reduces the number of expensive 𝐿𝑝 distance computations. Experiments on multiple real-world datasets show that U-HNSW not only achieves up to 2670 times shorter query times than the original MLSH implementation running on a RAM disk (up to 15 times shorter than the idealized MLSH), but also outperforms the original HNSW on the ANNS-𝐿𝑝 problem (with a fixed 𝑝 value), except for a few special 𝑝 values.
6
Artifacts
We have uploaded the code of U-HNSW and benchmark datasets in the anonymous GitHub link: https:// anonymous.4open.science/ r/ hnsw_lp. Please refer to the README file for instructions on how to use our code.
References [1] [n. d.]. HNSWlib—fast approximate nearest neighbor search. https://github.com/ nmslib/hnswlib. [2] [n. d.]. Milvus: The High-Performance Vector Database Built for Scale. https: //milvus.io/.
EDBT ’27, April 06–09, 2027, Lille, France
[3] [n. d.]. Pinecone: The vector database for scale in production. https://www. pinecone.io/. [4] Laurent Amsaleg and Hervé Jégou. 2010. Datasets for ANN neighbor search. http://corpus-texmex.irisa.fr/. [5] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. 2004. Localitysensitive hashing scheme based on p-stable distributions. In Proceedings of the Twentieth Annual Symposium on Computational Geometry (Brooklyn, New York, USA). Association for Computing Machinery, New York, NY, USA, 253–262. [6] Wenqi Fan, Yujuan Ding, Liangbo Ning, Shijie Wang, Hengyun Li, Dawei Yin, Tat-Seng Chua, and Qing Li. 2024. A Survey on RAG Meeting LLMs: Towards Retrieval-Augmented Large Language Models. In Proceedings of the 30th ACM SIGKDD Conference (Barcelona, Spain). Association for Computing Machinery, New York, NY, USA, 6491–6501. [7] Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast approximate nearest neighbor search with the navigating spreading-out graph. Proc. VLDB Endow. 12, 5 (Jan. 2019), 461–474. [8] Jianyang Gao and Cheng Long. 2024. RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 2, 3, Article 167 (May 2024), 27 pages. doi:10.1145/3654970 [9] Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2014. Optimized Product Quantization. IEEE Trans. Pattern Anal. Mach. Intell. 36, 4 (April 2014), 744–755. doi:10.1109/TPAMI.2013.240 [10] Long Gong, Huayi Wang, Mitsunori Ogihara, and Jun Xu. 2020. iDEC: indexable distance estimating codes for approximate nearest neighbor search. Proc. VLDB Endow. 13, 9 (May 2020), 1483–1497. [11] Peter Howarth and Stefan Rüger. 2005. Fractional distance measures for contentbased image retrieval. In European Conference on Information Retrieval. Springer, 447–456. [12] Qiang Huang, Jianlin Feng, Qiong Fang, Wilfred Ng, and Wei Wang. 2017. Queryaware locality-sensitive hashing scheme for 𝑙𝑝 norm. The VLDB Journal 26, 5 (Oct. 2017), 683–708. [13] Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search. IEEE Trans. Pattern Anal. Mach. Intell. 33, 1 (Jan. 2011), 117–128. doi:10.1109/TPAMI.2010.57 [14] Benjamin Klein and Lior Wolf. 2019. End-to-end supervised product quantization for image search and retrieval. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 5041–5050. [15] Xiang-Zhen Kong, Yu Song, Jin-Xing Liu, Chun-Hou Zheng, Sha-Sha Yuan, Juan Wang, and Ling-Yun Dai. 2021. Joint 𝐿𝑝 -norm and L2, 1-norm constrained graph laplacian PCA for robust tumor sample clustering and gene network module discovery. Frontiers in Genetics 12 (2021), 621317. [16] Erwin Kreyszig. 1991. Introductory functional analysis with applications. John Wiley & Sons. [17] Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. 2019. Approximate nearest neighbor search on high dimensional data—experiments, analyses, and improvement. IEEE Transactions on Knowledge and Data Engineering 32, 8 (2019), 1475–1488. [18] Zhenxin Li, Shuibing He, Jiahao Guo, Xuechen Zhang, Xian-He Sun, and Gang Chen. 2025. CRouting: Reducing Expensive Distance Calls in Graph-Based Approximate Nearest Neighbor Search. arXiv:2509.00365 [cs.DB] https://arxiv. org/abs/2509.00365 [19] Kevin Lin, Huei-Fang Yang, Jen-Hao Hsiao, and Chu-Song Chen. 2015. Deep learning of binary hash codes for fast image retrieval. In Conf. on Comput. Vis. and Pattern Recognit. Workshops (CVPRW). IEEE, Boston, USA, 27–35. [20] Kejing Lu and Mineichi Kudo. 2021. MLSH: Mixed Hash Function Family for Approximate Nearest Neighbor Search in Multiple Fractional Metrics. In Database Systems for Advanced Applications: 26th International Conference, DASFAA 2021, Taipei, Taiwan, April 11–14, 2021, Proceedings, Part II (Taipei, Taiwan). SpringerVerlag, Berlin, Heidelberg, 569–584. [21] Kejing Lu, Mineichi Kudo, Chuan Xiao, and Yoshiharu Ishikawa. 2021. HVS: hierarchical graph structure based on voronoi diagrams for solving approximate nearest neighbor search. Proc. VLDB Endow. 15, 2 (Oct. 2021), 246–258. [22] Yu A. Malkov and D. A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence 42, 4 (2020), 824– 836. [23] Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. GloVe: Global Vectors for Word Representation. https://nlp.stanford.edu/projects/glove/. [24] Simon Winder, Matt Brown, Noah Snavely, Steven Seitz, and Richard Szeliski. 2007. Trevi: Local Image Descriptors Data. http://phototour.cs.washington.edu/ patches/default.htm. [25] Jianxiong Xiao, Krista A. Ehinger, James Hays, Antonio Torralba, and Aude Oliva. 2016. SUN Database: Exploring a Large Collection of Scene Categories. Int. J. Comput. Vision 119, 1 (Aug. 2016), 3–22. [26] Frank F. Xu, Uri Alon, and Graham Neubig. 2023. Why do nearest neighbor language models work?. In Proceedings of the 40th International Conference on Machine Learning (Honolulu, Hawaii, USA) (ICML’23). JMLR.org, Article 1596,
EDBT ’27, April 06–09, 2027, Lille, France
17 pages. [27] Yuxin Zheng, Qi Guo, Anthony K.H. Tung, and Sai Wu. 2016. LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single
Wang, Meng, and Xu
Index. In Proceedings of the 2016 International Conference on Management of Data (San Francisco, California, USA). Association for Computing Machinery, New York, NY, USA, 2023–2037.