Ｗｅｂページ検索方法およびＷｅｂページ検索装置、Ｗｅｂページ検索プログラム並びにそのプログラムを記録した記録媒体
【課題】 Ｗｅｂページの系列を検索する方法を高速化する。
【解決手段】 インターネット上に発信されている大量のＷｅｂページから、Ｗｅｂページから抽出した属性に関する条件とハイパーリンクに関する条件を組み合わせて指定し、Ｗｅｂページの系列を検索するための問い合わせの処理方法において、Ｗｅｂページに関するインデックスを利用し、問い合わせに指定された条件から、未処理で、かつ他条件の処理結果に依存せずに処理結果を求めることのできる条件の処理コストと処理結果を予測し、問い合わせ処理の進行状況にあわせて最適な条件を選択し処理する操作を、問い合わせで指定された全ての条件を処理するまで繰り返し、問い合わせの条件を満たすＷｅｂページの系列を求める。
【解決手段】 インターネット上に発信されている大量のＷｅｂページから、Ｗｅｂページから抽出した属性に関する条件とハイパーリンクに関する条件を組み合わせて指定し、Ｗｅｂページの系列を検索するための問い合わせの処理方法において、Ｗｅｂページに関するインデックスを利用し、問い合わせに指定された条件から、未処理で、かつ他条件の処理結果に依存せずに処理結果を求めることのできる条件の処理コストと処理結果を予測し、問い合わせ処理の進行状況にあわせて最適な条件を選択し処理する操作を、問い合わせで指定された全ての条件を処理するまで繰り返し、問い合わせの条件を満たすＷｅｂページの系列を求める。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】本発明は、出願中の特許「ホームページの系列的検索方法、および装置、記録媒体（特願２０００−１６２６５８）」で発明された検索方法を高速に行うための発明である。
【０００２】インターネット上に発信されているＷｅｂページは、年々増加しており、特に都市部においては、地理的にも集中する傾向にある。このため、現在インターネット上で公開されているキーワード検索やディレクトリサービスだけでは、必要な情報を短時間で検索することは困難になりつつある。この問題を解決する手法の一つとして、複数の条件を組み合わせて、Ｗｅｂページを系列として検索する手法が考えられる。この系列を検索するための方法は、特願２０００−１６２６５８にて発明されているが、その検索を高速に実施する方法は発明されていなかった。
【０００３】Ｗｅｂページ系列の検索では、Ｗｅｂページの属性に関する条件と、Ｗｅｂページ間のリンクに関する条件を複数組み合わせて、問い合わせを指定することができる。例えば、類似する情報が複数あるときに、Ｗｅｂページ間のハイパーリンク関係に基づいて有名なリンク集からリンクされているＷｅｂページを選択したり、Ｗｅｂページから抽出した地理属性に基づき、一定距離以内にある情報という形で条件を指定し、リンク先を検索することができる。
【０００４】この問い合わせの処理するためには、大量のＷｅｂページとそこから抽出した属性を評価する必要があり、その検索空間が膨大となるため、幅優先探索アルゴリズムなど、従来の単純なアルゴリズムでは、現実的な時間で問い合わせを処理することはできなかった。本出願で発明する高速化手法では、検索対象となる情報に関する各種インデックスを利用し、その問い合わせ中の条件の評価順序を最適化し、高速に問い合わせ処理を可能にする。
【０００５】このＷｅｂページの系列に関する問い合わせが高速に処理できるようになると、従来のキーワード指定によるＷｅｂページの検索を、リンクに関する条件も含め複数の条件の指定による検索へと拡張することができる。この場合、検索サービスの利用者が、直接条件項目を指定することになるが、その問い合わせの入力方法を変えることで、文章や音声など自然言語による情報検索や、グラフィックユーザインタフェース（ＧＵＩ）を利用したインタラクティブな情報検索にも適用可能である。また、問い合わせの結果がＷｅｂページの系列となるので、その系列をリスト形式で出力したり、直接図示したり、カーナビゲーションのように必要に応じて、順序だててＷｅｂページを提示することも可能になる。このように、問い合わせの検索結果は、現在のカーナビゲーションや将来の携帯端末や街頭端末を使った歩行者ナビゲーションなどに応用可能であり、その処理を高速化することにより、ユーザから見た使い勝手を向上させることができる。
【０００６】
【従来の技術】インターネット上に存在する膨大な情報から、都市に関連したものを抽出するためには検索機能が必須である。ユーザが検索機能を直接利用する場合は、キーワード指定による検索が便利ではあるが、その検索結果に意図しない結果が大量に含まれるなど、その結果に対する信頼性には問題があった。
【０００７】こうした問題を解決する手法の一つとして、キーワードなどＷｅｂページの属性やハイパーリンク関係など複数の条件を指定して、Ｗｅｂページを系列として検索する手法が考えられる。これにより、例えばキーワードレベルだけで検索されていた意図されていなかった結果を排除することができる。
【０００８】こうしたＷｅｂページの系列を検索するための方法の一つとしてＷｅｂ空間を対象とした検索言語がある。この検索言語には、リンク構造とコンテンツに関する条件の指定により検索を行うＷ３ＱＬ（David Konopnicki and Oded Shmueli.W3QS: A Query System for the World-Wide Web. In Proceedings of the 21stInternational Conference on Very Large Data Bases, pp.54-65, 1995、David Konopllicki and Oded Shmueli. Information Gathering in the World WideWeb: The W3QL Query Language and the W3QS System. ACM Transactions on Database Systems, Vol. 23, No. 4, pp. 369-410, 1998）やＷｅｂＳＱＬ（Alberto O. Mendelzon, George A. Mihaila, and Tova Milo. Querying the World Wide Web. International Journal on Digital Libraries, Vol. 1, No. 1, pp. 54-67, 1997、Alberto O. Mendelzon and Tova Milo. Formal Models of Web Queries. In Proceedings of the 16th ACM Symposium on Principles of DatabaseSystems, pp. 134-143, 1997）、Ｗｅｂページの構造に関する条件指定や検索結果の再構成が可能なＷｅｂＯＱＬ（Gustavo O. Arocena and Alberto O. Mendelzon. Weboql: Restructuring Documents, Databases, and Webs. In Proceedings of ICDE, pp. 24-33. 1998）、ＳｔｒｕＱＬ（Mary Fernandez, Daniela Florescu, Alon Levy, and Dan Suciu. A Query Language for a Web-Site Management System. SIGMOD Record, Vol. 26, No. 3, pp. 4-11, 1997）がある。Ｗｅｂ情報を対象とした検索言語はＸＭＬの標準化と密接に関連する領域でもある。
【０００９】一方、電子化した都市情報を地図と関連づけて扱うためのシステムとしては、地理情報システム（ＧＩＳ）がある。従来ＧＩＳは単独の計算機で用いられることが多かったが、近年のネットワークとパソコンの普及により、多様な利用形態が可能な数多くの製品が発表されてきている。ＷｅｂＧＩＳなどインターネットへの広がりもその一つと考えられ、将来的には、インターネット上のコンテンツと密接に関わりを持つ可能性も持っている。現在の段階では、情報の位置を地図上に表示するようなサービスが公開されているが、特願２０００−１６２６５８のようなＷｅｂページの系列を検索するようなサービスはまだ行われていないと理解している。
【００１０】特願２０００−１６２６５８の発明は、その検索空間を拡張Ｗｅｂ空間（平松薫、石田亨、地域情報サービスのための拡張Ｗｅｂ空間、情報処理学会論文誌：データベース、Vol. 41, No. SIG6(TOD7), PP. 81-90, 2000）とし、その情報空間を半構造データ（Serge Abiteboul. Querying Semi-Structured Data. In Database Theory - ICDT '97, 6th, International Conference, pp. 1-18, 1997、田島敬史、半構造データのためのデータモデルと操作言語、情報処理学会論文誌:データベース、Vol. 40, No. SIG 3(TOD 1), pp. 152-170, 1999）として捉えている。半構造データを対象としたデータベースシステム（ＤＢＭＳ）の一つに、スタンフォード大学で開発されたＬｏｒｅがある。Ｌｏｒｅでは、ＸＭＬに代表される半構造データに特化した各種インデックスを導入（Roy Goldman and Jennifer Widom. DataGuide: Enabling Query Formulation and Optimization inSemistructured Databases. In Proceedings of the 23rd International Conference on Very Large Data Bases, pp. 436-445, 1997）し、その問い合わせ処理にはコスト予測を導入して最適化を実現している（Jason McHugh and Jennifer Widom. Query Optimization for XML. In Proceedings of the 25th International Conference on Very Large Data Bases, pp. 315-326, 1999）。本発明の手法は、Ｌｏｒｅの手法と非常に良く似ているが、最大の差は、対象とした検索空間の具体性にある。本発明では、実際の都市における情報に基づいた拡張Ｗｅｂ空間を検索対象とし、その問い合わせを最適化するために、条件の評価順序の決定方法を特化させている。また、検索システムで利用するインデックスの構築をＷｅｂページとＧＩＳを用いて作成し、最適化手法の有効性なものにしている。
【００１１】このインデックスの構築は、Ｗｅｂ情報のキャッシュを行うプロキシや、その関連プロトコル、ＧＩＳとＷｅｂ情報を関連づけるためのアドレスマッチングなどと関連するものである。本発明では、インデックスの効率的な構築や更新は考慮にいれていないが、問い合わせ処理の最適化と合わせて、拡張Ｗｅｂ空間に基づく検索システムの周辺技術として連携させる必要がある。
【００１２】
【発明が解決しようとする課題】本発明は、特願平１１−１４９１００（特開２０００−３３９３３０号公報）および特願２０００−１６２６５８から発想したものであり、これまでに発明したＷｅｂページの系列を検索する方法を高速化するためのものである。これまでに発明してきたＷｅｂページの系列の検索では、大量のＷｅｂページとそこから抽出した属性を評価する必要がある。その検索空間が膨大となるため、これまでの発明で用いた幅優先探索アルゴリズムなど、単純なアルゴリズムでは、検索自体は可能なものの、現実的な時間で問い合わせを処理することはできなかった。この処理時間の問題により、これまでの方法に基づき作製したシステムは、旅行計画やナビゲーション用のコンテンツの作成など、問い合わせに基づく検索結果をあらかじめ構築してそれを公開するような、間接的な利用に限られていた。
【００１３】
【課題を解決するための手段】前節で述べた処理時間による制限をなくすため、本出願ではその高速化手法を発明する。高速化手法では、検索対象となるＷｅｂページから抽出したキーワードやハイパーリンクなどの属性情報に関する各種インデックス、問い合わせに応じて抽出した属性間の関連性に基づきＷｅｂページ間のリンクを動的に生成するためのインデックスを利用し、問い合わせ処理を進めていく。インデックスは、実際のＷｅｂページをＷｅｂロボットで収集し、自然言語処理やアドレスマッチング等を行って作成する。
【００１４】問い合わせに含まれる複数の条件は、これらインデックスを利用して評価されるが、単純なアルゴリズムでは、従来システムと同様、検索空間が爆発する可能性がある。そこで、問い合わせを進めていく上で、逐次、指定された条件で未評価のものから条件間の依存関係に基づき評価可能な条件を選び、その条件式それぞれの処理コストと検索結果数を予測し、その積が最小となる条件式から、評価を行っていく。条件式の処理コストとは、システムが検索で利用するインデックスにアクセスする上で関数を呼び出す上での初期の遅延と、条件ごとにかかる検索遅延、そして検索結果の内部処理にかかる遅延をさす。これらの遅延は、検索システムの動作する環境ごとに計測し、統計情報として処理に反映させる。また、検索結果数は、インデックスの先読みと、インデックスの統計情報に基づいた予測により求めた、条件を満たすＷｅｂページ数をさす。この条件を選択する操作と条件の評価を、未評価の条件が無くなるまで繰り返すことで、要求された問い合わせの条件を満たすＷｅｂページの系列を求める。
【００１５】処理コストと検索結果数の積が最小になる条件式とは、処理が高速にでき、かつその処理による検索空間の広がりを抑えられる条件式になる。これにより、従来システムの単純なアルゴリズムで問題となった処理時間の問題と検索空間の爆発を回避できる。
【００１６】また、この種の予測を利用した最適化手法では、手法自体の精度と処理コストが問題となる。最適化手法で用いる予測の精度は、随時検索の進行状況を反映させた予測を行うことで、正確な予測を行うことを可能にする。また、発明した方法では、データベースシステムの最適化で多く利用されている動的プログラミングのような、処理の順序の組合わせ問題を解決するような複雑な処理は行わない。単純な処理の逐次予測を行い、処理を進めていくので、最適化による問い合わせ処理自体への影響を小さく抑え、問い合わせ処理全体を高速なものにできる。
【００１７】
【発明の実施の形態】以下、図面を参照して本発明の実施の形態を詳細に説明する。
［実施形態１］図１に本発明の一実施形態の構成を示す。本発明に基づいたこの検索システムは、検索制御モジュール、Ｗｅｂモジュール、形態素解析器、ＧＩＳ、地理的ジェネリックリンク生成モジュール、位置情報データベース（ＰＯＩ−ＤＢ）、Ｗｅｂページ中の属性に関するインデックス（属性インデックス）、そしてハイパーリンクに関するインデックス（リンクインデックス）で構成される。なお本実施形態では、Ｗｅｂページから抽出した地理属性に基づきユーザの問い合わせ要求に応じてＷｅｂページ間に動的に生成するリンクのことを地理的ジェネリックリンクと呼ぶ。
【００１８】各モジュールは以下のように動作する。
・検索制御モジュールは、ユーザインタフェースからのクエリの受け付けと問い合わせ処理の実行、そして処理結果の出力を行う。問い合わせ処理を実行するために、検索制御モジュールは、Ｗｅｂモジュールおよび地理的ジェネリックリンク生成モジュールと連携し、クエリで指定された検索経路上のＷｅｂページの条件評価とリンクの展開を行う。また検索制御モジュールは、この問い合わせ処理を最適化するために、評価可能な条件式の選択と処理コスト及び検索結果数の予測を行い、その積が最小となる条件から処理を行う。
・Ｗｅｂモジュールは、検索制御モジュールからの指示に従い、Ｗｅｂページの属性に対する条件評価、ハイパーリンクの抽出、そして属性指定によるインデックスの検索を行う。
・地理的ジェネリックリンク生成モジュールは、検索制御モジュールからの指示に従い、Ｗｅｂページから抽出した地理的属性に基づき、Ｗｅｂページ間の地理的な関係を表す地理的ジェネリックリンクを生成する。
【００１９】各インデックスは、実際のインターネットから収集したＷｅｂページと実際の地理情報に基づいて構築する。図２に、Ｗｅｂページ中の属性に関するインデックス、およびハイパーリンクに関するインデックスの構築例を示す。Ｗｅｂページ中の属性に関するインデックスでは、Ｗｅｂページから抽出したタイトル、キーワード、住所等の属性とＵＲＬを関連づけて保存し、クエリに指定された属性条件を満たすＷｅｂページのＵＲＬを高速に検索できるようにする。この際、Ｗｅｂページのタイトルはページ中のＨＴＭＬタグを分析して抽出する。キーワード、住所は自然言語処理を行い抽出する。また、ハイパーリンクに関するインデックスでは、指定されたＷｅｂページのＵＲＬをキーとして、そのＷｅｂページからリンクしているリンク先ＷｅｂページのＵＲＬ、もしくはそのＷｅｂページへとリンクしているリンク元ＷｅｂページのＵＲＬを高速に検索できるようにする。
【００２０】Ｗｅｂページ間の地理的ジェネリックリンクは、リンクの起点となるＷｅｂページのＵＲＬに対応する地理的座標を検索し、求めた座標と指定された地理的関係にあるオブジェクトを検索し、そのオブジェクトに対応するＵＲＬを求めて生成する。このうち、ＷｅｂページのＵＲＬと地理的座標の対応付けには、図３に示すような、ＷｅｂページのＵＲＬとそのページの内容に対応する地理的なオブジェクトの座標を組にして格納したＰＯＩ−ＤＢを利用する。このＰＯＩ−ＤＢを利用することで、対応付けの高速化を図る。また図中の例では、地理座標の表現方法として緯度経度による座標系のみを利用しているが、本発明の手法はこの座標系に限定されない。インデックスの高速検索および地理座標間の関係演算の高速化のために、ＰＯＩ−ＤＢ中の地理座標系を統一する必要があるが、１つのＷｅｂページに対応する座標が必要に応じて複数の座標系で表現されていても良い。平面直角座標系やＷＧＳ−８４系など、複数の座標系間での相互変換を可能にする適切な変換関数を用いることにより、複数の座標系への対応を可能にする。なお、各インデックスに格納されるＵＲＬに付加情報を加えることにより、検索時の優先順位の設定や、検索の抑制・禁止を指定することも可能である。
【００２１】本検索システムでは、インターネット上に発信されている大量のＷｅｂページから、問い合わせで指定された条件に基づいてＷｅｂページの系列を検索する。この問い合わせは、以下の要素を組み合わせて指定する。
・検索経路Ｗｅｂページとハイパーリンク、および地理的ジェネリックリンクの組合わせにより、Ｗｅｂページの系列を検索するための経路を指定する。
・検索条件検索経路上に出現するＷｅｂページの属性に関する条件と、ハイパーリンクもしくは地理的ジェネリックリンクに関する条件を指定する。
・出力形式検索されたＷｅｂページの系列から、検索結果として出力する要素を指定する。
【００２２】このうち、検索条件として指定できる条件とその例を以下に示す。
（１）Ｗｅｂページから抽出した属性と定数を比較する条件・Ｗｅｂページp_1のＵＲＬを指定 → p_1.url eq 'http://www.aa.com/'・Ｗｅｂページp_1のＵＲＬの一部を指定 → P_1.url =〜/com/・Ｗｅｂページp_1のテキスト部に指定文字列が含まれる → P_1.text =〜/xxxx/・Ｗｅｂページp_1の住所に指定文字列が含まれる → P_1.address =〜/addr/（２）Ｗｅｂページ間のハイパーリンクに関する条件・Ｗｅｂページp_1とＷｅｂページp_2がハイパーリンクlinkで接続している →link AS HYPERLINK（３）Ｗｅｂページ間の地理的ジェネリックリンクに関する条件・Ｗｅｂページp_1とＷｅｂページp_2が地理的ジェネリックリンクlinkで接続している → link AS Distance(P_1,P_2) < 100（検索経路上でP_1とP_2がlinkで接続していて、かつ距離１００未満という条件で地理的ジェネリックリンクを生成する場合）
（４）Ｗｅｂページから抽出した属性間で比較を行う条件・指定された属性（attr）がＷｅｂページp_1とＷｅｂページp_2で一致 → P_1.attr eq P_2.attr
【００２３】なお、これら問い合わせに含まれる要素は論文（平松薫、石田亨、地域情報サービスのための拡張Ｗｅｂ空間、情報処理学会論文誌：データベース、Vol. 41,No. SIG6(TOD7), PP. 81-90, 2000）中で定義されているデータベース検索言語として一般的なＳＱＬを拡張Ｗｅｂ空間の検索に合わせて拡張した検索言語に対応するものであるが、下記の要素を含んでいれば、本実施形態の検索システムはＷｅｂページの系列の検索を実行することができる。従って、問い合わせを指定するための表現は、定義された検索言語に限定されるものではない。
【００２４】また、この問い合わせを生成するユーザインタフェースとしては、地図を使ったインタフェースや３次元仮想空間を利用したインタフェース、自然言語を用いたインタフェースなどが考えられるが、本実施形態の中では特に言及はしない。ユーザがこれらのユーザインタフェースを利用して入力した問い合わせが、上記の形式へと変換された後の問い合わせ処理についてのみ扱うものとする。
【００２５】入力された問い合わせの処理手順は以下のようになる。また、この処理の流れを図４に示す。
［１］問い合わせ処理に利用する各関数の予測処理コストとインデックスの統計値を取得する。
［２］入力された問い合わせを解析し、システム内の中間形式に変換する。この際、検索パス上のＷｅｂページの状態を全て未処理に設定する。
［３］条件式のうち、未評価でかつ評価可能な式それぞれについて処理コストと検索結果数を予測し、その積が最小となる条件式を選択して以下のように処理する。
［３．１］対象Ｗｅｂページが未処理、かつ条件式が属性条件によるＷｅｂページの選択の場合は、条件式による検索結果を全て登録し、対象となったＷｅｂページの状態を処理中にする。
［３．２］対象Ｗｅｂページが処理中、かつ条件式が属性条件によるＷｅｂページの選択の場合は、条件式による検索結果と既に登録されている検索結果を比較し、一致しなかった検索結果を登録から削除する。
［３．３］対象Ｗｅｂページが未処理、かつ条件式がリンクの展開の場合は、条件式によって得たリンク情報を全て登録し、対象となったＷｅｂページの状態を処理中にする。
［３．４］対象Ｗｅｂページが処理中、かつ条件式がリンクの展開の場合は、条件式によって得たリンク先とリンク先のＷｅｂページとして既に登録されている検索結果を比較し、一致しなかった検索結果とそのリンク情報を登録から削除する。
［４］未評価の条件式が無くなった検索パス上のＷｅｂページの状態を検索済に変更する。
［５］検索パス上の全てのＷｅｂページが処理済となったら登録された検索結果から指定された属性を出力して検索終了、それ以外の場合は［３］へ戻る。
【００２６】この処理手順中で利用する処理コストの予測式は、問い合わせに指定された条件を、問い合わせの進行状況に応じて、最適な順序で処理するために利用する。従来のデータベース管理システムの問い合わせ処理では、実際の処理を始める前に指定された条件の処理順序を最適化し、その順序に従って処理を進めるのが一般的である。これに対し、本発明の処理手順では、問い合わせ処理の進行にあわせて処理可能な条件の処理コストを予測し、場面場面で最適な条件を決定する。検索システムは、この予測に基づいた処理対象とする条件の決定と実際の条件処理を繰り返し、問い合わせ処理を進める。これにより、インターネット上のＷＷＷ情報空間を地理情報により拡張した拡張Ｗｅｂ空間に半構造性に対応する。表１に処理コストの予測式の詳細を示す。
【００２７】
【表１】
【００２８】まず、問い合わせ条件に関する予測式に含まれる定数について説明する。*_index_access_overheadは、条件を処理するためにインデックスを利用する際に関数の初期化に必要なオーバーヘッドを示す。*_index_access_costは、実際に条件を指定しインデックスを検索するためのコストである。CompCostは検索システム内で、変数間の比較処理を行うためのコストを表す。これらの定数は、検索システム内の処理時間に基づいたコストであり、動作環境および検索システムが利用する各種インデックスの状況によって変化する。従って、検索システムが起動時に自動的に調査取得、もしくは同じ環境で調査取得して保存してある値を利用する。
【００２９】次に、予測式に含まれる変数について説明する。｜Ｐｎ｜は、それまでに行った問い合わせ処理の中間結果の中で、条件の対象となっているＷｅｂページＰｎに対応する中間結果として登録されているＷｅｂページ数を表す。｜estimation_result｜は、条件の処理により得られるであろう検索結果数の予測を表す。このうち｜estimation_result｜は、処理対象となっている属性のインデックスから条件に合致するデータ数のみを取得、もしくは属性の値の分布を表したヒストグラムと条件に合致する値の区間の関係を利用したデータ数の予測（Gregory Piatetsky-Shapiro and Charles Connnell. Accutrate estimation of the numberof tuples satisfying a condition. In Proceedings of 1984 ACM-SIGMOD Conference on the Managemente of Data, pp. 256-276, 1984）により求める。
【００３０】表１の問い合わせの条件は、先に述べた検索条件（１）〜（４）に対応する。なお、条件式中のｏｐｅｒａｔｏｒは、ｅｑ（等しい）などの２項間の比較演算子、＝〜（含んでいる）などのパターンマッチ演算子を示す。これらの記号は、プログラミング言語Ｐｅｒｌで用いられている演算子と同等である。
【００３１】問い合わせの条件のうち（１）〜（３）は、条件の対象となっている検索経路上のＷｅｂページが、それまでに処理の対象となったか否かによって、利用する予測式が異なる。（１）のＷｅｂページの属性と定数の比較の処理コストは、属性に関するインデックスを利用する際の関数の初期化に必要なコスト（予測式１行目）と、指定された値のインデックス検索を行うためのコスト（予測式２行目）と、検索結果の後処理に必要なコスト（予測式３行目）を足しあわせて予測する。このうち後処理に必要なコストは、条件の対象となっている検索経路上のＷｅｂページが、それまでに処理の対象となっていない場合は、条件の処理結果を中間結果としてシステム内の記憶領域へ登録するためのコストを加える。この時、条件の処理結果得られるＷｅｂページ数はインデックスを利用して予測する。また、Ｗｅｂページが既に処理対象となっていた場合は、登録されている中間結果と新たに得られた結果で一致している結果のみを中間結果に残すため、双方の比較に必要なコストを予測コストに加える。
【００３２】（２）のハイパーリンクの展開、および（３）の地理的ジェネリックリンクの展開は、リンクの起点となるＷｅｂページの中間結果が得られた時点で処理可能となり、処理コストを予測対象となる。予測式は、ほぼ（１）の予測式と同様であるが、各予測式の２行目でリンクに関するインデックス検索を行うコストを求める際、インデックス検索コストに条件の起点となっているＷｅｂページに対応する中間結果数をかけ、コストを予測する。また、ハイパーリンクに関する条件の場合は、順方向のリンク展開と逆方向のリンク展開の双方を考慮にいれる。（４）のＷｅｂページ間で属性を比較は、条件の対象となるＷｅｂページ双方の中間結果が得られた段階で評価可能となる。この操作の処理コストの予測は、対象となるＷｅｂページ数の和に比較処理コストをかけて求める。
【００３３】まず、コスト予測を利用した処理の最適化手順を示すために、図５に示した簡単な問い合わせ例の処理手順を説明する。図中の楕円でＰ１等記入されているのが、問い合わせで検索するＷｅｂページを示し、説明ではノードと呼ぶ。また、ノード間の矢印がリンクを示し、矢印の説明として記述されている“hyperlink”や“Distance”がそのリンクに関する条件を表す。
【００３４】この例では、ＵＲＬがhttp://www.aa.com/であるノードＰ１からハイパーリンクしているＷｅｂページで、かつ本文中に「支店」という文字列を含むノードＰ２を検索し、その系列を出力するというものである。この例ではＵＲＬの指定によりＰ１を確定した後、Ｐ１からハイパーリンクしているノードを検索するか、本文中に「支店」という文字列を含むノードを検索するかを、処理の予測コストの大小により決定する。この予測コストの大小は、時間に基づいた処理コストと処理結果の積で決まるので、処理時間が短く、かつ条件処理によって得られる結果が少ない場合に予測コストが小さくなる。すなわち、問い合わせ処理を進める上で、処理に時間が係らない条件で、かつ処理の結果、検索空間が大きくならない場合に予測コストが小となる。
【００３５】もし、ハイパーリンク条件の処理の方が予測コストが小さい場合、図の左側の処理となる。この場合は、Ｐ１からハイパーリンクで接続しているノードをハイパーリンクに関するインデックスを利用して求め、求めたノードの中からＷｅｂページの属性に関する条件である文字列「支店」を含むものを選択する。また、Ｗｅｂページの属性に関する条件の処理の方が予測コストが小さい場合は、図の右側の処理となる、こちらの場合は、Ｗｅｂページの属性に関する条件である文字列「支店」を含むノードを、Ｗｅｂページの本文中のキーワードに関するインデックスを利用して検索し、その後、検索したノードの中からＰ１とハイパーリンクで接続しているノードを求める。
【００３６】いずれの場合も処理結果は同じであるが、問い合わせ処理中の途中結果の大きさは、Ｐ１からハイパーリンクで接続しているＷｅｂページの数、およびＰ２の属性条件として指定された「支店」という文字列を含むＷｅｂページの数によって大きく左右される。この途中の検索空間を小さく抑えることで、システム内部の比較処理回数等を削減することができ、最終的には高速な問い合わせ処理が可能となる。
【００３７】次に、本実施形態を用いたより具体的な問い合わせ処理の最適化例を示すために、図６の例について説明する。この問い合わせでは、指定されたリンク集を起点にハイパーリンクをたどり、Ｗｅｂページの属性に関する条件と、地理的ジェネリックリンクに関する条件を組み合わせて、Ｗｅｂページの系列を検索する。問い合わせは、起点となるリンク集に対応するノードＰ１から、目的のＷｅｂページに対応するノードＰ４までが、ノードとリンクの繰り返しによる検索パスによって指定する。なお、バス停と喫茶店については、Ｗｅｂページ上の記述から検索できるものとして説明を進める。
【００３８】ちなみに、この例の問い合わせを文章で記述すると以下のようになる。「イタリア料理店を紹介するリンク集」で紹介されているお店から、「パスタ」に関する記述のあるＷｅｂページを選び、そのお店から、５００ｍ以内にあるバス停を検索し、そのバス停からさらに５００ｍ以内にある「コーヒー」を出す喫茶店を検索する。
【００３９】次に、この問い合わせ例の中の条件の処理順序について説明する。図７が最適化なしの場合の条件の処理順序、図８が最適化ありの場合の条件の処理順序であり、図中の括弧付の数字は、問い合わせ例の中で指定された条件の処理順序を表す。この処理順序を最適化ありの場合となしの場合で比較すると、ＵＲＬの指定に基づいた検索の起点Ｐ１の確定と、ハイパーリンクに関するインデックスを利用したＰ１からＰ２へのハイパーリンクの展開の２番目の処理までは同じ順序で行われた。しかし、３番目以降の処理順序には差が見られた。最適化なしの場合は、問い合わせに指定された順序に従って、条件処理が進んだのに対し、最適化ありの場合は、ノードＰ４、Ｐ２、Ｐ３のＷｅｂページの属性に関する条件が、Ｗｅｂページのテキスト部に出現する語句に関するインデックスを利用して先に処理され、その後、ノード間の地理的ジェネリックリンクに関する条件がＰＯＩ−ＤＢと地理的関係演算により処理された。
【００４０】この問い合わせ処理中にシステム内部で行われた比較処理回数（図９）を見てみると、問い合わせ処理の３番目と５番目に大きな差が見られ、最適化により属性に関する条件を先に評価し、その後リンクを展開することで、システム内部の比較回数が削減された事がわかる。従って、問い合わせ例の処理では、処理の前半に検索パス上のノードに対応するＷｅｂページの選択を行い、その後Ｗｅｂページ間のリンク関係を検証する手順を最適化により選択することで、問い合わせ処理の高速化ができた。
【００４１】本実施形態は、上記のような手法で実装する検索システムに関するものであるが、下記に挙げたユーザが利用する端末の形態、検索システムの設置形態、検索システムの利用形態、および利用するネットワークの形態のいずれを組合わせた場合も、実施形態の検索システムは入力された問い合わせを高速に処理することができる。
・ユーザが利用する端末の形態：デスクトップコンピュータ、携帯型コンピュータ、ＰＤＡ、ノート型コンピュータ、ウェアラブルコンピュータ、携帯電話、固定電話、公衆電話、カーナビゲーションシステム、街頭端末。
【００４２】・検索システムの設置形態：インターネットで公開されているコンピュータへの検索システムの設置。インターネットに公開されていない内部利用を目的とするコンピュータへの検索システムの設置。ネットワークに接続されていないが電話網、携帯電話網と接続するモデムを有するコンピュータへの検索システムの設置。ネットワーク及び電話網と独立し、単独で動作するコンピュータへの検索システムの設置。（上記の単独動作以外の場合は、検索システムを構成するモジュールを一台のコンピュータ上で集中的に動作しなければならないという制限はなく、複数のコンピュータに分散させることも可能）
【００４３】・検索システムの利用形態：穴埋め式フォームからの入力受け付けと、木構造表示、地図もしくは仮想空間を利用した２次元もしくは３次元的な表示の一つ以上の表示方法を組み合わせた検索結果表示。穴埋め式フォームからの条件入力と、検索可能な項目の木構造表示、地図もしくは仮想空間を利用した２次元もしくは３次元的な検索可能な項目の表示を一つ以上組合わせた問い合わせ入力と、それに対応した検索結果表示。上記の複数の入出力手法に、音声による条件入力及び検索結果出力を加えた複数の入出力方法から、一つ以上を組み合わせた利用形態。
・利用するネットワークの形態：無線接続もしくは有線接続、また常時接続もしくはダイアルアップ接続。
【００４４】［実施形態２］実施形態１の地理的ジェネリックリンク生成モジュールと同様に、Ｗｅｂページから抽出した語句の類似性など、Ｗｅｂページの自然言語属性の関連性によって動的にリンクを生成するモジュールを問い合わせ処理に利用する。このモジュールは、Ｗｅｂページから抽出した属性と抽出元であるＷｅｂページのＵＲＬを格納した自然言語属性ＤＢと、シソーラスもしくは辞書に基づき属性間の類似性を評価するための関数により、Ｗｅｂページ間にリンクを生成する。たとえば、以下のような語句の類似性に基づきＷｅｂページ間に動的にリンクを生成する。
・リンク元Ｗｅｂページの指定語句と同じ語句を含む。
・リンク元Ｗｅｂページの指定語句の類義語を含む。
この自然言語属性の関連性によって動的にリンクを生成するモジュール以外の検索システムの構成、検索手順、および利用形態は実施形態１と同様である。
【００４５】［実施形態３］実施形態１の地理的ジェネリックリンク生成モジュールの代わりに、Ｗｅｂページから抽出した属性、Ｗｅｂサーバ名、Ｗｅｂページのアドレス、ＵＲＬ、ＨＴＭＬタグ、ハイパーリンクの関連性により、動的に生成するモジュールを利用する。このモジュールは、抽出した属性と抽出元であるＷｅｂページのＵＲＬを格納したＷｅｂページ属性ＤＢと、属性間の類似性を評価するための関数により、Ｗｅｂページ間にリンクを生成する。
【００４６】たとえば、以下のような属性の類似性に基づきＷｅｂページ間に動的にリンクを生成する。
・リンク元Ｗｅｂページの保存されているサーバと同じサーバに保存されている（サーバアドレスの完全一致）。
・リンク元Ｗｅｂページの保存されているサーバと同じドメインに属するサーバに保存されている（サーバアドレスの部分一致）。
・リンク元Ｗｅｂページが保存されているＷｅｂサーバ上のディレクトリと同じディレクトリに保存されている。
・リンク元Ｗｅｂページが保存されているＷｅｂサーバ上のディレクトリに含まれる下位ディレクトリに保存されている。
・リンク元Ｗｅｂページが保存されているＷｅｂサーバ上のディレクトリの上位ディレクトリに保存されている。
・リンク元Ｗｅｂページと同種のタグ（たとえば、イメージタグ、表、箇条書き）を含んでいる。
・リンク元Ｗｅｂページ中のハイパーリンク先と同じリンク先を含んでいる。
【００４７】この、サーバ名、Ｗｅｂページのアドレスなど、Ｗｅｂページから抽出した属性の関連性によりリンクを動的に生成するモジュール以外の検索システムの構成、検索手順、および利用形態は実施形態１と同様である。
【００４８】［実施形態４］実施形態１から実施形態３で示した動的なリンクを生成するモジュールを一つ以上組み合わせて実施できる検索システム。
【００４９】以上、本発明者によってなされた発明を、前記実施の形態に基づき具体的に説明したが、本発明は、前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【００５０】
【発明の効果】以上述べたように本発明によれば、Ｗｅｂページの系列を検索する問い合わせを高速に処理することを可能にするという効果が得られる。この問い合わせとは、Ｗｅｂページから抽出した属性に関する条件と、Ｗｅｂページ間のハイパーリンクに関する条件と、Ｗｅｂページから抽出した属性の関連性を利用して動的に生成するＷｅｂページ間のリンクに関する条件を組み合わせ問い合わせたものである。また処理には、抽出した属性に関するインデックスとリンクを生成するためのインデックスを利用し、問い合わせ中の条件の処理コストと検索結果数の予測の積が最小となる条件から処理を進め、問い合わせの高速処理を可能にする。
【図面の簡単な説明】
【図１】本発明の一実施形態を示す図である。
【図２】検索システムで利用するインデックスの構築例を示す図である。
【図３】ＰＯＩ−ＤＢの構築例を示す図である。
【図４】問い合わせ処理手順を示す図である。
【図５】コスト予測による処理条件の選択例を示す図である。
【図６】問い合わせ例の検索パスを示す図である。
【図７】最適化なしの場合の検索順序を示す図である。
【図８】最適化ありの場合の検索順序を示す図である。
【図９】検索システム内部の累積比較回数を示す図である。
【０００１】
【発明の属する技術分野】本発明は、出願中の特許「ホームページの系列的検索方法、および装置、記録媒体（特願２０００−１６２６５８）」で発明された検索方法を高速に行うための発明である。
【０００２】インターネット上に発信されているＷｅｂページは、年々増加しており、特に都市部においては、地理的にも集中する傾向にある。このため、現在インターネット上で公開されているキーワード検索やディレクトリサービスだけでは、必要な情報を短時間で検索することは困難になりつつある。この問題を解決する手法の一つとして、複数の条件を組み合わせて、Ｗｅｂページを系列として検索する手法が考えられる。この系列を検索するための方法は、特願２０００−１６２６５８にて発明されているが、その検索を高速に実施する方法は発明されていなかった。
【０００３】Ｗｅｂページ系列の検索では、Ｗｅｂページの属性に関する条件と、Ｗｅｂページ間のリンクに関する条件を複数組み合わせて、問い合わせを指定することができる。例えば、類似する情報が複数あるときに、Ｗｅｂページ間のハイパーリンク関係に基づいて有名なリンク集からリンクされているＷｅｂページを選択したり、Ｗｅｂページから抽出した地理属性に基づき、一定距離以内にある情報という形で条件を指定し、リンク先を検索することができる。
【０００４】この問い合わせの処理するためには、大量のＷｅｂページとそこから抽出した属性を評価する必要があり、その検索空間が膨大となるため、幅優先探索アルゴリズムなど、従来の単純なアルゴリズムでは、現実的な時間で問い合わせを処理することはできなかった。本出願で発明する高速化手法では、検索対象となる情報に関する各種インデックスを利用し、その問い合わせ中の条件の評価順序を最適化し、高速に問い合わせ処理を可能にする。
【０００５】このＷｅｂページの系列に関する問い合わせが高速に処理できるようになると、従来のキーワード指定によるＷｅｂページの検索を、リンクに関する条件も含め複数の条件の指定による検索へと拡張することができる。この場合、検索サービスの利用者が、直接条件項目を指定することになるが、その問い合わせの入力方法を変えることで、文章や音声など自然言語による情報検索や、グラフィックユーザインタフェース（ＧＵＩ）を利用したインタラクティブな情報検索にも適用可能である。また、問い合わせの結果がＷｅｂページの系列となるので、その系列をリスト形式で出力したり、直接図示したり、カーナビゲーションのように必要に応じて、順序だててＷｅｂページを提示することも可能になる。このように、問い合わせの検索結果は、現在のカーナビゲーションや将来の携帯端末や街頭端末を使った歩行者ナビゲーションなどに応用可能であり、その処理を高速化することにより、ユーザから見た使い勝手を向上させることができる。
【０００６】
【従来の技術】インターネット上に存在する膨大な情報から、都市に関連したものを抽出するためには検索機能が必須である。ユーザが検索機能を直接利用する場合は、キーワード指定による検索が便利ではあるが、その検索結果に意図しない結果が大量に含まれるなど、その結果に対する信頼性には問題があった。
【０００７】こうした問題を解決する手法の一つとして、キーワードなどＷｅｂページの属性やハイパーリンク関係など複数の条件を指定して、Ｗｅｂページを系列として検索する手法が考えられる。これにより、例えばキーワードレベルだけで検索されていた意図されていなかった結果を排除することができる。
【０００８】こうしたＷｅｂページの系列を検索するための方法の一つとしてＷｅｂ空間を対象とした検索言語がある。この検索言語には、リンク構造とコンテンツに関する条件の指定により検索を行うＷ３ＱＬ（David Konopnicki and Oded Shmueli.W3QS: A Query System for the World-Wide Web. In Proceedings of the 21stInternational Conference on Very Large Data Bases, pp.54-65, 1995、David Konopllicki and Oded Shmueli. Information Gathering in the World WideWeb: The W3QL Query Language and the W3QS System. ACM Transactions on Database Systems, Vol. 23, No. 4, pp. 369-410, 1998）やＷｅｂＳＱＬ（Alberto O. Mendelzon, George A. Mihaila, and Tova Milo. Querying the World Wide Web. International Journal on Digital Libraries, Vol. 1, No. 1, pp. 54-67, 1997、Alberto O. Mendelzon and Tova Milo. Formal Models of Web Queries. In Proceedings of the 16th ACM Symposium on Principles of DatabaseSystems, pp. 134-143, 1997）、Ｗｅｂページの構造に関する条件指定や検索結果の再構成が可能なＷｅｂＯＱＬ（Gustavo O. Arocena and Alberto O. Mendelzon. Weboql: Restructuring Documents, Databases, and Webs. In Proceedings of ICDE, pp. 24-33. 1998）、ＳｔｒｕＱＬ（Mary Fernandez, Daniela Florescu, Alon Levy, and Dan Suciu. A Query Language for a Web-Site Management System. SIGMOD Record, Vol. 26, No. 3, pp. 4-11, 1997）がある。Ｗｅｂ情報を対象とした検索言語はＸＭＬの標準化と密接に関連する領域でもある。
【０００９】一方、電子化した都市情報を地図と関連づけて扱うためのシステムとしては、地理情報システム（ＧＩＳ）がある。従来ＧＩＳは単独の計算機で用いられることが多かったが、近年のネットワークとパソコンの普及により、多様な利用形態が可能な数多くの製品が発表されてきている。ＷｅｂＧＩＳなどインターネットへの広がりもその一つと考えられ、将来的には、インターネット上のコンテンツと密接に関わりを持つ可能性も持っている。現在の段階では、情報の位置を地図上に表示するようなサービスが公開されているが、特願２０００−１６２６５８のようなＷｅｂページの系列を検索するようなサービスはまだ行われていないと理解している。
【００１０】特願２０００−１６２６５８の発明は、その検索空間を拡張Ｗｅｂ空間（平松薫、石田亨、地域情報サービスのための拡張Ｗｅｂ空間、情報処理学会論文誌：データベース、Vol. 41, No. SIG6(TOD7), PP. 81-90, 2000）とし、その情報空間を半構造データ（Serge Abiteboul. Querying Semi-Structured Data. In Database Theory - ICDT '97, 6th, International Conference, pp. 1-18, 1997、田島敬史、半構造データのためのデータモデルと操作言語、情報処理学会論文誌:データベース、Vol. 40, No. SIG 3(TOD 1), pp. 152-170, 1999）として捉えている。半構造データを対象としたデータベースシステム（ＤＢＭＳ）の一つに、スタンフォード大学で開発されたＬｏｒｅがある。Ｌｏｒｅでは、ＸＭＬに代表される半構造データに特化した各種インデックスを導入（Roy Goldman and Jennifer Widom. DataGuide: Enabling Query Formulation and Optimization inSemistructured Databases. In Proceedings of the 23rd International Conference on Very Large Data Bases, pp. 436-445, 1997）し、その問い合わせ処理にはコスト予測を導入して最適化を実現している（Jason McHugh and Jennifer Widom. Query Optimization for XML. In Proceedings of the 25th International Conference on Very Large Data Bases, pp. 315-326, 1999）。本発明の手法は、Ｌｏｒｅの手法と非常に良く似ているが、最大の差は、対象とした検索空間の具体性にある。本発明では、実際の都市における情報に基づいた拡張Ｗｅｂ空間を検索対象とし、その問い合わせを最適化するために、条件の評価順序の決定方法を特化させている。また、検索システムで利用するインデックスの構築をＷｅｂページとＧＩＳを用いて作成し、最適化手法の有効性なものにしている。
【００１１】このインデックスの構築は、Ｗｅｂ情報のキャッシュを行うプロキシや、その関連プロトコル、ＧＩＳとＷｅｂ情報を関連づけるためのアドレスマッチングなどと関連するものである。本発明では、インデックスの効率的な構築や更新は考慮にいれていないが、問い合わせ処理の最適化と合わせて、拡張Ｗｅｂ空間に基づく検索システムの周辺技術として連携させる必要がある。
【００１２】
【発明が解決しようとする課題】本発明は、特願平１１−１４９１００（特開２０００−３３９３３０号公報）および特願２０００−１６２６５８から発想したものであり、これまでに発明したＷｅｂページの系列を検索する方法を高速化するためのものである。これまでに発明してきたＷｅｂページの系列の検索では、大量のＷｅｂページとそこから抽出した属性を評価する必要がある。その検索空間が膨大となるため、これまでの発明で用いた幅優先探索アルゴリズムなど、単純なアルゴリズムでは、検索自体は可能なものの、現実的な時間で問い合わせを処理することはできなかった。この処理時間の問題により、これまでの方法に基づき作製したシステムは、旅行計画やナビゲーション用のコンテンツの作成など、問い合わせに基づく検索結果をあらかじめ構築してそれを公開するような、間接的な利用に限られていた。
【００１３】
【課題を解決するための手段】前節で述べた処理時間による制限をなくすため、本出願ではその高速化手法を発明する。高速化手法では、検索対象となるＷｅｂページから抽出したキーワードやハイパーリンクなどの属性情報に関する各種インデックス、問い合わせに応じて抽出した属性間の関連性に基づきＷｅｂページ間のリンクを動的に生成するためのインデックスを利用し、問い合わせ処理を進めていく。インデックスは、実際のＷｅｂページをＷｅｂロボットで収集し、自然言語処理やアドレスマッチング等を行って作成する。
【００１４】問い合わせに含まれる複数の条件は、これらインデックスを利用して評価されるが、単純なアルゴリズムでは、従来システムと同様、検索空間が爆発する可能性がある。そこで、問い合わせを進めていく上で、逐次、指定された条件で未評価のものから条件間の依存関係に基づき評価可能な条件を選び、その条件式それぞれの処理コストと検索結果数を予測し、その積が最小となる条件式から、評価を行っていく。条件式の処理コストとは、システムが検索で利用するインデックスにアクセスする上で関数を呼び出す上での初期の遅延と、条件ごとにかかる検索遅延、そして検索結果の内部処理にかかる遅延をさす。これらの遅延は、検索システムの動作する環境ごとに計測し、統計情報として処理に反映させる。また、検索結果数は、インデックスの先読みと、インデックスの統計情報に基づいた予測により求めた、条件を満たすＷｅｂページ数をさす。この条件を選択する操作と条件の評価を、未評価の条件が無くなるまで繰り返すことで、要求された問い合わせの条件を満たすＷｅｂページの系列を求める。
【００１５】処理コストと検索結果数の積が最小になる条件式とは、処理が高速にでき、かつその処理による検索空間の広がりを抑えられる条件式になる。これにより、従来システムの単純なアルゴリズムで問題となった処理時間の問題と検索空間の爆発を回避できる。
【００１６】また、この種の予測を利用した最適化手法では、手法自体の精度と処理コストが問題となる。最適化手法で用いる予測の精度は、随時検索の進行状況を反映させた予測を行うことで、正確な予測を行うことを可能にする。また、発明した方法では、データベースシステムの最適化で多く利用されている動的プログラミングのような、処理の順序の組合わせ問題を解決するような複雑な処理は行わない。単純な処理の逐次予測を行い、処理を進めていくので、最適化による問い合わせ処理自体への影響を小さく抑え、問い合わせ処理全体を高速なものにできる。
【００１７】
【発明の実施の形態】以下、図面を参照して本発明の実施の形態を詳細に説明する。
［実施形態１］図１に本発明の一実施形態の構成を示す。本発明に基づいたこの検索システムは、検索制御モジュール、Ｗｅｂモジュール、形態素解析器、ＧＩＳ、地理的ジェネリックリンク生成モジュール、位置情報データベース（ＰＯＩ−ＤＢ）、Ｗｅｂページ中の属性に関するインデックス（属性インデックス）、そしてハイパーリンクに関するインデックス（リンクインデックス）で構成される。なお本実施形態では、Ｗｅｂページから抽出した地理属性に基づきユーザの問い合わせ要求に応じてＷｅｂページ間に動的に生成するリンクのことを地理的ジェネリックリンクと呼ぶ。
【００１８】各モジュールは以下のように動作する。
・検索制御モジュールは、ユーザインタフェースからのクエリの受け付けと問い合わせ処理の実行、そして処理結果の出力を行う。問い合わせ処理を実行するために、検索制御モジュールは、Ｗｅｂモジュールおよび地理的ジェネリックリンク生成モジュールと連携し、クエリで指定された検索経路上のＷｅｂページの条件評価とリンクの展開を行う。また検索制御モジュールは、この問い合わせ処理を最適化するために、評価可能な条件式の選択と処理コスト及び検索結果数の予測を行い、その積が最小となる条件から処理を行う。
・Ｗｅｂモジュールは、検索制御モジュールからの指示に従い、Ｗｅｂページの属性に対する条件評価、ハイパーリンクの抽出、そして属性指定によるインデックスの検索を行う。
・地理的ジェネリックリンク生成モジュールは、検索制御モジュールからの指示に従い、Ｗｅｂページから抽出した地理的属性に基づき、Ｗｅｂページ間の地理的な関係を表す地理的ジェネリックリンクを生成する。
【００１９】各インデックスは、実際のインターネットから収集したＷｅｂページと実際の地理情報に基づいて構築する。図２に、Ｗｅｂページ中の属性に関するインデックス、およびハイパーリンクに関するインデックスの構築例を示す。Ｗｅｂページ中の属性に関するインデックスでは、Ｗｅｂページから抽出したタイトル、キーワード、住所等の属性とＵＲＬを関連づけて保存し、クエリに指定された属性条件を満たすＷｅｂページのＵＲＬを高速に検索できるようにする。この際、Ｗｅｂページのタイトルはページ中のＨＴＭＬタグを分析して抽出する。キーワード、住所は自然言語処理を行い抽出する。また、ハイパーリンクに関するインデックスでは、指定されたＷｅｂページのＵＲＬをキーとして、そのＷｅｂページからリンクしているリンク先ＷｅｂページのＵＲＬ、もしくはそのＷｅｂページへとリンクしているリンク元ＷｅｂページのＵＲＬを高速に検索できるようにする。
【００２０】Ｗｅｂページ間の地理的ジェネリックリンクは、リンクの起点となるＷｅｂページのＵＲＬに対応する地理的座標を検索し、求めた座標と指定された地理的関係にあるオブジェクトを検索し、そのオブジェクトに対応するＵＲＬを求めて生成する。このうち、ＷｅｂページのＵＲＬと地理的座標の対応付けには、図３に示すような、ＷｅｂページのＵＲＬとそのページの内容に対応する地理的なオブジェクトの座標を組にして格納したＰＯＩ−ＤＢを利用する。このＰＯＩ−ＤＢを利用することで、対応付けの高速化を図る。また図中の例では、地理座標の表現方法として緯度経度による座標系のみを利用しているが、本発明の手法はこの座標系に限定されない。インデックスの高速検索および地理座標間の関係演算の高速化のために、ＰＯＩ−ＤＢ中の地理座標系を統一する必要があるが、１つのＷｅｂページに対応する座標が必要に応じて複数の座標系で表現されていても良い。平面直角座標系やＷＧＳ−８４系など、複数の座標系間での相互変換を可能にする適切な変換関数を用いることにより、複数の座標系への対応を可能にする。なお、各インデックスに格納されるＵＲＬに付加情報を加えることにより、検索時の優先順位の設定や、検索の抑制・禁止を指定することも可能である。
【００２１】本検索システムでは、インターネット上に発信されている大量のＷｅｂページから、問い合わせで指定された条件に基づいてＷｅｂページの系列を検索する。この問い合わせは、以下の要素を組み合わせて指定する。
・検索経路Ｗｅｂページとハイパーリンク、および地理的ジェネリックリンクの組合わせにより、Ｗｅｂページの系列を検索するための経路を指定する。
・検索条件検索経路上に出現するＷｅｂページの属性に関する条件と、ハイパーリンクもしくは地理的ジェネリックリンクに関する条件を指定する。
・出力形式検索されたＷｅｂページの系列から、検索結果として出力する要素を指定する。
【００２２】このうち、検索条件として指定できる条件とその例を以下に示す。
（１）Ｗｅｂページから抽出した属性と定数を比較する条件・Ｗｅｂページp_1のＵＲＬを指定 → p_1.url eq 'http://www.aa.com/'・Ｗｅｂページp_1のＵＲＬの一部を指定 → P_1.url =〜/com/・Ｗｅｂページp_1のテキスト部に指定文字列が含まれる → P_1.text =〜/xxxx/・Ｗｅｂページp_1の住所に指定文字列が含まれる → P_1.address =〜/addr/（２）Ｗｅｂページ間のハイパーリンクに関する条件・Ｗｅｂページp_1とＷｅｂページp_2がハイパーリンクlinkで接続している →link AS HYPERLINK（３）Ｗｅｂページ間の地理的ジェネリックリンクに関する条件・Ｗｅｂページp_1とＷｅｂページp_2が地理的ジェネリックリンクlinkで接続している → link AS Distance(P_1,P_2) < 100（検索経路上でP_1とP_2がlinkで接続していて、かつ距離１００未満という条件で地理的ジェネリックリンクを生成する場合）
（４）Ｗｅｂページから抽出した属性間で比較を行う条件・指定された属性（attr）がＷｅｂページp_1とＷｅｂページp_2で一致 → P_1.attr eq P_2.attr
【００２３】なお、これら問い合わせに含まれる要素は論文（平松薫、石田亨、地域情報サービスのための拡張Ｗｅｂ空間、情報処理学会論文誌：データベース、Vol. 41,No. SIG6(TOD7), PP. 81-90, 2000）中で定義されているデータベース検索言語として一般的なＳＱＬを拡張Ｗｅｂ空間の検索に合わせて拡張した検索言語に対応するものであるが、下記の要素を含んでいれば、本実施形態の検索システムはＷｅｂページの系列の検索を実行することができる。従って、問い合わせを指定するための表現は、定義された検索言語に限定されるものではない。
【００２４】また、この問い合わせを生成するユーザインタフェースとしては、地図を使ったインタフェースや３次元仮想空間を利用したインタフェース、自然言語を用いたインタフェースなどが考えられるが、本実施形態の中では特に言及はしない。ユーザがこれらのユーザインタフェースを利用して入力した問い合わせが、上記の形式へと変換された後の問い合わせ処理についてのみ扱うものとする。
【００２５】入力された問い合わせの処理手順は以下のようになる。また、この処理の流れを図４に示す。
［１］問い合わせ処理に利用する各関数の予測処理コストとインデックスの統計値を取得する。
［２］入力された問い合わせを解析し、システム内の中間形式に変換する。この際、検索パス上のＷｅｂページの状態を全て未処理に設定する。
［３］条件式のうち、未評価でかつ評価可能な式それぞれについて処理コストと検索結果数を予測し、その積が最小となる条件式を選択して以下のように処理する。
［３．１］対象Ｗｅｂページが未処理、かつ条件式が属性条件によるＷｅｂページの選択の場合は、条件式による検索結果を全て登録し、対象となったＷｅｂページの状態を処理中にする。
［３．２］対象Ｗｅｂページが処理中、かつ条件式が属性条件によるＷｅｂページの選択の場合は、条件式による検索結果と既に登録されている検索結果を比較し、一致しなかった検索結果を登録から削除する。
［３．３］対象Ｗｅｂページが未処理、かつ条件式がリンクの展開の場合は、条件式によって得たリンク情報を全て登録し、対象となったＷｅｂページの状態を処理中にする。
［３．４］対象Ｗｅｂページが処理中、かつ条件式がリンクの展開の場合は、条件式によって得たリンク先とリンク先のＷｅｂページとして既に登録されている検索結果を比較し、一致しなかった検索結果とそのリンク情報を登録から削除する。
［４］未評価の条件式が無くなった検索パス上のＷｅｂページの状態を検索済に変更する。
［５］検索パス上の全てのＷｅｂページが処理済となったら登録された検索結果から指定された属性を出力して検索終了、それ以外の場合は［３］へ戻る。
【００２６】この処理手順中で利用する処理コストの予測式は、問い合わせに指定された条件を、問い合わせの進行状況に応じて、最適な順序で処理するために利用する。従来のデータベース管理システムの問い合わせ処理では、実際の処理を始める前に指定された条件の処理順序を最適化し、その順序に従って処理を進めるのが一般的である。これに対し、本発明の処理手順では、問い合わせ処理の進行にあわせて処理可能な条件の処理コストを予測し、場面場面で最適な条件を決定する。検索システムは、この予測に基づいた処理対象とする条件の決定と実際の条件処理を繰り返し、問い合わせ処理を進める。これにより、インターネット上のＷＷＷ情報空間を地理情報により拡張した拡張Ｗｅｂ空間に半構造性に対応する。表１に処理コストの予測式の詳細を示す。
【００２７】
【表１】
【００２８】まず、問い合わせ条件に関する予測式に含まれる定数について説明する。*_index_access_overheadは、条件を処理するためにインデックスを利用する際に関数の初期化に必要なオーバーヘッドを示す。*_index_access_costは、実際に条件を指定しインデックスを検索するためのコストである。CompCostは検索システム内で、変数間の比較処理を行うためのコストを表す。これらの定数は、検索システム内の処理時間に基づいたコストであり、動作環境および検索システムが利用する各種インデックスの状況によって変化する。従って、検索システムが起動時に自動的に調査取得、もしくは同じ環境で調査取得して保存してある値を利用する。
【００２９】次に、予測式に含まれる変数について説明する。｜Ｐｎ｜は、それまでに行った問い合わせ処理の中間結果の中で、条件の対象となっているＷｅｂページＰｎに対応する中間結果として登録されているＷｅｂページ数を表す。｜estimation_result｜は、条件の処理により得られるであろう検索結果数の予測を表す。このうち｜estimation_result｜は、処理対象となっている属性のインデックスから条件に合致するデータ数のみを取得、もしくは属性の値の分布を表したヒストグラムと条件に合致する値の区間の関係を利用したデータ数の予測（Gregory Piatetsky-Shapiro and Charles Connnell. Accutrate estimation of the numberof tuples satisfying a condition. In Proceedings of 1984 ACM-SIGMOD Conference on the Managemente of Data, pp. 256-276, 1984）により求める。
【００３０】表１の問い合わせの条件は、先に述べた検索条件（１）〜（４）に対応する。なお、条件式中のｏｐｅｒａｔｏｒは、ｅｑ（等しい）などの２項間の比較演算子、＝〜（含んでいる）などのパターンマッチ演算子を示す。これらの記号は、プログラミング言語Ｐｅｒｌで用いられている演算子と同等である。
【００３１】問い合わせの条件のうち（１）〜（３）は、条件の対象となっている検索経路上のＷｅｂページが、それまでに処理の対象となったか否かによって、利用する予測式が異なる。（１）のＷｅｂページの属性と定数の比較の処理コストは、属性に関するインデックスを利用する際の関数の初期化に必要なコスト（予測式１行目）と、指定された値のインデックス検索を行うためのコスト（予測式２行目）と、検索結果の後処理に必要なコスト（予測式３行目）を足しあわせて予測する。このうち後処理に必要なコストは、条件の対象となっている検索経路上のＷｅｂページが、それまでに処理の対象となっていない場合は、条件の処理結果を中間結果としてシステム内の記憶領域へ登録するためのコストを加える。この時、条件の処理結果得られるＷｅｂページ数はインデックスを利用して予測する。また、Ｗｅｂページが既に処理対象となっていた場合は、登録されている中間結果と新たに得られた結果で一致している結果のみを中間結果に残すため、双方の比較に必要なコストを予測コストに加える。
【００３２】（２）のハイパーリンクの展開、および（３）の地理的ジェネリックリンクの展開は、リンクの起点となるＷｅｂページの中間結果が得られた時点で処理可能となり、処理コストを予測対象となる。予測式は、ほぼ（１）の予測式と同様であるが、各予測式の２行目でリンクに関するインデックス検索を行うコストを求める際、インデックス検索コストに条件の起点となっているＷｅｂページに対応する中間結果数をかけ、コストを予測する。また、ハイパーリンクに関する条件の場合は、順方向のリンク展開と逆方向のリンク展開の双方を考慮にいれる。（４）のＷｅｂページ間で属性を比較は、条件の対象となるＷｅｂページ双方の中間結果が得られた段階で評価可能となる。この操作の処理コストの予測は、対象となるＷｅｂページ数の和に比較処理コストをかけて求める。
【００３３】まず、コスト予測を利用した処理の最適化手順を示すために、図５に示した簡単な問い合わせ例の処理手順を説明する。図中の楕円でＰ１等記入されているのが、問い合わせで検索するＷｅｂページを示し、説明ではノードと呼ぶ。また、ノード間の矢印がリンクを示し、矢印の説明として記述されている“hyperlink”や“Distance”がそのリンクに関する条件を表す。
【００３４】この例では、ＵＲＬがhttp://www.aa.com/であるノードＰ１からハイパーリンクしているＷｅｂページで、かつ本文中に「支店」という文字列を含むノードＰ２を検索し、その系列を出力するというものである。この例ではＵＲＬの指定によりＰ１を確定した後、Ｐ１からハイパーリンクしているノードを検索するか、本文中に「支店」という文字列を含むノードを検索するかを、処理の予測コストの大小により決定する。この予測コストの大小は、時間に基づいた処理コストと処理結果の積で決まるので、処理時間が短く、かつ条件処理によって得られる結果が少ない場合に予測コストが小さくなる。すなわち、問い合わせ処理を進める上で、処理に時間が係らない条件で、かつ処理の結果、検索空間が大きくならない場合に予測コストが小となる。
【００３５】もし、ハイパーリンク条件の処理の方が予測コストが小さい場合、図の左側の処理となる。この場合は、Ｐ１からハイパーリンクで接続しているノードをハイパーリンクに関するインデックスを利用して求め、求めたノードの中からＷｅｂページの属性に関する条件である文字列「支店」を含むものを選択する。また、Ｗｅｂページの属性に関する条件の処理の方が予測コストが小さい場合は、図の右側の処理となる、こちらの場合は、Ｗｅｂページの属性に関する条件である文字列「支店」を含むノードを、Ｗｅｂページの本文中のキーワードに関するインデックスを利用して検索し、その後、検索したノードの中からＰ１とハイパーリンクで接続しているノードを求める。
【００３６】いずれの場合も処理結果は同じであるが、問い合わせ処理中の途中結果の大きさは、Ｐ１からハイパーリンクで接続しているＷｅｂページの数、およびＰ２の属性条件として指定された「支店」という文字列を含むＷｅｂページの数によって大きく左右される。この途中の検索空間を小さく抑えることで、システム内部の比較処理回数等を削減することができ、最終的には高速な問い合わせ処理が可能となる。
【００３７】次に、本実施形態を用いたより具体的な問い合わせ処理の最適化例を示すために、図６の例について説明する。この問い合わせでは、指定されたリンク集を起点にハイパーリンクをたどり、Ｗｅｂページの属性に関する条件と、地理的ジェネリックリンクに関する条件を組み合わせて、Ｗｅｂページの系列を検索する。問い合わせは、起点となるリンク集に対応するノードＰ１から、目的のＷｅｂページに対応するノードＰ４までが、ノードとリンクの繰り返しによる検索パスによって指定する。なお、バス停と喫茶店については、Ｗｅｂページ上の記述から検索できるものとして説明を進める。
【００３８】ちなみに、この例の問い合わせを文章で記述すると以下のようになる。「イタリア料理店を紹介するリンク集」で紹介されているお店から、「パスタ」に関する記述のあるＷｅｂページを選び、そのお店から、５００ｍ以内にあるバス停を検索し、そのバス停からさらに５００ｍ以内にある「コーヒー」を出す喫茶店を検索する。
【００３９】次に、この問い合わせ例の中の条件の処理順序について説明する。図７が最適化なしの場合の条件の処理順序、図８が最適化ありの場合の条件の処理順序であり、図中の括弧付の数字は、問い合わせ例の中で指定された条件の処理順序を表す。この処理順序を最適化ありの場合となしの場合で比較すると、ＵＲＬの指定に基づいた検索の起点Ｐ１の確定と、ハイパーリンクに関するインデックスを利用したＰ１からＰ２へのハイパーリンクの展開の２番目の処理までは同じ順序で行われた。しかし、３番目以降の処理順序には差が見られた。最適化なしの場合は、問い合わせに指定された順序に従って、条件処理が進んだのに対し、最適化ありの場合は、ノードＰ４、Ｐ２、Ｐ３のＷｅｂページの属性に関する条件が、Ｗｅｂページのテキスト部に出現する語句に関するインデックスを利用して先に処理され、その後、ノード間の地理的ジェネリックリンクに関する条件がＰＯＩ−ＤＢと地理的関係演算により処理された。
【００４０】この問い合わせ処理中にシステム内部で行われた比較処理回数（図９）を見てみると、問い合わせ処理の３番目と５番目に大きな差が見られ、最適化により属性に関する条件を先に評価し、その後リンクを展開することで、システム内部の比較回数が削減された事がわかる。従って、問い合わせ例の処理では、処理の前半に検索パス上のノードに対応するＷｅｂページの選択を行い、その後Ｗｅｂページ間のリンク関係を検証する手順を最適化により選択することで、問い合わせ処理の高速化ができた。
【００４１】本実施形態は、上記のような手法で実装する検索システムに関するものであるが、下記に挙げたユーザが利用する端末の形態、検索システムの設置形態、検索システムの利用形態、および利用するネットワークの形態のいずれを組合わせた場合も、実施形態の検索システムは入力された問い合わせを高速に処理することができる。
・ユーザが利用する端末の形態：デスクトップコンピュータ、携帯型コンピュータ、ＰＤＡ、ノート型コンピュータ、ウェアラブルコンピュータ、携帯電話、固定電話、公衆電話、カーナビゲーションシステム、街頭端末。
【００４２】・検索システムの設置形態：インターネットで公開されているコンピュータへの検索システムの設置。インターネットに公開されていない内部利用を目的とするコンピュータへの検索システムの設置。ネットワークに接続されていないが電話網、携帯電話網と接続するモデムを有するコンピュータへの検索システムの設置。ネットワーク及び電話網と独立し、単独で動作するコンピュータへの検索システムの設置。（上記の単独動作以外の場合は、検索システムを構成するモジュールを一台のコンピュータ上で集中的に動作しなければならないという制限はなく、複数のコンピュータに分散させることも可能）
【００４３】・検索システムの利用形態：穴埋め式フォームからの入力受け付けと、木構造表示、地図もしくは仮想空間を利用した２次元もしくは３次元的な表示の一つ以上の表示方法を組み合わせた検索結果表示。穴埋め式フォームからの条件入力と、検索可能な項目の木構造表示、地図もしくは仮想空間を利用した２次元もしくは３次元的な検索可能な項目の表示を一つ以上組合わせた問い合わせ入力と、それに対応した検索結果表示。上記の複数の入出力手法に、音声による条件入力及び検索結果出力を加えた複数の入出力方法から、一つ以上を組み合わせた利用形態。
・利用するネットワークの形態：無線接続もしくは有線接続、また常時接続もしくはダイアルアップ接続。
【００４４】［実施形態２］実施形態１の地理的ジェネリックリンク生成モジュールと同様に、Ｗｅｂページから抽出した語句の類似性など、Ｗｅｂページの自然言語属性の関連性によって動的にリンクを生成するモジュールを問い合わせ処理に利用する。このモジュールは、Ｗｅｂページから抽出した属性と抽出元であるＷｅｂページのＵＲＬを格納した自然言語属性ＤＢと、シソーラスもしくは辞書に基づき属性間の類似性を評価するための関数により、Ｗｅｂページ間にリンクを生成する。たとえば、以下のような語句の類似性に基づきＷｅｂページ間に動的にリンクを生成する。
・リンク元Ｗｅｂページの指定語句と同じ語句を含む。
・リンク元Ｗｅｂページの指定語句の類義語を含む。
この自然言語属性の関連性によって動的にリンクを生成するモジュール以外の検索システムの構成、検索手順、および利用形態は実施形態１と同様である。
【００４５】［実施形態３］実施形態１の地理的ジェネリックリンク生成モジュールの代わりに、Ｗｅｂページから抽出した属性、Ｗｅｂサーバ名、Ｗｅｂページのアドレス、ＵＲＬ、ＨＴＭＬタグ、ハイパーリンクの関連性により、動的に生成するモジュールを利用する。このモジュールは、抽出した属性と抽出元であるＷｅｂページのＵＲＬを格納したＷｅｂページ属性ＤＢと、属性間の類似性を評価するための関数により、Ｗｅｂページ間にリンクを生成する。
【００４６】たとえば、以下のような属性の類似性に基づきＷｅｂページ間に動的にリンクを生成する。
・リンク元Ｗｅｂページの保存されているサーバと同じサーバに保存されている（サーバアドレスの完全一致）。
・リンク元Ｗｅｂページの保存されているサーバと同じドメインに属するサーバに保存されている（サーバアドレスの部分一致）。
・リンク元Ｗｅｂページが保存されているＷｅｂサーバ上のディレクトリと同じディレクトリに保存されている。
・リンク元Ｗｅｂページが保存されているＷｅｂサーバ上のディレクトリに含まれる下位ディレクトリに保存されている。
・リンク元Ｗｅｂページが保存されているＷｅｂサーバ上のディレクトリの上位ディレクトリに保存されている。
・リンク元Ｗｅｂページと同種のタグ（たとえば、イメージタグ、表、箇条書き）を含んでいる。
・リンク元Ｗｅｂページ中のハイパーリンク先と同じリンク先を含んでいる。
【００４７】この、サーバ名、Ｗｅｂページのアドレスなど、Ｗｅｂページから抽出した属性の関連性によりリンクを動的に生成するモジュール以外の検索システムの構成、検索手順、および利用形態は実施形態１と同様である。
【００４８】［実施形態４］実施形態１から実施形態３で示した動的なリンクを生成するモジュールを一つ以上組み合わせて実施できる検索システム。
【００４９】以上、本発明者によってなされた発明を、前記実施の形態に基づき具体的に説明したが、本発明は、前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲において種々変更可能であることは勿論である。
【００５０】
【発明の効果】以上述べたように本発明によれば、Ｗｅｂページの系列を検索する問い合わせを高速に処理することを可能にするという効果が得られる。この問い合わせとは、Ｗｅｂページから抽出した属性に関する条件と、Ｗｅｂページ間のハイパーリンクに関する条件と、Ｗｅｂページから抽出した属性の関連性を利用して動的に生成するＷｅｂページ間のリンクに関する条件を組み合わせ問い合わせたものである。また処理には、抽出した属性に関するインデックスとリンクを生成するためのインデックスを利用し、問い合わせ中の条件の処理コストと検索結果数の予測の積が最小となる条件から処理を進め、問い合わせの高速処理を可能にする。
【図面の簡単な説明】
【図１】本発明の一実施形態を示す図である。
【図２】検索システムで利用するインデックスの構築例を示す図である。
【図３】ＰＯＩ−ＤＢの構築例を示す図である。
【図４】問い合わせ処理手順を示す図である。
【図５】コスト予測による処理条件の選択例を示す図である。
【図６】問い合わせ例の検索パスを示す図である。
【図７】最適化なしの場合の検索順序を示す図である。
【図８】最適化ありの場合の検索順序を示す図である。
【図９】検索システム内部の累積比較回数を示す図である。
【特許請求の範囲】
【請求項１】 インターネット上に発信されている大量のＷｅｂページから、Ｗｅｂページから抽出した属性に関する条件とハイパーリンクに関する条件を組み合わせて指定し、Ｗｅｂページの系列を検索するための問い合わせの処理方法において、Ｗｅｂページに関するインデックスを利用し、問い合わせに指定された条件から、未処理で、かつ他条件の処理結果に依存せずに処理結果を求めることのできる条件の処理コストと処理結果を予測し、問い合わせ処理の進行状況にあわせて最適な条件を選択し処理する操作を、問い合わせで指定された全ての条件を処理するまで繰り返し、問い合わせの条件を満たすＷｅｂページの系列を求めるＷｅｂページ検索方法。
【請求項２】 請求項１に記載のＷｅｂページ検索方法であって、前記Ｗｅｂページに関するインデックスは、Ｗｅｂページの属性値からＵＲＬを求めることの出来るインデックスと、ＷｅｂページのＵＲＬからリンク先およびリンク元ＷｅｂページのＵＲＬを求めることのできるハイパーリンクに関するインデックスであり、前記他条件の処理結果に依存せずに処理結果を求めることのできる条件は、Ｗｅｂページの属性に関する条件と、ハイパーリンクに関する条件のうち、他の条件の処理により、リンク元またはリンク先もしくはその両方のＷｅｂページ集合が空でない条件以外の条件であり、前記処理コストの予測は、検索システムがＷｅｂページに関するインデックスを利用して条件を処理するときに必要な時間の予測に基づくものであり、関数呼び出し時の初期遅延の予測と、条件を処理するための時間の予測、処理結果を検索システム内のそれまでの処理結果と整合させるために必要な時間の予測の和であり、前記処理結果の予測は、検索システムがＷｅｂページに関するインデックスを利用して条件を処理を行い得られる結果の予測であり、インデックスの先読みとインデックスの統計情報に基づき求めるものであり、前記問い合わせ処理の進行状況にあわせて最適な条件は、処理コストの予測と処理結果の予測の積が最小となる条件であることを特徴とするＷｅｂページ検索方法。
【請求項３】 請求項１または２に記載のＷｅｂページ検索方法であって、前記Ｗｅｂページの系列を検索するための問い合わせに、Ｗｅｂページから抽出した属性に基づきＷｅｂページ間に動的に生成するリンクに関する条件を加えて指定することができることを特徴とする検索方法。
【請求項４】 請求項３に記載のＷｅｂページ検索方法であって、ＷｅｂページのＵＲＬから動的に生成するリンクのリンク先およびリンク元ＷｅｂページのＵＲＬは、次の３ステップを経て求めることを特徴とするＷｅｂページ検索方法。
１．問い合わせ中で指定された属性をＵＲＬで指定されたＷｅｂページから抽出するステップ２．抽出した属性値から条件で指定された関係にある属性値を検索するステップ３．検索した属性値に対応するＵＲＬをインデックスを利用して検索するステップ
【請求項５】 請求項３または４に記載のＷｅｂページ検索方法であって、前記動的に生成するリンクに関する条件として、Ｗｅｂページ間の地理的関係によって動的に生成するリンクに関する条件を指定することができることを特徴とするＷｅｂページ検索方法。
【請求項６】 請求項５に記載のＷｅｂページ検索方法であって、Ｗｅｂページから抽出した地理的属性間の関係は、地理情報システム（ＧＩＳ）上の地理的関係演算、もしくは幾何的な関係演算を用いて処理し、Ｗｅｂページからの地理属性の抽出は、システム中に指定された地理表現とのパターンマッチング、もしくは文書中から地理表現を抽出することの出来る形態素解析を用いることを特徴とするＷｅｂページ検索方法。
【請求項７】 請求項３ないし６のうちいずれか１項に記載のＷｅｂページ検索方法であって、前記動的に生成するリンクに関する条件として、Ｗｅｂページから抽出した表現を自然言語表現の類似性によって動的に生成するリンクに関する条件を指定でき、Ｗｅｂページから抽出した自然言語表現間の類似性は、シソーラス、もしくは言語辞書を用いて、その関係を評価することを特徴とするＷｅｂ検索方法。
【請求項８】 請求項３ないし６のうちいずれか１項に記載のＷｅｂページ検索方法であって、前記動的に生成するリンクに関する条件として、Ｗｅｂページから抽出した属性Ｗｅｂサーバ名、Ｗｅｂページのアドレス、ＵＲＬ、ＨＴＭＬタグ、ハイパーリンクの関連性により動的に生成するリンクに関する条件を指定することができることを特徴とするＷｅｂページ検索方法。
【請求項９】 コンピュータを、インターネット上に発信されている大量のＷｅｂページから、Ｗｅｂページから抽出した属性に関する条件とハイパーリンクに関する条件を組み合わせて指定した、Ｗｅｂページの系列を検索するための問い合わせを受け付ける手段、Ｗｅｂページに関するインデックスを利用し、問い合わせに指定された条件から、未処理で、かつ他条件の処理結果に依存せずに処理結果を求めることのできる条件の処理コストと処理結果を予測し、問い合わせ処理の進行状況にあわせて最適な条件を選択し処理する操作を、問い合わせで指定された全ての条件を処理するまで繰り返し、問い合わせの条件を満たすＷｅｂページの系列を求める手段、および、問い合わせの条件を満たすＷｅｂページの系列を出力する手段、として機能させるためのＷｅｂページ検索プログラム。
【請求項１０】 請求項９に記載のＷｅｂページ検索プログラムであって、前記Ｗｅｂページに関するインデックスは、Ｗｅｂページの属性値からＵＲＬを求めることの出来るインデックスと、ＷｅｂページのＵＲＬからリンク先およびリンク元ＷｅｂページのＵＲＬを求めることのできるハイパーリンクに関するインデックスであり、前記他条件の処理結果に依存せずに処理結果を求めることのできる条件は、Ｗｅｂページの属性に関する条件と、ハイパーリンクに関する条件のうち、他の条件の処理により、リンク元またはリンク先もしくはその両方のＷｅｂページ集合が空でない条件以外の条件であり、前記処理コストの予測は、検索システムがＷｅｂページに関するインデックスを利用して条件を処理するときに必要な時間の予測に基づくものであり、関数呼び出し時の初期遅延の予測と、条件を処理するための時間の予測、処理結果を検索システム内のそれまでの処理結果と整合させるために必要な時間の予測の和であり、前記処理結果の予測は、検索システムがＷｅｂページに関するインデックスを利用して条件を処理を行い得られる結果の予測であり、インデックスの先読みとインデックスの統計情報に基づき求めるものであり、前記問い合わせ処理の進行状況にあわせて最適な条件は、処理コストの予測と処理結果の予測の積が最小となる条件であることを特徴とするＷｅｂページ検索プログラム。
【請求項１１】 請求項９または１０に記載のＷｅｂページ検索プログラムであって、前記Ｗｅｂページの系列を検索するための問い合わせに、Ｗｅｂページから抽出した属性に基づきＷｅｂページ間に動的に生成するリンクに関する条件を加えて指定することができることを特徴とする検索プログラム。
【請求項１２】 請求項１１に記載のＷｅｂページ検索プログラムであって、ＷｅｂページのＵＲＬから動的に生成するリンクのリンク先およびリンク元ＷｅｂページのＵＲＬは、次の３ステップを経て求めることを特徴とするＷｅｂページ検索プログラム。
１．問い合わせ中で指定された属性をＵＲＬで指定されたＷｅｂページから抽出するステップ２．抽出した属性値から条件で指定された関係にある属性値を検索するステップ３．検索した属性値に対応するＵＲＬをインデックスを利用して検索するステップ
【請求項１３】 請求項１１または１２に記載のＷｅｂページ検索プログラムであって、前記動的に生成するリンクに関する条件として、Ｗｅｂページ間の地理的関係によって動的に生成するリンクに関する条件を指定することができることを特徴とするＷｅｂページ検索プログラム。
【請求項１４】 請求項１３に記載のＷｅｂページ検索プログラムであって、Ｗｅｂページから抽出した地理的属性間の関係は、地理情報システム（ＧＩＳ）上の地理的関係演算、もしくは幾何的な関係演算を用いて処理し、Ｗｅｂページからの地理属性の抽出は、システム中に指定された地理表現とのパターンマッチング、もしくは文書中から地理表現を抽出することの出来る形態素解析を用いることを特徴とするＷｅｂページ検索プログラム。
【請求項１５】 請求項１１ないし１４のうちいずれか１項に記載のＷｅｂページ検索プログラムであって、前記動的に生成するリンクに関する条件として、Ｗｅｂページから抽出した表現を自然言語表現の類似性によって動的に生成するリンクに関する条件を指定でき、Ｗｅｂページから抽出した自然言語表現間の類似性は、シソーラス、もしくは言語辞書を用いて、その関係を評価することを特徴とするＷｅｂ検索プログラム。
【請求項１６】 請求項１１ないし１４のうちいずれか１項に記載のＷｅｂページ検索プログラムであって、前記動的に生成するリンクに関する条件として、Ｗｅｂページから抽出した属性Ｗｅｂサーバ名、Ｗｅｂページのアドレス、ＵＲＬ、ＨＴＭＬタグ、ハイパーリンクの関連性により動的に生成するリンクに関する条件を指定することができることを特徴とするＷｅｂページ検索プログラム。
【請求項１７】 請求項９ないし１６のうちいずれか１項に記載のプログラムを備えたＷｅｂページ検索装置。
【請求項１８】 請求項９ないし１６のうちいずれか１項に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１】 インターネット上に発信されている大量のＷｅｂページから、Ｗｅｂページから抽出した属性に関する条件とハイパーリンクに関する条件を組み合わせて指定し、Ｗｅｂページの系列を検索するための問い合わせの処理方法において、Ｗｅｂページに関するインデックスを利用し、問い合わせに指定された条件から、未処理で、かつ他条件の処理結果に依存せずに処理結果を求めることのできる条件の処理コストと処理結果を予測し、問い合わせ処理の進行状況にあわせて最適な条件を選択し処理する操作を、問い合わせで指定された全ての条件を処理するまで繰り返し、問い合わせの条件を満たすＷｅｂページの系列を求めるＷｅｂページ検索方法。
【請求項２】 請求項１に記載のＷｅｂページ検索方法であって、前記Ｗｅｂページに関するインデックスは、Ｗｅｂページの属性値からＵＲＬを求めることの出来るインデックスと、ＷｅｂページのＵＲＬからリンク先およびリンク元ＷｅｂページのＵＲＬを求めることのできるハイパーリンクに関するインデックスであり、前記他条件の処理結果に依存せずに処理結果を求めることのできる条件は、Ｗｅｂページの属性に関する条件と、ハイパーリンクに関する条件のうち、他の条件の処理により、リンク元またはリンク先もしくはその両方のＷｅｂページ集合が空でない条件以外の条件であり、前記処理コストの予測は、検索システムがＷｅｂページに関するインデックスを利用して条件を処理するときに必要な時間の予測に基づくものであり、関数呼び出し時の初期遅延の予測と、条件を処理するための時間の予測、処理結果を検索システム内のそれまでの処理結果と整合させるために必要な時間の予測の和であり、前記処理結果の予測は、検索システムがＷｅｂページに関するインデックスを利用して条件を処理を行い得られる結果の予測であり、インデックスの先読みとインデックスの統計情報に基づき求めるものであり、前記問い合わせ処理の進行状況にあわせて最適な条件は、処理コストの予測と処理結果の予測の積が最小となる条件であることを特徴とするＷｅｂページ検索方法。
【請求項３】 請求項１または２に記載のＷｅｂページ検索方法であって、前記Ｗｅｂページの系列を検索するための問い合わせに、Ｗｅｂページから抽出した属性に基づきＷｅｂページ間に動的に生成するリンクに関する条件を加えて指定することができることを特徴とする検索方法。
【請求項４】 請求項３に記載のＷｅｂページ検索方法であって、ＷｅｂページのＵＲＬから動的に生成するリンクのリンク先およびリンク元ＷｅｂページのＵＲＬは、次の３ステップを経て求めることを特徴とするＷｅｂページ検索方法。
１．問い合わせ中で指定された属性をＵＲＬで指定されたＷｅｂページから抽出するステップ２．抽出した属性値から条件で指定された関係にある属性値を検索するステップ３．検索した属性値に対応するＵＲＬをインデックスを利用して検索するステップ
【請求項５】 請求項３または４に記載のＷｅｂページ検索方法であって、前記動的に生成するリンクに関する条件として、Ｗｅｂページ間の地理的関係によって動的に生成するリンクに関する条件を指定することができることを特徴とするＷｅｂページ検索方法。
【請求項６】 請求項５に記載のＷｅｂページ検索方法であって、Ｗｅｂページから抽出した地理的属性間の関係は、地理情報システム（ＧＩＳ）上の地理的関係演算、もしくは幾何的な関係演算を用いて処理し、Ｗｅｂページからの地理属性の抽出は、システム中に指定された地理表現とのパターンマッチング、もしくは文書中から地理表現を抽出することの出来る形態素解析を用いることを特徴とするＷｅｂページ検索方法。
【請求項７】 請求項３ないし６のうちいずれか１項に記載のＷｅｂページ検索方法であって、前記動的に生成するリンクに関する条件として、Ｗｅｂページから抽出した表現を自然言語表現の類似性によって動的に生成するリンクに関する条件を指定でき、Ｗｅｂページから抽出した自然言語表現間の類似性は、シソーラス、もしくは言語辞書を用いて、その関係を評価することを特徴とするＷｅｂ検索方法。
【請求項８】 請求項３ないし６のうちいずれか１項に記載のＷｅｂページ検索方法であって、前記動的に生成するリンクに関する条件として、Ｗｅｂページから抽出した属性Ｗｅｂサーバ名、Ｗｅｂページのアドレス、ＵＲＬ、ＨＴＭＬタグ、ハイパーリンクの関連性により動的に生成するリンクに関する条件を指定することができることを特徴とするＷｅｂページ検索方法。
【請求項９】 コンピュータを、インターネット上に発信されている大量のＷｅｂページから、Ｗｅｂページから抽出した属性に関する条件とハイパーリンクに関する条件を組み合わせて指定した、Ｗｅｂページの系列を検索するための問い合わせを受け付ける手段、Ｗｅｂページに関するインデックスを利用し、問い合わせに指定された条件から、未処理で、かつ他条件の処理結果に依存せずに処理結果を求めることのできる条件の処理コストと処理結果を予測し、問い合わせ処理の進行状況にあわせて最適な条件を選択し処理する操作を、問い合わせで指定された全ての条件を処理するまで繰り返し、問い合わせの条件を満たすＷｅｂページの系列を求める手段、および、問い合わせの条件を満たすＷｅｂページの系列を出力する手段、として機能させるためのＷｅｂページ検索プログラム。
【請求項１０】 請求項９に記載のＷｅｂページ検索プログラムであって、前記Ｗｅｂページに関するインデックスは、Ｗｅｂページの属性値からＵＲＬを求めることの出来るインデックスと、ＷｅｂページのＵＲＬからリンク先およびリンク元ＷｅｂページのＵＲＬを求めることのできるハイパーリンクに関するインデックスであり、前記他条件の処理結果に依存せずに処理結果を求めることのできる条件は、Ｗｅｂページの属性に関する条件と、ハイパーリンクに関する条件のうち、他の条件の処理により、リンク元またはリンク先もしくはその両方のＷｅｂページ集合が空でない条件以外の条件であり、前記処理コストの予測は、検索システムがＷｅｂページに関するインデックスを利用して条件を処理するときに必要な時間の予測に基づくものであり、関数呼び出し時の初期遅延の予測と、条件を処理するための時間の予測、処理結果を検索システム内のそれまでの処理結果と整合させるために必要な時間の予測の和であり、前記処理結果の予測は、検索システムがＷｅｂページに関するインデックスを利用して条件を処理を行い得られる結果の予測であり、インデックスの先読みとインデックスの統計情報に基づき求めるものであり、前記問い合わせ処理の進行状況にあわせて最適な条件は、処理コストの予測と処理結果の予測の積が最小となる条件であることを特徴とするＷｅｂページ検索プログラム。
【請求項１１】 請求項９または１０に記載のＷｅｂページ検索プログラムであって、前記Ｗｅｂページの系列を検索するための問い合わせに、Ｗｅｂページから抽出した属性に基づきＷｅｂページ間に動的に生成するリンクに関する条件を加えて指定することができることを特徴とする検索プログラム。
【請求項１２】 請求項１１に記載のＷｅｂページ検索プログラムであって、ＷｅｂページのＵＲＬから動的に生成するリンクのリンク先およびリンク元ＷｅｂページのＵＲＬは、次の３ステップを経て求めることを特徴とするＷｅｂページ検索プログラム。
１．問い合わせ中で指定された属性をＵＲＬで指定されたＷｅｂページから抽出するステップ２．抽出した属性値から条件で指定された関係にある属性値を検索するステップ３．検索した属性値に対応するＵＲＬをインデックスを利用して検索するステップ
【請求項１３】 請求項１１または１２に記載のＷｅｂページ検索プログラムであって、前記動的に生成するリンクに関する条件として、Ｗｅｂページ間の地理的関係によって動的に生成するリンクに関する条件を指定することができることを特徴とするＷｅｂページ検索プログラム。
【請求項１４】 請求項１３に記載のＷｅｂページ検索プログラムであって、Ｗｅｂページから抽出した地理的属性間の関係は、地理情報システム（ＧＩＳ）上の地理的関係演算、もしくは幾何的な関係演算を用いて処理し、Ｗｅｂページからの地理属性の抽出は、システム中に指定された地理表現とのパターンマッチング、もしくは文書中から地理表現を抽出することの出来る形態素解析を用いることを特徴とするＷｅｂページ検索プログラム。
【請求項１５】 請求項１１ないし１４のうちいずれか１項に記載のＷｅｂページ検索プログラムであって、前記動的に生成するリンクに関する条件として、Ｗｅｂページから抽出した表現を自然言語表現の類似性によって動的に生成するリンクに関する条件を指定でき、Ｗｅｂページから抽出した自然言語表現間の類似性は、シソーラス、もしくは言語辞書を用いて、その関係を評価することを特徴とするＷｅｂ検索プログラム。
【請求項１６】 請求項１１ないし１４のうちいずれか１項に記載のＷｅｂページ検索プログラムであって、前記動的に生成するリンクに関する条件として、Ｗｅｂページから抽出した属性Ｗｅｂサーバ名、Ｗｅｂページのアドレス、ＵＲＬ、ＨＴＭＬタグ、ハイパーリンクの関連性により動的に生成するリンクに関する条件を指定することができることを特徴とするＷｅｂページ検索プログラム。
【請求項１７】 請求項９ないし１６のうちいずれか１項に記載のプログラムを備えたＷｅｂページ検索装置。
【請求項１８】 請求項９ないし１６のうちいずれか１項に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
【図１】
【図４】
【図６】
【図７】
【図２】
【図３】
【図８】
【図５】
【図９】
【図４】
【図６】
【図７】
【図２】
【図３】
【図８】
【図５】
【図９】
【公開番号】特開２００３−２０３０８９（Ｐ２００３−２０３０８９Ａ）
【公開日】平成１５年７月１８日（２００３．７．１８）
【国際特許分類】
【出願番号】特願２００２−２２５（Ｐ２００２−２２５）
【出願日】平成１４年１月７日（２００２．１．７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成１５年７月１８日（２００３．７．１８）
【国際特許分類】
【出願日】平成１４年１月７日（２００２．１．７）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]