図面 (/)

技術 情報の表現を生成するために使用するための情報を維持するための方法

出願人 アルカテル-ルーセントユーエスエーインコーポレーテッド
発明者 フィリップビー.ギボンズヨッシマティアスアンドリューウィトコウスキー
出願日 1996年12月25日 (23年10ヶ月経過) 出願番号 1996-345315
公開日 1997年9月9日 (23年2ヶ月経過) 公開番号 1997-237266
状態 未査定
技術分野 金銭登録機・受付機 特定用途計算機 金銭登録機・受付機
主要キーワード 発見的アルゴリズム 割当て量 小間物 集中システム 乱数発生関数 サンプリング誤差 補助定理 掃除用
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(1997年9月9日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (5)

課題

本発明は、情報を表現するための方法の分野に関する。

解決手段

本発明による方法においては、限定されたメモリデータベース内に項目商品)と関連する情報が維持され、この情報を使用して、情報の表現、例えば、高バイアスヒストグラムが生成される。本発明の方法による第一の実施例においては、ある閾値を超える販売量を持つ全ての項目と関連する情報が、それら項目の概算数量と共に維持される。閾値を適当に選択することによって、情報の表現を生成するために維持することを要求される情報の量が制限されるが、この閾値によって必要な情報が高い確率にて情報の表現内に存在することが保証される。

概要

背景

データセット高バイアスヒストグラムは、そのデータセット内の最も頻繁に発生する複数の項目表現(例えば、グラフィックディスプレイあるいはリスト)である。これら最も頻繁に発生する項目は、好ましくは、各項目と関連する(発生)数量によって決定され、数量が大きければ大きいほど、その項目がより頻繁に発生することを表す。これに関しては、Y.E.Ioannidis and S.Christodoulakis,“Optimal histograms for limiting worst-case error propagation in the size of join result”,ACMTrans. Database Sys.,vol.18,No.4,pp.709-748,December 1993を参照されたい。高バイアスヒストグラムは、営業活動において重要である。例えば、高バイアスヒストグラムは、ある企業によって扱われる製品の各部門あるいはカテゴリーに対する最も良く売れる項目およびそれらの数量(つまり、販売量)のリストとして(リストの表現として)使用することができる。

あるスーパーマーケットが、そのスーパーマーケットによって扱われる商品の様々な部門に対する最も良く売れる上位3つの項目およびそれらの数量に対するリストを維持することを考える(これら項目としては、例えば、食料品項目、個人ケアー項目、掃除用品、家庭用品贈答品小間物品などが考えられる)。このリストは、典型的には、データベースシステムを使用して作成される。データベースシステムは、その企業によって扱われるさまざまな項目と関連する情報、例えば、それら項目に対応する識別番号、およびそれら項目の販売量と対応する数量を(メモリ内に)蓄積するためのデータベースを含む。このデータベース内の情報は、スーパーマーケットのチックアウト通路の所に設置されたPOS端末からの新たな販売活動に関する情報を使用して絶えず更新される。このデータベースは、さらに、典型的には、処理サブシステムを含むが、この処理サブシステムは、データベース内の情報にアクセスし、データベースシステムに入力された照会応答してデータベース内の情報の高バイアスヒストグラムあるいは他の表現を生成することができる。この高バイアスヒストグラムおよび関連する統計を生成あるいは報告する能力は、幾つかの市販のデータベースシステム(例えば、DbaseII(登録商標))において既に実現されている機能である。ただし、後に説明されるように、高バイアスヒストグラムを生成するために使用される情報を、正確に、過多メモリあるいはタスク留保することなしに、維持することは、困難なことである。

スーパーマーケットのデータベースシステムに、ある部門に対する最も良く売れる上位3つの項目およびそれらの数量のリストを維持する問題について考えれば、このことが良く理解できる。ここで、このデータベースシステムは、新たな販売活動によって絶えず更新されるものとする。高バイアスヒストグラムを生成するための技法極端な例においては、単に、各部門に対して、その部門内の可能な全ての項目およびそれら項目の販売数量のリストが維持される。次に、高バイアスヒストグラムが、単に、これらリスト全てを分類することによって生成される。ただし、このような実現は、複数の短所を持つ。第一に、この実現においては、全ての項目が、数量とは無関係に、リスト内に入れられるために、多量のメモリを必要とする。さらに、大きなメモリを持つシステムは、一般的に、費用が高く、また、動作の速度が遅くなる(これは、高バイアスヒストグラムを生成するために全てのエントリにアクセスすることが必要になるためである)。代替技術として、全ての販売活動を記録し、これら活動を定期的にサンプリングして(例えば、五回の活動に対して一度調べることによって)、最も良く売れている項目を決定する方法が考えられる。この方法は、動作の速度を向上させることはできるが、この技法に必要とされるメモリの量は、典型的には、サンプリング誤差に基づく高バイアスヒストグラムの不正確さを低減するために、減らすことができない。

