(57)【要約】【課題】  大量データを対象とする、複数の属性によるそのデータの参照処理を、高速に実行する。【解決手段】  データに含まれる複数の属性値の内、任意の特定の属性値を受け付ける入力手段と、そのデータを格納する記憶手段に対するそのデータのアドレスを、その特定の属性値の特性とその記憶手段の特性とに対応するように、その特定の属性値を結合して得られるアドレスにおいて特定の値を持つその属性値の組み合わせに対応する複数のアドレスがより互いに近接するように、出力する変換手段と、を含む。【選択図】      図１
2014229105.tif 000002
【特許請求の範囲】
【請求項１】
データに含まれる複数の属性値の内、任意の特定の前記属性値を受け付ける入力手段と、
前記データを格納する記憶手段に対する前記データのアドレスを、前記入力手段が受け付けた前記特定の属性値の特性と前記記憶手段の特性とに対応するように、前記特定の属性値を結合して得られる前記アドレスにおいて特定の値を持つ、前記属性値の組み合わせに対応する複数の前記アドレスがより互いに近接するように、出力する変換手段と、を含む
アドレス生成装置。
【請求項２】
前記変換手段は、前記データの種別を示す種別情報に基づいて、前記アドレスを出力する
ことを特徴とする請求項１記載のアドレス生成装置。
【請求項３】
前記変換手段は、前記属性値を結合しかつビットの並び順を変更した前記アドレスを出力する
ことを特徴とする請求項１または２記載のアドレス生成装置。
【請求項４】
前記変換手段は、前記属性値のビットの並び順を反転するように前記ビットの並び順を変更した前記アドレスを出力する
ことを特徴とする請求項３記載のアドレス生成装置。
【請求項５】
前記変換手段は、前記属性値間でのビットの入れ替えにより前記ビットの並び順を変更した前記アドレスを出力する
ことを特徴とする請求項３または４記載のアドレス生成装置。
【請求項６】
前記変換手段は、前記属性値の結合の並び順を変更することにより前記ビットの並び順を変更した前記アドレスを出力する
ことを特徴とする請求項３乃至５のいずれか１項に記載のアドレス生成装置。
【請求項７】
複数の属性値を含むデータを記憶する記憶手段と、
前記データに含まれる複数の前記属性値の内、任意の特定の前記属性値を受け付ける入力手段と、
前記データを格納する記憶手段に対する前記データのアドレスを、前記入力手段が受け付けた前記特定の属性値の特性と前記記憶手段の特性とに対応するように、前記特定の属性値を結合して得られる前記アドレスにおいて特定の値を持つ、前記属性値の組み合わせに対応する複数の前記アドレスがより互いに近接するように、出力する変換手段と、を含む
情報処理装置。
【請求項８】
アドレス生成装置が、
データに含まれる複数の属性値の内、任意の特定の前記属性値を受け付け、
前記データを格納する記憶手段に対する前記データのアドレスを、前記受け付けた前記特定の属性値の特性と前記記憶手段の特性とに対応するように、前記特定の属性値を結合して得られる前記アドレスにおいて特定の値を持つ、前記属性値の組み合わせに対応する複数の前記アドレスがより互いに近接するように、出力する
アドレス生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶手段をアクセスする技術に関する。
【背景技術】
【０００２】
近年、センサーや端末などから時系
列的に得られるセンサーデータを処理することで社会インフラ（インフラストラクチャー、基盤）のスマート化を実現するといった、新しい情報処理技術が進展しつつある。
【０００３】
一般的に、そのようなセンサーデータは、例えば位置、速度及び走行距離などといった、複数の属性から構成されている。
【０００４】
具体的には、そのようなセンサーデータとして、非特許文献１で論じられるようなストリーミング・データ（例えば、http://udbl2.it.uu.se/LR/cardatapoints10.out）がある。
【０００５】
記憶領域（メモリ、記憶手段）に格納されたセンサーデータの中から、例えばある位置と速度とを持つセンサーデータを参照するためには、その位置とその速度との２つの属性を用いて、その記憶領域に格納された該当するセンサーデータを特定する必要がある。
【０００６】
一般的な記憶手段において、その記憶領域は、１次元参照による高速なデータ参照を可能とする。しかしながら、その記憶領域は、多次元参照、すなわち複数の属性、によりデータを高速に参照することを、その構造上原理的に難しいものとしている。
【０００７】
上述のように、一般的な記憶手段において、複数の属性によりデータを高速に参照することは困難であるという問題点がある。
【０００８】
一方、特許文献１は、多次元参照が可能な記憶手段として、連想メモリ（ＣＡＭ）を開示する。図１４は、特許文献１に開示されるような連想メモリを含む、情報処理装置９０１の構成を示すブロック図である。図１４に示すように、その情報処理装置９０１は、参照キー生成部９１１と連想メモリ９４１とから構成される。
【０００９】
参照キー生成部９１１は、データを構成する各属性の属性値６９２を順に結合し、キー情報６９１（ビット列）を生成し、出力する。
【００１０】
一方、連想メモリ９４１は、そのキー情報６９１に対応するそのデータを、リードデータ６９３として出力する。換言すると、連想メモリ９４１は、データの一部をキー情報６９１としてそのデータを参照することが可能な、特殊な記憶装置である。そして、この参照は、複数の属性を結合したキー情報６９１による参照であり、いわゆる多次元参照である。
【００１１】
しかしながら、連想メモリ９４１は、特殊な構成が必要であるため、大容量化が困難であり、センサーデータのような大量データの格納には不向きである。また、連想メモリ９４１の記憶素子における参照速度（アクセス速度）は、一般的な記憶素子のそれと比較して、遅いことが知られている。
【００１２】
即ち、特許文献１の技術は、大量データを対象とする処理には向いていないという問題点がある。
【００１３】
特許文献２は、上述の問題点を解決する技術を開示する。
【００１４】
具体的には、特許文献２は、ハッシュテーブルに関する技術を開示する。そのハッシュテーブルは、メモリに格納された内容を、その内容に対応するキーに基づいて参照する場合の、その参照の実行を高速にする。ここで、ハッシュテーブルは、ハッシュ値をインデックスとして、その内容を参照するために使用される。そのハッシュ値は、そのキーがハッシュ関数によりマッピングされたものである。
【００１５】
図１５は、ハッシュ関数を用いてアドレスを生成する手段を含む情報処理装置９０２の構成を示す図である。図１５に示すように、情報処理装置９０２は、ハッシュアドレス生成部９１２とデータ記憶部９４２とから構成される。
【００１６】
ハッシュアドレス生成部９１２は、検索の引数として複数の属性値６９２を受け取る。次にハッシュアドレス生成部９１２は、それらの属性値６９２を、ハッシュ関数を用いて１次元の数値（アドレス６９４）に変換する。
【００１７】
データ記憶部９４２は、一般的な記憶装置であり、すなわち、１次元のアドレス６９４によりデータを参照することが可能な記憶手段である。
【００１８】
上述のように、情報処理装置９０２は、大容量かつ高速アクセス可能なデータ記憶部９４２に対して、多次元参照を可能とする。
【先行技術文献】
【特許文献】
【００１９】
【特許文献１】特開平５−１９８１８６号公報
【特許文献２】特開昭６０−２５４２５４号公報
【非特許文献】
【００２０】
【非特許文献１】Arvind Arasu, Mitch Cherniack, Eduardo Galvez, David Maier, Anurag Maskey, Esther Ryvkina, Michael Stonebraker and Richard Tibbetts, ”Linear Road: A Stream Data Management Benchmark”, http://www.cs.brandeis.edu/%7Elinearroad/linear-road.pdf
【発明の概要】
【発明が解決しようとする課題】
【００２１】
しかしながら、上述の先行技術文献に記載された技術においては、大量データを対象とする、複数の属性によるそのデータの参照処理を、高速に実行することができない場合があるという問題点がある。
【００２２】
その理由は、上述した特許文献に記載された技術においては、特性の異なる様々な記憶装置について、その性能を十分に引き出すことができないからである。
【００２３】
具体的には、特許文献１に係る情報処理装置９０１は、連想メモリ９４１に特化されたシステムであるからである。
【００２４】
また、特許文献２の技術に係る情報処理装置９０２のハッシュアドレス生成部９１２で生成されるアドレス６９４は、規則性が乏しく、データ記憶部９４２に対してランダムなアクセスを行うからである。
【００２５】
即ち、特許文献２の技術を利用した場合、データ記憶部９４２が連続アクセスに強いＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）や、参照の局所性に性能が依存するキャッシュメモリである場合、その性能を十分に引き出すことができない場合がある。ここで、連続アクセスに強いＤＲＡＭとは、例えば、ＤＤＲ  ＳＤＲＡＭ(Ｄｏｕｂｌｅ  Ｄａｔａ  Ｒａｔｅ  Ｓｙｎｃｈｒｏｎｏｕｓ  Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）である。
【００２６】
本発明の目的は、上述した問題点を解決するアドレス生成装置、情報処理意装置及びアドレス生成方法を提供することにある。
【課題を解決するための手段】
【００２７】
本発明のアドレス生成装置は、データに含まれる複数の属性値の内、任意の特定の前記属性値を受け付ける入力手段と、前記データを格納する記憶手段に対する前記データのアドレスを、前記入力手段が受け付けた前記特定の属性値の特性と前記記憶手段の特性とに対応するように、前記特定の属性値を結合して得られる前記アドレスについて、特定の値を持つ前記属性値の組み合わせに対応する複数の前記アドレスがより互いに近接するように、出力する変換手段と、を含む。
【００２８】
本発明の情報処理装置は、複数の属性値を含むデータを記憶する記憶手段と、前記データに含まれる複数の前記属性値の内、任意の特定の前記属性値を受け付ける入力手段と、前記記憶手段に対する前記データのアドレスを、前記入力手段が受け付けた前記特定の属性値の特性と前記記憶手段の特性とに対応するように、前記特定の属性値を結合して得られる前記アドレスについて、特定の値を持つ前記属性値の組み合わせに対応する複数の前記アドレスがより互いに近接するように、出力する変換手段と、を含む。
【００２９】
本発明のアドレス生成方法は、アドレス生成装置が、データに含まれる複数の属性値の内、任意の特定の前記属性値を受け付け、前記データを格納する記憶手段に対する前記データのアドレスを、前記受け付けた前記特定の属性値の特性と前記記憶手段の特性とに対応するように、前記特定の属性値を結合して得られる前記アドレスについて、特定の値を持つ前記属性値の組み合わせに対応する複数の前記アドレスがより互いに近接するように、出力する。
【発明の効果】
【００３０】
本発明は、大量データを対象とする、複数の属性によるそのデータの参照処理を、高速に実行することが可能になるという効果がある。
【図面の簡単な説明】
【００３１】
【図１】図１は、第１の実施形態に係るアドレス生成装置の構成を示すブロック図である。
【図２】図２は、第１の実施形態におけるデータの一例を示す図である。
【図３】図３は、第１の実施形態に係るアドレス生成装置を含む情報処理装置の構成を示すブロック図である。
【図４】図４は、第１の実施形態におけるデータ記憶部の構成を示すブロック図である。
【図５】図５は、第１の実施形態における変換部の構成を示すブロック図である。
【図６】図６は、第１の実施形態における属性値の一例を示す図である。
【図７】図７は、第１の実施形態におけるキー情報からアドレスへの変換動作の一例を示す図である。
【図８】図８は、第１の実施形態における車両の存在状態を示す図である。
【図９】図９は、第１の実施形態における属性値の一例を示す図である。
【図１０】図１０は、第１の実施形態におけるキー情報からアドレスへの変換動作の一例を示す図である。
【図１１】図１１は、第１の実施形態における高速道路を区分けしたイメージを示す図である。
【図１２】図１２は、第１の実施形態におけるキー情報からアドレスへの変換動作の一例を示す図である。
【図１３】図１３は、第２の実施形態に係るアドレス生成装置の構成を示すブロック図である。
【図１４】図１４は、連想記憶部を含む関連技術の構成を示す図である。
【図１５】図１５は、ハッシュアドレス生成部を含む関連技術の構成を示す図である。
【発明を実施するための形態】
【００３２】
本発明を実施するための形態について図面を参照して詳細に説明する。尚、各図面及び明細書記載の各実施形態において、同様の構成要素には同様の符号を付与し、適宜説明を省略する。
【００３３】
＜＜＜第１の実施形態＞＞＞
図１は、本発明の第１の実施形態に係るアドレス生成装置１００の構成を示すブロック図である。
【００３４】
図１を示すように、本実施形態に係るアドレス生成装置１００は、変換部１１０と、入力部１３０とを含む。
【００３５】
＝＝＝入力部１３０＝＝＝
入力部１３０は、データ６０１（後述）に含まれる複数の属性値の内、特定の属性値６０２（第１属性値乃至第ｎ属性値から構成される属性値）を受け付ける。特定の属性値６０２の属性値数は、「ｎ」である。
【００３６】
図２は、データ６０１の構造一例を示す図である。図２に示すように、データ６０１は、属性値（ａ）から属性値（ｘ）までの任意の数の属性値を含む。例えば、データ６０１は、個々の文字を属性値とする文字列である。また、データ６０１は、速度や位置等を持つ車両情報などであってもよい。
【００３７】
即ち、データ６０１を構成する各属性値は、異なる次元の値である。そして、データ６０１は、その値を組み合わせた多次元データである。尚、図２に示すデータ６０１の例に係わらず、アドレス生成装置１００は、１次元のデータを処理することも可能である。
【００３８】
各属性値の値(内容)は、ビット列である。
【００３９】
入力部１３０は、データ６０１に含まれる属性値の内、特定の属性値６０２（例えば、属性値数ｎ＝２の場合、第１属性値＝属性値（ａ）及び第２属性値＝属性値（ｂ））を受け付ける。その特定の属性値６０２の値の組み合わせ（例えば、属性値（ａ）の値と属性値（ｂ）の値からなるビット列）は、データ６０１毎にユニークであるものとする。そして、その特定の属性値６０２の値の組み合わせがデータ６０１毎にユニークである限り、その特定の属性値６０２は、任意の属性値であってよい。
【００４０】
＝＝＝変換部１１０＝＝＝
変換部１１０は、入力部１３０からのその特定の属性値６０２の特性と記憶手段（不図示）の特性とに対応するアドレス６０３を出力する。ここで、アドレス６０３は、その特定の属性値６０２を結合して得られるアドレスである。そして、変換部１１０は、特定の値を持つ属性値６０２の組み合わせに対応する複数のアドレスが、互いにより近接するように、アドレス６０３を出力する。尚、その記憶手段は、データ６０１を記憶する記憶手段である。そのアドレス６０３は、その特定の属性値６０２に対応するそのデータ６０１の、その記憶手段における格納アドレスである。
【００４１】
具体的には、変換部１１０は、複数の属性値６０２（第１−第ｎの属性値）を結合しかつビットの並び順を変更したアドレス６０３を出力する。
【００４２】
例えば、変換部１１０は、各属性値６０２のビットの並び順を反転（上位と下位の位置を反転）するようにビットの並び順を変更し、そのビットの並び順を変更された複数の属性値を結合したアドレス６０３を出力する。
【００４３】
また、変換部１１０は、属性値６０２間（例えば、第１属性値と第２属性値との間）でのビットの入れ替えによりビットの並び順を変更し、そのビットの並び順を変更された複数の属性値を結合したアドレス６０３を出力するようにしてもよい。
【００４４】
また、変換部１１０は、複数の属性値６０２の結合の順番、即ち、並び順を変更することによりビットの並び順を変更したアドレス６０３を出力するようにしてもよい。
【００４５】
更に、変換部１１０は、上述のビット操作の組み合わせを含む、他の任意のビット操作を施した、属性値６０２を結合したアドレス６０３を出力するようにしてよい。
【００４６】
図３は、アドレス生成装置１００を含む情報処理装置１０１の構成を示す図である。図３に示すように、情報処理装置１０１は、アドレス生成装置１００とデータ記憶部４００とを含む。
【００４７】
情報処理装置１０１において、アドレス生成装置１００は、複数の属性値６０２を入力とし、アドレス６０３（１次元の数値情報）を生成し、データ記憶部４００へ出力する。
【００４８】
＝＝＝データ記憶部４００＝＝＝
データ記憶部４００は、データ６０１を記憶する記憶手段である。データ記憶部４００は、アドレス生成装置１００から出力されたアドレス６０３によってリードデータ６０６を読み出し、出力する。また、データ記憶部４００は、リード・ライト制御信号６０４によりライトを指定されると、ライトデータ６０５を書き込む。このライトデータ６０５及びリードデータ６０６の一例が、図２に示すデータ６０１である。
【００４９】
データ記憶部４００は、例えば、ＤＲＡＭやＳＲＡＭ（Ｓｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＭＲＡＭ（Ｍａｇｎｅｔｏｒｅｓｉｓｔｉｖｅ  ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、Ｆｌａｓｈ  ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）などといった、どのような記憶手段であってもよい。また、データ記憶部４００は、キャッシュ記憶部などの他の高速記憶装置と組み合わされた記憶手段であってもよい。
【００５０】
図４は、データ記憶部４００の構成の一例を示すブロック図である。図４に示すように、データ記憶部４００は、キャッシュ記憶部４１０と、ＤＲＡＭ４２０とを含む。
【００５１】
＝＝＝キャッシュ記憶部４１０＝＝＝
キャッシュ記憶部４１０は、例えば、マイクロプロセッサに搭載されるような、一般的なキャッシュ機構である。
【００５２】
キャッシュ記憶部４１０を備えたデータ記憶部４００を効率的にアクセスするためには、キャッシュの特性である空間局所性と時間局所性とを最大限に生かすように制御することが必要である。
【００５３】
＝＝＝ＤＲＡＭ４２０＝＝＝
ＤＲＡＭ４２０は、主記憶装置に使用されるような、一般的な記憶手段である。
【００５４】
図５は、変換部１１０の構成の一例を示すブロック図である。図５に示すように、変換部１１０は、参照キー生成部１１１とキー・アドレス変換部１１２とを含む。
【００５５】
＝＝＝参照キー生成部１１１＝＝＝
参照キー生成部１１１は、入力部１３０から受け取った属性値６０２を順に結合し、キー情報６１１を生成し、キー・アドレス変換部１１２へ出力する。ここで、キー情報６１１は、ビット列（１次元の情報）である。
【００５６】
＝＝＝キー・アドレス変換部１１２＝＝＝
キー・アドレス変換部１１２は、受け取ったキー情報６１１のビット列をシャッフルしたり、反転したりして、アドレス６０３に変換し、出力する。
【００５７】
次に、具体的な属性値６０２の例を示して、ビット列をシャッフルしたり反転したりする、キー・アドレス変換部１１２によるビット操作機能の詳細を説明する。
【００５８】
第１の例として、文字列データ（後述）の場合について説明する。
【００５９】
図６は、入力部１３０が受け取る属性値６０２の一例を示す図である。図６は、第１−第４属性値６０２のそれぞれが、文字の「Ａ」、「Ｂ」、「Ｃ」及び「Ｄ」であることを示す。以下では、データ６０１が、図６に示すような文字の属性値６０２からなる文字列を含む場合、そのデータを文字列データと呼ぶ。
【００６０】
文字列データは、例えば、物の名称などのアルファベットの文字列を含む。その名称の文字のそれぞれは、属性値として、例えば固定の属性値数（文字数）に対して左詰めで格納される。その名称の文字数が、その固定の属性値数に満たない場合、右側のその属性値には無効コード（例えば、「０ｘ００（全てのビットが「０」の８ビットのビット列）」）が挿入される。ここで、文字列データの左側を上位、右側を下位とする。
【００６１】
参照キー生成部１１１は、第１−第４属性値６０２を結合し、キー情報６１１を生成する。例えば、このキー情報６１１をそのままアドレス６０３として使用し、データ記憶部４００を参照する場合、無効コードが挿入された部分は、そのアドレスの下位ビットに対応する。このため、値が連続するそのアドレスに、無駄なアドレス（有効なデータ６０１を、記憶しないアドレス）が存在する。その無駄なアドレスは、挿入された無効コードのビット幅分のアドレス範囲から、無効コードを含むデータ６０１を格納するアドレスを除いたアドレスである。「挿入された無効コードのビット幅分のアドレス範囲」は、例えば挿入された無効コードが１つの場合、８ビット幅分のアドレス（２５６個のアドレス）範囲である。この場合、そのアドレス範囲に格納される６０１は、１つである。従って、無駄なアドレスは、２５６個のアドレスから１個のアドレス（無効コードを含むデータ６０１を格納するアドレス）を引いた、２５５個のアドレスである。
【００６２】
従って、そのアドレスは、キャッシュ記憶部４１０の特性である空間局所性を、十分に生かせない。
【００６３】
キー・アドレス変換部１１２は、参照キー生成部１１１が生成したキー情報６１１を反転、すなわち、右詰めにしたアドレス６０３を生成し、出力する。
【００６４】
図７は、文字列データに含まれる属性値６０２が結合されたキー情報６１１を、変換部１１０がアドレス６０３に変換する例を示す図である。
【００６５】
図７に示すように、キー・アドレス変換部１１２は、キー情報６１１に含まれる第１−第４属性値６０２の上位と下位とを、属性値６０２同士で入れ替え、キー情報６１１を反転したアドレス６０３を生成する。
【００６６】
こうして、変換部１１０は、無効コード以外の値（特定の値）の属性値６０２の値の組み合わせに対応する複数のアドレスがより互いに近接するように、アドレス６０３を出力する。例えば、そのより互いに近接する複数のアドレス６０３は、第２−第４属性値６０２の値が無効コードのその組み合わせに対応するアドレスである。また、そのより互いに近接する複数のアドレス６０３は、第３−第４属性値６０２の値が無効コードのその組み合わせに対応するアドレスである。更に、そのより互いに近接する複数のアドレス６０３は、第４属性値６０２の値が無効コードのその組み合わせに対応するアドレスである。
【００６７】
これらのアドレス６０３は、その文字列の属性値６０２の特性と、データ記憶部４００の特性とに対応するように出力されるアドレスである。その文字列の属性値６０２の特性は、属性値６０２が無効コードである場合があるという特性である。データ記憶部４００の特性は、キャッシュ記憶部４１０を含むことにより、空間局所性を有するという特性である。
【００６８】
尚、キー・アドレス変換部１１２は、キー情報６１１に含まれる第１−第４属性値６０２を、ビット単位で入れ替え、キー情報６１１を反転したアドレス６０３を生成するようにしてもよい。
【００６９】
第２の例として、位置情報データ（後述）の場合について説明する。
【００７０】
図８は、ある都市の車両の存在状態を、その都市の分割された区画毎に示す図である。図８において、斜線の施された区画は、車両が密集している区画を示す。図８に示すように、各区画は、ｘ軸方向の２ビットの番号（ｘ１、ｘ０）と、ｙ軸方向の２ビットの番号（ｙ１、ｙ０）とで特定される。
【００７１】
図９は、入力部１３０が受け取る属性値６０２の一例を示す図である。図９に示すように、第１属性値６０２及び第２属性値６０２のそれぞれは、ｘ軸方向の番号（ｘ１、ｘ０）が「０、０」及びｙ軸方向の番号（ｙ１、ｙ０）が「０、１」である。即ち、図９に示す属性値６０２は、図８の最左端の下から２番目の区画を指す。以下では、データ６０１が、図９に示すような位置を示す属性値６０２を含む場合、そのデータを位置情報データと呼ぶ。
【００７２】
参照キー生成部１１１は、例えば、第１属性値６０２の「ｘ１、ｘ０」、第２属性値６０２の「ｙ１、ｙ０」の順で、これらを結合し、キー情報６１１の「ｘ１、ｘ０、ｙ１、ｙ０、」を生成する。
【００７３】
図１０は、位置情報データに含まれる属性値６０２が結合されたキー情報６１１を、変換部１１０がアドレス６０３に変換する例を示す図である。また、図１０は、その都市に存在する車両の車両情報を参照する際に、そのキー情報６１１をアドレスとして用いた場合とアドレス６０３を用いた場合との、参照処理のイメージを示す。
【００７４】
図１０に示すように、キー・アドレス変換部１１２は、例えば、シャッフル処理により、キー情報６１１の「ｘ１、ｘ０、ｙ１、ｙ０、」からアドレス６０３の「ｘ１、ｙ１、ｘ０、ｙ０」を生成する。
【００７５】
こうして、変換部１１０は、属性値６０２のそれぞれの下位ビット（ｘ０及びｙ０）が変化した値（特定の値）の属性値６０２の値の組み合わせに対応する複数のアドレスがより互いに近接するように、アドレス６０３を出力する。換言すると、変換部１１０は、属性値６０２のそれぞれの上位ビット（ｘ１及びｙ１）が同一の値（特定の値）の属性値６０２の組み合わせに対応する複数のアドレスがより互いに近接するように、アドレス６０３を出力する。
【００７６】
次に、アドレス６０３によるデータ記憶部４００のアクセスについて、具体的に説明する。
【００７７】
例えば、キャッシュ記憶部４１０は、アドレスが隣接する４つのデータ６０１を保持する構成であると仮定する。この場合、例えば図８に示す区画に係る第１のブロックとしてキャッシュ記憶部４１０に保持されるデータ６０１は、データ記憶部４００に対するアドレスが「０、０、０、０」から「０、０、１、１」までのデータ６０１である。更に、第２のブロックは、データ記憶部４００に対するアドレスが「０、１、０、０」から「０、１、１、１」までのデータ６０１である。第３及び第４のブロックも同様である。
【００７８】
まず、比較のために、キー情報６１１をアドレスとして用いた場合を説明する。キー情報６１１の「ｘ１、ｘ０、ｙ１、ｙ０」を用いる場合、例えば、その第１のブロックとしてキャッシュ記憶部４１０に保持されるデータ６０１は、図１０に示す区画群８２１（太枠で囲んだ最左端の４つの区画）のデータ６０１である。即ち、密集していない区画（最左端の上の２つの区画）の車両情報をも、アクセスすることになる。以降に続く第２−第４のブロックについても同様である。
【００７９】
従って、キー情報６１１をそのまま用いたアドレスは、キャッシュ記憶部４１０の特性である空間局所性を、十分に生かせない。
【００８０】
一方、アドレス６０３の「ｘ１、ｙ１、ｘ０、ｙ０」を用いる場合、例えば、その第１のブロックとしてキャッシュ記憶部４１０に保持されるデータ６０１は、図１０に示す区画群８２２（太枠で囲んだ一番下の左側の２つの区画と下から２段目の左側の２つの区画）のデータ６０１である。即ち、密集している区画の車両情報だけを、アクセスすることができる。
【００８１】
更に、第４のブロックとして、キャッシュ記憶部４１０に保持されるデータ６０１は、データ記憶部４００に対するアドレスが「１、１、０、０」から「１、１、１、１」までのデータ６０１である。即ち、第４のブロックとしてキャッシュ記憶部４１０に保持されるデータ６０１は、図１０に示す区画群８２３（太枠で囲んだ上から２番目の右側の２つの区画と一番上の右側の２つの区画）のデータ６０１である。この場合も、密集している区画の車両情報だけを、アクセスすることができる。また、第２及び３のブロックをアクセスする必要はない。
【００８２】
以上説明したように、アドレス６０３を用いる場合、密集地帯の情報だけがキャッシュ記憶部４１０に格納され、高速にデータを参照することが可能となる。
【００８３】
第３の例として、道路情報データ（後述）の場合について説明する。
【００８４】
図１１は、ある高速道路を区分けしたイメージを示す図である。
【００８５】
図１１において、レーンＬは、その高速道路の車線の番号であり、例えば「０」から順に車線毎に付与される。セグメントｓは、その高速道路を進行方向について所定の間隔で分割した区分であり、例えば「０」から順に、区分の並び順に区分毎に付与される。また、方向ｄは、その高速道路上の車両の進行方向を示し、例えば「右」及び「左」のいずれかを付与される。
【００８６】
図１２は、参照キー生成部１１１が道路情報データに含まれる属性値６０２が結合して生成したキー情報６１１を、変換部１１０がアドレス６０３に変換する例を示す図である。
【００８７】
図１２に示すように、第１−第３属性値６０２のそれぞれは、方向ｄ、レーンＬ及びセグメントｓである。図１２に示す例では、方向ｄが「左」、レーンＬが「０」、セグメントｓが「５０」である。以下では、データ６０１が、図１２に示すような道路の区分を示す属性値６０２を含む場合、そのデータを道路情報データと呼ぶ。
【００８８】
図１２に示すように、変換部１１０は、属性値６０２の順番を入れ替える操作により、キー情報６１１の「方向ｄ（左）、レーンＬ（０）、セグメントｓ（５０）」からアドレス６０３の「セグメントｓ（５０）、レーンＬ（０）、方向ｄ（左）」を生成する。
＜＜＜道路情報データ参照の実施例＞＞＞
次に、図１４に示すアドレス６０３を用いた場合の、道路情報データの参照処理の実施例を説明する。
【００８９】
具体的な、データ６０１は、「http://udbl2.it.uu.se/LR/cardatapoints10.out」に示されるストリーミング・データである。このストリーミング・データは、高速道路上を走行する車両から発せられる位置報告の履歴情報である。このストリーミング・データは、高速道路の識別情報、方向ｄ、レーンＬ、セグメントｓ及び車両位置などを含む。
【００９０】
その方向ｄは、車両が位置報告を発する時点の、その車両が移動する方向（東向きの場合「０」、西向きの場合「１」）を示す。
【００９１】
そのレーンＬは、車両が位置報告を発する時点の、その車両が存在する車線（入り口ランプの場合「０」、通行車線の場合「１」−「３」、出口ランプの場合「４」）を示す。
【００９２】
そのセグメントｓは、車両が位置報告を発する時点の、その車両が存在する区分（「０」−「９９」で示される１マイル長の区分のいずれか）を示す。
【００９３】
その車両位置は、その高速道路の西端からの水平位置をフィートで示す。
このストリーミング・データの方向ｄ、レーンＬ及びセグメントｓのそれぞれを、第１属性値６０２、第２属性値６０２及び第３属性値６０２とする。
【００９４】
キー情報６１１をアドレスとして、そのストリーミング・データを記憶したデータ記憶部４００を参照した場合の、キャッシュ記憶部４１０のヒット率は、３２％であった。そのキー情報６１１は、参照キー生成部１１１がそれらの第１−第３属性値６０２を結合した、キー情報６１１の「方向ｄ、レーンＬ、セグメントｓ」である。キャッシュ記憶部４１０は、１キロバイト、１ウェイ、ＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔｌｙ  Ｕｓｅｄ）、３２バイトラインキャッシュ記憶部である。
【００９５】
次に、キー・アドレス変換部１１２が生成したアドレス６０３の「セグメントｓ、レーンＬ、方向ｄ」を用いた場合、そのヒット率は８７％であった。
【００９６】
以上より、アドレス生成装置１００は、高いヒット率を実現することにより、そのデータ・ストリームのデータ参照を非常に効率良く、従って高速に、実行することができる。
【００９７】
本実施形態のアドレス生成装置１００において、入力部１３０は、変換部１１０の一部として含まれてもよい。
【００９８】
上述した本実施形態における第１の効果は、大量データを対象とする、複数の属性によるそのデータの参照処理を、高速に実行することを可能にする点である。
【００９９】
その理由は、変換部１１０が属性値６０２の特性とデータ記憶部４００の特性とに対応するように属性値６０２を結合した、アドレス６０３を出力するようにしたからである。
【０１００】
上述した本実施形態における第２の効果は、比較的少量のデータを対象とした場合においても、複数の属性によるそのデータの参照処理を、高速に実行することを可能にする点である。
【０１０１】
その理由は、アドレス生成装置１００が、一般的な記憶素子により構成されるデータ記憶部４００に対応可能だからである。即ち、参照速度（アクセス速度）が比較的に遅い記憶素子で構成される連想メモリを使用する必要がないからである。
【０１０２】
＜＜＜第２の実施形態＞＞＞
次に、本発明の第２の実施形態について図面を参照して詳細に説明する。以下、本実施形態の説明が不明確にならない範囲で、前述の説明と重複する内容については説明を省略する。
【０１０３】
図１５は、本発明の第２の実施形態に係るアドレス生成装置２００の構成を示すブロック図である。
【０１０４】
図１５に示すように、本実施形態におけるアドレス生成装置２００は、第１の実施形態のアドレス生成装置１００と比べて、変換部１１０に替えて変換部２１０を含む。
【０１０５】
＝＝＝変換部２１０＝＝＝
変換部２１０は、データ種別（種別情報とも呼ばれる）６２０の入力を受け付ける。次に、変換部２１０は、そのデータ種別６２０に基づいて、アドレス６０３を出力する。
【０１０６】
データ種別６２０は、入力部１３０に入力される属性値６０２が、例えば、文字列データ、位置情報データ及び道路情報データなどのいずれの種別のデータ６０１に含まれる属性値６０２であるかを示す識別情報である。
【０１０７】
データ種別６２０は、属性値６０２の１つとして、アドレス生成装置２００に入力されてもよい。この場合、入力部１３０は、その属性値６０２をデータ種別６２０として変換部２１０に出力するようにしてよい。
【０１０８】
変換部２１０は、変換部１１０と同様に、属性値６０２を結合しかつビットの並び順を変更したアドレス６０３を出力する。そのビットの並び順を変更する際、変換部２１０は、データ種別６２０に対応するビット操作を実行する。
【０１０９】
例えば、データ種別６２０が文字列データを示している場合、変換部２１０は、文字列を反転したアドレス６０３を出力する。
【０１１０】
尚、図５に示す変換部１１０においては、元のデータ（例えば、名称）に準じて属性値６０２を結合したキー情報６１１を生成し、次に、属性値６０２の並び順を入れ替えるようにした。
【０１１１】
しかし、変換部２１０は、キー情報６１１を生成することなく、所望の並び順になるように、入力された属性値６０２をビット操作し、アドレス６０３として出力するようにしてよい。尚、図１に示す変換部１１０も、このキー情報６１１を生成することのない構成と同様の構成としてよい。
【０１１２】
また、データ種別６２０が位置情報データを示している場合、変換部２１０は、属性値６０２の所定のビットを入れ替え、かつそれらの属性値６０２を結合したアドレス６０３を出力する。この場合、変換部２１０は、キー情報６１１を生成することなく、所望の並び順になるように、入力されたアドレス６０３の結合とビットのシャッフルとを同時に実行し、アドレス６０３を出力するようにしてよい。尚、図１に示す変換部１１０も、このキー情報６１１を生成することのない構成と同様の構成としてよい。
【０１１３】
また、データ種別６２０が道路情報データを示している場合、変換部２１０は、属性値６０２を所定の結合順で結合したアドレス６０３を出力する。この場合、変換部２１０は、キー情報６１１を生成することなく、所望の並び順になるように、入力された属性値６０２を結合し、アドレス６０３として出力するようにしてよい。尚、図１に示す変換部１１０も、このキー情報６１１を生成することのない構成と同様の構成としてよい。
【０１１４】
上述した本実施形態における効果は、第１の実施形態の効果に加えて、様々な種別のデータへの対応を可能にする点である。
【０１１５】
その理由は、変換部２１０がデータ種別６２０に基づいて、ビット操作を実行し、アドレス６０３を出力するようにしたからである。
【０１１６】
以上の各実施形態で説明した各構成要素は、必ずしも個々に独立した存在である必要はない。例えば、各構成要素は、複数の構成要素が１個のモジュールとして実現されてよい。また、各構成要素は、１つの構成要素が複数のモジュールで実現されてもよい。また、各構成要素は、ある構成要素が他の構成要素の一部であるような構成であってよい。また、各構成要素は、ある構成要素の一部と他の構成要素の一部とが重複するような構成であってもよい。
【０１１７】
以上説明した各実施形態における各構成要素及び各構成要素を実現するモジュールは、必要に応じ、可能であれば、コンピュータ及びプログラムで実現されてよい。また、各構成要素及び各構成要素を実現するモジュールは、ハードウェア的なモジュールとコンピュータ及びプログラムとの混在により実現されてもよいし、ハードウェアでのみ実現されてもよい。
【０１１８】
そのプログラムは、例えば、磁気ディスクや半導体メモリなど、不揮発性のコンピュータ可読記録媒体に記録されて提供され、コンピュータの立ち上げ時などにコンピュータに読み取られる。この読み取られたプログラムは、そのコンピュータの動作を制御することにより、そのコンピュータを前述した各実施形態における構成要素として機能させる。
【０１１９】
更に、以上説明した各実施形態では、複数の動作は個々に相違するタイミングで実行されることに限定されない。例えば、ある動作の実行中に他の動作が発生したり、ある動作と他の動作との実行タイミングが部分的に乃至全部において重複していたりしていてもよい。
【０１２０】
更に、以上説明した各実施形態では、ある動作が他の動作の契機になるように記載しているが、その記載はある動作と他の動作との全ての関係を限定するものではない。このため、各実施形態を実施するときには、その複数の動作の関係は内容的に支障のない範囲で変更することができる。また各構成要素の各動作の具体的な記載は、各構成要素の各動作を限定するものではない。このため、各構成要素の具体的な各動作は、各実施形態を実施する上で機能的、性能的、その他の特性に対して支障をきたさない範囲内で変更されて良い。
【０１２１】
以上、各実施形態及び実施例を参照して本発明を説明したが、本発明は上記実施形態及び実施例に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解しえる様々な変更をすることができる。
【符号の説明】
【０１２２】
１００    アドレス生成装置
１０１    情報処理装置
１１０    変換部
１１１    参照キー生成部
１１２    アドレス変換部
１３０    入力部
２００    アドレス生成装置
２１０    変換部
４００    データ記憶部
４１０    キャッシュ記憶部
４２０    ＤＲＡＭ
６０１    データ
６０２    属性値
６０３    アドレス
６０４    ライト制御信号
６０５    ライトデータ
６０６    リードデータ
６１１    キー情報
６２０    データ種別
６９１    キー情報
６９２    属性値
６９３    リードデータ
６９４    アドレス
８２１    区画群
８２２    区画群
８２３    区画群
９０１    情報処理装置
９０２    情報処理装置
９１１    参照キー生成部
９１２    ハッシュアドレス生成部
９４１    連想メモリ
９４２    データ記憶部
ｄ    方向ｄ
ｌ    レーンＬ
ｓ    セグメントｓ
【図１】
2014229105.tif 000003
【図２】
2014229105.tif 000004
【図３】
2014229105.tif 000005
【図４】
2014229105.tif 000006
【図５】
2014229105.tif 000007
【図６】
2014229105.tif 000008
【図７】
2014229105.tif 000009
【図８】
2014229105.tif 000010
【図９】
2014229105.tif 000011
【図１０】
2014229105.tif 000012
【図１１】
2014229105.tif 000013
【図１２】
2014229105.tif 000014
【図１３】
2014229105.tif 000015
【図１４】
2014229105.tif 000016
【図１５】
2014229105.tif 000017