{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T22:33:00Z","timestamp":1771626780811,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T00:00:00Z","timestamp":1497916800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Datenbank Spektrum"],"published-print":{"date-parts":[[2017,7]]},"DOI":"10.1007\/s13222-017-0258-5","type":"journal-article","created":{"date-parts":[[2017,6,20]],"date-time":"2017-06-20T03:33:40Z","timestamp":1497929620000},"page":"155-167","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Reducing the Distance Calculations when Searching an M\u2011Tree"],"prefix":"10.1007","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8096-0105","authenticated-orcid":false,"given":"Steffen","family":"Guhlemann","sequence":"first","affiliation":[]},{"given":"Uwe","family":"Petersohn","sequence":"additional","affiliation":[]},{"given":"Klaus","family":"Meyer-Wegener","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,20]]},"reference":[{"issue":"3","key":"258_CR1","doi-asserted-by":"crossref","first-page":"919","DOI":"10.1016\/j.datak.2007.06.001","volume":"63","author":"L Aronovich","year":"2007","unstructured":"Aronovich L, Spiegler I (2007) CM-tree: a dynamic clustered index for similarity search in metric databases. Data Knowl Eng 63(3):919\u2013946","journal-title":"Data Knowl Eng"},{"key":"258_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1007\/3-540-58094-8_18","volume-title":"Combinatorial pattern matching","author":"R Baeza-Yates","year":"1994","unstructured":"Baeza-Yates R, Cunto W, Manber U, Wu S (1994) Proximity matching using fixed-queries trees. In: Crochemore M, Gusfield D (eds) Combinatorial pattern matching. Lecture Notes in Computer Science, vol 807. Springer, Berlin Heidelberg, pp 198\u2013212"},{"key":"258_CR3","first-page":"423","volume-title":"String processing and information retrieval","author":"I Bartolini","year":"2002","unstructured":"Bartolini I, Ciaccia P, Patella M (2002) String matching with metric trees using an approximate distance. In: String processing and information retrieval. Springer, Berlin Heidelberg, pp 423\u2013431"},{"issue":"2","key":"258_CR4","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1145\/253262.253345","volume":"26","author":"T Bozkaya","year":"1997","unstructured":"Bozkaya T, Ozsoyoglu M (1997) Distance-based indexing for high-dimensional metric spaces. ACM SIGMOD Rec 26(2):357\u2013368","journal-title":"ACM SIGMOD Rec"},{"key":"258_CR5","first-page":"574","volume-title":"Very Large Data Bases (VLDB)","author":"S Brin","year":"1995","unstructured":"Brin S (1995) Near neighbor search in large metric spaces. In: Very Large Data Bases (VLDB). IEEE, Washington, D.C, pp 574\u2013584 (Conference paper)"},{"issue":"4","key":"258_CR6","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1145\/362003.362025","volume":"16","author":"WA Burkhard","year":"1973","unstructured":"Burkhard WA, Keller RM (1973) Some approaches to best-match file searching. Commun ACM 16(4):230\u2013236","journal-title":"Commun ACM"},{"issue":"14","key":"258_CR7","doi-asserted-by":"crossref","first-page":"2357","DOI":"10.1016\/S0167-8655(03)00065-5","volume":"24","author":"B Bustos","year":"2003","unstructured":"Bustos B, Navarro G, Ch\u00e1vez E (2003) Pivot selection techniques for proximity searching in metric spaces. Pattern Recognit Lett 24(14):2357\u20132366","journal-title":"Pattern Recognit Lett"},{"key":"258_CR8","first-page":"75","volume-title":"An effective clustering algorithm to index high dimensional metric spaces","author":"E Ch\u00e1vez","year":"2000","unstructured":"Ch\u00e1vez E, Navarro G (2000) An effective clustering algorithm to index high dimensional metric spaces. Proc. 7th International Symposium on String Processing and Information Retrieval. IEEE CS Press, Washington DC, pp 75\u201386"},{"key":"258_CR9","first-page":"57","volume-title":"Overcoming the curse of dimensionality","author":"E Ch\u00e1vez","year":"1999","unstructured":"Ch\u00e1vez E, Marroqu\u00edn J, Navarro G (1999) Overcoming the curse of dimensionality. European Workshop on Content-based Multimedia Indexing (CBMI 99), pp 57\u201364"},{"issue":"2","key":"258_CR10","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1023\/A:1011343115154","volume":"14","author":"E Ch\u00e1vez","year":"2001","unstructured":"Ch\u00e1vez E, Marroqu\u00edn J, Navarro G (2001) Fixed queries array: a fast and economical data structure for proximity searching. Multimed Tools Appl 14(2):113\u2013135","journal-title":"Multimed Tools Appl"},{"key":"258_CR11","first-page":"15","volume-title":"Bulk loading the M\u2011tree","author":"P Ciaccia","year":"1998","unstructured":"Ciaccia P, Patella M (1998) Bulk loading the M\u2011tree. Proc. 9th Australasian Database Conf. (ADC), pp 15\u201326"},{"key":"258_CR13","volume-title":"The M2-tree: processing complex multi-feature queries with just one index","author":"P Ciaccia","year":"2000","unstructured":"Ciaccia P, Patella M (2000) The M2-tree: processing complex multi-feature queries with just one index. DELOS Workshop: Information Seeking, Searching and Querying in Digital Libraries."},{"key":"258_CR12","first-page":"426","volume-title":"Very Large Data Bases (VLDB)","author":"P Ciaccia","year":"1997","unstructured":"Ciaccia P, Patella M, Zezula P (1997) M\u2011tree: an efficient access method for similarity search in metric spaces. In: Very Large Data Bases (VLDB). ACM Press, New York, pp 426\u2013435 (Conference paper)"},{"key":"258_CR14","volume-title":"Operators for similarity search: semantics, techniques and usage scenarios","author":"P Deepak","year":"2015","unstructured":"Deepak P, Deshpande PM (2015) Operators for similarity search: semantics, techniques and usage scenarios. Springer, Berlin Heidelberg"},{"key":"258_CR15","series-title":"NATO ASI Series","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/978-3-642-83462-2_12","volume-title":"Syntactic and structural pattern recognition","author":"F Dehne","year":"1988","unstructured":"Dehne F, Noltemeier H (1988) Voronoi trees and clustering problems. In: Ferrate G, Pavlidis T, Sanfeliu A, Bunke H (eds) Syntactic and structural pattern recognition. NATO ASI Series, vol 45. Springer, Berlin Heidelberg, pp 185\u2013194"},{"issue":"1","key":"258_CR16","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1023\/A:1025026030880","volume":"21","author":"V Dohnal","year":"2003","unstructured":"Dohnal V, Gennaro C, Savino P, Zezula P (2003a) D\u2011index: distance searching index for metric data sets. Multimed Tools Appl 21(1):9\u201333","journal-title":"Multimed Tools Appl"},{"key":"258_CR17","doi-asserted-by":"crossref","first-page":"484","DOI":"10.1007\/978-3-540-45227-0_48","volume-title":"Database and Expert Systems Applications (DEXA)","author":"V Dohnal","year":"2003","unstructured":"Dohnal V, Gennaro C, Zezula P (2003b) Similarity join in metric spaces using eD-index. In: Database and Expert Systems Applications (DEXA). Springer, Berlin Heidelberg, pp 484\u2013493 (Conference paper)"},{"key":"258_CR18","volume-title":"Scientific and Statistical Database Management (SSDBM)","author":"D Fenz","year":"2012","unstructured":"Fenz D, Lange D, Rheinl\u00e4nder A, Naumann F, Leser U (2012) Efficient similarity search in very large string sets. In: Scientific and Statistical Database Management (SSDBM) Chania. (Conference paper)"},{"key":"258_CR19","unstructured":"Guhlemann S (2016) Neue Indexverfahren f\u00fcr die \u00c4hnlichkeitssuche in metrischen R\u00e4umen \u00fcber gro\u00dfen Datenmengen. PhD thesis, TU Dresden"},{"key":"258_CR20","first-page":"199","volume-title":"The basic principles of metric indexing","author":"ML Hetland","year":"2009","unstructured":"Hetland ML (2009) The basic principles of metric indexing. Springer, Berlin Heidelberg, pp 199\u2013232"},{"issue":"2","key":"258_CR21","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1145\/1071610.1071612","volume":"30","author":"HV Jagadish","year":"2005","unstructured":"Jagadish HV, Ooi BC, Tan KL, Yu C, Zhang R (2005) iDistance: an adaptive B+-tree based indexing method for nearest neighbor search. ACM Trans Database Syst (TODS) 30(2):364\u2013397","journal-title":"ACM Trans Database Syst (TODS)"},{"key":"258_CR22","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1109\/TSE.1983.235263","volume":"5","author":"I Kalantari","year":"1983","unstructured":"Kalantari I, McDonald G (1983) A data structure and an algorithm for the nearest point problem. IEEE Trans Softw Eng 5:631\u2013634. doi: 10.1109\/TSE.1983.235263","journal-title":"IEEE Trans Softw Eng"},{"issue":"1","key":"258_CR23","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/s13222-011-0046-6","volume":"11","author":"D Lange","year":"2011","unstructured":"Lange D, Vogel T, Draisbach U, Naumann F (2011) Projektseminar \u2019Similarity Search Algorithms\u2019. Datenbank Spektrum 11(1):51\u201357","journal-title":"Datenbank Spektrum"},{"issue":"1","key":"258_CR24","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0167-8655(94)90095-7","volume":"15","author":"M Mic\u00f3","year":"1994","unstructured":"Mic\u00f3 M, Oncina J, Vidal E (1994) A new version of the nearest-neighbour approximating and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements. Pattern Recognit Lett 15(1):9\u201317","journal-title":"Pattern Recognit Lett"},{"key":"258_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1007\/3-540-55488-2_27","volume-title":"Data structures and efficient algorithms","author":"H Noltemeier","year":"1992","unstructured":"Noltemeier H, Verbarg K, Zirkelbach C (1992) Monotonous Bisector* Trees \u2013 a tool for efficient partitioning of complex scenes of geometric objects. In: Monien B, Ottmann T (eds) Data structures and efficient algorithms. Lecture Notes in Computer Science, vol 594, pp 186\u2013203"},{"key":"258_CR26","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/978-3-7091-6916-2_14","volume-title":"Geometric modelling","author":"H Noltemeier","year":"1993","unstructured":"Noltemeier H, Verbarg K, Zirkelbach C (1993) A data structure for representing and efficient querying large scenes of geometric objects: MB* trees. In: Farin G, Hagen H, Noltemeier H, Kn\u00f6del W (eds) Geometric modelling. Springer, Vienna, pp 211\u2013226"},{"key":"258_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1007\/978-3-319-10085-2_4","volume-title":"Database and Expert Systems Applications (DEXA)","author":"D Novak","year":"2014","unstructured":"Novak D, Zezula P (2014) Rank aggregation of candidate sets for efficient similarity search. In: Decker H, Lhotsk\u00e1 L, Link S, Spies M, Wagner RR (eds) Database and Expert Systems Applications (DEXA). Lecture Notes in Computer Science, vol 8645. Springer, Cham, pp 42\u201358 (Conference paper)"},{"issue":"4","key":"258_CR28","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1016\/j.is.2010.10.002","volume":"36","author":"D Novak","year":"2011","unstructured":"Novak D, Batko M, Zezula P (2011) Metric index: an efficient and scalable solution for precise and approximate similarity search. Inf Syst 36(4):721\u2013733","journal-title":"Inf Syst"},{"key":"258_CR29","volume-title":"Similarity search in multimedia databases","author":"M Patella","year":"1999","unstructured":"Patella M (1999) Similarity search in multimedia databases. Dipartmento di Elettronica Informatica e Sistemistica, Bologna"},{"key":"258_CR30","doi-asserted-by":"crossref","first-page":"519","DOI":"10.1007\/978-3-642-13818-8_36","volume-title":"Int. Conf. on Scientific and Statistical Database Management (SSDBM)","author":"A Rheinl\u00e4nder","year":"2010","unstructured":"Rheinl\u00e4nder A, Knobloch M, Hochmuth N, Leser U (2010) Prefix tree indexing for similarity search and similarity joins on genomic data. In: Int. Conf. on Scientific and Statistical Database Management (SSDBM). Springer, Cham, pp 519\u2013536 (Conference paper)"},{"key":"258_CR31","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1007\/978-3-319-25087-8_19","volume-title":"Int. Conf. on Similarity Search and Applications","author":"J Sedmidubsky","year":"2015","unstructured":"Sedmidubsky J, Mic V, Zezula P (2015) Face image retrieval revisited. In: Int. Conf. on Similarity Search and Applications. Springer, Cham, pp 204\u2013216 (Conference paper)"},{"issue":"5","key":"258_CR32","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1145\/359581.359599","volume":"20","author":"M Shapiro","year":"1977","unstructured":"Shapiro M (1977) The choice of reference points in best-match file searching. Commun ACM 20(5):339\u2013343","journal-title":"Commun ACM"},{"key":"258_CR33","unstructured":"Skopal T (2004) Pivoting M\u2011tree: a metric access method for efficient similarity search. In: Dateso Annual Int. Workshop on Databases, Texts, Specifications and Objects Desna, 14.-16. April 2004. Desna, pp 27\u201337 (Conference paper)"},{"key":"258_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/978-3-540-39403-7_13","volume-title":"Advances in Databases and Information Systems","author":"T Skopal","year":"2003","unstructured":"Skopal T, Pokorn\u1ef3 J, Kr\u00e1tk\u1ef3 M, Sn\u00e1\u0161el V (2003) Revisiting M\u2011tree building principles. In: Advances in Databases and Information Systems. Lecture Notes in Computer Science, vol 2798. Springer, Berlin Heidelberg, pp 148\u2013162"},{"key":"258_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/3-540-46439-5_4","volume-title":"Advances in Database Technology, EDBT","author":"C Traina","year":"2000","unstructured":"Traina C, Traina A, Seeger B, Faloutsos C (2000) Slim-trees: High performance metric trees minimizing overlap between nodes. In: Advances in Database Technology, EDBT. Lecture Notes in Computer Science, vol 1777. Springer, Berlin Heidelberg, pp 51\u201365"},{"issue":"2","key":"258_CR36","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1109\/69.991715","volume":"14","author":"C Traina Jr","year":"2002","unstructured":"Traina C Jr, Traina A, Faloutsos C, Seeger B (2002) Fast indexing and visualization of metric data sets using slim-trees. Knowl Data Eng IEEE Trans 14(2):244\u2013260","journal-title":"Knowl Data Eng IEEE Trans"},{"issue":"4","key":"258_CR37","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0020-0190(91)90074-R","volume":"40","author":"J Uhlmann","year":"1991","unstructured":"Uhlmann J (1991) Satisfying general proximity\/similarity queries with metric trees. Inf Process Lett 40(4):175\u2013179","journal-title":"Inf Process Lett"},{"issue":"3","key":"258_CR38","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/0167-8655(86)90013-9","volume":"4","author":"E Vidal","year":"1986","unstructured":"Vidal E (1986) An algorithm for finding nearest neighbours in (approximately) constant average time. Pattern Recognit Lett 4(3):145\u2013157","journal-title":"Pattern Recognit Lett"},{"key":"258_CR39","first-page":"311","volume-title":"4th Annual ACM-SIAM Symp. on Discrete Algorithms","author":"P Yianilos","year":"1993","unstructured":"Yianilos P (1993) Data structures and algorithms for nearest neighbor search in general metric spaces. In: 4th Annual ACM-SIAM Symp. on Discrete Algorithms. Society for Industrial and Applied Mathematics, Philadelphia, pp 311\u2013321 (Conference paper)"},{"key":"258_CR40","unstructured":"Yianilos PN (1999) Excluded middle vantage point forests for nearest neighbor search. In: 6th DIMACS Implementation Challenge: Near Neighbor Searches (ALENEX) Baltimore. (Conference paper)"},{"key":"258_CR41","doi-asserted-by":"crossref","DOI":"10.1007\/0-387-29151-2","volume-title":"Similarity search: the metric space approach","author":"P Zezula","year":"2006","unstructured":"Zezula P, Amato G, Dohnal V, Batko M (2006) Similarity search: the metric space approach. Springer, Berlin"},{"key":"258_CR42","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1007\/11408079_36","volume-title":"Database Systems for Advanced Applications","author":"X Zhou","year":"2005","unstructured":"Zhou X, Wang G, Zhou X, Yu G (2005) BM+-tree: a hyperplane-based index method for high-dimensional metric spaces. In: Database Systems for Advanced Applications. Springer, Berlin Heidelberg, pp 398\u2013409"},{"key":"258_CR43","doi-asserted-by":"crossref","unstructured":"Zierenberg M, Schmitt I (2015) Optimizing the Distance Computation Order of Multi-Feature Similarity Search Indexing. In: Int. Conf. on Similarity Search and Applications. Springer, New York, pp 90\u201396","DOI":"10.1007\/978-3-319-25087-8_8"}],"container-title":["Datenbank-Spektrum"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s13222-017-0258-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13222-017-0258-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13222-017-0258-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,26]],"date-time":"2019-09-26T05:39:17Z","timestamp":1569476357000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s13222-017-0258-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,20]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["258"],"URL":"https:\/\/doi.org\/10.1007\/s13222-017-0258-5","relation":{},"ISSN":["1618-2162","1610-1995"],"issn-type":[{"value":"1618-2162","type":"print"},{"value":"1610-1995","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,6,20]]}}}