Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 1,359 papers for “Locality-sensitive hashing”

Beyond Locality-Sensitive Hashing

Alexandr Andoni, Piotr Indyk, Huy L. Nguyên et al. · DSpace@MIT (Massachusetts Institute of Technology) · 2013

We present a new data structure for the c-approximate near neighbor problem (ANN) in the Euclidean space. For n points in ℝd, our algorithm achieves Oc(nρ + dlogn) query time and Oc(n1+ρ + dlogn) space, where ρ ≤ 7/(8c2) + O(1/c3) + oc(1). This is the first improvement over the result by Andoni and Indyk (FOCS 2006) and the first data structure that bypasses a locality-sensitive hashing lower bound proved by O'Donnell, Wu and Zhou (ICS 2011). By a standard reduction we obtain a data structure for the Hamming space and ℓ1 norm with ρ ≤ 7/(8c)+ O(1/c3/2)+ oc(1), which is the first improvement over the result of Indyk and Motwani (STOC 1998).

Cited by 79Open access

Kernelized Locality-Sensitive Hashing

Brian Kulis, Kristen Grauman · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2011

Fast retrieval methods are critical for many large-scale and data-driven vision applications. Recent work has explored ways to embed high-dimensional features or complex distance functions into a low-dimensional Hamming space where items can be efficiently searched. However, existing methods do not apply for high-dimensional kernelized data when the underlying feature embedding for the kernel is unknown. We show how to generalize locality-sensitive hashing to accommodate arbitrary kernel functions, making it possible to preserve the algorithm's sublinear time similarity search guarantees for a wide class of useful similarity functions. Since a number of successful image-based kernels have unknown or incomputable embeddings, this is especially valuable for image retrieval tasks. We validate our technique on several data sets, and show that it enables accurate and fast performance for several vision problems, including example-based object classification, local feature matching, and content-based retrieval.

Cited by 338

Efficient Distributed Locality Sensitive Hashing

Bahman Bahmani, Ashish Goel, Rajendra Shinde · arXiv (Cornell University) · 2012

Distributed frameworks are gaining increasingly widespread use in applications that process large amounts of data. One important example application is large scale similarity search, for which Locality Sensitive Hashing (LSH) has emerged as the method of choice, specially when the data is high-dimensional. At its core, LSH is based on hashing the data points to a number of buckets such that similar points are more likely to map to the same buckets. To guarantee high search quality, the LSH scheme needs a rather large number of hash tables. This entails a large space requirement, and in the distributed setting, with each query requiring a network call per hash bucket look up, this also entails a big network load. The Entropy LSH scheme proposed by Panigrahy significantly reduces the number of required hash tables by looking up a number of query offsets in addition to the query itself. While this improves the LSH space requirement, it does not help with (and in fact worsens) the search network efficiency, as now each query offset requires a network call. In this paper, focusing on the Euclidian space under $l_2$ norm and building up on Entropy LSH, we propose the distributed Layered LSH scheme, and prove that it exponentially decreases the network cost, while maintaining a good load balance between different machines. Our experiments also verify that our scheme results in a significant network traffic reduction that brings about large runtime improvement in real world applications.

Cited by 2Open access

Query-adaptative locality sensitive hashing

Laurent Amsaleg, Cordelia Schmid, Patrick Gros · 2008

HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci-entific research documents, whether they are pub-lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et a ̀ la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Cited by 0

Locality-Sensitive Hashing of Curves

Anne Driemel, Francesco Silvestri · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2017

We study data structures for storing a set of polygonal curves in R^d such that, given a query curve, we can efficiently retrieve similar curves from the set, where similarity is measured using the discrete Fréchet distance or the dynamic time warping distance. To this end we devise the first locality-sensitive hashing schemes for these distance measures. A major challenge is posed by the fact that these distance measures internally optimize the alignment between the curves. We give solutions for different types of alignments including constrained and unconstrained versions. For unconstrained alignments, we improve over a result by Indyk [SoCG 2002] for short curves. Let n be the number of input curves and let m be the maximum complexity of a curve in the input. In the particular case where m <= (a/(4d)) log n, for some fixed a>0, our solutions imply an approximate near-neighbor data structure for the discrete Fréchet distance that uses space in O(n^(1+a) log n) and achieves query time in O(n^a log^2 n) and constant approximation factor. Furthermore, our solutions provide a trade-off between approximation quality and computational performance: for any parameter k in [m], we can give a data structure that uses space in O(2^(2k) m^(k-1) n log n + nm), answers queries in O( 2^(2k) m^(k) log n) time and achieves approximation factor in O(m/k).

