【手続補正書】
【提出日】平成25年2月14日(2013.2.14)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
索引データ構造（２００）によってデータベース内のオブジェクトを探索する方法であり、当該索引データ構造（２００）は、空間を分割するよう定義された空間要素（５１）のコレクション（２０５、２０６）にオブジェクト属性値を関連付けており、予め定義された数の空間要素（５１）が次のレベルの空間要素（５２）に結合可能である、
方法であって、
第１入力探索パターンを求めて前記索引データ構造（２００）を探索し、前記第１入力探索パターンが、空間要素（５１）の第１コレクション（２０５、２０６）に、前記索引データ構造（２００）によって関連付けられている場合には、前記第１コレクション（２０５、２０６）からの全ての空間要素（５１）を、空間要素（５１）の第１候補集合（１０２ａ、１０２ｂ）に含める工程であって、前記第１候補集合（１０２ａ、１０２ｂ）における空間要素（５１）の数が、一定の限界を超過する場合には、前記空間要素（５１）のうちの一部または全部が、より少ない数の次のレベルの空間要素（５２）に結合される、工程と、
第２入力探索パターンを求めて前記索引データ構造（２００）を探索し、前記第２入力探索パターンが、空間要素（５１）の第２コレクション（２０５、２０６）に、前記索引データ構造（２００）によって関連付けられている場合には、前記第２コレクション（２０５、２０６）からの全ての空間要素（５１）を、空間要素（５１）の第２候補集合（１０２ａ、１０２ｂ）に含める工程であって、前記第２候補集合（１０２ａ、１０２ｂ）における空間要素（５１）の数が、一定の限界を超過する場合には、前記空間要素（５１）のうちの一部または全部が、より少ない数の次のレベルの空間要素（５２）に結合される、工程と、
前記第１候補集合および前記第２候補集合（１０２ａ、１０２ｂ）から、空間要素（５１、５２）の結合後候補集合（１０４ａ）を形成する工程と、
結果オブジェクトの集合を取得するように、前記第１入力探索パターンおよび前記第２入力探索パターンと一致するオブジェクトを求めて、空間要素（５１、５２）の前記結合後候補集合（１０４ａ）を探索する工程とを備えた、オブジェクト探索方法。
【請求項２】
請求項１において、前記第１候補集合および前記第２候補集合（１０２ａ、１０２ｂ）の共通部分を構成することによって、前記第１候補集合および前記第２候補集合（１０２ａ、１０２ｂ）から前記結合後候補集合（１０４ａ）が構成される、オブジェクト探索方法。
【請求項３】
請求項１または２において、前記索引データ構造（２００）は、オブジェクト属性値を、２次元平面の一部分に相当する、４分木の空間要素（５１）に関連付け、
４枚の隣接したタイルが、次のレベルの空間要素（５２）を表す１枚の次のレベルのタイルに結合可能である、オブジェクト探索方法。
【請求項４】
請求項３において、空間要素（５１）の前記第１候補集合（１０２ａ、１０２ｂ）または前記第２候補集合（１０２ａ、１０２ｂ）内における、空間要素（５１）の組合せについて、４枚以下の隣接するタイル（５１）が、１枚の次のレベルのタイル（５２）に結合され、この結合は、前記次のレベルの空間要素（５２）の前記エリアが前記結合後空間要素（５１）の上位集合を表す、安全なコンパクト化を表している、オブジェクト探索方法。
【請求項５】
請求項１から４のいずれか一項において、連続したデータ要素を表す前記第１入力探索パターンまたは前記第２入力探索パターンを求めて前記索引データ構造（２００）を探索する間に、前記第１入力探索パターンまたは前記第２入力探索パターンが空間要素（５１、５２）の、あるオブジェクトの属性値の接頭部に一致するか否かが調べられる、オブジェクト探索方法。
【請求項６】
請求項１から５のいずれか一項において、入力探索パターンを求めて前記索引データ構造（２００）を探索することについて、予め組み立てられた補助の候補集合に対してオブジェクト属性またはオブジェクト属性の接頭部を関連付ける、補助の索引データ構造が使用され、
前記補助の索引データ構造内の前記探索が非空集合を生成する場合には、この集合は所望の候補集合（１０２ａ、１０２ｂ）を構成し、
前記補助の索引データ構造内の前記探索が非空集合を生成しない場合には、所望の候補集合（１０２ａ、１０２ｂ）が、前記入力探索パターンを求めて前記索引データ構造（２００）を探索することによって取得される、オブジェクト探索方法。
【請求項７】
請求項１から６のいずれか一項において、前記第１入力探索パターンと前記第２入力探索パターンのいずれか一方または両方を対話的に入力すると、前記結合後候補集合（１０４ａ）は段階的に減少する、オブジェクト探索方法。
【請求項８】
請求項１から７のいずれか一項において、前記第１入力探索パターンと前記第２入力探索パターンのいずれか一方または両方を対話的に入力すると、前記入力探索パターンに影響を及ぼされた候補集合（１０２ａ、１０２ｂ、１０４ａ）の表現性についてのフィードバックが提供され、
前記表現性は、前記候補集合（１０２ａ、１０２ｂ、１０４ａ）の濃度が減少すると増加する、オブジェクト探索方法。
【請求項９】
請求項１から８のいずれか一項において、前記結合後候補集合（１０４ａ）の前記濃度が所定のしきい値よりも低くなると、空間要素（５１、５２）の前記結合後候補集合（１０４ａ）においてオブジェクトを求めて前記探索が行われ、
前記結果オブジェクトが出力装置を介して出力される、オブジェクト探索方法。
【請求項１０】
請求項１から９のいずれか一項において、オブジェクトを求めて空間要素（５１、５２）の前記結合後候補集合（１０４ａ）を探索する間に、
既に探索済みの空間要素（５１、５２）の数が計数されて、この数が予め定義された制限値を超えると、探索処理が停止されるか、または、
既に見つかったオブジェクトの数が計数されて、この数が予め定義された制限値を超えると、探索処理が停止されるか、または、
探索の経過時間が測定され、予め定義された制限時間を超えると、探索処理が停止される、オブジェクト探索方法。
【請求項１１】
請求項１から１０のいずれか一項において、前記探索は、特定の標的領域に関連付けられた空間要素（５１、５２）のみを考慮するよう制約される、オブジェクト探索方法。
【請求項１２】
請求項１から１１のいずれか一項において、結果オブジェクトの集合のうちの、あるオブジェクトが、ユーザが実際に見つけようと意図するオブジェクトに相当する確率を示す、一連の発見的規則に従って、前記オブジェクトの関連性が決定され、
前記結果は、関連性の高いものから順にユーザに表示される、オブジェクト探索方法。
【請求項１３】
請求項１から１２のいずれか一項において、前記データベースはナビゲーション装置のマップデータを含み、
前記オブジェクトは当該マップデータの地理オブジェクトに相当し、
前記２次元平面は前記ナビゲーション装置によって表示される、前記空間要素（５１、５２）によって分割された正縮尺地図に相当する、オブジェクト探索方法。
【請求項１４】
請求項１３において、前記第１入力探索パターンと前記第２入力探索パターンのいずれか一方または両方を対話的に入力すると、空間要素（５１、５２）の前記結合後集合に相当する地理エリアが、前記対話入力中に出力される、オブジェクト探索方法。
【請求項１５】
請求項１から１４のいずれか一項において、前記第１入力探索パターンと前記第２入力探索パターンのいずれか一方または両方は、複数の文字と数字のいずれか一方または両方が一つのキーに割り当てられた簡易キーパッド（３）を介して入力され、各キーは前記入力探索パターンの一文字ごとに１度だけ押されるものである、オブジェクト探索方法。
【請求項１６】
請求項１から１５のいずれか一項において、前記第１入力探索パターンと前記第２入力探索パターンのいずれか一方または両方は、ある複数の予め定義された役割のうちの１つの役割を有する、と発見的に解釈され、前記役割は、前記各入力探索パターンの、想定される、根本的な意味を示す、オブジェクト探索方法。
【請求項１７】
請求項１６において、前記第１入力探索パターンと前記第２入力探索パターンのいずれか一方または両方を発見的に解釈することによって、役割に特化した発見的候補集合（１０２ａ、１０２ｂ）が入力探索パターンごとに計算され、
前記役割に特化した発見的候補集合（１０２ａ、１０２ｂ）の共通部分を求めることによって、探索クエリの特定の解釈についての結合後発見的候補集合（１０４ａ）が取得される、オブジェクト探索方法。
【請求項１８】
請求項１７において、第１ステップでは、ある探索クエリの複数の異なる解釈のそれぞれについて、結合後発見的候補集合（１０４ａ）がその都度計算されて全数探索され、
第２ステップでは、前記探索クエリを特定の解釈に制約することなく、前記結合後候補集合（１０４ａ）が計算されて全数探索される、オブジェクト探索方法。
【請求項１９】
請求項１８において、前記異なる解釈は、前記関連付けられた、役割に特化した発見的候補集合（１０２ａ、１０２ｂ）および結合後発見的候補集合（１０４ａ）を計算することなく、最初に記号を使って列挙され、
前記索引データ構造（２００）を検索することによって、１つ以上の前記役割に特化した発見的候補集合（１０２ａ、１０２ｂ）が空であると検出されと、前記異なる解釈はさらに考慮されない、オブジェクト探索方法。
【請求項２０】
請求項１８または１９において、入力探索パターンについての考慮される前記異なる解釈のうちの１つの解釈、または前記異なる解釈の前記記号による列挙は、索引データ構造（２００）内の検索によって得られた１つ以上の役割に特化した発見的候補集合（１０２ａ、１０２ｂ、１０４ａ）の推定濃度に従って決定される、オブジェクト探索方法。
【請求項２１】
索引データ構造（２００）によってデータベース内のオブジェクトを探索する方法であり、当該索引データ構造（２００）は、要素（５１）のコレクション（２０５、２０６）にデータベースのオブジェクト属性値を関連付ける、方法であって、
入力探索クエリ内で、第１入力探索パターンと第２入力探索パターンの一方または両方が、ある複数の予め定義された役割のうちの１つの役割を有する、と発見的に解釈する工程であって、前記役割は、オブジェクト属性値に関する、前記各入力探索パターンの、想定される、根本的な意味を示す、工程と、
前記第１入力探索パターンと前記第２入力探索パターンの一方または両方を発見的に解釈することによって、要素（５１）の役割に特化した発見的候補集合（１０２ａ、１０２ｂ）を前記索引データ構造によって入力探索パターンごとに計算する工程であって、前記役割に特化した発見的候補集合（１０２ａ、１０２ｂ）は、前記入力探索パターンとその規定の役割において一致する少なくとも１つの属性値を有するオブジェクトを含む要素（５１）のこれらコレクションを含む、工程と、
前記探索クエリの特定の解釈についての結合後発見的候補集合（１０４ａ）を取得するように、前記第１入力探索パターンおよび前記第２入力探索パターンについて、前記役割に特化した発見的候補集合（１０２ａ、１０２ｂ）の共通部分を求める工程と、
要素（５１、５２）の前記結合後発見的候補集合（１０４ａ）において前記第１入力探索パターンおよび前記入力第２探索パターンに一致するオブジェクトを特定し、これによって結果オブジェクトの集合を取得する工程とを備えたオブジェクト探索方法。
【請求項２２】
請求項２１において、第１ステップでは、ある探索クエリの複数の異なる解釈のそれぞれについて、結合後発見的候補集合（１０４ａ）がその都度計算されて、必要であれば、全数探索され、
第２ステップでは、前記探索クエリを特定の解釈に制約することなく、結合後候補集合（１０４ａ）が計算されて、必要であれば、全数探索される、オブジェクト探索方法。
【請求項２３】
請求項１から２２のいずれか一項において、ある入力探索パターンについての予めコンパクト化された候補集合（１０２ａ、１０２ｂ）を提供するように、前記メイン索引データ構造（２００）が利用される前に必ず調べられる補助の索引データ構造が利用される、オブジェクト探索方法。
【請求項２４】
請求項１から２３のいずれか一項において、候補集合（１０２ａ、１０２ｂ）および結合後候補集合（１０４ａ）が、最初に、所与の入力探索パターンについて計算され、その後、キャッシュメモリデータベースに格納される、オブジェクト探索方法。
【請求項２５】
請求項１から２４のいずれか一項において、前記索引データ構造（２００）は、オブジェクト属性の完全に同一値についてのみでなく、追加的に、前記完全に同一値の予め定義された変形値についてもエントリを有し、これら変形値は、ある文字を他の文字で置換しているか、ある文字を元の値に追加しているか、ある文字を元の値から省略しているか、または、いくつかの文字の位置を元の値における位置に対して交換している、オブジェクト探索方法。
【請求項２６】
請求項１から２５のいずれか一項において、前記第１候補集合および前記第２候補集合（１０２ａ、１０２ｂ）が結合される前に、前記第１候補集合および前記第２候補集合（１０２ａ、１０２ｂ）内に既に存在する前記空間要素（５１）に地理的に隣接する前記空間要素（５１）を、前記第１候補集合および第２候補集合（１０２ａ、１０２ｂ）に包含することによって、前記第１入力探索パターンおよび前記第２入力探索パターンについて前記第１候補集合および前記第２候補集合（１０２ａ、１０２ｂ）が拡張される、オブジェクト探索方法。
【請求項２７】
請求項１から２６のいずれか一項において、前期第１入力探索パターンおよび前記第２入力探索パターンが媒体を介して入力されて、単一の探索クエリの代わりに複数の入力探索パターンからそれぞれが成る複数の探索クエリ変形を生成し、
索引データ構造（２００）の検索を通して前記探索クエリ変形から探索パターンについて計算された候補集合（１０２ａ、１０２ｂ）の推定濃度、または前記探索クエリ変形について計算された結合後候補集合（１０４ａ）の濃度が用いられて、さらなる処理に前記探索クエリ変形の部分集合の選択を導くか、または、さらなる処理手順に影響を与える個々の探索クエリ変形への優先順位の割り当てを導く、オブジェクト探索方法。
【請求項２８】
請求項１から２７のいずれか一項において、索引データ構造（２００）内の検索を通して得られた１つ以上の候補集合（１０２ａ、１０２ｂ、１０４ａ）の推定濃度は、１つの入力探索パターンまたは複数の入力探索パターンの表現性の基準として用いられる、オブジェクト探索方法。
【請求項２９】
請求項１から２８のいずれか一項において、探索結果のユーザの最終選択は、将来の探索処理に用いられるように、永続的記憶媒体に登録される、オブジェクト探索方法。
【請求項３０】
請求項１から２９のいずれか一項において、空間要素（５１、５２）の前記結合後候補集合の前記全数探索の結果として、前記入力探索クエリの全ての入力探索パターンと一致する属性を有するオブジェクトのみでなく、１つ以上の入力探索パターンがオブジェクト属性に一致しないオブジェクトも登録される、オブジェクト探索方法。
【請求項３１】
請求項１から３０のいずれか一項において、前記索引データ構造（２００）、および空間要素（５１）の関連付けられたコレクション（２０４〜２０６）は、前記索引データ構造（２００）を用いて実際に探索される前記データベースから生成されるのではなく、実際に探索される前記データベースの前記オブジェクトの全部または大部分を含む、前記データベースよりも大きいデータベースから生成される、オブジェクト探索方法。
【請求項３２】
請求項１から３１のいずれか一項において、索引データ構造（２００）内に所与の単語が存在するか否か、索引データ構造（２００）の検索を通して得られた、１つ以上の関連付けられた候補集合（１０２ａ、１０２ｂ）の推定濃度、または１つ以上の結合後候補集合（１０４ａ）の濃度が用いられて、タイプミスされた探索パターンを特定および／または訂正し、および／または、タイプミスされた探索パターンを有効な探索パターンに変換することを意図したユーザ指定の探索パターンの自動的に生成された修正を評価する、オブジェクト探索方法。
【請求項３３】
請求項１から３２のいずれか一項において、非空間データベースの探索を可能にするために、合成空間位置の値が、既存データベースオブジェクト属性値の関数として、各データベースオブジェクトに関連付けられる、オブジェクト探索方法。
【請求項３４】
請求項１から３３のいずれか一項において、当該方法を実行するよう配置され、サーバとして動作する１つ以上のコンピュータ装置、およびクライアントとして動作する１つ以上のコンピュータ装置を備えたシステムを使用する方法であり、
各クライアントは、探索クエリをユーザ入力として受け付け、かつ／または、探索結果を１人以上のユーザに通信して返すように構成され、各クライアントはネットワークを介して、または一方向もしくは双方向の通信リンクを介して、前記サーバに永続的または断続的に接続される、オブジェクト探索方法。
【請求項３５】
請求項１から３４のいずれか一項に記載の方法を実行する、コンピュータ装置。
【請求項３６】
請求項１から３４のいずれか一項に記載の方法を実行する、モバイルコンピュータ装置。
【請求項３７】
請求項１から３４のいずれか一項に記載の方法を実行する、ナビゲーション装置。