Metric measure

The fact that a measure is a metric allows optimizations in many applications. For example, many efficient algorithms for searching shortest paths in graphs, such as Dijkstra’s algorithm, make use of the fact that the underlying measure is a metric.

$d: U \times U \rightarrow R^+ \cup \{0\}$ is called metric if the following holds:

• $d(x,y) \geq 0$ non-negativity
• $d(x,y) = d(y,x)$ symmetry
• $x = y \Leftrightarrow d(x,y) = 0$ identity
• $d(x,z) \leq d(x,y) + d(y,z)$ triangle inequality

Metric measure sometimes called (mathematical) distance. But not every string measure which is historically called “distance” is a metric, so it’s better to use word metric to avoid confusion.

Minkowski distance

Minkowski distance is an example of metric measure (not typically used as string measure though, given here as an example)

$$D\left(X,Y\right) = \left(\sum_{i=1}^n |x_i-y_i|^p\right)^{\frac{1}{p}}$$

where $X = (x_1,x_2,\ldots,x_n) \text{ and } Y = (y_1,y_2,\ldots,y_n) \in R^n$. For $p \geq 1$ , the Minkowski distance is a metric.

• $p = 1$ Manhattan distance
• $p = 2$ Euclidean distance
• $p \rightarrow \infty$ Chebyshev distance

Indexing metric spaces

from Exploring intersection trees for indexing metric spaces ↗

Data Structure	Space Complexity	Construction Complexity	Claimed Query Complexity	Extra CPU Query Time
BKT1	$n$ ptrs	$n \log n$	$n^α$	—
FQT2	$n \ldots n \log n$ ptrs	$n \log n$	$n^α$	—
FHQT3	$n \ldots nh$ ptrs	$nh$	$\log n^b$	$n^α$
FQA4	$nhb$ bits	$nh$	$log n^b$	$n^α \log n$
VPT5	$n$ ptrs	$n \log n$	$\log n^c$	—
MVPT6	$n$ ptrs	$n \log n$	$\log n^c$	—
VPF7	$n$ ptrs	$n^{2−α}$	$n^{1−α} \log n^c$	—
BST8	$n$ ptrs	$n\log n$	not analyzed	—
GHT9	$n$ ptrs	$n\log n$	not analyzed	—
GNAT10	$nm^2$ dsts	$nm \log_m n$	not analyzed	—
VT11	$n$ ptrs	$n\log n$	not analyzed	—
MT12	$n$ ptrs	$n(m \ldots m^2) \log_m n$	not analyzed	—
SAT13	$n$ ptrs	$n \log n / \log \log n$	$n^{1− \Theta(1 / \log \log n)}$	—
AESA14	$n^2$ dsts	$n^2$	$O(1)^d$	$n\ldots n^2$
LAESA15	$kn$ dsts	$kn$	$k + O(1)^d$	$\log n \ldots kn$
LC16	$n$ ptrs	$n^2/m$	not analyzed	$n/m$

from Searching in Metric Spaces ↗

Category	Index	Storage	Distance Domain
Pivot-based tables	AESA14, LAESA15, EPT, CPT	Main-memory	Continuous
Pivot-based trees	BKT1, FQT2, FQA4	Main-memory	Discrete
	VPT5, MVPT6	Main-memory	Continuous
Pivot-based external indexes	PM-tree, Omni-family, M-index, SPB-tree	Disk	Continuous

from Pivot-based Metric Indexing ↗

