Projekter pr. år
Abstract
We present a data structure for *spherical range reporting* on a point set S, i.e., reporting all points in S that lie within radius r of a given query point q. Our solution builds upon the LocalitySensitive Hashing (LSH) framework of Indyk and Motwani, which represents the asymptotically best solutions to near neighbor problems in high dimensions. While traditional LSH data structures have several parameters whose optimal values depend on the distance distribution from q to the points of S, our data structure is parameterfree, except for the space usage, which is configurable by the user. Nevertheless, its expected query time basically matches that of an LSH data structure whose parameters have been *optimally chosen for the data and query* in question under the given space constraints. In particular, our data structure provides a smooth tradeoff between hard queries (typically addressed by standard LSH) and easy queries such as those where the number of points to report is a constant fraction of S, or where almost all points in S are far away from the query point. In contrast, known data structures fix LSH parameters based on certain parameters of the input alone.
The algorithm has expected query time bounded by O(t(n/t)ρ), where t is the number of points to report and ρ∈(0,1) depends on the data distribution and the strength of the LSH family used. We further present a parameterfree way of using multiprobing, for LSH families that support it, and show that for many such families this approach allows us to get expected query time close to O(nρ+t), which is the best we can hope to achieve using LSH. The previously best running time in high dimensions was Ω(tnρ). For many data distributions where the intrinsic dimensionality of the point set close to q is low, we can give improved upper bounds on the expected query time.
The algorithm has expected query time bounded by O(t(n/t)ρ), where t is the number of points to report and ρ∈(0,1) depends on the data distribution and the strength of the LSH family used. We further present a parameterfree way of using multiprobing, for LSH families that support it, and show that for many such families this approach allows us to get expected query time close to O(nρ+t), which is the best we can hope to achieve using LSH. The previously best running time in high dimensions was Ω(tnρ). For many data distributions where the intrinsic dimensionality of the point set close to q is low, we can give improved upper bounds on the expected query time.
Originalsprog  Engelsk 

Titel  Proceedings of the TwentyEighth Annual ACMSIAM Symposium on Discrete Algorithms 
Antal sider  18 
Forlag  Society for Industrial and Applied Mathematics 
Publikationsdato  2017 
ISBN (Elektronisk)  9781611974782 
DOI  
Status  Udgivet  2017 
Emneord
  Spherical range reporting
  LocalitySensitive Hashing (LSH)
  Highdimensional data structures
  Query optimization
  Parameterfree algorithms
Fingeraftryk
Dyk ned i forskningsemnerne om 'Parameterfree Locality Sensitive Hashing for Spherical Range Reporting'. Sammen danner de et unikt fingeraftryk.Projekter
 1 Afsluttet

SSS: Scalable Similarity Search
Pagh, R. (PI), Christiani, T. L. (CoI), Pham, N. D. (CoI), Faithfull, A. (CoI), Silvestri, F. (CoI), Mikkelsen, J. W. (CoI), Sivertsen, J. V. T. (CoI), Aumüller, M. (CoI), Skala, M. (CoI), Ceccarello, M. (CoI), Themsen, R. (CoI), Jacob, R. (CoI), McCauley, S. (CoI) & Ahle, T. D. (CoI)
01/05/2014 → 30/04/2019
Projekter: Projekt › Forskning