{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T05:05:57Z","timestamp":1784264757948,"version":"3.55.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2017,10,6]],"date-time":"2017-10-06T00:00:00Z","timestamp":1507248000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61502504"],"award-info":[{"award-number":["61502504"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"the Fundamental Research Funds for the Central University, and the Research Funds of Renmin University of China","award":["No. 15XNLF09"],"award-info":[{"award-number":["No. 15XNLF09"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2017,12]]},"DOI":"10.1007\/s00778-017-0481-6","type":"journal-article","created":{"date-parts":[[2017,10,6]],"date-time":"2017-10-06T08:59:56Z","timestamp":1507280396000},"page":"829-854","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":25,"title":["MSQL: efficient similarity search in metric spaces using SQL"],"prefix":"10.1007","volume":"26","author":[{"given":"Wei","family":"Lu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jiajia","family":"Hou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ying","family":"Yan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Meihui","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaoyong","family":"Du","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas","family":"Moscibroda","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,10,6]]},"reference":[{"key":"481_CR1","volume-title":"Multimedia Databases in Perspective","year":"1997","unstructured":"Apers, P.M.G., Blanken, H.M., Houtsma, M.A.W. (eds.): Multimedia Databases in Perspective. Springer, Berlin (1997)"},{"issue":"3","key":"481_CR2","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.: Cm-tree: a dynamic clustered index for similarity search in metric databases. Data Knowl. Eng. 63(3), 919\u2013946 (2007)","journal-title":"Data Knowl. Eng."},{"key":"481_CR3","volume-title":"Modern Information Retrieval","author":"RA Baeza-Yates","year":"1999","unstructured":"Baeza-Yates, R.A., Ribeiro-Neto, B.A.: Modern Information Retrieval. ACM Press\/Addison-Wesley, New York (1999)"},{"key":"481_CR4","doi-asserted-by":"publisher","unstructured":"Behm, A., Ji, S., Li, C., Lu, J.: Space-constrained gram-based indexing for efficient approximate string search. In: Proceedings of the 25th International Conference on Data Engineering (ICDE), March 29 \u2013 April 2, 2009, Shanghai, China, pp. 604\u2013615 (2009). doi:\n                        10.1109\/ICDE.2009.32","DOI":"10.1109\/ICDE.2009.32"},{"issue":"3","key":"481_CR5","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1145\/328939.328959","volume":"24","author":"T Bozkaya","year":"1999","unstructured":"Bozkaya, T., \u00d6zsoyoglu, Z.M.: Indexing large metric spaces for similarity search queries. ACM Trans. Database Syst. 24(3), 361\u2013404 (1999)","journal-title":"ACM Trans. Database Syst."},{"key":"481_CR6","unstructured":"Brin, S.: Near neighbor search in large metric spaces. In: VLDB\u201995, Proceedings of 21th International Conference on Very Large Data Bases, September 11\u201315, 1995, Zurich, Switzerland, pp. 574\u2013584 (1995)"},{"issue":"3","key":"481_CR7","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1145\/502807.502808","volume":"33","author":"E Ch\u00e1vez","year":"2001","unstructured":"Ch\u00e1vez, E., Navarro, G., Baeza-Yates, R., Marroqu\u00edn, J.L.: Searching in metric spaces. ACM Comput. Surv. (CSUR) 33(3), 273\u2013321 (2001)","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"481_CR8","doi-asserted-by":"publisher","unstructured":"Chen, L., Gao, Y., Li, X., Jensen, C.S., Chen, G.: Efficient metric indexing for similarity search. In: 31st (IEEE) International Conference on Data Engineering (ICDE), April 13\u201317, 2015, Seoul, South Korea, pp. 591\u2013602 (2015). doi:\n                        10.1109\/ICDE.2015.7113317","DOI":"10.1109\/ICDE.2015.7113317"},{"key":"481_CR9","unstructured":"Ciaccia, P., Patella, M., Zezula, P.: M-tree: an efficient access method for similarity search in metric spaces. In: VLDB\u201997, Proceedings of 23rd International Conference on Very Large Data Bases, August 25\u201329, 1997, Athens, Greece, pp. 426\u2013435 (1997)"},{"issue":"7","key":"481_CR10","doi-asserted-by":"crossref","first-page":"3229","DOI":"10.1109\/TIT.2009.2021326","volume":"55","author":"S Dasgupta","year":"2009","unstructured":"Dasgupta, S., Freund, Y.: Random projection trees for vector quantization. IEEE Trans. Inf. Theory 55(7), 3229\u20133242 (2009)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"481_CR11","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.: D-index: distance searching index for metric data sets. Multimed. Tools Appl. 21(1), 9\u201333 (2003)","journal-title":"Multimed. Tools Appl."},{"key":"481_CR12","doi-asserted-by":"crossref","unstructured":"Gao, J., Jagadish, H.V., Lu, W., Ooi, B.C.: DSH: data sensitive hashing for high-dimensional k-nnsearch. In: International Conference on Management of Data, SIGMOD 2014, Snowbird, UT, USA, June 22\u201327, pp. 1127\u20131138 (2014)","DOI":"10.1145\/2588555.2588565"},{"key":"481_CR13","unstructured":"Gionis, A., Indyk, P., Motwani, R.: Similarity search in high dimensions via hashing. In: VLDB\u201999, Proceedings of 25th International Conference on Very Large Data Bases, September 7\u201310, 1999, Edinburgh, Scotland, UK, pp. 518\u2013529 (1999)"},{"key":"481_CR14","unstructured":"Goldstein, J., Ramakrishnan, R.: Contrast plots and p-sphere trees: space vs. time in nearest neighbour searches. In: Proceedings of 27th International Conference on Very Large Data Bases (VLDB), September 11\u201314, 2001, Roma, Italy, pp. 429\u2013440 (2000)"},{"key":"481_CR15","unstructured":"Gravano, L., Ipeirotis, P.G., Jagadish, H.V., Koudas, N., Muthukrishnan, S., Srivastava, D.: Approximate string joins in a database (almost) for free. In: Proceedings of 27th International Conference on Very Large Data Bases (VLDB), September 11\u201314, 2001, Roma, Italy, pp. 491\u2013500 (2001)"},{"key":"481_CR16","unstructured":"Hellerstein, J.M., Naughton, J.F., Pfeffer, A.: Generalized search trees for database systems. In: VLDB\u201995, Proceedings of 21th International Conference on Very Large Data Bases, September 11\u201315, 1995, Zurich, Switzerland, pp. 562\u2013573 (1995)"},{"issue":"4","key":"481_CR17","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1145\/958942.958948","volume":"28","author":"GR Hjaltason","year":"2003","unstructured":"Hjaltason, G.R., Samet, H.: Index-driven similarity search in metric spaces. ACM Trans. Database Syst. 28(4), 517\u2013580 (2003)","journal-title":"ACM Trans. Database Syst."},{"issue":"2","key":"481_CR18","doi-asserted-by":"crossref","first-page":"364","DOI":"10.1145\/1071610.1071612","volume":"30","author":"HV Jagadish","year":"2005","unstructured":"Jagadish, H.V., Ooi, B.C., Tan, K.-L., Yu, C., Zhang, R.: idistance: an adaptive B\n                        $$^{\\text{+ }}$$\n                        \n                            \n                                            \n                                \n                                    \n                                    \n                                        +\n                                        \n                                    \n                                \n                            \n                        \n                    -tree based indexing method for nearest neighbor search. ACM Trans. Database Syst. 30(2), 364\u2013397 (2005)","journal-title":"ACM Trans. Database Syst."},{"key":"481_CR19","doi-asserted-by":"crossref","unstructured":"Jr, C.T., Traina, A.J.M., Faloutsos, C., Seeger, B.: Fast indexing and visualization of metric data sets using slim-trees. IEEE Trans. Knowl. Data Eng. 14(2), 244\u2013260 (2002)","DOI":"10.1109\/69.991715"},{"key":"481_CR20","unstructured":"Kaufman, L., Rousseeuw, P.: Clustering by means of medoids. Statistical Data Analysis Based on the L1-Norm and Related Methods, pp. 405\u2013416 (1987)"},{"key":"481_CR21","doi-asserted-by":"crossref","unstructured":"Koudas, N., Marathe, A., Srivastava, D.: Flexible string matching against large databases in practice. In: Proceedings of the Thirtieth International Conference on Very Large Data Bases (VLDB), August 31 - September 3, 2004, Toronto, Canada, pp. 1078\u20131086 (2004)","DOI":"10.1016\/B978-012088469-8.50094-2"},{"issue":"4","key":"481_CR22","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1007\/BF01231606","volume":"3","author":"K-I Lin","year":"1994","unstructured":"Lin, K.-I., Jagadish, H.V., Faloutsos, C.: The TV-tree: an index structure for high-dimensional data. VLDB J. 3(4), 517\u2013542 (1994)","journal-title":"VLDB J."},{"issue":"12","key":"481_CR23","doi-asserted-by":"crossref","first-page":"2983","DOI":"10.1109\/TKDE.2014.2309131","volume":"26","author":"W Lu","year":"2014","unstructured":"Lu, W., Du, X., Hadjieleftheriou, M., Ooi, B.C.: Efficiently supporting edit distance based string similarity search using B\n                        $$^{+}$$\n                        \n                            \n                                            \n                                \n                                    \n                                    +\n                                \n                            \n                        \n                    -trees. IEEE Trans. Knowl. Data Eng. 26(12), 2983\u20132996 (2014)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"10","key":"481_CR24","first-page":"1016","volume":"5","author":"W Lu","year":"2012","unstructured":"Lu, W., Shen, Y., Chen, S., Ooi, B.C.: Efficient processing of k nearest neighbor joins using mapreduce. PVLDB 5(10), 1016\u20131027 (2012)","journal-title":"PVLDB"},{"issue":"4","key":"481_CR25","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.: Metric index: an efficient and scalable solution for precise and approximate similarity search. Inf. Syst. 36(4), 721\u2013733 (2011)","journal-title":"Inf. Syst."},{"issue":"10","key":"481_CR26","doi-asserted-by":"crossref","first-page":"2217","DOI":"10.1109\/TKDE.2012.195","volume":"25","author":"C Rong","year":"2013","unstructured":"Rong, C., Lu, W., Wang, X., Du, X., Chen, Y., Tung, A.K.H.: Efficient and scalable processing of string similarity join. IEEE Trans. Knowl. Data Eng. 25(10), 2217\u20132230 (2013)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"4","key":"481_CR27","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0020-0190(91)90074-R","volume":"40","author":"JK Uhlmann","year":"1991","unstructured":"Uhlmann, J.K.: Satisfying general proximity\/similarity queries with metric trees. Inf. Process. Lett. 40(4), 175\u2013179 (1991)","journal-title":"Inf. Process. Lett."},{"key":"481_CR28","unstructured":"Venkateswaran, J., Lachwani, D., Kahveci, T., Jermaine, C.M.: Reference-based indexing of sequence databases. In: Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB), September 12\u201315, 2006, Seoul, Korea, pp. 906\u2013917 (2006)"},{"key":"481_CR29","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4899-6846-3","volume-title":"Introduction to Computational Biology\u2014Maps, Sequences, and Genomes: Interdisciplinary Statistics","author":"MS Waterman","year":"1995","unstructured":"Waterman, M.S.: Introduction to Computational Biology\u2014Maps, Sequences, and Genomes: Interdisciplinary Statistics. CRC Press, Boca Raton (1995)"},{"key":"481_CR30","unstructured":"Winkler, W.E.: The state of record linkage and current research problems. Statistical Research Division, US Bureau of the Census (1999)"},{"key":"481_CR31","doi-asserted-by":"publisher","unstructured":"Yao, B., Li, F., Kumar, P.: K nearest neighbor queries and knn-joins in large relational databases (almost) for free. In: ICDE, pp. 4\u201315 (2010). doi:\n                        10.1109\/ICDE.2010.5447837","DOI":"10.1109\/ICDE.2010.5447837"},{"key":"481_CR32","unstructured":"Yianilos, P.N.: Data structures and algorithms for nearest neighbor search in general metric spaces. In: Proceedings of the Fourth Annual Symposium on Discrete Algorithms SODA, January 25\u201327, 1993, Austin, Texas, pp. 311\u2013321 (1993)"},{"issue":"1","key":"481_CR33","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1109\/69.755617","volume":"11","author":"A Yoshitaka","year":"1999","unstructured":"Yoshitaka, A., Ichikawa, T.: A survey on content-based retrieval for multimedia databases. IEEE Trans. Knowl. Data Eng. 11(1), 81\u201393 (1999)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"481_CR34","unstructured":"Yu, C., Ooi, B.C., Tan, K.-L., Jagadish, H.V.: Indexing the distance: an efficient method to knn processing. In: Proceedings of 27th International Conference on Very Large Data Bases (VLDB), September 11\u201314, 2001, Roma, Italy, pp. 421\u2013430 (2001)"},{"issue":"3","key":"481_CR35","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1145\/1093382.1093383","volume":"30","author":"R Zhang","year":"2005","unstructured":"Zhang, R., Kalnis, P., Ooi, B.C., Tan, K.-L.: Generalized multidimensional data mapping and query processing. ACM Trans. Database Syst. 30(3), 661\u2013697 (2005)","journal-title":"ACM Trans. Database Syst."},{"key":"481_CR36","doi-asserted-by":"publisher","unstructured":"Zhang, Z., Hadjieleftheriou, M., Ooi, B.C., Srivastava, D.: Bed-tree: an all-purpose index structure for string similarity search based on edit distance. In: Proceedings of the International Conference on Management of Data (SIGMOD), June 6\u201310, 2010, Indianapolis, Indiana, USA, pp. 915\u2013926 (2010). doi:\n                        10.1145\/1807167.1807266","DOI":"10.1145\/1807167.1807266"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00778-017-0481-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-017-0481-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-017-0481-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,8,15]],"date-time":"2018-08-15T11:42:09Z","timestamp":1534333329000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00778-017-0481-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,6]]},"references-count":36,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["481"],"URL":"https:\/\/doi.org\/10.1007\/s00778-017-0481-6","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,6]]}}}