Method		P17	BS18	VP19	GH20	MW21	D22	CPU23	I/O24
AESA14	25, 26, 27	•
AHC	28	•		•				•
Antipole Tree	29	•	•		◦	◦		•
BS-Tree	30		•		◦		•	•
BU-Tree	31		•		◦			•
CM-Tree	32	•	•		◦	•	•	•	•
DBM-Tree	33, 34	◦	•		◦	•	•	•	•
DF-Tree	35	•	•		◦	•	•	•	•
D-Index	36, 37, 38, 39	•		•		•	◦	•	•
DSA-Tree	40, 41, 42				•	•	•	•	◦
EGNAT	43	◦		•	◦	•	•	•	•
EHC	28			•		◦		•
EM-VP-Forest	44			•				•
GH-Tree	45, 46				•		•	•
GNAT10	47			•	◦	•		•
HC	28, 48			•				•
HSA-Tree	49, 50, 51	•			•	•	•	•	◦
iAESA	52	•
iDistance	53	◦	•		◦	•	•	•	•
LAESA15	54, 55, 25, 56	•					•		◦
LC16	57, 58			•				•	◦
Linear Scan	59						•
MB+-Tree	60			•		•	•	•	•
MB∗-Tree	61, 62		•		◦			•
M∗-Tree	63	•	•		◦	•	•	•	•
M-Tree12	64, 65, 66	◦	•		◦	•	•	•	•
MVP-Tree6	67, 68	•		•		•	•	•	•
OMNI	69	•					•	•	•
Opt-VP-Tree	70			•		•	•	•	•
PM∗-Tree	63	•	•		◦	•	•	•	•
PM-Tree	71	•	•		◦	•	•	•	•
ROAESA	72	•						•
SA-Tree	73, 74				•	•		•
Slim-Tree	75, 76		•		◦	•	•	•	•
Spaghettis	77	•					•	•
SSS-Tree	78		•		•	•		•
SSS-LC	79	•		•			◦	•	•
TLAESA	80, 81	•					•	•
Voronoi-Tree11	82		•		◦	◦	•	•
VP-Tree5	45, 46, 83			•				•

from The Basic Principles of Metric Indexing ↗

Index	Category	Space Cost	Construction Cost
BST [78], MBST [106]	CP-Index	$O(ns)$	$\Omega(n \log_2 n)$
VT [53, 54]	CP-Index	$O(ns)$	$\Omega(n \log_3 n)$
BU-Tree [83]	CP-Index	$O(ns + n^2)$	$O(n^3)$
GHT [139]	CP-Index	$O(ns)$	$\Omega(n \log_2 n)$
GNAT [23], EGNAT [87, 105]	Hybrid	$O(ns + nm)$	$\Omega(nm \log_m n)$
SAT [32, 97, 98]	CP-Index	$O(ns)$	$O(n\log^2n/\log\log n)$
DSAT [100–104]	CP-Index	$O(ns)$	$O(mn\log_mn)$
DSACLT [15, 24]	CP-Index	$O(ns)$	$O(mn\log_mn/k)$
kNNG [110]	CP-Index	$O(ns + nk)$	$O(n^2)$
M-tree [42, 46, 128]	CP-Index	$O(ns + ns/m)$	$O(n(m..m^2)\log_m n)$
PM-tree [130]	Hybrid	$O(n(s+l)+n(s+l)/m+ls)$	$O(n(m..m^2)\log_m n+nl\log_m n)$
LC [33, 34], DLC [104]	CP-Index	$O(ns)$	$O(n^2/m)$
HC [62, 63]	CP-Index	$O(ns)$	$O(n\log_2n/m)$
D-index [55, 56, 150]	Hybrid	$O(ns + nl + ls)$	$O(nl)$
MB+-Tree [75]	CP-Index	$O((n+n/m)(s+\log_2 n/m+log_2 n_d))$	$O(n\log_2n/m+nm\log_mn)$
AESA [119], ROAESA [144], iAESA [58, 59]	P-Index	$O(ns + n^2)$	$O(n^2)$
LAESA [91]	P-Index	$O(ns+ls+nl)$	$O(nl)$
TLAESA [90, 134]	Hybrid	$O(ns+ls+nl)$	$\Omega(n\log_2n+nl)$
EPT [120]	P-Index	$O(ns+lgs+nl)$	$O(nlg)$
EPT∗[39]	P-Index	$O(ns+l_cs+nl)$	$O(nll_cn_s)$
CPT [94]	P-Index	$O(ns+ns/m+ls+nl)$	$O(n(m..m^2)\log_m n+nl)$
BKT [25], FQT [14]	P-Index	$O(ns + ln_d)$	$O(nl)$
FHQT [13], FQA [35]	P-Index	$O(ns + nl)$	$O(nl)$
VPT [138, 139, 149], DVPT [64]	P-Index	$O(ns)$	$O(n\log_2n)$
MVPT [20, 21]	P-Index	$O(ns)$	$O(n\log_mn)$
Omni-family [22, 136]	P-Index	$O(ns+nl+nl/m+ls)$	$O(nml\log_mn)$
SPB-tree [36, 37]	P-Index	$O(ns+n+n/m+ls)$	$O(n(l^2..l^3) + n(m+l)\log_mn)$
M-index [107]	Hybrid	$O(ns+nl+n+n/m+ls)$	$\Omega(nl\log_ln/m) + O(nm\log_mn)$
M-index∗[39]	Hybrid	$O(ns+nl+n+n/m+nl/m+ls)$	$\Omega(nl\log_ln/m) + O(nm\log_mn)$