反対側の極端においては、多数の部門に対する最も良く売れる3つの項目のリストが、小量のメモリ(例えば、部門当たり3つの項目に関する情報のみを保持するメモリ)を使用して実現される。メモリ要件の低減は、典型的には、データベースシステムの購入および維持の費用が安くなり、また、応答が早くなることを意味する。メモリシステムの低減は、セットの部門内の特定の部門に対して、3のサイズの、要約テーブルTを使用して実現することができる。テーブルTは、特定の部門内の3つの最も良く売れる項目と関連する情報、例えば、これら3つの項目のおのおのに対する今日までの販売数量を含む。上のスーパーマーケットの例をさらに続けて、この特定の部門が、食料品を扱う部門であり、ここで、時間t1における最も良く売れる3つの項目およびそれらの数量が、テーブルT(t1)にリストされている通りであるものとする。

概要

本発明は、情報を表現するための方法の分野に関する。

本発明による方法においては、限定されたメモリのデータベース内に項目(商品)と関連する情報が維持され、この情報を使用して、情報の表現、例えば、高バイアスヒストグラムが生成される。本発明の方法による第一の実施例においては、ある閾値を超える販売量を持つ全ての項目と関連する情報が、それら項目の概算数量と共に維持される。閾値を適当に選択することによって、情報の表現を生成するために維持することを要求される情報の量が制限されるが、この閾値によって必要な情報が高い確率にて情報の表現内に存在することが保証される。

目的

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

項目と関連する情報を、データベース内に入力するために受信するステップ;および前記のデータベースが前記の項目と関連する他の情報を含む場合は、前記の他の情報を受信された情報に基づいて更新し、前記のデータベースが前記の項目と関連する他の情報を含まない場合は、前記の情報を前記のデータベースに、ある閾値関数としての確率にて(確率フィルタリングを使用して)加えるステップを含むことを特徴とする方法。

請求項2

前記の確率が、前記の情報が前記のデータベースに加えられるときの成功の確率であることを特徴とする請求項1の方法。

請求項3

前記のデータベースに加えられる前記の項目と関連する情報が前記の項目と関連する数量であり、前記の方法がさらに:前記のデータベース内に前記の項目と関連する前記数量を前記の閾値の関数として設定するステップを含むことを特徴とする請求項1の方法。

請求項4

前記の閾値が固定された値であることを特徴とする請求項1の方法。

請求項5

前記のデータベースがサイズを制限されることを特徴とし、このサイズの限度から前記のデータベース内の情報の最大量が決定され、さらに前記のデータベースが前記のサイズの限度一杯である場合、前記の閾値を調節するステップが含まれることを特徴とする請求項1の方法。

請求項6

前記のデータベース内の各項目と関連する情報に対して、前記のデータベース内の前記の各項目と関連する情報を、前記の調節された閾値の関数としての確率にて(調節された閾値の関数としての確率フィルタリングを使用して)維持するステップがさらに含まれることを特徴とする請求項5の方法。

請求項7

前記のデータベース内の前記の情報に基づいて高バイアスヒストグラムを生成するステップがさらに含まれ、前記の情報が前記のデータベース内の項目と関連する数量値から成り、前記の数量値が前記の調節された閾値の関数であることを特徴とする請求項4の方法。

請求項8

データベース内に情報を維持するための方法であって、前記のデータベースがある情報をある最大量だけ蓄積することができ、この方法が:項目と関連する情報をデータベース内に入力するために受信するステップ;前記のデータベースが前記の項目と関連する他の情報を含む場合、前記の他の情報を受信された情報に基づいて更新するステップ;前記のデータベースが情報の前記の最大量を含まない場合は、前記の情報を前記のデータベースに加えるステップ;および前記のデータベースが情報を前記の最大量だけ含む場合は、a)閾値を調節し、b)前記のデータベース内の各項目と関連する情報に対して、前記のデータベース内の前記の各項目と関連する情報を、前記の調節された閾値の関数としての確率にて(調節された閾値の関数としての確率を使用して)保持するステップを含むことを特徴とする方法。

請求項9

前記のデータベース内の前記の情報に基づいて高バイアスヒストグラムを生成するステップがさらに含まれ、前記の情報が項目と関連する数量値から成り、前記の数量値が前記の調節された閾値の関数であることを特徴とする請求項8の方法。

技術分野

0001

本発明は、情報を表現するための方法の分野に属する。

背景技術

0002

データセット高バイアスヒストグラムは、そのデータセット内の最も頻繁に発生する複数の項目の表現(例えば、グラフィックディスプレイあるいはリスト)である。これら最も頻繁に発生する項目は、好ましくは、各項目と関連する(発生)数量によって決定され、数量が大きければ大きいほど、その項目がより頻繁に発生することを表す。これに関しては、Y.E.Ioannidis and S.Christodoulakis,“Optimal histograms for limiting worst-case error propagation in the size of join result”,ACMTrans. Database Sys.,vol.18,No.4,pp.709-748,December 1993を参照されたい。高バイアスヒストグラムは、営業活動において重要である。例えば、高バイアスヒストグラムは、ある企業によって扱われる製品の各部門あるいはカテゴリーに対する最も良く売れる項目およびそれらの数量(つまり、販売量)のリストとして(リストの表現として)使用することができる。

