(57)【要約】【課題】二つの計数法を用いた異なり数計数を行う場合に、両者の推定精度および両者の精度を保証するために必要となる入力異なり数を考慮し、予め指定した推定精度で入力異なり数を推定する。【解決手段】レコードのある属性をキーｋとして指定し、ｋ毎にレコード上で任意に指定が可能な属性Ｆの異なり数を確率的に推定・記録する異なり数計数方法であって、ｋ毎に、異なり数を記録するためのビットマップを管理する統計管理部と、各々のｋに関して、前述したビットマップの情報を用いて異なり数を推定的に算出する異なり数推定部とを有し、小さい異なり数の計数に適した計数法（例えば、Linear counting法）と、大きな異なり数の計数に適した計数法（例えば、Loglog counting法）とを併用し、２つの計数法による推定誤差、および２つの計数法に適した入力異なり数の範囲を考慮し、２つの計数法の双方の推定値を利用し、予め指定した推定精度に基づき異なり数を推定・記録する。【選択図】図１
2008059293.tif 000002
【特許請求の範囲】
【請求項１】
時々刻々と到来するデータレコードについて、レコードのある属性をキーｋとして指定し、ｋ毎にレコード上で任意に指定が可能な属性Ｆの異なり数を確率的に推定・記録する異なり数計数方法であって、
ｋ毎に、異なり数を記録するためのビットマップを管理する統計管理部と、
各々のｋに関して、前述したビットマップの情報を用いて異なり数を推定的に算出する異なり数推定部とを有し、
異なり数推定部において、小さい異なり数の計数に適した計数法と、大きな異なり数の計数に適した計数法とを併用し、
前記２つの計数法による推定誤差、および前記２つの計数法に適した入力異なり数の範囲を考慮し、前記２つの計数法の双方の推定値を利用することにより、予め指定した推定精度に基づき異なり数を推定・記録し、
さらに、前記２つの計数法の各々において使用するビットマップのサイズを適切に設定することを特徴とする異なり数計数方法。
【請求項２】
時々刻々と到来するデータレコードについて、レコードのある属性をキーｋとして指定し、ｋ毎にレコード上で任意に指定が可能な属性Ｆの異なり数を確率的に推定・記録する異なり数計数装置であって、
ｋ毎に、異なり数を記録するためのビットマップを管理する統計管理部と、
各々のｋに関して、前述したビットマップの情報を用いて異なり数を推定的に算出する異なり数推定部とを有し、
異なり数推定部は、小さい異なり数の計数に適した計数法と、大きな異なり数の計数に適した計数法とを併用し、前記２つの計数法による推定誤差、および前記２つの計数法に適した入力異なり数の範囲を考慮し、前記２つの計数法の双方の推定値を利用することにより、予め指定した推定精度に基づき異なり数を推定・記録し、さらに、前記前記２つの計数法の各々において使用するビットマップのサイズを適切に設定することを特徴とする異なり数計数装置。
【請求項３】
時々刻々と到来するデータレコードについて、レコードのある属性をキーｋとして指定し、ｋ毎にレコード上で任意に指定が可能な属性Ｆの異なり数を確率的に推定・記録する異なり数計数システムであって、
ｋ毎に、異なり数を記録するためのビットマップを管理する統計管理装置と、
各々のｋに関して、前述したビットマップの情報を用いて異なり数を推定的に算出する異なり数推定装置とを有し、
異なり数推定装置は、小さい異なり数の計数に適した計数法と、大きな異なり数の計数に適した計数法とを併用し、前記２つの計数法による推定誤差、および前記２つの計数法に適した入力異なり数の範囲を考慮し、前記２つの計数法の双方の推定値を利用することにより、予め指定した推定精度に基づき異なり数を推定・記録し、さらに、前記２つの計数法の各々において使用するビットマップのサイズを適切に設定することを特徴とする異なり数計数システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、異なり数計数方法、異なり数計数装置、および異なり数計数システムに係り、特に、時々刻々と到来する膨大なデータレコードに関し、指定キー毎の異なり数を確率的に推定・記録するデータ分析技術に関する。
【背景技術】
【０００２】
時々刻々と到来する膨大なデータを分析する際に、コンパクトなデータ管理が必要とされるケースが多々ある。例えば、ＰＯＳ情報システムにおける顧客購買記録、センサネットワークから収集されるデータ、コンピュータネットワークにおけるトラヒック監視などの場合である。
これらの事例に特徴的である大量のデータを解析する場合、観測したすべてのデータをデータベース上で管理することが困難となるため、データの大まかな特徴を失うことなく、かつ、コンパクトデータ管理を行うデータ分析手法が近年着目されている。
その一例として、コンピュータネットワークにおける例を示す。
コンピュータネットワーク上のトラヒックを監視すると、各々のホストが送信したパケット情報を記録することが可能である。例えば、各々のホストが通信を行った相手ホストの数（異なり数）がわかると有用である。
すなわち、通信相手先のホスト数が他と比べて異常に大きいかあるいは急激に高まった場合、そのような通信を行っているホストを異常ホストとして分類することが可能である。
例えば、コンピュータワームに感染しているホストの通信パターンはこのような特徴を有することが知られている。
【０００３】
このようなホスト毎の異なり数を分析するためには、着目するホストが通信を行ったホストそのものの情報（例えば、ＩＰアドレスなど）をすべて記録・管理することによって実現可能である。
ところが、コンピュータネットワーク上を計測した際に得られるデータは非常に膨大であるため、各々のホスト毎に、通信先のホストそのものの情報をすべて記録するアプローチには限界がある。そこで、ホストそのものの情報を記録するのではなく、異なり数を限られたデータ空間上で記録するという戦略が考えられる。
上記の目的を達成する技術として、先行技術ＡＣＣ（Adaptive Cardinality Counting）（下記、非特許文献１参照）では、二つの確率的な異なり数計数方法である「Linear counting法」（下記、非特許先待文献２参照）および「Loglog counting法」（下記、非特許文献３参照）を組み合わせることによって、非常に大きな異なり数から小さな異なり数までを固定長のデータ空間で精度よく記録する手法を提案している。
なお、上記の他に公知の先行技術として、小さい異なり数に適した計数法として「directbitmap法」（下記、非特許文献４参照）が、大きな異なり数に適した計数法として「multi resolution bitmap法」（下記、非特許文献４参照）及び「probabilistic counting法」（下記、非特許文献５参照）が、それぞれ存在する。
【０００４】
なお、本願発明に関連する先行技術文献としては以下のものがある。
【非特許文献１】M.Cai,J.Pan,K.Kwok,and K.Hwang,"Fast and accurate trafficmatrix measurement using adaptive cardinality counting," Proc.ACM SIGCOMM Workshop on Mining Network Data,September2005.
【非特許文献２】Whang,K.,Vander-Zanden,B.,and Taylor,H.,A Linear-TimeProbabilistic Counting Algorithm for Database Applications,"ACM Trans.on Database Systems,Vol.15,No.2,PP.208-229,June1990.
【非特許文献３】Marianne Durand andPhilippe Flajo1et,,"Loglog Counting of Large Cardinalities",In the Engineering and Applications Track "of the 11th Annual European Symposium on Algorithms(ESAO3).Proceedings published by Springer;Lecture Notes in Computer Science,Vol2832,PP.605-617.This document is dated September 2003
【非特許文献４】"Bitmap algorithms for counting active flows on high speed links".Cristian Estan,George Varghese,Mike Fisk Internet Measurement Conference,October 2003
【非特許文献５】"Probabilistic Counting Algorithms for Data Base Applications.Philippe"Flajolet and G.Nigel Martin In Journal of Computer and SystemSciences,Vol31(2),1985,pp.182-209
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ところで、先行技術ＡＣＣでは、二つの異なり数計数法に対して、単一のビットマップを用いているため、特に、両者を切り替えるポイントにおいて推定精度が悪くなるという問題があった。
すなわち、本来は、Loglog counting法を採用するべきところを誤って、Linear counting法を採用してしまう（あるいはその反対のケースが生じる）といった現象があった。
また、Loglog counting法は、非常に大きな異なり数を計数することを前提とした計数法であるが、ＡＣＣでは、比較的小さな異なり数に対してもLoglog countingの推定結果を採用するケースが存在するため、精度が悪くなるという問題がある。
本発明は、前記従来技術の問題点を解決するためになされたものであり、本発明の目的は、二つの計数法を用いた異なり数計数を行う場合に、両者の推定精度および両者の精度を保証するために必要となる入力異なり数を考慮し、予め指定した推定精度で入力異なり数を推定することが可能な異なり数計数方法を提供することにある。
また、本発明の他の目的は、前述の異なり数計数方法を実現するための、異なり数計数装置、および異なり数計数システムを提供することにある。
本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述及び添付図面によって明らかにする。
【課題を解決するための手段】
【０００６】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、下記の通りである。
前述の目的を達成するため、時々刻々と到来するデータレコードについて、レコードのある属性をキーｋとして指定し、ｋ毎にレコード上で任意に指定が可能な属性Ｆの異なり数（属性Ｆの値として出現した値の種類の数）を、異なるサイズのビット列を有する二つの異なり計数法（小さい異なり数の計数に適した計数法（Ｃ１）と、大きな異なり数の計数に適した計数法（Ｃ２））を用い、属性Ｆの観測値に対してランダムな値を返すハッシュ関数を用いることによって異なり数を確率的に推定・記録する。
また、計数法（Ｃ１；例えば、Linear counting法）と、計数法（Ｃ２；例えば、Loglog counting法）とでそれぞれ記録したビットマップの情報は「統計管理部」によって管理され、「異なり数推定部」は推定値が必要となった各々のｋに関して、ビットマップから異なり数を推定的に算出する。
計数法（Ｃ１）と計数法（Ｃ２）の使い分けでは、まず最終的な目標となる推定誤差の許容範囲をεとし、また、計数法（Ｃ１）と計数法（Ｃ２）のそれぞれの推定誤差をＳ１（Ｌ１，ｎ），Ｓ２（Ｌ２，ｎ）とする。
【０００７】
ここに、推定誤差は（推定異なり数／真の異なり数）の標準偏差であり、計数法毎に理論的に計算することができる。また、Ｌ１，Ｌ２は、各々の計数法に必要となるビットマップのサイズ、および、ｎはビットマップに入力された異なり数である。
最初に、計数法（Ｃ２）に対する条件、（Ｉ）推定誤差がＳ２≦εを満たす、および（II）Loglog counting法に対して精度が保証できるほど、Ｌ２に対して十分大きな異なり数が入力される、という二つの条件より、これらを満たすＬ２＝Ｌ２”＊，ｎ＝ｎ＊を算出する。
さらに、この異なり数ｎ＊が、計数法（Ｃ１）に入力されたとき、計数法（Ｃ１）に対する条件、（III）推定誤差がＳ１≦εを満たす、および（IV）計数法（Ｃ１）に対して精度が保証できるほど、Ｌ１に対して十分小さな異なり数が入力される、という条件より、Ｌ１＝Ｌ１＊を算出する。
入力異なり数が（II）を満たす場合、計数法（Ｃ１）の推定値を採用し、（IV）を満たす場合、計数法（Ｃ２）の推定値を採用する。
さらに、上記の（II），（IV）の中間に対応する異なり数が入力された場合、計数法（Ｃ１）と計数法（Ｃ２）による推定値Ｅ１，Ｅ２を用い、異なり数推定値をＥ＝ｗＥ１＋（１−ｗ）Ｅ２とする。ここに、ｗは、ｗ＝Ｓ２２／（Ｓ１２＋Ｓ２２）であり、誤差分散を用いた重み付け平均である。
【発明の効果】
【０００８】
本願において開示される発明のうち代表的なものによって得られる効果を簡単に説明すれば、下記の通りである。
本発明によれば、Linear counting法とLoglog counting法の２つの計数法を用いた異なり数計数を推定する場合に、適切なパラメタ設計を行うことによって、精度の良い異なり数計数を推定することが可能となる。
【発明を実施するための最良の形態】
【０００９】
以下、図面を参照して本発明の実施例を詳細に説明する。
なお、実施例を説明するための全図において、同一機能を有するものは同一符号を付け、その繰り返しの説明は省略する。
図１は、本発明の実施例の異なり数計数方法の基本構成を示すブロック図である。なお、本実施例では、計数法Ｃ１は、Linear counting法、計数法（Ｃ２）は、Loglog counting法の場合について説明する。
同定部１０において、時々刻々と到来するデータから、任意に指定が可能なキーおよび属性値の情報を読みとり、読み取ったキーおよび属性値は、統計管理部２０の各々の異なり数計数法（Ｃ１）ユニット１１と、異なり数計数法（Ｃ２）ユニット１２に入力される。
図２に示すように、異なり数計数法（Ｃ１）ユニット１１では、キー毎にサイズが、Ｌ１のビットマップを管理し、異なり数計数法（Ｃ２）ユニット１２では、各々が小さなビットからなる（例えば、５ビット）Ｌ２個のバケットを管理する。
それぞれのビットマップおよびバケットに、キー毎の異なり数の情報が記録され、異なり数推定部３０では、これらの情報を用いてキー毎の異なり数を推定する。
【００１０】
以下では、適切なＬ１，Ｌ２の設定方法、および計数法（Ｃ１）と計数法（Ｃ２）の使い分け方の実例について述べる。
異なり数計数法（Ｃ１）ユニット１１では、受け取った属性値に対して、１からＬ１の値をランダムに返すハッシュ関数を適用し、得られたハッシュ値に対応するビットマップに対して１を立てる（ステップ１０１〜ステップ１０３）。なお、ビットマップの初期値は、すべて０としておく。
あるキーに対するビットマップにおいて、空のビット（０が立っている）の数をｕとすると、計数法（Ｃ１）のLinear counting法を用いることによって異なり数は、下記（１）式のように推定できる。また、この推定値の誤差Ｓ１は、下記（２）式で与えられる。
【００１１】
【数１】
2008059293.tif 000003
【００１２】
異なり数計数法（Ｃ２）ユニット１２では、受け取った属性値に対して、２進数のハッシュ列を計算し、そのハッシュ列の最初のＭビットからバケットの識別子ｊを決定する（ステップ１０４〜１０６）。例えば、図３に示すように、Ｍ＝４で、［０１１０］の場合、バケットの識別子ｊは６となる。ここに、Ｌ２＝２Ｍとする。また、すべてのバケットの初期値は０である。
さらに、残りのハッシュ列において、左から数えて最初に１が立った位置（ＰＦＯＢ：Position of First One Bit）の位置を計算する。
例えば、図４に示すように、ハッシュ列が、［０１０１１１１０１１...］であった場合、ＰＦＯＢ値は２となる。バケットｊのビットに、ＰＦＯＢ値を記録し、その値をｍ（ｊ）とする。
このプロセスを繰り返し、各々のバケットｊには、ＰＦＯＢ値の最大値を記録する。十分に大きな異なり数が入力された後の状態（すべてのバケットが埋まった状態）で、計数法（Ｃ２）のLoglog counting法を適用すると異なり数は、下記（３）式のように推定できる。Ｌ２が十分に大きいとき、αＬ２＝０．３９７０１である。
また、この推定値の誤差Ｓ２は、下記（４）式で与えられる。
【００１３】
【数２】
2008059293.tif 000004
【００１４】
目標とする推定誤差を、下記（５）式とする。このとき、条件（Ｉ）および（４）式より、下記（６）式が得られる。ここに、（７）式に示す記号は、ｘよりも大きい最小の整数を示す。
【００１５】
【数３】
2008059293.tif 000005
【００１６】
また、条件（II）を、入力した異なり数によってすべてのバケットが埋まるという条件とすると、入力異なり数の条件が、（８）式により得られる。
ここで、δは、バケットが埋まる確率を示すパラメタであり、１未満でなるべくおおきな値（例えば、０．９９９）に設定できる。
さらに、条件（IV）を、入力した異なり数によってビットマップが埋まらないという条件とし、条件（III）、および（２）式をまとめると、Ｌ１の満たす条件は、下記（９）式、（１０）式で与えられる。
ここで、γは、ビットマップが埋まらない条件に対応するパラメタであり、例えば、３などに設定するとビットマップが埋まらない確率が約９９％となる。
【００１７】
【数４】
2008059293.tif 000006
【００１８】
なお、前述の（９）式は数値計算によって求めることができる。表１に、δ＝０．９９９，γ＝３とした場合について、Ｌ１＊，Ｌ２＊を計算した数値計算例を示す。
【００１９】
【表１】
2008059293.tif 000007
【００２０】
前述した目標とする推定誤差εに対して、（６）式、（９）式によって計算される、Ｌ１＊、Ｌ２＊を用い、異なり数推定部３０では、下記（１１）に示す方法により、異なり数を推定する（ステップ１０７）。
【００２１】
【数５】
2008059293.tif 000008
なお、ｗはｗは、ｗ＝Ｓ２２／（Ｓ１２＋Ｓ２２）であり、誤差分散を用いた重み付け平均である。
【００２２】
図５に、本実施例の異なり数計数方法を適用した推定結果として、入力をネットワークの計測データとし、キーとして、発ＩＰアドレス、属性として着ＩＰアドレスとし、推定誤差がε＝０．１１を満たすように、Ｌ１＝１２８，Ｌ２＝３８４としたときのキー毎の異なり数の推定結果を示す。この図６からわかるように、大小の広い範囲において精度よく異なり数を推定できていることがわかる。
なお、図１に示す基本構成において、同定部１０、統計管理部２０、異なり数推定部３０を同一の装置（本発明の異なり数計数装置）に実装してもよく、あるいは、同定部１０および統計管理部２０を一つの装置（本発明の統計管理装置）に実装し、さらに、異なり数推定部３０を異なる装置（本発明の異なり数推定装置）に実装し、システム構成としてもよい。
以上、本発明者によってなされた発明を、前記実施例に基づき具体的に説明したが、本発明は、前記実施例に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【図面の簡単な説明】
【００２３】
【図１】本発明の実施例の異なり数計数方法の基本構成を示すブロック図である。
【図２】本発明の実施例の異なり数計数方法における、ビットマップ構成を示す図である。
【図３】本発明の実施例の異なり数計数方法における、バケット識別子の計算方法の具体例を示す図である。
【図４】本発明の実施例の異なり数計数方法における、ＰＦＯＢ値の計算方法の具体例を示す図である。
【図５】本発明の実施例の異なり数計数方法を適用した異なり数の推定結果の一例を示す図である。
【符号の説明】
【００２４】
１０  同定部
１１  異なり数計数法（Ｃ１）ユニット
１２  異なり数計数法（Ｃ２）ユニット
２０  統計管理部
３０  異なり数推定部
【図１】
2008059293.tif 000009
【図２】
2008059293.tif 000010
【図３】
2008059293.tif 000011
【図４】
2008059293.tif 000012
【図５】
2008059293.tif 000013