論文の概要: A Query-Driven Approach to Space-Efficient Range Searching

• arxiv url: http://arxiv.org/abs/2502.13653v1
• Date: Wed, 19 Feb 2025 12:01:00 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-20 13:58:38.164158
• Title: A Query-Driven Approach to Space-Efficient Range Searching
• Title（参考訳）: 空間効率のよい範囲探索へのクエリ駆動型アプローチ
• Authors: Dimitris Fotakis, Andreas Kalavas, Ioannis Psarros,
• Abstract要約: クエリのほぼ直線的なサンプルは、クエリ中に訪れたノード数がほぼ最適であるパーティションツリーを構築することができることを示す。 我々は、ノード処理を分類問題として扱い、浅いニューラルネットワークのような高速な分類器を活用して、実験的に効率的なクエリ時間を得ることにより、このアプローチを強化する。 我々のアルゴリズムは,クエリのサンプルに基づいて,セパレータに関連付けられたノードを持つバランスのとれたツリーを構築し,クエリの待ち行列を最小化する。
• 参考スコア（独自算出の注目度）: 12.760453906939446
• License:
• Abstract: We initiate a study of a query-driven approach to designing partition trees for range-searching problems. Our model assumes that a data structure is to be built for an unknown query distribution that we can access through a sampling oracle, and must be selected such that it optimizes a meaningful performance parameter on expectation. Our first contribution is to show that a near-linear sample of queries allows the construction of a partition tree with a near-optimal expected number of nodes visited during querying. We enhance this approach by treating node processing as a classification problem, leveraging fast classifiers like shallow neural networks to obtain experimentally efficient query times. Our second contribution is to develop partition trees using sparse geometric separators. Our preprocessing algorithm, based on a sample of queries, builds a balanced tree with nodes associated with separators that minimize query stabs on expectation; this yields both fast processing of each node and a small number of visited nodes, significantly reducing query time.
• Abstract（参考訳）: 範囲探索問題に対して分割木を設計するための問合せ駆動手法の研究を開始する。 データ構造は未知のクエリ分布のために構築され、サンプリングオラクルを通してアクセス可能であり、期待値に対する有意義なパフォーマンスパラメータを最適化するために選択されなければならないと仮定する。 最初のコントリビューションは、クエリのほぼ直線的なサンプルによって、クエリ中に訪れたノード数がほぼ最適であるパーティションツリーを構築することができることを示すことです。 我々は、ノード処理を分類問題として扱い、浅いニューラルネットワークのような高速な分類器を活用して、実験的に効率的なクエリ時間を得ることにより、このアプローチを強化する。 第2の貢献は、スパース幾何学分離器を用いた分割木の開発である。 我々の前処理アルゴリズムは,クエリのサンプルに基づいて,クエリ待ち時間を最小限に抑えるために,セパレータに関連付けられたノードとバランスのとれたツリーを構築し,各ノードの高速な処理と少数の訪問ノードの両方を出力し,クエリ時間を大幅に短縮する。

関連論文リスト

• ReTreever: Tree-based Coarse-to-Fine Representations for Retrieval [64.44265315244579]
  そこで本研究では,様々なレベルで参照文書を整理し,表現するためのツリーベース手法を提案する。 我々の手法はReTreeverと呼ばれ、クエリと参照ドキュメントが同様のツリーブランチに割り当てられるように、バイナリツリーの内部ノード毎のルーティング関数を共同で学習する。 我々の評価では、ReTreeverは一般的に完全な表現精度を保っている。
  論文  参考訳（メタデータ） (2025-02-11T21:35:13Z)
• Operational Advice for Dense and Sparse Retrievers: HNSW, Flat, or Inverted Indexes? [62.57689536630933]
  本稿では,オープンソースのLucene検索ライブラリを用いたBEIRデータセットの実験結果について述べる。 本研究は,高密度かつ疎密なレトリバーの設計空間を理解するための,今日の検索実践者へのガイダンスを提供する。
  論文  参考訳（メタデータ） (2024-09-10T12:46:23Z)
• LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
  本研究では,動的ノード選択とノードレベルの探索予算を備えた新しいガイド付き木探索アルゴリズムを提案する。 GSM8KおよびTabMWPデータセットを用いて行った実験により,本手法はベースライン法に比べて計算コストが大幅に低いことを示した。
  論文  参考訳（メタデータ） (2024-06-29T05:14:04Z)
• Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search [9.01394829787271]
  この研究は、クラスタリングに基づく最大内部積探索におけるルーティングを研究することによってギャップを埋める。 各シャード内の内積分布のモーメントを組み込んで最大内積を推定する枠組みを提案する。
  論文  参考訳（メタデータ） (2024-05-20T17:47:18Z)
• Group Testing for Accurate and Efficient Range-Based Near Neighbor Search for Plagiarism Detection [2.3814052021083354]
  本研究は, 近接探索問題に対する適応型群検定フレームワークを提案する。 本研究では,データベース内の各項目を問合せ点の隣人あるいは非隣人として,余剰距離閾値に基づいて効率よくマークする。 本研究では,ソフトマックスに基づく特徴量を用いて,完全探索よりも10倍以上の高速化を実現し,精度を損なわないことを示す。
  論文  参考訳（メタデータ） (2023-11-05T06:12:03Z)
• Towards Personalized Preprocessing Pipeline Search [52.59156206880384]
  ClusterP3Sは、Clusteringを介してパイプライン検索をパーソナライズする新しいフレームワークである。 本稿では,クラスタを協調的に学習し,最適なパイプラインを探索するための階層的探索手法を提案する。 ベンチマーク分類データセットの実験では、機能的に前処理可能なパイプライン探索の有効性が示されている。
  論文  参考訳（メタデータ） (2023-02-28T05:45:05Z)
• Tree Learning: Optimal Algorithms and Sample Complexity [10.638365461509]
  任意の分布から抽出したラベル付きサンプルから,データの階層木表現を学習する問題について検討する。 本稿では,この問題に対する最適なサンプル境界を,学習やオンライン学習など,いくつかの学習環境において提示する。
  論文  参考訳（メタデータ） (2023-02-09T08:35:17Z)
• Hypotheses Tree Building for One-Shot Temporal Sentence Localization [53.82714065005299]
  ワンショット時間文のローカライゼーション(ワンショットTSL)は、1つの注釈付きフレームだけでビデオ全体のクエリ情報を取得することを学習する。 我々はMHST(Multiple hypotheses Segment Tree)と呼ばれるワンショットTSLのための有効で斬新な木構造ベースラインを提案する。 MHSTは、不十分なアノテーションの下で、クエリ対応の識別フレーム情報をキャプチャする。
  論文  参考訳（メタデータ） (2023-01-05T01:50:43Z)
• Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
  興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。 基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。 我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
  論文  参考訳（メタデータ） (2022-09-27T17:51:31Z)
• Improving Document Representations by Generating Pseudo Query Embeddings for Dense Retrieval [11.465218502487959]
  反復的なクラスタリングプロセスにより,各文書のクエリを模倣する手法を設計する。 また、2段階のスコア計算手順でマッチング関数を最適化する。 いくつかの人気ランキングとQAデータセットに関する実験結果から、私たちのモデルが最先端の結果を達成できることが示された。
  論文  参考訳（メタデータ） (2021-05-08T05:28:24Z)
• A Practical Index Structure Supporting Fr\'echet Proximity Queries Among Trajectories [1.9335262420787858]
  我々は、計算コストの高いメトリクスの下で、レンジと近隣クエリに$k$のスケーラブルなアプローチを提案する。 計量指標のクラスタリングに基づいて,軌跡数に線形な木構造を求める。 本研究では,多種多様な合成および実世界のデータセットに関する広範な実験により,本手法の有効性と有効性について分析する。
  論文  参考訳（メタデータ） (2020-05-28T04:12:43Z)

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

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