0003

あるスーパーマーケットが、そのスーパーマーケットによって扱われる商品の様々な部門に対する最も良く売れる上位3つの項目およびそれらの数量に対するリストを維持することを考える(これら項目としては、例えば、食料品項目、個人ケアー項目、掃除用品、家庭用品贈答品小間物品などが考えられる)。このリストは、典型的には、データベースシステムを使用して作成される。データベースシステムは、その企業によって扱われるさまざまな項目と関連する情報、例えば、それら項目に対応する識別番号、およびそれら項目の販売量と対応する数量を(メモリ内に)蓄積するためのデータベースを含む。このデータベース内の情報は、スーパーマーケットのチックアウト通路の所に設置されたPOS端末からの新たな販売活動に関する情報を使用して絶えず更新される。このデータベースは、さらに、典型的には、処理サブシステムを含むが、この処理サブシステムは、データベース内の情報にアクセスし、データベースシステムに入力された照会応答してデータベース内の情報の高バイアスヒストグラムあるいは他の表現を生成することができる。この高バイアスヒストグラムおよび関連する統計を生成あるいは報告する能力は、幾つかの市販のデータベースシステム(例えば、DbaseII(登録商標))において既に実現されている機能である。ただし、後に説明されるように、高バイアスヒストグラムを生成するために使用される情報を、正確に、過多メモリあるいはタスク留保することなしに、維持することは、困難なことである。

0004

スーパーマーケットのデータベースシステムに、ある部門に対する最も良く売れる上位3つの項目およびそれらの数量のリストを維持する問題について考えれば、このことが良く理解できる。ここで、このデータベースシステムは、新たな販売活動によって絶えず更新されるものとする。高バイアスヒストグラムを生成するための技法極端な例においては、単に、各部門に対して、その部門内の可能な全ての項目およびそれら項目の販売数量のリストが維持される。次に、高バイアスヒストグラムが、単に、これらリスト全てを分類することによって生成される。ただし、このような実現は、複数の短所を持つ。第一に、この実現においては、全ての項目が、数量とは無関係に、リスト内に入れられるために、多量のメモリを必要とする。さらに、大きなメモリを持つシステムは、一般的に、費用が高く、また、動作の速度が遅くなる(これは、高バイアスヒストグラムを生成するために全てのエントリにアクセスすることが必要になるためである)。代替技術として、全ての販売活動を記録し、これら活動を定期的にサンプリングして(例えば、五回の活動に対して一度調べることによって)、最も良く売れている項目を決定する方法が考えられる。この方法は、動作の速度を向上させることはできるが、この技法に必要とされるメモリの量は、典型的には、サンプリング誤差に基づく高バイアスヒストグラムの不正確さを低減するために、減らすことができない。

0005

反対側の極端においては、多数の部門に対する最も良く売れる3つの項目のリストが、小量のメモリ(例えば、部門当たり3つの項目に関する情報のみを保持するメモリ)を使用して実現される。メモリ要件の低減は、典型的には、データベースシステムの購入および維持の費用が安くなり、また、応答が早くなることを意味する。メモリシステムの低減は、セットの部門内の特定の部門に対して、3のサイズの、要約テーブルTを使用して実現することができる。テーブルTは、特定の部門内の3つの最も良く売れる項目と関連する情報、例えば、これら3つの項目のおのおのに対する今日までの販売数量を含む。上のスーパーマーケットの例をさらに続けて、この特定の部門が、食料品を扱う部門であり、ここで、時間t1における最も良く売れる3つの項目およびそれらの数量が、テーブルT(t1)にリストされている通りであるものとする。

発明が解決しようとする課題

0006

この決定を行なうための様々な規則が提案されているが(例えば、数量と無関係に、売り上げの最も小さな項目を最近最も良く売れた項目と常に置換する方法などが提案されている)、ただし、典型的には、メモリ内に維持されているこれら情報から高バイアスヒストグラムを生成した場合の精度はあまり良くない。

0007

従って、データの表現、例えば、高バイアスヒストグラムを生成するために使用されるための情報を維持するための、小量のメモリを使用し、それでいて、予期しなかった傾向を検出することができ、そして、正確な表現を生成することができる方法が必要とされている。

課題を解決するための手段

0008

本発明においては、データ表現、例えば、高バイアスヒストグラムを生成するために使用される情報が、限定されたメモリを使用して維持される。本発明においては、メモリ内に蓄積されるべき情報は、ある閾値に基づく確率にて(確率フィルタリングを使用して)選択される。より詳細には、本発明の方法は、ある項目と関連する情報をデータベースに入力するために受信し、このデータベースが、その項目と関連する他の情報を既に含む場合は、この他の情報を受信された情報に基づいて更新する。データベースがその項目と関連する他の情報を含まない場合は、本発明の方法は、情報をデータベースに、ある閾値の関数としての確率にて(関数としての確率フィルタリングを使用して)加える。この確率は、情報がデータベースに加えられるときの成功の確率である。

