(57)【要約】  情報処理装置１００は、多次元空間上の点の集合を表現するデータ構造を処理対象としており、点の特徴値を表すビット表現から得られる接頭辞を特徴値接頭辞とし、点の特定の次元での座標を表すビット表現から得られる接頭辞を座標接頭辞として、クエリ領域として、特定の多次元の領域が指定された場合に、データ構造を構築している多次元の領域において、特徴値接頭辞で始まる領域と次元毎の座標接頭辞で始まる領域との共通部分として表現され、且つ、クエリ領域に含まれる、領域を特定し、特定した領域に対応するデータ構造上の区間である選定区間を出力する、検索部１０と、選定区間を用いてクエリ領域に含まれる点の集合に関する情報を計算する、集計部２０と、を備えている。
2016043121.tif 000002
【特許請求の範囲】
【請求項１】
多次元空間上の点の集合を表現するデータ構造を処理対象とする情報処理装置であって、
前記点の特徴値を表すビット表現から得られる接頭辞を特徴値接頭辞とし、前記点の特定の次元での座標を表すビット表現から得られる接頭辞を座標接頭辞として、
クエリ領域として、特定の多次元の領域が指定された場合に、
前記データ構造を構築している多次元の領域において、前記特徴値接頭辞で始まる領域と次元毎の前記座標接頭辞で始まる領域との共通部分として表現され、且つ、前記クエリ領域に含まれる、領域を特定し、
特定した領域に対応するデータ構造上の区間である選定区間を出力する、検索部と、
前記選定区間を用いて前記クエリ領域に含まれる点の集合に関する情報を計算する、集計部と、
を備えていることを特徴とする情報処理装置。
【請求項２】
前記データ構造が、
多次元上の前記点の集合それぞれの前記特徴値を、昇順に並べて得られる、特徴値列から、各次元について、前記特徴値の並び順と同じ順序で、各点の当該次元での座標を取り出すことで得られる座標列を用いて、次元毎に、前記座標列から、座標のビット表現が同じ座標接頭辞で始まる座標だけを、前記順番と同じ順序を保ったまま抽出して得られる部分列の、ビット表現の一部を用いて表現され、且つ、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されており、
前記検索部が、
前記部分列上の区間であって、当該区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、当該区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
請求項１に記載の情報処理装置。
【請求項３】
前記検索部が、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間について、この区間に含まれる座標に対応する点の集合が前記クエリ領域に完全に包含される区間であるかどうかを判定し、
判定の結果、前記クエリ領域に完全に包含される区間ではない場合に、
前記判定の対象となった前記部分列の抽出に用いられる前記座標接頭辞を延長して、第二の座標接頭辞を設定し、
そして、前記第二の接頭辞を用いて座標を抽出して得られた第二の部分列上の区間であって、前記第二の部分列上の区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、前記第二の部分列上の区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
請求項２に記載の情報処理装置。
【請求項４】
前記点の特徴値が、前記点の各次元の座標のビット表現を交互に組み合わせて得られるビット表現に基づく値である、
請求項１〜３のいずれかに記載の情報処理装置。
【請求項５】
前記データ構造が、複数のノードを有し、前記複数のノードそれぞれは、前記部分列に対応する各座標のビット表現における特定の桁のビットだけを取り出し、前記部分列と同じ順序で並べた前記ビットの列を用いて表現され、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されている、
請求項２または３に記載の情報処理装置。
【請求項６】
前記集計部が、前記情報として、前記選定区間の長さを合計した値を計算し、計算した値を出力する、
請求項１〜５のいずれかに記載の情報処理装置。
【請求項７】
前記集計部が、前記情報として、前記選定区間に含まれる各次元の座標を全て計算し、計算した全ての座標を出力する、
請求項１〜５のいずれかに記載の情報処理装置。
【請求項８】
多次元空間上の点の集合を表現するデータ構造を処理対象とする情報処理方法であって、
（ａ）前記点の特徴値を表すビット表現から得られる接頭辞を特徴値接頭辞とし、前記点の特定の次元での座標を表すビット表現から得られる接頭辞を座標接頭辞として、
クエリ領域として、特定の多次元の領域が指定された場合に、
前記データ構造を構築している多次元の領域において、前記特徴値接頭辞で始まる領域と次元毎の前記座標接頭辞で始まる領域との共通部分として表現され、且つ、前記クエリ領域に含まれる、領域を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定した領域に対応するデータ構造上の区間である選定区間を出力する、ステップと、
（ｃ）前記選定区間を用いて前記クエリ領域に含まれる点の集合に関する情報を計算する、ステップと、
を有することを特徴とする情報処理方法。
【請求項９】
前記データ構造が、
多次元上の前記点の集合それぞれの前記特徴値を、昇順に並べて得られる、特徴値列から、各次元について、前記特徴値の並び順と同じ順序で、各点の当該次元での座標を取り出すことで得られる座標列を用いて、次元毎に、前記座標列から、座標のビット表現が同じ座標接頭辞で始まる座標だけを、前記順番と同じ順序を保ったまま抽出して得られる部分列の、ビット表現の一部を用いて表現され、且つ、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されており、
前記（ａ）のステップにおいて、
前記部分列上の区間であって、当該区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、当該区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
請求項８に記載の情報処理方法。
【請求項１０】
前記（ａ）のステップにおいて、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間について、この区間に含まれる座標に対応する点の集合が前記クエリ領域に完全に包含される区間であるかどうかを判定し、
判定の結果、前記クエリ領域に完全に包含される区間ではない場合に、
前記判定の対象となった前記部分列の抽出に用いられる前記座標接頭辞を延長して、第二の座標接頭辞を設定し、
そして、前記第二の接頭辞を用いて座標を抽出して得られた第二の部分列上の区間であって、前記第二の部分列上の区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、前記第二の部分列上の区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
請求項９に記載の情報処理方法。
【請求項１１】
前記点の特徴値が、前記点の各次元の座標のビット表現を交互に組み合わせて得られるビット表現に基づく値である、
請求項８〜１０のいずれかに記載の情報処理方法。
【請求項１２】
前記データ構造が、複数のノードを有し、前記複数のノードそれぞれは、前記部分列に対応する各座標のビット表現における特定の桁のビットだけを取り出し、前記部分列と同じ順序で並べた前記ビットの列を用いて表現され、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されている、
請求項９または１０に記載の情報処理方法。
【請求項１３】
前記（ｃ）のステップにおいて、前記情報として、前記選定区間の長さを合計した値を計算し、計算した値を出力する、
請求項８〜１２のいずれかに記載の情報処理方法。
【請求項１４】
前記（ｃ）のステップにおいて、前記情報として、前記選定区間に含まれる各次元の座標を全て計算し、計算した全ての座標を出力する、
請求項８〜１２のいずれかに記載の情報処理方法。
【請求項１５】
コンピュータによって、多次元空間上の点の集合を表現するデータ構造を処理対象として情報処理を行なうためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記コンピュータに、
（ａ）前記点の特徴値を表すビット表現から得られる接頭辞を特徴値接頭辞とし、前記点の特定の次元での座標を表すビット表現から得られる接頭辞を座標接頭辞として、
クエリ領域として、特定の多次元の領域が指定された場合に、
前記データ構造を構築している多次元の領域において、前記特徴値接頭辞で始まる領域と次元毎の前記座標接頭辞で始まる領域との共通部分として表現され、且つ、前記クエリ領域に含まれる、領域を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定した領域に対応するデータ構造上の区間である選定区間を出力する、ステップと、
（ｃ）前記選定区間を用いて前記クエリ領域に含まれる点の集合に関する情報を計算する、ステップと、
を実行させる命令を含む、プログラムを記録しているコンピュータ読み取り可能な記録媒体。
【請求項１６】
前記データ構造が、
多次元上の前記点の集合それぞれの前記特徴値を、昇順に並べて得られる、特徴値列から、各次元について、前記特徴値の並び順と同じ順序で、各点の当該次元での座標を取り出すことで得られる座標列を用いて、次元毎に、前記座標列から、座標のビット表現が同じ座標接頭辞で始まる座標だけを、前記順番と同じ順序を保ったまま抽出して得られる部分列の、ビット表現の一部を用いて表現され、且つ、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されており、
前記（ａ）のステップにおいて、
前記部分列上の区間であって、当該区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、当該区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
請求項１５に記載のコンピュータ読み取り可能な記録媒体。
【請求項１７】
前記（ａ）のステップにおいて、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間について、この区間に含まれる座標に対応する点の集合が前記クエリ領域に完全に包含される区間であるかどうかを判定し、
判定の結果、前記クエリ領域に完全に包含される区間ではない場合に、
前記判定の対象となった前記部分列の抽出に用いられる前記座標接頭辞を延長して、第二の座標接頭辞を設定し、
そして、前記第二の接頭辞を用いて座標を抽出して得られた第二の部分列上の区間であって、前記第二の部分列上の区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、前記第二の部分列上の区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
請求項１６に記載のコンピュータ読み取り可能な記録媒体。
【請求項１８】
前記点の特徴値が、前記点の各次元の座標のビット表現を交互に組み合わせて得られるビット表現に基づく値である、
請求項１５〜１７のいずれかに記載のコンピュータ読み取り可能な記録媒体。
【請求項１９】
前記データ構造が、複数のノードを有し、前記複数のノードそれぞれは、前記部分列に対応する各座標のビット表現における特定の桁のビットだけを取り出し、前記部分列と同じ順序で並べた前記ビットの列を用いて表現され、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されている、
請求項１６または１７に記載のコンピュータ読み取り可能な記録媒体。
【請求項２０】
前記（ｃ）のステップにおいて、前記情報として、前記選定区間の長さを合計した値を計算し、計算した値を出力する、
請求項１５〜１９のいずれかに記載のコンピュータ読み取り可能な記録媒体。
【請求項２１】
前記（ｃ）のステップにおいて、前記情報として、前記選定区間に含まれる各次元の座標を全て計算し、計算した全ての座標を出力する、
請求項１５〜１９のいずれかに記載のコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法、及びこれらを実現するためのプログラムを記録したコンピュータ読み取り可能な記録媒体に関し、特には、多次元データ上での効率的な検索を行うための、情報処理装置、情報処理方法、及びコンピュータ読み取り可能な記録媒体に関する。
【背景技術】
【０００２】
多次元空間上に点が大量に存在するときに、指定した矩形の範囲に包含される点を見つけることは、矩形範囲検索（orthogonal range search）と呼ばれている。たとえば、次元数をdとおくと、d次元の多次元空間上の点は、d個の座標の組み合わせによりp=(p1, p2, …, pd)という形で表現できる。このとき、各次元kの範囲を[lqk, uqk]で表すとして、Q=[lq1, uq1]×[lq2, uq2]×…×[lqd, uqd]というd次元の矩形の範囲を考える。この矩形の範囲をクエリ領域と呼ぶこととすると、矩形範囲検索の目標は、このクエリ領域Qに包含される点p、すなわち∀k∈{1,…,d}: lqk ≦ pk≦ uqkを満たす点pを検索することである。【０００３】
そして、このような矩形範囲検索は、地理情報を扱うアプリケーション、更には多次元データ分析において、重要な役目を果たす。以下に具体例を示す。【０００４】
たとえば、地図上でのレストランの位置は（緯度, 経度）という２つの値の組み合わせである２次元データで表すことができる。このとき、矩形範囲検索を用いると、経度が138度から139度、緯度が35度から36度の範囲に収まるような全てのレストランを検索できる。【０００５】
また、たとえば、ある会社の社員に関する統計データを（年齢, 身長, 年収）という３次元データで表すことができる。このとき、矩形範囲検索を用いると、年齢が30歳から40歳で、身長が170cmから180cm、年収が500万円から600万円の範囲に収まる全ての社員を検索できる。【０００６】
更に、矩形範囲検索には、検索結果として何を返すかによって様々なバリエーションが存在する。バリエーションの一例として、レポート・クエリ（report query）と集計クエリ（aggregate query）とが挙げられる。【０００７】
まず、レポート・クエリは、クエリ領域に包含される全ての点のリストを返す矩形範囲検索である。レポート・クエリは、クエリ領域に包含される点の数をヒット数と呼ぶことにすると、ヒット数に比例する大きさのリストを返してしまうため、ヒット数が大きくなるような大規模データの分析には向かない。たとえば、数千万個の点が包含されるとき、数千万個の点を全て出力することになってしまう。【０００８】
そこで、大規模データの分析においては、クエリ領域に包含される全ての点のリストを返すよりも、それらの点について集計した結果を返す集計クエリが重要となる。様々な集計クエリの中でも最も代表的なクエリはカウント・クエリ（count query）である。【０００９】
このカウント・クエリは、クエリ領域に包含される点の数を返す矩形範囲検索である。この他にも、点にそれぞれ重みが付与されている場合に、クエリ領域に包含される点の重みの合計を返す合計（sum）クエリ、平均値を返す平均（average）クエリ、及び最大値を返す最大値（max）クエリなどが存在する。【００１０】
さて、矩形範囲検索に使うことができる代表的なデータ構造として、kd木が知られている（例えば、非特許文献１参照。）。kd木のサイズは、O(n)、つまり線形サイズで表現できる。また、kd木における矩形範囲検索の最悪時間計算量は、O(n(d-1)/d)であることが知られている。なお、nはデータ数、dは次元数である。kd木が達成している最悪時間計算量O(n(d-1)/d)は、これまで知られている線形サイズのデータ構造の時間計算量の中では、最良のものである。【００１１】
また、サイズがO(n)を超えてしまうような超線形サイズのデータ構造に、矩形範囲探索を適用した場合は、計算時間（計算量）を改善することができる。このような超線形サイズのデータ構造としては、たとえば、range treeと呼ばれるデータ構造が挙げられる。【００１２】
さらに、矩形範囲探索は、ウェーブレット木（wavelet tree）という２次元のデータ構造でも実現できる（例えば、非特許文献１参照）。この場合、２次元空間において探索が行なわれ、時間計算量は、O(log n)時間となる。なお、上述したkd木およびウェーブレット木を用いた矩形範囲検索については、非特許文献１に詳しく記載されている。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Meng He, ”Succinct and Implicit Data Structures for Computational Geometry”, Lecture Notes in Computer Science Volume 8066 “Space-Efficient Data Structures, Streams, and Algorithms”, pp 216-235, 2013, Springer Berlin Heidelberg, ISBN 978-3-642-40272-2
【発明の概要】
【発明が解決しようとする課題】
【００１４】
このように、矩形範囲検索は種々のデータ構造で実現することができるが、実際には、以下に示す問題がある。まず、矩形範囲探索をkd木で実現した場合においては、達成される最悪時間計算量O(n(d-1)/d)が、データ数n及び次元数dのいずれか又は両方が大きくなる程、大きくなってしまうという問題がある。【００１５】
また、矩形範囲検索を超線形サイズのデータ構造で実現した場合は、kd木で実現した場合に比べ、計算時間の改善は図られるが、超線形サイズのデータ構造のサイズが大きすぎるため、実際のアプリケーションに用いることが難しく、実用的でないという問題がある。【００１６】
更に、矩形範囲検索をウェーブレット木で実現した場合は、ウェーブレット木が２次元のデータにしか用いることができないため、３次元以上の任意の次元のデータ構造に対する検索ができないという問題がある。【００１７】
本発明の目的の一例は、上記問題を解消し、任意の次元について、線形サイズで、kd木よりも高速な矩形範囲検索を実現し得る、情報処理装置、情報処理方法、及びコンピュータ読み取り可能な記録媒体を提供することにある。
【課題を解決するための手段】
【００１８】
上記目的を達成するため、本発明の一側面における情報処理装置は、多次元空間上の点の集合を表現するデータ構造を処理対象とする情報処理装置であって、
前記点の特徴値を表すビット表現から得られる接頭辞を特徴値接頭辞とし、前記点の特定の次元での座標を表すビット表現から得られる接頭辞を座標接頭辞として、
クエリ領域として、特定の多次元の領域が指定された場合に、
前記データ構造を構築している多次元の領域において、前記特徴値接頭辞で始まる領域と次元毎の前記座標接頭辞で始まる領域との共通部分として表現され、且つ、前記クエリ領域に含まれる、領域を特定し、
特定した領域に対応するデータ構造上の区間である選定区間を出力する、検索部と、
前記選定区間を用いて前記クエリ領域に含まれる点の集合に関する情報を計算する、集計部と、
を備えていることを特徴とする。【００１９】
また、上記目的を達成するため、本発明の一側面における情報処理方法は、多次元空間上の点の集合を表現するデータ構造を処理対象とする情報処理方法であって、
（ａ）前記点の特徴値を表すビット表現から得られる接頭辞を特徴値接頭辞とし、前記点の特定の次元での座標を表すビット表現から得られる接頭辞を座標接頭辞として、
クエリ領域として、特定の多次元の領域が指定された場合に、
前記データ構造を構築している多次元の領域において、前記特徴値接頭辞で始まる領域と次元毎の前記座標接頭辞で始まる領域との共通部分として表現され、且つ、前記クエリ領域に含まれる、領域を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定した領域に対応するデータ構造上の区間である選定区間を出力する、ステップと、
（ｃ）前記選定区間を用いて前記クエリ領域に含まれる点の集合に関する情報を計算する、ステップと、
を有することを特徴とする。【００２０】
更に、上記目的を達成するため、本発明の一側面におけるコンピュータ読み取り可能な記録媒体は、コンピュータによって、多次元空間上の点の集合を表現するデータ構造を処理対象として情報処理を行なうためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記コンピュータに、
（ａ）前記点の特徴値を表すビット表現から得られる接頭辞を特徴値接頭辞とし、前記点の特定の次元での座標を表すビット表現から得られる接頭辞を座標接頭辞として、
クエリ領域として、特定の多次元の領域が指定された場合に、
前記データ構造を構築している多次元の領域において、前記特徴値接頭辞で始まる領域と次元毎の前記座標接頭辞で始まる領域との共通部分として表現され、且つ、前記クエリ領域に含まれる、領域を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定した領域に対応するデータ構造上の区間である選定区間を出力する、ステップと、
（ｃ）前記選定区間を用いて前記クエリ領域に含まれる点の集合に関する情報を計算する、ステップと、
を実行させる命令を含む、プログラムを記録していることを特徴とする。
【発明の効果】
【００２１】
以上のように、本発明によれば、任意の次元について、線形サイズで、kd木よりも高速な矩形範囲検索を実現することができる。
【図面の簡単な説明】
【００２２】
【図１】図１は、２次元空間における座標とZ値との一例を示す図である。
【図２】図２は、本発明の実施の形態における情報処理装置の概略構成を示すブロック図である。
【図３】図３は、本発明の実施の形態における情報処理装置の具体構成を示すブロック図である。
【図４】図４は、本発明の実施の形態で用いられるZ値列及び座標列の一例を示す図である。
【図５】図５は、本発明の実施の形態で用いられるウェーブレット木の一例を示す図であり、図５（ａ）及び（ｂ）はそれぞれ次元が異なるウェーブレット木を示している。
【図６】図６は、本発明の実施の形態における情報処理装置の動作を示すフロー図である。
【図７】図７は、再帰的に矩形範囲検索する関数range_search(V,Q)の動作を示すフロー図である。
【図８】図８は、Z値探索ノードVの左右の子ノードを計算する関数get_children(V)の動作を示すフロー図である。
【図９】図９は、図７に示す関数range_search_1d(V,Q)の動作を示す図である。
【図１０】図１０は、図９に示された関数range_search_1d_rec(πr, vr, sr, er, lqr, uqr)の動作を示す図である。
【図１１】図１１は、２次元の場合の探索ノード数と包含次元数との変化を示す図である。
【図１２】図１２は、本発明と従来手法との計算量の比較を示す図である。
【図１３】図１３は、本発明の実施の形態における情報処理装置を実現するコンピュータの一例を示すブロック図である。
【発明を実施するための形態】
【００２３】
（発明の原理）
最初に、本発明の基本的な原理について、一般的なkd木を例に挙げて以下に説明する。
【００２４】
まず、kd木は、多次元データを扱うための二分探索木である。kd木の特徴は、空間全体を、次元1から次元dまでの各次元で順番に２分割していくことである。kd木では、木構造が空間の再帰的な分割を表しており、二分探索木の各ノードが部分領域を担当している。各ノードvが担当する部分領域を、本明細書では、ノードの「カバー領域」と呼ぶことにする。
【００２５】
さらに、kd木は、各ノードに、そのノードのカバー領域に含まれる点の統計量を保持しておくことができる。たとえば、カウント・クエリを高速に計算したい場合は、各ノードのカバー領域に含まれる点の数が、そのノードに保存される。
【００２６】
kd木における矩形範囲検索は以下のように実現される。まず、ルートノードを出発点として、子ノードの担当するカバー領域がクエリ領域と重なるかどうかが判定され、重なる場合にだけ、その子ノードに移動することが繰り返される。子ノードへの移動は、特定の次元でカバー領域を二分割することに相当する。そして、ノードの担当するカバー領域が、クエリ領域に完全に包含された場合は、そのノードに保存されている、カバー領域の点の統計量が、出力結果に加えられる。
【００２７】
kd木の探索では、以上のように、与えられたクエリ領域を、カバー領域がクエリ領域に含まれるように、複数のノードに分割して、各ノードに保存されている、各カバー領域の点の統計量を合算することによって、探索結果が得られている。そして、kd木の最悪時間計算量O(n(d-1)/d)は、この空間分割を行うのに必要なノードの数を表している。このようなノードを基準とした空間分割を行う手法では、最悪時間計算量O(n(d-1)/d)より良い時間計算量を達成することは不可能である。
【００２８】
これに対して、本発明は、このようなノードを基準とした分割ではなく、多次元空間にある点の各座標を元にして計算される特徴値の接頭辞を基準とした分割が実行される。より具体的には、まず、各点についてZ値と呼ばれる特徴値が定義され、そして、クエリ領域に対応する、その特徴値が特定の接頭辞で始まるような領域が見つけ出される。次に、見つけ出された領域において、クエリ領域に含まれ、且つ、特定の次元での座標が特定の接頭辞で始まる部分領域が探索される。本発明では、このような部分領域は、木構造のノードではなく、木構造のノードに対応する座標部分列上の区間として得られる。
【００２９】
このように、本発明は、クエリ領域を、ノードを基準として分割するのではない。本発明では、点の特徴値の接頭辞で規定されるカバー領域と点の各次元での座標の接頭辞で規定されるカバー領域との共通部分の集合で、クエリ領域が分割されることになる。これにより、本発明によれば、kd木を用いる場合と異なり、クエリ領域の分割に要する計算量が削減され、kd木より高速な矩形範囲探索が実現される。
【００３０】
（本明細書で用いられる概念）
ここで、本明細書で用いられる種々の概念について以下に説明する。本明細書では、全ての点の座標piが[0,n-1]の整数で表されるものとする。さらに、これらの整数は、二進表現で長さl=ceil(log n)のビットで表されるとする。なお、ceil()は天井関数を表す。logは底を２とする対数関数を表す。
【００３１】
たとえば、n=8のとき、全ての座標は[0,7]の整数で表され、二進表現では長さl=ceil(log n) =3ビットで表される。すなわち、0=”000”, 1=”001”, 2=”010”, 3=”011”, 4=”100”, 5=”101”, 6=”110”, 7=”111”で表すことができる。
【００３２】
ただし、本発明は、座標が整数で表されていない一般の多次元空間に対しても適用できる。たとえば、順位空間(rank space)への変換という手法を用いれば、任意の実数で表されるn個の点を、[0,n-1]の範囲の整数の座標に変換でき、その座標を用いることで、矩形範囲検索を実現できる。従って、この順位空間への変換を用いることにより、本発明を、実数で表される一般の多次元空間に適用することが可能である。なお、順位空間への変換については、たとえば上述の非特許文献１に記載されている。
【００３３】
また、本発明は、値を１と０の二進表現で表現できていれば、順位変換への変換が行なわれていなくても適用できる。すなわち、データ数がnであるとき、座標の値の範囲が[0,n-1]の範囲から外れているデータであっても、本発明は適用できる。本明細書では、計算量の理論的な分析を行うために[0,n-1]の範囲に限定して説明しているだけであり、実用上は[0,n-1]の範囲に限らなくても問題なく本発明を適用できる。
【００３４】
また、本明細書では、「接頭辞」という概念を用いる。接頭辞とは、整数を二進表現で表したときに、その上位ビットだけを取り出したものである。本明細書では、整数の上位hビットの接頭辞を、h個の1と0、および(l-h)個の*の組み合わせで表記する。*はワイルドカードであり、1および0のどちらでもよいことを表している。ある整数が特定の接頭辞から始まることは、その整数が、特定の連続範囲に含まれることに対応する。
【００３５】
たとえば、整数が長さl=3のビット列であらわされているとする。このとき長さ1の接頭辞”0**”は、”000”, “001”, ”010”, ”011”という４つの値に対応する。すなわち、この接頭辞は、整数上の値の範囲である[“000”,”011”]=[0,3]に対応する。同様に、長さ2の接頭辞”01*”は、”010”と”011”という２つの値に対応しており、値の範囲で表すと[“010”,”011”]=[2,3]に対応する。一方、長さl(=3)の接頭辞は、ひとつの整数だけに対応する。
【００３６】
また、本明細書では、列(sequence)に関して以下の表記が用いられる。たとえば、長さnの列Aが存在するとき、Aの最初の要素をA[0]、Aの最後の要素をA[n-1]とする。さらに、A上の位置iの要素A[i]から位置jの要素A[j]までの区間をA[i,j]で表し、終端jを含まない場合の区間をA[i,j)で表すものとする。
【００３７】
次に、z-orderと呼ばれる空間充填曲線について説明する。空間充填曲線とは、d次元の空間上の全ての点を通るような曲線のことであり、これを用いることでd次元上での位置を１次元上での位置に変換することができる。たとえば、z-orderを用いることにより、d個の座標で特定される点p(p1, p2, …, pd)を、Z値と呼ばれる一次元の値に変換することができる。
【００３８】
ここで、Z値の定義を示す。piが長さlのビットで表されるとき、Z値は、点pの各次元での座標piを表すビットを交互に挟み込んだ長さd*lのビット列で表される。言い換えると、Z値は、多次元上の点の各座標で特定される特徴値である。また、まず初めに、座標p1, p2, …, pdそれぞれの上位1ビット目を集めて連結する。次に、座標p1, p2, …, pd それぞれの各次元の上位2ビット目を集めて連結する。これをl回繰り返した後、得られたビット列をこの順番でさらに連結する。こうして最終的に連結されたビット列がZ値となる。
【００３９】
ここで、図１を用いて、Z値の具体例について説明する。図１は、２次元空間における座標とZ値との一例を示す図である。図１において、縦軸は次元１を表し、横軸は次元２を表している。また、各マス目に記入されているビット列（２進数）が、各次元の座標から求められたZ値を示す。
【００４０】
具体的には、図１の例では、d(=2)次元上の点pが、ひとつあたりl=3ビットで表されている。このとき、点pに対応するZ値は、d*l=2*3=6ビットで表される。例えば、p=(p1,p2)=(”000”,”111”)=(0,7)のとき、この点pに対応するZ値は、z=“010101”である。
【００４１】
続いて、Z値の接頭辞に関して成り立つ重要な性質を説明する。以下では、Z値を表すビット表現から得られる接頭辞を「Z値接頭辞」と呼び、各次元の座標を表すビット表現から得られる接頭辞を「座標接頭辞」と呼ぶこととする。
【００４２】
Z値接頭辞πzは、各次元の座標からZ値への変換を逆に適用することで、各次元に対応するd個の座標接頭辞の集合{πk}(1≦k≦d)に分解できる。すなわち、1≦k≦dとなる次元kについて、最初のkビット目、(k+d)ビット目、(k+2d)ビット目、のようにd個のあいだをおいてビットを集めて連結することで、次元kの座標接頭辞πkを得られる。これを、次元kにおいてπzに対応する座標接頭辞と呼ぶことにする。
【００４３】
次元kの座標接頭辞πkに関し、πkで始まる次元kの座標の区間を [lπk,uπk] で表すものとする。このとき、πkのカバー領域C(πk)を、次元kについてのみ区間[lπk,uπk] に制限され、他の次元については制限がない領域として定義する。つまりC(πk)= [0,n-1] × … × [0,n-1] × [lπk,uπk] ×[0,n-1]  × … × [0,n-1]である。
【００４４】
また、Z値接頭辞πzのカバー領域C(πz)を、C(πz) = C(π1) ∩ C(π2) ∩ ... ∩ C(πd) = [lπ1,uπ1] × [lπ2,uπ2] × … × [lπd,uπd] と定義する。そして、点pがC(πz)に含まれるとき、点pのZ値は必ずπzで始まることが保証される。何故なら、各座標pkが座標接頭辞πkで始まるからである。
【００４５】
例えば、長さ3のZ値接頭辞πz ="011***"を考える。この接頭辞についてZ値から各次元の座標に逆変換を行うと、次元1での長さ2の座標接頭辞π1 ="01*"と、次元2での長さ1の座標接頭辞π2 ="1**"とに分解される。
【００４６】
また、このとき、 [lπ1,uπ1]=[“010”,”011”]=[2,3]、および[lπ2,uπ2]=[“100”,”111”]=[4,7]であり、C(πz) = [2,3] × [4,7] である。この関係は、図１に示されている。図１に示すように、次元1における領域C(π1)と、次元2における領域C(π2)との交わる領域C(π1) ∩ C(π2)が、C(πz)となっていることが分かる。C(πz)に含まれるZ値は全てπzで始まっている。
【００４７】
最後に、空間分割の終了条件を説明するために必要な「包含次元数」の定義について説明する。次元kについて、以下の包含条件が成り立つとき、「カバー領域がクエリ領域に次元kで包含されている」と呼ぶ。
包含条件：lqk ≦ lπk かつ uπk ≦ uqk
【００４８】
さらに、d個の次元のうちh個の次元において包含されているとき、「カバー領域の包含次元数はhである」、と定義する。また、包含次元数がdであるとき、すなわち、全ての次元が包含されているとき、カバー領域は完全に包含されていると呼ぶ。
【００４９】
（実施の形態）
続いて、本発明の実施の形態における、情報処理装置、情報処理方法、及びプログラムについて、図１〜図１３を参照しながら説明する。
【００５０】
［装置構成］
最初に、本実施の形態における情報処理装置の概略構成について図２を用いて説明する。図２は、本発明の実施の形態における情報処理装置の概略構成を示すブロック図である。図２に示す本実施の形態における情報処理装置１００は、多次元空間上の点の集合を表現するデータ構造を処理対象とする装置である。そして、図２に示すように、情報処理装置１００は、検索部１０と、集計部２０とを備えている。
【００５１】
このうち、検索部１０は、クエリ領域として、特定の多次元の領域が指定された場合に機能する。検索部１０は、この場合に、データ構造を構築している多次元の領域において、特徴値接頭辞で始まる領域と次元毎の座標接頭辞で始まる領域との共通部分として表現され、且つ、クエリ領域に含まれる、領域を特定する。
【００５２】
なお、「特徴値接頭辞」は、上述したZ値接頭辞と同義であり、点の特徴値（Z値）を表すビット表現から得られる接頭辞である。「座標接頭辞」は、上述したように、点の特定の次元での座標を表すビット表現から得られる接頭辞である。
【００５３】
続いて、検索部１０は、特定した領域に対応するデータ構造上の区間である選定区間を出力する。集計部２０は、この選定区間を用いて、クエリ領域に含まれる点の集合に関する情報を計算する。
【００５４】
このように、情報処理装置１０では、入力されたクエリ領域は、特徴値接頭辞で規定される領域と各次元の座標接頭辞で規定される領域との共通部分によって分割されることになるので、kd木を探索する場合に比べて、クエリ領域の分割に要する計算量が削減される。このため、情報処理装置１０によれば、任意の次元dについて、線形サイズで、kd木よりも高速な矩形範囲検索を実現することができる。
【００５５】
次に、図３を用いて、本実施の形態における情報処理装置１００の構成について更に具体的に説明する。図３は、本発明の実施の形態における情報処理装置の具体構成を示すブロック図である。
【００５６】
図３に示すように、本実施の形態では、情報処理装置１００は、上述した検索部１０及び集計部２０に加えて、入力受付部３０と、出力部４０と、記憶部５０と、を備えている。このうち、入力受付部３０は、外部からのクエリ領域の入力を受け付け、これを検索部１０に出力する。
【００５７】
記憶部５０は、多次元空間上の点の集合を表現するデータ構造５１を記憶している。データ構造５１は、本実施の形態では、その次元数をdとすると、d個のウェーブレット木で構築されている。また、各ウェーブレット木は、ひとつの次元に対応している。
【００５８】
ここで、このd個のウェーブレット木の構造について説明する。まず、多次元空間上のn個の点のZ値（図１参照）を、昇順にソートして並べた列（特徴値列）をZとする。さらに、それぞれのZ値に対応する点pを、Z値の昇順と同じ順番で並べることで、点pの列Pが構築される。そして、列Pを構築する各点の次元kの座標を取り出し、取り出した各座標を、先の順番と同じ順番で並べ、得られた列をPkとする。また、この列Pkを座標列(coordinate sequence)と呼ぶこととする。なお、列Z、列P、及び列Pkは、いずれも長さnの列である。
【００５９】
また、0≦i＜nとなるiについて、Z値Z[i]と座標Pk[i]とは、同一の点P[i]に対応している。さらに、1≦k≦dの範囲で、次元k毎に、座標列Pkに関してウェーブレット木が生成される。生成されるウェーブレット木はd個であり、このd個のウェーブレット木の集合をW={wk}とする。また、このd個のウェーブレット木の集合Wが、データ構造５１を構築している。
【００６０】
ここで、上述した図１に加え、図４及び図５を用いて、d個のウェーブレット木の具体例について説明する。また、以下の説明では、次元数は２次元であるとする。図４は、本発明の実施の形態で用いられるZ値列及び座標列の一例を示す図である。図５は、本発明の実施の形態で用いられるウェーブレット木の一例を示す図であり、図５（ａ）及び（ｂ）はそれぞれ次元が異なるウェーブレット木を示している。
【００６１】
まず、図１に示すように、各マス目に存在する８個の丸い円が、２次元上の点pを表すものとする。この例では、n=8であり、それぞれの点は[0,7]×[0,7]=64個のグリッド上の点として表現される。たとえば、(5,2)=(“101”,”010”)の点のZ値は、”100110”=38である。このとき、円の中に書かれている番号が、対応するZ値が昇順になるように並べた場合の順位を示している。
【００６２】
図４には、３つのテーブルが示されており、その内、上段のテーブルには、Z値の列Zが示されている。また、図４において、Z値の列Zは、図１に示す８個の点に対応している。更に、中段及び下段のテーブルには、Z値の列Zに対応する座標列Piが示されている。なお、本例では、次元数は２次元であるので、中段のテーブルに座標列P1が示され、下段のテーブルに座標列P2が示されている。
【００６３】
また、各テーブルにおいて、１行目は列の添字iを示し、２行目は添字に対応する整数を示している。そして、３行目以降には、各整数のビット表現が示されている。たとえば、図１において(5,2)の位置にある点のZ値38は、添字4の位置にある。よって、Z[4]=38 、P1[4]=5、P2[4]=2となる。
【００６４】
そして、次元iの座標列Piに対応するウェーブレット木は、以下のように、二分木として定義される。なお、ウェーブレット木は、深さlの二分木である。この木構造において、親から左の子に向かうエッジはビット0に対応し、親から右の子に向かうエッジはビット1に対応する。
【００６５】
まず、ウェーブレット木のルートノードは、深さ0にあり、長さ0ビットの座標接頭辞に対応しているものとする。さらにウェーブレット木の深さhにあるノードvは、ルートからそのノードへのパスに出現する h個のビットを連結して得られるhビットの座標接頭辞πに対応しているものとする。深さlにあるノードは全て葉ノードである。葉ノードは、ルートからそのノードへのパスに出現するl個のビットを連結して得られるlビットで表される１つの整数に対応する。
【００６６】
さらに、深さhにおいて座標接頭辞πに対応するノードvは、座標列Piの部分列Pi (π)に対応する。ただし、Pi (π)は、座標列Piから座標接頭辞πで始まる全ての整数を、その並び順と同じ順序を保ったまま抜き出した部分列とする。本明細書では、元となるPiを「座標列」、座標接頭辞πに注目して抜き出した部分列Pi(π)を、「座標部分列(coordinate subsequence)」と呼び分けることとする。
【００６７】
さらに、このノードvは、Pi (π)の各要素のh+1番目のビットのみを抜き出して同じ順序で連結したビット列Bvを記憶しているものとする。すなわち、整数Pi (π)[i]のh+1ビット目が0であるときBv[i]=0となり、1であるときBv[i]=1となるようなビット列である。
【００６８】
具体的には、図５（ａ）及び（ｂ）に示すように、本実施の形態では、次元１の座標列P1に対して構築されたウェーブレット木w1と、次元２の座標列P2に対して構築されたウェーブレット木w2とが用いられる。また、図５（ａ）及び（ｂ）においては、各ノードについて対応する座標接頭辞π、座標部分列Pi (π)、およびビット列Bvが示されている。
【００６９】
また、図５（ａ）に示すように、ウェーブレット木w1は、座標列P1=(0,1,3,2,5,7,4,6)のウェーブレット木である。座標列P1の各要素は、3ビットで表されている。そして、各ウェーブレット木のルートノードは、座標接頭辞π＝”***”に結びつけられている。よって、この座標接頭辞は3ビットで表せる全ての値、すなわち、[“000”,”111”]=[0,7]までの範囲の全ての値に対応している。このため、ルートノードは、座標部分列P1 (π)の0+1=1ビット目のビットをビット列Bvとして保持している。
【００７０】
次に、ルートノードの左の子ノードは、接頭辞“0**”に対応しており、1ビット目が0で始まる3ビットの整数、すなわち[0,3]の範囲に対応し、さらに、座標列P1から[0,3]の範囲に該当する値だけを取り出した座標部分列P1 (π)=(0,1,3,2)にも対応する。よって、この左の子ノードは、その2ビット目のビットをビット列Bvとして保持している。なお、以降の子ノードも同様に考えることができる。
【００７１】
また、ウェーブレット木は、各内部ノードvについて、ビット列Bvの完備辞書を保持している。完備辞書は、長さnのビット列Bに対してaccess、rank、selectと呼ばれる３種類の操作をサポートするデータ構造である。この３種類の操作は以下のように定義される。
【００７２】
access(B,i)は、B上の位置iの要素B[i]を返す。
rank1(B,i)は、B[0,i)の範囲に存在する1の数を返す。
rank0(B,i)は、B[0,i)の範囲に存在する0の数を返す。
select1(B,i)は、B上でi+1番目の1が出現する位置jを返す。
select0(B,i)は、B上でi+1番目の0が出現する位置jを返す。
【００７３】
なお、完備辞書は、文献によっては、簡潔ビットベクトルあるいはrank / select dictionaryなどと呼ばれることがある。
【００７４】
また、図５（ａ）及び（ｂ）の例では、説明のため、ウェーブレット木の各ノードにおいて、座標接頭辞πと、座標部分列Pi (π)と、ビット列Bvとが、示されているが、実際には、ウェーブレット木はBvの完備辞書だけを保持しており、座標接頭辞πおよび座標部分列Pi (π)を保持している必要はない。これは、座標接頭辞πは、たどってきたエッジの情報から計算でき、座標部分列Pi (π)の各要素は、ビット列Bvの完備辞書を用いることで計算できるためである。よって、記憶部５０は、実際には、データ構造として、完備辞書のみを保持することになる。
【００７５】
つまり、本実施の形態では、データ構造は、次元毎に、部分列Pi (π)のビット表現を含み、且つ、部分列上の区間であって、それに含まれる座標に対応した点の特徴値のビット表現が特徴値接頭辞から始まっている区間を特定できるように、構築されている。
【００７６】
なお、ウェーブレット木の定義方法は文献によって異なる。上述した非特許文献１では、ウェーブレット木は、接頭辞を用いずに定義されているが、本明細書では、ウェーブレット木は、説明のため、接頭辞を用いて定義されている。なお、どちらの定義の場合であっても、ウェーブレット木の本質的な構造は同一であり、同じ動作を実現できる。
【００７７】
また、ウェーブレット木は、木構造としての探索が可能な構造、即ち、複数のノードを有する構造を有していれば、明示的に木構造として構成されていなくてもよい。たとえば、ウェーブレット行列という、ビット列をノードごとに分けずにウェーブレット木を実装する手法が知られているが、本発明における議論は、ウェーブレット行列を使った場合でもまったく同様に成立する。
【００７８】
また、本実施の形態では、検索部１０は、入力受付部３０からクエリ領域が出力されてくると、記憶部５０に対して問い合わせ、データ構造５１を取得する。次に、検索部１０は、データ構造５１を参照し、座標部分列上の区間であって、その区間に含まれる座標に対応する点の特徴値のビット表現が特徴値接頭辞で始まっており、且つ、その区間に含まれる座標に対応する点の集合が全てクエリ領域に包含される区間を、選定区間として出力する。
【００７９】
また、集計部２０が、選定区間を用いて、クエリ領域に含まれる点の集合に関する情報（統計量）を計算すると、これを、出力部４０に出力する。その後、出力部４０は、集計部２０が出力した統計量を、外部の端末装置、サーバ装置等に出力する。
【００８０】
［探索アルゴリズムの概要］
続いて、情報処理装置１００の動作を説明する前に、情報処理装置１００において用いられる探索アルゴリズムの概要について以下に説明する。
【００８１】
まず、Z値接頭辞のカバー領域C(πz)と、特定の次元r (1≦r≦d) の座標接頭辞πrのカバー領域C(πr)と、の共通部分、すなわちC(πz) ∩C(πr)を考える。この共通部分の領域に含まれる点は、Z値がZ値接頭辞πzで始まり、かつ、次元rの座標が座標接頭辞πrで始まる点である。なお、このカバー領域の共通部分を、C(πz∧πr)= C(πz) ∩C(πr)と表記することにする。
【００８２】
このとき、C(πz∧πr)に含まれる点の集合は、次元rのウェーブレット木wrにおいてπrに対応するノードの座標部分列Pr(πr) において、必ずひとつながりの区間Pr(πr) [sr, er]に対応する。これは、座標列PrはZ値の昇順にソートされているため、座標列Pr上で、πzで始まる点に対応する座標は常にひとつながりの区間として得られるからである。また、Pr(πr)は、Prからπrで始まる座標のみを、Z値の並び順と同じ順序で抜き出した部分列であるため、C(πz∧πr)に含まれる点の集合は、必ずひとつながりの区間を形成するからである。
【００８３】
そして、本実施の形態では、このような性質が探索に利用される。まず、検索部１０は、初めにZ値接頭辞πzを条件として、C(πz)に対応するウェーブレット木のノードの座標部分列上の区間を計算する。次いで、検索部１０は、次元rの座標接頭辞πrを条件に加えてC(πz∧πr)に対応するウェーブレット木上のノードの座標部分列上の区間を計算する。
【００８４】
これにより、クエリ領域に包含される点の集合は、一つ以上のC(πz∧πr)に対応するような区間に含まれる点の集合の直和として表現される。そのような区間が得られれば、あとは各区間における統計量を合わせることで、クエリ領域に包含する点の統計量が得られる。
【００８５】
また、本実施の形態では、探索結果に必要な情報を表現するため、以下の２種類のノードVとノードYとが、各種情報を収めたタプルとして定義される。
V= (πz, <v1,[s1,e1] >, <v2, [s2,e2]>, <v3, [s3,e3] >, ..., <vd, [sd,ed]>)
Y = (πr , <vr,[sr,er] >)
【００８６】
ノードVは、C(πz)に対応する区間を探すための探索ノードである。以下では、ノードVを「Z値探索ノード」Vと呼ぶ。1≦k≦dの範囲の各次元kについて、次元kにおいてπzに対応する座標接頭辞をπkとおくとき、ノードVは、ウェーブレット木wk上においてπkに対応するノードvkと、座標部分列Pk(πk)上の区間[sk,ek]と、のペアを保持している。このとき、Pk(πk)[sk,ek]は、C(πz)に含まれる点に対応する区間であるとする。
【００８７】
ノードYは、特定の次元rに注目してC(πz∧πr)に対応する区間を保持するノードである。以下では、ノードYを「選定区間ノード」と呼ぶ。このノードYは、次元rのウェーブレット木wrにおいてπrに対応するノードvrと、座標部分列Pr(πr)においてC(πr∧πr)に対応する区間Pr(πr) [sr,er]と、を保持している。
【００８８】
本実施の形態における探索では、始め、Z値探索ノードVを用いて、C(πz)に対応する区間の探索が行なわれる。そして、C(πz)が特定の条件を満たすとき、次元rの接頭辞πrが条件に加えられ、C(πz∧πr)に対応する区間が探索される。その後、クエリ領域に含まれる点に対応する区間を保持している、選定区間ノードYが、探索結果として得られる。
【００８９】
［装置動作］
次に、本発明の実施の形態における情報処理装置１００の動作について図６を用いて説明する。図６は、本発明の実施の形態における情報処理装置の動作を示すフロー図である。また、以下の説明においては、適宜図１〜図４を参酌する。また、本実施の形態では、情報処理装置１００を動作させることによって、情報処理方法が実施される。よって、本実施の形態における情報処理方法の説明は、以下の情報処理装置１００の動作説明に代える。
【００９０】
図６に示すように、まず、入力受付部３０は、クエリ領域の範囲を指定するための外部からの入力を受付け（ステップＡ１）、受け付けた内容を検索部１０に出力する。この入力されたクエリ領域Qは、Q=[lq1, uq1]×[lq2, uq2]×…×[lqd, uqd]と表記される。
【００９１】
次に、検索部１０は、上述のように定義されるZ値探索ノードVに初期値を代入することによって、Vを初期化する（ステップＡ２）。具体的には、ステップＡ２では、Z値探索ノードVは、長さ0のZ値接頭辞πzに対応するように初期化される。また、各次元kにおいて長さ0のZ値接頭辞πzに対応する座標接頭辞πkは、同じく長さ0であり、ウェーブレット木のルートノードに対応する。すなわち、初期化により、各次元kに関して対応するノードvkは、ウェーブレット木wkのルートノードとなり、[sk,ek]=[0,n-1]に設定される。
【００９２】
次に、検索部１０は、記憶部５０に問い合わせを行なって、データ構造５１を取得する。そして、検索部１０は、クエリ領域Qについて、データ構造５１を対象として関数range_search(V,Q)を実行し、一つ以上の選定区間ノードの集合{Y}を返り値として取得する（ステップＡ３）。また、検索部１０は、取得した選定区間ノードの集合{Y}を、集計部２０に出力する。こうして得られた{Y}に含まれる各選定区間ノードYは、座標部分列の区間を保持しており、この区間に対応する点の集合は、互いに素(disjoint)となる。また、この区間に対応する点の集合の直和(disjoint union)は、クエリ領域に包含される点の集合と等しくなる。
【００９３】
次に、集計部２０は、検索部１０から、一つ以上の選定区間ノードの集合{Y}を受け取ると、関数aggregate({Y})を呼び出して、クエリ領域Qに包含される点の統計量resultを返り値として取得する（ステップＡ４）。また、集計部２０は、取得した統計量を出力部４０に出力する。この関数aggregate({Y})によれば、{Y}に含まれる各選定区間ノードYについて、Yが保持する区間に対応する点の集合に関する統計量が計算され、その後、それらの統計量が合わせられ、クエリ領域に包含される点に関する統計量が求められる。
【００９４】
最後に、出力部４０は、集計部２０から受け取った統計量を外部に出力する（ステップＡ５）。ステップＡ１〜ステップＡ５の実行により、クエリ領域Qについての探索処理は終了する。また、ステップＡ１〜ステップＡ５は、クエリ領域Qが入力される度に実行される。
【００９５】
［ステップＡ３］
続いて、図６に示したステップＡ３について、図７〜図１０を用いて更に具体的に説明する。図７は、再帰的に矩形範囲検索する関数range_search(V,Q)の動作を示すフロー図である。この関数は検索部１０が、記憶部５０に問い合わせを行なうことで実現される。
【００９６】
［ステップＡ３：概要］
図７のアルゴリズムについて詳細に説明する前に、図７のアルゴリズムの概要と、前提となる概念を説明する。
【００９７】
関数range_search(V,Q)は、長さ0のZ値接頭辞πzを引数にして呼び出され、さら、自らを再帰的に呼び出すことが可能な関数である。関数range_search(V,Q)は、自身を再帰的に呼び出す度に、Z値接頭辞πzを1ビットずつ延長し、延長された各πzについて対応するZ値探索ノードVを生成する。πzを1ビット延長することは、カバー領域C(πz)を二分割することに相当するため、πzが長くなるほどカバー領域は小さくなる。
【００９８】
そして、関数range_search(V,Q)は、カバー領域C(πz)が一定の条件を満たすと、再帰ループを抜けて、πrを追加し、これにより、カバー領域C(πz∧πr)を用いて空間を分割するフェイズに入る。そして、関数range_search(V,Q)は、このカバー領域C(πz∧πr)がクエリ領域Qに完全に包含されると、そのカバー領域に相当する、ウェーブレット木のノードの座標部分列の区間を保持する選定区間ノードYを返す。
【００９９】
ここで、この探索処理に必要になるZ値探索ノード V= (πz, <v1,[s1,e1] >, <v2, [s2,e2]>, <v3, [s3,e3] >, ..., <vd, [sd,ed]>)について、さらに詳しく説明する。また、ここでは、Z値接頭辞πzを考え、πzで始まるZ上の連続する区間をZ[sz,ez]とおく。πzで始まるZ[i]の数をnzで表すと、nz= ez - sz + 1が成り立つ。このnzは、カバー領域C(πz)に含まれる点の数に等しくなる。
【０１００】
上述したように、1からdの各次元において、πzに対応しているd個の座標接頭辞π1, π2, ..., πdが存在する。このとき、nz>0であれば、w1からwdの各ウェーブレット木に、これらの座標接頭辞に対応するノードv1, v2, ..., vdが必ず存在する。さらに、これらのノードにそれぞれに対応する座標部分列P1(π1), ..., Pd(πd)が存在する。
【０１０１】
さて、ここで、Z[sz,ez]の区間で、Z値がZ値接頭辞πzで始まるということは、1≦k≦dとなるkに関して、Pk[sz,ez]は、全て座標接頭辞πkから始まることを意味する。よって、この区間Pk[sz,ez]に含まれるnz個の連続する整数は、Pk(πk)においても全く同じ順序でnz個の連続する整数として含まれていることが分かる。この区間をPk(πk) [sk, ek]で表すものとする。このとき、nz = ez - sz+ 1 = ek - sk + 1が成り立ち、0≦i<nzとなる全てのiについて、Pk(πk) [sk +i] = Pk [sz+i]が成り立っている。
【０１０２】
また、Pk(πk) [sk, ek]の区間に含まれる座標は、Z値がπzで始まる点の座標であり、この点はカバー領域C(πz)に含まれる。よって、0≦i<nzとなる全てのiについて、lπk ≦ Pk(πk) [sk +i] ≦ uπk が成り立つ。Z値探索ノードVは、以上のような性質を持つZ値接頭辞πz、ノードvkおよび区間[sk, ek]を保持している。
【０１０３】
具体例を、図１、図４及び図５を用いて説明する。長さ3のZ値接頭辞πz ="011***"を考える。このZ値接頭辞を分解すると、Z値接頭辞πzに、次元1において長さ2の座標接頭辞π1 ="01*"と、次元2において長さ1の座標接頭辞π2 = "1**"と、が対応している。このとき、πzで始まるZの区間は、Z[sz,ez] = Z[2,3]である。nz=2である。
【０１０４】
このとき、次元1に着目する。P1[sz,ez] = {3,2}= {"011","010"}であるが、これらの値は座標接頭辞π1で始まるため、ウェーブレット木w1上でπ=π1のノードv1に対応する整数部分列P1(π1)に同じ順序で含まれる。この区間は、P1(π1)[s1,e1] = P1(π1)[0,1]である。
【０１０５】
同様に、次元2に着目する。P2[sz,ez] = {4,7}= {"100","111"}であるが、これらの値は座標接頭辞π2で始まるため、ウェーブレット木w2上でπ=π2のノードv2に対応する整数部分列P2(π2)に同じ順序で含まれる。この区間はP2(π2)[s2,e2] = P2(π2)[0,1]である。
【０１０６】
よって、上記のZ値接頭辞πzに対応するZ値探索ノードVは、以下の要素を保持している。
V= (πz, <v1,[s1,e1] >, <v2, [s2,e2]>) = ("011***", <v1,[0,1] >, <v2, [0,1] >)
【０１０７】
ここで、さらに、Z値探索ノード同士の間に親子関係を定義する。Z値接頭辞πzに対応するZ値探索ノードVがあるとき、πz+”0”に対応するZ値探索ノードをVの左の子、πz+”1”に対応するZ値探索ノードをVの右の子として定義する。たとえば、VがZ値接頭辞”111***”に対応するとき、Vの左の子はZ値接頭辞”1110**”に対応するZ値探索ノードであり、Vの右の子はZ値接頭辞”1111**”に対応するZ値探索ノードである。
【０１０８】
なお、以下では、Z値探索ノードVに含まれるπzのカバー領域のことを、Z値探索ノードVのカバー領域と呼ぶ。また、以下では、場合によって、Z値探索ノードVに含まれている要素を”.”で連結して表記するものとする。たとえば、Z値探索ノードVに含まれるZ値接頭辞πzは、V.πzと表記する。
【０１０９】
［ステップＡ３：具体例］
続いて、以上に述べた探索アルゴリズムの概要を踏まえて、図７に示すアルゴリズムについて、以下に詳細に説明する。
【０１１０】
図７に示すように、初めに、検索部１０は、Z値探索ノードVのカバー領域に点が存在するかどうかを判定する（ステップＢ１）。そして、検索部１０は、ステップＢ１の判定の結果、答えがYesであれば、ステップＢ２に進み、答えがNoであれば、空集合を返す。
【０１１１】
ステップＢ１では、任意の次元kについて、Z値探索ノードVのカバー領域に存在する点の数nz = ek- sk+1 が、0より大きいかどうかが調べられ、これにより判定が行なわれる。そして、ステップＢ１では、nz>0であれば、答えはYesであり、nz<=0であれば、答えはNoである。この判定は、πzで始まる点がひとつも存在しない場合に探索を打ち切るために必要な処理である。
【０１１２】
次に、検索部１０は、Z値探索ノードVのカバー領域がクエリ領域と重なるかどうかを判定する（ステップＢ２）。そして、検索部１０は、ステップＢ２の判定の結果、答えがYesであればステップＢ３に進み、答えがNoであれば空集合を返す。
【０１１３】
具体的には、ステップＢ２では、検索部１０は、Z値探索ノードVのカバー領域C(πz) = [lπ1,uπ1] × [lπ2,uπ2] × … × [lπd,uπd]をπzの値から求める。その上で、検索部１０は、1≦k≦dとなるkのどれかひとつの次元kにおいて、（uπk<lqk または uqk < lπk）が成り立つかどうかをチェックする。チェックの結果、上記関係が成り立つ場合は、空間上の重なりがないため、検索部１０は、Noと判定する。上記の関係が成り立たない場合は、空間上での重なりがあるため、検索部１０は、Yesと判定する。ステップＢ２の判定は、クエリ領域と重なりがないカバー領域をこれ以上探索しないように枝刈りすることが目的である。
【０１１４】
次に、検索部１０は、Z値探索ノードVのカバー領域とクエリ領域とを比較して、包含次元数hを計算する（ステップＢ３）。包含次元数hは、定義により、lqk≦ lπk かつ uπk ≦ uqkを満たすような次元kがいくつあるかを数えることで計算できる。
【０１１５】
次に、検索部１０は、包含次元数hがd-1よりも小さいかどうかを判定する（ステップＢ４）。検索部１０は、ステップＢ４の判定の結果、答えがYesであればステップＢ５に進み、答えがNoであればステップＢ６にて関数range_search_1d(V,Q)を返す。関数range_search_1d(V,Q)は、特定の次元rに注目してC(πz∧πr)による分割を行って、選定区間ノードの集合{Y}を返す関数である。
【０１１６】
次に、検索部１０は、VleftにZ値探索ノードVの左の子ノードを代入し、VrightにZ値探索ノードVの右の子ノードを代入する（ステップＢ５）。具体的には、検索部１０は、ステップＢ５では、Z値探索ノードVの情報を用いて、Vの左の子ノード、つまりπz+”0”に対応する探索ノードと、Vの右の子ノード、つまりπz+”1”に対応する探索ノードと、を計算する。なお、ステップＢ５については、図８を用いて後述する。ステップＢ５は、図８に示すアルゴリズムを実行することで実行することができる。
【０１１７】
その後、検索部１０は、ステップＢ５において、Z値探索ノードVの右の子ノードと左の子ノードとを求めたのち、同じ関数を以下のように再帰的に呼び出す。
return range_search(Vleft, Q) ∪range_search(Vright, Q)
【０１１８】
この再帰的呼び出しによって、検索部１０は、カバー領域が半分になった接頭辞πzについて、同じ計算を繰り返すことができる。
【０１１９】
［ステップＢ５：概要］
続いて、図８を用いて、ステップＢ５における処理を具体的に説明する。図８は、Z値探索ノードVの左右の子ノードを計算する関数get_children(V)の動作を示すフロー図である。この関数get_children(V)も、検索部１０が、記憶部５０に問い合わせることで実現される。
【０１２０】
まず、図８に示すアルゴリズムについて詳細に説明する前に、どのようにしてZ値探索ノードVから左右の子ノードが計算できるかについて説明する。
【０１２１】
まず、Z値探索ノードVが対応しているZ値接頭辞πzの末尾にビットbを追加した新たなZ値接頭辞をπ’zとおいて、π’zに対応する新たなZ値探索ノードV’を計算することを考える。bが0の場合、Z値探索ノードV’は、Z値探索ノードVの左の子ノードに当たり、bが1の場合、Z値探索ノードV’はZ値探索ノードVの右の子ノードに当たる。以下では、V’=(π’z, <v’1,[s’1,e’1]>, <v’2, [s’2,e’2]>, <v’3,[s’3,e’3]>, ..., <v’d,[s’d,e’d]>)とおく。
【０１２２】
そして、次元g = length(πz) mod d + 1とおくと、次元gに関して、以下の式が成り立つ。なお、上記において、length()は接頭辞の長さを表す。
π’k= πk+b     (k=g のとき)
πk       (それ以外のとき) 
【０１２３】
すなわち、πzに対応するZ値探索ノードVから、π’zに対応するZ値探索ノードV’を計算するとき、次元k(≠g)については、π’zに対応する座標接頭辞π’kは、πzに対応する座標接頭辞πkと同じである。しかし、次元gにおいてπ’zに対応する座標接頭辞π’gは、πzに対応する座標接頭辞πgにビットbを付加したものになる。π’g=πg +bであることから、ウェーブレット木wg上において、π’gに対応するノードv’gは、πg に対応するノードvgの子ノードとなる。
【０１２４】
具体的には、図１、図４、及び図５に示すように、Z値接頭辞πz = "011***"に、座標接頭辞π1="01*"とπ2="1**"が対応する。このとき、b=1の場合、すなわちπ’z= πz + "1"= "0111**"を考えると、π’z = "0111**"は、π’1="01*"とπ’2="11*"に対応する。また、g = length(πz) mod d + 1 = 3 mod 2 + 1 = 2である。
【０１２５】
上記の結果をみると、π’1=π1、かつ、π’2=π2+bであり、確かに、次元g=2にビットbが追加されていることが分かる。b=1であることから、π’gに対応するノードv’gは、πgに対応するノードvgの右の子ノードである。
【０１２６】
ここで、唯一座標接頭辞が変化する次元gのウェーブレット木wgに着目する。πz に対応する区間Pg(πg)[sg,eg]は既に分かっているため、これをもとにπ’z＝πz+bに対応する区間Pg(π’g)[s’g,e’g]を求めることを考える。
【０１２７】
ウェーブレット木wg上で、πgに対応するノードvgが保持しているビット列 Bvgに注目する。ビット列Bvg[sg,eg]は、Pg(πg)[sg,eg]のlength(πg )+1番目のビットを取り出して連結したものである。Pg(πg)[sg,eg]の座標は、Z[sz,ez]のZ値と同じ順序で同じ点に対応しているため、ビット列Bvg[sg,eg]は、Z[sz,ez]のlength(πz)+1番目のビットを取り出して連結したものに等しくなる。Z値は、昇順にソートされており、Z[sz,ez]は全てπz で始まっているから、length(πz)+1番目のビットを取り出して連結したものである、ビット列Bvg[sg,eg]は、”000…000111…111”のように、0だけが連続して並ぶ前半と1だけが連続して並ぶ後半とに分割できることが保証される。
【０１２８】
ビット列Bvg[sg,eg]に出現する0の数をnz0、1の数をnz1とおく。また、nz = nz0 + nz1である。さきほどの考察により、ビット列Bvg[sg,sg+nz0-1]のビットは、全て0である。Bvg[sg+nz0, eg]のビットは全て1である。このことは、すなわち、Z[sz,sz+nz0-1]の区間がπz+"0"で始まり、Z[sz+nz0,ez]の区間がπz+"1"で始まることを示している。これによって、π’z =πz+"0"であれば、[s'z,e'z]=[sz,sz+nz0-1]であり、π’z =πz+"1"であれば、[s'z,e'z]=[sz+nz0,ez]であると計算できる。nz0は、ビット列Bvgの完備辞書を用いてnz0 = rank0(Bvg,eg+1) - rank0(Bvg,sg)という式で計算できる。nz1はnz1 = nz - nz0で計算できる。
【０１２９】
b=0であれば、π’gに対応するノードv'gは、πgに対応するノードvgの左の子ノードである。さらに、Pg(π’g)上でπ’zに対応する区間[s'g,e'g]を以下のように計算できる。つまり、s'g = rank0(Bvg,sg)、およびe'g = s'g + nz0-1である。何故なら、任意のiについてBvg[i]のビットが0であることは、対応する整数Pg(πg) [i]が、π’g=πg+”0”で始まることを表しており、そのようなビット0に対応する整数だけがPg(πg)から抜粋され、Pg(π’g)に含まれるからである。
【０１３０】
同様に、b=1であれば、ノードv'gは、ノードvgの右の子ノードであり、ノードv'g上で対応する区間も、上記のb=0の場合と同様に計算できる。また、s'g = rank1(Bvg,sg)、およびe'g = s'g + nz1-1である。以上のように、次元gにおいて、座標接頭辞π’gに対応するPg(π’g)において、π’zに対応する区間Pg(π’g) [s'g,e'g]を求めることができる。
【０１３１】
k ≠ gとなる他の次元についても検討する。これらの次元kにおいては、π’k=πk であるので、同じ座標部分列Pk(π’k) =Pk(πk)上で、π’zに対応する範囲を求めることになる。ここで、もともとπzで始まる区間Z[sz,ez]に対応する区間が[sk,ek]であることが分かっているので、これを前後に分割し、π’z =πz+"0"であれば、[s'k,e'k]=[sk,sk+nz0-1]となるよう更新し、π’z =πz+"1"であれば、[s'k,e'k]=[sk+nz0,ek]となるよう更新すれば、π’zに対応する区間が求まる。
【０１３２】
以上により、πzに対応するZ値探索ノードVが与えられたとき、1ビット追加されたπ’zについても対応するZ値探索ノードV’に含まれる情報が計算できることが分かった。つまり、πz+”0”に対応する左の子ノードVleft、およびπz+”1”に対応する右の子ノードVrightを計算できる。
【０１３３】
具体的には、事実として、πz = "011***"、π1="01*"、π2="1**"、Z[sz,ez] = Z[2,3]、P1(π1)[s1,e1]=P1(π1)[0,1]、P2(π2)[s2,e2]=P2(π2)[0,1]、が分かっているものとする。また、b=1であるとする。このとき、π’z = πz + "1"= "0111**"に対応する区間を、次のように求めることができる。
【０１３４】
つまり、π’1=π1="01*"であり、π’2=π2+"1"="11*"であるから、座標接頭辞が変化するのは次元g=2だけである。よって、次元g=2のウェーブレット木に注目して、P2(π2)[s2,e2]からP2(π’2)[s'2,e'2]を計算することを考える。
【０１３５】
ノードv2の保持するビット列はBv2="0101"であるから、Bv2[s2,e2]=Bv2[0,1]="01"であり、nz0=1およびnz1=1である。Bv2[0,1]は、Z[2,3]の区間の4ビット目に対応しているため、ここからZ[2]の4ビット目が0であり、Z[3]の4ビット目が1であることが分かる。従って、b=1であるから、v'2はv2の右の子であり、s'2= rank1(Bv2,s2) = 0、およびe'2= s'2 + nz1 -1 = 0+1-1=0である。
【０１３６】
同様に、次元1においても、長さ2の領域が長さ1ずつの領域に分割されるため、新たな区間は以下のように計算される。
[s'1,e'1] =[s1+nz0,e1]=[0+1,1]=[1,1]
【０１３７】
以上により、π’zに関して以下の値が計算できる。
π’z= "0111**"、π’1="01*"、π’2="11*"、Z[s'z,e'z] = Z[3,3]、P1(π’1)[s'1,e'1]=P1(π’1)[1,1]、P2(π’2)[s'2,e'2]=P2(π’2)[0,0]
【０１３８】
［ステップＢ５：具体例］
上述した考察をアルゴリズムの形にしたものが図８に示すアルゴリズムである。図８に示すアルゴリズムについて、以下に詳細に説明する。また、図８に示すアルゴリズムにおいては、以下のようにZ値探索ノードVの左右の子ノードを計算する処理が実行される。更に、VleftをZ値探索ノードVの左の子ノードを表すタプルとし、VrightをZ値探索ノードVの右の子ノードを表すタプルとする。
【０１３９】
まず、図８に示すように、最初に、検索部１０は、VleftにZ値探索ノードVの内容をコピーし、VrightにもZ値探索ノードVの内容をコピーする（ステップＣ１）。これにより、VleftとVrightとのそれぞれに含まれるウェーブレット木のノードvkは、ともにZ値探索ノードVに含まれるウェーブレット木のノードvkと同一になる。
【０１４０】
次に、VleftとVrightとがそれぞれ含んでいるπkおよびvkについて、Z値探索ノードVとの差分を更新する（ステップＣ２）。すなわち、g = length(πz) mod d + 1として、Vleft.πz = V.πz+”0”を代入し、Vright.πz = V.πz + “1”を代入する。さらに、Vleft.vgにはV.vgの左の子ノードを代入し、Vright.vgにはV.vgの右の子ノードを代入する。また、nz = eg - sg + 1である。nz0は、ビット列Bvgの完備辞書を用いてnz0 = rank0(Bvg,eg+1) - rank0(Bvg,sg)という式で求められる。nz1はnz1 = nz - nz0によって計算される。
【０１４１】
次に、検索部１０は、区間[sk,ek]を計算するため、次元kについてループを回す（ステップＣ３）。次に、検索部１０は、このループの中で、k=gが成り立つかどうかを判定する（ステップＣ４）。そして、検索部１０は、ステップＣ４の判定の結果、YesならステップＣ５に移り、NoならステップＣ６に移る。
【０１４２】
ステップＣ４の判定の結果、Yesの場合、即ち、k=gが成り立つ場合は、検索部１０は、次元gについて計算する（ステップＣ５）。ステップＣ５では、Vleft.sg = rank0(Bvg,sg)、およびVleft.eg= Vleft.sg + nz0 -1である。さらに、Vright.sg = rank1(Bvg,sg) 、およびVright.eg = Vright.sg + nz1 -1である。
【０１４３】
一方、ステップＣ４の判定の結果、Noの場合、即ち、k=gが成り立たない場合は、検索部１０は、次元g以外のkについて計算する（ステップＣ６）。ステップＣ６では、Vleft.sk = V.sk、およびVleft.ek = V. sk+nz0-1である。さらに、Vright.sk = V. sk+nz0、およびVright.ek = V. ekである。
【０１４４】
次元kについてループが終了すると（ステップＣ７）、その後、VleftおよびVrightが返され、ステップＢ５は終了する。このように、図８に示すアルゴリズムは、Z値探索ノードVの左右の子ノードを計算する。
【０１４５】
以上により、図７に示すアルゴリズムにおいて、ステップＢ４でYesになる場合の動作について説明を終えた。次いで、ステップＢ４でNoになる場合の動作について説明する。すなわち、図７中の関数range_search_1d(V,Q)の動作について説明する。
【０１４６】
［ステップＢ６：概要］
続いて、図７に示したステップＢ６について、図９及び図１０を用いて説明する。関数range_search_1d(V,Q)は、Z値探索ノードVとクエリ領域Qとを入力として、クエリ領域Qに包含されるようなカバー領域C(πz∧πr)に対応する区間を保持する選定区間ノードYを返す関数である。
【０１４７】
まず、図９および図１０に示すアルゴリズムについて詳細に説明する前に、動作の概要について説明する。
【０１４８】
図７に示すステップＢ４において、Noになる場合、すなわち、接頭辞πzのカバー領域C(πz)の包含次元数がd-1に達した場合を考える。包含次元数がd-1に達したということは、d-1個の次元において、すでに包含条件が満たされたことを示している。このとき、残り1個の、まだ包含されていない次元を次元rとする。次元rにおいてπzに対応する座標接頭辞πrを考え、πzに対応する区間Pr (πr)[sr,er]に注目する。上述したように、この区間には、Pr[sz,ez]と同じ座標が同じ順序で含まれている。
【０１４９】
P[sz,ez]に含まれる全ての点は、πzのカバー領域に含まれるため、次元r以外の全ての包含条件を満たすが、次元rの包含条件は満たしていない。すなわち、次元rの座標の値prが[lqr, uqr]に包含されるという条件をまだ満たしていない。
【０１５０】
そこで、図９および図１０のアルゴリズムでは、πrだけを延長してカバー領域を小さくすることにより、クエリ領域に包含するようなカバー領域が形成される。すなわち、次元rにおいて [lqr, uqr]に包含されるようなカバー領域C(πz∧π’r)が得られるまで、πrを延長した座標接頭辞をπ’rとして、その結果得られるカバー領域に対応する座標部分列上での区間を保持する選定区間ノードが返される。
【０１５１】
［ステップＢ６：具体例］
次に、図７に示したステップＢ６を具体的に説明する。図９は、図７に示す関数range_search_1d(V,Q)の動作を示す図である。図９に示すように、検索部１０は、関数range_search_1d(V,Q)を呼び出し、Z値探索ノードVのカバー領域が、クエリ領域Qに包含されていない次元rを計算する（ステップＤ１）。
【０１５２】
次に、検索部１０は、次元rにおいてπzに対応する接頭辞πrを求める（ステップＤ２）。続いて、検索部１０は、ステップＤ２で求められた値を用いて、以下のように再帰的な関数を呼び出し、図１０に示す各ステップを実行する。
return  range_search_1d_rec(πr, V.vr, V.sr, V.er, Q.lqr, Q.uqr)
【０１５３】
ここで、図１０による詳細な説明に入る前に、関数range_search_1d_rec(πr, vr, sr, er, lqr, uqr)の概要について説明する。この関数range_search_1d_rec(πr, vr, sr, er, lqr, uqr)は、Z値がπzで始まり、次元rの座標の値prが[lqr, uqr]に包含されるような座標部分列Pr (π’r)上の区間Pr(π’r) [s’r, e’r]を返す再帰的な関数である。すなわち、この関数は、クエリ領域Qに完全に包含されるようなカバー領域C(πz∧π’r)に対応する区間を返す関数である。ただし、π’rは接頭辞πrを延長して得られる座標接頭辞とする。
【０１５４】
そして、関数range_search_1d_rec(πr, vr, sr, er, lqr, uqr)による操作は、区間の左端であるs’rと、右端であるe’rと、を各ノード上で計算することで実現できる。まず、初めに、接頭辞πrに対応するノードvrの座標部分列上の区間Pr (πr) [sr,er]を考える。
【０１５５】
ただし、この区間は、Z値がπzで始まる点に対応する区間であるとする。このとき、この探索ノードvrの、ウェーブレット木における左の子ノードvleftと右の子ノードvrightについて考える。子ノードに対応する接頭辞をπ’rとおくとき、Pr (π’r)[s’r,e’ r]は、Pr(πr) [sr,er]の区間から、π’rで始まる整数だけを抜き出してきた部分列に対応する区間を表すものとする。
【０１５６】
ウェーブレット木の定義により、左の子ノードに移動するときは s’ r = rank0(Bvr,sr) およびe’ r = rank0(Bvr,er+1)-1 という式によって、区間[s’ r,e’ r]を求めることができる。一方、右の子ノードに移動するときは、s’ r = rank1(Bvr, sr)とe’ r=rank1(Bvr, er+1)-1という式によって、区間[s’ r,e’ r]を求めることができる。
【０１５７】
以上の操作が、各ノードについて繰り返し実行され、ノードの対応する接頭辞π’rで始まる座標の値が全て[lqr,uqr]に包含された場合に、そのノード上での区間Pr (π’r)[s’ r,e’ r]を収めた選定区間ノードYが返される。この区間には、[lqr,uqr]の範囲の座標しか出現していないため、この区間は、次元rの範囲条件を満たす点に対応している。すなわち、選定区間ノードYは、クエリ領域に完全に包含されている点に対応している。また、以上の操作における計算量は、ウェーブレット木について既に知られている二次元のrange countの計算量と等しく、O(log n)である。
【０１５８】
続いて、図１０を用いて、関数range_search_1d_rec(πr, vr, sr, er, lqr, uqr)の動作を詳細に説明する。図１０は、図９に示された関数range_search_1d_rec(πr, vr, sr, er, lqr, uqr)の動作を示す図である。
【０１５９】
図１０に示すように、検索部１０は、関数range_search_1d_rec(πr, vr, sr, er, lqr, uqr)を実行して、sr> er または ([lπr, uπr] ∩ [lqr, uqr]) = φ が成り立つかどうかを判定する（ステップＥ１）。そして、検索部１０は、ステップＥ１の判定の結果、答えがNoであれば、ステップＥ２に進み、答えがYesであれば、空集合を返す。なお、[lπr, uπr]は、πrで始まる整数の区間を表している。
【０１６０】
次に、検索部１０は、 [lπr, uπr] ⊆ [lqr, uqr] が成り立つかどうかを判定する（ステップＥ２）。なお、[lπr, uπr]は、πrで始まる整数の区間を表している。
【０１６１】
ステップＥ２の判定の結果、答えがYesであれば、つまり、[lπr, uπr] ⊆ [lqr, uqr] が成り立つときは、カバー領域がクエリ領域に完全に包含される。従って、検索部１０は、この区間[lπr, uπr]を、選定区間ノードY = (πr, <vr, [sr ,er]>)に代入して返却する（ステップＥ３）。
【０１６２】
一方、ステップＥ２の判定の結果、答えがNoであれば、検索部１０は、πr に対応するノードvrのビット列をBvrとおいて、図１０中に示す４つのrankの式を用いて、左の子ノードにおける区間[sleft, eleft]と、右の子ノードにおける区間[sright, eright]とを計算する（ステップＥ４）。
【０１６３】
その後、検索部１０は、右の子ノード、および左の子ノードについて、同様の処理を行うため、再帰的に以下の関数を呼び出す。
return range_search_1d_rec(πr+”0”, vleft, sleft, eleft, lqr, uqr) ∪ range_search_1d_rec(πr+”1”, vright, sright, eright, lqr, uqr)
【０１６４】
［ステップＡ４］
続いて、図６に示したステップＡ４で呼び出される関数aggregate({Y})について説明す
る。この関数は集計部２０によって実行される。
【０１６５】
集計部２０は、関数aggregate({Y})によって、{Y}に含まれる各選定区間ノードYについて、選定区間ノードYに対応する区間に対応する点の集合に関する統計量を計算し、その後、それらの統計量を用いて、クエリ領域Qに包含される点に関する統計量を求めることができる。
【０１６６】
また、関数aggregate({Y})は、様々な集計関数を抽象化したものであり、この関数を、具体的な集計関数に置き換えることで、情報処理装置１００を様々な種類の矩形範囲検索に利用できる。
【０１６７】
たとえば、情報処理装置１００は、クエリ領域Qに含まれる点の数のカウントに使うことができる。具体的には、入力{Y}に選定区間ノードY = (πr, <vr, [sr ,er]>)が含まれている場合、座標部分列上の区間Pr (πr)[s r,e r]がクエリ領域Qに含まれる点に対応している。このことは、この区間に含まれる(e r - s r +1)個の点が、クエリ領域Qに含まれていることを表している。すなわち、得られた選定区間ノードYの全てについて(er - s r +1)を合計すれば、クエリ領域に含まれる点の数が計算できる。この場合、集計部２０は、クエリ領域Qに含まれる点の数を統計量として出力する。
【０１６８】
また、たとえば、全ての点pに重みw(p)が付与されているとき、情報処理装置１００は、クエリ領域に含まれる点の重みの合計を計算することができる。これは、あらかじめ、全ての座標部分列Pr (πr)に含まれる各座標について、対応する点pの重みw(p)を同じ順番で並べた列Wr(πr)が設定されている場合に、この列上での区間合計を計算できるようなデータ構造が用意されていれば可能となる。
【０１６９】
このようなデータ構造としては、既存のPartial Sumを扱うデータ構造が挙げられる。また、このようなデータ構造であれば、座標部分列上の区間Pr (πr)[s r,e r]がクエリ領域に含まれる点に対応していることが分かっているとき、この区間[s r,e r]に対応する重みの列上の区間Wr(πr) [s r,e r]に含まれる重みの区間合計を計算し、最後に足し合わせることで、クエリ領域Qに含まれる全ての点の重みの合計が計算できる。この場合、集計部２０は、クエリ領域Qに含まれる全ての点の重みの合計を統計量として出力する。
【０１７０】
同様に、情報処理装置１００は、クエリ領域Qに含まれる全ての点のリストを返すレポート・クエリとしても用いることができる。つまり、座標部分列上の区間Pr (πr)[s r,e r]について、この区間に含まれる各要素Pr(πr)[j]について、元の整数列Pr上での位置iを、ウェーブレット木をさかのぼることによって特定できる。このとき、点P[i]がクエリ領域に含まれる。この場合、集計部２０は、クエリ領域Qに含まれる全ての点のリストを統計量として出力する。
【０１７１】
以上のように、本実施の形態によれば、様々な種類の矩形範囲検索を実現することができる。また、本実施の形態は、図６〜図１０に示したアルゴリズムが単独で用いられる態様に限定されず、図６〜図１０に示したアルゴリズムに、適宜他の探索アルゴリズムが組み合わされた態様であってもよい。
【０１７２】
たとえば、本実施の形態では、図６〜図１０に示したアルゴリズムに、単純なスキャン処理が組み合わされていても良い。図６〜図１０に示したアルゴリズムでは、Z値探索ノードVで、Z値の列Z上の範囲Z[sz,ez]を分割することによって、探索が実行されている。しかし、範囲Z[sz,ez]が狭くなった場合は、ウェーブレット木の構造をそのままたどるよりも、座標列Pkの対応する範囲Pk[sz,ez]をスキャンして、ひとつひとつの値Pk[i]が条件を満たすかどうかを直接チェックしたほうが高速となる。よって、このため、上述したようにスキャン処理が組み合わされる。また、この場合、座標列Pkを保持する必要があるが、合計のデータ構造はやはり線形サイズとなる。
【０１７３】
［実施の形態による効果］
本実施の形態は、kd木よりも計算量が少なくなる効果がある。このことを明らかにするため、最悪計算量について解析する。通常のkd木は、包含次元数がdになるまで分割する手法であるのに対して、本実施の形態における手法は、d-1になるまで分割する手法である。このことが最悪計算量におよぼす影響を以下に述べる。
【０１７４】
まず、kd木、本実施の形態における手法のように、木構造において、深さ毎に、次元を順番に切り替えて空間を二分割する探索に関して、木構造がバランスしているときのノードの分割数を見積もる。計算量が最悪になるのは、空間分割数が最大になるときである。つまり、１回の分割で生じた２つのカバー領域が、常にクエリ領域と重なってしまう場合
である。
【０１７５】
図１１に、最悪な場合の探索ノード数と包含次元数の関係を示す。図１１は、２次元の場合の探索ノード数と包含次元数との変化を示す図である。図１１に示すように、木構造上のひとつのノードは、ひとつの探索ノードに対応している。木構造の深さが１つ下がることは、ノードが１回分割されて２つの探索ノードに分割されることを表している。ノード上の数字は、包含次元数を表している。分割されるほど、包含次元数が高いノードが増えていくことが分かる。
【０１７６】
ここで、d回の分割をまとめて考える。深さm * dにおいて包含次元数hになるノードの数をTh(m)とおいて、Th(m)とTh(m-1)のあいだに成り立つ漸化式を考える。d回の分割により、1つのカバー領域が2d個のカバー領域に分割される。このとき、必ず各次元で１回の分割が生じる。すでに包含されている次元について分割されても包含次元数は上がらないことを考えると、深さm * dにおいて、包含次元数がhになるノードの数を求めるには、深さ(m-1) * dにおいて包含次元数がi(≦ h)だったノードから、h-i個の次元が新たに包含される数を考えればよい。
【０１７７】
この漸化式は、以下の数１に示す通りとなる。ただし、以下の数１において、C(x,y)は組み合わせの数を表すものとする。
【０１７８】
【数１】
2016043121.tif 000003
【０１７９】
上記の数１から、d回の分割により、全体のノード数は2d倍に増加するが、そのうち包含次元数hのノードは2h倍に増加することが分かる。
【０１８０】
また、この分割をlog(n)/d回繰り返すと、探索木全体は深さlog nの二分木になり、全体のノード数はO(n)に達して分割が終了する。そのうち包含次元数hのノードは、O(n(h/d))となる。ただし包含次元数0のノードはO(log n)である。
【０１８１】
よって、以下のように言うことができる。まず、まったく探索を打ち切らなければ分割数は最大でO(n)になる。また、包含次元数がdに達した時点で分割を打ち切れば、分割数はO(n(d-1)/d)となる。一方、包含次元数がd-1に達した時点で分割を打ち切れば、分割数はO(n(d-2)/d)となる。そして、kd木では、包含次元数がdに達した時点で分割が打ち切られるため、計算量はO(n(d-1)/d)となる。これは従来から知られているオーダと一致する。
【０１８２】
また、このkd木での解析を、本実施の形態に適用することができる。つまり、本実施の形態における探索でいうZ値探索ノードは、空間を各次元で交互に分割するため、kd木と同じ手法で計算量を見積もれるからである。ただし、本実施の形態に合わせて、少し修正が必要である。
【０１８３】
本実施の形態では、包含次元数がd-1に達した時点で分割が打ち切られるので、分割数、すなわちZ値探索ノードの数は最大でO(n(d-2)/d)となる。ただし、Z値の長さはd log nであり、Z値探索ノードには、子ノードが1つだけのノードも存在し得るので、分割で生じた各Z値探索ノードにつき、最悪でd log n回の不要な計算が発生する。dを定数と見なすとO(log n)の計算である。
【０１８４】
また、各Z値探索ノードについて、range_search_1dにO(log n)の計算が必要である。これにより、本実施の形態における手法は、O(n(d-2)/d)個のZ値探索ノードについて、それぞれO(log n) + O(log n)の計算が必要になり、合計の計算量はO(n(d-2)/d log n)となる。
【０１８５】
ただし、d=2の場合は特殊である。d-1=1次元が包含された時点で探索ループを抜けるので、分割されたノードの数は、包括次元数が0となるノードの数O(log n)に比例する。各ノードについてO(log n)の計算が必要になるので、d=2の場合の計算量はO(log2n)となる。
【０１８６】
以上はクエリ領域に包含される点を数えるカウント・クエリの場合であるが、包含される点全てについてリストを出力するレポート・クエリには、出力される点の数をFとして、それぞれについてO(log n)の計算時間がかかる。まとめると、図１２に示す通りとなる。図１２に示すように、本発明によれば、kd木を用いて探索処理を行なう場合よりも計算量のオーダが改善されており、しかも従来のウェーブレット木と異なり、３次元以上にも適用できる。図１２は、本発明と従来手法との計算量の比較を示す図である。
【０１８７】
［プログラム］
本発明の実施の形態におけるプログラムは、コンピュータに、図６に示すステップＡ１〜Ａ５を実行させるプログラムであれば良い。このプログラムをコンピュータにインストールし、実行することによって、本実施の形態における情報処理装置と情報処理方法とを実現することができる。この場合、コンピュータのＣＰＵ（Central Processing Unit）は、検索部１０、集計部２０、入力受付部３０、及び出力部４０として機能し、処理を行なう。また、本実施の形態では、記憶部５０は、コンピュータに備えられたハードディスク等の記憶装置に、これらを構成するデータファイルを格納することによって実現される。
【０１８８】
なお、本実施の形態におけるプログラムは、複数のコンピュータによって構築されたコンピュータシステムによって実行されても良い。この場合は、例えば、各コンピュータが、それぞれ、検索部１０、集計部２０、入力受付部３０、及び出力部４０として機能しても良い。また、記憶部５０は、本実施の形態におけるプログラムを実行するコンピュータとは別のコンピュータ上に構築されていても良い。
【０１８９】
ここで、本実施の形態におけるプログラムを実行することによって、情報処理装置１００を実現するコンピュータについて図１３を用いて説明する。図１３は、本発明の実施の形態における情報処理装置を実現するコンピュータの一例を示すブロック図である。
【０１９０】
図１３に示すように、コンピュータ１１０は、ＣＰＵ１１１と、メインメモリ１１２と、記憶装置１１３と、入力インターフェイス１１４と、表示コントローラ１１５と、データリーダ／ライタ１１６と、通信インターフェイス１１７とを備える。これらの各部は、バス１２１を介して、互いにデータ通信可能に接続される。
【０１９１】
ＣＰＵ１１１は、記憶装置１１３に格納された、本実施の形態におけるプログラム（コード）をメインメモリ１１２に展開し、これらを所定順序で実行することにより、各種の演算を実施する。メインメモリ１１２は、典型的には、ＤＲＡＭ（Dynamic Random Access Memory）等の揮発性の記憶装置である。また、本実施の形態におけるプログラムは、コンピュータ読み取り可能な記録媒体１２０に格納された状態で提供される。なお、本実施の形態におけるプログラムは、通信インターフェイス１１７を介して接続されたインターネット上で流通するものであっても良い。
【０１９２】
また、記憶装置１１３の具体例としては、ハードディスクドライブの他、フラッシュメモリ等の半導体記憶装置が挙げられる。入力インターフェイス１１４は、ＣＰＵ１１１と、キーボード及びマウスといった入力機器１１８との間のデータ伝送を仲介する。表示コントローラ１１５は、ディスプレイ装置１１９と接続され、ディスプレイ装置１１９での表示を制御する。
【０１９３】
データリーダ／ライタ１１６は、ＣＰＵ１１１と記録媒体１２０との間のデータ伝送を仲介し、記録媒体１２０からのプログラムの読み出し、及びコンピュータ１１０における処理結果の記録媒体１２０への書き込みを実行する。通信インターフェイス１１７は、ＣＰＵ１１１と、他のコンピュータとの間のデータ伝送を仲介する。
【０１９４】
また、記録媒体１２０の具体例としては、ＣＦ（Compact Flash（登録商標））及びＳＤ（Secure Digital）等の汎用的な半導体記憶デバイス、フレキシブルディスク（Flexible Disk）等の磁気記憶媒体、又はＣＤ−ＲＯＭ（Compact Disk Read Only Memory）などの光学記憶媒体が挙げられる。
【０１９５】
また、上述した実施の形態の一部又は全部は、以下に記載する（付記１）〜（付記２１）によって表現することができるが、以下の記載に限定されるものではない。  
【０１９６】
（付記１）
多次元空間上の点の集合を表現するデータ構造を処理対象とする情報処理装置であって、
前記点の特徴値を表すビット表現から得られる接頭辞を特徴値接頭辞とし、前記点の特定の次元での座標を表すビット表現から得られる接頭辞を座標接頭辞として、
クエリ領域として、特定の多次元の領域が指定された場合に、
前記データ構造を構築している多次元の領域において、前記特徴値接頭辞で始まる領域と次元毎の前記座標接頭辞で始まる領域との共通部分として表現され、且つ、前記クエリ領域に含まれる、領域を特定し、
特定した領域に対応するデータ構造上の区間である選定区間を出力する、検索部と、
前記選定区間を用いて前記クエリ領域に含まれる点の集合に関する情報を計算する、集計部と、
を備えていることを特徴とする情報処理装置。
【０１９７】
（付記２）
前記データ構造が、
多次元上の前記点の集合それぞれの前記特徴値を、昇順に並べて得られる、特徴値列から、各次元について、前記特徴値の並び順と同じ順序で、各点の当該次元での座標を取り出すことで得られる座標列を用いて、次元毎に、前記座標列から、座標のビット表現が同じ座標接頭辞で始まる座標だけを、前記順番と同じ順序を保ったまま抽出して得られる部分列の、ビット表現の一部を用いて表現され、且つ、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されており、
前記検索部が、
前記部分列上の区間であって、当該区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、当該区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
付記１に記載の情報処理装置。
【０１９８】
（付記３）
前記検索部が、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間について、この区間に含まれる座標に対応する点の集合が前記クエリ領域に完全に包含される区間であるかどうかを判定し、
判定の結果、前記クエリ領域に完全に包含される区間ではない場合に、
前記判定の対象となった前記部分列の抽出に用いられる前記座標接頭辞を延長して、第二の座標接頭辞を設定し、
そして、前記第二の接頭辞を用いて座標を抽出して得られた第二の部分列上の区間であって、前記第二の部分列上の区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、前記第二の部分列上の区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
付記２に記載の情報処理装置。
【０１９９】
（付記４）
前記点の特徴値が、前記点の各次元の座標のビット表現を交互に組み合わせて得られるビット表現に基づく値である、
付記１に記載の情報処理装置。
【０２００】
（付記５）
前記データ構造が、複数のノードを有し、前記複数のノードそれぞれは、前記部分列に対応する各座標のビット表現における特定の桁のビットだけを取り出し、前記部分列と同じ順序で並べた前記ビットの列を用いて表現され、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されている、
付記２に記載の情報処理装置。
【０２０１】
（付記６）
前記集計部が、前記情報として、前記選定区間の長さを合計した値を計算し、計算した値を出力する、
付記１に記載の情報処理装置。
【０２０２】
（付記７）
前記集計部が、前記情報として、前記選定区間に含まれる各次元の座標を全て計算し、計算した全ての座標を出力する、
付記１に記載の情報処理装置。
【０２０３】
（付記８）
多次元空間上の点の集合を表現するデータ構造を処理対象とする情報処理方法であって、
（ａ）前記点の特徴値を表すビット表現から得られる接頭辞を特徴値接頭辞とし、前記点の特定の次元での座標を表すビット表現から得られる接頭辞を座標接頭辞として、
クエリ領域として、特定の多次元の領域が指定された場合に、
前記データ構造を構築している多次元の領域において、前記特徴値接頭辞で始まる領域と次元毎の前記座標接頭辞で始まる領域との共通部分として表現され、且つ、前記クエリ領域に含まれる、領域を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定した領域に対応するデータ構造上の区間である選定区間を出力する、ステップと、
（ｃ）前記選定区間を用いて前記クエリ領域に含まれる点の集合に関する情報を計算する、ステップと、
を有することを特徴とする情報処理方法。
【０２０４】
（付記９）
前記データ構造が、
多次元上の前記点の集合それぞれの前記特徴値を、昇順に並べて得られる、特徴値列から、各次元について、前記特徴値の並び順と同じ順序で、各点の当該次元での座標を取り出すことで得られる座標列を用いて、次元毎に、前記座標列から、座標のビット表現が同じ座標接頭辞で始まる座標だけを、前記順番と同じ順序を保ったまま抽出して得られる部分列の、ビット表現の一部を用いて表現され、且つ、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されており、
前記（ａ）のステップにおいて、
前記部分列上の区間であって、当該区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、当該区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
付記８に記載の情報処理方法。
【０２０５】
（付記１０）
前記（ａ）のステップにおいて、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間について、この区間に含まれる座標に対応する点の集合が前記クエリ領域に完全に包含される区間であるかどうかを判定し、
判定の結果、前記クエリ領域に完全に包含される区間ではない場合に、
前記判定の対象となった前記部分列の抽出に用いられる前記座標接頭辞を延長して、第二の座標接頭辞を設定し、
そして、前記第二の接頭辞を用いて座標を抽出して得られた第二の部分列上の区間であって、前記第二の部分列上の区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、前記第二の部分列上の区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
付記９に記載の情報処理方法。
【０２０６】
（付記１１）
前記点の特徴値が、前記点の各次元の座標のビット表現を交互に組み合わせて得られるビット表現に基づく値である、
付記８に記載の情報処理方法。
【０２０７】
（付記１２）
前記データ構造が、複数のノードを有し、前記複数のノードそれぞれは、前記部分列に対応する各座標のビット表現における特定の桁のビットだけを取り出し、前記部分列と同じ順序で並べた前記ビットの列を用いて表現され、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されている、
付記９に記載の情報処理方法。
【０２０８】
（付記１３）
前記（ｃ）のステップにおいて、前記情報として、前記選定区間の長さを合計した値を計算し、計算した値を出力する、
付記８に記載の情報処理方法。
【０２０９】
（付記１４）
前記（ｃ）のステップにおいて、前記情報として、前記選定区間に含まれる各次元の座標を全て計算し、計算した全ての座標を出力する、
付記８に記載の情報処理方法。
【０２１０】
（付記１５）
コンピュータによって、多次元空間上の点の集合を表現するデータ構造を処理対象として情報処理を行なうためのプログラムを記録したコンピュータ読み取り可能な記録媒体であって、
前記コンピュータに、
（ａ）前記点の特徴値を表すビット表現から得られる接頭辞を特徴値接頭辞とし、前記点の特定の次元での座標を表すビット表現から得られる接頭辞を座標接頭辞として、
クエリ領域として、特定の多次元の領域が指定された場合に、
前記データ構造を構築している多次元の領域において、前記特徴値接頭辞で始まる領域と次元毎の前記座標接頭辞で始まる領域との共通部分として表現され、且つ、前記クエリ領域に含まれる、領域を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定した領域に対応するデータ構造上の区間である選定区間を出力する、ステップと、
（ｃ）前記選定区間を用いて前記クエリ領域に含まれる点の集合に関する情報を計算する、ステップと、
を実行させる命令を含む、プログラムを記録しているコンピュータ読み取り可能な記録媒体。
【０２１１】
（付記１６）
前記データ構造が、
多次元上の前記点の集合それぞれの前記特徴値を、昇順に並べて得られる、特徴値列から、各次元について、前記特徴値の並び順と同じ順序で、各点の当該次元での座標を取り出すことで得られる座標列を用いて、次元毎に、前記座標列から、座標のビット表現が同じ座標接頭辞で始まる座標だけを、前記順番と同じ順序を保ったまま抽出して得られる部分列の、ビット表現の一部を用いて表現され、且つ、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されており、
前記（ａ）のステップにおいて、
前記部分列上の区間であって、当該区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、当該区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
付記１５に記載のコンピュータ読み取り可能な記録媒体。
【０２１２】
（付記１７）
前記（ａ）のステップにおいて、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間について、この区間に含まれる座標に対応する点の集合が前記クエリ領域に完全に包含される区間であるかどうかを判定し、
判定の結果、前記クエリ領域に完全に包含される区間ではない場合に、
前記判定の対象となった前記部分列の抽出に用いられる前記座標接頭辞を延長して、第二の座標接頭辞を設定し、
そして、前記第二の接頭辞を用いて座標を抽出して得られた第二の部分列上の区間であって、前記第二の部分列上の区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、前記第二の部分列上の区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
付記１６に記載のコンピュータ読み取り可能な記録媒体。
【０２１３】
（付記１８）
前記点の特徴値が、前記点の各次元の座標のビット表現を交互に組み合わせて得られるビット表現に基づく値である、
付記１５に記載のコンピュータ読み取り可能な記録媒体。
【０２１４】
（付記１９）
前記データ構造が、複数のノードを有し、前記複数のノードそれぞれは、前記部分列に対応する各座標のビット表現における特定の桁のビットだけを取り出し、前記部分列と同じ順序で並べた前記ビットの列を用いて表現され、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されている、
付記１６に記載のコンピュータ読み取り可能な記録媒体。
【０２１５】
（付記２０）
前記（ｃ）のステップにおいて、前記情報として、前記選定区間の長さを合計した値を計算し、計算した値を出力する、
付記１５に記載のコンピュータ読み取り可能な記録媒体。
【０２１６】
（付記２１）
前記（ｃ）のステップにおいて、前記情報として、前記選定区間に含まれる各次元の座標を全て計算し、計算した全ての座標を出力する、
付記１５に記載のコンピュータ読み取り可能な記録媒体。
【０２１７】
以上、実施の形態を参照して本願発明を説明したが、本願発明は上記実施の形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０２１８】
この出願は、２０１４年９月１９日に出願された日本出願特願２０１４−１９１１０２を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０２１９】
以上のように、本発明によれば、任意の次元dについて、線形サイズで、kd木よりも高速な矩形範囲検索を実現することができる。本発明は、大量のデータ群から必要なデータを探索する必要がある種々の分野において有用である。
【符号の説明】
【０２２０】
１０  検索部
２０  集計部
３０  入力受付部
４０  出力部
５０  記憶部
５１  データ構造
１００  情報処理装置
１１０  コンピュータ
１１１  ＣＰＵ
１１２  メインメモリ
１１３  記憶装置
１１４  入力インターフェイス
１１５  表示コントローラ
１１６  データリーダ／ライタ
１１７  通信インターフェイス
１１８  入力機器
１１９  ディスプレイ装置
１２０  記録媒体
１２１  バス
【図１】
2016043121.tif 000004
【図２】
2016043121.tif 000005
【図３】
2016043121.tif 000006
【図４】
2016043121.tif 000007
【図５】
2016043121.tif 000008
【図６】
2016043121.tif 000009
【図７】
2016043121.tif 000010
【図８】
2016043121.tif 000011
【図９】
2016043121.tif 000012
【図１０】
2016043121.tif 000013
【図１１】
2016043121.tif 000014
【図１２】
2016043121.tif 000015
【図１３】
2016043121.tif 000016
【手続補正書】
【提出日】平成29年3月6日(2017.3.6)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
多次元空間上の点の集合を表現するデータ構造を処理対象とする情報処理装置であって、
前記点の特徴値を表すビット表現から得られる接頭辞を特徴値接頭辞とし、前記点の特定の次元での座標を表すビット表現から得られる接頭辞を座標接頭辞として、
クエリ領域として、特定の多次元の領域が指定された場合に、
前記データ構造を構築している多次元の領域において、前記特徴値接頭辞で始まる領域と次元毎の前記座標接頭辞で始まる領域との共通部分として表現され、且つ、前記クエリ領域に含まれる、領域を特定し、
特定した領域に対応するデータ構造上の区間である選定区間を出力する、検索部と、
前記選定区間を用いて前記クエリ領域に含まれる点の集合に関する情報を計算する、集計部と、
を備えていることを特徴とする情報処理装置。
【請求項２】
前記データ構造が、
多次元上の前記点の集合それぞれの前記特徴値を、昇順に並べて得られる、特徴値列から、各次元について、前記特徴値の並び順と同じ順序で、各点の当該次元での座標を取り出すことで得られる座標列を用いて、次元毎に、前記座標列から、座標のビット表現が同じ座標接頭辞で始まる座標だけを、前記順番と同じ順序を保ったまま抽出して得られる部分列の、ビット表現の一部を用いて表現され、且つ、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されており、
前記検索部が、
前記部分列上の区間であって、当該区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、当該区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
請求項１に記載の情報処理装置。
【請求項３】
前記検索部が、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間について、この区間に含まれる座標に対応する点の集合が前記クエリ領域に完全に包含される区間であるかどうかを判定し、
判定の結果、前記クエリ領域に完全に包含される区間ではない場合に、
前記判定の対象となった前記部分列の抽出に用いられる前記座標接頭辞を延長して、第二の座標接頭辞を設定し、
そして、前記第二の接頭辞を用いて座標を抽出して得られた第二の部分列上の区間であって、前記第二の部分列上の区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、前記第二の部分列上の区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
請求項２に記載の情報処理装置。
【請求項４】
前記点の特徴値が、前記点の各次元の座標のビット表現を交互に組み合わせて得られるビット表現に基づく値である、
請求項１〜３のいずれかに記載の情報処理装置。
【請求項５】
前記データ構造が、複数のノードを有し、前記複数のノードそれぞれは、前記部分列に対応する各座標のビット表現における特定の桁のビットだけを取り出し、前記部分列と同じ順序で並べた前記ビットの列を用いて表現され、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されている、
請求項２または３に記載の情報処理装置。
【請求項６】
前記集計部が、前記情報として、前記選定区間の長さを合計した値を計算し、計算した値を出力する、
請求項１〜５のいずれかに記載の情報処理装置。
【請求項７】
前記集計部が、前記情報として、前記選定区間に含まれる各次元の座標を全て計算し、計算した全ての座標を出力する、
請求項１〜５のいずれかに記載の情報処理装置。
【請求項８】
多次元空間上の点の集合を表現するデータ構造を処理対象とする情報処理方法であって、
（ａ）前記点の特徴値を表すビット表現から得られる接頭辞を特徴値接頭辞とし、前記点の特定の次元での座標を表すビット表現から得られる接頭辞を座標接頭辞として、
クエリ領域として、特定の多次元の領域が指定された場合に、
前記データ構造を構築している多次元の領域において、前記特徴値接頭辞で始まる領域と次元毎の前記座標接頭辞で始まる領域との共通部分として表現され、且つ、前記クエリ領域に含まれる、領域を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定した領域に対応するデータ構造上の区間である選定区間を出力する、ステップと、
（ｃ）前記選定区間を用いて前記クエリ領域に含まれる点の集合に関する情報を計算する、ステップと、
を有することを特徴とする情報処理方法。
【請求項９】
前記データ構造が、
多次元上の前記点の集合それぞれの前記特徴値を、昇順に並べて得られる、特徴値列から、各次元について、前記特徴値の並び順と同じ順序で、各点の当該次元での座標を取り出すことで得られる座標列を用いて、次元毎に、前記座標列から、座標のビット表現が同じ座標接頭辞で始まる座標だけを、前記順番と同じ順序を保ったまま抽出して得られる部分列の、ビット表現の一部を用いて表現され、且つ、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されており、
前記（ａ）のステップにおいて、
前記部分列上の区間であって、当該区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、当該区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
請求項８に記載の情報処理方法。
【請求項１０】
前記（ａ）のステップにおいて、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間について、この区間に含まれる座標に対応する点の集合が前記クエリ領域に完全に包含される区間であるかどうかを判定し、
判定の結果、前記クエリ領域に完全に包含される区間ではない場合に、
前記判定の対象となった前記部分列の抽出に用いられる前記座標接頭辞を延長して、第二の座標接頭辞を設定し、
そして、前記第二の接頭辞を用いて座標を抽出して得られた第二の部分列上の区間であって、前記第二の部分列上の区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、前記第二の部分列上の区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
請求項９に記載の情報処理方法。
【請求項１１】
前記点の特徴値が、前記点の各次元の座標のビット表現を交互に組み合わせて得られるビット表現に基づく値である、
請求項８〜１０のいずれかに記載の情報処理方法。
【請求項１２】
前記データ構造が、複数のノードを有し、前記複数のノードそれぞれは、前記部分列に対応する各座標のビット表現における特定の桁のビットだけを取り出し、前記部分列と同じ順序で並べた前記ビットの列を用いて表現され、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されている、
請求項９または１０に記載の情報処理方法。
【請求項１３】
前記（ｃ）のステップにおいて、前記情報として、前記選定区間の長さを合計した値を計算し、計算した値を出力する、
請求項８〜１２のいずれかに記載の情報処理方法。
【請求項１４】
前記（ｃ）のステップにおいて、前記情報として、前記選定区間に含まれる各次元の座標を全て計算し、計算した全ての座標を出力する、
請求項８〜１２のいずれかに記載の情報処理方法。
【請求項１５】
コンピュータによって、多次元空間上の点の集合を表現するデータ構造を処理対象として情報処理を行なうためのプログラムであって、
前記コンピュータに、
（ａ）前記点の特徴値を表すビット表現から得られる接頭辞を特徴値接頭辞とし、前記点の特定の次元での座標を表すビット表現から得られる接頭辞を座標接頭辞として、
クエリ領域として、特定の多次元の領域が指定された場合に、
前記データ構造を構築している多次元の領域において、前記特徴値接頭辞で始まる領域と次元毎の前記座標接頭辞で始まる領域との共通部分として表現され、且つ、前記クエリ領域に含まれる、領域を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定した領域に対応するデータ構造上の区間である選定区間を出力する、ステップと、
（ｃ）前記選定区間を用いて前記クエリ領域に含まれる点の集合に関する情報を計算する、ステップと、
を実行させる、プログラム。
【請求項１６】
前記データ構造が、
多次元上の前記点の集合それぞれの前記特徴値を、昇順に並べて得られる、特徴値列から、各次元について、前記特徴値の並び順と同じ順序で、各点の当該次元での座標を取り出すことで得られる座標列を用いて、次元毎に、前記座標列から、座標のビット表現が同じ座標接頭辞で始まる座標だけを、前記順番と同じ順序を保ったまま抽出して得られる部分列の、ビット表現の一部を用いて表現され、且つ、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されており、
前記（ａ）のステップにおいて、
前記部分列上の区間であって、当該区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、当該区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
請求項１５に記載のプログラム。
【請求項１７】
前記（ａ）のステップにおいて、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間について、この区間に含まれる座標に対応する点の集合が前記クエリ領域に完全に包含される区間であるかどうかを判定し、
判定の結果、前記クエリ領域に完全に包含される区間ではない場合に、
前記判定の対象となった前記部分列の抽出に用いられる前記座標接頭辞を延長して、第二の座標接頭辞を設定し、
そして、前記第二の接頭辞を用いて座標を抽出して得られた第二の部分列上の区間であって、前記第二の部分列上の区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、前記第二の部分列上の区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
請求項１６に記載のプログラム。
【請求項１８】
前記点の特徴値が、前記点の各次元の座標のビット表現を交互に組み合わせて得られるビット表現に基づく値である、
請求項１５〜１７のいずれかに記載のプログラム。
【請求項１９】
前記データ構造が、複数のノードを有し、前記複数のノードそれぞれは、前記部分列に対応する各座標のビット表現における特定の桁のビットだけを取り出し、前記部分列と同じ順序で並べた前記ビットの列を用いて表現され、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されている、
請求項１６または１７に記載のプログラム。
【請求項２０】
前記（ｃ）のステップにおいて、前記情報として、前記選定区間の長さを合計した値を計算し、計算した値を出力する、
請求項１５〜１９のいずれかに記載のプログラム。
【請求項２１】
前記（ｃ）のステップにおいて、前記情報として、前記選定区間に含まれる各次元の座標を全て計算し、計算した全ての座標を出力する、
請求項１５〜１９のいずれかに記載のプログラム。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００１
【補正方法】変更
【補正の内容】
【０００１】
本発明は、情報処理装置、情報処理方法、及びこれらを実現するためのプログラムに関し、特には、多次元データ上での効率的な検索を行うための、情報処理装置、情報処理方法、及びプログラムに関する。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１７
【補正方法】変更
【補正の内容】
【００１７】
本発明の目的の一例は、上記問題を解消し、任意の次元について、線形サイズで、kd木よりも高速な矩形範囲検索を実現し得る、情報処理装置、情報処理方法、及びプログラムを提供することにある。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００２０
【補正方法】変更
【補正の内容】
【００２０】
更に、上記目的を達成するため、本発明の一側面におけるプログラムは、コンピュータによって、多次元空間上の点の集合を表現するデータ構造を処理対象として情報処理を行なうためのプログラムであって、
前記コンピュータに、
（ａ）前記点の特徴値を表すビット表現から得られる接頭辞を特徴値接頭辞とし、前記点の特定の次元での座標を表すビット表現から得られる接頭辞を座標接頭辞として、
クエリ領域として、特定の多次元の領域が指定された場合に、
前記データ構造を構築している多次元の領域において、前記特徴値接頭辞で始まる領域と次元毎の前記座標接頭辞で始まる領域との共通部分として表現され、且つ、前記クエリ領域に含まれる、領域を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定した領域に対応するデータ構造上の区間である選定区間を出力する、ステップと、
（ｃ）前記選定区間を用いて前記クエリ領域に含まれる点の集合に関する情報を計算する、ステップと、
を実行させる、ことを特徴とする。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００３３
【補正方法】変更
【補正の内容】
【００３３】
また、本発明は、値を１と０の二進表現で表現できていれば、順位空間への変換が行なわれていなくても適用できる。すなわち、データ数がnであるとき、座標の値の範囲が[0,n-1]の範囲から外れているデータであっても、本発明は適用できる。本明細書では、計算量の理論的な分析を行うために[0,n-1]の範囲に限定して説明しているだけであり、実用上は[0,n-1]の範囲に限らなくても問題なく本発明を適用できる。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００４６
【補正方法】変更
【補正の内容】
【００４６】
また、このとき、 [lπ1,uπ1]=[”010”,”011”]=[2,3]、および[lπ2,uπ2]=[”100”,”111”]=[4,7]であり、C(πz) = [2,3] × [4,7] である。この関係は、図１に示されている。図１に示すように、次元1における領域C(π1)と、次元2における領域C(π2)との交わる領域C(π1) ∩ C(π2)が、C(πz)となっていることが分かる。C(πz)に含まれるZ値は全てπzで始まっている。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００５４
【補正方法】変更
【補正の内容】
【００５４】
このように、情報処理装置１００では、入力されたクエリ領域は、特徴値接頭辞で規定される領域と各次元の座標接頭辞で規定される領域との共通部分によって分割されることになるので、kd木を探索する場合に比べて、クエリ領域の分割に要する計算量が削減される。このため、情報処理装置１００によれば、任意の次元dについて、線形サイズで、kd木よりも高速な矩形範囲検索を実現することができる。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００６１
【補正方法】変更
【補正の内容】
【００６１】
まず、図１に示すように、各マス目に存在する８個の丸い円が、２次元上の点pを表すものとする。この例では、n=8であり、それぞれの点は[0,7]×[0,7]=64個のグリッド上の点として表現される。たとえば、(5,2)=(”101”,”010”)の点のZ値は、”100110”=38である。このとき、円の中に書かれている番号が、対応するZ値が昇順になるように並べた場合の順位を示している。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００９７
【補正方法】変更
【補正の内容】
【００９７】
関数range_search(V,Q)は、長さ0のZ値接頭辞πzを引数にして呼び出され、自らを再帰的に呼び出すことが可能な関数である。関数range_search(V,Q)は、自身を再帰的に呼び出す度に、Z値接頭辞πzを1ビットずつ延長し、延長された各πzについて対応するZ値探索ノードVを生成する。πzを1ビット延長することは、カバー領域C(πz)を二分割することに相当するため、πzが長くなるほどカバー領域は小さくなる。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】０２１０
【補正方法】変更
【補正の内容】
【０２１０】
（付記１５）
コンピュータによって、多次元空間上の点の集合を表現するデータ構造を処理対象として情報処理を行なうためのプログラムであって、
前記コンピュータに、
（ａ）前記点の特徴値を表すビット表現から得られる接頭辞を特徴値接頭辞とし、前記点の特定の次元での座標を表すビット表現から得られる接頭辞を座標接頭辞として、
クエリ領域として、特定の多次元の領域が指定された場合に、
前記データ構造を構築している多次元の領域において、前記特徴値接頭辞で始まる領域と次元毎の前記座標接頭辞で始まる領域との共通部分として表現され、且つ、前記クエリ領域に含まれる、領域を特定する、ステップと、
（ｂ）前記（ａ）のステップで特定した領域に対応するデータ構造上の区間である選定区間を出力する、ステップと、
（ｃ）前記選定区間を用いて前記クエリ領域に含まれる点の集合に関する情報を計算する、ステップと、
を実行させる、プログラム。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】０２１１
【補正方法】変更
【補正の内容】
【０２１１】
（付記１６）
前記データ構造が、
多次元上の前記点の集合それぞれの前記特徴値を、昇順に並べて得られる、特徴値列から、各次元について、前記特徴値の並び順と同じ順序で、各点の当該次元での座標を取り出すことで得られる座標列を用いて、次元毎に、前記座標列から、座標のビット表現が同じ座標接頭辞で始まる座標だけを、前記順番と同じ順序を保ったまま抽出して得られる部分列の、ビット表現の一部を用いて表現され、且つ、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されており、
前記（ａ）のステップにおいて、
前記部分列上の区間であって、当該区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、当該区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
付記１５に記載のプログラム。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】０２１２
【補正方法】変更
【補正の内容】
【０２１２】
（付記１７）
前記（ａ）のステップにおいて、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間について、この区間に含まれる座標に対応する点の集合が前記クエリ領域に完全に包含される区間であるかどうかを判定し、
判定の結果、前記クエリ領域に完全に包含される区間ではない場合に、
前記判定の対象となった前記部分列の抽出に用いられる前記座標接頭辞を延長して、第二の座標接頭辞を設定し、
そして、前記第二の接頭辞を用いて座標を抽出して得られた第二の部分列上の区間であって、前記第二の部分列上の区間に含まれる座標に対応する点の特徴値のビット表現が前記特徴値接頭辞で始まっており、且つ、前記第二の部分列上の区間に含まれる座標に対応する点の集合が全て前記クエリ領域に包含される区間を、前記選定区間として出力する、
付記１６に記載のプログラム。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】０２１３
【補正方法】変更
【補正の内容】
【０２１３】
（付記１８）
前記点の特徴値が、前記点の各次元の座標のビット表現を交互に組み合わせて得られるビット表現に基づく値である、
付記１５に記載のプログラム。
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】０２１４
【補正方法】変更
【補正の内容】
【０２１４】
（付記１９）
前記データ構造が、複数のノードを有し、前記複数のノードそれぞれは、前記部分列に対応する各座標のビット表現における特定の桁のビットだけを取り出し、前記部分列と同じ順序で並べた前記ビットの列を用いて表現され、
前記部分列上の区間であって、当該区間に含まれる座標に対応した点の特徴値のビット表現が前記特徴値接頭辞から始まっている区間を特定できるように、
構築されている、
付記１６に記載のプログラム。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】０２１５
【補正方法】変更
【補正の内容】
【０２１５】
（付記２０）
前記（ｃ）のステップにおいて、前記情報として、前記選定区間の長さを合計した値を計算し、計算した値を出力する、
付記１５に記載のプログラム。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】０２１６
【補正方法】変更
【補正の内容】
【０２１６】
（付記２１）
前記（ｃ）のステップにおいて、前記情報として、前記選定区間に含まれる各次元の座標を全て計算し、計算した全ての座標を出力する、
付記１５に記載のプログラム。
【手続補正１８】
【補正対象書類名】図面
【補正対象項目名】図７
【補正方法】変更
【補正の内容】
【図７】
2016043121.tif 000017
【国際調査報告】
2016043121.tif 000018
2016043121.tif 000019