Cited by 35Open access

Boundary-expanding locality sensitive hashing

Qiang Wang, Zhiyuan Guo, Gang Liu et al. · 2012

Locality sensitive hashing (LSH) has been introduced as an indexing structure for fast large-scale data retrieval. A significant drawback of this technique is that a large number of hash functions require lots of hash computation time. To resolve this issue, the paper presents a new index construction algorithm called boundary-expanding LSH, where the boundary of each bucket is expanded so that each point may be mapped to multiple adjacent buckets in each hash table. The proposed algorithm can map points near to the two sides of the boundary into the same bucket, which increases the collision probability of neighbors. To achieve the same search accuracy, boundary-expanding LSH needs fewer hash tables and less hash computation time, so it can provide us a higher acceleration factor. To obtain the best performance, the paper also presents a parameter optimization method. Experiments conducted on two audio databases show its efficiency.

Cited by 4

Non-Metric Locality-Sensitive Hashing

Yadong Mu, Shuicheng Yan · Proceedings of the AAAI Conference on Artificial Intelligence · 2010

Non-metric distances are often more reasonable compared with metric ones in terms of consistency with human perceptions. However, existing locality-sensitive hashing (LSH) algorithms can only support data which are gauged with metrics. In this paper we propose a novel locality-sensitive hashing algorithm targeting such non-metric data. Data in original feature space are embedded into an implicit reproducing kernel Krein space and then hashed to obtain binary bits. Here we utilize the norm-keeping property of p-stable functions to ensure that two data's collision probability reflects their non-metric distance in original feature space. We investigate various concrete examples to validate the proposed algorithm. Extensive empirical evaluations well illustrate its effectiveness in terms of accuracy and retrieval speedup.

Cited by 70Open access

Compressing Locality Sensitive Hashing Tables

Francisco Santoyo, Edgar Chávez, Eric S. Téllez · 2013

LSH is the industry standard for proximity searching tasks on collections of data having coordinates. An LSH index applies a set of hashing functions to the representation of an object to identify proximal objects to a query, leaving distal objects apart. In other words, objects with the same hash will be mutually proximal with high probability. LSH is very fast and gives probabilistic guarantees on the quality of the results. On the other hand, mobile applications using proximity queries are becoming common place. Feature extraction can be done in a smart phone. However, the actual query rely on a wireless link because memory is a scarce resource. To tackle the above problem, we present in this paper a method to compress the LSH index while still being able to query without decompressing. The query speed is practically the same, and can even be faster. We derive a lower bound on the memory requirements for the compress representation and present an implementation using close to optimal storage. We provide an extensive experimental comparison of our compressed representation against the uncompressed one over a large database of 55 million objects. We obtained a compression ratio ranging from 70% to 80% without slowing down, in practice, the search speed.

Cited by 1

Optimal Boolean Locality-Sensitive Hashing

Tobias Christiani · arXiv (Cornell University) · 2018

For $0 \leq β&lt; α&lt; 1$ the distribution $\mathcal{H}$ over Boolean functions $h \colon \{-1, 1\}^d \to \{-1, 1\}$ that minimizes the expression \begin{equation*} ρ_{α, β} = \frac{\log(1/\Pr_{\substack{h \sim \mathcal{H} \\ (x, y) \text{ $α$-corr.}}}[h(x) = h(y)])}{\log(1/\Pr_{\substack{h \sim \mathcal{H} \\ (x, y) \text{ $β$-corr.}}}[h(x) = h(y)])} \end{equation*} assigns nonzero probability only to members of the set of dictator functions $h(x) = \pm x_i$.

Cited by 0Open access

Lower bounds on Locality Sensitive Hashing

Rajeev Motwani, et al. · 2006