0009

本発明の第一の実施例においては、ある閾値以上の販売量を持つ全ての項目と関連する情報が維持される。この閾値の適当な選択によって、維持および蓄積されるべき情報の量が制限される。ある項目と関連する情報がいったん入力あるいは加えられると、そのときの閾値を使用して、その項目の実際の販売概算数量が設定(計算)される。これら項目のこれら概算数量が、情報の表現、例えば、高バイアスヒストグラムを生成するために使用されるが、こうして生成される表現は、長所として、小さなエラーと高い信頼性を持つ。本発明の第二の実施例においては、情報が限定された割当て量のメモリ内に維持されるが、これは、閾値を蓄積される情報の量が制限されるような方法にて調節することによって達成される。

0010

第一の実施例に対する本発明の方法の精度について検討されたが、この方法は、高バイアスヒストグラムに対する概算結果を与えるが、これら結果は、全体としてだけでなく、高バイアスヒストグラム内に出現すべき、あるいは出現すべきでない、個々の項目に対しても、高い精度と高い信頼性を持つことが確認された。

0011

詳細な説明
このセクションは、4つの部分に分けられる。第一の部分においては、本発明がその中で実施されるシステムについて説明され、本発明の方法が概説される。第二の部分においては、本発明の方法の二つの実施例が示される。第三の部分においては、第一の実施例の分析が示される。この分析は、本発明の方法の第一の実施例における項目(item)の概算の数量(approximate count)を決定するために使用される補償係数(compensation factor)を誘導する。この分析は、また、第一の実施例の性能特性(つまり、精度)について議論する。第四の部分においては、本発明の方法の他の用途について議論される。

0012

A.概説
図1には、小売店、例えば、スーパーマーケット内での販売(トランザクション)を監視するための集中システムが示されるが、本発明による、限定されたタスクメモリを使用して情報を維持し、この情報に基づいて高バイアスヒストグラム(high-biased histograms)および他のデータ表現を生成する方法は、このようなシステムの中で実施されることを想定される。このシステムは、セットのn個のPOS(point-of-sale)端末105−j、j=1、2、...nを含む。図1のシステムにおいては、POS端末105−jは、スーパーマーケットのチェックアウト通路の所に設置された電子キャッシュレジスタである。各POS端末105−jは、データベースシステム190に接続され、各POS端末105−jの所で実行された販売(トランザクション)に関する情報がシステム190に入力される。

0013

データベースシステム190は、プロセッサ110とタスクメモリ120を含む。プロセッサ110は、好ましくは、タスクメモリ120内の情報を、POS端末105−jから受信された入力に基づいて更新し、プロセッサ110は、タスクメモリ120に、ユーザからのタスクメモリ120内に蓄積された情報に関する照会に応答してアクセスする。タスクメモリ120は、好ましくは、情報を蓄積するための媒体、例えば、フロッピーディスクハードドライブランダムアクセスメモリ、その他を使用して実現される。データベースシステムは、さらに、好ましくは、他の要素、例えば、メモリ130、キーボード140(ユーザからの照会を入力するために使用)、およびディスプレイ150(タスクメモリ120から生成された情報の表現を表示するために使用)を含む。プロセッサ110、タスクメモリ120、メモリ130、キーボード140およびディスプレイ150は、互いにバス160によって接続される。データベースシステム190は、パーソナルコンピュータおよび適当な周辺デバイスを使用して実現される。本発明は、分散システム内において実施することもできるが、この場合、分散システムの要素(例えば、メモリおよびプロセッサ)は互いにネットワーク化される。

0014

図2は、本発明のデータ表現(例えば、高バイアスヒストグラム)を生成するために使用される、情報を限定されたメモリ(例えば、タスクメモリ120)内に維持するための方法におけるステップ解説する。メモリを限定する動機としては、データベースシステムのコストを削減すること、および/あるいはデータベースシステムがユーザからの照会に応答する速度を増加することがある。前述のように、限定されたメモリ内に高バイアスヒストグラムを維持することの困難さは、(例えば、予想に反して良く売れた商品を識別(検出)することの失敗による)不正確さの問題である。本発明による方法は、この困難を、情報を、ある閾値の関数である確率にて、蓄積することによって克服する。つまり、この閾値が入って来る情報に対する“確率フィルタ(probabilistic filter)”として機能し、この閾値の関数である確率にて、情報が蓄積される。つまり、この確率フィルタをパスした情報が蓄積されることとなる。この閾値を適当に選択することによって、良く売れる項目(例えば、最近急に売れだした項目)が、高い信頼性にて、識別(検出)されることが保証される。

0015