Partitioning Technique	Index	Storage	Scalability
Generalized hyperplane partitioning	GHT, GNAT	Main-memory	Static
	EGNAT	Secondary-memory	Dynamic
	kNNG	Main-memory	Dynamic
	M-index(∗)	Secondary-memory	Dynamic
Ball partitioning	M-tree and PM-tree	Secondary-memory	Dynamic
	LC, DLC, HC	Secondary-memory	Dynamic
Hash partitioning	D-index	Secondary-memory	Dynamic
	MB+-tree	Secondary-memory	Dynamic
Hybrid partitioning	BST, MBST, VT, BU-tree	Main-memory	Static
	SAT	Main-memory	Static
	DSAT, DSACLT	Secondary-memory	Dynamic
	TLAESA	Main-memory	Static

Category	Index	Storage	Scalability
Pivot-based tables	AESA, ROAESA, iAESA	Main-memory	Dynamic
	LAESA	Main-memory	Dynamic
	EPT	Main-memory	Dynamic
	CPT	Secondary-memory	Dynamic
Pivot-based trees	BKT	Main-memory	Dynamic
	FQT, FHQT, FQA	Main-memory	Dynamic
	TLAESA	Main-memory	Static
	GNAT	Main-memory	Static
	VPT, MVPT	Main-memory	Static
	DVPT	Main-memory	Dynamic
Pivot-based secondary-memory indexes	PM-tree	Secondary-memory	Dynamic
	EGNAT	Secondary-memory	Dynamic
	D-index	Secondary-memory	Dynamic
	Omni-family	Secondary-memory	Dynamic
	M-index(∗)	Secondary-memory	Dynamic
	SPB-tree	Secondary-memory	Dynamic

from Indexing Metric Spaces for Exact Similarity Search ↗

Other

• Indexing Structures for Searching in Metric Space ↗
• DIMS: Distributed Index for Similarity Search in Metric Spaces ↗
• Adaptive Vantage Tree. Adaptive Indexing in High-Dimensional Metric Spaces ↗
• GiST: A Generalized Search Tree for Secondary Storage ↗ (related to M-tree?)

---

Footnotes

1. Burkhard–Keller Tree ↩ ↩²

2. A further development over BKTs is the fixed queries tree ↩ ↩²

3. fixedheight FQT ↩

4. fixed queries array ↩ ↩²

5. vantage-point trees ↩ ↩² ↩³

6. multi-vantage-point tree ↩ ↩² ↩³

7. excluded middle vantage point forest ↩

8. bisector trees ↩

9. generalized-hyperplane tree ↩

10. The GHT is extended to an m-ary tree. Geometric near-neighbor access tree ↩ ↩²

