arXiv:2502.18803cs.DScs.DB2025-02

用低成本近似方法高效计算相似数据的聚合统计,适合医疗等高精度场景。

On Efficient Approximate Aggregate Nearest Neighbor Queries over Learned Representations

  • 融合高质量与低耗表示,分三步采样、找邻、聚合
  • 在五个数据集上误差最低,计算开销最小
  • 对不同聚合函数敏感性有理论保障,适合大规模应用

我们研究基于最近邻的聚合查询(AQNN),即对指定查询对象邻域内学习表征的聚合结果进行计算。例如,医生可能关注与失眠患者表征相似的患者群体的平均心率。由于生成高质量表征(如通过人类专家标注训练的深度学习模型)成本高昂,且不同聚合函数对邻居选择错误的敏感度不同,准确高效地回答AQNN极具挑战。为此,我们结合高质量与低代价表示来近似聚合结果。我们定义了值敏感与数量敏感的AQNN,并提出SPRinT框架,包含三个步骤:采样、最近邻选择和聚合。我们进一步建立了样本量与聚合误差的理论边界。在来自医疗、社交媒体和电商三个领域的五个数据集上进行的大量实验表明,相较于现有方法,SPRinT在多数情况下以最小计算开销实现最低聚合误差。其性能随数据规模增长保持稳定,证实了其在需要兼顾准确性和效率的大规模应用场景中的可扩展性。

原文摘要 · Abstract (English)

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.

近邻查询聚合分析高效计算学习表征

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。