[發明專利]信息處理裝置、數據存取方法以及程序

在審

• 申請號: 201280052433.0
• 申請日: 2012-08-24
• 公開（公告）號: CN103890763A
• 公開（公告）日: 2014-06-25
• 發明（設計）人: 小柳光生;R.H.P.魯迪;海野裕也;今道貴司
• 申請（專利權）人: 國際商業機器公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06F12/00;G06F17/28
• 代理公司: 北京市柳沈律師事務所 11105
• 代理人: 金景花

技術領域

本發明涉及數據存儲器(data?store)，更詳細而言，涉及實現高效率地存儲密鑰(key)的數據存儲器的信息處理裝置、對于該數據存儲器的數據存取方法以及程序。

背景技術

在語言處理、用戶管理等的應用開發的領域中，對于將單詞、句子、人名、URL等的龐大的字符串空間效率高地存儲在存儲器中的技術的期望提高。這是因為，通過實現將字符串等作為密鑰的效率高的數據存儲器，能夠將多個字符串以節省存儲器的方式進行管理，進而，能夠高效率地實現上述應用。

作為在上述用途中使用的數據存儲器，已知散列圖(Hash?Map/Hash?Table)。散列圖是使用散列函數而將密鑰映射到值的數據結構，能夠以密鑰來注冊值，以密鑰進行查詢而取得值。由于散列圖根據從密鑰概括的散列值來管理“值”，所以容易追加，并且，無論元素數如何都能夠進行恒定時間中的檢索以及追加，能夠進行高速的數據存取。但是，散列圖為了降低沖突而使用充分稀疏的表，難以提高存儲器空間效率。

作為在上述的用途中使用的其他的數據存儲器，已知在雙陣列(Double-Array)中安裝的字典樹(TRIE)。在雙陣列中安裝的字典樹(以下，有時簡稱為雙陣列)是將存儲密鑰的字典樹以鏈接結構維持的數據結構。已知與上述散列圖相比，雙陣列在數據存取速度的觀點上是遜色的，但能夠將存儲器空間效率設得比較高。

作為在上述的用途中使用的其他的數據存儲器，進而，已知在LOUDS(Level?Order?Unary?Degree?Structure，一級階一元等級結構)中安裝的字典樹。LOUDS是表現樹結構的簡潔數據結構(非專利文獻1)。也報告了如下例子：通過在存儲單詞等的字符串的字典樹的表現中使用LOUDS，與雙陣列中的安裝相比，在存取速度上花費數倍的成本，但實現了4～10倍的存儲器空間效率(非專利文獻2)。另一方面，由于LOUDS是在存儲器空間中緊密地配置的數據結構，所以為了對一旦完成的LOUDS追加新的字符串，為了在要追加新的字符串的節點(node)的部位制作縫隙(表現節點的1比特)而需要移動平均一半的數據。因此，在構筑完畢的數據結構中追加新的字符串會產生大的處理成本。

此外，已知在處理龐大的量的流數據的用途中，優先保持高頻度地出現的密鑰的戰略。例如，非專利文獻3公開了如下技術：通過誤差允許計數法(Lossy?Counting?Method)，對作為流數據而輸入的項目的頻度進行計數，取得出現頻度上位的項目的集合。除此之外，作為誤差允許計數法的改良型，已知在非專利文獻4中公開的概率性誤差允許計數法(Probabilistic?Lossy?Counting?Method)和在非專利文獻5中公開的助記符誤差允許計數法(Mnemonic?Lossy?Counting?Method)。

現有技術文獻

非專利文獻

非專利文獻1:G.Jacobson、“Space-efficient?Static?Trees?and?Graphs”、In?Proceedings?of?the30th?Annual?Symposium?on?Foundations?of?Computer?Science(SFCS'89)、IEEE?Computer?Society、USA、1989、549-554

非專利文獻2:岡野原大輔、“大規模キー集合の効率的な格納法tx?bep(大規模密鑰集合的高效率的存儲法tx?bep)”、[online]、東京大學、[平成23年9月15日檢索]、互聯網＜URL：http://www-tsujii.is.s.u-tokyo.ac.jp/～hillbig/papers/2007-1031-massiveKeys.pdf＞

非專利文獻3:G.S.Manku,et?al.、“Approximate?Frequency?Counts?over?Data?Streams”、Proceedings?of?the28th?International?Conference?on?Very?Large?Data?Base(VLDB)、2002

非專利文獻4:X.Dimitropoulos,et?al.、“Probabilistic?Lossy?Counting:An?efficient?Algorithm?for?Finding?Heavy?Hitters”、ACM?SIGCOMM?Computer?Communication?Review、Volume38、Issue1、January2008