Document Open Access Logo

Simultaneous Nearest Neighbor Search

Authors Piotr Indyk, Robert Kleinberg, Sepideh Mahabadi, Yang Yuan

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.44.pdf
  • Filesize: 2.48 MB
  • 15 pages

Document Identifiers

Author Details

Piotr Indyk
Robert Kleinberg
Sepideh Mahabadi
Yang Yuan

Cite As Get BibTex

Piotr Indyk, Robert Kleinberg, Sepideh Mahabadi, and Yang Yuan. Simultaneous Nearest Neighbor Search. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.44

Abstract

Motivated by applications in computer vision and databases, we introduce and study the Simultaneous Nearest Neighbor Search (SNN) problem. Given a set of data points, the goal of SNN is to design a data structure that, given a collection of queries, finds a collection of close points that are compatible with each other. Formally, we are given k query points Q=q_1,...,q_k, and a compatibility graph G with vertices in Q, and the goal is to return data points p_1,...,p_k that minimize (i) the weighted sum of the distances from q_i to p_i and (ii) the weighted sum, over all edges (i,j) in the compatibility graph G, of the distances between p_i and p_j. The problem has several applications in computer vision and databases, where one wants to return a set of *consistent* answers to multiple related queries. Furthermore, it generalizes several well-studied computational problems, including Nearest Neighbor Search, Aggregate Nearest Neighbor Search and the 0-extension problem.

In this paper we propose and analyze the following general two-step method for designing efficient data structures for SNN. In the first step, for each query point q_i we find its (approximate) nearest neighbor point p'_i; this can be done efficiently using existing approximate nearest neighbor structures. In the second step, we solve an off-line optimization problem over sets q_1,...,q_k and p'_1,...,p'_k; this can be done efficiently given that k is much smaller than n. Even though p'_1,...,p'_k  might not constitute the optimal answers to queries q_1,...,q_k, we show that, for the unweighted case, the resulting algorithm satisfies a O(log k/log log k)-approximation guarantee. Furthermore, we show that the approximation factor can be in fact reduced to a constant for compatibility graphs frequently occurring in practice, e.g., 2D grids, 3D grids or planar graphs. 

Finally, we validate our theoretical results by preliminary experiments. In particular, we show that the empirical approximation factor provided by the above approach is very close to 1.

Subject Classification