11. Voronoi tree ↩ ↩²

12. M-tree ↩ ↩²

13. spatial approximation tree ↩

14. approximating eliminating search algorithm ↩ ↩² ↩³

15. linear AESA ↩ ↩² ↩³

16. list of clusters ↩ ↩²

17. The structural properties indicate the use of pivoting ↩

18. BS-style ball partitioning ↩

19. VP-style ball partitioning ↩

20. generalized hyperplane partitioning ↩

21. and multiway partitioning ↩

22. The functional features indicate whether the method is dynamic ↩

23. whether it is designed to reduce extra CPU cost ↩

24. or memory use and/or disk accesses ↩

25. Juan Ramón Rico-Juan and Luisa Micó. Comparison of AESA and LAESA search algorithms using string and tree-edit-distances. Pattern Recognition Letters, 24(9–10):1417–1426, 2002. ↩ ↩²

26. Enrique Vidal. New formulation and improvements of the nearestneighbour approximating and eliminating search algorithm (AESA). Pattern Recognition Letters, 15(1):1–7, January 1994. ↩

27. Enrique Vidal Ruiz. An algorithm for finding nearest neighbours in (approximately) constant average time. Pattern Recognition Letters, 4(3): 145–157, 1986. ↩

28. Kimmo Fredriksson. Engineering efficient metric indexes. Pattern Recognition Letters, 2006. ↩ ↩² ↩³

29. Domenico Cantone, Alfredo Ferro, Alfredo Pulvirenti, Diego Reforgiato Recupero, and Dennis Shasha. Antipole tree indexing to support range search and k-nearest neighbor search in metric spaces. IEEE Transactions on Knowledge and Data Engineering, 17(4):535–550, April 2005. ↩

30. Iraj Kalantari and Gerard McDonald. A data structure and an algorithm for the nearest point problem. IEEE Transactions on Software Engineering, 9(5):631–634, 1983. ↩

31. Bing Liu, Zhihui Wang, Xiaoming Yang, Wei Wang, and Baile Shi. A bottom-up distance-based index tree for metric space. In Rough Sets and Knowledge Technology, volume 4062 of Lecture Notes in Computer Science, pages 442–449. Springer, 2006. ↩

32. Lior Aronovich and Israel Spiegler. Efficient similarity search in metric databases using the CM-tree. Data & Knowledge Engineering, 2007. ↩

33. Marcos R. Vieira, Caetano Traina Jr., Fabio Jun Takada Chino, and Agma J. M. Traina. DBM-tree: a dynamic metric access method sensitive to local density data. In Proceedings of the 19th Brazilian Symposium on Databases (SBBD). UnB, 2004. ↩

34. Marcos R. Vieira, Caetano Traina Jr., Fabio Jun Takada Chino, and Agma Juci Machado Traina. DBM-tree: trading height-balancing for performance in metric access methods. Journal of the Brazilian Computer Society, 11(3):20–39, 2006. ↩

35. Caetano Traina Jr., Agma Traina, Roberto Figueira Santos Filho, and Christos Faloutsos. How to improve the pruning ability of dynamic metric access methods. In Proceedings of the eleventh international conference on Information and knowledge management, pages 219–226, 2002. ↩

36. Vlastislav Dohnal. An access structure for similarity search in metric spaces. In Wolfgang Lindner, Marco Mesiti, Can T¨urker, Yannis Tzitzikas, and Athena Vakali, editors, EDBT Workshops, volume 3268 of Lecture Notes In Computer Science, pages 133–143. Springer, 2004. ↩

37. Vlastislav Dohnal, Claudio Gennaro, Pasquale Savino, and Pavel Zezula. D-index: Distance searching index for metric data sets. Multimedia Tools and Applications, 21(1):9–33, 2003. ↩

38. Vlastislav Dohnal, Claudio Gennaro, Pasquale Savino, and Pavel Zezula. Separable splits of metric data sets. In Proceedings of the Nono Convegno Nazionale Sistemi Evoluti per Basi di Dati, SEBD, June 2001. ↩