図2は、本発明の方法におけるステップを示す。データベースが、複数の項目と関連する情報(例えば、複数の項目と、それらと関連する数量のテーブルあるいはリスト)を含むものと想定する。ステップ210において、ある項目(商品)と関連する情報(例えば、その項目の新たな販売と関連する情報)が受信される。ステップ220において、その項目と関連する情報が、既にテーブル内に存在するか決定される。その項目と関連する情報がテーブル内に存在する場合は、ステップ230において、単に、(項目)vと関連する情報が更新される(例えば、数量がその新たな販売数を反映するように更新される)。その項目と関連する情報がテーブル内に存在しない場合は、ステップ240において、その項目と関連する情報が、閾値τに基づく確率にて(確率フィルタを使用して)テーブル内に入れられる。データテーブル内に情報を入れるか否かの決定の実現(つまり、確率フィルタリングの結果の決定)は、(例えば、多くのコンピュータで利用できる)乱数発生関数を使用して、0から1までの間の数xを生成することによって行なわれる。生成された数が1/τより大きな場合は、情報はテーブル内に入力されない。生成された数が1/τより小さな場合は、情報は、テーブル内に入力される。

0016

本発明の具体例を、上記のスーパーケットの例の背景にて説明する。例えば、閾値τが、好ましくは、1/1000に設定されるものと想定する。ある項目の販売に関する新たな情報がPOS端末から到着すると、その項目と関連する情報が既にテーブル内に存在する場合は、販売数量がこの新たな情報に基づいて修正される(つまり、1だけ増加される)。一方、この項目と関連する情報がテーブル内に存在しない場合は、この新たな情報は、1/1000の確率にて(1/1000の確率フィルタリングを使用して)、テーブル内に加えられる。直観的に、ある項目は、それが1000回出現した後に、それと関連する情報をテーブル内に加えられることを理解できる。そして、新たな情報の項目がテーブル内に入力される場合、その項目の数量については、好ましくは、閾値の関数としてセットされる。つまり、ここでは、この数量は、1000にセットされる。こうして、上位から3つの項目以外の数量は当初は記録されないが、この閾値を使用して、新たに加えられた項目に対する数量を指定することができる。

0017

B.本発明の実施例
方法1:閾値を固定し、タスクメモリの使用量を動的に調節する方法
本発明のこの実施例においては、閾値以上の概算の数量(販売量)を持つ全ての項目に関する情報が高信頼度にて維持され、これら最も高い概算数量を持つ項目と関連する情報から、高バイアスヒストグラムが生成される。この第一の実施例における、ある項目をタスクメモリ内に加えるための閾値は、τと呼ばれ、τは固定される。一方、タスクメモリのサイズMは、タスクメモリに加えられるように選択された項目と関連する全ての情報が収容できるように、動的に調節される。閾値を高く設定するとによって、要求されるメモリサイズMを、小さくすることができる。

0018

本発明の第一の実施例におけるステップが図3に示される。ステップ305において、項目vと関連する情報が、(好ましくは、データベースシステムの所で)受信される。より具体的には、この情報が、項目vの販売を示すケースについて考える。ステップ310において、タスクメモリがチェックされ、項目vと関連する情報がタスクメモリ内に既に存在するか調べられる。存在する場合は、単に、ステップ320において、タスクメモリ内の情報が受信された情報に基づいて更新される(例えば、項目vと関連する数量が増加される)。一方、項目vと関連する情報がタスクメモリ内に存在しない場合は、ステップ330において、vと関連する情報をタスクメモリに加えるべきか否かの決定が行なわれる。より具体的には、vと関連する情報が、タスクメモリ内に、確率1/τにて(1/τの確率フィルタリングを使用して)、加えられる。加える判定が成功である場合(つまり、関連する情報が1/τの確率を持つ場合)は、ステップ340において、情報が加えられる。好ましくは、このτの値は、この方法の動作を通じて固定される。失敗の場合は、情報は無視され、タスクメモリは変更されない(つまり、ステップ330における判定の“否定”の枝が取られる)。成功の場合は、ステップ340において、項目と関連する情報を使用してタスクメモリが更新される。より具体的には、好ましくは、ステップ350において、この新たな項目と関連する概算の数量が1+c’に選択あるいは調節される。ここで、c’=0.418τ−1とされる(後に説明)。この新たな数量は、情報をタスクメモリに入れるためのそれ以前の不成功の試みに対する補償として機能する。新たな項目と関連する情報が入力されると、タスクメモリ内の項目の数Mが1だけ増加される。

0019

上記の特定の例においては、タスクメモリ内に入力される情報の結果として、項目の販売の発生数が、1だけ増加するケースについて考えた。より一般的なシナリオ(この場合も図3のステップに従う)においては、タスクメモリ内への情報の各更新の結果として、特定の項目の販売数が、より大きく増加される(つまり、更新が、項目の一個の販売ではなく、項目の複数個の販売を反映するようにされる)。例えば、タスクメモリの販売量の更新を、項目番号xと、数量wとの両方から構成し、更新が、項目番号xに対して、w項目(数量)だけ売れたことを示すようにされる。このシナリオは加重更新シナリオ(weighted updates scenario)であり、この場合、数量は、重みである。

