(57)【要約】【課題】位置依存情報の高速検索を考慮してデータベースに格納する格納方法及び当該格納方法に対応した高速な検索方法を提供する。【解決手段】大きく分けてデータ登録／削除モジュール、データ検索モジュール、データ管理モジュールという３つの機能モジュールから構成される。データ登録／削除モジュールは、データ登録手段１０１、データ削除手段１０２、データ登録／削除の結果のデータ数をカウントするブロック別データ数カウンター１０３から構成され、データ検索モジュールは、検索キー入力手段１０４、存在密度参照手段１０５、メッシュ決定手段１０６、データ抽出手段１０７、距離比較を行い検索結果を決定する検索結果決定手段１０８という構成である。データ管理モジュールは、位置依存情報データベース１０９、データの密度を監視記録するデータ密度管理手段１１０、地理的エリアを区画する仮想メッシュ生成手段１１１という構成である。【選択図】        図１
2004178191.tif 000002
【特許請求の範囲】
【請求項１】
所定の地理的範囲にある地理的位置と関連づけられた情報（以下、位置依存情報という）から位置情報を検索キーとして距離の近い順にｋ件分のデータを検索結果として抽出する検索方法において、
前記位置依存情報の存在密度を検知する存在密度管理手段を備え、該存在密度管理手段に検知された前記存在密度を参照して決まるサイズの区画（以下、メッシュという）によって前記地理的範囲を分割して各メッシュにメッシュＩＤを設定し、前記地理的位置が属するメッシュのメッシュＩＤを前記位置依存情報に付与してデータベースに格納しておき、
１）  検索キーとして位置情報を入力するステップ、
２）  前記検索キーが属するメッシュを検索するステップ、
３）  前記検索キーが属するメッシュのメッシュＩＤを参照して、該メッシュに属する第１次候補データとしての位置依存情報群もしくはデータＩＤ群を呼び出すステップ、
４）  前記第１次候補データの数がｋに達しない場合、前記検索キーが属するメッシュの外周に接するメッシュ（以下、外周メッシュという）群のメッシュＩＤを参照して前記外周メッシュに属する第２次候補データとしての位置依存情報群もしくはデータＩＤ群を呼び出すステップ、
５）  前記第１次候補データと前記第２次候補データとを合わせた数がｋに達しない場合、外周の外周に接するメッシュに属するメッシュのメッシュＩＤを参照して、該メッシュに属する第３次候補データとしての位置依存情報群もしくはデータＩＤ群を呼び出すステップ、
６）  以下、候補データの数がｋに達するまでさらに外周のメッシュに属する位置依存情報群もしくはデータＩＤ群を呼び出すステップを繰り返すステップ、
というステップで前記ｋ件分の検索結果を抽出することを特徴とする位置依存情報の検索方法。
【請求項２】
所定の地理的範囲にある地理的位置と関連づけられた情報（以下、位置依存情報という）から位置情報を検索キーとして距離の近い順にｋ件分のデータを検索結果として抽出する検索方法において、
前記地理的範囲を予め設定したメッシュサイズの異なる複数のレベルで分割し、前記地理的位置に対して該複数レベル毎に決まるメッシュＩＤを前記位置依存情報に付与してデータベースに格納しておき、
１）  検索キーとして位置情報を入力するステップ、
２）  検索に利用するメッシュのレベルを前記検索キーが属するメッシュもしくは複数のメッシュからなる広域ブロックにおける前記位置依存情報の存在密度に応じて決めるステップ、
３）  ステップ２）で決まったレベルで前記検索キーが属するメッシュを検索するステップ、
４）  前記検索キーが属するメッシュのメッシュＩＤを参照して、該メッシュに属する第１次候補データとしての位置依存情報群もしくはデータＩＤ群を呼び出すステップ、
５）  前記第１次候補データの数がｋに達しない場合、前記検索キーが属するメッシュの外周に接するメッシュ（以下、外周メッシュという）群のメッシュＩＤを参照して前記外周メッシュに属する第２次候補データとしての位置依存情報群もしくはデータＩＤ群を呼び出すステップ、
６）  前記第１次候補データと前記第２次候補データとを合わせた数がｋに達しない場合、外周の外周に接するメッシュに属するメッシュのメッシュＩＤを参照して、該メッシュに属する第３次候補データとしての位置依存情報群もしくはデータＩＤ群を呼び出すステップ、
７）  以下、候補データの数がｋに達するまでさらに外周のメッシュに属する位置依存情報群もしくはデータＩＤ群を呼び出すステップを繰り返すステップ、
というステップで前記ｋ件分の検索結果を抽出することを特徴とする位置依存情報の検索方法。
【請求項３】
予め設定された各レベルの前記メッシュのサイズは、前記地理的範囲における前記位置依存情報の存在密度に応じて、その大きさが決められることを特徴とする特許請求範囲第２項に記載の位置依存情報の検索方法。
【請求項４】
前記地理的範囲の分割をメッシュサイズの異なる複数のレベルで行い、該レベル毎に決まる複数のメッシュＩＤを前記位置依存情報に付与して前記データベースに格納し、前記検索に利用するメッシュのレベルは前記検索キーが属するメッシュ（レベルは予め設定する）もしくは複数のメッシュからなる広域ブロックにおける前記位置依存情報の存在密度に応じて決められるレベルであることを特徴とする特許請求範囲第１項に記載の位置依存情報の検索方法。
【請求項５】
前記位置依存情報の存在密度を検知する存在密度管理手段を備え、該存在密度管理手段に検知された前記存在密度を参照して決まるサイズの区画（以下、メッシュという）によって前記地理的範囲を分割して各メッシュにメッシュＩＤを設定し、前記地理的位置が属するメッシュのメッシュＩＤを前記位置依存情報に付与してデータベースに格納することを特徴とする特許請求範囲第２項に記載の位置依存情報の検索方法。
【請求項６】
前記存在密度管理手段は、前記データベースに追加する位置依存情報が与えられたり、前記データベースから位置依存情報が削除されたりした場合、前記存在密度を計算し記録し、該存在密度管理手段に記録された存在密度を参照して前記レベルが決定されることを特徴とする特許請求範囲第１項もしくは第５項に記載の位置依存情報の検索方法。
【請求項７】
前記データベースには前記複数レベルのメッシュＩＤを格納する複数のデータ項目が設けられており、前記位置依存情報に付与されたレベル毎の複数メッシュＩＤがそれぞれのデータ項目に格納されていることを特徴とする特許請求範囲第２項、第３項、第４項、第５項もしくは第６項に記載の位置依存情報の検索方法。
【請求項８】
前記メッシュＩＤをインデックスとして、該当するメッシュに属する位置依存情報群もしくはデータＩＤ群をまとめて管理することを特徴とする特許請求範囲第１項乃至第７項に記載の位置依存情報の検索方法。
【請求項９】
前記検索によって呼び出された候補データ（複数）がｋを超えていたり、前記検索結果のデータに対する近さ順を決める場合、さらに前記候補データに対して前記検索キーとの距離を計算し、計算された距離の比較によって候補データの近さの順位を決定することを特徴とする特許請求範囲第１項乃至第８項に記載の位置依存情報の検索方法。
【発明の詳細な説明】
【０００１】
【発明が属する技術分野】
本発明は、類似検索もしくは近傍検索の方法に関し、特に地理的範囲の位置に関係づけられた情報依存情報を検索キーとして入力された位置情報の示す位置から近い順に所定数ｋ件分の位置依存情報を検索する方法に関する。
【０００２】
【従来の技術】
近年ＧＰＳシステムを利用可能な携帯端末が数多く一般に発売され、測位によって得られた携帯端末の端末位置に基づいて、その位置に関連する情報を配信するサービスに対する需要が増えてきている。
【０００３】
ユーザがいる現在位置を検索キーとして、その近辺の情報を検索する方法としては、検索キーとしての位置に対しての情報の属する位置との距離をデータベースに格納された情報すべてについて計算することにより、それぞれ比較して距離の近い順にｋ件求める直接的方法がある。
【０００４】
しかしながら、このような単純な方法では、データベースに格納するデータ量が増えると加速度的に比較回数が増えることにより、その検索性能は大きく低下する。そのためデータベース内のデータ空間を分割してツリー状の構造を持つ索引を用いて高速化を図る検索方法が提案されている。
【０００５】
【発明が解決しようとする課題】
今後、ＧＰＳシステムを利用可能な携帯端末など測位機能を備えた端末が普及することが予想され、不特定多数のユーザが自身の端末を使って位置依存情報を登録したり、削除したりするというような状況が予測される。
【０００６】
そのとき従来の検索方法では、データ分布随時変化する場合データ空間を分割したツリーの平衡状態を維持するのが困難であり、使い勝手が改善されない問題が有る。
【０００７】
本発明の目的は上記従来例の問題点を改善し、データ更新のため随時変化するデータ分布に対応してデータ空間を分割したツリーの平衡状態を維持し、検索の高速性を確保する事である。
【０００８】
【課題を解決するための手段】
本願請求項１に係わる発明においては、所定の地理的範囲にある地理的位置と関連づけられた情報（以下、位置依存情報という）から位置情報を検索キーとして距離の近い順にｋ件分のデータを検索結果として抽出する検索方法において（ここでｋは、検索装置で予め設定した数、利用者が単に指定した数、データベースに格納されたデータ数によって決まる数などの所定数である）、
前記位置依存情報の存在密度を検知する存在密度管理手段を備え、該存在密度管理手段に検知された前記存在密度を参照して決まるサイズの区画（以下、メッシュという）によって前記地理的範囲を分割して各メッシュにメッシュＩＤを設定し、前記地理的位置が属するメッシュのメッシュＩＤを前記位置依存情報に付与してデータベースに格納しておき、
１）            検索キーとして位置情報を入力するステップ、
２）            前記検索キーが属するメッシュを検索するステップ、
３）            前記検索キーが属するメッシュのメッシュＩＤを参照して、該メッシュに属する第１次候補データとしての位置依存情報群もしくはデータＩＤ群を呼び出すステップ、
４）            前記第１次候補データの数がｋに達しない場合、前記検索キーが属するメッシュの外周に接するメッシュ（以下、外周メッシュという）群のメッシュＩＤを参照して前記外周メッシュに属する第２次候補データとしての位置依存情報群もしくはデータＩＤ群を呼び出すステップ、
５）            前記第１次候補データと前記第２次候補データとを合わせた数がｋに達しない場合、外周の外周に接するメッシュに属するメッシュのメッシュＩＤを参照して、該メッシュに属する第３次候補データとしての位置依存情報群もしくはデータＩＤ群を呼び出すステップ、
６）            以下、候補データの数がｋに達するまでさらに外周のメッシュに属する位置依存情報群もしくはデータＩＤ群を呼び出すステップを繰り返すステップ、
というステップで前記ｋ件分の検索結果を抽出する方法を採用した。
【０００９】
本願請求項２に係わる発明の位置依存情報の検索方法は、所定の地理的範囲にある地理的位置と関連づけられた情報（以下、位置依存情報という）から位置情報を検索キーとして距離の近い順にｋ件分のデータを検索結果として抽出する検索方法において、
前記地理的範囲を予め設定したメッシュサイズの異なる複数のレベルで分割し、前記地理的位置に対して該複数レベル毎に決まるメッシュＩＤを前記位置依存情報に付与してデータベースに格納しておき、
１）  検索キーとして位置情報を入力するステップ、
２）  検索に利用するメッシュのレベルを前記検索キーが属するメッシュもしくは複数のメッシュからなる広域ブロックにおける前記位置依存情報の存在密度に応じて決めるステップ、
３）  ステップ２）で決まったレベルで前記検索キーが属するメッシュを検索するステップ、
４）  前記検索キーが属するメッシュのメッシュＩＤを参照して、該メッシュに属する第１次候補データとしての位置依存情報群もしくはデータＩＤ群を呼び出すステップ、
５）  前記第１次候補データの数がｋに達しない場合、前記検索キーが属するメッシュの外周に接するメッシュ（以下、外周メッシュという）群のメッシュＩＤを参照して前記外周メッシュに属する第２次候補データとしての位置依存情報群もしくはデータＩＤ群を呼び出すステップ、
６）  前記第１次候補データと前記第２次候補データとを合わせた数がｋに達しない場合、外周の外周に接するメッシュに属するメッシュのメッシュＩＤを参照して、該メッシュに属する第３次候補データとしての位置依存情報群もしくはデータＩＤ群を呼び出すステップ、
７）  以下、候補データの数がｋに達するまでさらに外周のメッシュに属する位置依存情報群もしくはデータＩＤ群を呼び出すステップを繰り返すステップ、
というステップで前記ｋ件分の検索結果を抽出する方法を採用した。
【００１０】
本願請求項３に係わる発明の位置依存情報の検索方法は、本願請求項２に係わる発明において、データ検索に利用されるメッシュの大きさが前記地理的範囲における前記位置依存情報の存在密度に応じて、その大きさが決められることを特徴とする。
【００１１】
本願請求項４に係わる発明の位置依存情報の検索方法は、本願請求項１に係わる発明において、前記地理的範囲の分割をメッシュサイズの異なる複数のレベルで行い、該レベル毎に決まる複数のメッシュＩＤを前記位置依存情報に付与して前記データベースに格納し、前記検索に利用するメッシュのレベルは前記検索キーが属するメッシュ（レベルは予め設定する）もしくは複数のメッシュからなる広域ブロックにおける前記位置依存情報の存在密度に応じて決められるレベルであることを特徴とする。
【００１２】
本願請求項５に係わる発明の位置依存情報の検索方法は、請求項２に記載の位置依存情報の検索方法において、前記位置依存情報の存在密度を検知する存在密度管理手段を備え、該存在密度管理手段に検知された前記存在密度を参照して決まるサイズの区画（以下、メッシュという）によって前記地理的範囲を分割して各メッシュにメッシュＩＤを設定し、前記地理的位置が属するメッシュのメッシュＩＤを前記位置依存情報に付与してデータベースに格納することを特徴とする。
【００１３】
本願請求項６に係わる発明の位置依存情報の検索方法は、第１項もしくは第５項に記載の位置依存情報の検索方法において、前記存在密度管理手段は、前記データベースに追加する位置依存情報が与えられたり、前記データベースから位置依存情報が削除されたりした場合、前記存在密度を計算し記録し、該存在密度管理手段に記録された存在密度を参照して前記レベルが決定されることを特徴とする。
【００１４】
本願請求項７に係わる発明の位置依存情報の検索方法は、第２項、第３項、第４項、第５項もしくは第６項に記載の位置依存情報の検索方法において、前記データベースには前記複数レベルのメッシュＩＤを格納する複数のデータ項目が設けられており、前記位置依存情報に付与されたレベル毎の複数メッシュＩＤがそれぞれのデータ項目に格納されていることを特徴とする。
【００１５】
本願請求項８に係わる発明の位置依存情報の検索方法は、請求項１乃至請求項５に記載の位置依存情報の検索方法において、前記メッシュＩＤをインデックスとして、該当するメッシュに属する位置依存情報群もしくはデータＩＤ群をまとめて管理することを特徴とする。
【００１６】
本願請求項９に係わる発明の位置依存情報の検索方法は、請求項１乃至請求項８に記載の位置依存情報の検索方法において、前記検索によって呼び出された候補データ（複数）がｋを超えていたり、前記検索結果のデータに対する近さ順を決める場合、さらに前記候補データに対して前記検索キーとの距離を計算し、計算された距離の比較によって候補データの近さの順位を決定することを特徴とする。
【００１７】
【発明の実施の形態】
【全体構成】
図１は、本発明による位置依存情報の検索方法を実現するシステム構成の一例を示したブロック図である。大きく分けてデータ登録／削除モジュール、データ検索モジュール、データ管理モジュールという３つの機能モジュールから構成される。
【００１８】
データ登録／削除モジュールは、位置依存情報データベース１０８に新たに位置依存情報をアップロードするためのデータ登録手段１０１、登録されている位置依存情報を削除するためのデータ削除手段１０２、データ登録／削除の結果のデータ数をカウントするブロック別データ数カウンター１０３から構成され、データ管理モジュールに対して位置依存情報の登録／削除とそれに伴うデータ数の増減を予め設定した地域（ブロック）毎にカウントを行う。
【００１９】
データ検索モジュールは、検索キーとしての位置情報を入力する検索キー入力手段１０４、検索キーの属するブロックにおけるデータ存在密度を参照する存在密度参照手段１０５、検索に利用するメッシュのレベルを決定するメッシュ決定手段１０６、メッシュ内の存在するデータを抽出するデータ抽出手段１０７、抽出した候補データの距離比較を行い検索結果を決定する検索結果決定手段１０８という構成である。
【００２０】
データ管理モジュールは、位置依存情報データベース１０９、データが存在する地理的範囲や予め設定した地域的ブロックに存在するデータの密度を監視記録するデータ密度管理手段１１０、監視記録されたデータ密度を参照して地理的エリアを区画する仮想メッシュ生成手段１１１という構成である。ここで生成する仮想メッシュは、後で詳しく説明するような予め段階的に設定したメッシュでもよいし、監視記録されたデータ密度から所定の演算で決定される大きさのメッシュでもよい。
【００２１】
図２はデータベースに新しくデータを追加するときのフローチャートである。データ入力ステップ２０１において、位置存生情報が入力されると、次に該当メッシュ検索ステップ２０２において、位置依存情報が関連づけられている位置の位置情報を参照して、その位置が属するメッシュを検索する。データ格納ステップ２０３において、検索されたメッシュのメッシュＩＤを該当データ項目に付与して位置依存情報データベース１０９に格納する。データ数カウントステップ２０４において、データが属するブロックのデータ数に１加算される。データ密度計算ステップ２０５において、所定のタイミングでカウント数をデータ密度管理手１１０に通知し、データ存在密度を計算する。
【００２２】
図３はデータベースからデータを削除するときのフローチャートである。削除データ指定ステップ３０１において、データ管理者が削除したいデータの指定が行われる。指定データ削除ステップ３０２において、位置存生法データベース１０９から該当する位置存生情報が削除されると、次にデータ数減算ステップ３０３において、該当する位置依存情報が関連づけられている位置が属するブロックのデータ数に１減算する。データ密度計算ステップ３０４において、所定のタイミングでカウント数をデータ密度管理手１１０に通知し、データ存在密度を計算する。ここでステップ３０４や図２のステップ２０５における通知し存在密度を再計算するタイミングは、データを追加、削除する毎でもよいし、毎日の一定の時間帯を設定して行ってもよい。データベースの更新頻度を考慮して適切に定めればよい。
【００２３】
図４は位置依存情報データベース１０９に格納された位置依存情報と付与されたメッシュＩＤを示したマトリクスである。ここではレベル１からレベル６まで６つのレベルの区画が採用されている。
【００２４】
図５は、各レベルのメッシュの大きさを表している。例えばレベル１は、タテ１．６ｋｍ  ヨコ１．６ｋｍのメッシュであることを示している。図６は各レベルのメッシュ同士の関係を示した概念図である。レベル１の１区画が４分割されてレベル２のタテヨコ８００ｍのメッシュとなり、そのレベル２の１区画がさらに４分割されてレベル３に４００ｍのメッシュとなる。図示していないが、このような分割が繰り返されて、最終的にレベル６のタテヨコ５０ｍのメッシュが仮想的に生成される。
【００２５】
図７は、本実施例の検索の大まかなフローチャートである。検索キー入力ステップ７０１において検索者がＧＰＳ等で測位した位置情報などの検索キーが入力される。該当ブロックのデータ存在密度参照ステップ７０２において、データ密度管理手段１１０に記録された検索キーの属するブロックのデータ密度が参照される。
【００２６】
図８から図１１はＡブロック、Ｂブロック、Ｃブロック、Ｄブロックという４つのブロックのデータ格納部とデータ密度管理手段に記録されているデータ存在密度を示した概念図である。
【００２７】
メッシュレベル決定ステップ７０３において、参照されたデータ密度と図１２に示すようなレベル決定表を参照して、検索に用いるメッシュのレベルを決定する。図１２において、例えばデータ存在密度が１０１から１０００であるならば、レベル２が選択される。図１３は決定したメッシュレベルを○で示したマトリクスである。Ａブロックに属する検索キーの場合レベル１のメッシュが、Ｂブロックの場合レベル３、Ｃブロックの場合レベル６、Ｄブロックの場合レベル４という具合に利用されるメッシュのレベルが決定される。
【００２８】
候補データ抽出ステップ７０４において、検索キーが属するメッシュ、このメッシュの外周という具合に段階的に検索結果の候補となる候補データの抽出をデータ数が所定数ｋに達するまで行われる。このメッシュ検索のプロセスは後で詳しく説明する。
【００２９】
候補データの距離計算ステップ７０５では、候補データすべてに対して検索キーとなる位置との距離が計算される。次に候補データの順位決定ステップ７０６において、候補データと検索キーとの近さの順位が比較決定される。検索結果出力ステップ７０７において、決定した順位に基づいて上位ｋ件分のデータが検索結果として出力される。
【００３０】
図１４、図１５は、メッシュを使った候補データ抽出のプロセスを詳細に示したフローチャートである。検索キーが属するメッシュ検索ステップ１４０１において、入力された検索キーとしての位置情報が参照され、その位置が属するメッシュを検索する。次にメッシュに属するデータ抽出ステップ１４０２において、検索されたメッシュのメッシュＩＤに属するデータの抽出が行われる。ここでは検索対象となるメッシュのメッシュＩＤをキーとして、位置依存情報データベースに格納されたデータの該当するデータ項目を参照して合致するメッシュＩＤを持つデータを候補データとして抽出する。
【００３１】
ここでは、該当するレベルのメッシュＩＤを格納したデータ項目を全データについて参照する方式を採用したが、本発明の実施の方法はこれに限られるものではない。例えばメッシュＩＤをインデックスとして、メッシュＩＤ毎にそのメッシュに属するデータのデータＩＤをインデクス管理し、インデクスを参照して候補データを抽出する方式であれば、全データを参照する必要がないため、より高速なデータ抽出が可能になる。図１６は、メッシュＩＤ毎に管理されたデータＩＤを示した概念図である。メッシュＩＤがＤ６であるメッシュには、データ００１、００８、００９が、Ｄ７には００２、００６のデータが管理されている。ここで検索キーがメッシュＤ６に属していれば、００１、００８、００９が候補データとして１ステップで抽出可能になる。
【００３２】
さて、ステップ１４０４では、候補データのデータ抽出数が所定の数ｋに達しているかの判定が行われる。ここでｋ件分に達する候補データがあれば、候補データ確定ステップ１４０５に進み、メッシュ検索が終了する。
【００３３】
ｋに抽出数が達していない場合、図１５に示したＢのフローを実行する。すなわち、該当メッシュの外周メッシュを検索ステップ１５０１において、検索キーが属するメッシュの外周に接する外周メッシュを検索する。次に外周メッシュに属するデータを抽出ステップ１５０２において、検索された外周メッシュのメッシュＩＤに属するデータの抽出が行われる。ここでは検索対象となるメッシュのメッシュＩＤをキーとして、位置依存情報データベースに格納されたデータの該当するデータ項目を参照して合致するメッシュＩＤを持つデータを候補データとして抽出する。
【００３４】
該当するレベルのメッシュＩＤを格納したデータ項目を全データについて参照する方式を採用したが、本発明の実施の方法はこれに限られるものではない。例えばメッシュＩＤをインデックスとして、メッシュＩＤ毎にそのメッシュに属するデータのデータＩＤをインデクス管理し、インデクスを参照して候補データを抽出する方式でもよい。
【００３５】
さて、ステップ１５０３では、候補データのデータ抽出数が所定の数ｋに達しているかの判定が行われる。ここでｋ件分に達する候補データがあれば、候補データ確定ステップ１５０４に進み、メッシュ検索が終了する。
【００３６】
ｋに抽出数が達していない場合、ステップ１５０１に戻って、さらに外側の外周メッシュの検索を実行する。
【００３７】
図１７は、Ａ１、Ａ２・・・・・、Ｂ１、Ｂ２・・・・、Ｃ１、・・・、Ｄ１、・・・という具合に区画されたメッシュを示した概念図である。ここで検索キーがＤ６に属する場合の上記図１４、図１５で示したフローで候補データを抽出するために参照するメッシュの検索順番の一例を示したのが、図１８である。図１８では時計回りに中心から外側へメッシュを辿っているが、本発明はこれに限られるものではなく、反時計回りでも所定のアルゴリズムで決まる順番でもよい。
【００３８】
【発明の効果】
本発明による位置依存情報の検索方法を利用することにより、随時変化するデータ分布に対応してツリー（メッシュ）の大きさを選択し、検索対象となるメッシュの平衡状態を維持する効果がある。
【図面の簡単な説明】
【図１】位置依存情報の検索方法を実現するシステム構成
【図２】データを追加するときのフローチャート
【図３】データを削除するときのフローチャート
【図４】位置依存情報と付与されたメッシュＩＤを示したマトリクス
【図５】各レベルのメッシュの大きさ
【図６】各レベルのメッシュ同士の関係を示した概念図
【図７】検索の大まかなフローチャート
【図８】Ａブロックのデータ格納部とデータ存在密度を示した概念図
【図９】Ｂブロックのデータ格納部とデータ存在密度を示した概念図
【図１０】Ｃブロックのデータ格納部とデータ存在密度を示した概念図
【図１１】Ｄブロックのデータ格納部とデータ存在密度を示した概念図
【図１２】レベル決定表
【図１３】決定したメッシュレベルを示したマトリクス
【図１４】メッシュを使った候補データ抽出のプロセスを詳細に示したフローチャート
【図１５】メッシュを使った候補データ抽出のプロセスを詳細に示したフローチャート
【図１６】メッシュＩＤ毎に管理されたデータＩＤを示した概念図
【図１７】区画されたメッシュを示した概念図
【図１８】参照するメッシュの検索順番の一例
【符号の説明】
１０１    データ登録手段
１０３    ブロック別データ数カウンター
１０５    存在密度参照手段
１０６    メッシュ決定手段
１０７    データ抽出手段
【図１】
2004178191.tif 000003
【図２】
2004178191.tif 000004
【図３】
2004178191.tif 000005
【図４】
2004178191.tif 000006
【図５】
2004178191.tif 000007
【図６】
2004178191.tif 000008
【図７】
2004178191.tif 000009
【図８】
2004178191.tif 000010
【図９】
2004178191.tif 000011
【図１０】
2004178191.tif 000012
【図１１】
2004178191.tif 000013
【図１２】
2004178191.tif 000014
【図１３】
2004178191.tif 000015
【図１４】
2004178191.tif 000016
【図１５】
2004178191.tif 000017
【図１６】
2004178191.tif 000018
【図１７】
2004178191.tif 000019
【図１８】
2004178191.tif 000020