EUVIMEDEUVIMED entdecken
Crossref

On Efficient Approximate Aggregate Nearest Neighbor Queries over Learned Representations

Carrie Wang, Sihem Amer-Yahia, Laks V.S. Lakshmanan, Reynold Cheng

Proceedings of the ACM on Management of Data · 02.04.2026 · 4 (1) · 1-26

DOI: 10.1145/3786672 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 07.04.2026. Verfasst von Carrie Wang und 3 weiteren Autor:innen. Die Arbeit nennt 33 Literaturangaben. Gefördert von: Natural Sciences and Engineering Research Council of Canada, European Union's Horizon Europe Research and Innovation programme, Research Grant Council of Hong Kong.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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 the average heart rate of patients whose representations are similar to that of an insomnia patient. 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 Sampler with Precision-Recall in Target ( SPRinT ), 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 SPRinT achieves the lowest aggregation error with minimal computation cost in most cases compared to existing solutions. SPRinT 's performance remains stable as dataset size grows, confirming its scalability for large-scale applications requiring both accuracy and efficiency.

Förderung

  • Natural Sciences and Engineering Research Council of Canada
  • European Union's Horizon Europe Research and Innovation programme
  • Research Grant Council of Hong Kong

Zitieren

APA

Wang, C., Amer-Yahia, S., Lakshmanan, L. V., & Cheng, R. (2026). On Efficient Approximate Aggregate Nearest Neighbor Queries over Learned Representations. Proceedings of the ACM on Management of Data, 4(1), 1-26. https://doi.org/10.1145/3786672

Vancouver

Wang C, Amer-Yahia S, Lakshmanan LV, Cheng R. On Efficient Approximate Aggregate Nearest Neighbor Queries over Learned Representations. Proceedings of the ACM on Management of Data. 2026;4(1):1-26. doi:10.1145/3786672

BibTeX
@article{Wang2026,
  author = {Wang, Carrie and Amer-Yahia, Sihem and Lakshmanan, Laks V.S. and Cheng, Reynold},
  title = {On Efficient Approximate Aggregate Nearest Neighbor Queries over Learned Representations},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {1},
  pages = {1--26},
  doi = {10.1145/3786672}
}
Kostenlos starten →