{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T15:19:26Z","timestamp":1759331966622},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,6]]},"abstract":"<jats:p>Similarity search finds similar objects for a given query object based on a certain similarity metric. Similarity search in metric spaces has attracted increasing attention, as the metric space can accommodate any type of data and support flexible distance metrics. However, a metric space only models a single data type with a specific similarity metric. In contrast, a multi-metric space combines multiple metric spaces to simultaneously model a variety of data types and a collection of associated similarity metrics. Thus, a multi-metric space is capable of performing similarity search over any combination of metric spaces. Many studies focus on indexing a single metric space, while only a few aims at indexing multi-metric space to accelerate similarity search. In this paper, we propose DESIRE, an efficient dynamic cluster-based forest index for similarity search in multi-metric spaces. DESIRE first selects high-quality centers to cluster objects into compact regions, and then employs B<jats:sup>+<\/jats:sup>-trees to effectively index distances between centers and corresponding objects. To support dynamic scenarios, efficient update strategies are developed. Further, we provide filtering techniques to accelerate similarity queries in multi-metric spaces. Extensive experiments on four real datasets demonstrate the superior efficiency and scalability of our proposed DESIRE compared with the state-of-the-art multi-metric space indexes.<\/jats:p>","DOI":"10.14778\/3547305.3547317","type":"journal-article","created":{"date-parts":[[2022,9,7]],"date-time":"2022-09-07T16:09:53Z","timestamp":1662566993000},"page":"2121-2133","source":"Crossref","is-referenced-by-count":6,"title":["DESIRE"],"prefix":"10.14778","volume":"15","author":[{"given":"Yifan","family":"Zhu","sequence":"first","affiliation":[{"name":"Zhejiang University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lu","family":"Chen","sequence":"additional","affiliation":[{"name":"Zhejiang University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yunjun","family":"Gao","sequence":"additional","affiliation":[{"name":"Zhejiang University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Baihua","family":"Zheng","sequence":"additional","affiliation":[{"name":"Singapore Management University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pengfei","family":"Wang","sequence":"additional","affiliation":[{"name":"Zhejiang University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,9,7]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Molecular-level similarity search brings computing to DNA data storage. Nature communications 12, 1","author":"Bee Callista","year":"2021","unstructured":"Callista Bee , Yuan-Jyue Chen , Melissa Queen , David Ward , Xiaomeng Liu , Lee Organick , Georg Seelig , Karin Strauss , and Luis Ceze . 2021. Molecular-level similarity search brings computing to DNA data storage. Nature communications 12, 1 ( 2021 ), 1--9. Callista Bee, Yuan-Jyue Chen, Melissa Queen, David Ward, Xiaomeng Liu, Lee Organick, Georg Seelig, Karin Strauss, and Luis Ceze. 2021. Molecular-level similarity search brings computing to DNA data storage. Nature communications 12, 1 (2021), 1--9."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Tolga Bozkaya and Z. Meral \u00d6zsoyoglu. 1997. Distance-Based Indexing for High-Dimensional Metric Spaces. In SIGMOD. 357--368. Tolga Bozkaya and Z. Meral \u00d6zsoyoglu. 1997. Distance-Based Indexing for High-Dimensional Metric Spaces. In SIGMOD. 357--368.","DOI":"10.1145\/253262.253345"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/328939.328959"},{"key":"e_1_2_1_4_1","unstructured":"Sergey Brin. 1995. Near Neighbor Search in Large Metric Spaces. In VLDB. 574--584. Sergey Brin. 1995. Near Neighbor Search in Large Metric Spaces. In VLDB. 574--584."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Benjamin Bustos Daniel A. Keim and Tobias Schreck. 2005. A pivot-based index structure for combination of feature vectors. In SAC. 1180--1184. Benjamin Bustos Daniel A. Keim and Tobias Schreck. 2005. A pivot-based index structure for combination of feature vectors. In SAC. 1180--1184.","DOI":"10.1145\/1066677.1066945"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11042-011-0731-3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1178677.1178698"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2015.10.014"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/SPIRE.2000.878182"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2004.11.014"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502808"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Lu Chen Yunjun Gao Xinhan Li Christian S. Jensen and Gang Chen. 2015. Efficient metric indexing for similarity search. In ICDE. 591--602. Lu Chen Yunjun Gao Xinhan Li Christian S. Jensen and Gang Chen. 2015. Efficient metric indexing for similarity search. In ICDE. 591--602.","DOI":"10.1109\/ICDE.2015.7113317"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2506556"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3115404.3115411"},{"key":"e_1_2_1_16_1","volume-title":"DELOS","volume":"001","author":"Ciaccia Paolo","year":"2000","unstructured":"Paolo Ciaccia and Marco Patella . 2000 . The M2-tree: Processing Complex Multi-Feature Queries with Just One Index . In DELOS , Vol. 01\/W 001 . Paolo Ciaccia and Marco Patella. 2000. The M2-tree: Processing Complex Multi-Feature Queries with Just One Index. In DELOS, Vol. 01\/W001."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/582410.582412"},{"key":"e_1_2_1_18_1","volume-title":"M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. In VLDB. 426--435.","author":"Ciaccia Paolo","year":"1997","unstructured":"Paolo Ciaccia , Marco Patella , and Pavel Zezula . 1997 . M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. In VLDB. 426--435. Paolo Ciaccia, Marco Patella, and Pavel Zezula. 1997. M-tree: An Efficient Access Method for Similarity Search in Metric Spaces. In VLDB. 426--435."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Maximilian Franzke Tobias Emrich Andreas Z\u00fcfle and Matthias Renz. 2016. Indexing multi-metric data. In ICDE. 1122--1133. Maximilian Franzke Tobias Emrich Andreas Z\u00fcfle and Matthias Renz. 2016. Indexing multi-metric data. In ICDE. 1122--1133.","DOI":"10.1109\/ICDE.2016.7498318"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/958942.958948"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.2.180"},{"key":"e_1_2_1_22_1","volume-title":"Soliman","author":"Ilyas Ihab F.","year":"2008","unstructured":"Ihab F. Ilyas , George Beskales , and Mohamed A . Soliman . 2008 . A survey of top-k query processing techniques in relational database systems. ACM Comput. Surv . 40, 4 (2008), 11:1--11:58. Ihab F. Ilyas, George Beskales, and Mohamed A. Soliman. 2008. A survey of top-k query processing techniques in relational database systems. ACM Comput. Surv. 40, 4 (2008), 11:1--11:58."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071612"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0178-0"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Yongjiang Liang and Peixiang Zhao. 2017. Similarity Search in Graph Databases: A Multi-Layered Indexing Approach. In ICDE. 783--794. Yongjiang Liang and Peixiang Zhao. 2017. Similarity Search in Graph Databases: A Multi-Layered Indexing Approach. In ICDE. 783--794.","DOI":"10.1109\/ICDE.2017.129"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0481-6"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(94)90095-7"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780200060"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2010.10.002"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3403896.3403967"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Tom\u00e1s Skopal Jaroslav Pokorn\u00fd and V\u00e1clav Sn\u00e1sel. 2004. PM-tree: Pivoting Metric Tree for Similarity Search in Multimedia Databases. In ADBIS. 803--815. Tom\u00e1s Skopal Jaroslav Pokorn\u00fd and V\u00e1clav Sn\u00e1sel. 2004. PM-tree: Pivoting Metric Tree for Similarity Search in Multimedia Databases. In ADBIS. 803--815.","DOI":"10.1007\/11408079_73"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90074-R"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(86)90013-9"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Qitong Wang and Themis Palpanas. 2021. Deep Learning Embeddings for Data Series Similarity Search. In KDD. 1708--1716. Qitong Wang and Themis Palpanas. 2021. Deep Learning Embeddings for Data Series Similarity Search. In KDD. 1708--1716.","DOI":"10.1145\/3447548.3467317"},{"key":"e_1_2_1_35_1","unstructured":"Peter N. Yianilos. 1993. Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces. In SODA. 311--321. Peter N. Yianilos. 1993. Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces. In SODA. 311--321."},{"key":"e_1_2_1_36_1","unstructured":"Albert Yu Pankaj K. Agarwal and Jun Yang. 2012. Processing a large number of continuous preference top-k queries. In SIGMOD. 397--408. Albert Yu Pankaj K. Agarwal and Jun Yang. 2012. Processing a large number of continuous preference top- k queries. In SIGMOD. 397--408."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2451630"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"Guilherme F. Zabot Mirela T. Cazzolato Lucas C. Scabora Agma J. M. Traina and Caetano Traina. 2019. Efficient Indexing of Multiple Metric Spaces with Spectra. In ISM. 169--176. Guilherme F. Zabot Mirela T. Cazzolato Lucas C. Scabora Agma J. M. Traina and Caetano Traina. 2019. Efficient Indexing of Multiple Metric Spaces with Spectra. In ISM. 169--176.","DOI":"10.1109\/ISM46123.2019.00038"},{"key":"e_1_2_1_39_1","volume-title":"Rundensteiner","author":"Zhang Huayi","year":"2020","unstructured":"Huayi Zhang , Lei Cao , Yizhou Yan , Samuel Madden , and Elke A . Rundensteiner . 2020 . Continuously Adaptive Similarity Search. In SIGMOD. 2601--2616. Huayi Zhang, Lei Cao, Yizhou Yan, Samuel Madden, and Elke A. Rundensteiner. 2020. Continuously Adaptive Similarity Search. In SIGMOD. 2601--2616."},{"key":"e_1_2_1_40_1","first-page":"280","article-title":"Scalable Multi-grained Cross-modal Similarity Query with Interpretability. Data Sci","volume":"6","author":"Zhu Mingdong","year":"2021","unstructured":"Mingdong Zhu , Derong Shen , Lixin Xu , and Xianfang Wang . 2021 . Scalable Multi-grained Cross-modal Similarity Query with Interpretability. Data Sci . Eng. 6 , 3 (2021), 280 -- 293 . Mingdong Zhu, Derong Shen, Lixin Xu, and Xianfang Wang. 2021. Scalable Multi-grained Cross-modal Similarity Query with Interpretability. Data Sci. Eng. 6, 3 (2021), 280--293.","journal-title":"Eng."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00691-4"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3547305.3547317","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,3]],"date-time":"2024-10-03T11:19:52Z","timestamp":1727954392000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3547305.3547317"}},"subtitle":["an efficient dynamic cluster-based forest indexing for similarity search in multi-metric spaces"],"short-title":[],"issued":{"date-parts":[[2022,6]]},"references-count":40,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["10.14778\/3547305.3547317"],"URL":"https:\/\/doi.org\/10.14778\/3547305.3547317","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2022,6]]}}}