Diverse near neighbor problem
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...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/87000 https://orcid.org/0000-0001-5004-8991 https://orcid.org/0000-0002-7983-9524 |
| _version_ | 1826190149693734912 |
|---|---|
| author | Abbar, Sofiane Amer-Yahia, Sihem Indyk, Piotr Mahabadi, Sepideh Varadarajan, Kasturi R. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Abbar, Sofiane Amer-Yahia, Sihem Indyk, Piotr Mahabadi, Sepideh Varadarajan, Kasturi R. |
| author_sort | Abbar, Sofiane |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T08:35:48Z |
| format | Article |
| id | mit-1721.1/87000 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T08:35:48Z |
| publishDate | 2014 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/870002022-09-23T13:08:42Z Diverse near neighbor problem Abbar, Sofiane Amer-Yahia, Sihem Indyk, Piotr Mahabadi, Sepideh Varadarajan, Kasturi R. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Indyk, Piotr Mahabadi, Sepideh 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. Charles Stark Draper Laboratory National Science Foundation (U.S.) (Award NSF CCF-1012042) David & Lucile Packard Foundation 2014-05-15T17:09:36Z 2014-05-15T17:09:36Z 2013-06 Article http://purl.org/eprint/type/ConferencePaper 9781450320313 http://hdl.handle.net/1721.1/87000 Sofiane Abbar, Sihem Amer-Yahia, Piotr Indyk, Sepideh Mahabadi, and Kasturi R. Varadarajan. 2013. Diverse near neighbor problem. In Proceedings of the twenty-ninth annual symposium on Computational geometry (SoCG '13). ACM, New York, NY, USA, 207-214. https://orcid.org/0000-0001-5004-8991 https://orcid.org/0000-0002-7983-9524 en_US http://dx.doi.org/10.1145/2462356.2462401 Proceedings of the 29th annual symposium on Symposuim on computational geometry (SoCG '13) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) MIT web domain |
| spellingShingle | Abbar, Sofiane Amer-Yahia, Sihem Indyk, Piotr Mahabadi, Sepideh Varadarajan, Kasturi R. Diverse near neighbor problem |
| title | Diverse near neighbor problem |
| title_full | Diverse near neighbor problem |
| title_fullStr | Diverse near neighbor problem |
| title_full_unstemmed | Diverse near neighbor problem |
| title_short | Diverse near neighbor problem |
| title_sort | diverse near neighbor problem |
| url | http://hdl.handle.net/1721.1/87000 https://orcid.org/0000-0001-5004-8991 https://orcid.org/0000-0002-7983-9524 |
| work_keys_str_mv | AT abbarsofiane diversenearneighborproblem AT ameryahiasihem diversenearneighborproblem AT indykpiotr diversenearneighborproblem AT mahabadisepideh diversenearneighborproblem AT varadarajankasturir diversenearneighborproblem |