論文の概要: Filtered ANN as a Phase Transition: When Selectivity-Estimation Error Causes Plan Regret

• arxiv url: http://arxiv.org/abs/2606.16341v1
• Date: Mon, 15 Jun 2026 07:44:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-16 16:21:34.157992
• Title: Filtered ANN as a Phase Transition: When Selectivity-Estimation Error Causes Plan Regret
• Title（参考訳）: 位相遷移としてのフィルタANN:選択性推定誤差が計画回帰を引き起こすとき
• Authors: Madhulatha Mandarapu, Sandeep Kunkunuru,
• Abstract要約: 選択性推定誤差は、これらの境界付近の臨界領域でのみ、計画後悔(記憶喪失とオラクル戦略)を引き起こすことを示す。 真の近似指数は境界線を誤定しないが、バイアス付きコストモデルは、推定エラーの堅牢性を修正することができない永続的な誤判定帯域を開放する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A filtered approximate-nearest-neighbor (ANN) query returns the k nearest vectors among those satisfying an attribute predicate P of selectivity s. The best execution strategy -- pre-filter, post-filter, or in-filter -- changes with s, so a system must estimate s and choose. We model this as an argmax over a landscape with phases (regions where each strategy wins) separated by boundaries, and show that selectivity-estimation error produces plan regret -- recall lost versus the oracle strategy -- only in the critical regions around those boundaries. The regret is a wedge of log-width equal to the multiplicative estimation error epsilon and height equal to the local cliff |V'(s*)| epsilon; the flip-margin 1/|V'(s*)| is the condition number of a sibling cardinality-estimation study reappearing as the local boundary theory. The two phase boundaries follow from independent mathematics: order statistics place the post-filter cliff at s ~ k/K, and site percolation places the in-filter cliff at s_c ~ 0.83/M for graph degree M (corpus-size independent). Criticality exists only under a constrained budget B < sqrt(k n). Under pre-registered decision rules we confirm, on synthetic sweeps and real SIFT1M, that regret concentrates ~290x at the boundary and that the regret curves obey a finite-size scaling collapse onto one universal wedge across two decades of corpus size. A real approximate index does not mis-locate the boundary, but a biased cost model opens a persistent miscalibration band that estimation-error robustness cannot fix. The contribution is a characterization, not a new index. Code and the full pre-registration are public.
• Abstract（参考訳）: ANN (Filted Near-nearest-neighbor) クエリは、選択性 s の属性述語 P を満たすものの中で k に近いベクトルを返す。 最高の実行戦略 -- フィルター前、ポストフィルタ、インフィルタ -- はsで変更されるため、システムはsを見積もる必要がある。 私たちはこれを、境界によって区切られたフェーズ(各戦略が勝つ領域)のある風景上のargmaxとしてモデル化し、選択性-推定誤差がプランの後悔を生み出すことを示す。 後悔は対数幅のくさびであり、乗法誤差のエプシロンと高さは局所崖 |V'(s*)| エプシロンと等しい; フリップマージン 1/|V'(s*)| は局所境界理論として再現れる兄弟濃度推定研究の条件数である。 順序統計はポストフィルタの崖を s ~ k/K とし、サイトパーコレーションはグラフ次数 M に対して s_c ~ 0.83/M とする。 臨界性は制限付き予算 B < sqrt(k n) の下にのみ存在する。 事前登録された決定規則の下では、合成スイープと実SIFT1Mにおいて、後悔は境界に約290xの集中を集中し、後悔曲線は20年間のコーパスサイズで1つの普遍的なくさびに有限の大きさのスケーリング崩壊に従うことを確認している。 真の近似指数は境界線を誤定しないが、バイアス付きコストモデルは、推定エラーの堅牢性を修正することができない永続的な誤判定帯域を開放する。 コントリビューションはキャラクタリゼーションであり、新しいインデックスではない。 コードと事前登録はパブリックである。

関連論文リスト

• When Does q-error Predict Plan Regret? Three Regimes of Cardinality-Estimation Error [0.0]
  カーディナリティ推定(CE: Cardinality-estimation)研究は、qerrorによる推定をランク付けする。 我々は、qerrorが良いプロキシである時期と、そうでない時期を計測駆動で説明します。
  論文  参考訳（メタデータ） (2026-06-14T05:06:30Z)