0020

重み(つまり、数量)wを持つ加重更新は、重み1のw個の更新として扱うことができる。ただし、wが大きい場合は、このアプローチは低速となる。つまり、加重更新をw個の別個の更新として扱う方法においては、最高、w回の一連の確率フィルタリングが遂行され、その後に初めて、ある値が、タスクメモリ内に入力されることになるか、場合によっては、タスクメモリに情報を加えようとするこれら全てのw回の試みが失敗に終わることとなる。従って、一度の判定ステップあるいは一度の確率フィルタリングステップのみを遂行し、しかも、タスクメモリ内に情報が入力される確率が、あたかもw回の試みが遂行された場合と同一となるような方法が要望される。より具体的には、項目と関連する情報がタスクメモリ内に存在せず、閾値τが固定された場合の、w回の試行における情報の挿入されない確率は以下のようになる:

0021

ステップ360において、タスクメモリ内の情報に基づいてデータ表現、例えば、高バイアスヒストグラムを生成するか否か決定される。一連の情報が到達した後に、タスクメモリのM個のエントリと関連して、値(項目)および概算の数量が存在するものと想定する。固定された閾値τに対して、概算の数量が相対的に高くなればなるほど、より正確な値が得られる。(ステップ370において)M’<M個の項目に対する高バイアスヒストグラムがタスクメモリから、つまり、データメモリ内に蓄積された最も高い概算数量を持つM’個の項目に対する識別を持つ情報から、これら概算数量が少なくともτに等しいという前提の下で生成される。τ以上の最も高い概算数量を持つ項目が存在しない場合は、好ましくは、タスクメモリは、この情報に基づいて、どの項目も4τ−c’+1=3.582τ以上の数量を持たないことを報告する。この方法は、(後に示される分析に基づいて)95%の信頼度にて正しいと言える。

0022

方法2:タスクメモリの割当てを固定し、閾値を動的に調節する方法
上記の第一の実施例のアプローチは、本発明の方法の第二の実施例の基礎となるが、本発明の第二の実施例においては、最も良く売れる項目とそれらの概算数量の概算高バイアスヒストグラムが、指定された量以下のメモリを使用して、タスクメモリ内に維持された情報から生成される(例えば、メモリの割当てが固定され、あるいは、固定されたサイズのデータベースを用いて、ある最大限の情報が維持される)。閾値が、タスクメモリのサイズが指定された限度を超えないことを確保するために、必要に応じて動的に調節される。この実施例においては、最高M個までのエントリのタスクメモリに対するメモリのブロックが提供され、ここで、Mは、固定される。

0023

図4は、本発明の第二の実施例におけるステップを示す。タスクメモリ内に関連する情報を持つ全ての項目に対して、観測数量(observed count)が維持される。この観測数量は、項目と関連する情報が最初からタスクメモリ内に挿入されるために、重みの総和である(つまり、これは、上で議論された補償c’は含まない)。この方法においても、閾値が固定される場合(上の方法1の場合)と同様に、ステップ405−415が遂行される。ただし、いったんタスクメモリが一杯になると、別の情報を加えるために、どの情報を除去すべきか、決定することが必要となる(例えば、予測されなかった傾向を検出することが必要になる)。

0024

こうして、この方法は、ステップ420において、ある項目と関連する受信された情報をタスクメモリ内に加えるべきか否かを決定する。この決定は、(好ましくは、上に説明の乱数発生関数を使用して)、成功の確率が1/τとなるようにして行なわれる。ここで、τは、現在の閾値である。情報を加えないことが決定された場合は、ステップ480(後に説明)が実行される。情報を加えるべきである場合は、ステップ430において、タスクメモリが、指定された限度を超えないことを保証するためのチェックが行なわれる。タスクメモリが一杯でない場合は、受信された情報が追加され(ステップ440)、次に、ステップ480が実行される。ただし、タスクメモリが一杯である場合は、現在の閾値がステップ450において調節される。ステップ460において、本発明のこの方法においては、項目と関連するどの情報をタスクメモリから除去あるいは削除すべきかが決定される。この決定は、(調節された)現在の閾値に基づいて行なわれる。

0025

どの情報を除去すべきかを決定するための一つの技法は、現在の閾値を、タスクメモリ内の最後から二番目に低い数量を持つ項目と関連する数量に基づいて更新し、最も低い数量を持つ項目と関連する情報を削除する方法である。この方法は、単純ではあるが、この方法では、項目間の依存性が生成され、結果として、ヒストグラムの精度が落ちることとなる。これは、更新された閾値が、後の項目と関連する情報にのみ適用されるために起こる。つまり、閾値が上げられるに従って、後の項目と関連する情報は、タスクメモリに挿入されるのがますます困難となり、一方、閾値が低い時点でタスクメモリ内に入力された情報は、最低の数量とならない限りとどまることとなる。

0026

