文献

J-GLOBAL ID：202202247262796999   整理番号：22A0917496

再検討した線形プロービング:Tombstonesは一次クラスタリングの消滅をマークする【JST・京大機械翻訳】

Linear Probing Revisited: Tombstones Mark the Demise of Primary Clustering

著者 (3件)： Bender Michael A. (Stony Brook University,Dept. of Computer Science,Stony Brook,NY,USA,11794-2424) ,  Kuszmaul Bradley C. (Google, Inc.,Cambridge,MA,USA,02142) ,  Kuszmaul William (CSAIL, Massachusetts Institute of Technology,Cambridge,MA,USA,02139)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2022  号： FOCS  ページ： 1171-1182  発行年： 2022年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 線形プロービングハッシュテーブルは,コンピュータ科学における最も古く,最も広く使用されたデータ構造の一つである。しかし,線形プロービングは,ハッシュテーブルが高メモリ利用に達するとすぐに,ハッシュテーブル内の要素が一緒にクラスタを始め,挿入が遅くなる。一次クラスタリングとして知られるこの現象は,1963年にDonald Knuthによって最初に捕獲された。1-1/xの負荷因子で,挿入当りの予想時間は,より望ましいΘ(x)よりむしろΘ(x2)である。著者らは,古典的解析より層位が,示唆するように見えることを示した。欠失がいかに実行されるかにおける小さな設計決定は,挿入の漸近性能に劇的な影響を与えることが分かった。これらの設計決定を正しく行うならば,負荷因子1-Θ(1/x)で連続的にあるハッシュテーブルでさえ,平均挿入時間O(x)を達成できる。重要な洞察は,欠失によって残されたトンボストンが驚くほど強い「アンチクラスター化」効果を引き起こし,挿入と欠失が1対1である場合,欠失のアンチクラスタリング効果が実際に挿入のクラスタ化効果を過出力するということである。また,著者らは,操作の任意のシーケンスで一次クラスタ化を完全に除去する,悪い庭ハッシングと呼ぶ,線形プロービングの新しい変種を提示した。もし,運転を行うと,電流負荷係数は,いくつかのxで1-1/xであり,次に,運転の予想コストは,O(x)である。1つは,Bのデータブロックサイズを有する外部メモリモデルにおいて,悪い場ハッシングは,次の顕著な保証を提供する:任意の負荷因子1-1/xでx=o(B)で,悪い場ハッシングは,1+o(1)が,操作あたり1+o(1)を期待したブロック移動を達成する。過去の外部メモリハッシュテーブルは,ブロックサイズBが少なくともΩ(x2)であるとき,1+o(1)保証を提供できるだけである。結果は,理論者と実務者の両方に対する行動可能な教訓があり,特に,mb石の良く設計された使用は,線形プロービングが如何に振舞うかの漸近的景観を完全に変えることができる(そして,欠失がないかどうか)。Copyright 2022 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 記憶装置 ,  電流 ,  データ構造 ,  計算機科学 ,  層序 ,  *クラスタ化 ,  *クラスタ ,  線形性 ,  外部記憶装置 ,  ハッシング
準シソーラス用語： ボストン ,  ハッシュテーブル , 【Automatic Indexing@JST】

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (3件)： 線形 ,  クラスタリング ,  マーク