{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T21:47:44Z","timestamp":1775598464166,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"Natural Sciences and Engineering Research Council of Canada","award":["RGPIN-2020-05408"],"award-info":[{"award-number":["RGPIN-2020-05408"]}]},{"name":"European Union's Horizon Europe Research and Innovation programme","award":["101188416"],"award-info":[{"award-number":["101188416"]}]},{"name":"Research Grant Council of Hong Kong","award":["17202325"],"award-info":[{"award-number":["17202325"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,4,2]]},"abstract":"<jats:p>\n                    We study Aggregation Queries over Nearest Neighbors (AQNN), which compute aggregates over the learned representations of the neighborhood of a designated query object. For example, a medical professional may be interested in\n                    <jats:italic toggle=\"yes\">the average heart rate of patients whose representations are similar to that of an insomnia patient.<\/jats:italic>\n                    Answering AQNNs accurately and efficiently is challenging due to the high cost of generating high-quality representations (e.g., via a deep learning model trained on human expert annotations) and the different sensitivities of different aggregation functions to neighbor selection errors. We address these challenges by combining high-quality and low-cost representations to approximate the aggregate. We characterize value- and count-sensitive AQNNs and propose the\n                    <jats:italic toggle=\"yes\">Sampler with Precision-Recall in Target<\/jats:italic>\n                    (\n                    <jats:sc>SPRinT<\/jats:sc>\n                    ), a query answering framework that works in three steps: (1) sampling, (2) nearest neighbor selection, and (3) aggregation. We further establish theoretical bounds on sample sizes and aggregation errors. Extensive experiments on five datasets from three domains (medical, social media, and e-commerce) demonstrate that\n                    <jats:sc>SPRinT<\/jats:sc>\n                    achieves the lowest aggregation error with minimal computation cost in most cases compared to existing solutions.\n                    <jats:sc>SPRinT<\/jats:sc>\n                    's performance remains stable as dataset size grows, confirming its scalability for large-scale applications requiring both accuracy and efficiency.\n                  <\/jats:p>","DOI":"10.1145\/3786672","type":"journal-article","created":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T17:54:13Z","timestamp":1775584453000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["On Efficient Approximate Aggregate Nearest Neighbor Queries over Learned Representations"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-7638-1448","authenticated-orcid":false,"given":"Carrie","family":"Wang","sequence":"first","affiliation":[{"name":"The University of Hong Kong, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6194-4502","authenticated-orcid":false,"given":"Sihem","family":"Amer-Yahia","sequence":"additional","affiliation":[{"name":"CNRS, Univ. Grenoble Alpes, Grenoble, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9775-4241","authenticated-orcid":false,"given":"Laks V.S.","family":"Lakshmanan","sequence":"additional","affiliation":[{"name":"The University of British Columbia, Vancouver, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9480-9809","authenticated-orcid":false,"given":"Reynold","family":"Cheng","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2015. Yelp Dataset. https:\/\/www.yelp.com\/dataset."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2465351.2465355"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00132"},{"key":"e_1_2_1_4_1","volume-title":"Hd-index: Pushing the scalability-accuracy boundary for approximate knn search in high-dimensional spaces. arXiv preprint arXiv:1804.06829","author":"Arora Akhil","year":"2018","unstructured":"Akhil Arora, Sakshi Sinha, Piyush Kumar, and Arnab Bhattacharya. 2018. Hd-index: Pushing the scalability-accuracy boundary for approximate knn search in high-dimensional spaces. arXiv preprint arXiv:1804.06829 (2018)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Jon L Bentley. 1975. A survey of techniques for fixed radius near neighbor searching. Technical Report. Stanford University Stanford CA USA.","DOI":"10.2172\/1453938"},{"key":"e_1_2_1_6_1","volume-title":"Approximate Query Processing Using Wavelets. In VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases, September 10--14","author":"Chakrabarti Kaushik","year":"2000","unstructured":"Kaushik Chakrabarti, Minos N. Garofalakis, Rajeev Rastogi, and Kyuseok Shim. 2000. Approximate Query Processing Using Wavelets. In VLDB 2000, Proceedings of 26th International Conference on Very Large Data Bases, September 10--14, 2000, Cairo, Egypt. Morgan Kaufmann, 111--122."},{"key":"e_1_2_1_7_1","volume-title":"nithum, and Will Cukierski","author":"Sorensen Jeffrey","year":"2017","unstructured":"cjadams, Jeffrey Sorensen, Julia Elliott, Lucas Dixon, Mark McDonald, nithum, and Will Cukierski. 2017. Toxic Comment Classification Challenge. https:\/\/kaggle.com\/competitions\/jigsaw-toxic-comment-classification-challenge."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3574245.3574273"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355745"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0865-5_26"},{"key":"e_1_2_1_11_1","volume-title":"Bridging Language and Items for Retrieval and Recommendation. arXiv preprint arXiv:2403.03952","author":"Hou Yupeng","year":"2024","unstructured":"Yupeng Hou, Jiacheng Li, Zhankui He, An Yan, Xiusi Chen, and Julian McAuley. 2024. Bridging Language and Items for Retrieval and Recommendation. arXiv preprint arXiv:2403.03952 (2024)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850470"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_14_1","volume-title":"Conference On Learning Theory. PMLR","author":"Indyk Piotr","year":"2018","unstructured":"Piotr Indyk and Tal Wagner. 2018. Approximate nearest neighbors in limited space. In Conference On Learning Theory. PMLR, 2012--2036."},{"key":"e_1_2_1_15_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_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.INS.2020.09.024"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137664"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407804"},{"key":"e_1_2_1_19_1","volume-title":"Central limit theorem: the cornerstone of modern statistics. Korean journal of anesthesiology 70, 2","author":"Kwak Sang Gyu","year":"2017","unstructured":"Sang Gyu Kwak and Jong Hae Kim. 2017. Central limit theorem: the cornerstone of modern statistics. Korean journal of anesthesiology 70, 2 (2017), 144--156."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452786"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380600"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3183751"},{"key":"e_1_2_1_24_1","volume-title":"Proc. of 5th Berkeley Symposium on Math. Stat. and Prob. 281--297","author":"McQueen James B","year":"1967","unstructured":"James B McQueen. 1967. Some methods of classification and analysis of multivariate observations. In Proc. of 5th Berkeley Symposium on Math. Stat. and Prob. 281--297."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2014.2321376"},{"key":"e_1_2_1_26_1","volume-title":"Jesse D Raffa, Leo A Celi, Roger G Mark, and Omar Badawi.","author":"Pollard Tom J","year":"2018","unstructured":"Tom J Pollard, Alistair EW Johnson, Jesse D Raffa, Leo A Celi, Roger G Mark, and Omar Badawi. 2018. The eICU Collaborative Research Database, a freely available multi-center database for critical care research. Scientific data 5, 1 (2018), 1--13."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA45697.2020.00045"},{"key":"e_1_2_1_28_1","volume-title":"Probability inequalities for the sum in sampling without replacement. The Annals of Statistics","author":"Serfling Robert J","year":"1974","unstructured":"Robert J Serfling. 1974. Probability inequalities for the sum in sampling without replacement. The Annals of Statistics (1974), 39--48."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2008.4587638"},{"key":"e_1_2_1_30_1","volume-title":"Mpnet: Masked and permuted pre-training for language understanding. Advances in neural information processing systems 33","author":"Song Kaitao","year":"2020","unstructured":"Kaitao Song, Xu Tan, Tao Qin, Jianfeng Lu, and Tie-Yan Liu. 2020. Mpnet: Masked and permuted pre-training for language understanding. Advances in neural information processing systems 33 (2020), 16857--16867."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2017.2761740"},{"key":"e_1_2_1_32_1","volume-title":"Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems","author":"Wang Wenhui","year":"2020","unstructured":"Wenhui Wang, Furu Wei, Li Dong, Hangbo Bao, Nan Yang, and Ming Zhou. 2020. MiniLM: Deep Self-Attention Distillation for Task-Agnostic Compression of Pre-Trained Transformers. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6--12, 2020, virtual."},{"key":"e_1_2_1_33_1","volume-title":"Gliner: Generalist model for named entity recognition using bidirectional transformer. arXiv preprint arXiv:2311.08526","author":"Zaratiana Urchade","year":"2023","unstructured":"Urchade Zaratiana, Nadi Tomeh, Pierre Holat, and Thierry Charnois. 2023. Gliner: Generalist model for named entity recognition using bidirectional transformer. arXiv preprint arXiv:2311.08526 (2023)."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3786672","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T21:01:01Z","timestamp":1775595661000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3786672"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,2]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,4,2]]}},"alternative-id":["10.1145\/3786672"],"URL":"https:\/\/doi.org\/10.1145\/3786672","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,2]]}}}