(57)【要約】      （修正有）【課題】位置情報を付与された文書を中心から求められた距離の範囲で検索する際、距離の閾値を適切に設定する。【解決手段】距離閾値指定装置のセル定義部１０１は、文書ＤＢ１０４の文書について、位置情報に基づいてセルを配置するためのセル定義を行って、配置基準を文書分配式格納ＤＢ１０５に保存する。範囲設定部１０２は、各文書を付与された位置情報に基づき配置基準にしたがってセルに分配し、各セルについて距離閾値を算出し、距離閾値インデックスＤＢ１０６に保存する。検索部１０３は、ユーザから入力された位置情報を質問式として、該位置情報の属するセルについてのインデクスＤＢ１０６から距離閾値を読み出し、読み出した距離閾値内に属する文書を、文書ＤＢ１０４から検索する。【選択図】図２
2015219614.tif 000002
【特許請求の範囲】
【請求項１】
位置情報を付与された文書を中心から求められる距離の範囲で検索するにあたって距離の閾値を設定する装置であって、
文書に付与された位置情報に基づいてセルに配置するためのセルの定義を行って配置基準を保存するセル定義部と、
各文書を付与された位置情報に基づき前記配置基準にしたがってセルに分配し、各セルについて距離閾値を算出してインデクスとして保存する範囲設定部と、
を備えることを特徴とする距離閾値指定装置。
【請求項２】
ユーザ入力の位置情報を質問式として受け付け、受け付けた位置情報の属するセルについての前記インデクスから距離閾値を読み出し、読み出した距離閾値内に属する文書をデータベースから検索してユーザに提示する検索部を、
さらに備えることを特徴とする請求項１記載の距離閾値指定装置。
【請求項３】
範囲設定部は、分配されたセルごとに文書数を求める手段と、
各セルについて目標とする文書数に達するまで隣接セルに含まれる文書数を加算し、目標に達した隣接数を距離閾値としてインデクスに格納する手段と、
を備えることを特徴とする請求項１または２のいずれか１項に記載の距離閾値指定装置。
【請求項４】
位置情報を付与された文書を中心から求められる距離の範囲で検索するにあたってコンピュータで距離の閾値を設定する方法であって、
文書に付与された位置情報に基づいてセルに配置するためのセルの定義を行って配置基準を保存するセル定義ステップと、
各文書を付与された位置情報に基づき前記配置基準にしたがってセルに分配し、各セルについて距離閾値を算出してインデクスとして保存する範囲設定ステップと、
を有することを特徴とする距離閾値指定方法。
【請求項５】
ユーザ入力の位置情報を質問式として受け付け、受け付けた位置情報の属するセルについての前記インデクスから距離閾値を読み出し、読み出した距離閾値内に属する文書をデータベースから検索してユーザに提示する検索ステップを、
さらに有することを特徴とする請求項４記載の距離閾値指定方法。
【請求項６】
範囲設定ステップは、分配されたセルごとに文書数を求めるステップと、
各セルについて目標とする文書数に達するまで隣接セルに含まれる文書数を加算し、目標に達した隣接数を距離閾値としてインデクスに格納するステップと、
を有することを特徴とする請求項４または５のいずれか１項に記載の距離閾値指定方法。
【請求項７】
請求項１〜３のいずれか１項に記載の距離閾値指定装置としてコンピュータを機能させる距離閾値指定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、位置情報が付与された電子文書（以下、文書とする。）群を検索する情報検索の技術に関する。
【背景技術】
【０００２】
従来、文書に地理上の位置が緯度と経度の組で与えられた文書データベースに対する検索システムが提案されている。ここで「文書」とは、実世界での事象を表現した情報であり、各事象は、永続的に存在する場合と、ある有限時間内に発生する場合がある。
【０００３】
この文書データベースに対し、地理上の位置を緯度と経度として入力すると、その位置を中心としてある距離以内にある文書を検索する地域情報検索システムを考える。ここでは地理上の事象は、地域によって密度には濃淡が認められる。
【０００４】
例えば地域で開催されるイベントを記述した文書集合があったとき、各文書には、データベース中ではそれぞれのイベントの発生位置が付与され、位置に基づいた検索が可能となる。こうしたとき、人口密度に応じて、多くのイベントが発生する地域と、あまりイベントが発生しない地域が存在することは容易に想像できる。
【０００５】
図１に基づきある地域において文書に与えられた位置情報の分布を説明する。ここで地点Ａの付近では、多くの文書が配置されているが、地点Ｂの付近では配置された文書は少ない。このとき地点Ａと地点Ｂで、中心から同じ距離の範囲で文書を検索すると、地点Ａでは多くの文書が検索され、地点Ｂでは十分な数の文書が検索されないことになる。
【０００６】
この問題の自明な解決方法としては、検索される位置の入力が行われたとき、データベース内の全ての文書について、入力された位置と割り当てられた位置との距離を計算し、その距離の昇順に文書をソートし、十分な数の文書が得られるまで上位から順に提供する方法が考えらえる。
【０００７】
しかしながら、この方法には計算量上の問題点が残る。すなわち、Ｎ個の文書が含まれたデータベース上の全ての位置との計算をするためには「Ｏ（Ｎ）］、得られた検索位置との距離に応じてソートするには、最良のアルゴリズムを利用しても「Ｏ（Ｎ  ｌｏｇ  Ｎ）」の計算量がかかる。
【０００８】
そこで、特許文献１は、地名を与えて検索する際、その地名が含意する範囲の広さを利用することで検索範囲を定める方法を提案している。特許文献２は範囲を指定して、その範囲内の文書を指す手法を提案している。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００９−１３４４６３
【特許文献２】特開２０１２−８９０１９
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、特許文献１の方法は、検索する際に地名の付近にどれだけ多くの文書が割り当てられるかは未知なため、実効性に乏しいおそれがある。
【００１１】
また、特許文献２の方法も、位置に割り当てられた文書の密度に応じて検索される文書数は左右され、どの場所においても十分な文書数を検索するための閾値を求めることができないおそれがある。
【００１２】
本発明は、このような問題を解決するためになされ、位置情報を付与された文書を中心から決められた距離の範囲で検索するにあたって距離の閾値を適切に設定することを解決課題としている。
【課題を解決するための手段】
【００１３】
そこで、本発明は、地名をセル（メッシュなど）に区切って各セルの文書数を求める。このとき密度の濃いセルは１つに限定する一方、密度が低いセルは隣接セルまででなどと検索範囲を事前に設定しておく。実際の検索にあたっては検索範囲に応じて文書を出力する。
【００１４】
本発明の距離閾値指定装置は、文書に付与された位置情報に基づいてセルに配置するためのセルの定義を行って配置基準を保存するセル定義部と、各文書を付与された位置情報に基づき前記配置基準にしたがってセルに分配し、各セルについて距離閾値を算出してインデクスとして保存する範囲設定部と、を備えることを特徴としている。
【００１５】
本発明の距離閾値指定方法は、文書に付与された位置情報に基づいてセルに配置するためのセルの定義を行って配置基準を保存するセル定義ステップと、各文書を付与された位置情報に基づき前記配置基準にしたがってセルに分配し、各セルについて距離閾値を算出してインデクスとして保存する範囲設定ステップと、を有することを特徴としている。
【００１６】
なお、本発明は、前記装置としてコンピュータを機能させるプログラムの態様としてもよい。このプログラムは、ネットワークや記録媒体などを通じて提供することができる。
【発明の効果】
【００１７】
本発明によれば、位置情報を付与された文書を中心から決められた距離の範囲で検索するにあたって距離の閾値を適切に設定することができる。
【図面の簡単な説明】
【００１８】
【図１】位置情報の分布図。
【図２】本発明の実施形態に係る距離閾値指定装置の構成図。
【図３】同  セル定義部の処理フロー図。
【図４】矩形セルの一例を示す図。
【図５】六角形セルの一例を示す図。
【図６】六角形セルの文書分配式の説明図。
【図７】範囲設定部の処理フロー図。
【図８】矩形セルの距離閾値計算アルゴリズムを示す説明図。
【図９】六角形セルの距離閾値計算アルゴリズムを示す説明図。
【図１０】検索部の処理フロー図。
【図１１】矩形セルの文書群選択アルゴリズムを示す説明図。
【図１２】六角形セルの文書群選択アルゴリズムを示す説明図。
【図１３】六角形のセル定義を示す図。
【図１４】領域の矩形分割例を示す図。
【図１５】文書の分布例を示す図。
【図１６】文書の分布例（数値化）を示す図。
【図１７】距離閾値の説明図（地点Ａ）。
【図１８】距離閾値の説明図（地点Ｂ）。
【図１９】全セルの距離閾値例を示す図。
【図２０】六角形の場合の隣接セル図。
【図２１】検索実行例の図。
【発明を実施するための形態】
【００１９】
以下、本発明の実施形態に係る距離閾値指定装置を説明する。この距離閾値指定装置は、データベース内で位置情報を付与された文書を、中心から決められた距離の範囲で検索する検索システムに利用され、地理上の地点が入力されればその地点を中心に距離的に近い所定枚数の文書を抽出する。
【００２０】
≪構成例≫
図２に基づき前記距離閾値指定装置の構成例を説明する。ここでは前記距離閾値指定装置１００はコンピュータにより構成され、ＣＰＵ，主記憶装置（ＲＡＭ，ＲＯＭ等），補助記憶装置（ハードディスクドライブ装置，「Ｆｌａｓｈ  ＳＳＤ」等）などのハードウェアリソースを備える。
【００２１】
このハードウェアリソースとソフトウェアリソースとの協働の結果、前記距離閾値指定装置１００は、セル定義部１０１，範囲設定部１０２，検索部１０３，文書ＤＢ１０４，文書分配式格納ＤＢ１０５，距離閾値インデクスＤＢ１０６を有している。
【００２２】
この各ＤＢ１０４〜１０６は、それぞれ前記記憶装置に構築されているものとする。具体的には文書ＤＢ１０４は文書に関する情報として位置情報および所属するセルのＩＤを保持し、文書分配式ＤＢ１０５は文書をセルに分配するための文書分配式を保持し、距離閾値インデクスＤＢ１０６は各セルについての距離閾値を保持する。
【００２３】
セル定義部１０１は、文書に付与された位置情報に基づいてセルに配置するためのセルの定義を行い、文書の配置基準となる文書分配式を文書分配式格納ＤＢ１０５に格納する。
【００２４】
範囲設定部１０２は、文書ＤＢ１０４に格納された各文書を、各文書の位置情報に基づき文書分配式格納ＤＢ１０５の文書分配式に従ってセルに分配する。その後に各セルについて距離閾値を計算して距離閾値インデクス１０６に格納し、また相当するセルのＩＤを文書ＤＢ１０４内の当該文書のレコードに書き出す。
【００２５】
検索部１０３は、ユーザから入力された位置情報を質問式として読み出し、当該位置情報の属するセルについて、距離閾値インデクスＤＢ１０６の距離閾値インデクスから距離閾値を読み出し、読み出した閾値内に属する文書を文書ＤＢ１０４から検索し、検索結果を出力してユーザに提示する。
【００２６】
≪セル定義部１０１の処理内容≫
図３に基づきセル定義部１０１の処理内容（セル定義ステップ）を説明する。セル定義部１０１は、セル形状、セルサイズ、および対象領域が入力されると（Ｓ２０１）、セル定義（Ｓ２０２）を行った上で文書分配式を構築し（Ｓ２０３）、構築した文書分配式を文書分配式格納ＤＢ１０５へ格納する（Ｓ２０４）。
【００２７】
（１）セル形状等の入力受付（Ｓ２０１）
セル形状等の入力は、前記距離閾値指定装置１００の入力手段（キーボード，ポインティングデバイスなど）や、図示省略のユーザ端末（スマートフォン，ＰＣなど）からネットワーク経由での入力でもよく、セル定義部１０１は入力されたセル形状等を受け付ける。
【００２８】
ここでセルは、領域を定義できてＩＤを与えられるならば任意の形とすることが可能だが、簡単に取り扱うには矩形あるいは六角形で構成する。また、セルサイズは、距離閾値の拡大範囲によって定義する。例えば「１０ｋｍ以内の文書」，「２０ｋｍ以内の文書．．．」のように、１０ｋｍ単位で距離閾値を拡大する場合は、セルサイズは１０ｋｍとする。さらに領域は、文書に位置情報が与えられる範囲として定義する。任意の座標系を利用することが可能である。
【００２９】
なお、実施例の１つとしては、球面上の２本ずつの緯線と経線によって区切られた領域として与えられる。この場合、緯度および経度の上限および下限によって定義される。
【００３０】
（２）セル定義（Ｓ２０２）
図４に基づき矩形で構成された分割の例を説明する。矩形に区切る場合はメッシュと呼んでも構わない。地球の表面をセルに分割する場合は、緯度範囲，経度範囲によって各セルの領域を指定することができる。各セルは緯線方向，経線方向の番号の組み合わせからＩＤを指定できる。例えば経度方向が「ｊ」，緯度方向が「ｉ」のセルは、２つ組（ｉ，ｊ）として表現できる。
【００３１】
また、図５に示すような六角形で構成された分割例でも各セルは、緯線方向，経線方向の番号の組みあわせからＩＤを指定できる。例えば経度方向が「ｊ」，緯度方向が「ｉ」のセルは、２つ組（ｉ，ｊ）として表現できる。
【００３２】
（３）文書分配方式の構成（Ｓ２０３）
領域として緯度方向に［Ｌａｔmin，Ｌａｔmax］，経度方向に［Ｌｎｇmin，Ｌｎｇmax］が入力されたとする。また、セル形状として矩形が入力され、セルサイズとして「Ｃ」が入力されたとする。
【００３３】
ここで位置情報として経度方向に「ｙ」，緯度方向に「ｘ」（この位置を≡（ｘ，ｙ）≡と記述する。）が割り当てられた文書が与えられたとき、文書分配式は式（１）以下のように定義される。
【００３４】
【数１】
2015219614.tif 000003
【００３５】
ここで[Ｘ]は実数「ｘ」について「ｘ」以下の最大の整数を表す。また、「ＰLat」，「ＰLng」は、それぞれ緯度，経度についてセルサイズあたりの距離（球面を対象にする場合は度数）を表し、式（２）で与えられる。
【００３６】
【数２】
2015219614.tif 000004
【００３７】
また、セル形状として六角形が入力された場合、セル（ｉ，ｊ）の中心点を「ｃi,j」とすると、文書分配式は式（３）のように定義される。
【００３８】
【数３】
2015219614.tif 000005
【００３９】
ここで「ａｒｇｍｉｎCｘ」は「ｘ」を最小にするよう「ｃ」を選択する関数、「ｌｅｎｇｔｈ（ｐ，ｑ）」は２点「ｐ」，「ｑ」間の距離を表す関数とする。これは図６に示すように、与えられた点に最も近い中心点を持つセルに分配することを意味する。文書分配式はセルサイズによって変化するため、必要に応じてセルサイズに応じた文書分配式を文書分配式格納ＤＢ１０５に格納する。
【００４０】
≪範囲設定部１０２の処理内容≫
図７に基づき範囲設定部１０２の処理内容（範囲設定ステップ）を説明する。範囲設定部１０２は、検索文書概数リストを入力として読み出し（Ｓ３０１）、文書ＤＢ１０４に未処理の文書が存在するか否かを確認し（Ｓ３０２）、存在していれば文書ＤＢ１０４から文書データを読み出す。（Ｓ３０３）。
【００４１】
その後に文書分配式格納ＤＢ１０５から文書分配式を読み出して各文書をセルに割り当て（Ｓ３０４）、その結果を文書ＤＢ１０４に書き出す。そして、全ての文書の処理が完了した後で距離閾値インデクスを作成し（Ｓ３０５）、各セルに対する距離閾値を距離閾値インデクスＤＢ１０６へ格納する。
【００４２】
ここでＳ３０１の検索文書概数リストは、一度の検索で提供することを意図した文書数のリストである。一度に１０文献を提供する場合と１００文献を提供する場合があるならば、リストは（１０，１００）となる。以下、範囲設定部１０２の処理内容の中心となるセル割当（Ｓ３０４）および距離閾値インデクス作成（Ｓ３０５）を説明する。
【００４３】
（１）セル割当（Ｓ３０４）
ここでは各文書について、文書データとして位置情報を読み出し、位置情報に基づき文書分配式格納ＤＢ１０５に格納された文書分配式に従って、文書をセルに割り当て、各文書が属するセルＩＤを文書ＤＢ１０４に書き出す。
【００４４】
文書ＤＢ１０４は、各文書についてのデータを、位置情報を含めて格納しているが、ここにセルＩＤも格納可能とする。表１は、文書ＤＢ１０４の格納データの一例を示し、セル割当が未処理の文書についてはセルＩＤに空（?）が記述されている。
【００４５】
【表１】
2015219614.tif 000006
【００４６】
また、セルＩＤをキーとして文書を検索可能とするように、転置ファイルも同時に作成する。表２は転置ファイルの一例を示し、各セルについて分配された文書ＩＤが記録されている。
【００４７】
【表２】
2015219614.tif 000007
【００４８】
（２）距離閾値インデクス作成（Ｓ３０５）
距離閾値インデクス作成においては、文書ＤＢ１０４から転置ファイルを読み出して、検索文書概数リストに含まれた検索対象数毎に距離閾値を計算する。
【００４９】
距離閾値は各セルおよび検索文字概数毎に計算する。まず、当該セル内の文書数のみで検索文書数を超える場合は、距離閾値を「０」とする。当該セル内の文書数のみで検索文書概数を超えない場合、隣接するセル群の文書数の合計と当該セル内の文書数とを加算する。１つ隣接したセル群の文書の合計までで検索文書数を超える場合は距離閾値を「１」とする。
【００５０】
以下同様に１つ隣接したセル群に隣接したセル群（これを「２つ隣接したセル群」と呼ぶ。以下同じ）、さらにそれらに隣接したセル群と範囲を拡大し、当該セルから「ｍ」だけ隣接したセル群に含まれる文書数で検索文書概数を超えたときに「ｍ」を距離閾値とする。
【００５１】
距離閾値インデクスは、検索文書概数に達するまでに検索対象をどれだけの隣接セルに拡張すべきかの値、即ち距離閾値「ｍ」を格納する。例えば１つ隣接したセルまでの範囲で検索文書概数に達する場合、値として「１」が格納される。
【００５２】
より具体的にはセル形状が矩形の場合は図８のアルゴリズムで計算する。矩形の場合、「隣接したセル」には上下左右に隣接したセルおよび斜め上下左右のセルも含む。また、セル形状が六角形の場合は図９のアルゴリズムで計算する。ただし、「ａｂｓ（ｘ）」は「ｘ」の絶対値を返す関数とする。
【００５３】
【表３】
2015219614.tif 000008
【００５４】
表３は、距離閾値インデクスの一例を示している。ここではセル（０，０）では、「１０文書」を検索するために１つ隣接したセルまでを範囲に含める必要があることが示され、「２０文書」を検索するためには２つ隣接したセルまでを範囲に含める必要があることが示されている。
【００５５】
したがって、前記距離閾値指定装置１００によれば、各セルについて隣接の観点からどれだけの領域を拡大すれば必要な文書が得られるのかが距離閾値インデックスとされる。これにより検索時の距離に関する閾値を地域に応じて妥当な距離に設定することができる。その結果、データベース内で位置情報が付与された文書を中心から求められた距離の範囲で検索する検索システムにおいて、該距離の閾値を適切に設定することができる。
【００５６】
≪検索部１０３の処理内容≫
図１０に基づき検索部１０３の処理内容（検索ステップ）を説明する。検索部１０３では、まずユーザが入力した検索式を読み出す（Ｓ４０１）。ユーザの入力は、ユーザ端末からネットワーク経由での入力でもよく、また前記距離閾値指定装置１００の入力手段による入力でもよく、検索式には位置情報と文書数が含まれるものとする。
【００５７】
この位置情報に対して距離閾値を距離閾値インデクスから取得し（Ｓ４０２）、当該位置から距離閾値範囲内の文書を文書ＤＢ１０４から読み出し、検索式の位置情報以外の条件に基づいて検索を実行する（Ｓ４０３）。その結果として得られた文書リストを検索結果出力によってユーザに提供する（Ｓ４０４）。
【００５８】
このように位置情報が検索時に与えられれば、その位置情報が属するセルについて距離閾値を距離閾値インデクスＤＢ１０６から求め、その距離内に含まれる文書がユーザに検索結果として提示される。あるいは距離閾値を前記ＤＢ１０６から求め、改めて各文書との距離を計算して閾値未満の距離にある文書を検索結果として提示することもできる。以下、距離閾値取得（Ｓ４０２）および検索実行（Ｓ４０３）の詳細を説明する。
【００５９】
（１）距離閾値取得（Ｓ４０２）
ここでは検索式内で指定された位置情報に基づいて距離閾値を距離閾値インデクスから読み出す。検索位置情報を（ｘ，ｙ）としたとき、文書分配式格納ＤＢ１０５中に格納された文書分配式を読み出し、この文書分配式に従って、検索位置が属するセルを決定する。セルが決定されると、距離閾値インデクスＤＢ１０６から、当該セルに対応する距離閾値が、隣接セルの拡張数の形式で与えられる。
【００６０】
（２）検索実行（Ｓ４０３）
距離閾値取得の結果、得られた距離閾値（隣接セルの拡張数）を「θ」，セルサイズを「Ｃ」とすると、文書ＤＢ１０４から検索式で指定された位置から「θＣ」以内の距離にある文書群が選択され、選択された文書群に対して検索式中の位置以外の条件が適用される。この場合、文書ＤＢ１０４中の全ての文書と検索位置との距離を計算する必要があるため、文書群を得るために「Ｏ（Ｎ）」の計算量が必要となる。
【００６１】
文書ＤＢ１０４の転置ファイルを使用する場合、必要な隣接セルに含まれる文書群を、「θＣ」以内の距離にあると見なして、これらの文書群に対して検索式中の位置以外の条件を適用できる。転置ファイルを用いた検索において、セル（ｉ，ｊ）に含まれる文書の集合をＴ（ｉ，ｊ）とすると、距離閾値以内の文書群は、距離閾値までの範囲にあるセルに含まれる文書のリストで得られる。
【００６２】
より具体的には、距離閾値内の文書群は、セル形状が矩形の場合は図１１のアルゴリズムで得られる。また、セル形状が六角形の場合は、図１２のアルゴリズムでで得られる。ただし、「ａｂｓ（ｘ）」は「ｘ」の絶対値を表す。このとき、文書ＤＢ１０４中の全ての文書と検索位置との距離を計算する必要がないため、文書群を得るためには「Ｏ（Ｎ）」の計算量で十分である。
【００６３】
≪実施例≫
（１）矩形セルでの範囲設定
図１３に基づき地球上の一部の地域と仮定して、その範囲を矩形セルに分割する方法を説明する。ここでは対象とする領域は、緯度方向に「Ｌａｔmax」度と「Ｌａｔmin」度、経度方向に「ＬＮＧmax」度と「ＬＮＧmin」度の広袤を持つと仮定する。この領域を、およそ一辺「Ｃｋｍ」のセルに分割する場合を説明する。なお、球面上の領域であるが、各辺は直線で模してある。
【００６４】
ここで定めることは、およそ一辺「Ｃｋｍ」のセルが、緯度の領域，経度の領域それぞれの定義方法である。緯度の領域については、地球を回転楕円体ではなく球とみなせば、地球上の位置によらず度数当たりの経線方向の長さは一定であり、その値は、子午線の円周長を「Ｒ」とすれば1秒当たり「Ｒ／１，２９６，０００」であり、地球の場合は１秒当たりおよそ「０．０３０８６ｋｍ」となる。
【００６５】
したがって、緯度方向に「Ｃｋｍ」の領域を取るためには、セルの緯度領域は「Ｃ／０．０３０８６」で決められる。例えば一辺「１０ｋｍ」のセルを作るには、セル当たりの緯度領域はおよそ「３２４．０」秒とすればよい。
【００６６】
経度領域については、緯度によって領域の緯線方向の線分長は異なる。緯度によらず各セルの経度範囲を一定に保ちながらセルの辺の長さをほぼ一定に保つために、基準となる緯線の度数を「θ＝（Ｌａｔmax＋Ｌａｔmin）／２」とし、この緯線上でのセルの長さに基づいて経度範囲を定める。
【００６７】
緯度領域と同様に地球を球と見なせば、この緯線上では、１秒当たりの長さは、赤道の円周長をＲとすれば「Ｒ＊ｃｏｓθ／１，２９６，０００」となり、１ｋｍあたりの度数はその逆数となる。例として、北緯「２４．４２６」度から「４５．５５８」度，東経「１２２．００５」度から「１５３．９８１」度の領域を、一辺「１０」ｋｍのセルに分割することを考える。このとき、１つのセルの緯度方向の領域は、簡単化のために「子午線長Ｒ＝４０，０００ｋｍ」とすると、「１０×１，２９６，０００／４０，０００＝３２４．０」から「３２４．０」秒である。
【００６８】
経度の領域は、１秒当たりの距離が「（４０，０００×ｃｏｓ（２４．４２６°＋４５．５５８°）／２）／１，２９６，０００＝（４０，０００×ｃｏｓ３４．９９２°）／１，２９６，０００＝０．０２５２８（ｋｍ）」となるため、当該緯度における１つのセルの経度方向の領域は「３９５．５」秒とすればよい。この数値を前記式（１）に当てはめることで、文書分配式が構成できる。
【００６９】
（２）六角形分割での範囲設定
図１４に基づき地球上の一部の地域と仮定して、その範囲を六角形セルに分割する方法を示す。ここでも対象とする領域は、緯度方向に「Ｌａｔmax」度と「Ｌａｔmin」度、経度方向に「ＬＮＧmax」度と「ＬＮＧmin」度の広袤を持つと仮定する。この領域を、中心間の間隔がおよそ「Ｃｋｍ」のセルに分割することを考える。このとき各セル同士は、図１４に示すとおり、経度方向に「Ｃ」，緯度方向に「｛（√３）／２｝Ｃ」の間隔が空けられることになる。また、緯度方向に１つずれたセル同士は、経度方向で「Ｃ／２」の間隔が空けられる。
【００７０】
図１３と同様、経度方向の領域幅は緯度によって変化するため、「Ｌａｔmax＋Ｌａｔmin／２」の緯度での幅を基準とする。この区間を「Ｃ」ｋｍに分割すると、経度１秒あたりの地球上のこの緯線上の距離は、赤道長を「Ｒ」とすると「Ｒ＊ｃｏｓθ／１，２９６，０００」であり、セルあたり、「Ｃ」を緯線上の１秒当たりの距離で除した秒数で得られる。
【００７１】
緯度方向については、１秒当たりの距離は、子午線長を「Ｒ」と置くと「Ｒ／１，２９６，０００」であり、セル当たり、「｛（√３）／２｝Ｃ」をこの値で除した秒数となる。
【００７２】
与えられた全領域の最小経度、最小緯度を基準として、緯度方向、経度方向にセルの中心を配置することで前記式（３）に示す方法を用いて文書分配式を構成できる。
【００７３】
（３）距離閾値インデクス
図１５の文書分布例に基づき距離閾値インデクスの構成方法の一例を詳述する。ここでは領域が「７×７」の矩形セルに分割され、分割された文書数が図１６に示されている。
【００７４】
ここで図１の地点Ａおよび地点Ｂに含まれるセルについて、それぞれの隣接セルをどれだけ辿れば「１０文書」が範囲に入るかを検討する。
【００７５】
与えられた位置の含まれるセルを基準として、当該セル内で「１０文書」に達しなければ隣接したセル全てを対象とし、そこでも「１０文書」に達しなければ更にもう１段階隣接したセルを対象とし、最終的に「１０文書」に達するまで範囲を拡大する。これを地点Ａ，地点Ｂについて、行った結果が図１７および図１８に示されている。
【００７６】
地点Ａにおいては、当該セルには「９文書」だけが含まれるが、隣接した８つのセルを合計すると、「１０文書」を超えるため、「１０文書」に達するのに必要な隣接数は「１」となり、これが距離閾値となる。
【００７７】
地点Ｂにおいては、当該セルには「０文書」、隣接したセルを合計しても「３文書」のみなため、「１０文書」に達するためには２段階隣接したセルに分配された文書を合計する必要があり、距離閾値は「２」となる。
【００７８】
距離閾値は各セルについて計算できる。図１９には全てのセルについての距離閾値が示されている。ここでは文書の密度が高い部分は小さい距離閾値が与えられたセルが多く、文書の密度が低い部分は大きな距離閾値が与えられたセルが多くなることが示されている。
【００７９】
なお、図２０は六角形セルの場合の隣接の考え方を示し、六角形のセルは矩形に比べて隣接したセルの相対は円に近くなるため、与えられた位置と文書との間の距離の閾値について、より精度よく求めることができる。
【００８０】
（４）検索実行
図２１に基づき矩形セルの領域における検索実行例を説明する。ここではセル（ｉ，ｊ）内の位置が指定されたとする。このとき当該セルの求める文書数に対する距離閾値が「１」だったとすると、1つ隣接したセルに分配された文書数を合計すれば、求める数以上の文書が得られることが分かる。
【００８１】
したがって、指定された位置を中心に、「２Ｃ」の範囲で文書を検索すればよく、一般的に当該セルの距離閾値が「θ」だった場合は文書検索範囲は「（θ＋１）Ｃ」とすればよい。また、転置ファイルを使用する場合は、「θ」だけ離れて隣接したセルに分配された文書を選択すれば、必要な文書数を得られる。
【００８２】
（５）イベントのサンプリング
前記距離閾値指定装置１００の主な目標は、各セル領域において、検索される文書数を概数として予め得ることにある。このため、全ての文書が事前にセルに割り当てられている必要はない。文書数が多く、かつ範囲設定部の処理時間が十分に確保できない場合は、サンプリングにより、各セルに属する文書の数を概数として保存し、各セルの濃度を予測してもよい。
【００８３】
この場合、転置ファイルが使用できないため、検索時には、与えられた位置情報に対して、全ての文書に対して距離計算が行われる必要がある。
【００８４】
なお、本発明は上記実施形態に限定されるものではなく、装置構成などは各請求項に記載された範囲内で変形して実施することができる。また、本発明は、前記距離閾値指定装置１００の各部１０１〜１０６の一部もしくは全部として、コンピュータを機能させる文書検索プログラムとして構成することもできる。このプログラムによれば、Ｓ２０１〜Ｓ２０４，Ｓ３０１〜Ｓ３０５，Ｓ４０１〜Ｓ４０４の一部あるいは全部をコンピュータに実行させることが可能となる。
【００８５】
前記プログラムは、Ｗｅｂサイトや電子メールなどネットワークを通じて提供することができる。また、前記プログラムは、ＣＤ−ＲＯＭ，ＤＶＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−ＲＷ，ＤＶＤ−Ｒ，ＤＶＤ−ＲＷ，ＭＯ，ＨＤＤ，ＢＤ−ＲＯＭ，ＢＤ−Ｒ，ＢＤ−ＲＥなどの記録媒体に記録して、保存・配布することも可能である。この記録媒体は、記録媒体駆動装置を利用して読み出され、そのプログラムコード自体が前記実施形態の処理を実現するので、該記録媒体も本発明を構成する。
【符号の説明】
【００８６】
１００…距離閾値指定装置
１０１…セル定義部
１０２…範囲設定部
１０３…検索部
１０４…文書ＤＢ
１０５…文書分配式格納ＤＢ
１０６…距離閾値インデクスＤＢ
【図１】
2015219614.tif 000009
【図２】
2015219614.tif 000010
【図３】
2015219614.tif 000011
【図４】
2015219614.tif 000012
【図５】
2015219614.tif 000013
【図６】
2015219614.tif 000014
【図７】
2015219614.tif 000015
【図８】
2015219614.tif 000016
【図９】
2015219614.tif 000017
【図１０】
2015219614.tif 000018
【図１１】
2015219614.tif 000019
【図１２】
2015219614.tif 000020
【図１３】
2015219614.tif 000021
【図１４】
2015219614.tif 000022
【図１５】
2015219614.tif 000023
【図１６】
2015219614.tif 000024
【図１７】
2015219614.tif 000025
【図１８】
2015219614.tif 000026
【図１９】
2015219614.tif 000027
【図２０】
2015219614.tif 000028
【図２１】
2015219614.tif 000029