{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,15]],"date-time":"2026-09-15T01:11:03Z","timestamp":1789434663716,"version":"build-2803163510"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,11]]},"abstract":"<jats:p>\n            In this paper, we study the problem of cardinality estimation for similarity search on high-dimensional data (CE4HD). We aim to perform CE4HD with high\n            <jats:italic>data robustness<\/jats:italic>\n            (i.e., robust to different datasets),\n            <jats:italic>query robustness<\/jats:italic>\n            (i.e., robust to large cardinality variance and scale) and efficiency. We propose to leverage the cardinality estimation of selected objects (called reference objects) in the database to achieve the above. Specifically, we propose two techniques that adopt different strategies to select and leverage reference objects, as well as strategies to support efficient computation in dynamic databases. Extensive experiments on datasets from diverse domains show that our methods achieve up to ~10x speed-up and up to ~136x smaller mean Q-error compared to existing studies.\n          <\/jats:p>","DOI":"10.14778\/3712221.3712224","type":"journal-article","created":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T18:03:04Z","timestamp":1744048984000},"page":"544-556","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects"],"prefix":"10.14778","volume":"18","author":[{"given":"Hai","family":"Lan","sequence":"first","affiliation":[{"name":"RMIT University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shixun","family":"Huang","sequence":"additional","affiliation":[{"name":"The University of Wollongong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhifeng","family":"Bao","sequence":"additional","affiliation":[{"name":"RMIT University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Renata","family":"Borovica-Gajic","sequence":"additional","affiliation":[{"name":"The University of Melbourne"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,4,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n. d.]. Faiss Source Code. https:\/\/https:\/\/github.com\/facebookresearch\/faiss."},{"key":"e_1_2_1_2_1","unstructured":"[n. d.]. Fasttext Dataset. https:\/\/fasttext.cc\/docs\/en\/english-vectors.html."},{"key":"e_1_2_1_3_1","unstructured":"[n. d.]. Glove Dataset. https:\/\/nlp.stanford.edu\/projects\/glove\/."},{"key":"e_1_2_1_4_1","unstructured":"[n. d.]. Seismic Dataset. http:\/\/ds.iris.edu\/data\/access\/."},{"key":"e_1_2_1_5_1","unstructured":"[n. d.]. SelNet Source Code. https:\/\/github.com\/yyssl88\/SelNet-Estimation."},{"key":"e_1_2_1_6_1","unstructured":"[n. d.]. SimCardCode. https:\/\/github.com\/greatji\/SimCard_code."},{"key":"e_1_2_1_7_1","unstructured":"[n. d.]. Supplied Material. https:\/\/github.com\/rmitbggroup\/CE4HD."},{"key":"e_1_2_1_8_1","unstructured":"[n. d.]. Youtube Dataset. https:\/\/www.cs.tau.ac.il\/~wolf\/ytfaces\/index.html."},{"key":"e_1_2_1_9_1","unstructured":"[n. d.]. Youtube Dataset. http:\/\/sites.skoltech.ru\/compvision\/noimi."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335388"},{"key":"e_1_2_1_11_1","article-title":"A Survey on Evaluation of Large Language Models","volume":"15","author":"Chang Yupeng","year":"2024","unstructured":"Yupeng Chang, Xu Wang, Jindong Wang, Yuan Wu, Linyi Yang, Kaijie Zhu, Hao Chen, Xiaoyuan Yi, Cunxiang Wang, Yidong Wang, Wei Ye, Yue Zhang, Yi Chang, Philip S. Yu, Qiang Yang, and Xing Xie. 2024. A Survey on Evaluation of Large Language Models. ACM Trans. Intell. Syst. Technol. 15, 3 (2024), 39:1--39:45.","journal-title":"ACM Trans. Intell. Syst. Technol."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3579075.3579087"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Yu Chen and Ke Yi. 2017. Two-Level Sampling for Join Size Estimation. In SIGMOD. 759--774.","DOI":"10.1145\/3035918.3035921"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Abhinandan Das Johannes Gehrke and Mirek Riedewald. 2004. Approximation Techniques for Spatial Data. In SIGMOD. ACM 695--706.","DOI":"10.1145\/1007568.1007646"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"112","DOI":"10.14778\/3282495.3282498","article-title":"The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art","volume":"12","author":"Echihabi Karima","year":"2018","unstructured":"Karima Echihabi, Kostas Zoumpatianos, Themis Palpanas, and Houda Benbrahim. 2018. The Lernaean Hydra of Data Series Similarity Search: An Experimental Evaluation of the State of the Art. Proc. VLDB Endow. 12, 2 (2018), 112--127.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611533"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3389133.3389135"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Alex Galakatos Michael Markovitch Carsten Binnig Rodrigo Fonseca and Tim Kraska. 2019. FITing-Tree: A Data-aware Index Structure. In SIGMOD. 1189--1206.","DOI":"10.1145\/3299869.3319860"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3503585.3503586"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384349"},{"key":"e_1_2_1_21_1","volume-title":"Breakthroughs in statistics: Methodology and distribution","author":"Huber Peter J","unstructured":"Peter J Huber. 1992. Robust estimation of a location parameter. In Breakthroughs in statistics: Methodology and distribution. Springer, 492--518."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Yannis E. Ioannidis. 2003. The History of Histograms (abridged). In VLDB. Morgan Kaufmann 19--30.","DOI":"10.1016\/B978-012722442-8\/50011-2"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Saehan Jo and Immanuel Trummer. 2023. Demonstration of ThalamusDB: Answering Complex SQL Queries with Natural Language Predicates on Multi-Modal Data. In SIGMOD. ACM 179--182.","DOI":"10.1145\/3555041.3589730"},{"key":"e_1_2_1_24_1","volume-title":"Leo Anthony Celi, and Roger G Mark","author":"Johnson Alistair EW","year":"2016","unstructured":"Alistair EW Johnson, Tom J Pollard, Lu Shen, Li-wei H Lehman, Mengling Feng, Mohammad Ghassemi, Benjamin Moody, Peter Szolovits, Leo Anthony Celi, and Roger G Mark. 2016. MIMIC-III, a freely accessible critical care database. Scientific data 3, 1 (2016), 1--9."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3611479.3611532"},{"key":"e_1_2_1_26_1","volume-title":"Seo, Wook-Shin Han, Kangwoo Choi, and Jaehyok Chong.","author":"Kim Kyoungmin","year":"2022","unstructured":"Kyoungmin Kim, Jisung Jung, In Seo, Wook-Shin Han, Kangwoo Choi, and Jaehyok Chong. 2022. Learned Cardinality Estimation: An In-depth Study. In SIGMOD. ACM, 1214--1227."},{"key":"e_1_2_1_27_1","volume-title":"Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In CIDR.","author":"Kipf Andreas","year":"2019","unstructured":"Andreas Kipf, Thomas Kipf, Bernhard Radke, Viktor Leis, Peter A. Boncz, and Alfons Kemper. 2019. Learned Cardinalities: Estimating Correlated Joins with Deep Learning. In CIDR."},{"key":"e_1_2_1_28_1","volume-title":"Jeffrey Dean, and Neoklis Polyzotis.","author":"Kraska Tim","year":"2018","unstructured":"Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The Case for Learned Index Structures. In SIGMOD. 489--504."},{"key":"e_1_2_1_29_1","first-page":"86","article-title":"A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration. Data Sci","volume":"6","author":"Lan Hai","year":"2021","unstructured":"Hai Lan, Zhifeng Bao, and Yuwei Peng. 2021. A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration. Data Sci. Eng. 6, 1 (2021), 86--101.","journal-title":"Eng."},{"key":"e_1_2_1_30_1","first-page":"86","article-title":"A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration. Data Sci","volume":"6","author":"Lan Hai","year":"2021","unstructured":"Hai Lan, Zhifeng Bao, and Yuwei Peng. 2021. A Survey on Advancing the DBMS Query Optimizer: Cardinality Estimation, Cost Model, and Plan Enumeration. Data Sci. Eng. 6, 1 (2021), 86--101.","journal-title":"Eng."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850583.2850594"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2909204"},{"key":"e_1_2_1_33_1","volume-title":"LHist: Towards Learning Multidimensional Histogram for Massive Spatial Data","author":"Liu Qiyu","unstructured":"Qiyu Liu, Yanyan Shen, and Lei Chen. 2021. LHist: Towards Learning Multidimensional Histogram for Massive Spatial Data. In ICDE. IEEE, 1188--1199."},{"key":"e_1_2_1_34_1","volume-title":"HAP: An Efficient Hamming Space Index Based on Augmented Pigeonhole Principle. In SIGMOD '22: International Conference on Management of Data","author":"Liu Qiyu","year":"2022","unstructured":"Qiyu Liu, Yanyan Shen, and Lei Chen. 2022. HAP: An Efficient Hamming Space Index Based on Augmented Pigeonhole Principle. In SIGMOD '22: International Conference on Management of Data, Philadelphia, PA, USA, June 12 - 17, 2022. ACM, 917--930."},{"key":"e_1_2_1_35_1","volume-title":"Yashunin","author":"Malkov Yury A.","year":"2016","unstructured":"Yury A. Malkov and Dmitry A. Yashunin. 2016. Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. CoRR abs\/1603.09320 (2016). http:\/\/arxiv.org\/abs\/1603.09320"},{"key":"e_1_2_1_36_1","volume-title":"DeWitt","author":"Muralikrishna M.","year":"1988","unstructured":"M. Muralikrishna and David J. DeWitt. 1988. Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries. In SIGMOD. ACM Press, 28--36."},{"key":"e_1_2_1_37_1","volume-title":"Survey of Vector Database Management Systems. CoRR abs\/2310.14021","author":"Pan James Jie","year":"2023","unstructured":"James Jie Pan, Jianguo Wang, and Guoliang Li. 2023. Survey of Vector Database Management Systems. CoRR abs\/2310.14021 (2023)."},{"key":"e_1_2_1_38_1","first-page":"120","article-title":"ACORN: Per-formant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data","volume":"2","author":"Patel Liana","year":"2024","unstructured":"Liana Patel, Peter Kraft, Carlos Guestrin, and Matei Zaharia. 2024. ACORN: Per-formant and Predicate-Agnostic Search Over Vector Embeddings and Structured Data. Proc. ACM Manag. Data 2, 3 (2024), 120.","journal-title":"Proc. ACM Manag. Data"},{"key":"e_1_2_1_39_1","volume-title":"FaceNet: A unified embedding for face recognition and clustering","author":"Schroff Florian","unstructured":"Florian Schroff, Dmitry Kalenichenko, and James Philbin. 2015. FaceNet: A unified embedding for face recognition and clustering. In CVPR. IEEE Computer Society, 815--823."},{"key":"e_1_2_1_40_1","first-page":"307","article-title":"An End-to-End Learning-based Cost Estimator","volume":"13","author":"Sun Ji","year":"2020","unstructured":"Ji Sun and Guoliang Li. 2020. An End-to-End Learning-based Cost Estimator. VLDB 13, 3 (2020), 307--319.","journal-title":"VLDB"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Ji Sun Guoliang Li and Nan Tang. 2021. Learned Cardinality Estimation for Similarity Queries. In SIGMOD. ACM 1745--1757.","DOI":"10.1145\/3448016.3452790"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Tin Vu Alberto Belussi Sara Migliorini and Ahmed Eldawy. 2021. A Learned Query Optimizer for Spatial Join. In SIGSPATIAL. ACM 458--467.","DOI":"10.1145\/3474717.3484217"},{"key":"e_1_2_1_43_1","volume-title":"Milvus: A Purpose-Built Vector Data Management System. In SIGMOD. ACM, 2614--2627.","author":"Wang Jianguo","year":"2021","unstructured":"Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, Kun Yu, Yuxing Yuan, Yinghao Zou, Jiquan Long, Yudong Cai, Zhenxiang Li, Zhifeng Zhang, Yihua Mo, Jun Gu, Ruiyi Jiang, Yi Wei, and Charles Xie. 2021. Milvus: A Purpose-Built Vector Data Management System. In SIGMOD. ACM, 2614--2627."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476255"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"TaiNing Wang and Chee-Yong Chan. 2020. Improved Correlated Sampling for Join Size Estimation. In ICDE. 325--336.","DOI":"10.1109\/ICDE48307.2020.00035"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Yaoshu Wang Chuan Xiao Jianbin Qin Xin Cao Yifang Sun Wei Wang and Makoto Onizuka. 2020. Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach. In SIGMOD. ACM 1197--1212.","DOI":"10.1145\/3318464.3380570"},{"key":"e_1_2_1_47_1","volume-title":"Consistent and Flexible Selectivity Estimation for High-dimensional Data. CoRR abs\/2005.09908","author":"Wang Yaoshu","year":"2020","unstructured":"Yaoshu Wang, Chuan Xiao, Jianbin Qin, Rui Mao, Makoto Onizuka, Wei Wang, and Rui Zhang. 2020. Consistent and Flexible Selectivity Estimation for High-dimensional Data. CoRR abs\/2005.09908 (2020)."},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Yaoshu Wang Chuan Xiao Jianbin Qin Rui Mao Makoto Onizuka Wei Wang Rui Zhang and Yoshiharu Ishikawa. 2021. Consistent and Flexible Selectivity Estimation for High-Dimensional Data. In SIGMOD. ACM 2319--2327.","DOI":"10.1145\/3448016.3452772"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2304.08264"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01231357"},{"key":"e_1_2_1_51_1","volume-title":"IWCTS 2014, Proceedings of the 7th ACM SIGSPATIAL International Workshop on Computational Transportation Science, Dallas\/Fort Worth, TX, USA","author":"Xie Hairuo","year":"2014","unstructured":"Hairuo Xie, Egemen Tanin, Lars Kulik, Peter Scheuermann, Goce Trajcevski, and Maryam Fanaeepour. 2014. Euler histogram tree: a spatial data structure for aggregate range queries on vehicle trajectories. In IWCTS 2014, Proceedings of the 7th ACM SIGSPATIAL International Workshop on Computational Transportation Science, Dallas\/Fort Worth, TX, USA, November 4, 2014. ACM, 18--24."},{"key":"e_1_2_1_52_1","first-page":"279","article-title":"Deep Unsupervised Cardinality Estimation","volume":"13","author":"Yang Zongheng","year":"2019","unstructured":"Zongheng Yang, Eric Liang, Amog Kamsetty, Chenggang Wu, Yan Duan, Peter Chen, Pieter Abbeel, Joseph M. Hellerstein, Sanjay Krishnan, and Ion Stoica. 2019. Deep Unsupervised Cardinality Estimation. VLDB 13, 3 (2019), 279--292.","journal-title":"VLDB"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461539"},{"key":"e_1_2_1_54_1","first-page":"1","volume-title":"Proc. ACM Manag. Data 2","author":"Zuo Chaoji","year":"2024","unstructured":"Chaoji Zuo, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. 2024. SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search. Proc. ACM Manag. Data 2, 1 (2024), 69:1--69:26."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3712221.3712224","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,7]],"date-time":"2025-04-07T18:26:02Z","timestamp":1744050362000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3712221.3712224"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11]]},"references-count":54,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["10.14778\/3712221.3712224"],"URL":"https:\/\/doi.org\/10.14778\/3712221.3712224","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,11]]},"assertion":[{"value":"2025-04-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}