• Bandit Convex Optimization with Gradient Prediction Adaptivity [56.816177049016794]
  本研究では, 楽観的な勾配予測が, 最悪の後悔の保証を予測順応的に改善できるかどうかを考察する。 鍵となるアイデアは、分散が勾配ノルムではなく予測誤差でスケールする、新しい分散還元勾配推定器である。 我々は、$(sqrtmathbbE[S_T])$としてスケールする情報理論の下限を確立し、最も達成可能な予測適応的後悔の基本的な特徴を提供する。
  論文  参考訳（メタデータ） (2026-05-21T08:57:38Z)
• The 99% Success Paradox: When Near-Perfect Retrieval Equals Random Selection [1.2647816797166167]
  本稿では,ビットオーバランサム(BoR)について紹介する。これは,高い成功率がランダムレベルのパフォーマンスを隠蔽することを示す検索選択度尺度である。 予測カバレッジ比$left(fracK cdot barR_qNright)$が3～5を超えると,ベースラインが支配的になり,選択性が低下することを示す。 これらの結果から,BoRは従来の指標とともに報告され,追加検索が無視可能な選択性向上をもたらす場合の深度選択を再考することが示唆された。
  論文  参考訳（メタデータ） (2026-05-14T00:19:57Z)
• The Extrapolation Cliff in On-Policy Distillation of Near-Deterministic Structured Outputs [52.709361620508595]
  ListOPDは、パラメータの5分の1で8B-SFTベースラインで、学生をドメイン内に持ち込む。 Amazon Fashionでは、3つの事前登録テスト — 細粒度崖間隔テスト、小さなクリップのクロス予測 — がロックされた予測ウィンドウ内に落下し、グリッド解像度以下のクローズドフォーム予測に一致する小さなクリップ値が設定されている。
  論文  参考訳（メタデータ） (2026-05-09T06:48:00Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。 PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。 得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
  論文  参考訳（メタデータ） (2025-12-01T02:52:33Z)
• Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
  我々は,個別かつ不可逆な意思決定を対象とするオンライン学習と最適化の問題を定義した。 各期間において、意思決定者は、オープンする施設を選択し、それぞれの成功に関する情報を受け取り、将来の決定を導くために分類モデルを更新する。 目的は,多数の施設を対象とする地平線を特徴とし,カバー対象を反映するチャンス制約の下で施設開口を最小化することである。
  論文  参考訳（メタデータ） (2024-06-20T23:00:25Z)
• Resampled Confidence Regions with Exponential Shrinkage for the Regression Function of Binary Classification [0.0]
  我々は,再サンプリングテストに基づいて,任意のユーザ・センサ信頼度レベルと有限サンプルサイズに対する回帰関数の分布自由信頼領域を構築した。 有限擬次元および逆リプシッツパラメータ化を持つモデルクラスに対する新しい経験的リスクベースアプローチの強い均一性を証明する。 また、k-ネアレスト近傍法についても検討し、排除の確率に基づいて強い点を有界に証明する。
  論文  参考訳（メタデータ） (2023-08-03T15:52:27Z)
• Optimal PAC Bounds Without Uniform Convergence [11.125968799758436]
  我々は、一様収束論の極限を超えるフレームワークを通して、最適な高確率リスク境界を提供する。 我々のフレームワークは、置換不変予測器の残余誤差を高い確率リスク境界に変換する。 具体的には, 1-inclusion graph アルゴリズムの特定のアグリゲーションが最適であることを示す。
  論文  参考訳（メタデータ） (2023-04-18T17:57:31Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• DeepStrip: High Resolution Boundary Refinement [60.00241966809684]
  関心領域をストリップ画像に変換し、ストリップ領域の境界予測を計算することを提案する。 対象境界を検出するために,2つの予測層を持つフレームワークを提案する。 我々は、誤報を減らすために、整合性とC0連続性正規化をネットワークに強制する。
  論文  参考訳（メタデータ） (2020-03-25T22:44:48Z)

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

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