米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> ヒューレット・パッカード・カンパニー

発明の名称 データストリームの実質リアルタイム解析方法
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2003−87325(P2003−87325A)
公開日 平成15年3月20日(2003.3.20)
出願番号 特願2002−221143(P2002−221143)
出願日 平成14年7月30日(2002.7.30)
代理人 【識別番号】100081721
【弁理士】
【氏名又は名称】岡田 次生 (外2名)
【テーマコード(参考)】
5K030
【Fターム(参考)】
5K030 GA20 HA08 HB08 JA10 MB09 
発明者 エヌ・リー・ロデス
要約 課題
大容量のリアルタイム確率密度分布及びインターネット使用量と同様の特性を有するネットワーク使用量データのストリーミングを提供すること。

解決手段
動的統計データ分布システム(320)及び方法を有するネットワーク使用量解析システム及び方法(20)である。一実施形態では、本発明は、データストリームの実質リアルタイム解析方法を備える。本方法は、データストリーム(324)を受けとるステップを含む。本方法では、指数関数的に増加するサイズ(312)を有するデータビンを生成すること、及びデータビン(306)にデータを表す統計値を割り当てることを含む、データストリームを表すデータ分布(300)を決定するステップを含む。データ分布は、該データストリームを解析するのに用いられる。
特許請求の範囲
【請求項1】データストリームを受けとるステップと、指数関数的に増加するサイズを有するデータビンを生成すること、及びデータビンにデータを表す統計値を割り当てることを含む、データストリームを表すデータ分布を決定するステップと、該データ分布を用いて該データストリームを解析するステップとを備えるデータストリームの実質リアルタイム解析方法。
発明の詳細な説明
【0001】
【発明の属する技術分野】本発明はネットワーク使用量解析システム及び方法に関し、特に動的統計データ分布システム及び方法に関する。
【0002】
【従来の技術】ネットワークシステムは、毎日の個人及びビジネス目的のコミニュケーションリンクとして利用されている。特にインターネット等のネットワークシステムが成長し、コンピュータハードウェア及びソフトウェア技術が発達したので、ネットワークの使用は、電子メール等の単純な通信交換から、ウェブブラウジング、電子商取引、及びインターネット音声及びインターネットビデオオンデマンド等の他の多くの電子ネットワークサービス、等のより複雑でデータ集約型の通信セッションにわたってきている。
【0003】ネットワーク使用情報は、当事者間の通信セッションで交換される実際の情報を含むものではなく、通信セッションについてのメタデータ(データに関するデータ)情報を含み、多くの使用詳細記録(usage detail records、UDRs)により構成される。各UDRに含まれるメタデータのタイプは、関連するサービス及びネットワークのタイプにより様々であるが、セッション開始時間及び中断時間、セッションのソース又はオリジネータ(originator)、セッションの目的地、会計のための信頼できる相手方、転送されるデータのタイプ、転送されるデータの量、引き渡されるサービスの質、等のパーティ間の所定イベント又は通信セッションについての関連項目情報を多くの場合含む。
【0004】電話ネットワークにおいて、使用情報を構成するUDRは、呼出詳細記録(calldetail records)すなわちCDRと呼ばれる。インターネットのネットワークにおいて、使用詳細記録は標準とされた名前を依然として持たないが、これを適用する場合、それはインターネット詳細記録(internet detail record)すなわちIDRと呼ばれる。特にこの用語IDRは、インターネットの例における文脈での、この適用例を通して用いられているが、用語IDRはあらゆるネットワークのUDRを表すよう定義されている。
【0005】ネットワーク使用情報は、加入者への請求、マーケティング及び顧客への対応、オペレーションマネジメント等の多くの重要なビジネス機能において有用である。ネットワーク使用データ報告システムは、発生時にネットワーク使用情報を収集し、相互に関連させ、まとめるにあたり利用される。そして上述のビジネス機能をサポートするコンピュータビジネスシステムにより消費することができる出力としてUDRを生成するのに利用される。これらのコンピュータビジネスシステムの例は、請求システム、マーケティング及び顧客関係経営システム、顧客動向解析システム、及びデータマイニング(data mining)システムを含む。
【0006】特にインターネットのネットワークに関して、いくつかの重要な技術の変化は、インターネット使用情報又は基礎となるIDRの時間及びコスト面で効率的な解析を、ますます必要としていく上で中心的な役割を持つものである。
【0007】
【発明が解決しようとする課題】技術上の変化の1つとして、適度な加入者コストでの、インターネットアクセスの帯域幅が劇的に増えているということがある。今日大半の消費者は、アナログ電話モデムを介する、インターネットへの限定されたアクセス帯域幅のみしかない。アナログ電話モデムは、実データ転送レートの上限が56,000ビット毎秒である。ネットワークサービスプロバイダの加入者がこうした遅いレートに制限されている場合、サービスプロバイダネットワークの潜在的な混雑及び過負荷に対する効果的な上限となる。
【0008】しかしながら、デジタルケーブルモデム、デジタル加入者回線、マクロウェーブ、及び衛星サービスを介してのブロードバンドインターネットアクセスが幅広いスケールで広がっていくことで、複数桁単位でインターネットアクセスが増える。そのようにして、この高速アクセス帯域幅は、ヘビーユーザによるネットワークの混雑及び帯域幅の酷使の可能性を潜在的に増やす。このようにますます大きな帯域幅が利用可能となることで、ヘビーユーザとライトユーザの間の使用量の違いはかなり大きくなりうるので、固定価格で好きなだけ使える料金プランが維持困難になる。サービスプロバイダがサービスについてかなり大きな課金をする場合、ライトユーザはヘビーユーザを補助することになる。サービスプロバイダがあまり課金をしない場合、ヘビーユーザは利用可能なネットワーク帯域幅を酷使し、それによりサービスプロバイダにコストをかけることになる。
【0009】他の技術的な変化として、大きい帯域幅を必要とするアプリケーションとサービスの急成長がある。例として、インターネット電話、ビデオオンデマンド、複雑な複数プレイヤによるマルチメディアゲームがある。これらのタイプのサービスは、ユーザが、サービスプロバイダにより供給されるべきかなり大きな帯域幅をより必要とするとともに、ネットワークに接続される継続時間を累積する。
【0010】他の技術的な変化として、「ベストエフォート(best effort)」から「ミッションクリティカル(mission critical)」へのインターネットの推移がある。多くのビジネスがインターネットへと動くにつれ、ビジネスは日々ビジネスで成功するためこの媒体へますます依存するようになってきている。このことがインターネットを、カジュアルでベストエフォートな引き渡しサービスから商売のメインストリームへと推移させている。ビジネスの経営者は、サービスプロバイダ保証のサービスの質を備えることを要求しており、こうした高品質サービスへの支払いを歓迎する。
【0011】上述の推進力を要因として、インターネットサービスプロバイダは、最新で、固定料金で、好きなだけ使えるインターネットアクセス請求プランから、メトリックス(metrics)により課金するより複雑な請求プランへと移行する。メトリックスは、例えば転送されたデータの量、利用された帯域幅、用いられたサービス、1日当たりの時間、及び加入者クラス等である。そしてその使用プロフィール、所属組織、又はその他の属性により、同様の加入者グループを定義する。
【0012】このような料金構造の例は、毎月の固定料金部分、毎月の固定料金の一部として含められる使用量の割当て、及びこれに加えその割当て(すなわち上限)を超える使用に対する変動料金部分を含む。所定のサービスプロバイダについて、サービス及び加入者クラスの多くの可能な組み合わせに対してこのように多くの料金構造がある。
【0013】ネットワーク使用量解析システムは、サービスプロバイダのサービスが、どのようにそして誰により用いられるかについての情報を提供する。これは、速く変化していくトレンドの識別、競争力のある価格の確立、必要とされる新たなサービス又は加入者クラスの定義にあたり、サービスプロバイダが備えなければならない必要不可欠なビジネス情報である。新たなインターネットサービスが現れるペースの速さのため、サービスプロバイダは、この必要不可欠な情報へのすばやいアクセスをしなければならない。
【0014】既知の解析パッケージは、ネットワーク使用データを大規模なデータベースへ供給し、それから後にこのデータについての解析を続いて実行する。これらのデータベースシステムは、かなり大きなものを得ることができる。100万の加入者を持つサービスプロバイダは、毎日数十ギガバイト単位の使用データを生成することができる。膨大な量のデータを記憶するための技術が益々改良されていくが、インターネットのトラフィックはさらに速いペースで成長する。このデータの全てを記憶することは高くつき、結局法外なものとなる。非常に高い処理レートで大規模なファイルセットをサポートするには、大規模で高価な支援ハードウェアが必要であり(例えばテラバイトディスクストレージ、バックアップシステム)、そして高価なリレーショナルデータベースマネジメントソフトウェアシステム(RDBMS)が必要とされる。さらに、データベース管理の人員が、これらの大きなデータベース管理システムをサポートし維持するにあたり配置されなければならない。
【0015】解析のタイプが一度決定されると、データマイニング及び解析ソフトウェアシステムは、データベース中に記憶されたかなりの量のネットワーク使用情報を照会し解析するのに利用される。データマイニング及び解析ソフトウェアシステムは、さらなるビジネス解析コンサルティングサービス、さらなるハードウェアサポート、及びデータマイニングソフトウェアライセンスを多くの場合必要とする。さらに、処理を必要とするデータ量が与えられると、全体の待ち時間又はデータの劣化時間がかなり長いものとなりうるので、必要とされる情報を抽出するのに数日から数週間かかる場合がある。
【0016】米国特許出願番号09/548124、出願日2000年4月12日、タイトル「インターネット使用量分析システム及び方法」で開示される、あるタイプの分析は、ネットワーク使用データを分析する統計モデルを利用する。生のネットワーク使用量データは、迅速に調べるにはあまりに量が多いので、生のネットワーク使用量データを表すよう、統計モデルが解釈される。これらの統計モデルは記憶されるが、ネットワーク使用量の問題を解決するために続いて解析することができる。
【0017】データ変量値の確率密度分布を決定する最も一般的な方法は、図1に示される従来の直線ヒストグラムを用いることである。かかるヒストグラムは全データを収集する前に確立される必要があり、いくつかのキーパラメータが定義されなければならない。例えば、データ変量の期待値の下方境界(LB)及び上方境界(UB)を定義しなければならず、ビンの数を、また同様にビンのサイズや幅を定義しなければならない。全てのビンは直線ヒストグラム中で同じサイズを有している。ヒストグラムをつくることは、各ビンに関連するカウンタを増加することからなるが、データ変量の値がビンの割当て範囲内にあるところで起こったイベントの数を表すものである。興味深いことに、この文献で公表されたビンサイズを見積もるための思考アルゴリズムは存在するが、まだ実用段階ではない。
【0018】しかしながら、こうした思考アルゴリズムは、このヒストグラムに記録されるべき期待イベントの数である、Nの値が先に分かることを前提としている。従来これらのパラメータを確立するにあたっては、全データを記憶し、それから全データを予めスキャンしてLB、UB、Nの値を確立してきた。それからヒストグラムは、適切に定義されたLB及びUBを用いて確立され、そしてビンサイズがNから経験的に得られた見積に基づき定義される。それから生データが秒単位の時間でスキャンされヒストグラムを形成する。上述の通り、イベントの量が多くデータレートが高いので、こうした生データを全て記憶することは高コストとなり、待ち時間が長くなる。記憶せずには、こうしたキーパラメータのいずれも正確に決定することができない。このことが、大容量のリアルタイム確率密度分布解析や、ネットワーク使用量データのストリーミングのツールとしての、従来の直線ヒストグラムの有用性を制限している。
【0019】大容量でのリアルタイム確率密度解析を行い、インターネット使用量データなどのネットワーク使用量データを流すシステム及び方法を提供することが望まれる。こうしたタイプのデータ特性には次のような場合がある。データが、超高速データレート(例えば10,000レコード/秒)で連続して収集される必要がある。データ量が多すぎて効率的に記憶できない、又はたとえ記憶してもシヤーサイズのデータセットにより、データ解析及び結果の生成において待ち時間が長くなる。流入データの上方境界と下方境界のいずれもが不明である。流入データイベント数が不明である。さらに、流入データの値は常にプラスであり、大きさ順に並ぶ傾向があり、およそ1/x毎に分布している。
【0020】この最後の特性は、ネットワーク使用量データにおいてかなり一般的なものであり、そして次の事実を反映している。それは、かなりの大容量を使う、すなわちネットワーク上の「パワー」ユーザが一般的に少数に限られていること、そして所定使用量(x)のユーザ数が、量(x)が0に向かって減少するにつれ、およそ1/xに比例して増加することである。上述の理由、及び本実施例の好ましい実施形態の欄での記述でさらに詳細に説明される他の理由により、大容量のリアルタイム確率密度分布及びインターネット使用量と同様の特性を有するネットワーク使用量データのストリーミングを提供するため、さらに進んだ技術が必要とされる。
【0021】
【課題を解決するための手段】本発明は、動的統計データ分布システム及び方法を有するネットワーク使用量解析システム及び方法である。実施形態の1つにおいて、本発明は、データストリームの実質リアルタイム解析方法を提供する。本方法は、データストリーム受け取りステップを含む。データ分布は、データストリームを表すよう決定されるが、指数関数的に増加するサイズを有するデータビンを生成すること、及びデータビンにデータを表す統計値を割り当てることを含む。統計データ分布は、データストリームの解析に用いられる。
【0022】この適用例を通して、ネットワークという語が特に用いられるが、ネットワークという語は、データトランスポートに適したTCP/IPプロトコルを用いたり用いなかったりする公的及び私的なネットワークを含めた、インターネット及び他のネットワークシステムを含むものとして定義される。例として、インターネット、イントラネット、電話ネットワーク、及び他の有線及び無線のネットワークを含む。インターネットという語がこの適用例を通して特に用いられるが、インターネットという語は、ネットワークの1つの例である。
【0023】
【発明の実施の形態】次に述べる好ましい実施形態の詳細な説明において、発明の一部を形成し絵で示すものである後続の図面と、本発明が実施される具体的な実施形態の参照がなされる。本発明の範囲から離れない条件で、他の実施形態を用いることができ、そして構造的又は論理的に変更することができることは理解されたい。それゆえ後述の詳細な説明は、限定する意味でとられるものではなく、本発明の範囲は特許請求の範囲で定義されるものである。
【0024】本発明にかかるネットワーク使用量解析システムは、図2の20に概略的に説明している。ネットワーク使用量解析システム20は、動的適応統計データ分布収集システム及び方法を提供している。一形態においては、生の使用量データは動的で適合型の対数ヒストグラムの形で統計データとして収集され組織化される。使用量データの収集及び解析がなされ、対応する統計データは複数の「グループ」又は「ビン(bin)」として記憶される。ビンは、ここで説明したシステム及び方法で決定された、指数関数的に増加するサイズを有する。本発明は、ビンが、流入する使用量データの値に基づき、必要に応じたベース(オンザフライ)の上に生成されることを規定している。その結果としてのヒストグラム(メモリ中にテーブルの形で記憶することができるもの)は、ヒストグラムに対応した確率密度分布の計算などの後続のネットワーク使用量解析に用いられる。
【0025】従来の直線ヒストグラムはビンを利用するものであるが、各ビンは同じ幅を有する。従来のヒストグラムは多くのものに適用するにあたり有用であるが、インターネット使用量データ等の連続データストリームの確率分布を、リアルタイムに見積るシステム及び方法を提供するのが望ましい。このタイプのデータ特性においては、次のような場合がある。データは、超高速データレート(例えば10,000レコード/秒)で連続して収集する必要がある。データ量が多すぎて効率的に記憶できない、又はたとえ記憶してもデータ解析及び結果の生成において、シヤー(shear)サイズのデータセットにより、待ち時間が長くなる。流入データの上方境界と下方境界のいずれも未知である。流入データイベント数が未知である。さらに、流入データの値はプラスであり、大きさ順に並んでおり、およそ1/xで分布している。
【0026】従来の直線ヒストグラムは、一律に間隔を開けたインターバル又はビン幅を用いるものであり、このため上述の特性に起因して生のインターネット使用量データからの統計分布を生成することが困難となっている。従って従来のヒストグラムを用いる方法において、データの値に関連する下方境界及び上方境界を決定するにあたり2度のスキャンが必要となる。このことは、生の使用量データの記憶にあたり追加費用を必要とせず待ち時間を必要としない。さらに、各ビンの幅(又はインターバルの数)を決定する従来の思考アルゴリズムにあたっては、測定されるべきイベントの数を適切に見積もることを必要とする。本発明にかかる動的適応統計データ分布収集システム及び方法は、インターネット使用量データと同様の特性を有するデータタイプの収集及び解析を持つ、従来のヒストグラム統計モデルを用いることに関連した課題(例えば膨大な量のデータの記憶、データの2度の走査などの課題)の解決を意図したものである。
【0027】ネットワーク使用量解析システム20は、いくつかの主要となる要素を含んでおり、その各々はソフトウェアプログラムである。ネットワーク使用量解析システム20の主要なソフトウェアプログラム要素は、1つ又は複数のコンピュータサーバシステム上で動作する。一実施形態において、主要なソフトウェアプログラム要素の各々は、その自身のコンピュータシステムにおいて動作する。
【0028】本発明で用いられるネットワーク使用量解析システムは、米国特許出願番号09/548124、出願日2000年4月12日、タイトル「インターネット使用量分析システム及び方法」で開示され、発明者及び出願人ともに本出願と同じである。
【0029】典型的な実施形態の1つにおいて、ネットワーク使用量解析システム20は、データ解析システムサーバ22及びヒストリキャッシュ24を含む。データ解析システムサーバ22は、データ収集システム26からの使用量データすなわち「記録イベント」25を受けとる。データ収集システム26は、ネットワーク28からのネットワーク使用量データを受けとる。ある好ましい実施形態において、ネットワーク28は、インターネット30を含む。一般的に、使用量データは、ネットワーク使用量データの記録すなわち記録イベントのリアルタイムストリームである。実施形態の1つにおいて、使用量データは、ネットワーク28上に位置するデータ収集システム26から生成される記録イベントのリアルタイムストリームである。
【0030】データ解析サーバ22は、データ収集システム26からの通信リンク25を介した記録イベントの形の使用量データを受けとる。一形態では、使用量データ収集システム26は、ネットワーク使用データ仲介システムから分かれており、他形態では、使用量データ収集システム26は、ネットワーク使用データ仲介システムを含んでいる。さらに別の形態では、データ収集システム26は、データ解析システムサーバ22の一部である。
【0031】本発明とともに用いるのに適当なデータ収集システムの1つは、米国ヒューレットパッカード社の、商品名インターネット使用マネージャ、において商業的に利用可能である。本発明に関連する使用量解析システムとともに使用されるのに適した、他のデータ収集及び報告システムは、本出願を読めば当業者に明らかになるであろう。
【0032】データ解析システムサーバ22は、使用量データを使用して、予め決められたネットワーク使用量統計解析を実行する。詳細には、まずデータストリームが受けとられる。データストリームを表すデータ分布が決定されるが、指数関数的に増加するサイズを有するデータビンの生成も含む。データの統計表現がデータビンに記録される。データ分布がデータストリームの解析に用いられる。データ解析システムサーバ22は、統計データをデータ格納システム24に記憶すべく処理を行う。この統計データは流入する生データよりもサイズがかなり小さいので、格納の必要性はかなり小さい。一態様においては、統計モデル34をインタラクティブに解析するためのユーザインターフェースに応答する。さらに、統計モデル34のリアルタイムグラフィック表現は、ユーザインターフェース38におけるディスプレイシステムへの出力とすることができる。
【0033】典型的な実施形態の1つにおいて、データ解析システムサーバ22は、1つ又は複数のコンピュータ又はサーバにおいて動作するコンピュータソフトウェアプログラムを含む。統計モデル34は、テーブルの形式の統計データとして記憶することができる。データ格納システム24は、揮発性メモリ(例えばランダムアクセスメモリRAM)や、不揮発性メモリ(例えばハードディスクドライブ又は他の永続的格納装置)とすることができる。ユーザインターフェース38は、キーボードやマウス、又は他のインターフェース装置とすることができる。このインターフェース装置は、業界で知られたビデオディスプレイデバイス等のディスプレイシステムをもつものである。
【0034】図3は、本発明にかかる動的適応統計分布収集システムを有するネットワーク使用量解析システムを用いて生成される、対数ヒストグラム統計モデル34の一般的な実施形態の1つを説明する概略図である。x軸302は、メガバイト単位でのネットワーク使用量等の変量の対数に比例する変量の範囲を図示するものである。y軸304は、各ビン内で記録されたイベントの周波数又は数を図示するものである。使用量が収集され解析されると、306で示されるように、対応する統計データは複数の「グループ」又は「ビン」として記憶される。ビンは後述のように、「随時」生成される。各ビンは312に示すように幅を持っている。これは指数関数的に増加するサイズを有し、bk/r、b(k+1)/r、b(k+2)/r、b(k+3)/r、b(k+n)/rとして示されるビンの境界として示されるものである(ここでbは、対数の底(例えば底10に対してb=10)であり、kはキーであり、rは本適用例において詳述されるように分解要素である)。
【0035】使用量データが収集されるとき、データ自身は各ビン306には収集されないが、各ビン306についての変量302に関連するイベントの頻度又は数が表にされる。その結果のヒストグラム統計モデル(メモリ中のテーブルの形式で記憶することができる)は、ヒストグラム300に対応する確率密度の計算等、後続のネットワーク使用量解析に用いられる。本発明は、用途ベースで統計データを記憶するためのビンを動的に生成し、先に説明したものと同様の特徴を有するデータと共に用いるのに適したシステム及び方法を提供している。
【0036】図4は、320で概略的に図示される本発明にかかる動的適応統計データ分布収集システムの一般的な実施形態の1つを示した概略図である。動的統計データ分布収集システム320は、ここですでに説明したネットワーク使用量解析システムの一部として用いることができ、ここですでに説明したデータ解析システムサーバ22内に配置することができる。動的統計データ分布収集システムは、すでに説明したインターネット使用量データと同様の特徴を有するデータタイプを利用している。
【0037】動的統計データ分布収集システム320は、動的分布コレクタ322を含んでいる。動的分布コレクタ322は、324に示すようにインターネット使用量データの実質的に連続なストリームを受けとる又は検索する。一形態において、使用量データのストリームを検索することには、使用量データソースを照会し、照会に応答して使用量データソースから使用量データのストリームを収集することが含まれる。他の形態では、動的分布コレクタは、データがそこに押し出される「静的」データコレクタとすることができる。一形態では、システムは統計データ分布検索システム326を含む。統計データ分布検索システムは、328で示されるように、使用量データ統計についての動的分布コレクタ322を照会すべく処理を行う。これに応答して、動的分布コレクタ322は、最小限の待ち時間で使用量データ324を表す統計データ分布アレイの出力を提供する。動的分布コレクタ322は、使用量データのストリーム324を受けとり、データストリームを表す統計データ分布を決定するが、指数関数的に増加するサイズを有するデータビンを生成すること(例えばヒストグラム統計モデルの場合)、イベントとしての使用量データを適当なデータビンに記録することを含む。指数関数的に増加するサイズを有するデータビンを生成することには、対数キーのセットを決定すること及びこれらのキーを介して使用量データビンをインデックス化することを含む。
【0038】特に、指数関数的に増加するサイズを有するビン306を生成又は定義するためには、ビンキーkは、次の式を用いて計算される。
【0039】
【数1】

