論文の概要: Robust Learning-Augmented Dictionaries
- arxiv url: http://arxiv.org/abs/2402.09687v1
- Date: Thu, 15 Feb 2024 03:45:44 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-16 17:02:24.272324
- Title: Robust Learning-Augmented Dictionaries
- Title(参考訳): ロバスト学習型辞書
- Authors: Ali Zeynali, Shahin Kamali, Mohammad Hajiesmaili
- Abstract要約: 最適な一貫性とロバスト性を備えた辞書を実装するための,最初の学習拡張データ構造を提案する。
我々のデータ構造はRobostSLと呼ばれ、データシーケンス内の要素のアクセス頻度の予測によって拡張されたスキップリストである。
数値実験により、RobostSLは、合成データと実データの両方を用いて、代替データ構造よりも優れていることが示された。
- 参考スコア(独自算出の注目度): 5.906278982316205
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present the first learning-augmented data structure for implementing
dictionaries with optimal consistency and robustness. Our data structure, named
RobustSL, is a skip list augmented by predictions of access frequencies of
elements in a data sequence. With proper predictions, RobustSL has optimal
consistency (achieves static optimality). At the same time, it maintains a
logarithmic running time for each operation, ensuring optimal robustness, even
if predictions are generated adversarially. Therefore, RobustSL has all the
advantages of the recent learning-augmented data structures of Lin, Luo, and
Woodruff (ICML 2022) and Cao et al. (arXiv 2023), while providing robustness
guarantees that are absent in the previous work. Numerical experiments show
that RobustSL outperforms alternative data structures using both synthetic and
real datasets.
- Abstract(参考訳): 最適な一貫性とロバスト性を備えた辞書を実装するための,最初の学習拡張データ構造を提案する。
robustslというデータ構造は、データシーケンス内の要素のアクセス頻度の予測によって拡張されたスキップリストです。
適切な予測により、RobostSL は最適整合性(静的最適性を得る)を持つ。
同時に、各操作の対数実行時間を維持し、たとえ予測が逆向きに生成されるとしても、最適な堅牢性を確保する。
それゆえ、RobostSLはLin, Luo, and Woodruff (ICML 2022) と Cao et al. (arXiv 2023) の最近の学習強化データ構造の利点を全て備えている。
数値実験により、RobostSLは合成データと実データの両方を用いて代替データ構造より優れていた。
関連論文リスト
Err
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。