(57)【要約】  本明細書で開示されるのは、ビッグデータの問合せをして、問合せの結果を表示するための装置、非一時的なコンピュータ読み取り可能な媒体及び方法である。検索の線形性を低下させるために、複数のレベルのデータ構造の階層が特定の日と関連付けられる。問合せの結果を受けるクライアントは、連結リストに結果の記録と一致する記録の形式で問合せの結果を保存する。クライアントは、全ての結果が受信されるまで、グラフィカルユーザインタフェースを問合せの結果で周期的に更新することも行う。【選択図】図１
2021532450.tif 000002
【特許請求の範囲】
【請求項１】
メモリと、
相互に連結されたデータ構造の階層と、ハッシュテーブルであって、当該ハッシュテーブルにおけるエントリが、日と前記相互に連結されたデータ構造の階層における第１のデータ構造との間の関連を含むような、ハッシュテーブルとを含む、索引を前記メモリに生成し、
リモートデバイスから、前記日を含む複数の検索パラメータを有する、検索要求を受け、
前記日を用いて、前記相互に連結されたデータ構造の階層における前記第１のデータ構造のメモリアドレスがあるかについて、前記ハッシュテーブルを検索し、
前記検索パラメータに基づいて前記相互に連結されたデータ構造をトラバースするための計画を判別し、
前記トラバースの計画に従った前記第１のデータ構造における前記検索要求によって求められているデータの検索を開始し、
前記リモートデバイスに前記検索の結果を返す、
少なくとも１つのプロセッサと、
を備える、
装置。
【請求項２】
前記トラバースの計画を判別するように、前記検索要求によって求められている前記データを取得するために、前記階層をトラバースすべき深さを判別するように、前記少なくとも１つのプロセッサが更に構成されている、
請求項１に記載の装置。
【請求項３】
前記第１のデータ構造は、前記相互に連結されたデータ構造の階層における第１のレベルにある、
請求項１に記載の装置。
【請求項４】
前記第１のデータ構造は、第１の二分木のデータ構造である、
請求項３に記載の装置。
【請求項５】
前記少なくとも１つのプロセッサは、前記第１の二分木のデータ構造の各ノードにおいて、前記階層における第２のレベルに属する第２のデータ構造へのポインタを生成するように更に構成されている、
請求項４に記載の装置。
【請求項６】
前記第２のデータ構造は、ベクトルのデータ構造である、
請求項５に記載の装置。
【請求項７】
前記第２のデータ構造は、第２の二分木のデータ構造である、
請求項５に記載の装置。
【請求項８】
前記少なくとも１つのプロセッサは、前記第２の二分木のデータ構造の各ノードにおいて、前記階層における第３のレベルに属する第３のデータ構造へのポインタを生成するように更に構成されている、
請求項７に記載の装置。
【請求項９】
少なくとも１つのプロセッサによって、相互に連結されたデータ構造の階層と、ハッシュテーブルであって、当該ハッシュテーブルにおけるエントリが、日と前記相互に連結されたデータ構造の階層における第１のデータ構造との間の関連を含むような、ハッシュテーブルとを含む、索引をメモリに生成することと、
前記少なくとも１つのプロセッサによって、リモートデバイスから、前記日を含む複数の検索パラメータを有する、検索要求を受けることと、
前記少なくとも１つのプロセッサによって、前記日を用いて、前記相互に連結されたデータ構造の階層における前記第１のデータ構造のメモリアドレスがあるかについて、前記ハッシュテーブルを検索することと、
前記少なくとも１つのプロセッサによって、前記検索パラメータに基づいて前記相互に連結されたデータ構造をトラバースするための計画を判別することと、
前記少なくとも１つのプロセッサによって、前記トラバースの計画に従った前記第１のデータ構造における前記検索要求によって求められているデータの検索を開始することと、
前記少なくとも１つのプロセッサによって、前記リモートデバイスに前記検索の結果を返すことと、
を含む、
方法。
【請求項１０】
前記トラバースの計画を判別することは、前記少なくとも１つのプロセッサによって、前記検索要求によって求められている前記データを取得するために、前記階層をトラバースすべき深さを判別することを含む、
請求項９に記載の方法。
【請求項１１】
前記第１のデータ構造は、前記相互に連結されたデータ構造の階層における第１のレベルにある、
請求項９に記載の方法。
【請求項１２】
前記第１のデータ構造は、第１の二分木のデータ構造である、
請求項１１に記載の方法。
【請求項１３】
前記少なくとも１つのプロセッサによって、前記第１の二分木のデータ構造の各ノードにおいて、前記階層における第２のレベルに属する第２のデータ構造へのポインタを生成することを更に含む、
請求項１２に記載の方法。
【請求項１４】
前記第２のデータ構造は、ベクトルのデータ構造である、
請求項１２に記載の方法。
【請求項１５】
前記第２のデータ構造は、第２の二分木のデータ構造である、
請求項１４に記載の方法。
【請求項１６】
前記少なくとも１つのプロセッサによって、前記第２の二分木のデータ構造の各ノードにおいて、前記階層における第３のレベルに属する第３のデータ構造へのポインタを生成することを更に含む、
請求項１５に記載の装置。
【請求項１７】
メモリと、
表示デバイスと、
前記表示デバイスにグラフィカルユーザインタフェースをレンダリングし、
リモートサーバに検索要求を伝送し、
前記検索要求に応答して、それぞれの受信される記録の形式が、それぞれの記録に割り当てられたそれぞれのメモリ空間の形式と一致する複数の記録を受信し、
それぞれの受信した記録を個別の割り当てられたメモリ空間に複製し、
前記複数の記録が受信された順序を反映するような順序を示す、前記メモリ空間の連結リストに、それぞれの割り当てられた前記メモリ空間を追加し、
前記検索要求に対応する全てのデータの記録が受信されるまで、現在受信している記録を前記グラフィカルユーザインタフェースに周期的にレンダリングする、
少なくとも１つのプロセッサと、
を備える、
装置。
【請求項１８】
前記少なくとも１つのプロセッサは、所定の期間が満了すると、前記現在受信している記録をレンダリングするように構成されている、
請求項１７に記載の装置。
【請求項１９】
前記少なくとも１つのプロセッサは、
前記グラフィカルユーザインタフェースに表示されている所定のフィールドの選択を検出し、
前記選択に応答して、前記所定のフィールドに対応する集計データを含む別のグラフィカルユーザインタフェースをレンダリングする、
ように更に構成されている、
請求項１７に記載の装置。
【請求項２０】
前記所定の期間は、約１秒である、
請求項１７に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願）
本出願は、２０１８年７月６日に出願された米国特許出願シリアル番号第１６／０２８６４１号の利益を主張し、これにより当該出願の内容が全体としてここで参照によって取り込まれる。
【背景技術】
【０００２】
（背景）
現在のコンピュータ計算デバイス及びアプリケーションは、重大な決定、予測分析、ビジネスインテリジェンス等のために使われ得る圧倒的な量のデータ（「ビッグデータ」）を生成する。このようなデバイス及びアプリケーションは、センサ、携帯電話、ラップトップ及びソーシャルネットワーキングアプリケーションを含んでいてもよいが、これらに限られるものではない。幸運にも、データストレージのコストは低下してきた。
【図面の簡単な説明】
【０００３】
【図１】図１は、この開示の複数の観点に従った例示システムである。
【図２】図２は、この開示の複数の観点に従った例示フロー図である。
【図３】図３から３Ｄは、この開示の複数の観点に従った実例を描いたものである。
【図３Ａ】図３から３Ｄは、この開示の複数の観点に従った実例を描いたものである。
【図３Ｂ】図３から３Ｄは、この開示の複数の観点に従った実例を描いたものである。
【図３Ｃ】図３から３Ｄは、この開示の複数の観点に従った実例を描いたものである。
【図３Ｄ】図３から３Ｄは、この開示の複数の観点に従った実例を描いたものである。
【図４】図４は、本開示の複数の観点に従った別の例示フロー図である。
【図５】図５から５Ｂは、本開示の複数の観点に従った更なる例示フロー図である。
【図５Ａ】図５から５Ｂは、本開示の複数の観点に従った更なる例示フロー図である。
【図５Ｂ】図５から５Ｂは、本開示の複数の観点に従った更なる例示フロー図である。
【発明を実施するための形態】
【０００４】
ビッグデータは多数の利益を提供するが、効率的な方法でこのようなデータを処理することは、終わりのない挑戦である。伝統的なデータ処理は、ビッグデータの集合の複雑さと量に対処することができない。その結果、ビッグデータを扱う多数の異なる解決法が進化し、多数のデータベースの索引が設計されてきた。場合によっては、特定の問合せがごく一般的である。例えば、ユーザは、特定の日に起こるトランザクションを度々検索する。このような問合せの高度な知識がある程度あるにもかかわらず、それに応じてデータ索引は整理されていない。クライアント側では、結果自体も大きく、かつ、複雑であるため、大きなデータ問合せの結果を受け取ることと表示することも挑戦的であり得る。これは、ユーザが彼らのグラフィカルユーザインタフェース（「ＧＵＩ」）から遅い応答を経験することにつながるであろう。
【０００５】
上述したことを考慮して、ビッグデータの集合の問合せ及び表示のための装置、非一時的なコンピュータ読み取り可能な媒体及び方法が本明細書において開示される。本明細書において開示される技術は、コンピュータがより効率的な方法でビッグデータの集合を問い合わせて、かつ、表示することを可能にすることにより、コンピュータの性能を向上させる。次に、ユーザはＧＵＩ上の遅延を少ししか経験せずに、データベース上に載せられた負荷は軽減され得る。
【０００６】
一例において、装置は、メモリと以下の動作を実行する少なくとも１つのプロセッサを備え得る。少なくとも１つのプロセッサは、相互に連結されたデータ構造の階層と、ハッシュテーブルであって、ハッシュテーブルにおけるエントリが、日と相互に連結されたデータ構造の階層における第１のデータ構造との間の関連を含むような、ハッシュテーブルとを含む、索引をメモリに生成し、リモートデバイスから、日を含む複数の検索パラメータを有する、検索要求を受け、日を用いて、相互に連結されたデータ構造の階層における第１のデータ構造のメモリアドレスがあるかについて、ハッシュテーブルを検索し、検索パラメータに基づいて相互に連結されたデータ構造をトラバースするための計画を判別し、トラバースの計画に従った第１のデータ構造における検索要求によって求められているデータの検索を開始し、リモートデバイスに検索の結果を返す。
【０００７】
更なる例において、方法が開示される。方法は、少なくとも１つのプロセッサによって、相互に連結されたデータ構造の階層と、ハッシュテーブルであって、ハッシュテーブルにおけるエントリが、日と相互に連結されたデータ構造の階層における第１のデータ構造との間の関連を含むような、ハッシュテーブルとを含む、索引をメモリに生成することと、少なくとも１つのプロセッサによって、リモートデバイスから、日を含む複数の検索パラメータを有する、検索要求を受けることと、少なくとも１つのプロセッサによって、日を用いて、相互に連結されたデータ構造の階層における第１のデータ構造のメモリアドレスがあるかについて、ハッシュテーブルを検索することと、少なくとも１つのプロセッサによって、検索パラメータに基づいて相互に連結されたデータ構造をトラバースするための計画を判別することと、少なくとも１つのプロセッサによって、トラバースの計画に従った第１のデータ構造における検索要求によって求められているデータの検索を開始することと、少なくとも１つのプロセッサによって、リモートデバイスに検索の結果を返すことと、を含み得る。
【０００８】
更に別の例において、装置は、メモリと、表示デバイスと、以下の動作を実行する少なくとも１つのプロセッサと、を備え得る。少なくとも１つのプロセッサは、表示デバイスにグラフィカルユーザインタフェースをレンダリングし、リモートサーバに検索要求を伝送し、検索要求に応答して、それぞれの受信される記録の形式が、それぞれの記録に割り当てられたそれぞれのメモリ空間の形式と一致する複数の記録を受信し、それぞれの受信した記録を個別の割り当てられたメモリ空間に複製し、複数の記録が受信された順序を反映するような順序を示す、メモリ空間の連結リストに、それぞれの割り当てられたメモリ空間を追加し、検索要求に対応する全てのデータの記録が受信されるまで、現在受信している記録をグラフィカルユーザインタフェースに周期的にレンダリングする。
【０００９】
以下の例の説明及び付属する図を参照して考慮すると、本開示の複数の観点、特徴及び利点が理解される。以下の説明は、応用を限定するものではなく、この開示の範囲は添付の請求の範囲及びそれらと均等のものによって定義される。
【００１０】
（詳細な説明）
図１は本開示の動作を実行するための例示的なシステム１００の概略図を示す。コンピュータ装置１０１、１１２、１１６及び１１８は、それぞれ命令を処理し、かつ、他のコンピュータにデータを伝送し、他のコンピュータからデータの伝送を受けることができるデバイスを含んでいてもよい。図１の例において、コンピュータ装置１０１は、索引１０３として調整された大きなデータリポジトリを含むサーバコンピュータであってもよい。コンピュータ装置１１２、１１６及び１１８は、コンピュータ装置１０１からデータを問い合わせ、問合せの結果を表示するためのクライアントコンピュータであってもよい。図１に示したそれぞれの装置は、コンピュータに関連して通常用いられる全ての部品を含んでいてもよい。例えば、それぞれがキーボードとマウス、及び／又は、ペン入力、ジョイスティック、ボタン、タッチスクリーン等の様々な他の種類の入力デバイス、並びに、例えば、ＣＲＴ、ＬＣＤ、プラズマスクリーンモニタ、ＴＶ、プロジェクタ等を含み得るディスプレイ１１４を有し得る。
【００１１】
図１に示したそれぞれのコンピュータ装置は、インテル（登録商標）コーポレーションから販売されているプロセッサなどの、少なくとも１つのプロセッサ１０２を備えていてもよく、それは、既知の任意のプロセッサの数であってもよい。別の例においては、プロセッサ１０２は、特定用途向け集積回路（「ＡＳＩＣ」）であり得る。各コンピュータは、プロセッサ１０２によって取得され、実行され得る命令を保持するメモリ１０４を備えていてもよい。上述したように、コンピュータ装置１０１のメモリ１０４は、索引１０３を保持してもよい。以下で更に詳細に説明されるように、索引１０３は、特定の日に生じるデータに対する問合せを最適化する特定の方法で整理されたデータベースであり得る。一例において、メモリ１０４は、ランダムアクセスメモリ（「ＲＡＭ」）デバイスであり得る。更なる例において、メモリ１０４は、デュアル・インライン・メモリ・モジュール（「ＤＩＭＭ」）として整理された複数のメモリセグメントに分割され得る。また、メモリ１０４は、非一時的なコンピュータ読み取り可能な媒体などの他の種類のデバイスを含み得る。非一時的なコンピュータ読み取り可能な媒体は、多数の物理メディア（例えば、電子的、磁気的、光学的、電磁気的又は半導体の媒体）のうちの任意のものを含み得る。適切な非一時的なコンピュータ読み取り可能な媒体のより具体的な例は、フロッピーディスク又はハードドライブなどの移動可能な磁気的コンピュータディスク、読み取り専用メモリ（「ＲＯＭ」）、消去可能なプログラム可能な読み取り専用メモリ、移動可能なコンパクトディスクまたはコンピュータ装置に直接に又は間接に結合され得る他のストレージデバイスを含むが、これらに限定されるものではない。メモリ１０４は、上記の１つ以上及び／又は他のデバイスの任意の組合せも含んでいてよい。各コンピュータ装置の全ての構成要素は同一のブロック内にあるように機能的に説明されているが、構成要素は同一の物理的なハウジング内に保持されていてもされていなくてもよいことが理解される。
【００１２】
図１に示した複数のコンピュータは、ネットワークインタフェース１０８を用いたネットワークを介して互いに接続されていてもよい。ネットワークは、ローカルエリアネットワーク（「ＬＡＮ」）、ワイドエリアネットワーク（「ＷＡＮ」）、インターネット等であってもよい。ネットワークインタフェース１０８は、仮想プライベートネットワーク、ローカルイーサネットのネットワーク、１つ以上の会社に独自の通信プロトコルを利用するプライベートネットワーク、セルラー及びワイヤレスのネットワーク、ＨＴＴＰ、及びこれらの様々な組合せを含む様々なプロトコルを利用してもよい。本明細書においては少数のコンピュータしか描かれないが、ネットワークが追加的な相互に接続されたコンピュータを含んでいてもよいことが理解されるべきである。
【００１３】
上述したように、メモリ１０４に存在する命令はプロセッサ１０２によって取得され、実行されてもよい。これらの命令はプロセッサ１０２によって直接に（機械語など）、又は間接に（スクリプトなど）実行されるべき命令の任意の集合を含んでいてもよい。この点について、「命令」、「スクリプト」又は「モジュール」という語は、本明細書において、交換可能に用いられ得る。コンピュータ実行可能命令は、オブジェクトコード又はソースコードのモジュールなどで、任意のコンピュータ言語又は形式で保存され得る。さらに、命令はハードウェア、ソフトウェアまたはハードウェアとソフトウェアの組合せの形式で実装されてもよく、本明細書における例は単なる例示であることを理解されたい。
【００１４】
本明細書の技術に従った１つの動作例が図２から３Ｄに示されている。具体的には、図２は、問合せに応答するための例示の方法２００のフロー図を説明している。図３から３Ｄは、対応する動作例を示している。図３から３Ｄに示されている動作は、以下、図２のフロー図に関して説明される。
【００１５】
図２を参照して、ブロック２０２に示されているように、少なくとも１つのプロセッサがメモリに相互に連結されたデータ構造の階層を生成し得る。相互に連結されたデータ構造の階層は、データベースの索引の一部であってもよく、二分木のデータ構造、連結リストのデータ構造、ベクトルのデータ構造等を含んでいてもよいが、それらに限定されるものではない。更に詳細に説明されるように、階層の所定のレベルにおけるデータ構造の各ノードは、次のレベルの第２のデータ構造における対応するノードへのポインタを含んでいてもよい。
【００１６】
次にブロック２０４を参照して、少なくとも１つのプロセッサは、メモリにハッシュテーブルを生成し得る。ハッシュテーブルは索引の別の観点であり得る。一例において、ハッシュテーブルにおける各エントリは、日と相互に連結されたデータ構造の階層の第１のデータ構造との間の関連を有し得る。次に図３を参照して、説明のためのハッシュテーブル３０２が示されている。ハッシュテーブル３０２は、日３０４（即ち、２０１７年７月２０日）とデータ構造３０８との関連とデータ構造３１０との日３０６（即ち、２０１６年２月２日）の関連を示す。図３の例において、データ構造３０８とデータ構造３１０は、二分探索木（「ＢＳＴ」）である。さらに、データ構造３０８とデータ構造３１０は、それぞれのデータ構造の階層において、それぞれ第１のデータ構造であり得る。説明のためのハッシュテーブル３０２は、日を有する問合せがその日に関連するデータに効率的にマッピングされることを可能にする。データ構造３０８／３１０は、それぞれ問合せによって求められているデータにつながる階層の第１のレベルにあり、その求められているデータは、第１のレベルにおいて見つかり得る。以下で更に詳細に説明されるように、二分木を第１の層として用いることの利点は、二分木がデータにおける構造的な関係を反映し得ることである。構造的な関係は、コンピュータが要求されたデータを見つけるためにかかる時間を削減し得る。
【００１７】
図２に戻って参照して、少なくとも１つのプロセッサは、ブロック２０６に示されているように、リモートデバイスから検索要求を受け得る。検索要求は、日と複数の他の検索パラメータを含み得る。ブロック２０８において、少なくとも１つのプロセッサは、日を用いて、データ構造の階層の第１のデータ構造の関連付けられたメモリアドレスがあるかについて、ハッシュテーブル（例えば、ハッシュテーブル３０２）を検索し得る。ブロック２１０において、コンピュータの少なくとも１つのプロセッサは、検索パラメータに基づいて、相互に連結されたデータ構造の階層をトラバースするための計画を判別し得る。一例において、トラバースの計画は、検索パラメータに基づいて、求められているデータが見つかるであろう階層における深さを判別することを含み得る。少なくとも１つのプロセッサは、ブロック２１２に示されているように、階層の第１のデータ構造において求められているデータの検索を開始し得る。
【００１８】
次に図３Ａを参照して、データ構造３０８の詳細な説明が示される。例として、データは、金融商品のトランザクションを含み得て、問合せによって求められているデータは、全て２０１７年７月２０日に銘柄記号「ＴＴＴ」に対して実行された全ての取引のトランザクションである。図３に示されているように、２０１７年７月２０日という日は、データ構造３０８にマッピングされている。図３ＡのＢＳＴは７つのノード３１２、３１４、３１６、３１８、３２０、３２２及び３２４しか含まないが、ビッグデータの環境におけるＢＳＴは遙かに多数のノードを有しており、図３Ａには説明を容易にするため、少数のノードが示されていることが理解される。この例における各メモリノードは、銘柄記号を保持する。ルートノード３１２は、銘柄記号「ＭＭＭ」を含み、ルートノード３１２の左から分岐するノードはアルファベット順で「ＭＭＭ」より小さい一方、右側から分岐するノードはアルファベット順で「ＭＭＭ」より大きい。少なくとも１つのプロセッサは、「ＴＴＴ」記号を検索する途中で、比較をしながらＢＳＴをルートから葉までトラバースし得る。平均して、プロセッサが木の約半分をスキップすることを、それぞれの比較が可能にするように、ＢＳＴは整理されている。このようにして、記号を調べるためにかかる時間は、木に保持されている項目の数の対数に比例し得て、これは、線形探索よりも効率的である。
【００１９】
ＢＳＴ３０８は、この例において、データ構造の階層における第１のデータ構造であり得る。図３Ａに示されているＢＳＴにおける各ノードは、階層における第２のデータ構造へのポインタを含み得る。階層の第１のレベルは、記号を含み得る一方、階層の第２のレベルは、その特定の日の、その記号と関連付けられたトランザクションを含み得る。図３Ａの例においては、ノード３１２は２０１７年７月２０日の記号「ＭＭＭ」に対する全てのトランザクションを含むデータ構造３１２Ａへのポインタを含み、ノード３２０は２０１７年７月２０日の記号「ＴＴＴ」に対する全てのトランザクションを含むデータ構造３２０Ａへのポインタを含み、ノード３１４は２０１７年７月２０日の記号「ＧＧＧ」に対する全てのトランザクションを含むデータ構造３１４Ａへのポインタを含み、ノード３１６は２０１７年７月２０日の記号「ＣＣＣ」に対する全てのトランザクションを含むデータ構造３１６Ａへのポインタを含み、ノード３１８は２０１７年７月２０日の記号「ＪＪＪ」に対する全てのトランザクションを含むデータ構造３１８Ａへのポインタを含み、ノード３２２は２０１７年７月２０日の記号「ＰＰＰ」に対する全てのトランザクションを含むデータ構造３２２Ａへのポインタを含み、ノード３２４は２０１７年７月２０日の記号「ＹＹＹ」に対する全てのトランザクションを含むデータ構造３２４Ａへのポインタを含む。図３Ａの例は、データの２つのレベルしか含まないが、階層は特定の問合せに対応するために必要とされる数のレベルを含み得る。即ち、データは、検索をより線形でないようにするためにより多くのレベルを含んでいてもよい。
【００２０】
次に図３Ｂを参照して、データ構造３２０Ａの詳細な説明が示される。プロセッサは、２０１７年７月２０日の「ＴＴＴ」トランザクションを検索するときに、ＢＳＴのノード３２０に到達し得る。しかし、この動作例においては、第１レベルのデータ構造３０８は記号だけを含んでいる。トランザクションは次のレベルにおいて見つけられ得る。上述したように、データ構造３２０Ａは、階層の第２レベルにあり、２０１７年７月２０日の記号「ＴＴＴ」に対する全てのトランザクションを含んでいる。図３Ｂの例において、データ構造３２０Ａはベクトルのデータ構造であり得る。図３Ｂのベクトルのデータ構造は、２０１７年７月２０日の記号「ＴＴＴ」に対する順序を表す３つのノード３２６、３２８及び３３０を示す。各ノードはそこから分岐し、それぞれの順序に対するトランザクションを表す更なる連結リストを含む。例えば、ノード３２６は、そこから分岐する２つのトランザクション３２６Ａ及び３２６Ｂで順序を表し得て、ノード３２８は、そこから分岐する３つのトランザクション３２８Ａ、３２８Ｂ及び３２８Ｃで順序を表し得て、ノード３３０は、そこから分岐する１つのトランザクションで順序を表し得る。図２の方法に戻って参照して、ブロック２１４に示されているように、問合せの結果が返される。図３Ｂに戻って参照して、ベクトルのデータ構造３２０Ａにおけるデータが、この情報を要求しているデバイスに送り返され得る。この例は順序のためにベクトルのデータ構造を使うが、他の状況においては、配列、連結リスト等の他の種類のデータ構造が使われてもよいことが理解される。
【００２１】
上述したように、最も頻繁に受ける問合せに応じて、データ構造は２レベルより多いデータを含み得る。図３Ｃの例においては、二値のデータ構造３１０がそこから分岐する３レベルとともに示されている。図３においてこれまでに見たように、データ構造３１０はハッシュテーブル３０２における２０１６年２月２日という日と関連付けられている。図３Ｃの説明のための階層は、３層のデータの階層である。具体的には、図３Ｃの例は、顧客を示す記号とトランザクションとの間のレベルを含む。この整理は、特定の顧客による記号トランザクションに対する問合せが一般的である場合に有益であり得る。図３Ｃの例示的な階層において、ノード３３２は記号「ＭＭＭ」、及び、記号「ＭＭＭ」と関わりを持つ顧客を含むデータ構造３３２Ａへのポインタを含み、今度は、データ構造３３２Ａは、顧客による記号「ＭＭＭ」のためのトランザクションを示すトランザクションデータ構造３３２Ｂへのポインタを含む。ノード３４４は、記号「ＧＧＧ」と記号「ＧＧＧ」と関わりを持つ顧客を含むデータ構造３４４Ａへのポインタを含み、今度は、データ構造３４４Ａは、顧客による記号「ＧＧＧ」のためのトランザクションを示すトランザクションデータ構造３４４Ｂへのポインタを含む。ノード３３４は、記号「ＴＴＴ」、及び、記号「ＴＴＴ」と関わりを持つ顧客を含むデータ構造３３４Ａへのポインタを含み、今度は、データ構造３３４Ａは、顧客による記号「ＴＴＴ」のためのトランザクションを示すトランザクションデータ構造３３４Ｂへのポインタを含む。ノード３４２は、記号「ＣＣＣ」、及び、記号「ＣＣＣ」と関わりを持つ顧客を含むデータ構造３４２Ａへのポインタを含み、今度は、データ構造３４２Ａは、顧客による記号「ＣＣＣ」のためのトランザクションを示すトランザクションデータ構造３４２Ｂへのポインタを含む。ノード３４０は、記号「ＪＪＪ」、及び、記号「ＪＪＪ」と関わりを持つ顧客を含むデータ構造３４０Ａへのポインタを含み、今度は、データ構造３４０Ａは、顧客による記号「ＪＪＪ」のためのトランザクションを示すトランザクションデータ構造３４０Ｂへのポインタを含む。ノード３３８は、記号「ＰＰＰ」、及び、記号「ＰＰＰ」と関わりを持つ顧客を含むデータ構造３３８Ａへのポインタを含み、今度は、データ構造３３８Ａは、顧客による記号「ＰＰＰ」のためのトランザクションを示すトランザクションデータ構造３３８Ｂへのポインタを含む。ノード３３６は、記号「ＹＹＹ」、及び、記号「ＹＹＹ」と関わりを持つ顧客を含むデータ構造３３６Ａへのポインタを含み、今度は、データ構造３３６Ａは、顧客による記号「ＹＹＹ」のためのトランザクションを示すトランザクションデータ構造３３６Ｂへのポインタを含む。
【００２２】
次に図３Ｄを参照して、顧客データ構造３３４Ａの詳細な説明が示される。図３Ｃにおいて見たように、「ＴＴＴ」の記号のノード３３４は、ポインタの方法によってデータ構造３３４Ａと関連付けられている。データ構造３３４Ａは、顧客「ＪＰＭｏｒｇａｎ」を含むルートノード３５２、顧客「Ｃｈａｓｅ」を含むノード３５４及び顧客「ＮＦＳＣ」を含むノード３５６を備えるＢＳＴとしても整理され得る。図３Ｃは、トランザクションデータ構造への個別のポインタを含む各顧客ノードも描いている。イベントにおいて、２０１６年２月２日に顧客「Ｃｈａｓｅ」によって行われた「ＴＴＴ」のトランザクションに対する問合せが受信されると、少なくとも１つのプロセッサは、「ＴＴＴ」の記号を含むノード３３４に到達するため、ＢＳＴ構造３１０をまずトラバースし得て、これは、ＢＳＴ構造３３４Ａにつながる。プロセッサは、次に、ノード３５４における顧客「Ｃｈａｓｅ」を見つけるために、ＢＳＴ構造３３４Ａをトラバースし得て、これは、トランザクションデータ構造３３４Ｂにつながる。トランザクションデータ構造３３４Ｂからのデータは、問合せに応じて返され得る。顧客の名前を含む余分なＢＳＴを追加することは、検索をより線形でなくすことにより、特定の日に生じた顧客のトランザクションを検索する効率を改善し得る。
【００２３】
以上で説明した階層は単に例示的なものである。そのようなものとして、階層はデータ構造の異なる組合せを含むことができる。例えば、第１のレベルはＢＳＴであってもよく、第２のレベルは配列であってもよく、第３のレベルは別のＢＳＴであってもよい。特定の階層において用いられたデータ構造の組合せは、最も頻繁に受ける問合せに対応されてもよい。特定のシステムに対する階層は、検索の線形性を減少させるように設計されてもよい。しかし、異なる状況は異なるデータ構造の整理を要求し得る。
【００２４】
ビッグデータの問合せの性能が改善され得る別の領域は、データを要求するクライアントデバイスにある。ビッグデータの問合せの結果を表示する動作例が図４から５Ｂに示される。具体的には、図４は問合せの結果を表示するための例示的な方法４００のフロー図を示し、図５から５Ｂは対応する動作例を示す。図５から５Ｂに示された動作は図４のフロー図との関係で、以下説明される。
【００２５】
図４を参照して、コンピュータ装置の少なくとも１つのプロセッサは、ブロック４０２に示されているように、スクリーンにＧＵＩをレンダリングし、ブロック４０４に示すように、検索要求をリモートサーバに伝送する。ブロック４０６において、少なくとも１つのプロセッサが検索要求に応答して、複数の記録を受信し得て、ブロック４０８において、それぞれの受信した記録が個別の割り当てられたメモリ空間に複製され得る。一例において、それぞれの受信された記録は、それぞれの記録に割り当てられたそれぞれのメモリ空間の形式と一致する。メモリ空間と記録の間の形式を一致させておくことは、少なくとも１つのプロセッサがそれぞれの受信された記録のフィールドをメモリにおける対応するフィールドに効率的に複製することを可能にし得る。そのようなものとして、フィールド、データの種類またはデータのオブジェクトの形式を再設定する必要がないため、得られた記録を処理するための時間が削減され得る。
【００２６】
図５を参照して、コンピュータ装置１０１は、記録をコンピュータ装置１１２に提供するサーバコンピュータであり得て、コンピュータ装置１１２は、要求するクライアントコンピュータであり得る。コンピュータ装置１０１が記録５０２をコンピュータ装置１１２に戻すように示されている。記録は、表示デバイス５０８に表示され得る。
【００２７】
図４に戻って参照して、ブロック４１０に示されているように、それぞれの割り当てられたメモリ空間は、メモリ空間の連結リストに追加され得る。一例において、連結リストの順序は、記録が受信された順序を反映し得る。図５は、メモリ１０４における記録の連結リスト５０４を示す。図４に戻って参照して、ブロック４１２に示されているように、現在受信している記録は、周期的にＧＵＩにレンダリングされ得る。一例において、所定の周期の時間、１秒毎等が経過すると、記録はレンダリングされ得る。周期的にＧＵＩを更新することの利点は、残りの結果がまだ転送中の間に、ユーザが現在受信している結果をまだ確認することができることである。このため、ネットワークの遅延が生じると、ユーザは既にＧＵＩ上で結果を見ることができるので、そのような遅延はユーザから隠され得る。一例において、更新は全ての結果が受信されるまで周期的に続く。
【００２８】
図５Ａを参照して、取引データの問合せの結果を伴う説明のためのＧＵＩ５１０が示されている。ＧＵＩは、状態、記号、価格、サイズ等の取引データに典型的であろうフィールドを含んでいるが、これらに限られるものではない。一例において、クライアントデバイスの少なくとも１つのプロセッサがＧＵＩ上に表示されている所定の行のユーザ選択を検出し得る。選択に応答して、プロセッサは、その所定の行に対応する集計データを表示し得る。例として、ユーザがＧＵＩ５１０の記号（「Ｓｙｍ」）の行をクリックしてもよい。その結果、少なくとも１つのプロセッサは、図５Ｂに示されているように、記号の行に関連する全ての順序を集計する別のＧＵＩ５１４をレンダリングし得る。一例において、少なくとも１つのプロセッサは、記号の行をユーザがクリックしたことに応答して、記号の行をキーとして用いて、連結リスト（例えば、連結リスト５０４）の線形走査をし得る。即ち、ユーザは任意の行をクリックしてもよく、少なくとも１つのプロセッサは選択された行を線形走査のためのキーとして用いてもよい。
【００２９】
有利なことに、上記の装置、非一時的なコンピュータ読み取り可能な媒体及び方法は、ハッシュテーブルと特定の日に生じたトランザクションに関する一般的な問合せに最適であり得る複数のレベルのデータ構造を備える索引を生成する。更に、クライアントデバイスは、問合せの結果の形式と一致する形式を備えるメモリを割り当ててもよく、ＧＵＩ上に周期的に問合せの結果を更新してもよい。今度は、結果を取得するときに遅延があるとしても、ユーザは、ＧＵＩ上でデータをまだ見ることができる。従って、上で開示された索引とＧＵＩの技術は、サーバにおけるビッグデータの問合せを加速して、クライアントにおける問合せの結果の表示を加速することにより、コンピュータの性能を改善する。
【００３０】
本明細書における開示は具体例を参照して説明されたが、これらの例は単にこの開示の本質を説明するためのものであることを理解されたい。このため、例に多数の変更が施されてもよく、付属の請求の範囲によって定義されるようにこの開示の精神と範囲から離れることなく他の変形がなされてもよいことを理解されたい。更に、添付の図面において、具体的な処理が特定の順序で示されているが、そのような処理は、そのような順序が本明細書に明示的に記載されていない限り、いかなる特定の順序にも限定されない。むしろ、様々なステップが異なる順序で、又は同時に処理されることができ、ステップが省略され、又は追加されてもよい。
【００３１】
（付記）
（付記１）
メモリと、
相互に連結されたデータ構造の階層と、ハッシュテーブルであって、当該ハッシュテーブルにおけるエントリが、日と前記相互に連結されたデータ構造の階層における第１のデータ構造との間の関連を含むような、ハッシュテーブルとを含む、索引を前記メモリに生成し、
リモートデバイスから、前記日を含む複数の検索パラメータを有する、検索要求を受け、
前記日を用いて、前記相互に連結されたデータ構造の階層における前記第１のデータ構造のメモリアドレスがあるかについて、前記ハッシュテーブルを検索し、
前記検索パラメータに基づいて前記相互に連結されたデータ構造をトラバースするための計画を判別し、
前記トラバースの計画に従った前記第１のデータ構造における前記検索要求によって求められているデータの検索を開始し、
前記リモートデバイスに前記検索の結果を返す、
少なくとも１つのプロセッサと、
を備える、
装置。
【００３２】
（付記２）
前記トラバースの計画を判別するように、前記検索要求によって求められている前記データを取得するために、前記階層をトラバースすべき深さを判別するように、前記少なくとも１つのプロセッサが更に構成されている、
付記１に記載の装置。
【００３３】
（付記３）
前記第１のデータ構造は、前記相互に連結されたデータ構造の階層における第１のレベルにある、
付記１に記載の装置。
【００３４】
（付記４）
前記第１のデータ構造は、第１の二分木のデータ構造である、
付記３に記載の装置。
【００３５】
（付記５）
前記少なくとも１つのプロセッサは、前記第１の二分木のデータ構造の各ノードにおいて、前記階層における第２のレベルに属する第２のデータ構造へのポインタを生成するように更に構成されている、
付記４に記載の装置。
【００３６】
（付記６）
前記第２のデータ構造は、ベクトルのデータ構造である、
付記５に記載の装置。
【００３７】
（付記７）
前記第２のデータ構造は、第２の二分木のデータ構造である、
付記５に記載の装置。
【００３８】
（付記８）
前記少なくとも１つのプロセッサは、前記第２の二分木のデータ構造の各ノードにおいて、前記階層における第３のレベルに属する第３のデータ構造へのポインタを生成するように更に構成されている、
付記７に記載の装置。
【００３９】
（付記９）
少なくとも１つのプロセッサによって、相互に連結されたデータ構造の階層と、ハッシュテーブルであって、当該ハッシュテーブルにおけるエントリが、日と前記相互に連結されたデータ構造の階層における第１のデータ構造との間の関連を含むような、ハッシュテーブルとを含む、索引をメモリに生成することと、
前記少なくとも１つのプロセッサによって、リモートデバイスから、前記日を含む複数の検索パラメータを有する、検索要求を受けることと、
前記少なくとも１つのプロセッサによって、前記日を用いて、前記相互に連結されたデータ構造の階層における前記第１のデータ構造のメモリアドレスがあるかについて、前記ハッシュテーブルを検索することと、
前記少なくとも１つのプロセッサによって、前記検索パラメータに基づいて前記相互に連結されたデータ構造をトラバースするための計画を判別することと、
前記少なくとも１つのプロセッサによって、前記トラバースの計画に従った前記第１のデータ構造における前記検索要求によって求められているデータの検索を開始することと、
前記少なくとも１つのプロセッサによって、前記リモートデバイスに前記検索の結果を返すことと、
を含む、
方法。
【００４０】
（付記１０）
前記トラバースの計画を判別することは、前記少なくとも１つのプロセッサによって、前記検索要求によって求められている前記データを取得するために、前記階層をトラバースすべき深さを判別することを含む、
付記９に記載の方法。
【００４１】
（付記１１）
前記第１のデータ構造は、前記相互に連結されたデータ構造の階層における第１のレベルにある、
付記９に記載の方法。
【００４２】
（付記１２）
前記第１のデータ構造は、第１の二分木のデータ構造である、
付記１１に記載の方法。
【００４３】
（付記１３）
前記少なくとも１つのプロセッサによって、前記第１の二分木のデータ構造の各ノードにおいて、前記階層における第２のレベルに属する第２のデータ構造へのポインタを生成することを更に含む、
付記１２に記載の方法。
【００４４】
（付記１４）
前記第２のデータ構造は、ベクトルのデータ構造である、
付記１２に記載の方法。
【００４５】
（付記１５）
前記第２のデータ構造は、第２の二分木のデータ構造である、
付記１４に記載の方法。
【００４６】
（付記１６）
前記少なくとも１つのプロセッサによって、前記第２の二分木のデータ構造の各ノードにおいて、前記階層における第３のレベルに属する第３のデータ構造へのポインタを生成することを更に含む、
付記１５に記載の装置。
【００４７】
（付記１７）
メモリと、
表示デバイスと、
前記表示デバイスにグラフィカルユーザインタフェースをレンダリングし、
リモートサーバに検索要求を伝送し、
前記検索要求に応答して、それぞれの受信される記録の形式が、それぞれの記録に割り当てられたそれぞれのメモリ空間の形式と一致する複数の記録を受信し、
それぞれの受信した記録を個別の割り当てられたメモリ空間に複製し、
前記複数の記録が受信された順序を反映するような順序を示す、前記メモリ空間の連結リストに、それぞれの割り当てられた前記メモリ空間を追加し、
前記検索要求に対応する全てのデータの記録が受信されるまで、現在受信している記録を前記グラフィカルユーザインタフェースに周期的にレンダリングする、
少なくとも１つのプロセッサと、
を備える、
装置。
【００４８】
（付記１８）
前記少なくとも１つのプロセッサは、所定の期間が満了すると、前記現在受信している記録をレンダリングするように構成されている、
付記１７に記載の装置。
【００４９】
（付記１９）
前記少なくとも１つのプロセッサは、
前記グラフィカルユーザインタフェースに表示されている所定のフィールドの選択を検出し、
前記選択に応答して、前記所定のフィールドに対応する集計データを含む別のグラフィカルユーザインタフェースをレンダリングする、
ように更に構成されている、
付記１７に記載の装置。
【００５０】
（付記２０）
前記所定の期間は、約１秒である、
付記１７に記載の装置。
【図１】
2021532450.tif 000003
【図２】
2021532450.tif 000004
【図３】
2021532450.tif 000005
【図３Ａ】
2021532450.tif 000006
【図３Ｂ】
2021532450.tif 000007
【図３Ｃ】
2021532450.tif 000008
【図３Ｄ】
2021532450.tif 000009
【図４】
2021532450.tif 000010
【図５】
2021532450.tif 000011
【図５Ａ】
2021532450.tif 000012
【図５Ｂ】
2021532450.tif 000013
【国際調査報告】
2021532450.tif 000014