本発明の方法において、全ての情報を、それが受信された順番と無関係に、より一様に扱うために、タスクメモリ内の全ての項目と関連する情報に対して、好ましくは、閾値が調節されるたびに、ステップ460において、確率フィリタリングが適用される。より具体的には、タスクメモリ内の情報に対して割当てられたメモリが一杯になるたびに、好ましくは、ステップ450において、閾値が調節される。つまり、タスクメモリ内の各項目と関連する全ての情報が調べられ、調節された閾値の関数としてのある成功のバイアスあるいは確率(p’v、後に定義)にて(確率フィルタリングを使用して)、各項目vと関連する情報がタスクメモリ内に保持される。このバイアスは、各項目と関連する情報が、その項目の数量に基づく適当な確率にて、タスクメモリ内に残されるあるいは削除されることを保証する。

0027

タスクメモリが初めて一杯になり、閾値が、本発明の好ましい方法に従って上げられるものと想定する。τ1が初期の閾値であり、τ2が新たな閾値であるものとする。タスクメモリ内の項目vと関連する全ての情報は、以下の成功の確率にて(確率フィルタリングを使用して)選択され、タスクメモリ内に入れられることとなる:

0028

一般的に、本発明の方法は、タスクメモリ内の各エントリに対して成功の確率p’vの追跡を行なう。本発明の方法においては、閾値が、τiからτi+1に上げられるが、このとき、各項目vと関連する情報は、タスクメモリ内に、以下の成功の確率にて維持される:

0029

本発明に対する各閾値τ1、τ2...τkを選択する方法には柔軟性がある(例えば、閾値は、各回ごとに固定されたパーセント量だけ増加することも、あるいは閾値をより低い数量の項目と関連する数量の関数として増加することもできる)。目標は、タスクメモリが結果としてほぼ一杯となるように閾値を選択することにある:閾値が大き過ぎる場合は、小量の情報を除いて全てが削除されることとなり、一方、閾値が小さすぎる場合は、タスクメモリがすぐに一杯になり、追加のフィリタリングがすぐに必要となることとなる。(最初に一杯になった後)本発明の方法全体を通じてタスクメモリがほぼ一杯に保たれた場合は、観測数量が累積する機会が与えられ、より高い精度が得られることとなる。事実、観測数量の品質は、典型的には、関連する情報が最後にタスクメモリに移された時点の閾値の大きさに依存する。

0030

一連の情報が到達した後にタスクメモリのM個のエントリ内に複数の観測数量が保持されており、τjが現在の閾値であるものと想定する。タスクメモリ内の情報の表現の生成が要求された場合(つまり、ステップ480の結果が“肯定”である場合)、ステップ490において本発明の方法が実行される。ステップ490において、タスクメモリ内に関連する情報を持つ各項目に対する概算数量が、各観測数量にc’=0.418τjを加えることによって得られる。τjに対して概算数量が相対的に高くなればなるほど結果の精度は上がることとなる。M’<M値に対する高バイアスヒストグラムが、タスクメモリ内の最も高い概算数量を持つM’の値から、これら概算数値がτjを超えないという条件下で、生成される。

0031

C.方法1の分析
このセクションにおいては、量c’の誘導について説明される。この量は、上で使用された観測数量に加えられるべき補償係数であり、これは、その値(数量値)がテーブルに挿入される前にも発生した事実を考慮するために導入される。このセクションにおいては、方法1によって生成される高バイアスヒストグラムの精度についても議論される。

0032

以下の分析においては、到着の順番と無関係に、ヒストグラムの品質性能が保証されることが示される。各項目vに対して、mvを、vに対する実際の(つまり、概算でない完全な)数量であるものと想定する(つまり、値vに対する全ての到着を通じての重さの総和であるものと想定する)。この分析は、以下の望ましい特性が、順番に関係なく、保持されることを示す:

0033

1.人気項目(商品)の値(popular values)がテーブル内に存在する:つまり、実際の数量、mv≧ατ(ここで、α>0)を持つ全ての値(項目)が、少なくとも

0034

2.人気項目の値の概算数量が非常に正確である:つまり、実際の数量、mvを持つ任意の値(項目)vの概算数量は、全てのα>0に対して、[mv−ατからmv+0.418τ−1]の範囲に、少なくとも

0035

3.不人気項目の値(unpopular values)は、テーブル内に存在しないか、あるいは小さな概算数量を持つ。少なくともατ(ここで、α≧1)の概算数量を持つ全ての値(項目)は、実際の数量、mv>(α−0.418)τを持つ。従って、実際の数量、mv≦0.582τを持つどんな値(項目)も、τ以上の概算数量を持つことはない。

0036

次に、分析に移るが、ある与えられたエントリ閾値τに対して、ある項目は、それがテーブル内に挿入される前に、τ回観測されたことが期待される。目標は、これら“記録されなかった”発生を、観測数量に、ある補償係数c’を加え、高品質のヒストグラムが得られるような方法にて、考慮することである。

0037

