特許ウォッチ

公開番号2024068340
公報種別公開特許公報(A)
公開日2024-05-20
出願番号2022178710
出願日2022-11-08
発明の名称データ操作プログラム、データ操作システム、およびデータ操作方法
出願人国立大学法人静岡大学
代理人個人,個人,個人
主分類G06F 16/901 20190101AFI20240513BHJP(計算;計数)
要約【課題】ストリーミングデータの中でクエリに対応するデータがどのくらい出現するかを検索するための仕組みを提供すること。
【解決手段】データ操作プログラムは、ストリーミングデータに含まれるトランザクションのアイテム数の最大値をmとし、トランザクションを記録するためのカウンタの衝突に関する値の種類数をpとして、それぞれがp個の配列セットを含むm個の配列セットグループを生成する生成ステップであって、各配列セットが複数の1次元配列を含み、各1次元配列の各要素がカウンタに対応する、該生成ステップと、複数のトランザクションのそれぞれについて、(i)該トランザクションのアイテム数に対応する配列セットグループを選択し、(ii)該配列セットグループ内の各1次元配列において、該トランザクションに対応するカウンタをインクリメントする登録ステップとをコンピュータに実行させる。
【選択図】図1
特許請求の範囲【請求項１】
ストリーミングデータに含まれるトランザクションのアイテム数の最大値をｍとし、前記トランザクションを記録するためのカウンタの衝突に関する値の種類数をｐとして、それぞれがｐ個の配列セットを含むｍ個の配列セットグループを生成する生成ステップであって、各配列セットが複数の１次元配列を含み、各１次元配列の各要素が前記カウンタに対応する、該生成ステップと、
複数の前記トランザクションのそれぞれについて、（ｉ）該トランザクションのアイテム数に対応する前記配列セットグループを選択し、（ｉｉ）該配列セットグループ内の各１次元配列において、該トランザクションに対応する前記カウンタをインクリメントする登録ステップと、
をコンピュータに実行させるデータ操作プログラム。
続きを表示（約 3,500 文字）【請求項２】
クエリに対応する前記トランザクションの出現度を算出する検索ステップを前記コンピュータに更に実行させ、
前記検索ステップが、
前記クエリのアイテム数から前記ｍまでの範囲に対応する少なくとも一つの前記配列セットグループのそれぞれの各配列セットについて、カーネル密度推定による推定値を算出するステップと、
前記少なくとも一つの配列セットグループのそれぞれについて、該配列セットグループの各配列セットの前記推定値と、該配列セットグループに対応するＪａｃｃａｒｄ行列とに基づいて、該配列セットグループにおける部分出現度を算出するステップと、
少なくとも一つの前記部分出現度に基づいて前記出現度を算出するステップと、
を含む、
請求項１に記載のデータ操作プログラム。
【請求項３】
ストリーミングデータに含まれる複数のトランザクションのそれぞれについてデータ構造にカウンタを記録する登録ステップをコンピュータに実行させ、
前記データ構造が、トランザクションのアイテム数の最大値をｍとし、前記トランザクションを記録するためのカウンタの衝突に関する値の種類数をｐとして、それぞれがｐ個の配列セットを含むｍ個の配列セットグループを含み、各配列セットが複数の１次元配列を含み、各１次元配列の各要素が前記カウンタに対応し、
前記登録ステップが、前記複数のトランザクションのそれぞれについて、（ｉ）該トランザクションのアイテム数に対応する前記配列セットグループを選択し、（ｉｉ）該配列セットグループ内の各１次元配列において、該トランザクションに対応する前記カウンタをインクリメントするステップを含む、
データ操作プログラム。
【請求項４】
ストリーミングデータに含まれる複数のトランザクションのそれぞれについてカウンタが記録されたデータ構造を参照して、クエリに対応する前記トランザクションの出現度を算出する検索ステップをコンピュータに実行させ、
前記データ構造が、トランザクションのアイテム数の最大値をｍとし、前記トランザクションを記録するためのカウンタの衝突に関する値の種類数をｐとして、それぞれがｐ個の配列セットを含むｍ個の配列セットグループを含み、各配列セットが複数の１次元配列を含み、各１次元配列の各要素が前記カウンタに対応し、
各配列セットグループの各１次元配列の各要素が、該配列セットグループに対応する前記トランザクションに基づいてインクリメントされたカウンタを記録し、
前記検索ステップが、
前記クエリのアイテム数から前記ｍまでの範囲に対応する少なくとも一つの前記配列セットグループのそれぞれの各配列セットについて、カーネル密度推定による推定値を算出するステップと、
前記少なくとも一つの配列セットグループのそれぞれについて、該配列セットグループの各配列セットの前記推定値と、該配列セットグループに対応するＪａｃｃａｒｄ行列とに基づいて、該配列セットグループにおける部分出現度を算出するステップと、
少なくとも一つの前記部分出現度に基づいて前記出現度を算出するステップと、
を含む、
データ操作プログラム。
【請求項５】
少なくとも一つのプロセッサを備え、
前記少なくとも一つのプロセッサが、
ストリーミングデータに含まれるトランザクションのアイテム数の最大値をｍとし、前記トランザクションを記録するためのカウンタの衝突に関する値の種類数をｐとして、それぞれがｐ個の配列セットを含むｍ個の配列セットグループを生成する生成ステップであって、各配列セットが複数の１次元配列を含み、各１次元配列の各要素が前記カウンタに対応する、該生成ステップと、
複数の前記トランザクションのそれぞれについて、（ｉ）該トランザクションのアイテム数に対応する前記配列セットグループを選択し、（ｉｉ）該配列セットグループ内の各１次元配列において、該トランザクションに対応する前記カウンタをインクリメントする登録ステップと、
を実行するデータ操作システム。
【請求項６】
少なくとも一つのプロセッサを備えるデータ操作システムによって実行されるデータ操作方法であって、
ストリーミングデータに含まれるトランザクションのアイテム数の最大値をｍとし、前記トランザクションを記録するためのカウンタの衝突に関する値の種類数をｐとして、それぞれがｐ個の配列セットを含むｍ個の配列セットグループを生成する生成ステップであって、各配列セットが複数の１次元配列を含み、各１次元配列の各要素が前記カウンタに対応する、該生成ステップと、
複数の前記トランザクションのそれぞれについて、（ｉ）該トランザクションのアイテム数に対応する前記配列セットグループを選択し、（ｉｉ）該配列セットグループ内の各１次元配列において、該トランザクションに対応する前記カウンタをインクリメントする登録ステップと、
を含むデータ操作方法。
【請求項７】
少なくとも一つのプロセッサを備え、
前記少なくとも一つのプロセッサが、ストリーミングデータに含まれる複数のトランザクションのそれぞれについてカウンタが記録されたデータ構造を参照して、クエリに対応する前記トランザクションの出現度を算出する検索ステップを実行し、
前記データ構造が、トランザクションのアイテム数の最大値をｍとし、前記トランザクションを記録するためのカウンタの衝突に関する値の種類数をｐとして、それぞれがｐ個の配列セットを含むｍ個の配列セットグループを含み、各配列セットが複数の１次元配列を含み、各１次元配列の各要素が前記カウンタに対応し、
各配列セットグループの各１次元配列の各要素が、該配列セットグループに対応する前記トランザクションに基づいてインクリメントされたカウンタを記録し、
前記検索ステップが、
前記クエリのアイテム数から前記ｍまでの範囲に対応する少なくとも一つの前記配列セットグループのそれぞれの各配列セットについて、カーネル密度推定による推定値を算出するステップと、
前記少なくとも一つの配列セットグループのそれぞれについて、該配列セットグループの各配列セットの前記推定値と、該配列セットグループに対応するＪａｃｃａｒｄ行列とに基づいて、該配列セットグループにおける部分出現度を算出するステップと、
少なくとも一つの前記部分出現度に基づいて前記出現度を算出するステップと、
を含む、
データ操作システム。
【請求項８】
少なくとも一つのプロセッサを備えるデータ操作システムによって実行されるデータ操作方法であって、
ストリーミングデータに含まれる複数のトランザクションのそれぞれについてカウンタが記録されたデータ構造を参照して、クエリに対応する前記トランザクションの出現度を算出する検索ステップを含み、
前記データ構造が、トランザクションのアイテム数の最大値をｍとし、前記トランザクションを記録するためのカウンタの衝突に関する値の種類数をｐとして、それぞれがｐ個の配列セットを含むｍ個の配列セットグループを含み、各配列セットが複数の１次元配列を含み、各１次元配列の各要素が前記カウンタに対応し、
各配列セットグループの各１次元配列の各要素が、該配列セットグループに対応する前記トランザクションに基づいてインクリメントされたカウンタを記録し、
前記検索ステップが、
前記クエリのアイテム数から前記ｍまでの範囲に対応する少なくとも一つの前記配列セットグループのそれぞれの各配列セットについて、カーネル密度推定による推定値を算出するステップと、
前記少なくとも一つの配列セットグループのそれぞれについて、該配列セットグループの各配列セットの前記推定値と、該配列セットグループに対応するＪａｃｃａｒｄ行列とに基づいて、該配列セットグループにおける部分出現度を算出するステップと、
少なくとも一つの前記部分出現度に基づいて前記出現度を算出するステップと、
を含む、
データ操作方法。