39. Vlastislav Dohnal. Indexing Structures for Searching in Metric Spaces. PhD thesis, Masaryk University, Faculty of Informatics, 2004. ↩

40. Gonzalo Navarro and Nora Reyes. Dynamic spatial approximation trees. In Proceedings of the XXI Conference of the Chilean Computer Science Society, SCCC, pages 213–222, 2001. ↩

41. Gonzalo Navarro and Nora Reyes. Fully dynamic spatial approximation trees. In Proceedings of the 9th International Symposium on String Processing and Information Retrieval, SPIRE, volume 2476 of Lecture Notes in Computer Science, pages 254–270, 2002. ↩

42. Gonzalo Navarro and Nora Reyes. Improved deletions in dynamic spatial approximation trees. In Proceedings of the XXIII International Conference of the Chilean Computer Science Society, SCCC, 2003. ↩

43. Roberto Uribe, Gonzalo Navarro, Ricardo J. Barrientos, and Mauricio Marín. An index data structure for searching in metric space databases. In Vassil N. Alexandrov, Geert Dick van Albada, Peter M. A. Sloot, and Jack Dongarra, editors, Proceedings of the 6th International Conference of Computational Science, ICCS, volume 3991 of Lecture Notes in Computer Science, pages 611–617. Springer, 2006. ↩

44. Peter N. Yianilos. Excluded middle vantage point forests for nearest neighbor search. Technical report, NEC Research Institute, 1999. ↩

45. Jeffrey K. Uhlmann. Metric trees. Applied Mathematics Letters, 4(5): 61–62, 1991. ↩ ↩²

46. Jeffrey K. Uhlmann. Satisfying general proximity/similarity queries with metric trees. Information Processing Letters, 40(4):175–179, November 1991. ↩ ↩²

47. Sergey Brin. Near neighbor search in large metric spaces. In Umeshwar Dayal, Peter M. D. Gray, and Shojiro Nishio, editors, Proceedings of 21th International Conference on Very Large Data Bases, VLDB, pages 574–584. Morgan Kaufmann, 1995. ↩

48. Kimmo Fredriksson. Exploiting distance coherence to speed up range queries in metric indexes. Information Processing Letters, 95(1):287–292, 2005. ↩

49. Diego Arroyuelo, Gonzalo Navarro, and Nora Reyes. Fully dynamic and memory-adaptative spatial approximation trees. In Proceedings of the Argentinian Congress in Computer Science, CACIC, pages 1503–1513, 2003. ↩

50. Diego Arroyuelo, Francisca Mu˜noz, Gonzalo Navarro, and Nora Reyes. Memory-adaptative dynamic spatial approximation trees. In Proceedings of the 10th International Symposium on String Processing and Information Retrieval, SPIRE, 2003. ↩

51. Edgar Chavez, Norma Herrera, and Nora Reyes. Spatial approximation + sequential scan = efficient metric indexing. In Proceedings of the XXIV International Conference of the Chilean Computer Science Society, SCCC, 2004. ↩