全ての新たな項目がある項目の一つの新たな発生に対応し(つまり、全ての重みが1であり)、閾値が固定される場合のシナリオについて考える。各項目vに対して、mv≧1を、その発生の回数であるものとする。この場合、閾値が固定されたアルゴリズムを使用して、テーブル内に、それと関連する情報を持たない各項目が、1/τの確率にて(確率フィルタリングを使用して)加えられる。項目vと関連する情報がテーブル内に初めて挿入されたとき、ある数量が割当てられるが、これは、1に、後に定義される補償値c’=c’(τ)を加えた値とされる。この数量は、その後、項目vが発生するたびに1だけ増分される。

0038

cvを、vに対する観測数量、つまり、vの、テーブル内にvと関連する情報を入力することとなったvの発生後のこの発生も含む数量であるものと想定する。Estvを、vの最後の発生の後のvの概算数量;つまり、Estv=c’+cvであるものとする。この値c’が、Estvがmvと近付くように選択される。より詳細には、Eが、期待される値の演算子であるものとすると、

0039

q=1−1/τとし、mv≧2であるものと想定する。(mv=1の場合は、単純である。)すると、

0040

こうして、E(Estv|vテーブル内)=mvを得るためには、以下が要求される:

0041

c’はmvに依存し、mvは未知であるため、c’は、mv=τの時に完全に補償するように、以下のように選択される:

0042

c’のこの値は、本発明の方法における、重さが任意とされ、閾値が調節されるシナリオに対する発見的アルゴリズム(heuristic)として使用される。後者のケースにおいては、c’は、単に概算数量を計算するために観測数量に加えるために使用され、ヒストグラムを維持するための手続きの一部分としては使用されない。τkが、概算数量が計算される時点での現在の閾値であるものとすると、c’−0.418・τk−1となる。

0043

次に、本発明の方法の第一の実施例の性能保証について考える。第一の補助定理は、人気品目の値が、方法1の実施例の全ての時点においてテーブル内に存在する可能性を示す。前述のように、到着する項目は正の整数の重みを持ち、項目vの実際の数量、mvは、これら重みの総和であるものとする。

0044

補助定理1 方法1の実施例について考え、τは、閾値を表すものとする。現在までの実際の数量がmv≧α・τ(ここでα>0)である全ての項目vは、確率

0045

証明:kが、現在までの値vを持つ項目の数であり、w1、w2,...、wkがこれらの発生と関連する重みであるものとする。すると、Σki=1wi=mvである。vがテーブル内に挿入されない確率は、

0046

補助定理2 方法1の実施例を考え、τが閾値を表すものと想定する。Estvが、現在までの実際の数量がmvである項目の概算数量であるものとする。すると、全てのα>0に対して、Estv∈[mv−α・τ、mv+.418・τ−1]となることが、

0047

証明:cvがvに対する観測数量を表すものとする。Estvに対するこの上限は、Estv=cv+c’=cv+.418・τ−1≦mv+.418・τ−1であるという事実から言える。下限については、補助定理1は、

0048

必然的な結論(系)1 方法1の実施例を考え、τが閾値を表すものとする。Estvが、項目vの概算数量であるものとすると、実際の数量は、95%の確率にて、[Estv−.418・τ+1、Estv+2.582・τ]の範囲内に入ることがいえる。

0049

D.結論
本発明は、データ表現、例えば、高バイアスヒストグラムを生成するために使用される情報を維持するための方法および装置について開示する。この方法においては、確率的フィルタリング技術を使用して、タスクメモリ内に加えられるべき情報が選択され、こうして選択された情報を使用して、情報と関連する全ての数量を明示的に(正確に)追跡することなく、高バイアスヒストグラム(テーブル)が生成される。本発明の方法の第一の実施例においては、ある固定された閾値より高い数量を持つ全ての項目と関連する情報が、ヒストグラム内に、高い確率にて表現される。この第一の実施例に対するメモリ要件は、閾値を満足する項目の数に依存する。第二の実施例は、第一の実施例を基礎とする。第二の実施例においては、高バイアスヒストグラムが、固定された量のメモリにて維持される。第二の実施例においては、項目を入力するための閾値が調節され、タスクメモリが固定された量に維持される。本発明の方法は、他の用途、例えば、数量に対するバイアスが、より最近入力され更新された情報に対して、与えられるような高バイアスヒストグラムの生成にも適用することがきる。

0050

開示される方法の説明に当たって、具体的なハードウエアおよびソフトウエアには触れられなかったが、当業者においては、本発明の上の説明から、特定の用途に対して利用できる、あるいは好ましいと考えられる、ハードウエアおよびソフトウエアを容易に設計できるものである。

図面の簡単な説明

0051

図1本発明が中で実現されるシステムを示す図である。
図2本発明の方法におけるステップを示す図である。
図3本発明の方法の第一の実施例におけるステップを示す図である。
図4本発明の方法の第二の実施例におけるステップを示す図である。

--

0052

105−1,2POS端末
110プロセッサ
120タスクメモリ
130主メモリ
140キーボード
150ディスプレイ
160バス
190 データベースシステム

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