論文の概要: Unified Dominance Graph for Interval-Predicate Approximate Nearest Neighbor Search

• arxiv url: http://arxiv.org/abs/2606.24204v1
• Date: Tue, 23 Jun 2026 06:46:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-24 22:16:48.806677
• Title: Unified Dominance Graph for Interval-Predicate Approximate Nearest Neighbor Search
• Title（参考訳）: 区間述語近似近傍探索のための統一支配グラフ
• Authors: Kwun Hang Lau, Ruiyuan Zhang, Elton Chun-Chai Li, Wun Yu Chan, Xiaojun Cheng, Xiaofang Zhou,
• Abstract要約: 我々は、オブジェクト間隔とクエリ間隔の間の述語によって妥当性が決定されるInterval-Predicate ANNSについて検討する。 既存のレンジフィルタANNS法は1次元スカラーフィルタのために設計されている。 We propose the Unified Dominance Graph (UDG) a graph-indexing framework for the closed two-bound conjunctive fragment of IPANNS。
• 参考スコア（独自算出の注目度）: 8.875776605139185
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.
• Abstract（参考訳）: Approximate Nearest Neighbor Search (ANNS)は、非構造化データ検索のコアプリミティブである。 リアルタイムアプリケーション - 時間データベース、財務データ分析、検索強化生成など は、しばしば、有効オブジェクトがライフスパンや価格範囲などの連続的な間隔属性によって制約されるハイブリッドクエリを必要とする。 IPANNS(Interval-Predicate ANNS)では、オブジェクト間隔とクエリ間隔の間の述語によって妥当性が決定される。 既存のレンジフィルタANNS(RFANNS)法は1次元スカラーフィルタのために設計されているが、包含や重なり合いなどの区間述語は2つの結合エンドポイント制約に依存する。 エンドポイントを独立したスカラー属性として扱うことは、大きな交差点のオーバーヘッドを引き起こす可能性があるが、包摂的メソッドには一般化されたインデックスの抽象化が欠如している。 本稿では, IPANNS の閉2行共役フラグメントのためのグラフインデクシングフレームワークである Unified Dominance Graph (UDG) を提案する。 選択した間隔述語に対して、UDGはオブジェクトとクエリエンドポイントを正規化された2次元支配空間にマッピングし、変換された座標の上に支配ラベル付きグラフを構築する。 したがって、各UDGインスタンスはその選択した述語に結びついているのに対して、セマンティックマッピングの後に同じ構築アルゴリズムと検索アルゴリズムを再利用する。 UDGはクエリ状態固有の近接グラフを1つのコンパクトインデックスに圧縮する。 制限間隔フィルタ下でのグラフ探索を改善するために,少数のオブジェクトが有効である場合のルーティング選択を提供する,妥当性保持パッチエッジを追加する。 標準ベンチマークと実世界のデータセットの大規模な評価は、UDGが複数のインターバル関係とワークロードにわたる安定したクエリパフォーマンスを実現し、インデックス化のオーバーヘッドを低く保ちながら、既存のハイブリッド検索ベースラインを大幅に上回っていることを示している。

関連論文リスト

• Hyperdimensional computing for structured querying on tabular data embeddings [2.260258863997296]
  タブラルデータ埋め込みは、データプロファイリングとデータ統合パイプラインの基盤となっている。 既存のアプローチでは、行、列、またはテーブル全体をベクトル空間に埋め込んで、最も近い隣の検索を使って候補マッチングを検索する。 現在の埋め込み法の基本的な制限は、解釈可能な類似性スコアの欠如である。
  論文  参考訳（メタデータ） (2026-06-11T19:54:11Z)
• GONDOR to the Rescue: Satisficing Planning with Low Memory [80.8869960059932]
  GONDORはGreedy Best-First Search(GBFS)の拡張である GONDORは、アンカー状態のスパースセットを保持しながら周期的に探索木を圧縮し、ゴールに達するとスパース状態間の再探索によって経路を再構築する。 実験により、GONDORは標準のGBFSと比較して、低メモリ予算下でのカバレッジを一貫して改善することが示された。
  論文  参考訳（メタデータ） (2026-05-27T13:20:58Z)
• Curator: Efficient Vector Search with Low-Selectivity Filters [12.774238654446032]
  グラフベースのインデックスは、未フィルタリングANNSでは最先端のパフォーマンスを実現するが、低選択性フィルタリングクエリでは接続性の低下に遭遇する。 近年の研究では、グラフ度を拡大することでこの問題に対処するグラフインデックスが提案されている。 低選択性フィルタANNSに対する既存のグラフベースのアプローチを補完する分割型インデックスであるCuratorを提案する。
  論文  参考訳（メタデータ） (2026-01-03T21:35:01Z)
• Empowering Graph-based Approximate Nearest Neighbor Search with Adaptive Awareness Capabilities [19.352675865525395]
  本稿では,Adaptive Topology とQuery AwarEness を用いた GATE, High-tier Near Graph を提案する。 Gateは、最先端のグラフベースのインデックスと比較して、クエリパフォーマンスの1.2-2.0倍の高速化を実現している。
  論文  参考訳（メタデータ） (2025-06-19T03:07:12Z)
• Temporal-aware Hierarchical Mask Classification for Video Semantic Segmentation [62.275143240798236]
  ビデオセマンティックセグメンテーションデータセットは、ビデオ毎のカテゴリが限られている。 VSSトレーニング中に意味のある勾配更新を受けるために、クエリの10%未満がマッチする可能性がある。 提案手法は,最新のVSSベンチマークVSPWにおいてベルやホイッスルを使わずに,最先端の性能を実現する。
  論文  参考訳（メタデータ） (2023-09-14T20:31:06Z)
• Single-Stage Visual Relationship Learning using Conditional Queries [60.90880759475021]
  TraCQは、マルチタスク学習問題とエンティティペアの分布を回避する、シーングラフ生成の新しい定式化である。 我々は,DETRをベースとしたエンコーダ-デコーダ条件付きクエリを用いて,エンティティラベル空間を大幅に削減する。 実験結果から、TraCQは既存のシングルステージシーングラフ生成法よりも優れており、Visual Genomeデータセットの最先端の2段階メソッドを多く上回っていることがわかった。
  論文  参考訳（メタデータ） (2023-06-09T06:02:01Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。 マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。 本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
  論文  参考訳（メタデータ） (2022-01-25T00:10:03Z)
• Learning Query Expansion over the Nearest Neighbor Graph [94.80212602202518]
  グラフクエリ拡張(GQE)が提示され、教師付き方法で学習され、クエリの拡張近傍で集約を実行する。 この技術は既知のベンチマークよりも最先端の結果が得られる。
  論文  参考訳（メタデータ） (2021-12-05T19:48:42Z)
• Target-Aware Object Discovery and Association for Unsupervised Video Multi-Object Segmentation [79.6596425920849]
  本稿では,教師なしビデオマルチオブジェクトセグメンテーションの課題について述べる。 より正確で効率的な時間区分のための新しいアプローチを紹介します。 DAVIS$_17$とYouTube-VISに対する提案手法を評価した結果,セグメント化精度と推論速度の両方において最先端の手法より優れていることが示された。
  論文  参考訳（メタデータ） (2021-04-10T14:39:44Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。