(57)【要約】【課題】多次元範囲検索時のヒットページの検出を高速化する。【解決手段】多次元範囲検索装置は、空間充填曲線上の特定区間の最小点及び最大点を表す始端インデックスキー及び終端インデックスキーを取得する取得部と、始端インデックスキー及び終端インデックスキーの各ビット列に基づいて、上記特定区間に含まれるインデックスキーのビット列を表し得るプレフィックスデータを抽出する抽出部と、抽出部により抽出されたプレフィックスデータのプレフィックスを共通して有するインデックスキーの集合により形成される空間充填曲線上のプレフィックス区間と多次元範囲検索の問い合わせ区間との重複を判定する判定部とを有する。【選択図】図２
2015018497.tif 000002
【特許請求の範囲】
【請求項１】
複数の属性からなるデータセットがマッピングされる多次元空間の一次元化に用いられる空間充填曲線上の特定区間の最小点及び最大点を表す始端インデックスキー及び終端インデックスキーを取得する取得部と、
前記取得部により取得された始端インデックスキー及び終端インデックスキーの各ビット列に基づいて、前記特定区間に含まれるインデックスキーのビット列を表し得るプレフィックスデータを抽出する抽出部と、
前記抽出部により抽出されたプレフィックスデータのプレフィックスを共通して有するインデックスキーの集合により形成される前記空間充填曲線上のプレフィックス区間と多次元範囲検索の問い合わせ区間との重複を判定する判定部と、
を備え、
前記空間充填曲線は、前記プレフィックスデータと、前記プレフィックスデータにより示されるプレフィックスを共通して有する点の集合からなる前記プレフィックス区間とが一対一に対応し、該プレフィックスデータのプレフィックスの長さと該プレフィックス区間の大きさとが負の相関を持つ特性を有する、
多次元範囲検索装置。
【請求項２】
前記空間充填曲線は、各属性のビット列の並び順を変えず、該各属性のビット列同士を任意の順序で混合することで、前記多次元空間を一次元化し、
前記抽出部は、前記属性の数に依存しない所定ビット長で取り得る各ビットパターンについて、ビット反転及びワイルドカード文字への置換の少なくとも一方を含む置換ルールをそれぞれ持ち、前記始端インデックスキー及び前記終端インデックスキーにおける共通プレフィックス長を算出し、前記始端インデックスキー及び前記終端インデックスキーにおける該共通プレフィックス長より下位の各対象ビット列を該所定ビット長で区切ることで得られる部分ビット列のビットパターンに対応する該置換ルールを用いて、前記プレフィックスデータを抽出する、
請求項１に記載の多次元範囲検索装置。
【請求項３】
前記抽出部は、前記始端インデックスキーの前記対象ビット列を下位から上位に向かって走査し、かつ、前記終端インデックスキーの前記対象ビット列を上位から下位に向かって走査することにより、前記プレフィックスデータを抽出する、
請求項２に記載の多次元範囲検索装置。
【請求項４】
前記抽出部は、前記始端インデックスキー及び前記終端インデックスキーの前記各対象ビット列の参照ビットが０の場合に、該参照ビットを１に変え、かつ、該参照ビットより下位のビットをワイルドカード文字に変え、該参照ビットが１の場合にビット置換を行わない第１の置換ルール、及び、該参照ビットが１の場合に、該参照ビットを０に変え、かつ、該参照ビットより下位のビットをワイルドカード文字に変え、該参照ビットが０の場合にビット置換を行わない第２の置換ルールを持ち、前記始端インデックスキーの前記対象ビット列には前記第１の置換ルールを適用し、前記終端インデックスキーの前記対象ビット列には前記第２の置換ルールを適用する、
請求項２又は３に記載の多次元範囲検索装置。
【請求項５】
前記判定部は、
前記プレフィックス区間の最小点及び最大点を表す各インデックスキーから、前記プレフィックス区間のビット列の範囲を属性毎にそれぞれ抽出し、
前記問い合わせ区間の最小点及び最大点を表す各インデックスキーから、前記問い合わせ区間のビット列の範囲を属性毎にそれぞれ抽出し、
前記プレフィックス区間と前記問い合わせ区間とのビット列の範囲の重複を各属性についてそれぞれ判定することにより、前記プレフィックス区間と前記問い合わせ区間との重複を判定する、
請求項１から４に記載の多次元範囲検索装置。
【請求項６】
複数の属性からなるデータセットがマッピングされる多次元空間の一次元化に用いられる空間充填曲線上の特定区間の最小点及び最大点を表す始端インデックスキー及び終端インデックスキーを取得し、
前記取得された始端インデックスキー及び終端インデックスキーの各ビット列に基づいて、前記特定区間に含まれるインデックスキーのビット列を表し得るプレフィックスデータを抽出し、
前記抽出されたプレフィックスデータのプレフィックスを共通して有するインデックスキーの集合により形成される前記空間充填曲線上のプレフィックス区間と多次元範囲検索の問い合わせ区間との重複を判定する、
ことを含み、
前記空間充填曲線は、前記プレフィックスデータと、前記プレフィックスデータにより示されるプレフィックスを共通して有する点の集合からなる前記プレフィックス区間とが一対一に対応し、該プレフィックスデータのプレフィックスの長さと該プレフィックス区間の大きさとが負の相関を持つ特性を有する、
多次元範囲検索方法。
【請求項７】
前記空間充填曲線は、各属性のビット列の並び順を変えず、該各属性のビット列同士を任意の順序で混合することで、前記多次元空間を一次元化し、
前記プレフィックスデータの抽出は、前記始端インデックスキー及び前記終端インデックスキーにおける共通プレフィックス長を算出し、前記属性の数に依存しない所定ビット長で取り得る各ビットパターンに対し設けられる、ビット反転及びワイルドカード文字への置換の少なくとも一方を含む複数の置換ルールの中の、前記始端インデックスキー及び前記終端インデックスキーにおける該共通プレフィックス長より下位の各対象ビット列を該所定ビット長で区切ることで得られる部分ビット列のビットパターンに対応する置換ルールを用いて、前記プレフィックスデータを抽出する、
請求項６に記載の多次元範囲検索方法。
【請求項８】
前記プレフィックスデータの抽出は、前記始端インデックスキーの前記対象ビット列を下位から上位に向かって走査し、かつ、前記終端インデックスキーの前記対象ビット列を上位から下位に向かって走査することにより、前記プレフィックスデータを抽出する、
請求項７に記載の多次元範囲検索方法。
【請求項９】
前複数の置換ルールは、前記始端インデックスキー及び前記終端インデックスキーの前記各対象ビット列の参照ビットが０の場合に、該参照ビットを１に変え、かつ、該参照ビットより下位のビットをワイルドカード文字に変え、該参照ビットが１の場合にビット置換を行わない第１の置換ルール、及び、該参照ビットが１の場合に、該参照ビットを０に変え、かつ、該参照ビットより下位のビットをワイルドカード文字に変え、該参照ビットが０の場合にビット置換を行わない第２の置換ルールを含み、
前記プレフィックスデータの抽出は、前記始端インデックスキーの前記対象ビット列には前記第１の置換ルールを適用し、前記終端インデックスキーの前記対象ビット列には前記第２の置換ルールを適用する、
請求項６又は７に記載の多次元範囲検索方法。
【請求項１０】
前記プレフィックス区間の最小点及び最大点を表す各インデックスキーから、前記プレフィックス区間のビット列の範囲を属性毎にそれぞれ抽出し、
前記問い合わせ区間の最小点及び最大点を表す各インデックスキーから、前記問い合わせ区間のビット列の範囲を属性毎にそれぞれ抽出し、
前記プレフィックス区間と前記問い合わせ区間とのビット列の範囲の重複を各属性についてそれぞれ判定する、
ことを更に含み、
前記重複の判定は、前記ビット列の範囲の重複の判定結果に基づいて、前記プレフィックス区間と前記問い合わせ区間との重複を判定する、
請求項６から９のいずれか１項に記載の多次元範囲検索方法。
【請求項１１】
請求項６から１０のいずれか１項に記載の多次元範囲検索方法を少なくとも１つのコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、多次元範囲検索におけるインデックス走査技術に関する。
【背景技術】
【０００２】
データベースに対する或る範囲内のレコードを抽出する範囲検索は、基本的な問い合わせ処理の一つである。この範囲検索を効率的に実行するために、多くのインデックス構造が提案されている。Ｂツリーは、一次元の範囲検索に適したインデックス構造として知られている。Ｂツリーは、インデックスの値の範囲でレコード集合（データセット）を分割して、分割されたレコード集合を各ページに分散配置し、各ページによりカバーされるレコード範囲の起点又は終点を木構造で管理する。Ｂツリーによれば、或る範囲内のレコードが格納されているページを効率的に取得することができる。
【０００３】
Ｂツリーを拡張し、複数次元の範囲検索を効率的に実行するための多次元インデックス構造の一つとして、Ｕ（Universal）Ｂツリーが知られている。ＵＢツリーは、空間充填曲線であるＺカーブ（Ｚ曲線）を用いて、多次元空間上の点を一次元上に写像し、その写像された点をインデックスキーとして、Ｂツリーに格納する手法である。多次元空間上の点を一次元上の点に写像するため、多次元空間上で連続する多次元の矩形領域は、一次元上では区間の集合として表現される。このため、多次元範囲検索は、Ｂツリー上の（一次元）範囲検索の集合として表現される。
【０００４】
しかしながら、単純に多次元範囲検索を一次元の範囲検索の集合に分解すると、一次元の範囲検索の数が膨大に膨れ上がることが知られている。そこで、下記非特許文献１は、多次元範囲検索を分解するのではなく、与えられた多次元範囲内にあるレコードが含まれているページ（以下、ヒットページと表記する）を効率的に見つけるアルゴリズムを提案している。
【０００５】
下記非特許文献１は、ページがカバーする領域と検索範囲の重なり検査を効率的にするために、Ｚカーブのビット表現におけるビットパターンとＺカーブの多次元空間におけるフラクタル形状との関係性を利用したアルゴリズムを提案している（下記非特許文献１の図１１参照）。Ｚカーブは、各属性のビット列を交互に混ぜ合わせることでインデックスキーを生成する。下記非特許文献１の手法は、属性数がｎの場合、Ｚカーブで生成されたビット列をｎビットずつに区切る。ｎビット長の部分ビット列は、多次元空間上の超立方体に対応付けることができ、部分ビット列の区切り位置（何番目の区切りか）が、多次元空間上でのスケールを表し、その部分ビット列までのビットパターンが多次元空間上の位置を表す。
【０００６】
下記非特許文献１の手法は、Ｚカーブのこの性質を利用して、以下のようにして、ページがカバーする領域を超直方体の集合に分解する。ページの区間の開始点をα、終了点をβとする。まず、当該手法は、α及びβを含む最小の超立方体を見つける。当該手法は、α及びβをｎビットずつ区切り、最上位側から最下位側の方向の順で、区切られた各部分ビット列が一致しているかどうかを検査する。この検査は、一致していない部分ビット列が見つかるまで繰り返される。ここで、ｊ番目の区切り位置の部分ビット列が一致していないと仮定する。次に、当該手法は、上述のように見つけた超立方体内で、ページの区間に対応する領域と完全に重なる超直方体の集合を見つける。α及びβのｉ番目の区切りの長さｎのビット列をα［ｉ］及びβ［ｉ］とする。α及びβそれぞれに関して、ｊ番目の区切りから最後の区切りまでの各ビットパターンを観察し、各ｉ番目の超立方体の中でページの区間に含まれる最大の超直方体を見つける。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Tomas Skopal, etc., "A new range query algorithm for Universal B-trees", 2006/9, Figs.3 and 11, Algorithm 5 and 6, http://www.sciencedirect.com/science/article/pii/S0306437905000116
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上述の手法は、単純な空間充填曲線であるＺカーブにしか適用できないという制約を持つ。これにより、インデックス設計の範囲が制約される。例えば、上述の手法は、各属性のビット長が異なっており、短いビット長の属性のビット列に対するゼロパディングを行うことなく、各属性のビット列を混合する空間充填曲線や、ビット列の混ぜ合わせ順に自由度がある空間充填曲線を用いることができない。属性数と同じビット長でインデックスキーが区切られてなる部分ビット列と、単純なＺカーブのフラクタル形状との対応関係に基づいてアルゴリズムが設計されているからである。
【０００９】
これにより、範囲検索の指定内容やインデックス対象のデータセットの分布に応じたインデックス設計を行うことができないため、上述の手法では、範囲検索処理の効率を低下させてしまう可能性がある。
【００１０】
本発明は、上述のような課題に鑑みてなされたものであり、多次元範囲検索時のヒットページの検出を高速化する技術を提供する。
【課題を解決するための手段】
【００１１】
本発明の各側面では、上述した課題を解決するために、それぞれ以下の構成を採用する。
【００１２】
第１の側面は、多次元範囲検索装置に関する。第１の側面に係る多次元範囲検索装置は、複数の属性からなるデータセットがマッピングされる多次元空間の一次元化に用いられる空間充填曲線上の特定区間の最小点及び最大点を表す始端インデックスキー及び終端インデックスキーを取得する取得部と、取得部により取得された始端インデックスキー及び終端インデックスキーの各ビット列に基づいて、上記特定区間に含まれるインデックスキーのビット列を表し得るプレフィックスデータを抽出する抽出部と、抽出部により抽出されたプレフィックスデータのプレフィックスを共通して有するインデックスキーの集合により形成される空間充填曲線上のプレフィックス区間と多次元範囲検索の問い合わせ区間との重複を判定する判定部とを有する。第１の側面で用いられる上記空間充填曲線は、プレフィックスデータと、プレフィックスデータにより示されるプレフィックスを共通して有する点の集合からなるプレフィックス区間とが一対一に対応し、プレフィックスデータのプレフィックスの長さとプレフィックス区間の大きさとが負の相関を持つ特性を有する。
【００１３】
第２の側面は、上記第１の側面と同様の特性を持つ空間充填曲線を用いる多次元範囲検索方法に関する。第２の側面に係る多次元範囲検索方法は、複数の属性からなるデータセットがマッピングされる多次元空間の一次元化に用いられる空間充填曲線上の特定区間の最小点及び最大点を表す始端インデックスキー及び終端インデックスキーを取得し、取得された始端インデックスキー及び終端インデックスキーの各ビット列に基づいて、上記特定区間に含まれるインデックスキーのビット列を表し得るプレフィックスデータを抽出し、抽出されたプレフィックスデータのプレフィックスを共通して有するインデックスキーの集合により形成される空間充填曲線上のプレフィックス区間と多次元範囲検索の問い合わせ区間との重複を判定することを含む。
【００１４】
なお、本発明の他の側面としては、上記第２の側面の方法を少なくとも１つのコンピュータに実行させるプログラムであってもよいし、このようなプログラムを記録したコンピュータが読み取り可能な記録媒体であってもよい。この記録媒体は、非一時的な有形の媒体を含む。
【発明の効果】
【００１５】
上記各側面によれば、多次元範囲検索時のヒットページの検出を高速化する技術を提供することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施形態における多次元範囲検索装置（検索装置）のハードウェア構成例を概念的に示す図である。
【図２】第１実施形態における多次元範囲検索装置（検索装置）の処理構成例を概念的に示す図である。
【図３】インデックス格納部の例を示す図である。
【図４】上述の実施形態における多次元範囲検索装置（検索装置）の動作例を示すフローチャートである。
【図５】実施例で利用される空間充填曲線及びプレフィックス区間を示す図である。
【図６】実施例で用いられる空間充填曲線及インデックスキーを示す図である。
【図７】実施例における特定区間に含まれるプレフィックスデータの抽出を概念的に示す図である。
【図８】問い合わせ区間とプレフィックス区間との重複判定を概念的に示す図である。
【発明を実施するための形態】
【００１７】
以下、本発明の実施の形態について説明する。なお、以下に挙げる実施形態は例示であり、本発明は以下の実施形態の構成に限定されない。
【００１８】
以下に挙げる本発明の実施の形態における多次元範囲検索装置は、多次元範囲検索のクエリを取得し、このクエリの問い合わせ区間（検索空間）と或る区間（特定区間）との重複を判定する。ここで、多次元範囲検索とは、複数の属性が条件に指定された範囲検索であり、指定される属性の数は複数であれば特に制限されない。
【００１９】
〔装置構成〕
図１は、本発明の実施形態における多次元範囲検索装置（以降、単に検索装置と表記する）１０のハードウェア構成例を概念的に示す図である。本実施形態における検索装置１０は、いわゆるコンピュータであり、例えば、バス５で相互に接続される、ＣＰＵ（Central Processing Unit）２、メモリ３、入出力インタフェース（Ｉ／Ｆ）４等を有する。メモリ３は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ハードディスク等である。
【００２０】
入出力Ｉ／Ｆ４は、ネットワーク（図示せず）を介して他のコンピュータと通信を行う通信装置、可搬型記録媒体に対するアクセスを制御する装置、キーボード、マウス等のようなユーザ操作の入力を受け付ける入力装置、ディスプレイ装置やプリンタ等のようなユーザに情報を提供する出力装置等と接続可能である。但し、検索装置１０のハードウェア構成は制限されない。
【００２１】
〔処理構成〕
図２は、第１実施形態における検索装置１０の処理構成例を概念的に示す図である。第１実施形態における検索装置１０は、取得部１１、抽出部１２、判定部１３等を有する。これら各処理部は、例えば、ＣＰＵ２によりメモリ３に格納されるプログラムが実行されることにより実現される。また、当該プログラムは、例えば、ＣＤ（Compact Disc）、メモリカード等のような可搬型記録媒体やネットワーク上の他のコンピュータから入出力Ｉ／Ｆ４を介してインストールされ、メモリ３に格納されてもよい。
【００２２】
検索装置１０で検索対象とされる、複数の属性からなるデータセットは、空間ベースの空間分割法により、各部分空間に含まれるデータ数が閾値以下となるまで空間的に分割され、分割されたデータセットが各部分空間と関連付けられたデータページへ分散配置されている。一方、当該データセットがマッピングされる多次元空間の各データ点は、当該多次元空間が空間充填曲線で一元化されることで生成される各多次元インデックスキー（以降、単に、インデックスキーと表記する）により索引付けされている。
【００２３】
このようなインデックスキーとデータページとのマッピング情報は、図示されていないインデックス格納部に格納される。
図３は、インデックス格納部の例を示す図である。図３に示されるように、インデックス格納部は、インデックスデータ及びページ情報をそれぞれ含む複数のエントリを格納する。インデックス格納部は、検索装置１０により実現されてもよいし、他の装置により実現されてもよい。
【００２４】
インデックス格納部に格納されるインデックスデータは、上記多次元空間の或る部分空間の位置及び範囲を特定し得るデータ形式を持ち、対応する部分空間に含まれるインデックスキーの最長共通プレフィックスとワイルドカード文字との組み合わせで形成される。なお、対応する部分空間に含まれるインデックスキーが１つの場合、その部分空間を示すインデックスデータは、そのインデックスキーそのものとなる。インデックス格納部に格納されるページ情報は、同じエントリに含まれるインデックスデータにより示される部分空間と関連付けられたデータページの所在位置を示す。データページ自体は、検索装置に保持されてもよいし、他の装置に保持されていてもよい。
【００２５】
インデックス格納部に格納されるエントリは、図３に示されるように、インデックスデータの名前順にソートされている。即ち、インデックス格納部では、ページ情報は、インデックスデータの名前順にソートされている。また、インデックス格納部は、Ｂツリーのような周知の木構造で各エントリを格納してもよい。
【００２６】
本実施形態において、上記多次元空間の一次元化に用いられる空間充填曲線には、Ｚ曲線、ヒルベルト曲線等のような周知の固定化されたものが利用されてもよいし、より汎用化されたものが利用されてもよい。汎用化された空間充填曲線は、例えば、各属性のビット列の並び順を変えず、各属性のビット列同士を任意の順序で混合することで、多次元空間を一次元化する。本実施形態で用いられる空間充填曲線は、プレフィックスデータと、そのプレフィックスデータのプレフィックスを共通して有するインデックスキーの集合により形成されるプレフィックス区間とが一対一に対応し、プレフィックスデータのプレフィックスの長さとプレフィックス区間の大きさとが負の相関を持つ特性を有するものであればよい。プレフィックスデータの説明は後述する。
【００２７】
取得部１１は、上記多次元空間の一次元化に用いられる上記空間充填曲線上の特定区間の最小点及び最大点を表す始端インデックスキー及び終端インデックスキーを取得する。特定区間は、例えば、或るデータページに対応する当該空間充填曲線上の区間に設定される。このデータページは、インデックス格納部に格納されるページ情報で示される。この場合、始端インデックスキーは、そのデータページに対応するインデックスデータのワイルドカード文字を０に置き換えたものであり、かつ、当該特定区間の最小値である。終端インデックスキーは、そのインデックスデータのワイルドカード文字を１に置き換えたものであり、かつ、当該特定区間の最大値である。但し、当該特定区間は、データページに制限されず、任意の区間に設定されることもできる。
【００２８】
取得部１１は、始端インデックスキー及び終端インデックスキーを、可搬型記録媒体、他のコンピュータ等から入出力Ｉ／Ｆ４を経由して取得してもよいし、入力画面等に基づいて入力部をユーザが操作することにより入力された情報として取得してもよい。始端インデックスキー及び終端インデックスキーの取得方法は制限されない。
【００２９】
抽出部１２は、取得部１１により取得された始端インデックスキー及び終端インデックスキーの各ビット列に基づいて、当該特定区間に含まれるインデックスキーのビット列を表し得るプレフィックスデータを抽出する。プレフィックスデータとは、固定ビット長のビット列であり、プレフィックスのみから形成されるビット列、又は、プレフィックスと少なくとも１つのワイルドカード文字とから形成されるビット列である。プレフィックスとは、プレフィックスデータが表す空間充填曲線上の区間に含まれるインデックスキー間において、先頭ビットから連続して共通する部分ビット列である。ここでは、１つのワイルドカード文字も１ビットデータとして扱われる。例えば、始端インデックスキーが「００００１１」であり、終端インデックスキーが「０００１１１」である場合、抽出部１２は、「００００１１」及び「０００１＊＊」をプレフィックスデータとして抽出する。この例では、ワイルドカード文字には「＊」が利用されている。但し、ワイルドカード文字は制限されない。
【００３０】
このように、抽出部１２により抽出されるプレフィックスデータは、データセットがマッピングされた多次元空間内における、少なくとも１つのインデックスキーを示す１つの部分空間に対応する。そして、本実施形態では、このプレフィックスデータが、そのプレフィックスデータのプレフィックスを共通して有するインデックスキーの集合により形成されるプレフィックス区間（部分空間）と一対一に対応し、プレフィックスデータのプレフィックスの長さとプレフィックス区間の大きさとが負の相関を持つような、空間充填曲線が利用される。ここで、プレフィックスデータのプレフィックスの長さとプレフィックス区間の大きさとが負の相関とは、プレフィックスの長さが長くなる程、そのプレフィックスデータに対応するプレフィックス区間が小さくなり、プレフィックスの長さが短くなる程、そのプレフィックスデータに対応するプレフィックス区間が大きくなる関係を意味する。
【００３１】
抽出部１２は、例えば、次のようにして、始端インデックスキー及び終端インデックスキーの各ビット列に基づいて、プレフィックスデータを抽出することができる。抽出部１２は、データセットの属性数に依存しない所定ビット長で取り得る各ビットパターンについて、ビット反転及びワイルドカード文字への置換の少なくとも一方を含む置換ルールをそれぞれ持ち、始端インデックスキー及び終端インデックスキーにおける共通プレフィックス長を算出し、始端インデックスキー及び終端インデックスキーにおける共通プレフィックス長より下位の各対象ビット列を所定ビット長で区切ることで得られる部分ビット列のビットパターンに対応する置換ルールを用いて、プレフィックスデータを抽出する。ここでは、始端インデックスキー及び終端インデックスキーにおける、共通プレフィックス長より下位のビット列が対象ビット列と表記される。
【００３２】
抽出部１２が持つ置換ルールは、本実施形態で利用される空間充填曲線及び所定ビット長に適応するように設定される。ここで、所定ビット長は、１ビット以上であれば、特に制限されない。例えば、所定ビット長を、コンピュータで効率的に処理できる長さ（例えば、６４ビットや１２８ビット等）に設定することもできる。このようにすれば、置換ルールの適用処理を効率化することができ、結果として、プレフィックスデータの抽出処理を一層高速化することができる。
【００３３】
判定部１３は、抽出部１２により抽出されたプレフィックスデータのプレフィックスを共通して有するインデックスキーの集合により形成される空間充填曲線上のプレフィックス区間と多次元範囲検索の問い合わせ区間との重複を判定する。ここで、プレフィックスデータによれば、プレフィックス区間の最大値及び最小値を簡単に取得することができる。ワイルドカード文字を全て１に置換すれば、プレフィックス区間の最大値が取得され、ワイルドカード文字を全て０に置換すれば、プレフィックス区間の最小値が取得され得る。また、多次元範囲検索の問い合わせ区間に関する情報は、判定部１３により予め保持されていてもよいし、取得部１１により始端インデックスキー及び終端インデックスキーと同様に取得されてもよい。判定部１３は、例えば、プレフィックス区間の最大値及び最小値と、問い合わせ区間の最大値及び最小値とを比較することにより、容易に、両区間が重複するか否かを判定することができる。ここで、プレフィックス区間と問い合わせ区間との重複とは、両区間の少なくとも一部の重複を意味する。
【００３４】
判定部１３は、例えば、次のように重複判定を行うことができる。判定部１３は、プレフィックス区間の最小点及び最大点を表す各インデックスキーから、プレフィックス区間のビット列の範囲を属性毎にそれぞれ抽出する。更に、判定部１３は、問い合わせ区間の最小点及び最大点を表す各インデックスキーから、問い合わせ区間のビット列の範囲を属性毎にそれぞれ抽出する。そして、判定部１３は、プレフィックス区間と問い合わせ区間とのビット列の範囲の重複を各属性についてそれぞれ判定することにより、プレフィックス区間と問い合わせ区間との重複を判定する。ここで、プレフィックス区間と問い合わせ区間とのビット列の範囲の重複とは、両区間の少なくとも一部の重複を意味する。判定部１３は、プレフィックス区間のビット列の範囲と問い合わせ区間のビット列の範囲とが重複しない属性が１つでも検出された場合に、両区間が重複しないと判定し、それ以外、即ち、全ての属性において両区間のビット列の範囲が重複する場合に、両区間が重複すると判定することができる。
【００３５】
〔動作例〕
以下、本発明の実施の形態における多次元範囲検索方法について図４を用いて説明する。図４は、上述の実施形態における検索装置１０の動作例を示すフローチャートである。以下の説明では、検索装置１０が各工程の実行主体となるが、検索装置１０に含まれる上述の各処理部や他の装置が実行主体となってもよい。
【００３６】
ここで、本実施形態における多次元範囲検索方法では、複数の属性からなるデータセットが、空間ベースの空間分割法により分割され、複数のデータページに分散配置されており、上述のインデックス格納部が存在することが前提となる。
【００３７】
まず、検索装置１０は、複数の属性からなるデータセットがマッピングされる多次元空間の一次元化に用いられる空間充填曲線上の特定区間の最小点及び最大点を表す始端インデックスキー及び終端インデックスキーを取得する（Ｓ４１）。ここで、本実施形態における多次元範囲検索方法で用いられる空間充填曲線は、上述したとおりである。また、特定区間についても上述したとおりである。
【００３８】
検索装置１０は、（Ｓ４１）で取得された始端インデックスキー及び終端インデックスキーの各ビット列に基づいて、当該特定区間に含まれるインデックスキーのビット列を表し得るプレフィックスデータを抽出する（Ｓ４２）。プレフィックスデータは、上述のとおりである。また、プレフィックスデータの抽出方法は、抽出部１２の処理として上述した手法で実現され得る。
【００３９】
続いて、検索装置１０は、（Ｓ４２）で抽出されたプレフィックスデータのプレフィックスを共通して有するインデックスキーの集合により形成される空間充填曲線上のプレフィックス区間と、多次元範囲検索の問い合わせ区間との重複を判定する（Ｓ４３）。この重複の判定方法は、判定部１３の処理として上述した手法で実現され得る。
【００４０】
〔本実施形態の作用及び効果〕
上述したように本実施形態では、空間充填曲線上の特定区間の最小点及び最大点を表す始端インデックスキー及び終端インデックスキーの各ビット列に基づいて、その特定区間に含まれるインデックスキーのビット列を表し得るプレフィックスデータが抽出され、プレフィックスデータにより表わされるプレフィックス区間と多次元範囲検索の問い合わせ区間との重複が判定される。この重複の判定により、当該特定区間が問い合わせ区間と重複するか否かを判定することができる。
【００４１】
また、本実施形態で用いられる空間充填曲線は、プレフィックスデータと、そのプレフィックスデータにより表わされるプレフィックス区間とが一対一に対応し、プレフィックスデータのプレフィックスの長さとプレフィックス区間の大きさとが負の相関を持つ特性を有するものであれば、その空間充填曲線自体は制限されない。即ち、周知の固定ルール化された空間充填曲線が利用されてもよいし、各属性のビット列の並び順を変えず、各属性のビット列同士を任意の順序で混合することで、多次元空間を一次元化する空間充填曲線が利用されてもよい。
【００４２】
このように、本実施形態によれば、プレフィックスのみ、又は、プレフィックスと少なくとも１つのワイルドカード文字とから形成される、固定長のビット列であるプレフィックスデータを用いることで、問い合わせ区間と特定区間との重複を効率的に確認することができ、ひいては、多次元範囲検索時のヒットページの検出の高速化を実現することができる。
【００４３】
更に、本実施形態によれば、上述のような特性を持つ空間充填曲線を利用するため、インデックス設計の制約、及び、データセットのページ分割手法の制約を大幅に緩和することができる。即ち、本実施形態では、Ｚ曲線やヒルベルト曲線のようなビット列の混ぜ合わせ順が固定化された空間充填曲線のみでなく、汎用化された空間充填曲線を用いることができる。従って、本実施形態によれば、範囲検索の指定内容やインデックス対象のデータセットの分布に応じた最適なインデックス設計を行うことができるため、検索環境に依存した検索処理の効率低下を防ぐことができる。
【００４４】
また、本実施形態では、始端インデックスキー及び終端インデックスキーにおける共通プレフィックス長より下位の各対象ビット列を所定ビット長で区切ることで得られる部分ビット列のビットパターンに対応する置換ルールを用いて、プレフィックスデータが抽出される。この置換ルールは、その所定ビット長で取り得る各ビットパターンについての、ビット反転及びワイルドカード文字への置換の少なくとも一方を含むものである。このように、本実施形態によれば、始端インデックスキー及び終端インデックスキーに対するビット処理により効率的にプレフィックスデータを抽出することができる。
【００４５】
また、上述のプレフィックスデータの抽出で用いられる所定ビット長は、データセットの属性数に依存しない値に設定可能である。従って、本実施形態によれば、属性数と等しいビット長のビット列を処理単位としなければならないといった制約も排除し、８ビット、１６ビット、３２ビットといったコンピュータ処理を効率化させ得る処理単位を自由に使うことができ、ひいては、範囲検索処理の効率を向上させることができる。
【００４６】
［拡張例］
上述の実施形態において、次のようにすれば、更に効率的にプレフィックスデータを抽出することができる。
【００４７】
抽出部１２は、始端インデックスキーの対象ビット列を下位から上位に向かって走査し、かつ、終端インデックスキーの対象ビット列を上位から下位に向かって走査することにより、プレフィックスデータを順次抽出する。対象ビット列とは、上述したように、始端インデックスキーと終端インデックスキーとの共通プレフィックスより下位のビット列を意味する。判定部１３は、抽出部１２で抽出された順に、プレフィックスデータに対応するプレフィックス区間と問い合わせ区間との重複を判定し、検索部１４は、判定部１３により重複すると判定された順に、対応するページ情報を検索する。
【００４８】
始端インデックスキーと終端インデックスキーとの共通プレフィックスによれば、当該特定区間を空間充填曲線上で始端インデックスキー側と終端インデックスキー側とに２分割する境界を表すことができる。そして、始端インデックスキーの対象ビット列を下位から上位に向かって走査してプレフィックスデータを抽出することは、当該特定区間の始端インデックスキーから上記境界までの区間から、始端インデックスキー側から上記境界に向かう方向にプレフィックス区間を徐々に切りだしていくことに相当する。また、当該対象ビット列の上記走査方向によれば、プレフィックス長の長いプレフィックスデータから順次抽出されるため、狭いプレフィックス区間から徐々に切り出される。
【００４９】
一方で、終端インデックスキーの対象ビット列を上位から下位に向かって走査してプレフィックスデータを抽出することは、当該特定区間の終端インデックスキーから上記境界までの区間から、上記境界側から終端インデックスキーに向かう方向にプレフィックス区間を徐々に切りだしていくことに相当する。また、当該対象ビット列の上記走査方向によれば、プレフィックス長の短いプレフィックスデータから順次抽出されるため、広いプレフィックス区間から徐々に切り出される。
【００５０】
このように、本実施形態は、Ｚ曲線のようなフラクタル形状（超立方体）のみでなく、全辺の長さが同じとはならない超直方体（プレフィックス区間）を多次元空間から分解していく。従って、拡張例によれば、空間充填曲線上の昇順、即ち、インデック順に、プレフィックスデータを抽出することができ、インデックス順にソートされた状態でページ情報を抽出することができる。これにより、データページの格納位置がインデックス順に並ぶ場合に、データページへのアクセスを効率化することができる。
【００５１】
以下に実施例を挙げ、上述の実施形態を更に詳細に説明する。本発明は以下の実施例から何ら限定を受けない。
【実施例】
【００５２】
本実施例ではＺ曲線を汎用化させた空間充填曲線が利用される。
図５は、実施例で利用される空間充填曲線及びプレフィックス区間を示す図である。本実施例では、図５に示されるように、属性ごとのビット列の混ぜ合わせ順序に自由度を持たせた空間充填曲線を用いる。この空間充填曲線で実現可能な１つの例として、Ｚ曲線が存在する。本実施例では、データセットが２次元空間にマッピングされ、その２次元空間がその空間充填曲線で一次元化される。具体的には、空間充填曲線は、３ビットの長さを持つ２つの属性のビット列「ｘ１，ｘ２，ｘ３」及び「ｙ１，ｙ２，ｙ３」を「ｙ１，ｘ１，ｙ２，ｙ３，ｘ２，ｘ３」のように混ぜ合わせる。図５に示される矢印は、空間充填曲線により二次元空間が埋め尽くされる様を表している。
【００５３】
また、図５には、４つのプレフィックスデータと、各プレフィックスデータに対応するプレフィックス区間とが表されている。左上図では、プレフィックスデータ「０＊＊＊＊＊」に対応するプレフィックス区間が斜線（グレー背景）で示される。右上図では、プレフィックスデータ「００＊＊＊＊」に対応するプレフィックス区間が斜線（グレー背景）で示される。左下図では、プレフィックスデータ「０００＊＊＊」に対応するプレフィックス区間が斜線（グレー背景）で示される。右下図では、プレフィックスデータ「００００＊＊」に対応するプレフィックス区間が斜線（グレー背景）で示される。このように、本実施例の空間充填曲線は、プレフィックスデータと、そのプレフィックスデータにより示されるプレフィックス区間とが一対一に対応する。更に、プレフィックスデータのプレフィックスの長さ（０の数）とプレフィックス区間の大きさとが負の相関を示すことが分かる。即ち、プレフィックスの長さが長い程、プレフィックス区間が小さくなり、プレフィックスの長さが短い程、プレフィックス区間が大きくなっている。
【００５４】
本実施例では、プレフィックスデータを形成するワイルドカード文字として「＊」が利用される。これにより、「＊」を０で置き換えたビット列が、そのプレフィックスデータに対応するプレフィックス区間の最小値を示し、「＊」を１で置き換えたビット列が、そのプレフィックスデータに対応するプレフィックス区間の最大値を示す。
【００５５】
本実施例では、或るデータページがカバーする区間が特定区間とされ、検索装置１０は、この特定区間の始端インデックスキーα及び終端インデックスキーβを取得し、この特定区間と、多次元範囲検索の問い合わせ区間との重複を判定する。以降、始端インデックスキーα及び終端インデックスキーβの、最上位ビットからｉ番目のビット値はα［ｉ］及びβ［ｉ］と表記される。また、最上位ビットは、０番目のビットと表記される。
【００５６】
本実施例における検索装置１０は、始端インデックスキーαと終端インデックスキーβとの共通プレフィックスを検出し、共通プレフィックス長を算出する。共通プリフィックス長は、例えば、両ビット列の排他的論理和（ＸＯＲ）で得られるビット列において、最上位から連続する０の数（number of leading zeroと呼ばれるビット演算）により、算出され得る。ここでは、共通プレフィックス長がｋと表記される。
【００５７】
検索装置１０は、始端インデックスキーα及び終端インデックスキーβにおける（ｋ＋１）番目のビット以降の対象ビット列を所定ビット長（本実施例では１）ずつ区切り、各ビットデータに対応する置換ルールを用いて、プレフィックスデータを抽出する。本実施例では、最上位ビットは０番目とされており、共通プレフィックスの２ビット下位のビット以降のビット列が対象ビット列とされたが、共通プレフィックスの１ビット下位のビット以降のビット列（ｋ番目のビットより下位のビットから形成されるビット列）を対象ビット列とし、置換ルールに、ｋ番目のビットは何もしないことを含めるようにしてもよい。
【００５８】
本実施例では、検索装置１０（抽出部１２）は、始端インデックスキー及び終端インデックスキーの各対象ビット列の参照ビットが０の場合に、その参照ビットを１に変え、かつ、その参照ビットより下位のビットをワイルドカード文字に変え、その参照ビットが１の場合にビット置換を行わない第１の置換ルール、及び、その参照ビットが１の場合に、その参照ビットを０に変え、かつ、その参照ビットより下位のビットをワイルドカード文字に変え、その参照ビットが０の場合にビット置換を行わない第２の置換ルールを持つ。これにより、検索装置１０（抽出部１２）は、始端インデックスキーの対象ビット列には第１の置換ルールを適用し、終端インデックスキーの対象ビット列には第２の置換ルールを適用する。
【００５９】
始端インデックスキー及び終端インデックスキーのビット長がｎであり、変数ｍが（ｋ＋１）以上かつ（ｎ−１）以下の正の整数とすれば、検索装置１０は、次のようにプレフィックスデータを抽出する。検索装置１０は、α［ｍ］が０であれば、αのビット列において、α［ｍ］を１に置換し、かつ、α［ｍ＋１］以降をワイルドカード文字「＊」に置換することで、プレフィックスデータの１つを抽出する。更に、検索装置１０は、β［ｍ］が１であれば、αのビット列において、α［ｍ］を０に置換し、かつ、α［ｍ＋１］以降をワイルドカード文字「＊」に置換することで、プレフィックスデータの１つを抽出する。検索装置１０は、αの対象ビット列を下位から上位に向けて１ビットずつ走査し、βの対象ビット列を上位から下位に向けて１ビットずつ走査すれば、上述の拡張例のように、インデックス順にソートされた状態で、プレフィックスデータを順次抽出するｋとができる。
【００６０】
始端インデックスキーの対象ビット列に含まれる各ビットデータと特定区間との関係は、次のように説明され得る。その対象ビット列に含まれるビットが０の場合、そのビットを１に置換して得られるビット列により表わされるインデックスキーは、特定区間内に存在することが保障される。これは、対象ビット列に含まれるビットが０ということは、始端インデックスキーが小さい側に存在しているからである。よって、上記置換ルールでは、そのビットが０から１に置換され、そのビットより下位のビットがワイルドカード文字＊に置換される。一方、その対象ビット列に含まれるビットが１の場合、そのビットを０に置換して得られるビット列により表わされるインデックスキーは、特定区間内に存在しないことのみが保障される。よって、上記置換ルールでは、そのビットの置換は行われない。
【００６１】
終端インデックスキーの対象ビット列に含まれる各ビットデータと特定区間との関係は、上記始端インデックスキーの場合の逆になる。即ち、その対象ビット列に含まれるビットが１の場合、そのビットを０に置換して得られるビット列により表わされるインデックスキーは、特定区間内に存在することが保障される。よって、上記置換ルールでは、そのビットが１から０に置換され、そのビットより下位のビットがワイルドカード文字＊に置換される。一方、その対象ビット列に含まれるビットが０の場合、そのビットを１に置換して得られるビット列により表わされるインデックスキーは、特定区間内に存在しないことのみが保障される。よって、上記置換ルールでは、そのビットの置換は行われない。
【００６２】
検索装置１０は、上述のように抽出されたプレフィックスデータに対応するプレフィックス区間と問い合わせ区間との重複を判定する。これにより、検索装置１０は、少なくとも１つのプレフィックスデータに対応するプレフィックス区間が問い合わせ区間と重複すると判定した場合、或るデータページがカバーする区間（特定区間）が問い合わせ区間と重複すると判定することができる。
【００６３】
以下、本実施例を図６、図７及び図８を用いて更に詳細に説明する。
図６は、本実施例で用いられる空間充填曲線及インデックスキーを示す図である。図６に示される空間充填曲線は、３ビットの長さを持つ２つの属性のビット列「ａ，ｂ，ｃ」及び「ｘ，ｙ，ｚ」を「ｘ，ａ，ｂ，ｙ，ｃ，ｚ」のように混ぜ合わせる。また、図６では、特定区間（或るデータページがカバーする区間）が、空間充填曲線上の実線で示されており、始端インデックスキー及び終端インデックスキーが円で囲まれて表記されている。始端インデックスキーは「０００１１０」であり、終端インデックスキーは「１０１０００」である。
【００６４】
図７は、本実施例における特定区間に含まれるプレフィックスデータの抽出を概念的に示す図である。図７では、図６の多次元インデックス構造に対して、特定区間、始端インデックスキー、終端インデックスキー、各プレフィックス区間が明示されている。特定区間は、斜線（グレー背景）で示され、特定区間から抽出される各プレフィックス区間は、特定区間内の太線で囲まれた領域で示される。
図８は、問い合わせ区間とプレフィックス区間との重複判定を概念的に示す図である。図８では、図７の内容に対して、破線で示される問い合わせ区間が更に付加されている。
【００６５】
検索装置１０は、始端インデックスキー「０００１１０」及び終端インデックスキー「１０１０００」を取得する。検索装置１０は、それらの共通プレフィックス長が０（ゼロ）であるため、始端インデックスキー及び終端インデックスキーにおける１番目以降のビット列を対象ビット列「００１１０」及び「０１０００」とする。検索装置１０は、始端インデックスキーαの対象ビット列「００１１０」を下位ビットから上位ビットに向けて１ビットずつ区分けし、終端インデックスキーβの対象ビット列「０１０００」を上位ビットから下位ビットに向けて１ビットずつ区分けする。検索装置１０は、区分けされる各ビットに置換ルールをそれぞれ適用することにより、プレフィックスデータを抽出する。
【００６６】
具体的には、検索装置１０は、始端インデックスキーの対象ビット列「００１１０」から次のようにプレフィックスデータを抽出する。α［５］が０であるため、α［５］が１に置換されることで、プレフィックスデータ「０００１１１」が抽出される。また、始端インデックスキー「０００１１０」もプレフィックスデータとして抽出される。α［４］及びα［３］が１であるため、何もせず、α［２］が０であるため、α［２］が１に置換され、かつ、α［３］以降がワイルドカード文字「＊」に置換されることで、プレフィックスデータ「００１＊＊＊」が抽出される。更に、α［１］が０であるため、α［１］が１に置換され、かつ、α［２］以降がワイルドカード文字「＊」に置換されることで、プレフィックスデータ「０１＊＊＊＊」が抽出される。
【００６７】
更に、検索装置１０は、終端インデックスキーの対象ビット列「０１０００」から次のようにプレフィックスデータを抽出する。β［１］が０であるため、何もされず、β［２］が１であるため、β［２］が０に置換され、かつ、β［３］以降がワイルドカード文字「＊」に置換されることで、プレフィックスデータ「１００＊＊＊」が抽出される。β［３］以降は０であるため、何もされない。最後に、終端インデックスキー「１０１０００」そのものもプレフィックスデータとして抽出される。
【００６８】
但し、始端インデックスキー及び終端インデックスキーの最下位ビットを置換する場合には、始端インデックスキーそのもの及び終端インデックスキーそのものもプレフィックス区間に含まれるため、その最下位ビットはワイルドカード文字「＊」に置換するようにしてもよい。このようにすれば、始端インデックスキーそのもの及び終端インデックスキーそのものを別途プレフィックスデータとして追加しなくてもよい。
【００６９】
このように、検索装置１０は、始端インデックスキー及び終端インデックスキーの各ビット列を走査することにより、プレフィックスデータ「０００１１＊＊」、「００１＊＊＊」、「０１＊＊＊＊」、「１００＊＊＊」及び「１０１０００」を抽出することができる。抽出された各プレフィックスデータにより示される各プレフィックス区間は、図７に示されるとおりとなる。
【００７０】
検索装置１０は、このように抽出された各プレフィックスデータにより示される各プレフィックス区間と、図８に示される問い合わせ区間との重複を判定する。プレフィックスデータ「０００１１＊」のプレフィックス区間は、その最大値「０００１１１」が問い合わせ区間の最小値「００１１１０」よりも小さいため、問い合わせ区間と重複しない。
【００７１】
そこで、検索装置１０は、プレフィックスデータ「００１＊＊＊」により示されるプレフィックス区間と問い合わせ区間との重複を次のように判定する。検索装置１０は、プレフィックスデータ「００１＊＊＊」から最小値「００１０００」及び最大値「００１１１１」を取得し、問い合わせ区間の最小値「００１１１０」及び最大値「１１１００１」を取得し、各属性のビット列をそれぞれ抽出する。プレフィックスデータからは、属性「ａ，ｂ，ｃ」に関し、最小値のビット列「０１０」及び最大値のビット列「０１１」が抽出され、属性「ｘ，ｙ，ｚ」に関し、最小値のビット列「０００」及び最大値のビット列「０１１」が抽出される。同様に、問い合わせ区間からは、属性「ａ，ｂ，ｃ」に関し最小値のビット列「０１１」及び最大値のビット列「１１０」が抽出され、属性「ｘ，ｙ，ｚ」に関し最小値のビット列「０１０」及び最大値のビット列「１０１」が抽出される。これにより、検索装置１０は、プレフィックス区間に関し、属性「ａ，ｂ，ｃ」のビット列の範囲「０１０」から「０１１」を抽出し、属性「ｘ，ｙ，ｚ」のビット列の範囲「０００」から「０１１」を抽出することができる。同様に、検索装置１０は、問い合わせ区間に関し、属性「ａ，ｂ，ｃ」のビット列の範囲「０１１」から「１１０」を抽出し、属性「ｘ，ｙ，ｚ」のビット列の範囲「０１０」から「１０１」を抽出することができる。検索装置１０は、属性「ｘ，ｙ，ｚ」も属性「ａ，ｂ，ｃ」もビット列の範囲が一部重複するため、プレフィックスデータ「００１＊＊＊」のプレフィックス区間と問い合わせ区間とが重複すると判定することができる。
【００７２】
プレフィックスデータ「０１＊＊＊＊」のプレフィックス区間についても同様に重複が判定される。検索装置１０は、プレフィックスデータ「０１＊＊＊＊」から最小値「０１００００」及び最大値「０１１１１１」を取得し、問い合わせ区間の最小値「００１１１０」及び最大値「１１１００１」を取得し、各属性のビット列をそれぞれ抽出する。プレフィックスデータからは、属性「ａ，ｂ，ｃ」に関し、最小値のビット列「１００」及び最大値のビット列「１１１」が抽出され、属性「ｘ，ｙ，ｚ」に関し、最小値のビット列「０００」及び最大値のビット列「０１１」が抽出される。同様に、問い合わせ区間からは、属性「ａ，ｂ，ｃ」に関し、最小値のビット列「０１１」及び最大値のビット列「１１０」が抽出され、属性「ｘ，ｙ，ｚ」に関し、最小値のビット列「０１０」及び最大値のビット列「１０１」が抽出される。これにより、検索装置１０は、プレフィックス区間に関し、属性「ａ，ｂ，ｃ」のビット列の範囲「１００」から「１１１」を抽出し、属性「ｘ，ｙ，ｚ」のビット列の範囲「０００」から「０１１」を抽出することができる。同様に、検索装置１０は、問い合わせ区間に関し、属性「ａ，ｂ，ｃ」のビット列の範囲「０１１」から「１１０」を抽出し、属性「ｘ，ｙ，ｚ」のビット列の範囲「０１０」から「１０１」を抽出することができる。検索装置１０は、属性「ｘ，ｙ，ｚ」も属性「ａ，ｂ，ｃ」もビット列の範囲が一部重複するため、プレフィックスデータ「０１＊＊＊＊」のプレフィックス区間と問い合わせ区間とが重複すると判定することができる。
【００７３】
プレフィックスデータ「１００＊＊＊」のプレフィックス区間についても同様に重複が判定される。検索装置１０は、プレフィックスデータ「１００＊＊＊」から最小値「１０００００」及び最大値「１００１１１」を取得し、問い合わせ区間の最小値「００１１１０」及び最大値「１１１００１」を取得し、各属性のビット列をそれぞれ抽出する。プレフィックスデータからは、属性「ａ，ｂ，ｃ」に関し、最小値のビット列「０００」及び最大値のビット列「００１」が抽出され、属性「ｘ，ｙ，ｚ」に関し、最小値のビット列「１００」及び最大値のビット列「１１１」が抽出される。問い合わせ区間からは、属性「ａ，ｂ，ｃ」に関し、最小値のビット列「０１１」及び最大値のビット列「１１０」が抽出され、属性「ｘ，ｙ，ｚ」に関し、最小値のビット列「０１０」及び最大値のビット列「１０１」が抽出される。これにより、検索装置１０は、プレフィックス区間に関し、属性「ａ，ｂ，ｃ」のビット列の範囲「０００」から「００１」を抽出し、属性「ｘ，ｙ，ｚ」のビット列の範囲「１００」から「１１１」を抽出することができる。同様に、検索装置１０は、問い合わせ区間に関し、属性「ａ，ｂ，ｃ」のビット列の範囲「０１１」から「１１０」を抽出し、属性「ｘ，ｙ，ｚ」のビット列の範囲「０１０」から「１０１」を抽出することができる。ここで、属性「ａ，ｂ，ｃ」において、両区間が重複しないため、検索装置１０は、プレフィックスデータ「１００＊＊＊」のプレフィックス区間と問い合わせ区間とが重複しないと判定することができる。
【００７４】
また、上記例は、１ビットずつ走査する置換ルールが用いられたが、複数ビットずつ走査する置換ルールが用いられたとしても、上記例と同じプレフィックスデータを抽出することは可能である。例えば、コンピュータでの処理を効率化するために、ｓビットずつ走査する置換ルールを用いることができる。この場合、置換ルールは、ｓビットで取り得る全てのビットパターンの各々に対して、上述の置換ルールと同じ結果となるような、ビット反転及びワイルドカード文字への置換の少なくとも一方をそれぞれ含むように設定されればよい。例えば、２ビットずつのビット走査を行う場合には、参照ビット列の全ビットパターン「００」、「０１」、「１０」及び「１１」についての置換ルールがそれぞれ設定される。具体的には、参照ビット列が「００」であれば、その参照ビット列を「０１」に置換し、かつ、その参照ビット列よりも下位の各ビットを「＊」に置換するパターンと、その参照ビット列を「１＊」に置換し、かつ、その参照ビット列よりも下位の各ビットを「＊」に置換するパターンとが実行される。参照ビット列が「０１」であれば、その参照ビット列を「１＊」に置換し、かつ、その参照ビット列よりも下位の各ビットを「＊」に置換するパターンが実行される。参照ビット列が「１０」であれば、その参照ビット列を「１１」に置換し、かつ、その参照ビット列よりも下位の各ビットを「＊」に置換するパターンが実行される。参照ビット列が「１１」であれば、置換がなされない。
【００７５】
このように、本実施例によれば、或るデータページをカバーする特定区間における始端インデックスキー及び終端インデックスキーの各ビット列に対する簡単なビット演算により、特定区間に含まれるプレフィックス区間を効率的に抽出することができ、更には、各プレフィックス区間を表す各プレフィックスデータと問い合わせ区間とに関する重複も簡易なビット演算により効率的に判定することができる。
【００７６】
また、上記実施例では、Ｚ曲線を汎用化させた空間充填曲線が例示されたが、プレフィックスデータとプレフィックス区間との上述のような対応関係を持つ空間充填曲線であれば、ヒルベルト曲線やその派生曲線であっても同様の作用及び効果を得ることができる。この場合には、ヒルベルト曲線やその派生曲線に対応する置換ルールが設けられれば良い。
【００７７】
なお、上述の説明で用いたフローチャートでは、複数の工程（処理）が順番に記載されているが、本実施形態で実行される工程の実行順序は、その記載の順番に制限されない。本実施形態では、図示される工程の順番を内容的に支障のない範囲で変更することができる。
【符号の説明】
【００７８】
２  ＣＰＵ
３  メモリ
４  入出力Ｉ／Ｆ
１０  多次元範囲検索装置（検索装置）
１１  取得部
１２  抽出部
１３  判定部
１４  検索部
【図１】
2015018497.tif 000003
【図２】
2015018497.tif 000004
【図３】
2015018497.tif 000005
【図４】
2015018497.tif 000006
【図５】
2015018497.tif 000007
【図６】
2015018497.tif 000008
【図７】
2015018497.tif 000009
【図８】
2015018497.tif 000010