52. Karina Figueroa, Edgar Chávez, Gonzalo Navarro, and Rodrigo Paredes. On the least cost for proximity searching in metric spaces. In Carme Alvarez and Maria Serna, editors, ` Proceedings of the 5th International Workshop on Experimental Algorithms, volume 4007 of Lecture Notes in Computer Science, pages 279–290. Springer, 2006. ↩

53. Cui Yu, Beng Chin Ooi, Kian-Lee Tan, and H. V. Jagadish. Indexing the distance: An efficient method to KNN processing. In Proceedings of the 27th International Conference on Very Large Data Bases, VLDB, pages 421–430, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc. ↩

54. Oscar Pedreira and Nieves R. Brisaboa. Spatial selection of sparse pivots for similarity search in metric spaces. In Proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science, number 4362 in Lecture Notes in Computer Science, pages 434–445, 2007. ↩

55. María Luisa Micó and José Oncina. 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, January 1994. ↩

56. Benjamin Bustos, Gonzalo Navarro, and Edgar Chávez. Pivot selection techniques for proximity searching in metric spaces. Pattern Recognition Letters, 24(14):2357–2366, October 2003. ↩

57. Edgar Chávez and Gonzalo Navarro. A compact space decomposition for effective metric indexing. Pattern Recognition Letters, 26(9):1363–1376, July 2005. ↩

58. Edgar Chávez and Gonzalo Navarro. An effective clustering algorithm to index high dimensional metric spaces. In Proceedings of the 6th International Symposium on String Processing and Information Retrieval, SPIRE, pages 75–86. IEEE Computer Society, 2000. ↩

59. Kevin Beyer, Jonathan Goldstein, Raghu Ramakrishnan, and Uri Shaft. When is “nearest neighbor” meaningful? In Proceedings of the 7th International Conference on Database Theory, volume 1540 of Lecture Notes In Computer Science, pages 217–235, London, UK, 1999. Springer-Verlag. ↩

60. Masahiro Ishikawa, Hanxiong Chen, Kazutaka Furuse, Jeffrey Xu Yu, and Nobuo Ohbo. Mb+tree: A dynamically updatable metric index for similarity search. In H. Lu and A. Zhou, editors, Proceedings of the First International Conference on Web-Age Information Management, volume 1846 of Lecture Notes in Computer Science, page 356. Springer, 2000. ↩

61. Hartmut Noltemeier, Knut Verbarg, and Christian Zirkelbach. Monotonous bisector∗ trees: a tool for efficient partitioning of complex scenes of geometric objects. In Burkhard Monien and Thomas Ottmann, editors, Data Structures and Efficient Algorithms, volume 594 of Lecture Notes In Computer Science, pages 186–203. Springer, 1992. ↩

62. Hartmut Noltemeier, Knut Verbarg, and Christian Zirkelbach. A data structure for representing and efficient querying large scenes of geometric objects: MB∗ trees. In Gerald E. Farin, Hans Hagen, Hartmut Noltemeier, and Walter Knödel, editors, Geometric Modelling, volume 8 of Computing Supplement. Springer, 1992. ↩

63. T. Skopal and D. Hoksza. Improving the performance of M-tree family by nearest-neighbor graphs. In Proceedings of the Eleventh East-European Conference on Advances in Databases and Information Systems, ADBIS, 2007. ↩ ↩²

64. Pavel Zezula, Paolo Ciaccia, and Fausto Rabitti. M-tree: A dynamic index for similarity queries in multimedia databases. Technical Report 7, HERMES ESPRIT LTR Project, 1996. ↩

65. Paolo Ciaccia, Marco Patella, and Pavel Zezula. M-tree: An efficient access method for similarity search in metric spaces. In Proceedings of the 23rd International Conference on Very Large Data Bases, VLDB, pages 426–435. Morgan Kaufmann, 1997. ↩

66. Paolo Ciaccia, Marco Patella, Fausto Rabitti, and Pavel Zezula. Indexing metric spaces with M-tree. In Matteo Cristiani and Letizia Tanca, editors, Atti del Quinto Convegno Nazionale su Sistemi Evoluti per Basi di Dati (SEBD’97), pages 67–86, Verona, Italy, June 1997. ↩

67. Tolga Bozkaya and Meral Ozsoyoglu. Distance-based indexing for high-dimensional metric spaces. In Proceedings of the 1997 ACM SIGMOD international conference on Management of data, pages 357–368, New York, NY, USA, 1997. ACM Press. ↩

68. Tolga Bozkaya and Meral Ozsoyoglu. Indexing large metric spaces for similarity search queries. ACM Transactions on Database Systems, TODS, 24(3), 1999. ↩

69. Roberto Figueira Santos Filho, Agma Traina, Caetano Traina Jr., and Christos Faloutsos. Similarity search without tears: the OMNI-family of all-purpose access methods. In Proceedings of the 17th International Conference on Data Engineering, ICDE, pages 623–630, 2001. ↩

70. Tzi-cker Chiueh. Content-based image indexing. In Proceedings of the Twentieth International Conference on Very Large Databases, VLDB, pages 582–593, Santiago, Chile, 1994. ↩

71. Tomáš Skopal. Pivoting M-tree: A metric access method for efficient similarity search. In V. Snášel, J. Pokorný, and K. Richta, editors, Proceedings of the Annual International Workshop on DAtabases, TExts, Specifications and Objects (DATESO), volume 98 of CEUR Workshop Proceedings, Desna, Czech Republic, April 2004. Technical University of Aachen (RWTH). ↩

72. J. M. Vilar. Reducing the overhead of the AESA metric-space nearest neighbour searching algorithm. Information Processing Letters, 56(5): 265–271, December 1995. ↩

73. Gonzalo Navarro. Searching in metric spaces by spatial approximation. The VLDB Journal, 11(1):28–46, August 2002. ↩

74. Gonzalo Navarro. Searching in metric spaces by spatial approximation. In Proceedings of the 6th International Symposium on String Processing and Information Retrieval, SPIRE, pages 141–148. IEEE Computer Society, 1999. ↩

75. Caetano Traina Jr., Agma J. M. Traina, Bernhard Seeger, and Christos Faloutsos. Slim-trees: High performance metric trees minimizing overlap between nodes. In Proceedings of the 7th International Conference on Extending Database Technology, EDBT, volume 1777 of Lecture Notes in Computer Science, pages 51–65. Springer-Verlag, 2000. ↩

76. Tomáš Skopal, Jaroslav Pokorný, Michal Krátký, and Václav Snášel. Revisiting M-tree building principles. In Advances in Databases and Information Systems, volume 2798 of Lecture Notes In Computer Science, pages 148–162, September 2003. ↩

77. Edgar Chávez, José Luis Marroquín, and Ricardo Baeza-Yates. Spaghettis: An array based algorithm for similarity queries in metric spaces. In Proceedings of the String Processing and Information Retrieval Symposium & International Workshop on Groupware (SPIRE), pages 38–46. IEEE Computer Society, September 1999. ↩

78. Nieves Brisaboa, Oscar Pedreira, Diego Seco, Roberto Solar, and Roberto Uribe. Clustering-based similarity search in metric spaces with sparse spatial centers. In Proceedings of the 34th Conference on Current Trends in Theory and Practice of Computer Science, number 4910 in Lecture Notes in Computer Science, pages 186–197. Springer, 2008. ↩

79. Mauricio Marin, Veronica Gil-Costa, and Roberto Uribe. Hybrid index for metric space databases. In Proceedings of the International Conference on Computational Science, 2008. ↩

80. María Luisa Micó, José Oncina, and Rafael C. Carrasco. A fast branch & bound nearest neighbour classifier in metric spaces. Pattern Recognition Letters, 17(7):731–739, June 1996. ↩

81. Ken Tokoro, Kazuaki Yamaguchi, and Sumio Masuda. Improvements of TLAESA nearest neighbour search algorithm and extension to approximation search. In Proceedings of the 29th Australasian Computer Science Conference, pages 77–83. Australian Computer Society, Inc., 2006. ↩

82. Frank K. H. A. Dehne and Hartmut Noltemeier. Voronoi trees and clustering problems. Information Systems, 12(2):171–175, 1987. ↩

83. Peter N. Yianilos. Data structures and algorithms for nearest neighbor search in general metric spaces. In Proceedings of the fourth annual ACMSIAM Symposium on Discrete algorithms, pages 311–321, Philadelphia, PA, USA, 1993. Society for Industrial and Applied Mathematics. ↩