{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:08:52Z","timestamp":1750219732677,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T00:00:00Z","timestamp":1699833600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["IIS-18-16889","IIS-20-41415","IIS-21-14451"],"award-info":[{"award-number":["IIS-18-16889","IIS-20-41415","IIS-21-14451"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,11,13]]},"DOI":"10.1145\/3615890.3628531","type":"proceedings-article","created":{"date-parts":[[2023,12,11]],"date-time":"2023-12-11T19:46:11Z","timestamp":1702323971000},"page":"1-8","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Metric Indexing for the Earth Mover's Distance"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0008-7487-8509","authenticated-orcid":false,"given":"Vincent","family":"Hsiao","sequence":"first","affiliation":[{"name":"University of Maryland, College Park, MD, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8230-0653","authenticated-orcid":false,"given":"Hanan","family":"Samet","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, MD, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,12,11]]},"reference":[{"volume-title":"Proceedings of the 40th IEEE Annual Symposium on Foundations of Computer Science","author":"Amir A.","key":"e_1_3_2_1_1_1","unstructured":"A. Amir , A. Efrat , P. Indyk , and H. Samet . 1999. Efficient regular data structures and algorithms for location and proximity problems . In Proceedings of the 40th IEEE Annual Symposium on Foundations of Computer Science . New York, 160--170. A. Amir, A. Efrat, P. Indyk, and H. Samet. 1999. Efficient regular data structures and algorithms for location and proximity problems. In Proceedings of the 40th IEEE Annual Symposium on Foundations of Computer Science. New York, 160--170."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.56221"},{"key":"e_1_3_2_1_3_1","unstructured":"M. Arjovsky S. Chintala and L. Bottou. 2017. Wasserstein gan. arXiv preprint arXiv:1701.07875.  M. Arjovsky S. Chintala and L. Bottou. 2017. Wasserstein gan. arXiv preprint arXiv:1701.07875."},{"volume-title":"Proc. of the 22nd Intl Conf. on Data Engineering, ICDE","author":"Assent I.","key":"e_1_3_2_1_4_1","unstructured":"I. Assent , A. Wenning , and T. Seidl . 2006. Approximation Techniques for Indexing the Earth Mover's Distance in Multimedia Databases . In Proc. of the 22nd Intl Conf. on Data Engineering, ICDE , Atlanta, GA, USA. IEEE Computer Society, 11. I. Assent, A. Wenning, and T. Seidl. 2006. Approximation Techniques for Indexing the Earth Mover's Distance in Multimedia Databases. In Proc. of the 22nd Intl Conf. on Data Engineering, ICDE, Atlanta, GA, USA. IEEE Computer Society, 11."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2019.02.006"},{"key":"e_1_3_2_1_6_1","volume-title":"Proc. of the 22nd Intl Conf. on Very Large Data Bases (VLDB). Mumbai (Bombay), India, 28--39","author":"Berchtold S.","year":"1996","unstructured":"S. Berchtold , D. A. Keim , and H.-P. Kriegel . 1996 . The X-tree: an index structure for high-dimensional data . In Proc. of the 22nd Intl Conf. on Very Large Data Bases (VLDB). Mumbai (Bombay), India, 28--39 . S. Berchtold, D. A. Keim, and H.-P. Kriegel. 1996. The X-tree: an index structure for high-dimensional data. In Proc. of the 22nd Intl Conf. on Very Large Data Bases (VLDB). Mumbai (Bombay), India, 28--39."},{"volume-title":"Proc. of the 23rd Intl Conf. on Machine learning.","author":"Beygelzimer A.","key":"e_1_3_2_1_7_1","unstructured":"A. Beygelzimer , S. Kakade , and J. Langford . 2006. Cover trees for nearest neighbor . Proc. of the 23rd Intl Conf. on Machine learning. A. Beygelzimer, S. Kakade, and J. Langford. 2006. Cover trees for nearest neighbor. Proc. of the 23rd Intl Conf. on Machine learning."},{"volume-title":"Proceedings. Springer.","author":"Boytsov L.","key":"e_1_3_2_1_8_1","unstructured":"L. Boytsov and B. Naidan . 2013. Engineering Efficient and Effective Non-metric Space Library. In Similarity Search and Applications - 6th Intl Conf., SISAP, A Coru\u00f1a, Spain , Proceedings. Springer. L. Boytsov and B. Naidan. 2013. Engineering Efficient and Effective Non-metric Space Library. In Similarity Search and Applications - 6th Intl Conf., SISAP, A Coru\u00f1a, Spain, Proceedings. Springer."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"G-I Brokos P. Malakasiotis and I. Androutsopoulos. 2016. Using centroids of word embeddings and word mover's distance for biomedical document retrieval in question answering. arXiv preprint arXiv:1608.03905.  G-I Brokos P. Malakasiotis and I. Androutsopoulos. 2016. Using centroids of word embeddings and word mover's distance for biomedical document retrieval in question answering. arXiv preprint arXiv:1608.03905.","DOI":"10.18653\/v1\/W16-2915"},{"volume-title":"Proc. of the IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, I--I.","author":"Grauman K.","key":"e_1_3_2_1_10_1","unstructured":"K. Grauman and T. Darrell . 2004. Fast contour matching using approximate earth mover's distance . Proc. of the IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, I--I. K. Grauman and T. Darrell. 2004. Fast contour matching using approximate earth mover's distance. Proc. of the IEEE Computer Society Conf. on Computer Vision and Pattern Recognition, I--I."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"volume-title":"Deep Residual Learning for Image Recognition. In IEEE Conf. on Computer Vision and Pattern Recognition (CVPR). 770--778","author":"He K.","key":"e_1_3_2_1_12_1","unstructured":"K. He , X. Zhang , S. Ren , and J. Sun . 2016 . Deep Residual Learning for Image Recognition. In IEEE Conf. on Computer Vision and Pattern Recognition (CVPR). 770--778 . K. He, X. Zhang, S. Ren, and J. Sun. 2016. Deep Residual Learning for Image Recognition. In IEEE Conf. on Computer Vision and Pattern Recognition (CVPR). 770--778."},{"key":"e_1_3_2_1_13_1","unstructured":"G. R. Hjaltason and H. Samet. 2000. Incremental similarity search in multimedia databases. Computer Science Technical Report TR-4199. University of Maryland College Park MD.  G. R. Hjaltason and H. Samet. 2000. Incremental similarity search in multimedia databases. Computer Science Technical Report TR-4199. University of Maryland College Park MD."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"G. R. Hjaltason and H. Samet. 2003. Properties of embedding methods for similarity searching in metric spaces. 25 5 530--549.  G. R. Hjaltason and H. Samet. 2003. Properties of embedding methods for similarity searching in metric spaces. 25 5 530--549.","DOI":"10.1109\/TPAMI.2003.1195989"},{"key":"e_1_3_2_1_15_1","unstructured":"G. Huang C. Guo M. J Kusner Y. Sun F. Sha and K. Q Weinberger. 2016. Supervised word mover's distance. In Advances in Neural Information Processing Systems. 4862--4870.  G. Huang C. Guo M. J Kusner Y. Sun F. Sha and K. Q Weinberger. 2016. Supervised word mover's distance. In Advances in Neural Information Processing Systems. 4862--4870."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"H. Jegou M. Douze and C. Schmid. 2010. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 33 1 117--128.  H. Jegou M. Douze and C. Schmid. 2010. Product quantization for nearest neighbor search. IEEE transactions on pattern analysis and machine intelligence 33 1 117--128.","DOI":"10.1109\/TPAMI.2010.57"},{"key":"e_1_3_2_1_17_1","unstructured":"J. Johnson M. Douze and H. J\u00e9gou. 2017. Billion-scale similarity search with GPUs. arXiv preprint arXiv:1702.08734.  J. Johnson M. Douze and H. J\u00e9gou. 2017. Billion-scale similarity search with GPUs. arXiv preprint arXiv:1702.08734."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1058"},{"key":"e_1_3_2_1_19_1","volume-title":"IEEE Conf. on Computer Vision and Pattern Recognition","volume":"2","author":"Nilsback M-E","unstructured":"M-E Nilsback and A. Zisserman . 2006. A Visual Vocabulary for Flower Classification . In IEEE Conf. on Computer Vision and Pattern Recognition , Vol. 2 . 1447--1454. M-E Nilsback and A. Zisserman. 2006. A Visual Vocabulary for Flower Classification. In IEEE Conf. on Computer Vision and Pattern Recognition, Vol. 2. 1447--1454."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"H. Noltemeier K. Verbarg and C. Zirkelbach. 1992. Monotonous bisector* trees - a tool for efficient partitioning of complex scenes of geometric objects. In Data Structures and Efficient Algorithms (vol. 594 of Springer-Verlag Lecture Notes in Computer Science). Berlin West Germany.  H. Noltemeier K. Verbarg and C. Zirkelbach. 1992. Monotonous bisector * trees - a tool for efficient partitioning of complex scenes of geometric objects. In Data Structures and Efficient Algorithms (vol. 594 of Springer-Verlag Lecture Notes in Computer Science). Berlin West Germany.","DOI":"10.1007\/3-540-55488-2_27"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"H. Noltemeier K. Verbarg and C. Zirkelbach. 1993. A data structure for representing and efficient querying large scenes of geometric objects: mb*-trees. In Geometric Modelling Computing\/Supplement 8. Springer-Verlag Vienna Austria 211--226.  H. Noltemeier K. Verbarg and C. Zirkelbach. 1993. A data structure for representing and efficient querying large scenes of geometric objects: mb * -trees. In Geometric Modelling Computing\/Supplement 8. Springer-Verlag Vienna Austria 211--226.","DOI":"10.1007\/978-3-7091-6916-2_14"},{"volume-title":"IEEE 12th Intl Conf. on Computer Vision, ICCV","author":"Pele O.","key":"e_1_3_2_1_22_1","unstructured":"O. Pele and M. Werman . 2009. Fast and robust Earth Mover's Distances . In IEEE 12th Intl Conf. on Computer Vision, ICCV , Kyoto, Japan. IEEE Computer Society, 460--467. O. Pele and M. Werman. 2009. Fast and robust Earth Mover's Distances. In IEEE 12th Intl Conf. on Computer Vision, ICCV, Kyoto, Japan. IEEE Computer Society, 460--467."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"I. R. V. Pola A. J. M. Traina and C. Traina. 2009. Easing the Dimensionality Curse by Stretching Metric Spaces. In Scientific and Statistical Database Management. Springer Berlin Heidelberg Berlin Heidelberg 417--434.  I. R. V. Pola A. J. M. Traina and C. Traina. 2009. Easing the Dimensionality Curse by Stretching Metric Spaces. In Scientific and Statistical Database Management. Springer Berlin Heidelberg Berlin Heidelberg 417--434.","DOI":"10.1007\/978-3-642-02279-1_30"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026543900054"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/358172.358409"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"H. Samet. 1985. Reconstruction of quadtrees from quadtree medial axis transforms. Computer vision graphics and image processing 29 3 311--328.  H. Samet. 1985. Reconstruction of quadtrees from quadtree medial axis transforms. Computer vision graphics and image processing 29 3 311--328.","DOI":"10.1016\/0734-189X(85)90128-8"},{"key":"e_1_3_2_1_27_1","volume-title":"Symposium on Large Spatial Databases. Springer, 191--212","author":"Samet H.","year":"1989","unstructured":"H. Samet . 1989 . Hierarchical spatial data structures . In Symposium on Large Spatial Databases. Springer, 191--212 . H. Samet. 1989. Hierarchical spatial data structures. In Symposium on Large Spatial Databases. Springer, 191--212."},{"volume-title":"Foundations of Multidimensional and Metric Data Structures","author":"Samet H.","key":"e_1_3_2_1_28_1","unstructured":"H. Samet . 2006. Foundations of Multidimensional and Metric Data Structures . Morgan Kaufmann Publishers Inc . H. Samet. 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann Publishers Inc."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.75"},{"volume-title":"IEEE Computer Society Conf. on Computer Vision and Pattern Recognition (CVPR)","author":"Shirdhonkar S.","key":"e_1_3_2_1_30_1","unstructured":"S. Shirdhonkar and D. W. Jacobs . 2008. Approximate earth mover's distance in linear time . In IEEE Computer Society Conf. on Computer Vision and Pattern Recognition (CVPR) , Anchorage, Alaska, USA. IEEE Computer Society. S. Shirdhonkar and D. W. Jacobs. 2008. Approximate earth mover's distance in linear time. In IEEE Computer Society Conf. on Computer Vision and Pattern Recognition (CVPR), Anchorage, Alaska, USA. IEEE Computer Society."},{"volume-title":"21st Intl Conf. on Data Engineering (ICDE'05)","author":"Tanin E.","key":"e_1_3_2_1_31_1","unstructured":"E. Tanin , A. Harwood , and H. Samet . 2005. A distributed quadtree index for peer-to-peer settings . In 21st Intl Conf. on Data Engineering (ICDE'05) . IEEE, 254--255. E. Tanin, A. Harwood, and H. Samet. 2005. A distributed quadtree index for peer-to-peer settings. In 21st Intl Conf. on Data Engineering (ICDE'05). IEEE, 254--255."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90074-R"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.955109"},{"volume-title":"Proceedings of the Intl Conf. on Imaging Science, Systems and Technology, CISST","author":"Wu L.","key":"e_1_3_2_1_34_1","unstructured":"L. Wu and T. Bretschneider . 2004. VP-EMD Tree: An Efficient Indexing Strategy for Image Retrieval . In Proceedings of the Intl Conf. on Imaging Science, Systems and Technology, CISST , Las Vegas, Nevada, USA. CSREA Press, 421--426. L. Wu and T. Bretschneider. 2004. VP-EMD Tree: An Efficient Indexing Strategy for Image Retrieval. In Proceedings of the Intl Conf. on Imaging Science, Systems and Technology, CISST, Las Vegas, Nevada, USA. CSREA Press, 421--426."},{"key":"e_1_3_2_1_35_1","volume-title":"Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Yianilos P. N.","year":"1993","unstructured":"P. N. Yianilos . 1993 . Data structures and algorithms for nearest neighbor search in general metric spaces . In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms . Austin, TX, 311--321. P. N. Yianilos. 1993. Data structures and algorithms for nearest neighbor search in general metric spaces. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms. Austin, TX, 311--321."},{"volume-title":"Proc. of the IEEE\/CVF Conf. on Computer Vision and Pattern Recognition (CVPR).","author":"Zhang C.","key":"e_1_3_2_1_36_1","unstructured":"C. Zhang , Y. Cai , G. Lin , and C. Shen . 2020. DeepEMD: Few-Shot Image Classification With Differentiable Earth Mover's Distance and Structured Classifiers . In Proc. of the IEEE\/CVF Conf. on Computer Vision and Pattern Recognition (CVPR). C. Zhang, Y. Cai, G. Lin, and C. Shen. 2020. DeepEMD: Few-Shot Image Classification With Differentiable Earth Mover's Distance and Structured Classifiers. In Proc. of the IEEE\/CVF Conf. on Computer Vision and Pattern Recognition (CVPR)."}],"event":{"name":"GeoSearch '23: 2nd ACM SIGSPATIAL International Workshop on Searching and Mining Large Collections of Geospatial Data","sponsor":["SIGSPATIAL ACM Special Interest Group on Spatial Information"],"location":"Hamburg Germany","acronym":"GeoSearch '23"},"container-title":["Proceedings of the 2nd ACM SIGSPATIAL International Workshop on Searching and Mining Large Collections of Geospatial Data"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3615890.3628531","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3615890.3628531","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:28Z","timestamp":1750178188000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3615890.3628531"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,13]]},"references-count":36,"alternative-id":["10.1145\/3615890.3628531","10.1145\/3615890"],"URL":"https:\/\/doi.org\/10.1145\/3615890.3628531","relation":{},"subject":[],"published":{"date-parts":[[2023,11,13]]},"assertion":[{"value":"2023-12-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}