(57)【要約】  クエリーの結果の一連の近似を作成するための方法、システム及びコンピュータプログラム。クエリーがデータの徐々に大きくなっていく標本に適用されて、徐々に精度が高くなっていく近似が算出される。選択によってクエリーの真の結果が算出されるまで処理が続けられる。
2008516313.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータ要素Ｄへのクエリーの結果Ｒの一連の近似を作成するための方法であって、
a）Ｄの標本Ｓiへのクエリーの結果Ａiを算出するステップと、
b）少なくとも前記の結果Ａiをもとに、結果Ｒの近似Ｂiを算出するステップと、
c）ステップ（a）及び（b）を、異なるＳiについて複数のｉ回実行することによって一連の近似を作成するステップと
を含む方法。
【請求項２】
ステップ（a）の一連の適用において、標本Ｓiが徐々に大きくなっていき（つまり|Ｓi+1| > |Ｓi|）、ステップ（b）の一連の適用において、近似Ｂiの期待精度が徐々に高くなっていく
ことを特徴とする請求項１に記載の方法。
【請求項３】
ステップ（a）の少なくとも一回の適用において、標本Ｓiが、前回の標本Ｓjからのデータ要素と複数の新しいデータ要素Ｎiとを含んでおり、
ＡiがＡjとＮiとの関数として算出される
ことを特徴とする請求項１に記載の方法。
【請求項４】
Ｎiが、Ｄのランダム又は擬似ランダム順列の間順走査によって作成される
ことを特徴とする請求項３に記載の方法。
【請求項５】
Ｎiが、Ｄのランダム又は擬似ランダム走査によって作成される
ことを特徴とする請求項３に記載の方法。
【請求項６】
ステップ（a）の少なくとも一回の適用において、標本Ｓiが前記複数のデータ要素Ｄを含んでいる
ことを特徴とする請求項１に記載の方法。
【請求項７】
クエリーを作成するステップをさらに含む請求項１に記載の方法。
【請求項８】
表示装置にステップ（c）で作成される前記一連の近似を表示するステップをさらに含む請求項１に記載の方法。
【請求項９】
前記複数のデータ要素Ｄが単層ファイルに格納されており、
前記方法が、前記単層ファイルにアクセスするステップをさらに含んでいる請求項１に記載の方法。
【請求項１０】
前記クエリーが完了した割合を示すインジケータを作成するステップをさらに含む請求項１に記載の方法。
【請求項１１】
近似Ｂiごとに前記近似Ｂiの正確度合いを示す信頼インジケータＣiを作成するステップをさらに含む請求項１に記載の方法。
【請求項１２】
データ記憶装置に格納された複数のデータ要素Ｄへのクエリーの結果Ｒの一連の近似を作成するためのシステムであって、
前記データ記憶装置にアクセスするように構成されており、（a）複数のデータ要素Ｄの標本Ｓiへのクエリーの結果Ａiを算出し、（b）少なくとも結果Ａiをもとに結果Ｒの近似Ｂiを算出し、（c）（a）及び（b）を、異なる標本Ｓiについて複数のｉ回実行することによって一連の近似を作成するように構成されている処理部を備えるシステム。
【請求項１３】
前記処理部がさらに、（a）の一連の適用において、徐々に大きくなっていく標本Ｓi（つまり|Ｓi+1| > |Ｓi|）をＤから選択するように構成されており、
ステップ（b）の一連の適用において、近似Ｂiの期待精度が徐々に高くなっていく
ことを特徴とする請求項１２に記載のシステム。
【請求項１４】
前記処理部が実行する（a）の少なくても１回の適用において、標本Ｓiが、前回の標本Ｓjからのデータ要素と複数の新しいデータ要素Ｎiとを含んでおり、
ＡiがＡjとＮiとの関数として算出される
ことを特徴とする請求項１２に記載のシステム。
【請求項１５】
Ｎiが、Ｄのランダム又は擬似ランダム順列の間順走査によって作成される
ことを特徴とする請求項１４に記載のシステム。
【請求項１６】
Ｎiが、Ｄのランダム又は擬似ランダム走査によって作成される
ことを特徴とする請求項１４に記載のシステム。
【請求項１７】
ステップ（a）の少なくとも１回の適用において、標本Ｓiが前記複数のデータ要素Ｄを含んでいる
ことを特徴とする請求項１２に記載のシステム。
【請求項１８】
前記処理部がさらに、クエリー要請を受け付けて前記クエリー要請をもとに前記クエリーを作成するように構成されている
ことを特徴とする請求項１２に記載のシステム。
【請求項１９】
前記処理部がさらに、（c）にて作成された前記一連の近似を表示装置に表示するように構成されている
ことを特徴とする請求項１２に記載のシステム。
【請求項２０】
前記複数のデータ要素Ｄが前記データ記憶装置の単層ファイルに格納されている
ことを特徴とする請求項１２に記載のシステム。
【請求項２１】
前記処理部がさらに、前記クエリーが完了した割合を示すインジケータを作成するように構成されている
ことを特徴とする請求項１２に記載のシステム。
【請求項２２】
前記処理部がさらに、近似Ｂiごとに前記近似Ｂiの正確度合いを示す信頼インジケータＣiを作成するように構成されている
ことを特徴とする請求項１２に記載のシステム。
【請求項２３】
前記信頼インジケータＣiが、少なくとも結果Ａiをもとにしている
ことを特徴とする請求項２２に記載のシステム。
【請求項２４】
データ記憶装置に格納された複数のデータ要素Ｄへのクエリーの結果Ｒの一連の近似を作成するコンピュータプログラムであって、コンピュータで読み込み可能な媒体に格納されており、
前記データ記憶装置にアクセスし、複数のデータ要素Ｄの標本Ｓiへのクエリーの結果Ａiを算出するための第１のコード部分と、
少なくとも結果Ａiをもとに結果Ｒの近似Ｂiを算出するための第２のコード部分と、
前記第１及び第２のコード部分を、異なる標本Ｓiについて複数のｉ回実行することによって一連の近似を作成するための第３のコード部分と
を備えるコンピュータプログラム。
【請求項２５】
前記第１のコード部分が、徐々に大きくなっていく標本Ｓi（つまり|Ｓi+1| > |Ｓi|）を使用するように構成されており、
前記第２のコード部分の一連の実行において、近似Ｂiの期待精度が徐々に高くなっていく
ことを特徴とする請求項２４に記載のコンピュータプログラム。
【請求項２６】
前記第１のコード部分の少なくとも１回の実行において、標本Ｓiが、前回の標本Ｓjからのデータ要素と複数の新しいデータ要素Ｎiとを含んでおり、
ＡiがＡjとＮiとの関数として算出される
ことを特徴とする請求項２４に記載のコンピュータプログラム。
【請求項２７】
Ｎiが、Ｄのランダム又は擬似ランダム順列の間順走査によって作成される
ことを特徴とする請求項２６に記載のコンピュータプログラム。
【請求項２８】
Ｎiが、Ｄのランダム又は擬似ランダム走査によって作成される
ことを特徴とする請求項２６に記載のコンピュータプログラム。
【請求項２９】
前記第１のコード部分の少なくとも一回の実行において、標本Ｓiが前記複数のデータ要素Ｄを含んでいる
ことを特徴とする請求項２４に記載のコンピュータプログラム。
【請求項３０】
クエリーを作成するための第４のコード部分をさらに含む請求項２４に記載のコンピュータプログラム。
【請求項３１】
前記一連の近似を表示するための第４のコード部分をさらに含む請求項２４に記載のコンピュータプログラム。
【請求項３２】
前記複数のデータ要素Ｄが単層ファイルに格納されている
ことを特徴とする請求項２４に記載のコンピュータプログラム。
【請求項３３】
前記クエリーが完了した割合を示すインジケータを作成するための第４のコード部分をさらに含む請求項２４に記載のコンピュータプログラム。
【請求項３４】
近似Ｂiごとに前記近似Ｂiの正確度合いを示す信頼インジケータＣiを作成するための第４のコード部分をさらに含む請求項２４に記載のコンピュータプログラム。
【請求項３５】
複数のデータ要素Ｄへのクエリーの結果Ｒの一連の近似を作成するための方法であって、
a）Ｄの標本Ｓiへのクエリーの結果Ａiを算出するための各ステップと、
b）少なくとも結果Ａiをもとに結果Ｒの近似Ｂiを算出するための各ステップと、
c）ステップ（a）及び（b）を、異なるＳiについて複数のｉ回実行することによって一連の近似を作成するための各ステップと
を含む方法。
【請求項３６】
（a）の一連の適用において、標本Ｓiが徐々に大きくなっていき（つまり|Ｓi+1| > |Ｓi|）、（b）の一連の適用において、近似Ｂiの期待精度が徐々に高くなっていく
ことを特徴とする請求項３５に記載の方法。
【請求項３７】
（a）の少なくとも一回の適用において、標本Ｓiが、前回の標本Ｓjからのデータ要素と複数の新しいデータ要素Ｎiとを含んでおり、
ＡiがＡjとＮiとの関数として算出される
ことを特徴とする請求項３５に記載の方法。
【請求項３８】
Ｎiが、Ｄのランダム又は擬似ランダム順列の間順走査によって作成される
ことを特徴とする請求項３７に記載の方法。
【請求項３９】
Ｎiが、Ｄのランダム又は擬似ランダム走査によって作成される
ことを特徴とする請求項３７に記載の方法。
【請求項４０】
（a）の少なくとも一回の適用において、標本Ｓiが前記複数のデータ要素Ｄを含んでいる
ことを特徴とする請求項３５に記載の方法。
【請求項４１】
クエリーを作成するための各ステップをさらに含む請求項３５に記載の方法。
【請求項４２】
（c）で作成される前記一連の近似を表示装置に表示するための各ステップをさらに含む請求項３５に記載の方法。
【請求項４３】
前記複数のデータ要素Ｄが単層ファイルに格納されており、
前記方法が、前記単層ファイルにアクセスするための各ステップをさらに含んでいる請求項３５に記載の方法。
【請求項４４】
前記クエリーが完了した割合を示すインジケータを作成するための各ステップをさらに含む請求項３５に記載の方法。
【請求項４５】
近似Ｂiごとに前記近似Ｂiの正確度合いを示す信頼インジケータＣiを作成するための各ステップをさらに含む請求項３５に記載の方法。
【請求項４６】
データ記憶装置に格納された複数のデータ要素Ｄへのクエリーの結果Ｒの一連の近似を作成するためのシステムであって、
前記データ記憶装置にアクセスし、（a）複数のデータ要素Ｄの標本Ｓiへのクエリーの結果Ａiを算出し、（b）少なくとも結果Ａiをもとに結果Ｒの近似Ｂiを算出し、（c）（a）及び（b）を、異なる標本Ｓiについて複数のｉ回実行することによって一連の近似を作成するための処理手段を備えるシステム。
【請求項４７】
前記処理手段が、（a）の一連の適用において、徐々に大きくなっていく標本Ｓi（つまり|Ｓi+1| > |Ｓi|）をＤから選択し、
ステップ（b）の一連の適用において、近似Ｂiの期待精度が徐々に高くなっていく
ことを特徴とする請求項４６に記載のシステム。
【請求項４８】
（a）の少なくても１回の適用において、処理手段が、前回の標本Ｓjからのデータ要素と複数の新しいデータ要素Ｎiとを含むように標本Ｓiを選択し、ＡjとＮiとの関数としてＡiを算出する
ことを特徴とする請求項４６に記載のシステム。
【請求項４９】
前記処理手段が、Ｄのランダム又は擬似ランダム順列の間順走査によってＮiを作成する
ことを特徴とする請求項４８に記載のシステム。
【請求項５０】
前記処理手段が、Ｄのランダム又は擬似ランダム走査によってＮiを作成する
ことを特徴とする請求項４８に記載のシステム。
【請求項５１】
（a）の少なくとも１回の適用において、標本Ｓiが前記複数のデータ要素Ｄを含んでいる
ことを特徴とする請求項４６に記載のシステム。
【請求項５２】
前記処理手段が、クエリー要請を受け付けて、前記クエリー要請をもとに前記クエリーを作成する
ことを特徴とする請求項４６に記載のシステム。
【請求項５３】
前記処理手段が、（c）にて作成された前記一連の近似を表示装置に表示する
ことを特徴とする請求項４６に記載のシステム。
【請求項５４】
前記複数のデータ要素Ｄが前記データ記憶装置の単層ファイルに格納されている
ことを特徴とする請求項４６に記載のシステム。
【請求項５５】
前記処理手段が、前記クエリーが完了した割合を示すインジケータを作成する
ことを特徴とする請求項４６に記載のシステム。
【請求項５６】
前記処理手段が、近似Ｂiごとに前記近似Ｂiの正確度合いを示す信頼インジケータＣiを作成する
ことを特徴とする請求項４６に記載のシステム。
【請求項５７】
前記信頼インジケータＣiが、少なくともＡiをもとにしている
ことを特徴とする請求項５６に記載のシステム。
【請求項５８】
データ記憶装置に格納された複数のデータ要素Ｄへのクエリーの結果Ｒの一連の近似を作成するためのシステムであって、
データネットワークに接続されたクライアント・ユーザー・インターフェースであって、クエリー要請を作成し、このクエリー要請を前記データネットワークを介して処理手段に送信し、これに応える一連の近似を受け取り表示するように構成されているクライアント・ユーザー・インターフェースを備え、
前記クエリー要請をもとに、前記処理手段が前記データネットワークに接続されて、（a）前記複数のデータ要素Ｄの標本Ｓiへのクエリーの結果Ａiを算出し、（b）少なくとも結果Ａiをもとに結果Ｒの近似Ｂiを算出し、（c）（a）及び（b）を、異なる標本Ｓiについて複数のｉ回実行することによって一連の近似を作成し、（d）前記一連の近似を前記クライアント・ユーザー・インターフェースに送信する
ことを特徴とするシステム。
【請求項５９】
前記処理手段が、（a）の一連の適用において、徐々に大きくなっていく標本Ｓi（つまり|Ｓi+1| > |Ｓi|）をＤから選択し、
ステップ（b）の一連の適用において、近似Ｂiの期待精度が徐々に高くなっていく
ことを特徴とする請求項５８に記載のシステム。
【請求項６０】
処理手段が、（a）の少なくとも一回の適用において、前回の標本Ｓjからのデータ要素と複数の新しいデータ要素Ｎiとを含むように標本Ｓiを選択し、ＡjとＮiとの関数としてＡiを算出する
ことを特徴とする請求項５８に記載のシステム。
【請求項６１】
前記処理手段が、Ｄのランダム又は擬似ランダム順列の間順走査によってＮiを作成する
ことを特徴とする請求項６０に記載のシステム。
【請求項６２】
前記処理手段が、Ｄのランダム又は擬似ランダム走査によってＮiを作成する
ことを特徴とする請求項６０に記載のシステム。
【請求項６３】
（a）の少なくとも１回の適用において、標本Ｓiが前記複数のデータ要素Ｄを含んでいる
ことを特徴とする請求項５８に記載のシステム。
【請求項６４】
前記複数のデータ要素Ｄが前記データ記憶装置の単層ファイルに格納されている
ことを特徴とする請求項５８に記載のシステム。
【請求項６５】
前記処理手段が前記クエリーの完了した割合を示すインジケータを作成し、前記クライアント・ユーザー・インターフェースが前記インジケータを表示する
ことを特徴とする請求項５８に記載のシステム。
【請求項６６】
前記処理手段が近似Ｂiごとに前記近似Ｂiの正確度合いを示す信頼インジケータＣiを作成し、前記クライアント・ユーザー・インターフェースが前記信頼インジケータＣiを表示する
ことを特徴とする請求項５８に記載のシステム。
【請求項６７】
前記クライアント・ユーザー・インターフェースがさらに、前記インジケータをグラフィカルに表示するように構成されている
ことを特徴とする請求項６５に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は全体的に、データを分析及びクエリーするためのシステムと方法に関する。さらに詳細には、本発明は、クエリー結果を徐々に、選択によってはクエリー完了時の真のクエリー結果が算出されるまで、近似計算していくためのシステムと方法に関する。
【背景技術】
【０００２】
現代のビジネスでは、大量のデータの分析がますます重要なものとなってきている。しかし、大量のデータセットの複雑な分析及びクエリーには長時間かかりコストが高くなることがある。従って、複雑なデータ分析及びクエリーをより速くより安価に実行するために多くの手段が考案されている。
【０００３】
大量のデータセットをより早く分析するための一つの方法は、より高性能のコンピュータシステムを使用してクエリー処理に掛かる時間を短縮することである。無論、コンピュータ処理のリソースに高い性能を求めると、多くの企業・組織には手が出せないほど高い予算が必要となることが多い。
【０００４】
一つの手段として、大量のデータセットを処理及びクエリーするときに、特定の統計的標本抽出法を利用することが挙げられる。データの統計的標本を作成してからクエリーすることによって、実際に処理してクエリーするデータの量を大幅に低減できるので、処理に関わるコンピュータシステムの必要なリソースも低減できる。共有の特許文献１には、統計的標本抽出法を使用してデータ処理及びクエリーに掛かる時間を減少させる統計的標本抽出機能を有するデータ処理、クエリー及び分析システムが記載されている。特許文献１の全内容を参照により本願明細書に援用する。このシステムでは、大量なデータの複雑な処理、クエリー及び分析が実行されるが、データのクエリー及び分析を担当するコンピュータ処理システムの部分には、そのデータセットサイズの限界よりも大きいデータセットのうちの一部（統計的標本）のみが渡される。この構成によって、データセットのクエリー及び分析に必要なコンピュータ処理リソースが、データセット全体を処理及びクエリーする場合よりも少なくなるという効果がもたらされる。つまり、このような統計的標本抽出法によって、コンピュータ処理用のリソースと、コストと、時間とが節約できる。システムのデータセットサイズの限界よりもクエリーされるデータセットの方が少ない場合を除いては、データセット全体がクエリー及び分析に利用できる訳ではないので、無論、提示される結果は、許容できる程度までは正確である場合もあるが、１００パーセント正確であるとは言えない。
【０００５】
よって、コンピュータ処理用リソースとコストと時間とを節約して、データを処理し、クエリー及び分析するための新しく改良されたシステム及び方法に対する要求は継続して存在している。
【特許文献１】米国特許出願公開第２００３０１４４８６８号明細書
【発明の開示】
【０００６】
《発明の概要》
本発明の一実施形態によると、複数のデータ要素Ｄへのクエリーの結果Ｒの一連の近似を作成するための方法が提供される。この方法は、（a）Ｄの標本Ｓiへのクエリーの結果Ａiを算出するステップと、（b）少なくとも結果Ａiをもとに結果Ｒの近似Ｂiを算出するステップと、（c）ステップ（a）及び（b）を、異なるＳiについて複数のｉ回実行することによって一連の近似を作成するステップとを含んでいる。
【０００７】
本発明の別の実施形態によると、データ記憶装置に格納された複数のデータ要素Ｄへのクエリーの結果Ｒの一連の近似を作成するためのシステムが提供される。このシステムは、前記データ記憶装置にアクセスするように構成されており、（a）複数のデータ要素Ｄの標本Ｓiへのクエリーの結果Ａiを算出し、（b）少なくとも結果Ａiをもとに結果Ｒの近似Ｂiを算出し、（c）（a）及び（b）を、異なる標本Ｓiについて複数のｉ回実行することによって一連の近似を作成するように構成されている処理部を有している。
【０００８】
本発明の別の実施形態によると、データ記憶装置に格納された複数のデータ要素Ｄへのクエリーの結果Ｒの一連の近似を作成するコンピュータプログラムが提供される。前記コンピュータプログラムはコンピュータで読み込み可能な媒体に格納されており、前記データ記憶装置にアクセスし複数のデータ要素Ｄの標本Ｓiへのクエリーの結果Ａiを算出するための第１のコード部分を有している。前記コンピュータプログラムはさらに、少なくとも結果Ａiをもとに結果Ｒの近似Ｂiを算出するための第２のコード部分を有している。前記コンピュータプログラムはさらに、前記第１及び第２のコード部分を、異なる標本Ｓiについて複数のｉ回実行することによって一連の近似を作成するための第３のコード部分を有している。
【０００９】
本発明の別の実施形態によると、複数のデータ要素Ｄへのクエリーの結果Ｒの一連の近似を作成するための方法が提供される。この方法は、（a）Ｄの標本Ｓiへのクエリーの結果Ａiを算出するための各ステップと、（b）少なくとも結果Ａiをもとに結果Ｒの近似Ｂiを算出するための各ステップと、（c）ステップ（a）及び（b）を、異なるＳiについて複数のｉ回実行することによって一連の近似を作成するための各ステップとを含んでいる。
【００１０】
本発明の別の実施形態によると、データ記憶装置に格納された複数のデータ要素Ｄへのクエリーの結果Ｒの一連の近似を作成するためのシステムが提供される。このシステムは、前記データ記憶装置にアクセスし、（a）複数のデータ要素Ｄの標本Ｓiへのクエリーの結果Ａiを算出し、（b）少なくとも結果Ａiをもとに結果Ｒの近似Ｂiを算出し、（c）（a）及び（b）を、異なる標本Ｓiについて複数のｉ回実行することによって一連の近似を作成するための処理手段を有している。
【００１１】
本発明の別の実施形態によると、データ記憶装置に格納された複数のデータ要素Ｄへのクエリーの結果Ｒの一連の近似を作成するためのシステムが提供される。このシステムは、データネットワークに接続されて、クエリー要請を作成しこのクエリー要請を前記データネットワークを介して処理手段に送信するように構成されているクライアント・ユーザー・インターフェースを有している。このクライアント・ユーザー・インターフェースは、クエリー要請に応える一連の近似を受け取り表示する。前記クエリー要請をもとに前記処理手段は、（a）前記複数のデータ要素Ｄの標本Ｓiへのクエリーの結果Ａiを算出し、（b）少なくとも結果Ａiをもとに結果Ｒの近似Ｂiを算出し、（c）（a）及び（b）を、異なる標本Ｓiについて複数のｉ回実行することによって一連の近似を作成し、（d）前記一連の近似を前記クライアント・ユーザー・インターフェースに送信する。
【００１２】
本発明の各種の実施形態のさらなる応用及び利点を、図面を参照しながら以降で説明する。
【発明を実施するための最良の形態】
【００１３】
《好適な実施形態の詳細な説明》
本発明は多くの様々な形態で実現できるが、本願明細書ではいくつかの例示的な実施形態を説明する。ただし、本開示は本発明の原理の例を示すものとみなすべきであり、また、これらの例は、本願明細書に開示及び／又は図示される好適な実施形態に本発明を限定するためのものではない、ということを理解されたい。
【００１４】
クエリー結果の一連の近似算出（以下、ＳＡＱＲ）は、クエリーが完了するまでクエリー結果の一連の近似を算出していく革新的な方法である。
【００１５】
「クエリー」は、各データ要素が「ドメイン」Ｄのメンバーであるデータ要素のリスト（データリスト）から「範囲」Ｒのメンバーである結果を抽出する数学関数Ｑとして、以下のように表すことができる：
Ｑ：list（Ｄ）→  Ｒ
【００１６】
データリストＸに対するクエリー関数Ｑの適用を「Ｘへのクエリー」と称する。また、このような適用によって算出される値Ｑ（Ｘ）を「ＸへのクエリーＱの結果」と称する。
【００１７】
クエリー関数は、データリスト内の順序を変更してもクエリーの結果が変わらない場合は、「バッグ関数」であると見なされる。つまり、あらゆるデータについて以下のようになる：
Ｑ（permute(data)）= Ｑ(data)
【００１８】
前回の結果（Ｒのメンバー）とデータ要素（これもＤのメンバー）から新しい結果（これもＲのメンバー）を算出する「更新関数」Ｕがあれば、例えばこのＵがデータ要素のリストへのクエリーＱの結果と新しいデータ要素とに適用されると、その結果が、その新しいデータ要素をそのリストに加える（appendする）ことによって作成されるリストへのクエリーＱの結果と同一であるようであれば、クエリー関数は「段階的に評価する」ことができる。これは以下によって表すことができる：
Ｕ：（Ｒ×Ｄ）→  Ｒ；
Ｕ（Ｑ(a), b）＝  Ｑ（append(a, b)）;
(append(a, b)は、リスト[a1, a2, … an, b]のこと)
【００１９】
結果（Ｒのメンバー）と、標本の大きさ（自然数グループＮのメンバーである）と、母集団の大きさ（同様にＮのメンバー）とから新しい結果（同様にＲのメンバー）を算出する「近似関数」Ａがあって、データの十分に大きなランダム又は擬似ランダム標本があることを前提に、この標本に適用されるクエリーＱと、標本中のデータ要素の数と、データ中のデータ要素の数とに適用されるＡの結果がこのデータに適用されるＱの結果の有効な近似となるようであれば、クエリー関数は標本から近似を算出できる。これは以下によって表される：
Ａ：（Ｒ×Ｎ×Ｎ）→  Ｒ；
(s = sample(a)) → Ａ（Ｑ(s), |s|, |a|）は、Ｑ(a)の有効な近似である）
通常、近似関数は、より大きい標本へのクエリーの結果が与えられると、期待精度がより高い（つまりＱ(a)に対して期待誤差がより低い）近似を算出し、母集団全体が与えられるとその母集団へのクエリーの結果そのものを算出する（つまり、Ａ（Ｑ(a), |a|, |a| = Ｑ(a)）。
【００２０】
バッグ関数であり標本から近似算出できるクエリー関数は、本発明の方法によって連続的に近似算出できる。次に説明する好適な実施形態では、さらにこのクエリー関数が段階的に評価できることも必要としている。
【００２１】
図１を参照すると、本発明の実施形態に従ったＳＡＱＲを使用してデータをクエリーする方法がフローチャートで示されている。ステップＳ１−１では、（ドメインＲの）結果変数が、空のリストへのクエリーの結果へと初期化されている。これは以下のように表すことができる。  
r : = Ｑ([])
【００２２】
次に、ステップＳ１−２において、データをランダム並べ替え（random permutation）したものに渡ってクエリーを繰り返し（つまり繰り返し評価し）、更新関数を適用したデータ要素の数を記録していく。これは以下によって表される：
rpdata : = random_permutation (data)；
for count : = 1 to |rpdata|；
d = rpdata[count]
【００２３】
ステップＳ１−３では、データ要素ごとに更新関数を前回の結果とデータ要素とに適用して、新しいクエリー結果r:=Ｕ(r, d)を算出する。更新関数の各適用の間に、ステップＳ１−４において、結果と、カウントと、データ要素の総数とに近似関数を適用してＱ（data）の近似を算出することができる。なお、処理効率のために、近似関数の実行を図１に示すように毎回ではなく一定期間ごとのみにすることが必要となる場合もある。近似関数は以下によって表される：
a : = Ａ(r, count, |rpdata|)
【００２４】
アプリケーションによっては、算出処理の実行中に、近似をステップＳ１−５においてユーザーに表示する、又は他の処理に対して出力することもできる。
【００２５】
さらに繰り返す必要がある場合（Ｓ１−６）、クエリーの次の調査が実行される。繰り返すべき処理が全て完了すると、クエリー結果がステップＳ１−７にて作成される。この段階ではクエリーは全データに対して実行されているので、ここでの結果rはＱ(data)と正確に同一である。この段階で、クエリー結果rをユーザーに表示できる、又は格納できる、又は他の処理に出力できる。
【００２６】
つまり、本発明の方法では、徐々に大きくなる標本に対してクエリーを評価し近似のクエリー結果を作成していき、これにより、データの母集団全体に対してクエリーすることになるまで徐々に精度の高い近似を出力していくことができる。前述の実施形態では、各標本は前回の標本と一つの追加のデータ要素とから構成されており、更新関数を一度適用するだけで次のより大きな標本へ進むことができる。近似関数が有効であるとしてランダム並べ替えに関するコストを無視すれば、この処理は、更新関数を利用してデータリスト全体へクエリーを評価するまで漸近的に結果を提供していく。
【００２７】
アプリケーションによっては、データ要素のランダム順列を算出して格納し、そしてそれを多くのクエリーで使用することが適切である場合がある。又は、ランダム順列に対応する順序でランダムアクセスデータ構造を走査する、又は種類を問わず他の方法を利用して対応する順序でデータを走査する方がより適切である場合がある。
【００２８】
新しいデータ要素は、順列におけるランダムな位置に各要素を挿入することによって挿入すると、データリストをランダム順列の状態で維持できる。
【００２９】
クエリーの進行中にデータ要素を挿入又は修正又は削除する必要がある場合は、その処理が起こってもこれに纏わる変更を無視してクエリーすべきであるか（必要に応じて修正又は削除された要素を保存して）、又は該当するデータ要素が現在処理中の標本に（つまり、既に更新関数によって処理されたデータリストのランダム順列の一部に）属している場合は、クエリー処理はこのような変更も反映すべきであるかのどちらかである。新しい要素「ｎ」の現在処理中の標本への挿入は、単に更新関数をこれらに適用することによって反映させることができる。有効である標本の大きさの変更を記録しておく必要もある場合がある。これは以下のように表すことができる：
r : = Ｕ（r, n）
count : = count + 1
【００３０】
Ｕ−１（Ｑ（append(a, b)）, b）＝Ｑ(a)であるようなクエリーへの「逆更新関数」Ｕ−１があれば、現在処理中の標本における古い値「o」から新しい値「n」へのデータ要素の修正、又は古い値「o」に対応するデータ要素の現在処理中の標本からの削除を以下のようにして反映させることができる：
修正：  r: = Ｕ（Ｕ−１(r, o), n）
削除：  r: = Ｕ−１(r, o)
count: = count − 1
【００３１】
真に「ランダム」な順列を、全てのケースで達成することは困難である場合もある。ほぼ全てのクエリー及び近似関数のために、決定性擬似ランダム値によって、又はデータ要素ごとに異なる値を生成するようなデータ要素の機能によるハッシュによってソートすることを、近似の正確度合いに影響を与えずに順列を作成するために利用できる。
【００３２】
別の実施形態によると、データ要素を連結可能な２つ以上の標本に分割するようにしてもよい。各データ要素が一つの標本に属する必要があり、各データ要素は、同等かつ別個の確率を有する所定の標本に属する。これらの標本を連結したものは、必ずしも内部的にランダムな順序であるとは限らないので、ランダム順列とは言えない。しかし、近似が標本間の境目でのみ算出される場合は、その結果はやはり有効かつ正確である。
【００３３】
本発明の非常にシンプルな実施形態は、データ要素の小さな標本を作成し、その小さな標本に渡って高速でクエリーを評価して第一の近似を算出し、そしてデータリスト全体に渡ってクエリーを評価して真の結果となる第二の近似を算出するものである。
【００３４】
本発明によって、真のクエリー結果の算出を待たずにいつでもクエリーを打ち切ることが可能となる。近似の結果は打ち切る直前の処理をもとに出力できる。クエリーは、特定のアプリケーションにおいて、統計的性質をもとに近似関数から決定できるので近似結果の出力がその目的にとって十分に正確であるという理由で、早期に打ち切る場合がある。同様に、状況が変化するとクエリーの結果がもはや有効ではなくなるという理由から、クエリーを早期に打ち切る場合もある。
【００３５】
なお、本発明は、クエリーが完了したときの結果の完全な正確さと引き換えにコストをさらに減少させるために、一般的なランダム標本抽出と組み合わせて、データ要素のランダム標本のみが並び替えられてクエリーされるようにすることができる。同じ目的が順列のサフィックスを単に取り除くことによって達成できる。これにより格納するデータ要素の数は減少するがクエリーの完了は不可能となる。
【００３６】
本発明の要件を満たす関数の例示的なクラスを以下に列挙する。
【００３７】
各データ要素の関数Ｆの合計：
Ｑ(data) =      Ｆ(d) ;
Ｕ(r, d) = r + Ｆ(d) ;
Ａ(r, n, Ｎ) = r * Ｎ / n 
【００３８】
複数のクエリーの組み合わせ：
Ｑ(data) = (Ｒ(data), Ｓ(data));
Ｕ((r,s), d ) = (ＵＲ(r,d), ＵＳ(s,d));
Ａ((r,s), n, Ｎ) = (ＡＲ(r,n,Ｎ), ＡＳ(s,n,Ｎ)) 
【００３９】
複数のクエリーの関数：
たとえ別個のクエリーの結果が出力では必要ないとしても、これらの結果で結果のドメインを拡大させる。これにより、各クエリーの更新関数でこれらの結果を使用できるようになる。更新関数においてＦを調査するように選択しない実施も可能である。  
Ｑ(data) = (Ｆ(Ｒ(data), Ｓ(data)), Ｒ(data), Ｓ(data));
Ｕ((f,r,s), d) = (Ｆ(ＵＲ(r,d), ＵＳ(s,d)), ＵＲ(r,d), ＵＳ(s,d));
Ａ((f,r,s), n, Ｎ) = (Ｆ(ＡＲ(r,n,N), ＡＳ(s,n,N)), ＡＲ(r,n,N), ＡＳ(s,n,N))
【００４０】
ある述語Ｆを満たすデータ要素の抽出。ここでは、このような抽出のランダム標本がリスト全体の有効な近似となる。  
Ｑ(data) = Concatenate ||d in data ({{d} if Ｆ(d), {} otherwise );
Ｕ( r, d ) = {append(r,d) if Ｆ(d), r otherwise ;
Ａ( r, n, Ｎ ) = r 
【００４１】
以下の擬似コードが、例示的なＳＡＱＲ処理のスクリプト方法を示している。  
r := ( Undefined, 0, 0 )
rpdata := random_permutation(data)
for count := 1 to |rpdata|
d := rpdata[count]
r := U( r, d )
if (count ％ 3000) = 0
(fraction, numerator, denominator):= A( r, count, |rpdata|)
print “割合の近似値は”, fraction * 100.0
if (ユーザーが処理を中断する)
exit
fraction, numerator, denominator := r
print “割合の真の値は”, fraction * 100.0
exit
【００４２】
以下の例によって本発明の方法を例示する。なお、この例は本発明を限定するものではない。大勢の人々についての情報を分析するとする（例えば、国勢調査、又は世論調査などからの情報）。例えば、各個人に、「年齢」、「２００３年の所得」、「都市」、「目の色」などの様々な属性を付帯できるようになっているとする。このデータは、指定の条件に合う人々の割合を知りたいという要求に応じて繰り返し調査できる。この場合の条件としては、例えば以下のようなものが考えられる：
所得＜＄20,000の人のうち、何パーセントが都市＝「ニューヨーク」であるか？
都市＝「シアトル」の人のうち、何パーセントが所得＞＄80,000であるか？
年齢＞55の人のうち、何パーセントが所得＜＄15,000であるか？
【００４３】
また、データセットが非常に大量（例えば、地球の全人口など）であって、利用できるコンピュータ処理用リソースでは、上述のような指定の質問のいずれに答えを出すのにも相当な時間がかかるものとする。データのユーザーにとって時間が重要な問題である場合、ユーザーが、長い処理時間を掛けて真の結果（54.125936…％）を得るよりも、短時間で得られるならば近似の結果（約54.2％）でもよいとすることはよくあることである。
【００４４】
上述の前提に加えて、各個人についての情報が属性の一データとして表されるとし、これらのデータが以下のように「データ」リストに入れられているとする：
Ｄ＝名前×年齢×所得×都市×目の色；
ｄ１＝（「ジョン・ドウ」、25、＄35300、「ニューヨーク」、青）；
ｄ２＝（「ジェーン・スミス」、42、＄61200、「シアトル」、茶）；
data = [d1, d２, … dn] ここでは（diはＤのメンバーである）
【００４５】
前処理のステップでは、このデータリストをランダムに並び替えて（rpdata = random_permutation(data)）、何らかの法則に沿った人々の順序がない状態にする。これは、例えば、擬似ランダムキーで各diを増やしていき、そしてこのキーによってデータリストを結合してソートすることなどによって達成できる。これらのステップは、データの全リストを保有するのに十分な容量のＲＡＭを必要とせずに、外部の（ディスク）ストレージにて実行できる。
【００４６】
上述したようなクエリーが提出されると、２つの述語関数がクエリー中の条件をもとに定義される。例えば、「所得＜＄20,000の人のうち、何パーセントが都市＝「ニューヨーク」であるか？」というクエリーでは、以下のような２つの述語が定義される：
PredA(d) = {1 if income(d) < ＄20000, 0 otherwise；
PredB(d) = {1 if city(d) = “ニューヨーク”, 0 otherwise
【００４７】
「年齢＞55の人のうち、何パーセントが所得＜＄15,000であるか？」というクエリーの場合は、以下のような２つの述語が定義される：
PredA(d) = {1 if age(d) > 55, 0 otherwise；
PredB(d) = {1 if income(d) < $15000, 0 otherwise
【００４８】
これらの述語関数をもとに、クエリー関数を以下のように定義できる：
Ｑ(d) = ( (    PredA(d)*PredB(d)) / (Sumd in data PredA(d)), 
(    PredA(d)*PredB(d)),
(    PredA(d)) 
【００４９】
適切な更新関数と近似関数は以下のように定義される：
Ｕ((f,r,s), d ) = ((d+PredA(d)*PredB(d))/(d+PredA(d)),
d + PredA(d)*PredB(d), 
d + PredA(d) ),
Ａ((f,r,s), n, N) = (r/s, r*N/n, s*N/n)
【００５０】
上述した通りにデータリストが順に処理されていく。この例では、数千のレコードが処理される度に、近似関数が計算されて、その結果がパーセントの形式に整えられて、ユーザーに（近似の結果として）表示される。ユーザーは処理を中断する機会を与えられる。処理が中断されなければ、クエリーが完了したときに真の結果が表示される。
【００５１】
ＰＹＴＨＯＮスクリプト言語で記載されたスクリプトの以下のプログラムを上述の例を遂行するために使用できる。なお、このプログラムは、理解を容易にするために一例として示すものに過ぎず。本発明をどのような形であれ制限するものではない。  
import random
domains = ("名前", "年齢", "所得", "都市", "目の色")
data…  =    [("ジョン・ドウ", 25, 35300, "ニューヨーク", "青"),
..........("ジェーン・スミス", 42, 61200, "シアトル", "茶"),
..........("ジェイソン・ジョンソン", 33, 48400, "シアトル", "茶"),
..........("フレッド・フリントストーン", 10000, 0, "ベッドロック", "茶"),
..........("ボブ・ジョーンズ", 18, 0, "ボストン", "青"),
..........              ]
#上記の一握りのレコードをあまり
#大きくないサイズにコピーする
data = data * 10000
def ToDictionary( tuple ):
.........."""ドメインからのキーとデータからの値を含む
..........ディクショナリを返す"""
..........dict = {}
..........for k,v in zip(domains,tuple):
..........          dict[k]=v
..........return dict
#データのランダム順列を作成する
rpdata = data[:]
random.shuffle(rpdata)
while 1:
..........# ユーザーにクエリーを入力するよう要請する
..........queryA = raw_input("クエリー：…である人のうち何パーセントが")
..........queryB = raw_input("              …であるか")
..........#クエリーをもとにPredA とPredB とを定義する
..........def PredA(d): return float(eval(queryA, ToDictionary(d)))
..........ef PredB(d): return float(eval(queryB, ToDictionary(d)))
..........def Update( (f,r,s), d ):
..........      return (r+PredA(d) and (r+PredA(d)*PredB(d))/(s+PredA(d)),
..........      r+PredA(d)*PredB(d),
..........      s+PredA(d) )
..........def Approximate( (f,r,s), n, N ):
..........      return (s and r/s, r*N/n, s*N/n)
..........try:
..........          # 徐々に精度の高いクエリー結果を算出していく
..........          result = ("未定義", 0, 0)
..........          for i,d in enumerate(rpdata):
..........                    count = i+1
..........                    result = Update(result, d)
..........                    if count % 1000 == 0:
..........                    fraction, numerator, denominator = Approximate(result, count, len(rpdata))
..........                    print "割合の近似値は", fraction * 100.0
..........          fraction, numerator, denominator = result
..........                    print "割合の真の値は", fraction * 100.0
..........except KeyboardInterrupt:
..........      print
..........      print "クエリーはユーザーによって中断されました。"
..........Print
【００５２】
前記のスクリプトを実行したら以下の例示的な結果が生成された：
クエリー：都市 == "ニューヨーク"である人のうち何パーセントが  …所得 < 30000であるか割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.０割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値は0.0割合の近似値はクエリーはユーザーによって中断されました。  
クエリー: 年齢 > 20である人のうち何パーセントが  …所得 < 30000であるか割合の近似値は25.0316055626割合の近似値は24.7648902821割合の近似値は23.9038785835割合の近似値は23.8170347003割合の近似値は24.2576748868割合の近似値は24.1379310345割合の近似値は24.6695248303割合の近似値は24.5721463338割合の近似値は24.8015596714割合の近似値は24.9749373434割合の近似値は25.0割合の近似値は25.0260145682割合の近似値は25.0287797391割合の近似値は24.9288002848割合の近似値は24.8626602297割合の近似値は24.9219968799割合の近似値は25.0459052516割合の近似値は25.0797614093割合の近似値は24.9852100177割合の近似値は25.0046848648割合の近似値は25.1070154578割合の近似値は25.0823208811割合の近似値は25.145404142割合の近似値は25.0886155129割合の近似値は25.0275302833割合の近似値は24.9843607141割合の近似値は24.9212087505割合の近似値は24.8747091462割合の近似値は24.8616874136割合の近似値は24.8402856069割合の近似値は24.9201923465割合の近似値は24.8816371249割合の近似値は24.9687085151割合の近似値は24.9687385068割合の近似値は25.0223190372割合の近似値は25.0355717508割合の近似値は25.0388382303割合の近似値は25.0419118372割合の近似値は25.0272243931割合の近似値は25.0421743205割合の近似値は25.093004818割合の近似値は25.1286781113割合の近似値は25.0922938287割合の近似値は25.038337025割合の近似値は25.0763422353割合の近似値は25.0801325583割合の近似値は25.0392193358割合の近似値は25.0436186558割合の近似値は25.0255128074割合の近似値は25.0割合の真の値は25.0
クエリー：目の色== "茶"である人のうち何パーセントが  …都市== "シアトル"であるか割合の近似値は66.0377358491割合の近似値は67.0008354219割合の近似値は67.7657760091割合の近似値は67.940552017割合の近似値は67.5420875421割合の近似値は67.6561187342割合の近似値は67.0090778786割合の近似値は67.1701279631割合の近似値は66.8466120625割合の近似値は66.5210818075割合の近似値は66.3658611196割合の近似値は66.3400979706割合の近似値は66.3701985048割合の近似値は66.5072342461割合の近似値は66.5958398569割合の近似値は66.5164535737クエリーはユーザーによって中断されました。
【００５３】
上記の例から明確に理解できるように、クエリー結果の一連の近似が算出されていき、クエリーを最後まで実行させた場合、最後のこのような「近似」は真のクエリー結果となる。実際の精度は不規則に変動するが、連続して算出される各近似の期待精度は高まっていく。
【００５４】
上述の例では、印刷された出力の性質上、その時点までの連続算出された近似の全てが表示されている。これが有益である例もあるが、最終かつ最良の近似だけ表示すればよいというのがもっと一般的である。
【００５５】
図２は、本発明の方法を実行可能である処理機構の構成を示すブロック図である。処理機構の構成２００には、データ記憶装置２０４に接続された処理部２０２と、入／出力（Ｉ／Ｏ）装置２０６と、表示装置２０８と、プリンタ装置２１０とが含まれている。処理部はＣＰＵを有していてもよく、上述の処理を遂行するためのコンピュータプログラムを実行するように構成されていてもよい。当技術の通常の技量を有するものであれば、処理機構の構成２００が、無制限の数のハードウェア及びソフトウェア構成で実現可能であり、これらのハードウェア及びソフトウェアはアプリケーションに応じて選択可能であることが分かるだろう。例えば、ＳＡＱＲエンジンは、ＰＹＴＨＯＮ等のオブジェクト指向のスクリプト言語で記述でき、ＵＮＩＸをベースとするプロセッサ上で作動できる。
【００５６】
クエリーされるデータはデータ記憶装置２０４に格納されていてもよい。データ記憶装置２０４は、例えばスタンドアローンのデータベース、データウェアハウス等である。データは、単層ファイルに、又はその他のどのような構成で格納されていてもよい。データは、オブジェクト指向型のもの、リレーショナル型のもの等であってもよい。当業者であれば、あるデータ構造では、その他の構造よりもランダム順列を達成することがより困難となる場合があることが分かるだろう。
【００５７】
当業者であれば、分散型構成において、又はクライアント・サーバー構成やウェブをベースとした構成などの様々な構成のいずれを介しても、処理を中央で実行するようにできることが分かるだろう。
【００５８】
データの表示は、クライアントユーザー用のインターフェース等、どのような手段を介したどのような形で実行してもよい。情報は、ベンチマーク、信頼区間、カラーランプ測定値、動的抽出次元、スケールと凡例、トレリスグラフ、平滑推移、線グラフのための移動平均及びカーネル平滑化など、様々なプレゼンテーション手法を用いて表示できる。
【００５９】
図３は、基本的で例示的なインターフェース３００を示している。インターフェース３００ではクエリー３０２の入力が可能であり、クエリーの結果３０４が表示される。結果３０４は、前述したとおりにデータに渡ってクエリーが処理されるのに従って更新されていってもよい。「信頼度」インジケータ３０６を近似の結果と共に表示して、近似の正確度合いを示すことができる。この例では、シンプルな棒グラフを用いて既に調査されたデータの量（サンプルの大きさ）を示している。しかし、信頼度インジケータは、近似の正確度合いを示すために様々な統計分析手法のいずれを用いて計算しても構わない。標準偏差などデータのその他の特性も同様に表示できる。
【００６０】
統計学の分野では、信頼区間及びその他の正確度の指標を算出するために多くの有用な式や方法が存在している。述語を満たすデータ要素のカウントについての８０％対称信頼区間を近似算出するのに利用できるあるシンプルかつ効果的な式は、以下のようになる：
((count + 0.68)^0.5 * 1.281551 + 1.2269) / count
【００６１】
ＳＡＱＲが、例えば、ユーザーのシステムとの１回のやりとりに応えて（つまり１つのクエリーをもとに）時間の経過と共に精度を高めていく結果の連続表示をシステムのユーザーに提供できる、などの明らかな利点を有することが当業者であれば分かるだろう。つまり、１つのクエリー要請に応えて表示可能な動的クエリー結果を作成する。この動的クエリー結果では、それぞれ精度と信頼度が高まっていく瞬間的な結果の無制限なセットが提供される。
【００６２】
ここまで、図面を参照しながら様々な好適な実施形態を詳細に説明してきた。これらの好適な実施形態をもとに本発明を説明したが、当業者であれば、説明した実施形態への修正、改変、代替の構成の適用などが本発明の趣旨と範囲の中で可能であることが明確に理解できるであろう。
【００６３】
《著作権について》
本特許出願の一部は著作権保護の対象となる内容を含んでいる。著作権の所有者は、特許商標局で開示されているとおりの特許書類又は特許開示は誰が複製してもよいとしているが、それ以外の場合は全著作権を留保する。
【図面の簡単な説明】
【００６４】
【図１】図１は、例示的なＳＡＱＲ方法を示すフローチャートである。
【図２】図２は、本発明を実施するために使用できるコンピュータ処理機構の構成を示すブロック図である。
【図３】図３は、本発明の一実施形態に従った例示的な表示を図示している。
【符号の説明】
【００６５】
２００  処理機構の構成
２０２  処理部
２０４  データ記憶装置
２０６  Ｉ／Ｏ装置
２０８  表示装置
２１０  プリンタ
３００  インターフェース
３０２  クエリー
３０４  クエリーの結果
３０６  信頼度
【図１】
2008516313.tif 000003
【図２】
2008516313.tif 000004
【図３】
2008516313.tif 000005
【国際調査報告】
2008516313.tif 000006