Counting distance permutations. (English) Zbl 1162.68011
Summary: Distance permutation indexes support fast proximity searching in high-dimensional metric spaces. Given some fixed reference sites, for each point in a database the index stores a permutation naming the closest site, the second-closest, and so on. We examine how many distinct permutations can occur as a function of the number of sites and the size of the space. We give theoretical results for tree metrics and vector spaces with \(L_{1}, L_{2}\), and \(L_{\infty }\) metrics, improving on the previous best known storage space in the vector case. We also give experimental results and commentary on the number of distance permutations that actually occur in a variety of vector, string, and document databases.
References:
| [1] | Agarwala, R.; Bafna, V.; Farach, M.; Narayanan, B.; Paterson, M.; Thorup, M., On the approximability of numerical taxonomy (fitting distances by tree metrics), (Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’96) (1996), ACM/SIAM: ACM/SIAM Atlanta, Georgia, USA) · Zbl 0853.65014 |
| [2] | Alon, N.; Karp, R. M.; Peleg, D.; West, D. B., A graph-theoretic game and its application to the \(k\)-server problem, SIAM Journal on Computing, 24, 1, 78-100 (1995) · Zbl 0818.90147 |
| [3] | Aurenhammer, F., Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys, 23, 3 (1991) |
| [4] | Bartal, Y., Probabilistic approximations of metric spaces and its algorithmic applications, (37th Annual Symposium on Foundations of Computer Science (FOCS’96) (1996), IEEE) |
| [5] | Björner, A.; Las Vergnas, M.; Sturmfels, B.; White, N.; Ziegler, G. M., Oriented Matroids (1999), Cambridge University Press · Zbl 0944.52006 |
| [6] | Buneman, P., A note on the metric properties of trees, Journal of Combinatorial Theory, Series B, 17, 48-50 (1974) · Zbl 0286.05102 |
| [7] | Chávez, E.; Figueroa, K.; Navarro, G., Proximity searching in high dimensional spaces with a proximity preserving order, (Gelbukh, A.; de Álbornoz, A.; Terashima-Marín, H., 4th Mexican International Conference on Artificial Intelligence (MICAI’05) (2005), Springer) |
| [8] | E. Chávez, G. Navarro, Measuring the dimensionality of general metric spaces, Tech. Rep. TR/DCC-00-1, Department of Computer Science, University of Chile, 2000; E. Chávez, G. Navarro, Measuring the dimensionality of general metric spaces, Tech. Rep. TR/DCC-00-1, Department of Computer Science, University of Chile, 2000 |
| [9] | (Chávez, E.; Navarro, G., Proceedings of the 1st International Workshop on Similarity Search and Applications (SISAP’08). Proceedings of the 1st International Workshop on Similarity Search and Applications (SISAP’08), Apr. 11-12, 2008 (2008), IEEE Computer Society: IEEE Computer Society Cancún, Mexico) · Zbl 1167.90304 |
| [10] | Dress, A. W.M., Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces, Advances in Mathematics, 53, 3, 321-402 (1984) · Zbl 0562.54041 |
| [11] | Figueroa, K.; Chávez, E.; Navarro, G.; Paredes, R., On the least cost for proximity searching in metric spaces, (Àlvarez, C.; Serna, M., Experimental and Efficient Algorithms: 5th International Workshop (WEA’06) (2006), Springer) · Zbl 1196.68071 |
| [12] | Figueroa, K.; Navarro, G.; Chávez, E., Metric spaces library, online, Accessed November 24, 2007 |
| [13] | Grünbaum, B., Arrangements and Spreads, Conference Board of the Mathematical Sciences Regional Conference Series in Mathematics, vol. 10 (1971), American Mathematical Society: American Mathematical Society Providence |
| [14] | Icking, C.; Klein, R.; Lê, N.-M.; Ma, L., Convex distance functions in 3-space are different, Fundamenta Informaticae, 22, 4, 331-352 (1995) · Zbl 0815.68117 |
| [15] | Icking, C.; Klein, R.; Lê, N.-M.; Ma, L.; Santos, F., On bisectors for convex distance functions in 3-space, (11th Canadian Conference on Computational Geometry (CCCG ’99) (1999), University of British Columbia) |
| [16] | Lowe, D. G., Distinctive image features from scale-invariant keypoints, International Journal of Computer Vision, 60, 2, 91-110 (2004) |
| [17] | Lynn, B.; Prabhakaran, M.; Sahai, A., Positive results and techniques for obfuscation, (Cachin, C.; Camenisch, J., Advances in Cryptology: International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT’04) (2004), Springer: Springer Interlaken, Switzerland) · Zbl 1122.94434 |
| [18] | A. Mandel, Topology of oriented matroids, Ph.D. thesis, University of Waterloo, 1982; A. Mandel, Topology of oriented matroids, Ph.D. thesis, University of Waterloo, 1982 |
| [19] | Matoušek, J., On embedding trees into uniformly convex Banach spaces, Israel Journal of Mathematics, 114, 1, 221-237 (1999) · Zbl 0948.46011 |
| [20] | Micó, L.; Oncina, J.; Vidal, E., A new version of the nearest-neighbour approximating and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements, Pattern Recognition Letters, 15, 1, 9-17 (1994) |
| [21] | Ott, E., Chaos in Dynamical Systems (2002), Cambridge University Press: Cambridge University Press Cambridge, UK · Zbl 1006.37001 |
| [22] | Paredes, R.; Chávez, E., Using the \(k\)-nearest neighbor graph for proximity searching in metric spaces, (Consens, M. P.; Navarro, G., String Processing and Information Retrieval, 12th International Conference (SPIRE’05) (2005), Springer) |
| [23] | Price, D. J., Some unusual series occurring in \(n\)-dimensional geometry, The Mathematical Gazette, 30, 149-150 (1946) |
| [24] | Sahlgren, M., The word-space model, Ph.D. thesis, Stockholm University, 2006 |
| [25] | Santos, F., On Delaunay oriented matroids for convex distance functions, Discrete & Computational Geometry, 16, 2, 197-210 (1996) · Zbl 0879.52008 |
| [26] | Skala, M., Measuring the difficulty of distance-based indexing, (Consens, M. P.; Navarro, G., String Processing and Information Retrieval: 12th International Conference (SPIRE’05) (2005), Springer) |
| [27] | M. Skala, Counting distance permutations, in: Chávez and Navarro [9]; M. Skala, Counting distance permutations, in: Chávez and Navarro [9] · Zbl 1162.68011 |
| [28] | Skala, M. A., Aspects of metric spaces in computation, Ph.D. thesis, University of Waterloo, 2008 |
| [29] | Uhlmann, J. K., Satisfying general proximity/similarity queries with metric trees, Information Processing Letters, 40, 175-179 (1991) · Zbl 0748.68088 |
| [30] | Vidal Ruiz, E., An algorithm for finding nearest neighbors in (approximately) constant time, Pattern Recognition Letters, 4, 145-157 (1986) |
| [31] | Yianilos, P. N., Data structures and algorithms for nearest neighbor search in general metric spaces, (Fourth Annual ACM/SIGACT-SIAM (1993), Symposium on Discrete Algorithms (SODA’93): Symposium on Discrete Algorithms (SODA’93) ACM/SIAM) · Zbl 0801.68037 |
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.
