論文の概要: Generalized Range Filtering Approximate Nearest Neighbor Search: Containment and Overlap [Technical Report]

• arxiv url: http://arxiv.org/abs/2605.26474v1
• Date: Tue, 26 May 2026 02:31:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-27 17:51:41.584451
• Title: Generalized Range Filtering Approximate Nearest Neighbor Search: Containment and Overlap [Technical Report]
• Title（参考訳）: 一般化レンジフィルタ近似近傍探索:包含とオーバーラップ [技術報告]
• Authors: Yingfan Liu, Tong Wu, Jiadong Xie, Yang Zhao, Jeffrey Xu Yu, Jiangtao Cui,
• Abstract要約: 距離フィルタを用いた近似近接探索(ANN)が近年注目されている。 この論文は、この問題の一般化形式、すなわち、範囲値属性に基づく正確な範囲範囲(RR)述語を用いたANNサーチ、RRフィルタリングANN (RRANN) に展開する。 我々は、任意のRR述語を効率的に扱うマルチセグメント木グラフという新しいアプローチを導入する。 実世界のデータを用いた実験は、RRANNクエリにおける我々のアプローチの有効性を示し、ベースラインと同じ精度で最大12.5倍の高速化を実現した。
• 参考スコア（独自算出の注目度）: 25.485076435677957
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Approximate nearest neighbor (ANN) search with range filters has recently garnered significant attention. This paper delves into a generalized form of this problem, i.e., ANN search with exact range-range (RR) predicates on a range-valued attribute, named RR filtering ANN (RRANN). Specifically, given $n$ vectors in $\mathbb{R}^d$, each vector $v_i$ is associated with a numeric range $[l_i, r_i]$, symbolizing aspects like a price range or time interval. An RRANN query $(v_q, l_q, r_q)$ aims at finding $k$ vectors closest to $v_q$ within the vectors satisfying an arbitrary RR predicate defined between the query range $[l_q, r_q]$ and the object range $[l_i, r_i]$. The RR predicate remains unspecified, enabling user-defined conditions. It may encompass containment ($[l_i, r_i] \subseteq [l_q, r_q]$ or $[l_q, r_q] \subseteq [l_i, r_i]$), overlap ($l_i \le l_q \le r_i \le r_q$ or $l_q \le l_i \le r_q \le r_i$), or a disjunction of them. RRANN has broad applications in queries related to price ranges or time intervals, and it generalizes existing variants of ANN search with range filters. However, existing dedicated approaches for these problems lack the capacity to support queries with arbitrary RR predicates. Hence, we introduce a new approach, labeled multi-segment tree graph. It efficiently handles arbitrary RR predicates by avoiding traversal through non-predicate-satisfied nodes, and keeps equivalent index size and construction time to state-of-the-art methods for RFANN. Extensive experiments on real-world data demonstrate the efficacy of our approach in RRANN queries, achieving up to 12.5x speedups with the same accuracy as the baselines. Moreover, our approach attains comparable RFANN search performance and notably superior IFANN and TSANN search performance compared to the respective state-of-the-art approaches. Our code is available at https://github.com/FanEDG/MSTG.
• Abstract（参考訳）: 距離フィルタを用いた近似近接探索(ANN)が近年注目されている。 この論文は、この問題の一般化された形式、すなわち、範囲値の属性に基づいて正確な範囲範囲(RR)を述語するANNサーチ(RR filtering ANN (RRANN))に展開する。 具体的には、$\mathbb{R}^d$の$n$ベクトルが与えられた場合、各ベクトル $v_i$ は数値範囲 $[l_i, r_i]$ に関連付けられ、価格範囲や時間間隔のような側面を象徴する。 RRANNクエリ$(v_q, l_q, r_q)$は、クエリ範囲$[l_q, r_q]$とオブジェクト範囲$[l_i, r_i]$の間で定義された任意のRR述語を満たすベクトル内で、$v_q$に最も近い$k$ベクトルを見つけることを目的としている。 RR述語は未定のままであり、ユーザ定義条件が可能である。 包含物([l_i, r_i] \subseteq [l_q, r_q]$または$[l_q, r_q] \subseteq [l_i, r_i]$)、重複物(l_i \le l_q \le r_i \le r_q$または$l_q \le l_i \le r_q \le r_i$)を含むことができる。 RRANNは、価格範囲や時間間隔に関するクエリに広く応用されており、レンジフィルタによる既存のANN検索の変種を一般化している。 しかし、これらの問題に対する既存の専用のアプローチは、任意のRR述語でクエリをサポートする能力に欠けていた。 そこで我々は,マルチセグメント木グラフをラベル付けした新しい手法を提案する。 RFANNの最先端手法に等価なインデックスサイズと構築時間を保持することで、任意のRR述語を効率よく処理する。 実世界のデータに対する大規模な実験は、RRANNクエリにおける我々のアプローチの有効性を示し、ベースラインと同じ精度で最大12.5倍の高速化を実現した。 さらに,本手法は,各最先端手法と比較して,比較可能なRFANN検索性能,特にIFANNとTSANN検索性能に優れる。 私たちのコードはhttps://github.com/FanEDG/MSTG.comで利用可能です。

