特許
J-GLOBAL ID：201103095396073166
異なり数計数方法、異なり数計数装置、および異なり数計数システム
発明者：
,
,
,
出願人/特許権者：
代理人 (3件)：
秋田 収喜
, 近野 恵一
, 井上 雅夫
公報種別：特許公報
出願番号（国際出願番号）：特願2006-235574
公開番号（公開出願番号）：特開2008-059293
特許番号：特許第4339342号
出願日： 2006年08月31日
公開日（公表日）： 2008年03月13日
請求項（抜粋）：
【請求項1】 時々刻々と到来するネットワークの計測データについて、発IPアドレスをキーとし、各発IPアドレス毎の着アドレスIP数を確率的に推定・記録する異なり数計数装置における異なり数計数方法であって、
各発IPアドレス毎に着アドレスIPの観測値に対してランダムな値を返すハッシュ関数により得られたハッシュ値に対応するビットに「1」を記憶する第1のビットマップと、
各発IPアドレス毎に着アドレスIPの観測値に対して2進数のハッシュ列を計算し、当該ハッシュ列の最初の所定数のビットからバケットの識別子を決定するとともに、当該ハッシュ列の最初の所定数のビットを除いた残りのハッシュ列のPFOB値を算出し、前記識別子で指定されたバケット毎にそれまでに観測したPFOB値のうち最大の値を記憶する第2のビットマップと、
各々の発IPアドレスに関して、前記第1のビットマップ内の空きビット数と前記第2のビットマップに記憶された前記最大PFOB値とを用いて異なり数を推定的に算出する異なり数推定部とを有し、
最終的な目標となる推定誤差の許容範囲をε、第1のビットマップのサイズをL1、第2のビットマップのサイズをL2、前記異なり数計数装置に入力された異なり数をn、Linear counting法とLoglog counting法のそれぞれの推定誤差をS1(L1,n),S2(L2,n)、δ、γをパラメタとするとき、
異なり数推定部は、S2≦εを満たす、および、前記異なり数計数装置に入力された異なり数によってすべての前記第2のビットマップが埋まるという2つの条件を満たすL2*,n*を、下記(1)、(2)式を用いて算出するステップ1と、
前記異なり数n*を用い、S1≦εを満たす、および、前記異なり数計数装置に入力された異なり数によって前記第1のビットマップが埋まらないという2つの条件を満たすL1*を、下記(3)式を用いて算出するステップ2と、
前記ステップ1、ステップ2で算出したL1*とL2*とを用いて、前記第2のビットマップに空きバケットが存在する時に、前記第1のビットマップに記憶されたハッシュ値を用いLinear counting法により異なり数推定値E1を算出し、また、前記第1および前記第2のビットマップが全て埋まった時に、前記第2のビットマップに記憶されたハッシュ値を用いてLoglog counting法により異なり数推定値E2を算出し、さらに、前記第2のビットマップが全て埋り、前記第1のビットマップに空きが存在する時に、異なり数推定値EをE=wE1+(1-w)E2、w=S22/(S12+S22)として算出するステップ3とを有することを特徴とする異なり数計数方法。
IPC (2件)：
G06F 17/18 ( 200 6.01)
, H04L 12/56 ( 200 6.01)
G06F 17/18 D
, H04L 12/56 400 Z
