arXiv:2606.24204cs.DBcs.IR2026-06

统一主导图提升区间查询近邻搜索效率,支持多种时间/价格范围查询。

Unified Dominance Graph for Interval-Predicate Approximate Nearest Neighbor Search

  • 构建统一主导图,将区间端点映射到二维空间,统一处理包含、重叠等查询
  • 在多个数据集上查询性能优于现有方法,且索引开销低
  • 适合需要多类型区间约束的实时检索场景,如金融分析、时序数据库

近似最近邻搜索(ANNS)是无结构数据检索的核心技术。真实场景如时序数据库、金融数据分析和检索增强生成,常需基于连续区间属性(如寿命或价格范围)的混合查询。本文研究区间谓词近邻搜索(IPANNS),其中有效性由对象区间与查询区间间的谓词决定。现有范围过滤型近邻搜索(RFANNS)方法仅适用于单维标量过滤,而包含、重叠等区间谓词依赖两个耦合的端点约束。将端点视为独立标量会引入巨大交集开销,而专用包含方法缺乏通用索引抽象。本文提出统一主导图(UDG),一种针对IPANNS闭合两边界合取片段的图索引框架。对选定的区间谓词,UDG将对象和查询端点映射至归一化二维主导空间,并在此构建带主导标签的图。包含、重叠等端点约束谓词可通过语义映射复用相同构造与搜索算法,每个UDG实例仅绑定特定谓词。UDG将查询状态相关的近邻图压缩为单一紧凑索引。为提升受限区间过滤下的搜索效率,引入保持有效性的补丁边,提供路由选择。在标准基准和真实数据集上的大量实验表明,UDG在多种区间关系与工作负载下均实现稳定查询性能,显著优于现有混合搜索基线,同时保持低索引开销。

原文摘要 · Abstract (English)

Approximate Nearest Neighbor Search (ANNS) is a core primitive for unstructured data retrieval. Real-world applications--such as temporal databases, financial data analysis, and retrieval-augmented generation--often require hybrid queries whose valid objects are constrained by continuous interval attributes, such as lifespans or price ranges. We study Interval-Predicate ANNS (IPANNS), where validity is determined by a predicate between an object interval and a query interval. Existing range-filtering ANNS (RFANNS) methods are designed for single-dimensional scalar filters, but interval predicates such as containment and overlap rely on two coupled endpoint constraints. Treating endpoints as independent scalar attributes can incur large intersection overhead, while containment-specific methods lack a generalized indexing abstraction. In this paper, we propose the Unified Dominance Graph (UDG), a graph-indexing framework for the closed two-bound conjunctive fragment of IPANNS. For a chosen interval predicate, UDG maps object and query endpoints into a normalized two-dimensional dominance space and builds a dominance-labeled graph over the transformed coordinates. Containment, overlap, and other supported endpoint-bound predicates therefore reuse the same construction and search algorithms after semantic mapping, while each UDG instance remains tied to its selected predicate. UDG compresses query-state-specific proximity graphs into one compact index. To improve graph search under restrictive interval filters, we add validity-preserving patch edges that provide routing choices when few objects remain valid. Extensive evaluations on standard benchmarks and real-world datasets show that UDG achieves stable query performance across multiple interval relations and workloads, significantly outperforming existing hybrid search baselines while maintaining low indexing overhead.

近邻搜索区间查询图索引高效检索

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