関連論文リスト

• Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
  MNLモデル(Multinomial Logit、MNL)は、アイテム$[n]=1, ..., n$の有限宇宙から成り、それぞれ正の重みを割り当てる。 クエリはslateと呼ばれる許容可能なサブセットを指定し、モデルはそのslateからその重みに比例した確率で1つのアイテムを選択する。 このクエリモデルは、文学におけるPockett-Luceモデルまたは条件付きサンプリングオラクルとしても知られている。
  論文  参考訳（メタデータ） (2026-01-07T22:07:44Z)
• A Fast Binary Splitting Approach for Non-Adaptive Learning of Erdős--Rényi Graphs [33.51066694357509]
  ノードサブセット上のグループクエリを用いて未知のグラフを学習する問題について検討し、各クエリは、クエリされたノード間に少なくとも1つのエッジが存在するかどうかを報告する。 Erds--Rényi (ER) graphs $GsimmathrmER(n,q)$ in the non-adaptive set, where the expected number of edges is $bark=qbinomn2$。 我々は、最近非適応型グループテストのために開発されたバイナリ分割アプローチをERグラフ設定に拡張し、それを証明した。
  論文  参考訳（メタデータ） (2025-11-21T13:34:29Z)
• Clustering with Non-adaptive Subset Queries [16.662507957069813]
  クエリ $S の部分集合 U$, $|S|=2$ が与えられたとき、オラクルは、ポイントが同じクラスタにあり、そうでなければ、イエスを返す。 ペアワイズクエリを用いた適応アルゴリズムでは、必要なクエリの数は$Theta(nk)$であることが知られている。 非適応スキームは$Omega(n2)$クエリを必要とするが、これは全ての点を問合せすることで得られる自明な$O(n2)$上限と一致する。
  論文  参考訳（メタデータ） (2024-09-17T05:56:07Z)
• List-Decodable Sparse Mean Estimation via Difference-of-Pairs Filtering [42.526664955704746]
  そこで我々は,リストデコダブルなスパース平均推定のための,新しい,概念的にシンプルな手法を開発した。 特に、$k$-sparse方向の「確実に有界な」$t-thモーメントを持つ分布の場合、このアルゴリズムは、サンプル複雑性$m = (klog(n))O(t)/alpha(mnt)$の誤差を1/alpha(O (1/t)$で達成する。 Gaussian inliers の特別な場合、我々のアルゴリズムは $Theta (sqrtlog) の最適誤差を保証する。
  論文  参考訳（メタデータ） (2022-06-10T17:38:18Z)
• Statistical Inference of Constrained Stochastic Optimization via Sketched Sequential Quadratic Programming [53.63469275932989]
  制約付き非線形最適化問題のオンライン統計的推測を考察する。 これらの問題を解決するために、逐次二次計画法(StoSQP)を適用する。
  論文  参考訳（メタデータ） (2022-05-27T00:34:03Z)
• Statistical Query Lower Bounds for List-Decodable Linear Regression [55.06171096484622]
  本稿では,リスト復号化可能な線形回帰問題について考察する。 我々の主な成果は、この問題に対して$dmathrmpoly (1/alpha)$の統計的クエリ(SQ)の低いバウンダリである。
  論文  参考訳（メタデータ） (2021-06-17T17:45:21Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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