Given a metric space (X, dX), c ≥ 1, r&amp;gt; 0, and p, q ∈ [0, 1], a distribution over mappings H: X → N is called a (r, cr, p, q)-sensitive hash family if any two points in X at distance at most r are mapped by H to the same value with probability at least p, and any two points at distance greater than cr are mapped by H to the same value with probability at most q.This notion was introduced by Indyk and Motwani in 1998 as the basis for an efficient approximate nearest neighbor search algorithm, and has since been used extensively for this purpose.The performance of these algorithms is governed by the parameter ρ = log(1/p) log(1/q),and constructing hash families with small ρ automatically yields improved nearest neighbor algorithms.Here we show that for X = ℓ1 it is impossible to achieve ρ ≤ 1.This al-2c most matches the construction of Indyk and Motwani which achieves ρ ≤ 1 c.

Cited by 0

Locality Sensitive Hashing in Hyperbolic Space

Chengyuan Deng, Jie Gao, K. X. Lu et al. · ArXiv.org · 2026

For a metric space $(X, d)$, a family $\mathcal{H}$ of locality sensitive hash functions is called $(r, cr, p_1, p_2)$ sensitive if a randomly chosen function $h\in \mathcal{H}$ has probability at least $p_1$ (at most $p_2$) to map any $a, b\in X$ in the same hash bucket if $d(a, b)\leq r$ (or $d(a, b)\geq cr$). Locality Sensitive Hashing (LSH) is one of the most popular techniques for approximate nearest-neighbor search in high-dimensional spaces, and has been studied extensively for Hamming, Euclidean, and spherical geometries. An $(r, cr, p_1, p_2)$-sensitive hash function enables approximate nearest neighbor search (i.e., returning a point within distance $cr$ from a query $q$ if there exists a point within distance $r$ from $q$) with space $O(n^{1+ρ})$ and query time $O(n^ρ)$ where $ρ=\frac{\log 1/p_1}{\log 1/p_2}$. But LSH for hyperbolic spaces $\mathbb{H}^d$ remains largely unexplored. In this work, we present the first LSH construction native to hyperbolic space. For the hyperbolic plane $(d=2)$, we show a construction achieving $ρ\leq 1/c$, based on the hyperplane rounding scheme. For general hyperbolic spaces $(d \geq 3)$, we use dimension reduction from $\mathbb{H}^d$ to $\mathbb{H}^2$ and the 2D hyperbolic LSH to get $ρ\leq 1.59/c$. On the lower bound side, we show that the lower bound on $ρ$ of Euclidean LSH extends to the hyperbolic setting via local isometry, therefore giving $ρ\geq 1/c^2$.

Cited by 0Open access

Locality-sensitive hashing in function spaces

Will Shand, Stephen Becker · arXiv (Cornell University) · 2020

We discuss the problem of performing similarity search over function spaces. To perform search over such spaces in a reasonable amount of time, we use {\it locality-sensitive hashing} (LSH). We present two methods that allow LSH functions on $\mathbb{R}^N$ to be extended to $L^p$ spaces: one using function approximation in an orthonormal basis, and another using (quasi-)Monte Carlo-style techniques. We use the presented hashing schemes to construct an LSH family for Wasserstein distance over one-dimensional, continuous probability distributions.

Cited by 0Open access

Locality-Sensitive Hashing for Chi2 Distance

David Gorisse, Matthieu Cord, Fŕed́eric Precioso · IEEE Transactions on Pattern Analysis and Machine Intelligence · 2011

In the past 10 years, new powerful algorithms based on efficient data structures have been proposed to solve the problem of Nearest Neighbors search (or Approximate Nearest Neighbors search). If the Euclidean Locality Sensitive Hashing algorithm, which provides approximate nearest neighbors in a euclidean space with sublinear complexity, is probably the most popular, the euclidean metric does not always provide as accurate and as relevant results when considering similarity measure as the Earth-Mover Distance and 2 distances. In this paper, we present a new LSH scheme adapted to 2 distance for approximate nearest neighbors search in high-dimensional spaces. We define the specific hashing functions, we prove their local-sensitivity, and compare, through experiments, our method with the Euclidean Locality Sensitive Hashing algorithm in the context of image retrieval on real image databases. The results prove the relevance of such a new LSH scheme either providing far better accuracy in the context of image retrieval than euclidean scheme for an equivalent speed, or providing an equivalent accuracy but with a high gain in terms of processing speed.

Cited by 97