Conference proceeding
Diverse Near Neighbor Problem
Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG), pp.207-214
SoCG 2013 - Symposium on Computational Geometry
06/17/2013
DOI: 10.1145/2462356.2462401
Abstract
Motivated by the recent research on diversity-aware search, we investigate the k-diverse near neighbor reporting problem. The problem is defined as follows: given a query point q, report the maximum diversity set S of k points in the ball of radius r around q. The diversity of a set S is measured by the minimum distance between any pair of points in S (the higher, the better). We present two approximation algorithms for the case where the points live in a d-dimensional Hamming space. Our algorithms guarantee query times that are sub-linear in n and only polynomial in the diversity parameter k, as well as the dimension d. For low values of k, our algorithms achieve sub-linear query times even if the number of points within distance r from a query q is linear in n. To the best of our knowledge, these are the first known algorithms of this type that offer provable guarantees.
Details
- Title: Subtitle
- Diverse Near Neighbor Problem
- Creators
- Sofiane Abbar - Qatar Computing Research InstituteSihem Amer-Yahia - Centre National de la Recherche ScientifiquePiotr Indyk - Massachusetts Institute of TechnologySepideh Mahabadi - Massachusetts Institute of TechnologyKasturi Varadarajan - University of Iowa
- Resource Type
- Conference proceeding
- Publication Details
- Proceedings of the 29th Annual Symposium on Computational Geometry (SoCG), pp.207-214
- Conference
- SoCG 2013 - Symposium on Computational Geometry
- DOI
- 10.1145/2462356.2462401
- Publisher
- ACM
- Language
- English
- Date published
- 06/17/2013
- Academic Unit
- Computer Science
- Record Identifier
- 9984259421002771
Metrics
10 Record Views