発明の詳細な説明【技術分野】
【０００１】
本開示の一側面は、データ操作プログラム、データ操作システム、およびデータ操作方法に関する。
続きを表示（約 2,300 文字）【背景技術】
【０００２】
非特許文献１には、高次元ストリーミングデータのカーネル密度推定のための効率的なスケッチアルゴリズムであるＲＡＣＥ（ＲｅｐｅａｔｅｄＡｒｒａｙ－ｏｆ－ＣｏｕｎｔｓＥｓｔｉｍａｔｏｒ）が記載されている。非特許文献２には、ストリーミングデータにおける頻出アイテム集合検索（ＦｒｅｑｕｅｎｔＩｔｅｍｓｅｔＭｉｎｉｎｇｉｎＳｔｒｅａｍｉｎｇＤａｔａ（ＦＩＭ－ＳＤ））のためのアルゴリズムが記載されている。
【先行技術文献】
【非特許文献】
【０００３】
Coleman, B. and Shrivastava, A.: Sub-linear RACE sketches forapproximate kernel density estimation on streaming data, Proc. of WWW'20 (2020).https://dl.acm.org/doi/fullHtml/10.1145/3366423.3380244
Yamamoto, Y., Tabei, Y. and Iwanuma, K.: PARASOL: a hybridapproximate approach for scalable frequent itemset mining in streaming data.Journal of Intelligent Information Systems (2020). https://link.springer.com/article/10.1007/s10844-019-00590-9
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ストリーミングデータの中でクエリに対応するデータがどのくらい出現するかを検索するための仕組みが望まれている。
【課題を解決するための手段】
【０００５】
本開示の一側面に係るデータ操作プログラムは、ストリーミングデータに含まれるトランザクションのアイテム数の最大値をｍとし、トランザクションを記録するためのカウンタの衝突に関する値の種類数をｐとして、それぞれがｐ個の配列セットを含むｍ個の配列セットグループを生成する生成ステップであって、各配列セットが複数の１次元配列を含み、各１次元配列の各要素がカウンタに対応する、該生成ステップと、複数のトランザクションのそれぞれについて、（ｉ）該トランザクションのアイテム数に対応する配列セットグループを選択し、（ｉｉ）該配列セットグループ内の各１次元配列において、該トランザクションに対応するカウンタをインクリメントする登録ステップとをコンピュータに実行させる。
【０００６】
このような側面においては、トランザクションのアイテム数の最大値と、トランザクションを記録するためのカウンタの衝突に関する値の種類数との積の分だけ配列セットが用意される。そして、個々のトランザクションについて、トランザクションのアイテム数に対応する配列セットグループの各配列セットにおいて、対応するカウンタがインクリメントされる。このようなデータ構造の生成およびトランザクションの登録によって、ストリーミングデータの中でクエリに対応するデータがどのくらい出現するかを検索することが可能になる。
【発明の効果】
【０００７】
本開示の一側面によれば、ストリーミングデータの中でクエリに対応するデータがどのくらい出現するかを検索することが可能になる。
【図面の簡単な説明】
【０００８】
データ操作システムの機能構成の一例を示す図である。
データ操作システムを構成するコンピュータのハードウェア構成の一例を示す図である。
ＧＲＡＣＥの構造の一例を示す図である。
ＲＡＣＥの構造の一例を示す図である。
データ操作システムによる処理の一例を示すフローチャートである。
ストリーミングデータをＧＲＡＣＥに登録する処理の一例を示すフローチャートである。
カウンタを記録しようとするＲＡＣＥの選択を示す図である。
カウンタのインクリメントを示す図である。
クエリに基づいてＧＲＡＣＥを検索する処理の一例を示すフローチャートである。
検索におけるＧＲＡＣＥの参照を示す図である。
【発明を実施するための形態】
【０００９】
以下、添付図面を参照しながら本開示での実施形態を詳細に説明する。図面の説明において同一または同等の要素には同一の符号を付し、重複する説明を省略する。
【００１０】
［システムの構成］
本開示に係るデータ操作システムは、ストリーミングデータに関する操作を実行するコンピュータシステムである。一例では、データ操作システムは、ストリーミングデータの中でクエリに対応するデータがどのくらい出現（または存在）するかを検索するための環境を提供する。データ操作システムは、記憶容量を節約しつつその検索を実現するためのデータ構造を生成し、ストリーミングデータのデータレコードである複数のトランザクションについてのカウンタをそのデータ構造に登録する。別の例では、データ操作システムはクエリに基づく検索を実行して、そのクエリに対応するトランザクションがストリーミングデータ内にどのくらい出現するかを示す指数である出現度を算出する。出現度は割合、個数などの様々な数値によって表されてよい。
（【００１１】以降は省略されています）

関連特許