外部メモリにおけるサイズ優先情報によるバッチ前処理とソーティング【JST・京大機械翻訳】

Bender Michael A.; Goswami Mayank; Mededovic Dzejla; Montes Pablo; Tsichlas Kostas

プレプリント

J-GLOBAL ID：202202205303848156 整理番号：22P0140099

外部メモリにおけるサイズ優先情報によるバッチ前処理とソーティング【JST・京大機械翻訳】

Batched Predecessor and Sorting with Size-Priced Information in External Memory

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (5件)： , , , ,
資料名：
発行年： 2020年04月27日プレプリントサーバーでの情報更新日： 2020年04月27日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

ユニットコスト比較モデルにおいて,ブラックボックスは入力2項目を採り,比較の結果を出力する。仕分けや探索のような問題は,このモデルで研究され,価格情報の概念を含むように一般化され,そこでは,異なるペアのアイテム(データベース記録)が異なる比較コストを持っている。これらの比較費用は任意であり(どの事例も最適(Charikarら,STOC2000)),構造化(例えば,比較コストがデータベースの長さ(GuptaらのFOCS 2001)),または確率(Angelov et al.LATIN2008)に依存する。コストがアイテムのサイズに依存するデータベース設定によって動機づけられて,筆者らは,アイテムAとBの2つの非一様集合が入力として与えられる,ソーティングとバッチ化前処理の問題を考察した。(1)RAM設定では,両集合がn鍵を持つシナリオを考察した。Aの2項目を比較するコストは,Aの項目をBの項目と比較することであり,Bの2項目を比較する。≦b≦cの場合の上限と下限を与えた。事例b=1,a=c=∞は有名な「ナットとボルトの問題である。(2)ディスクと内部メモリ間の移動要素が主要なボトルネックであるDisk-Accessモデル(DAM)において,Bの要素がAの要素より大きいシナリオを考察した。より大きな項目はメモリに持ち込むためにより多くのI/Oを取り入れ,内部メモリでより多くの空間を消費して,比較のためにそれらの全体に必要であった。著者らは最初に,バッチ式前処理問題に関する出力に敏感な下界と上界を与えて,これらを用いて,2つのモデルにおけるソーティングの複雑性に関する限界を引き出した。この限界は,ほとんどの場合,タイトであり,外部メモリにおける古典的下限技術の新しい一般化を必要とし,鍵の非一様性を収容する。【JST・京大機械翻訳】

, , , , , , , , , , , ,
, , , 【Automatic Indexing@JST】

人工知能

, , , , ,

前のページに戻る