Keywords
  • Approximate Nearest Neighbor
  • Metric Labeling
  • 0-extension
  • Simultaneous Nearest Neighbor
  • Group Nearest Neighbor

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Pankaj K Agarwal, Alon Efrat, and Wuzhou Zhang. Nearest-neighbor searching under uncertainty. In Proceedings of the 32nd symposium on Principles of database systems. ACM, 2012. Google Scholar
  2. Alexandr Andoni, Piotr Indyk, Huy L Nguyen, and Ilya Razenshteyn. Beyond locality-sensitive hashing. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1018-1028. SIAM, 2014. Google Scholar
  3. Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, and Éva Tardos. Approximate classification via earthmover metrics. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1079-1087. Society for Industrial and Applied Mathematics, 2004. Google Scholar
  4. Sunil Arya, David M Mount, Nathan S Netanyahu, Ruth Silverman, and Angela Y Wu. An optimal algorithm for approximate nearest neighbor searching fixed dimensions. Journal of the ACM (JACM), 45(6):891-923, 1998. Google Scholar
  5. Connelly Barnes, Eli Shechtman, Adam Finkelstein, and Dan Goldman. Patchmatch: A randomized correspondence algorithm for structural image editing. ACM Transactions on Graphics-TOG, 28(3):24, 2009. Google Scholar
  6. Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18(9):509-517, 1975. Google Scholar
  7. Yuri Boykov and Vladimir Kolmogorov. An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 26(9):1124-1137, 2004. Google Scholar
  8. Yuri Boykov, Olga Veksler, and Ramin Zabih. Fast approximate energy minimization via graph cuts. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 23(11):1222-1239, 2001. Google Scholar
  9. Gruia Calinescu, Howard Karloff, and Yuval Rabani. Approximation algorithms for the 0-extension problem. SIAM Journal on Computing, 34(2):358-372, 2005. Google Scholar
  10. Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, and Kunal Talwar. An improved approximation algorithm for the 0-extension problem. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 257-265. Society for Industrial and Applied Mathematics, 2003. Google Scholar
  11. Pedro Felzenszwalb, William Freeman, Piotr Indyk, Robert Kleinberg, and Ramin Zabih. Bigdata: F: Dka: Collaborative research: Structured nearest neighbor search in high dimensions, 2015. URL: http://cs.brown.edu/~pff/SNN/.
  12. Pedro F Felzenszwalb and Daniel P Huttenlocher. Efficient belief propagation for early vision. International journal of computer vision, 70(1):41-54, 2006. Google Scholar
  13. Pedro F Felzenszwalb, Gyula Pap, Eva Tardos, and Ramin Zabih. Globally optimal pixel labeling algorithms for tree metrics. In Computer Vision and Pattern Recognition (CVPR), 2010 IEEE Conference on, pages 3153-3160. IEEE, 2010. Google Scholar
  14. William T Freeman, Thouis R Jones, and Egon C Pasztor. Example-based super-resolution. Computer Graphics and Applications, IEEE, 22(2):56-65, 2002. Google Scholar
  15. Anupam Gupta, Robert Krauthgamer, and James R Lee. Bounded geometries, fractals, and low-distortion embeddings. In Foundations of Computer Science, 2003. Proceedings. 44th Annual IEEE Symposium on, pages 534-543. IEEE, 2003. Google Scholar
  16. Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pages 604-613. ACM, 1998. Google Scholar
  17. Howard Karloff, Subhash Khot, Aranyak Mehta, and Yuval Rabani. On earthmover distance, metric labeling, and 0-extension. SIAM Journal on Computing, 39(2):371-387, 2009. Google Scholar
  18. Alexander V Karzanov. Minimum 0-extensions of graph metrics. European Journal of Combinatorics, 19(1):71-101, 1998. Google Scholar
  19. Jon Kleinberg and Eva Tardos. Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields. Journal of the ACM (JACM), 49(5):616-639, 2002. Google Scholar
  20. Tsvi Kopelowitz and Robert Krauthgamer. Faster clustering via preprocessing. arXiv preprint arXiv:1208.5247, 2012. Google Scholar
  21. Robert Krauthgamer and James R Lee. Navigating nets: simple algorithms for proximity search. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, pages 798-807. Society for Industrial and Applied Mathematics, 2004. Google Scholar
  22. Eyal Kushilevitz, Rafail Ostrovsky, and Yuval Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. SIAM Journal on Computing, 30(2):457-474, 2000. Google Scholar
  23. James R Lee and Assaf Naor. Metric decomposition, smooth measures, and clustering. Preprint, 2004. Google Scholar
  24. Feifei Li, Bin Yao, and Piyush Kumar. Group enclosing queries. Knowledge and Data Engineering, IEEE Transactions on, 23(10):1526-1540, 2011. Google Scholar
  25. Yang Li, Feifei Li, Ke Yi, Bin Yao, and Min Wang. Flexible aggregate similarity search. In Proceedings of the 2011 ACM SIGMOD international conference on management of data, pages 1009-1020. ACM, 2011. Google Scholar
  26. David R Martin, Charless C Fowlkes, and Jitendra Malik. Learning to detect natural image boundaries using local brightness, color, and texture cues. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 26(5):530-549, 2004. Google Scholar
  27. Man Lung Yiu, Nikos Mamoulis, and Dimitris Papadias. Aggregate nearest neighbor queries in road networks. Knowledge and Data Engineering, IEEE Transactions on, 17(6):820-833, 2005. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact