Metric spaces with expensive distances. (English) Zbl 1508.68387
Summary: In algorithms for finite metric spaces, it is common to assume that the distance between two points can be computed in constant time, and complexity bounds are expressed only in terms of the number of points of the metric space. We introduce a different model, where we assume that the computation of a single distance is an expensive operation and consequently, the goal is to minimize the number of such distance queries. This model is motivated by metric spaces that appear in the context of topological data analysis.
We consider two standard operations on metric spaces, namely the construction of a \((1+\varepsilon)\)-spanner and the computation of an approximate nearest neighbor for a given query point. In both cases, we partially explore the metric space through distance queries and infer lower and upper bounds for yet unexplored distances through triangle inequality. For spanners, we evaluate several exploration strategies through extensive experimental evaluation. For approximate nearest neighbors, we prove that our strategy returns an approximate nearest neighbor after a logarithmic number of distance queries.
We consider two standard operations on metric spaces, namely the construction of a \((1+\varepsilon)\)-spanner and the computation of an approximate nearest neighbor for a given query point. In both cases, we partially explore the metric space through distance queries and infer lower and upper bounds for yet unexplored distances through triangle inequality. For spanners, we evaluate several exploration strategies through extensive experimental evaluation. For approximate nearest neighbors, we prove that our strategy returns an approximate nearest neighbor after a logarithmic number of distance queries.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 51K05 | General theory of distance geometry |
References:
| [1] | Edelsbrunner, H., Letscher, D. and Zomorodian, A., Topological persistence and simplification, Discret. Comput. Geom.28 (2002) 511. · Zbl 1011.68152 |
| [2] | Biasotti, S., Giorgi, D., Spagnuolo, M. and Falcidieno, B., Reeb graphs for shape analysis and applications, Theoret. Comput. Sci.392 (2008) 5, Computational Algebraic Geometry and Applications. · Zbl 1134.68064 |
| [3] | Cohen-Steiner, D., Edelsbrunner, H. and Harer, J., Stability of persistence diagrams, Discret. Comput. Geom.37 (2007) 103. · Zbl 1117.54027 |
| [4] | Bauer, U., Ge, X. and Wang, Y., Measuring distance between reeb graphs, in Proc. 30th Ann. Symp. Computational Geometry (ACM, 2014), p. 464. · Zbl 1395.68288 |
| [5] | De Silva, V., Munch, E. and Patel, A., Categorified reeb graphs, Discret. Comput. Geom.55 (2016) 854. · Zbl 1350.68271 |
| [6] | Di Fabio, B. and Landi, C., The edit distance for reeb graphs of surfaces, Discret. Comput. Geom.55 (2016) 423. · Zbl 1332.05038 |
| [7] | Rubner, Y., Tomasi, C. and Guibas, L. J., The earth mover’s distance as a metric for image retrieval, Int. J. Comput. Vision40 (2000) 99. · Zbl 1012.68705 |
| [8] | Shirdhonkar, S. and Jacobs, D. W., Approximate earth mover’s distance in linear time, in 2008 IEEE Conference on Computer Vision and Pattern Recognition (IEEE, 2008), pp. 1-8. |
| [9] | Pele, O. and Werman, M., Fast and robust earth mover’s distances, in 2009 IEEE 12th Int. Conf. Computer Vision (2009), pp. 460-467. |
| [10] | Cuturi, M., Sinkhorn distances: Lightspeed computation of optimal transport, in Advances in Neural Information Processing Systems (2013), pp. 2292-2300. |
| [11] | Har-Peled, S. and Mendel, M., Fast construction of nets in low dimensional metrics and their applications, SIAM J. Comput.35 (2006) 1148. · Zbl 1100.68014 |
| [12] | Callahan, P. B. and Kosaraju, S. R., A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields, J. ACM42 (1995) 67. · Zbl 0886.68078 |
| [13] | Krauthgamer, R. and Lee, J. R., The black-box complexity of nearest-neighbor search, Theoret. Comput. Sci.348 (2005) 262. · Zbl 1081.68013 |
| [14] | Althöfer, I., Das, G., Dobkin, D., Joseph, D. and Soares, J., On sparse spanners of weighted graphs, Discret. Comput. Geom.9 (1993) 81. · Zbl 0762.05039 |
| [15] | Callahan, P. B. and Kosaraju, S. R., A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields, J. ACM (JACM)42 (1995) 67. · Zbl 0886.68078 |
| [16] | Beygelzimer, A., Kakade, S. and Langford, J., Cover trees for nearest neighbor, in Proc. 23rd Int. Conf. Machine Learning (ACM, New York, NY, USA, 2006), ICML ’06, pp. 97-104. |
| [17] | Farshi, M. and Gudmundsson, J., Experimental study of geometric \(t\)-spanners, J. Experimental Algorithmics (JEA)14 (2009) 3. · Zbl 1284.68716 |
| [18] | Har-Peled, S., Geometric Approximation Algorithms, Vol. 173 (American Mathematical Soc., 2011). · Zbl 1230.68215 |
| [19] | Zhang, J., Siddiqi, K., Macrini, D., Shokoufandeh, A. and Dickinson, S., Retrieving articulated 3D models using medial surfaces and their graph spectra, in International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition (Springer, 2005), pp. 285-300. |
| [20] | Bauer, U., Kerber, M. and Reininghaus, J., Distributed computation of persistent homology, in 2014 Proc. 16th Workshop on Algorithm Engineering and Experiments (ALENEX) (SIAM, 2014), pp. 31-38. · Zbl 1429.68328 |
| [21] | Kerber, M., Morozov, D. and Nigmetov, A., Geometry helps to compare persistence diagrams, J. Experimental Algorithmics (JEA)22 (2017) 1. · Zbl 1414.68129 |
| [22] | G. Doran, PyEMD: Earth mover’s distance for Python, 2014-, [Online; accessed]. |
| [23] | Fei-Fei, L., Fergus, R. and Perona, P., Learning generative visual models from few training examples: An incremental bayesian approach tested on 101 object categories, in 2004 Conf. Comput. Vision and Pattern Recognition Workshop (IEEE, 2004), pp. 178-178. |
| [24] | Seidel, R., Backwards analysis of randomized geometric algorithms, in New Trends in Discrete and Computational Geometry, ed. Pach, J. (Springer, 1993). · Zbl 0834.68122 |
| [25] | Kleinberg, J., Slivkins, A. and Wexler, T., Triangulation and embedding using small sets of beacons, J. ACM (JACM)56 (2009) 1. · Zbl 1325.68030 |
| [26] | Stallkamp, J., Schlipsing, M., Salmen, J. and Igel, C., Man vs. computer: Benchmarking machine learning algorithms for traffic sign recognition, Neural Netw.32 (2012) 323. |
| [27] | Smid, M., Efficient Algorithms (Springer-Verlag, Berlin, Heidelberg, 2009), ch. The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension, pp. 275-289. · Zbl 1257.05053 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