v=入力使用量変量値r=一般的には整数値となる分解要素b=vに適用される対数関数の底であり、一般的には10(int)は、浮動点値タイプであるfloor関数により生成される値を、正又は負となる整数に変換する。
【0040】分解要素rは、所望の大きい順のビンの数として定義される。上述の式の結果、ビンが指数関数的に増加するサイズと共に生成される。分解要素rは、問題となっている未知の値LB、UB、及びN(又はビンサイズ)の異なる変量への変換として見ることができ、全データの収集より前に概算又は収集することはかなり容易である。ユーザはビン処理の所望の相対精度に基づき値rを選択するので、分解要素という名前になる。この点を示すにあたり、上述のビンキーの式は、キー値kを生成するが、これは所定のビンについての固有識別子である。この方法で計算されたすべてのビンについて、ビンの下限に対するビンの上限の比率は、rの同じ値で生成された全てのビンに対する定数となる。
【0041】比率は、(ビンkの上限)/(ビンkの下限)=101/r である。
【0042】例としてr=24の場合、この比率は〜1.10である。このことは、ビンの上限が同じビンの中心より約5%高く、ビンの下限が同じビンの中心より約5%低いことを意味している。r=13については、ビン処理の相対精度は約+/−10%である。
【0043】全てのビンが所定範囲内にあるとき、これは本発明で必ずしも必要というわけではないが、ビンの境界は以下のようにパワーシーケンス(powe sequence)を形成する。
【0044】kは−mからnにわたり、b=10とする。10-m/r、10(-m+1)/r、L、10-1/r、1、101/r、102/r、L、10n/rである。
【0045】この数列は、比率k/rが自然数となる境界が、0.01、0.1、1、10、100等、選択された底の整数乗に丁度対応するという、望ましい属性を有する。
【0046】このビンはメモリに記憶され、さらにネットワーク使用量解析(ここですでに説明した)において使用可能となる。例として、頻度は、対応するビンに集まるイベントに対応するものの値を加えることにより記憶することができる。他の例では、ヒット数を記憶する(1ずつ増加する)代わりに、総和又は全体使用量をビン中にトラックし記憶することができる。
【0047】図5は、本発明にかかる動的適応統計データ分布収集システム320を用いて決定された統計データを、ログし記憶するのに用いられる、アレイ構造の一般的実施形態の1つを図示した概略図である。アレイ構造は340で概略的に説明される。特に、図示された一般的な実施形態について、2に等しい分解要素rが選択される。ビンキーkは、344で示されるように決定される。ビンキーk344は、アレイ340に関連するアレイインデックス346に対応する。アレイ340は、収集されたデータ(例えばイベントの頻度)を表す統計データを記録するのに用いられる。図示された一般的な実施形態において、アレイは決定された範囲に入るイベントの数を記録するのに用いられる。アレイはメモリ中の近傍値のセットとして記憶される。
【0048】図示しているように、アレイインデックス0は、.01000から.03162の値の範囲のイベントを記録している。アレイインデックス1は、.03162から.1000の値の範囲のイベントの記録に対応している。アレイインデックス2は、.1000から.3162の値の範囲のイベントの記録に対応している。アレイインデックス3は、.3162から1.000の値の範囲のイベントの記録に対応している。アレイインデックス4は、1.000から3.162の値の範囲のイベントの記録に対応している。アレイインデックス5は、3.162から10.00の値の範囲のイベントの記録に対応している。アレイインデックス6は、10.00から31.62の値の範囲のイベントの記録に対応している。アレイインデックス7は、31.62から100.0の値の範囲のイベントの記録に対応している。アレイインデックス8は、100.0から316.2の値の範囲のイベントの記録に対応している。アレイインデックス9は、316.2から1000.0の値の範囲のイベントの記録に対応している。
【0049】本発明にかかる対数ビンインデックスを用いる方法において、分解要素rは、大きいものから順にビンインターバルの数を決定する。その結果の量子化誤差は、ビン中に統計的に表された絶対値による大きさに対して一定である。この方法の結果、多くの利点がある。ビンキーkは、上述のビンキーの式を用いて素早く計算することができる。k/rが一定であるとして、この式を用いて計算されたビンの下方境界は、選択された底の整数乗である。
【0050】アレイ構造を用いる結果、計算がかなり高速になり、各統計データイベントについて適切なデータビンが決定される。一形態において、アレイ340の格納空間は、メモリに固まりで予め配置される。他の形態において、アレイ340の格納空間は、メモリ中に動的に配置することができるが、記録イベントの値に基づく。アレイ340内のビン又は配置が、記録イベントの所定値に対して存在しないことが決定された後、メモリ空間は、サイズ変更処理を用いて動的に配置される。
【0051】図6は、本発明にかかるアレイ構造に統計データを記録し又は分布させる方法の実施形態の1つを図示した概略図である。使用量データストリームからの流入データイベントの値vは、350に表されている、352において、ビンキーkは、値v及び所望の分解要素(例えばr=2)を用いて計算される。354においてアレイインデックスは決定され、従ってアレイ中の対応するビンも決定される。356において、ステップ354において計算されたアレイインデックスが既存のアレイインデックスの範囲内にあるかどうかが決定される。計算されたアレイインデックス値がアレイインデックスの範囲内である場合、対応するビンについての統計は更新されて358に示すように流入値vに反映する。ステップ354で計算されたアレイインデックス値がアレイインデックス値の範囲外の場合、アレイのサイズは新たな入力データ値を含めるよう動的に拡張される。一形態において、アレイは360で示されるように、メモリにおいてアレイの他端でrビン(例えばr=2)ずつ増加して拡張される。一度アレイが拡張されて計算されたアレイインデックス値を含める場合、358に示すように、統計値が更新される。
【0052】他の実施形態においては、「ツリー」構造が、メモリ中の決定されたビンに流入するデータイベントを表す統計データを記憶するのに利用される。図7は、本発明にかかるシステムを用いたメモリに統計使用量イベントを記録するツリー構造の一般的な実施形態の1つを図示した概略図を示したものである。ツリー構造は370で概略的に図示されている。ツリー構造を利用してビンの順序を達成する利点は、その方法が、流入データ値の下方境界又は上方境界を予め知っておくこととは完全に独立していることである。メモリはビン毎に随時配置される。随意的に、一度ツリー構造が所定の最大サイズに達すると、隣り合ったビンの結合は、かなり単純なものとなり、従って用いられるサイズ又はその構造のサイズの量に限界を配置する能力を提供する。記録されたイベントが受けとられたときにツリー構造が構築されるので、イベントの入力記録は、アレイ構造を用いるよりも遅いものとすることができる。しかしながら、全ての必要なビンがそこにあるとき、もはやビンの生成は必要とされず、イベントの記録はかなり高速となる。
【0053】ツリー構造370は、ノード372,374,376,378,380,382,384,388,390,392として示される各データビンを表すノードの数を含んでいる。各ノードは、記録された統計に対する入れ物すなわちビンとして用いられる。さらに例として、r=2の分解要素について、記録イベントの値の範囲が決定されそして394として示される。ビンキーkの値は各ノードに関連し、以下に示す各ノードは、ツリー構造370中にある。入力データイベント値が受けとられると、ツリー構造370が生成される。
【0054】ツリー構造370で図示される一般的な実施形態において、データイベント値5は、値の範囲3.162から10の範囲に入り、従ってビンはノード372で表されキー値1を伴う。次の記録イベント値が50の場合、そしてその値に対するビンが存在しない場合、ビンはノード374で生成され、キー値は3となるが、それは値50が31.62から100.0メガバイトの範囲内にあるからである。ツリー構造370は、このようにして続いて構築される。従って、データイベント値がそのノードに関連するビンの範囲内に入らない場合、ノード(ビン)のうちいくつかは、生成する必要がないとすることができる。
【0055】図8は、本発明にかかるツリー構造中の使用量データイベントを記録する方法の一般的な実施形態の1つを図示する概略図である。この方法は、400で概略的に示される。402において、記録イベントの流入値vが受けとられる。404において、ビンキーkが、データイベント値から計算される。ビンキーkに関連するビンは、406に配置される。408において、ビンが存在するとき、410で示されるようにビンで統計値が更新される。計算されたビンキーkに対応するビン又はノードが存在しない場合、412に示すようにビンがツリー構造に追加される。ツリー構造の最大サイズは、追加的に予め定義することができる。414において、ビン又はノードを追加する結果としてのツリー構造のサイズはが所定の最大サイズに比べ大きくない場合、統計値がそのノードで更新される。414において、ツリー構造のサイズが所定の最大値よりも大きい場合、随意に2つの最低ビン又はノードの統計値が、416に示されるように単一ノードへと結合される。例えば、インターネット使用量に関連する統計データを収集するのにおいて、最小の2つのビンを結合するのが望ましい。というのも、それらが最小の(すなわちもっとも重要でない)値を運ぶからである。
【0056】ここで好ましい実施形態の説明の目的のため、具体的な実施形態を図示し記述してきたが、様々な代替の若しくは同等の実施形態を本発明の範囲から逸脱せずに図示し記述した具体的な実施形態でおきかえることができることは当業者に理解されるであろう。化学、機械、電気機械、電子、及びコンピュータにおける知識を有するものであれば、本発明が様々な実施形態で具現化できることはすぐに理解されるであろう。この適用例は、ここで説明した好ましい実施形態の適用又は変形をカバーすることを意図されている。それゆえ、この発明を限定するものが特許請求の範囲及びそれについての同等の構成のみであることは明白に意図される。この発明は例として、次の実施形態を含む。
【0057】(1)データストリーム(27,324)を受けとるステップと、指数関数的に増加するサイズ(312)を有するデータビンを生成すること、及びデータビン(340,370)にデータを表す統計値を割り当てることを含む、データストリームを表すデータ分布(300)を決定するステップと、該データ分布を用いて該データストリームを解析するステップとを備えるデータストリームの実質リアルタイム解析方法(20,22)。
【0058】(2)該指数関数的に増加するサイズを有するデータビンの生成ステップは、該流入データの対数による関数から決定されるキーのセット(344)を用いてビンをインデックス化するステップ、及び指数関数的に増加するインターバルのセットを決定してデータビンのサイズ(342,394)を定義するステップと、を含む(1)に記載の方法。
【0059】(3)該キーのセットを決定するステップは、選択された対数の底の累乗毎に所望のデータビンの数として分解要素を定義するステップと、該分解要素を用いて指数関数的に増加するインターバルのセットを決定するステップと、を含む(2)に記載の方法。
【0060】(4)データストリームを受けとるステップは、データソースを照会するステップ及び該照会に応答して該データソースからデータストリームを収集するステップを含む(1)に記載の方法。
【0061】(5)データストリーム(324)を、高いデータレートで、正の値のみを有し、未知の最小値及び未知の最大値を有する連続データストリームとして定義するステップを備える(1)に記載の方法。
【0062】(6)ビンの順序を定義するステップと、メモリに該ビンの順序を記憶するステップと、該ビンの順序をアレイ構造として定義するステップと、データビンをメモリのアレイ構造(340,370)に記憶するステップとを備え、該データビンにデータ値を配置するステップは、データ値を受けとるステップと、該データ値に関連するビンインデックスを計算するステップ(344)と、インデックス値のアレイを有するアレイインデックスを定義するステップ(346)とを含み、各アレイインデックス値はデータビンに関連し、該アレイインデックス及びビンインデックスを用いてデータ値に関連するデータビンを決定する、(1)に記載の方法。
【0063】(7)該データビンに記憶された値を更新するステップをさらに備える(6)に記載の方法。
【0064】(8)データビンが決定できない場合に、該アレイ構造を拡張して該データビンを入れる(6)に記載の方法。
【0065】(9)該アレイ構造をツリーアレイ構造(370)として定義するステップをさらに備え、該ツリーアレイ構造にデータ値を配置するステップは、データ値に対するデータビンを決定するステップと、データビンが存在しない場合にデータビンを生成するステップ(400)を含む(6)に記載の方法。
【0066】(10)データストリームを受けとり、指数関数的に増加するサイズを有するデータビンの生成、及びデータビン中のデータを表す統計値を配置することを含めて、データストリームを表すデータ分布を決定するよう構成された動的分布コレクタ(322)を備える、(1)から(9)のいずれか1つに記載の方法の実行するデータストリーム解析システム。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013