(57)【特許請求の範囲】
【請求項１】
検索に用いられたクエリを示すクエリノードおよび前記クエリ以外の前記検索に関する他の項目を示す中継ノードを含む複数のノードをエッジで接続したグラフを取得する第１取得手段と、
クエリ、前記クエリのジャンルを示すジャンル識別子および前記クエリと前記ジャンルとの関連性の高さを示すジャンルスコアを含むジャンル辞書の中から、指定されたジャンル識別子に対応するジャンルスコアおよびクエリを取得する第２取得手段と、
前記第１取得手段により取得されたグラフに含まれるクエリノードのうち前記ジャンル辞書にジャンルスコアが記載されていないクエリを示す対象ノードの中から特定されたノードを基点ノードとして、前記基点ノードと前記中継ノードを介してエッジで接続された他のクエリノードが示すクエリのジャンルスコアを、前記第２取得手段により取得されたジャンルスコアの中から用いて、前記基点ノードのクエリのジャンルスコアを算出する処理を、終了条件が満たされるまで前記基点ノードを更新しながら繰り返し行い、複数のクエリのジャンルスコアを算出する算出手段と
を有するサーバ装置。
【請求項２】
前記複数のノードが、前記検索の結果ユーザに閲覧された文書の所在を階層構造を用いて示す第１所在情報を示す第１所在ノード、前記第１所在情報よりも上位の第２所在情報を示す第２所在ノード、および前記検索をしたユーザ名を示すユーザノードを含み、
前記中継ノードが、前記第１所在ノードであり、
前記処理は、前記中継ノードとエッジで接続された前記第２所在ノードまたは前記ユーザノードとエッジで接続された他のクエリノードが示すクエリのジャンルスコアを用いて、前記基点クエリのジャンルスコアを算出する処理である
ことを特徴とする請求項１に記載のサーバ装置。
【請求項３】
前記複数のノードが、前記検索の結果ユーザに閲覧された文書の所在を階層構造を用いて示す第１所在情報を示す第１所在ノード、および前記第１所在情報よりも上位の第２所在情報を示す第２所在ノードを含み、
前記中継ノードが、前記第１所在ノードであり、
前記算出手段は、前記第２所在情報毎に、前記第２所在情報と前記ジャンルとの間の相関を示すパラメータを算出し、
前記処理は、前記基点ノードと関連する第２所在ノードと関連する他のクエリノードが示すクエリのジャンルスコアおよび前記パラメータを用いて、前記基点ノードのクエリのジャンルスコアを算出する処理である
ことを特徴とする請求項１に記載のサーバ装置。
【請求項４】
検索に用いられたクエリと前記検索が行われた回数である検索回数とが蓄積された検索ログを取得する第３取得手段と、
クエリが入力されると検索結果を出力する検索サーバに対し、前記検索ログに含まれるクエリを入力し、前記クエリに対する検索結果を取得する第４取得手段と、
前記第３取得手段により取得された検索ログおよび前記第４取得手段により取得された検索結果を用いて前記エッジの重みを推定する推定手段と
を有し、
前記処理は、前記基点ノードと関連する第２所在ノードと関連する他のクエリノードが示すクエリのジャンルスコアおよび前記推定された重みを用いて、前記基点ノードのクエリのジャンルスコアを算出する処理である
ことを特徴とする請求項１に記載のサーバ装置。
【請求項５】
検索に用いられたクエリと、前記検索により閲覧された文書の所在を階層構造により示す第１所在情報とを含む複数の項目を含む検索ログを、コンピュータの制御手段が第１記憶手段に記憶するステップと、
前記第１記憶手段に記憶されている検索ログに含まれる項目のうち、前記クエリおよび前記クエリ以外の他の項目をノードとして、前記制御手段が抽出するステップと、
前記抽出されたクエリを示すクエリノードと、前記抽出された他の項目を示す中継ノードとエッジで接続したグラフを、前記制御手段が生成するステップと、
クエリ、前記クエリのジャンルを示すジャンル識別子および前記クエリと前記ジャンルとの関連性の高さを示すジャンルスコアを含むジャンル辞書を記憶した第２記憶手段から、指定されたジャンル識別子に対応するジャンルスコアおよびクエリを、前記制御手段が取得するステップと、
前記生成されたグラフに含まれるクエリノードのうち所定の条件を満たす対象ノードの中から特定されたノードを基点ノードとして、前記基点ノードと前記中継ノードを介してエッジで接続された他のクエリノードが示すクエリのジャンルスコアを、前記取得されたジャンルスコアの中から用いて、前記基点ノードのクエリのジャンルスコアを算出する処理を、終了条件が満たされるまで前記基点ノードを更新しながら繰り返し行い、複数のクエリのジャンルスコアを、前記制御手段が算出するステップと
を有するジャンルスコア算出方法。
【請求項６】
前記複数のノードが、前記検索の結果ユーザに閲覧された文書の所在を階層構造を用いて示す第１所在情報を示す第１所在ノード、前記第１所在情報よりも上位の第２所在情報を示す第２所在ノード、および前記検索をしたユーザ名を示すユーザノードを含み、
前記中継ノードが、前記第１所在ノードであり、
前記処理は、前記中継ノードとエッジで接続された前記第２所在ノードまたは前記ユーザノードとエッジで接続された他のクエリノードが示すクエリのジャンルスコアを用いて、前記基点クエリのジャンルスコアを、前記制御手段が算出する処理である
ことを特徴とする請求項５に記載のジャンルスコア算出方法。
【請求項７】
前記複数のノードが、前記検索の結果ユーザに閲覧された文書の所在を階層構造を用いて示す第１所在情報を示す第１所在ノード、および前記第１所在情報よりも上位の第２所在情報を示す第２所在ノードを含み、
前記中継ノードが、前記第１所在ノードであり、
前記第２所在情報毎に、前記第２所在情報と前記ジャンルとの間の相関を示すパラメータを、前記制御手段が算出するステップをさらに有し、
前記処理は、前記基点ノードと関連する第２所在ノードと関連する他のクエリノードが示すクエリのジャンルスコアおよび前記パラメータを用いて、前記基点ノードのクエリのジャンルスコアを、前記制御手段が算出する処理である
ことを特徴とする請求項５に記載のジャンルスコア算出方法。
【請求項８】
検索に用いられたクエリと、前記検索が行われた回数とを含む検索ログを、コンピュータの制御手段が第１記憶手段に記憶するステップと、
クエリが入力されると検索結果を出力する検索サーバに対し、前記第１記憶手段に記憶されている検索ログに含まれるクエリを入力し、前記クエリに対する検索結果を、前記制御手段が取得するステップと、
前記第１記憶手段に記憶されている検索ログに含まれる項目のうち、前記クエリおよび前記クエリ以外の他の項目をノードとして、前記制御手段が抽出するステップと、
前記抽出されたクエリを示すクエリノードと、前記抽出された他の項目を示す中継ノードとエッジで接続したグラフを、前記制御手段が生成するステップと、
前記第１記憶手段に記憶されている検索ログおよび前記取得された検索結果を用いて前記エッジの重みを、前記制御手段が推定するステップと、
クエリ、前記クエリのジャンルを示すジャンル識別子および前記クエリと前記ジャンル
との関連性の高さを示すジャンルスコアを含むジャンル辞書を記憶した第２記憶手段から、指定されたジャンル識別子に対応するジャンルスコアおよびクエリを、前記制御手段が取得するステップと、
前記生成されたグラフに含まれるクエリノードのうち所定の条件を満たす対象ノードの中から特定されたノードを基点ノードとして、前記基点ノードと前記中継ノードを介してエッジで接続された他のクエリノードが示すクエリのジャンルスコアを、前記取得されたジャンルスコアの中から用いて、かつ前記推定された重みを用いて、前記基点ノードのクエリのジャンルスコアを算出する処理を、終了条件が満たされるまで前記基点ノードを更新しながら繰り返し行い、複数のクエリのジャンルスコアを、前記制御手段が算出するステップと
を有するジャンルスコア算出方法。
【請求項９】
コンピュータに、
検索に用いられたクエリと、前記検索により閲覧された文書の所在を階層構造により示す第１所在情報とを含む複数の項目を含む検索ログを第１記憶手段に記憶するステップと、
前記第１記憶手段に記憶されている検索ログに含まれる項目のうち、前記クエリおよび前記クエリ以外の他の項目をノードとして抽出するステップと、
前記抽出されたクエリを示すクエリノードと、前記抽出された他の項目を示す中継ノードとエッジで接続したグラフを生成するステップと、
クエリ、前記クエリのジャンルを示すジャンル識別子および前記クエリと前記ジャンルとの関連性の高さを示すジャンルスコアを含むジャンル辞書を記憶した第２記憶手段から、指定されたジャンル識別子に対応するジャンルスコアおよびクエリを取得するステップと、
前記生成されたグラフに含まれるクエリノードのうち所定の条件を満たす対象ノードの中から特定されたノードを基点ノードとして、前記基点ノードと前記中継ノードを介してエッジで接続された他のクエリノードが示すクエリのジャンルスコアを、前記取得されたジャンルスコアの中から用いて、前記基点ノードのクエリのジャンルスコアを算出する処理を、終了条件が満たされるまで前記基点ノードを更新しながら繰り返し行い、複数のクエリのジャンルスコアを算出するステップと
を実行させるためのプログラム。
【請求項１０】
コンピュータに、
検索に用いられたクエリと、前記検索が行われた回数とを含む検索ログを第１記憶手段に記憶するステップと、
クエリが入力されると検索結果を出力する検索サーバに対し、前記第１記憶手段に記憶されている検索ログに含まれるクエリを入力し、前記クエリに対する検索結果を取得するステップと、
前記第１記憶手段に記憶されている検索ログに含まれる項目のうち、前記クエリおよび前記クエリ以外の他の項目をノードとして抽出するステップと、
前記抽出されたクエリを示すクエリノードと、前記抽出された他の項目を示す中継ノードとエッジで接続したグラフを生成するステップと、
前記第１記憶手段に記憶されている検索ログおよび前記取得された検索結果を用いて前記エッジの重みを推定するステップと、
クエリ、前記クエリのジャンルを示すジャンル識別子および前記クエリと前記ジャンルとの関連性の高さを示すジャンルスコアを含むジャンル辞書を記憶した第２記憶手段から、指定されたジャンル識別子に対応するジャンルスコアおよびクエリを取得するステップと、
前記生成されたグラフに含まれるクエリノードのうち所定の条件を満たす対象ノードの中から特定されたノードを基点ノードとして、前記基点ノードと前記中継ノードを介してエッジで接続された他のクエリノードが示すクエリのジャンルスコアを、前記取得されたジャンルスコアの中から用いて、かつ前記推定された重みを用いて、前記基点ノードのクエリのジャンルスコアを算出する処理を、終了条件が満たされるまで前記基点ノードを更新しながら繰り返し行い、複数のクエリのジャンルスコアを算出するステップと
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、検索クエリのジャンルを推定する技術に関する。
【背景技術】
【０００２】
ネットワークにおける検索サービスが用いられている。欲しい情報をより効率的に得るためには、検索サービスの利用者が複数の単語を組み合わせるなどして、より適切なクエリを作成する必要がある。利用者の利便性を向上させるため、入力されたクエリに対して推薦クエリを提供する技術が知られている（例えば、特許文献１および２）。
【０００３】
特許文献１は、情報検索サーバを開示している。特許文献１において、情報検索サーバは、ユーザによる操作履歴情報（ユーザＩＤ、捜査対象、操作内容、操作回数、評価値）を含むデータベースを有する。情報検索サーバは、入力された要求情報（検索対象の商品名やジャンル名）に対し、ｗｅｂページ群を抽出し、抽出したｗｅｂページ群をカテゴリに分類し、ユーザに送信する（図７）。特許文献２は、検索クエリに関するスコアを算出する技術を開示している。具体的に、特許文献２は、ＵＲＬを介して複数のクエリを結びつけ、クエリの組み合わせに対してスコアを算出し、スコアに基づいて一のクエリから他のクエリを推薦することを開示している（段落００７７、図１１）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００４−３２６５３７号公報
【特許文献２】特開２００９−２５２０７０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
特許文献１および２に記載された技術によっても、他のクエリのジャンルスコアを用いてジャンルスコアを算出することができなかった。
これに対し本発明は、他のクエリのジャンルスコアを用いてジャンルスコアを算出する技術を提供する。
【０００６】
本発明は、検索に用いられたクエリを示すクエリノードおよび前記クエリ以外の前記検索に関する他の項目を示す中継ノードを含む複数のノードをエッジで接続したグラフを取得する第１取得手段と、クエリ、前記クエリのジャンルを示すジャンル識別子 および前記クエリと前記ジャンルとの関連性の高さを示すジャンルスコアを含むジャンル辞書の中から、指定されたジャンル識別子に対応するジャンルスコアおよびクエリを取得 する第２取得手段と、前記第１取得手段により取得されたグラフに含まれるクエリノードのうち前記ジャンル辞書にジャンルスコアが記載されていないクエリを示す対象ノードの中から特定されたノードを基点ノードとして 、前記基点ノードと前記中継ノードを介してエッジで接続された他のクエリノードが示すクエリのジャンルスコアを、前記第２取得手段により取得されたジャンルスコアの中から用いて、前記基点ノードのクエリのジャンルスコアを算出する処理を、終了条件が満たされるまで前記基点ノードを更新しながら繰り返し行い、複数のクエリのジャンルスコアを算出する算出手段とを有するサーバ装置を提供する。
このサーバ装置によれば、他のクエリのジャンルスコアを用いてジャンルスコアを算出することができる。
【０００７】
好ましい態様において、前記複数のノードが、前記検索の結果ユーザに閲覧された文書の所在を階層構造を用いて示す第１所在情報を示す第１所在ノード 、前記第１所在情報よりも上位の第２所在情報を示す第２所在ノード、および前記検索をしたユーザ名を示すユーザノードを含み、前記中継ノードが、前記第１所在ノードであり、前記処理は、前記中継ノードとエッジで接続された前記第２所在ノードまたは前記ユーザノードとエッジで接続された他のクエリノードが示すクエリのジャンルスコアを用いて、前記基点クエリのジャンルスコアを算出する処理であってもよい。
このサーバ装置によれば、第１所在ノードよりも上位のノードで接続されたクエリノードのジャンルスコアを用いてジャンルスコアを算出することができる。
【０００８】
別の好ましい態様において、前記複数のノードが、前記検索の結果ユーザに閲覧された文書の所在を階層構造を用いて示す第１所在情報を示す第１所在ノード、および前記第１所在情報よりも上位の第２所在情報を示す第２所在ノードを含み、前記中継ノードが、前記第１所在ノードであり、前記算出手段は、前記第２所在情報毎に、前記第２所在情報と前記ジャンルとの間の相関を示すパラメータを算出し、前記処理は、前記基点ノードと関連する第２所在ノードと関連する他のクエリノードが示すクエリのジャンルスコアおよび前記パラメータを用いて、前記基点ノードのクエリのジャンルスコアを算出する処理であってもよい。
このサーバ装置によれば、第２所在情報とジャンルとの間の相関を示すパラメータを用いてジャンルスコアを算出することができる。
【０００９】
さらに別の好ましい態様において、このサーバ装置は、検索に用いられたクエリと前記検索が行われた回数である検索回数とが蓄積された検索ログを取得する第３取得手段と、クエリが入力されると検索結果を出力する検索サーバに対し、前記検索ログに含まれるクエリを入力し、前記クエリに対する検索結果を取得する第４取得手段と、前記第３取得手段により取得された検索ログおよび前記第４取得手段により取得された検索結果を用いて前記エッジの重みを推定する推定手段とを有し、前記処理は、前記基点ノードと関連する第２所在ノードと関連する他のクエリノードが示すクエリのジャンルスコアおよび前記推定された重みを用いて、前記基点ノードのクエリのジャンルスコアを算出する処理であってもよい。
このサーバ装置によれば、検索に用いられたクエリと前記検索が行われた回数である検索回数とが蓄積された検索ログから、ジャンルスコアを算出することができる。
【００１０】
また、本発明は、検索に用いられたクエリと、前記検索により閲覧された文書の所在を階層構造により示す第１所在情報とを含む複数の項目を含む検索ログを第１記憶手段に記憶するステップと、前記第１記憶手段に記憶されている検索ログに含まれる項目のうち、前記クエリおよび前記クエリ以外の他の項目をノードとして抽出するステップと、前記抽出されたクエリを示すクエリノードと、前記抽出された他の項目を示す中継ノードとエッジで接続したグラフを生成するステップと、クエリ、前記クエリのジャンルを示すジャンル識別子および前記クエリと前記ジャンルとの関連性の高さを示すジャンルスコアを含むジャンル辞書を記憶した第２記憶手段から、指定されたジャンル識別子に対応するジャンルスコアおよびクエリを取得するステップと、前記生成されたグラフに含まれるクエリノードのうち所定の条件を満たす対象ノードの中から特定されたノードを基点ノードとして、前記基点ノードと前記中継ノードを介してエッジで接続された他のクエリノードが示すクエリのジャンルスコアを、前記取得されたジャンルスコアの中から用いて、前記基点ノードのクエリのジャンルスコアを算出する処理を、終了条件が満たされるまで前記基点ノードを更新しながら繰り返し行い、複数のクエリのジャンルスコアを算出するステップとを有するジャンルスコア算出方法を提供する。
この方法によれば、他のクエリのジャンルスコアを用いてジャンルスコアを算出することができる。
【００１１】
好ましい態様において、前記複数のノードが、前記検索の結果ユーザに閲覧された文書の所在を階層構造を用いて示す第１所在情報を示す第１所在ノード、前記第１所在情報よりも上位の第２所在情報を示す第２所在ノード、および前記検索をしたユーザ名を示すユーザノードを含み、前記中継ノードが、前記第１所在ノードであり、前記処理は、前記中継ノードとエッジで接続された前記第２所在ノードまたは前記ユーザノードとエッジで接続された他のクエリノードが示すクエリのジャンルスコアを用いて、前記基点クエリのジャンルスコアを算出する処理であってもよい。
この方法によれば、第１所在ノードよりも上位のノードで接続されたクエリノードのジャンルスコアを用いてジャンルスコアを算出することができる。
【００１２】
別の好ましい態様において、前記複数のノードが、前記検索の結果ユーザに閲覧された文書の所在を階層構造を用いて示す第１所在情報を示す第１所在ノード、および前記第１所在情報よりも上位の第２所在情報を示す第２所在ノードを含み、前記中継ノードが、前記第１所在ノードであり、前記第２所在情報毎に、前記第２所在情報と前記ジャンルとの間の相関を示すパラメータを算出するステップをさらに有し、前記処理は、前記基点ノードと関連する第２所在ノードと関連する他のクエリノードが示すクエリのジャンルスコアおよび前記パラメータを用いて、前記基点ノードのクエリのジャンルスコアを算出する処理であってもよい。
この方法によれば、第２所在情報とジャンルとの間の相関を示すパラメータを用いてジャンルスコアを算出することができる。
【００１３】
さらに、本発明は、検索に用いられたクエリと、前記検索が行われた回数とを含む検索ログを第１記憶手段に記憶するステップと、クエリが入力されると検索結果を出力する検索サーバに対し、前記第１記憶手段に記憶されている検索ログに含まれるクエリを入力し、前記クエリに対する検索結果を取得するステップと、前記第１記憶手段に記憶されている検索ログに含まれる項目のうち、前記クエリおよび前記クエリ以外の他の項目をノードとして抽出するステップと、前記抽出されたクエリを示すクエリノードと、前記抽出された他の項目を示す中継ノードとエッジで接続したグラフを生成するステップと、前記第１記憶手段に記憶されている検索ログおよび前記取得された検索結果を用いて前記エッジの重みを推定するステップと、クエリ、前記クエリのジャンルを示すジャンル識別子および前記クエリと前記ジャンルとの関連性の高さを示すジャンルスコアを含むジャンル辞書を記憶した第２記憶手段から、指定されたジャンル識別子に対応するジャンルスコアおよびクエリを取得するステップと、前記生成されたグラフに含まれるクエリノードのうち所定の条件を満たす対象ノードの中から特定されたノードを基点ノードとして、前記基点ノードと前記中継ノードを介してエッジで接続された他のクエリノードが示すクエリのジャンルスコアを、前記取得されたジャンルスコアの中から用いて、かつ前記推定された重みを用いて、前記基点ノードのクエリのジャンルスコアを算出する処理を、終了条件が満たされるまで前記基点ノードを更新しながら繰り返し行い、複数のクエリのジャンルスコアを算出するステップとを有するジャンルスコア算出方法を提供する。
この方法によれば、検索に用いられたクエリと前記検索が行われた回数である検索回数とが蓄積された検索ログから、ジャンルスコアを算出することができる。
【００１４】
さらに、本発明は、コンピュータに、検索に用いられたクエリと、前記検索により閲覧された文書の所在を階層構造により示す第１所在情報とを含む複数の項目を含む検索ログを第１記憶手段に記憶するステップと、前記第１記憶手段に記憶されている検索ログに含まれる項目のうち、前記クエリおよび前記クエリ以外の他の項目をノードとして抽出するステップと、前記抽出されたクエリを示すクエリノードと、前記抽出された他の項目を示す中継ノードとエッジで接続したグラフを生成するステップと、クエリ、前記クエリのジャンルを示すジャンル識別子 および前記クエリと前記ジャンルとの関連性の高さを示すジャンルスコアを含むジャンル辞書を記憶した第２記憶手段から、指定されたジャンル識別子に対応するジャンルスコアおよびクエリを取得するステップと、前記生成されたグラフに含まれるクエリノードのうち所定の条件を満たす対象ノードの中から特定されたノードを基点ノードとして、前記基点ノードと前記中継ノードを介してエッジで接続された他のクエリノードが示すクエリのジャンルスコアを、前記取得されたジャンルスコアの中から用いて、前記基点ノードのクエリのジャンルスコアを算出する処理を、終了条件が満たされるまで前記基点ノードを更新しながら繰り返し行い、複数のクエリのジャンルスコアを算出するステップとを実行させるためのプログラムを提供する。
このプログラムによれば、他のクエリのジャンルスコアを用いてジャンルスコアを算出することができる。
【００１５】
さらに、本発明は、コンピュータに、検索に用いられたクエリと、前記検索が行われた回数とを含む検索ログを第１記憶手段に記憶するステップと、クエリが入力されると検索結果を出力する検索サーバに対し、前記第１記憶手段に記憶されている検索ログに含まれるクエリを入力し、前記クエリに対する検索結果を取得するステップと、前記第１記憶手段に記憶されている検索ログに含まれる項目のうち、前記クエリおよび前記クエリ以外の他の項目をノードとして抽出するステップと、前記抽出されたクエリを示すクエリノードと、前記抽出された他の項目を示す中継ノードとエッジで接続したグラフを生成するステップと、前記第１記憶手段に記憶されている検索ログおよび前記取得された検索結果を用いて前記エッジの重みを推定するステップと、クエリ、前記クエリのジャンルを示すジャンル識別子 および前記クエリと前記ジャンルとの関連性の高さを示すジャンルスコアを含むジャンル辞書を記憶した第２記憶手段から、指定されたジャンル識別子に対応するジャンルスコアおよびクエリを取得するステップと、前記生成されたグラフに含まれるクエリノードのうち所定の条件を満たす対象ノードの中から特定されたノードを基点ノードとして、前記基点ノードと前記中継ノードを介してエッジで接続された他のクエリノードが示すクエリのジャンルスコアを、前記取得されたジャンルスコアの中から用いて、かつ前記推定された重みを用いて、前記基点ノードのクエリのジャンルスコアを算出する処理を、終了条件が満たされるまで前記基点ノードを更新しながら繰り返し行い、複数のクエリのジャンルスコアを算出するステップとを実行させるためのプログラムを提供する。
このプログラムによれば、他のクエリのジャンルスコアを用いてジャンルスコアを算出することができる。
【図面の簡単な説明】
【００１６】
【図１】一実施形態に係る検索システム１の構成を示す図である。
【図２】検索ログを例示する図である。
【図３】グラフを例示する図である。
【図４】グラフの生成処理を説明する図である。
【図５】ジャンル辞書を例示する図である。
【図６】ジャンルサーバ１０のハードウェア構成を示す図である。
【図７】ジャンルスコア算出処理を示すフローチャートである。
【図８】この例で取得されたグラフを示す図である。
【図９】図８のグラフの付随データを示す図である。
【図１０】ジャンルスコア算出処理の一例を示すフローチャートである。
【図１１】ジャンルサーバ１０からの出力データを例示する図である。
【図１２】対比例としてのグラフを示す図である。
【図１３】変形例１に係るグラフを例示する図である。
【図１４】図１３のグラフに付随するデータを示す図である。
【図１５】変形例２に係る動作を示すフローチャートである。
【図１６】変形例２に係るグラフを例示する図である。
【図１７】図１６のグラフに付随するデータを示す図である。
【図１８】変形例３に係るグラフを例示する図である。
【図１９】変形例４に係る検索システム１の構成を示す図である。
【図２０】変形例４に係る検索ログを例示する図である。
【図２１】検索結果を例示する図である。
【図２２】算出された推定値を含むテーブルを例示する図である。
【発明を実施するための形態】
【００１７】
１．構成
図１は、一実施形態に係る検索システム１の構成を示す図である。検索システム１は、ジャンルサーバ１０、検索サーバ２０およびクライアント３０を有する。検索システム１において、ジャンルサーバ１０は、クライアント３０からジャンル識別子が入力されると、そのジャンル識別子に対応するクエリのジャンルスコアを出力する。
【００１８】
ジャンルサーバ１０は、機能要素として、記憶部１１、記憶部１３、生成部１２（第３取得手段、第４取得手段、および推定手段の一例）、呼出部１４、算出部１５（第１取得手段、第２取得手段、および算出手段の一例）および出力部１６を有する。記憶部１１は、検索ログを記憶する。検索ログは、検索のクエリと検索の結果として閲覧された文書の識別子とを含む複数の項目のデータが蓄積されたログである。
【００１９】
図２は、検索ログを例示する図である。この例で、検索ログは複数のデータセット（レコード）を含む。各データセットは、複数の項目に区分されたデータを含む。項目としては、ユーザ名、クエリ、ＵＲＬ（Uniform Resource Locator）、タイムスタンプ、順位、第１位ＵＲＬ、第２位ＵＲＬ、および第３位ＵＲＬが用いられる。検索される文書は、インターネット上に存在する文書である。ここで、「文書」とは、ＨＴＭＬ（HyperText Markup Language）ファイル、音声ファイル、画像ファイルその他のあらゆる形式のファイルをいう。文書の所在は、階層構造を用いた所在情報であるＵＲＬ（第１所在情報の一例）によって示される。ユーザ名は、検索を行ったユーザを示す。クエリは、文書の検索に用いられた語を示す。ＵＲＬは、検索により抽出された複数の文書の中からユーザが閲覧（選択）した文書の所在を示す。タイムスタンプは、検索を行った時刻を示す。順位は、ユーザが閲覧した文書の、検索結果における順位を示す。第１位ＵＲＬは、検索結果において順位が第１位の文書の所在を示す。第２位ＵＲＬおよび第３位ＵＲＬについても同様である。図２の例で、最上行のデータセットは、ユーザ名「ｕ１」のユーザが、２０１０年１月２５日０時０分３８秒にクエリ「ｑ１」を用いて検索を行ったことを示している。さらに、この検索では、ＵＲＬ「ｓ１」、「ｓ２」、および「ｓ４」の文書が、検索結果において第１−３位として提示され、ユーザは、その中からＵＲＬ「ｓ１」で示される文書（検索結果が第１位の文書）を閲覧したことが示されている。
【００２０】
再び図１を参照する。生成部１２は、記憶部１１に記憶されている検索ログから、グラフを生成する。ここで、「グラフ」とは、複数のノードの接続関係をエッジ（リンク）により表した情報、またはその視覚的な表現をいう。
【００２１】
図３は、グラフを例示する図である。丸印はノードを、実線はエッジをそれぞれ示している。この例では、クエリとドメイン（第２所在情報の一例）がノードとして用いられている。以下、クエリのノードを「クエリノード」といい、ドメインのノードを「ドメインノード」（第２所在ノードの一例）という。他のノードについても同様である。ドメインを基準にして見ると、例えば、ドメインノードｄ１にはクエリノードｑ１およびｑ２が接続されており、ドメインノードｄ２にはクエリノードｑ３が接続されている。あるいは、クエリを基準にして見ると、クエリノードｑ３にはドメインノードｄ２，ｄ３，およびｄ５が接続されている。このグラフから、クエリｑ１を入力して、ドメインｄ１に属する文書をユーザが閲覧したことが検索ログに記録されていることが読み取れる。
【００２２】
図４は、グラフの生成処理を説明する図である。ここでは、図２に示される検索ログからグラフを生成する例を説明する。図４中、上段の表は、図２の検索ログに対応している。グラフは以下のように生成される。生成部１２は、記憶部１１から検索ログを読み出す。生成部１２は、読み出した検索ログからノードを抽出する。ここでは、ユーザ名、クエリ、ＵＲＬ、およびドメインがノードとして抽出される。これらの項目は、階層的に配置される。階層は、下位から順に、ユーザ名、クエリ、ＵＲＬ、およびドメインという構造を有している。どの項目をノードとして抽出するか、および、ノードの階層構造はあらかじめ決められている。ドメインは、ＵＲＬから抽出される。ＵＲＬは、「aaa://bbb.ccc.ddd/eee/fff」のように、所定の書式で階層構造が記述される。ドメインは、このうちの階層構造が上位の一部、具体的にはＵＲＬの先頭から、「://」の次の最初の「/」の前までの文字列である。この例では、「aaa://bbb.ccc.ddd」がドメインである。この例でドメインはＵＲＬより階層が上位の概念であり、単一のＵＲＬから複数のドメインが抽出されることはない（すなわち、単一のＵＲＬに複数のドメインが対応することはない）。生成部１２は、データセット毎にエッジを生成する。図４の例では、第１番目のデータセットは、ユーザ名「ｕ１」、クエリ「ｑ１」、およびＵＲＬ「ｓ１」を含んでいる。ＵＲＬ「ｓ１」からドメイン「ｄ１」が抽出される。生成部１２は、第１番目のデータセットに対し、ノードｕ１、ノードｑ１、ノードｓ１、およびノードｄ１をそれぞれエッジで接続する。エッジは、隣接する階層のノード間に設けられる。例えば、ユーザノードとクエリノードは階層が隣接しているのでエッジで接続される。ユーザノードとＵＲＬノード（第１所在ノードの一例）は階層が隣接していない（間にクエリノードが存在する）ので、エッジで直接結ばれない。図４の第２番目のデータセットは、ユーザ名「ｕ１」、クエリ「ｑ１」、およびＵＲＬ「ｓ２」を含んでいる。ＵＲＬ「ｓ２」からドメイン「ｄ２」が抽出される。生成部１２は、第２番目のデータセットに対し、ノードｕ１、ノードｑ１、ノードｓ２、およびノードｄ２をそれぞれエッジで接続する。以下同様に、すべてのデータセットに対して、ノードがエッジで接続される。
【００２３】
生成部１２は、さらに、グラフに付随する付随データを検索ログから生成する。付随データは、ジャンルスコアの算出に用いられるデータを含む。付随データの詳細は後述する。
【００２４】
再び図１を参照する。記憶部１３は、ジャンル辞書を記憶する。ジャンル辞書は、クエリとジャンルの関連性を示すデータベースである。
【００２５】
図５は、ジャンル辞書を例示する図である。ジャンル辞書は、複数のデータセットを含む。各データセットは、複数の項目に区分されたデータを含む。項目としては、クエリ、ジャンル識別子、ジャンル、およびジャンルスコアが用いられる。ジャンルは、文書の分類または種類を示す。ジャンル識別子は、ジャンルの識別子である。ジャンルスコアは、クエリとジャンルとの関連性の高さを示す。この例では、ジャンルスコアの最高点は１．００であり、最低点は０．００である。例えばジャンルスコアが１．００である場合、そのクエリとそのジャンルが高い関連性を有する。図５の第１番目のデータセットは、クエリ「ｑ１」がジャンル「お笑い」（＝ジャンル識別子「１５６７」）に関連しており、そのジャンルスコアが１．００であることを示している。ジャンルスコアの算出は、PageRank、HITS algorithm、SALSA、またはTrustRankその他の周知のアルゴリズムにより行われる。ジャンルスコアの算出は、ジャンルサーバ１０（算出部１５）によって行われてもよいし、検索サーバ２０等ジャンルサーバ１０以外の装置によって行われてもよい。
【００２６】
再び図１を参照する。呼出部１４は、クライアント３０から引数としてジャンル識別子を受け取る。呼出部１４は、受け取ったジャンル識別子に対応するクエリを、記憶部１３に記憶されているジャンル辞書に含まれるクエリの中から抽出する。呼出部１４は、抽出したクエリを算出部１５に出力する。
【００２７】
算出部１５は、呼出部１４から入力されたクエリについて、ジャンルスコアを算出する。出力部１６は、算出部１５により算出されたジャンルスコアをクライアント３０に出力する。
【００２８】
図６は、ジャンルサーバ１０のハードウェア構成を示す図である。ジャンルサーバ１０は、制御部１１０、記憶部１２０、入力部１３０、表示部１４０、通信部１５０を有する。制御部１１０は、他の構成要素を制御する。制御部１１０は、ＣＰＵ（Central Processing Unit）１１１、ＲＡＭ（Random Access Memory）１１２およびＲＯＭ（Read Only Memory）１１３を有する。ＣＰＵ１１１は、種々の演算を行う装置である。ＲＡＭ１１２は、ＣＰＵ１１１がプログラムを実行する際の作業エリアとして機能する記憶装置である。ＲＯＭ１１３は、プログラムやデータを記憶する記憶装置である。記憶部１２０は、内蔵フラッシュメモリや、ＨＤＤ（Hard Disk Drive）、着脱式のメモリカード等の不揮発性の記憶装置を含む。記憶部１２０は、種々のプログラムおよびデータを記憶する。制御部１１０が記憶部１２０に記憶されているジャンルスコア算出プログラムを実行することにより、図１の機能が実現される。記憶部１１、記憶部１３等、情報を記憶する機能は、ＲＡＭ１１２や記憶部１２０に記憶領域を確保し、この記憶領域に情報を記憶する。
【００２９】
入力部１３０は、制御部１１０に情報を入力する。入力部１３０は、キーボードおよびマウス等の入力装置を含む。表示部１４０は、情報を表示する。表示部１４０は、ＬＣＤ（Liquid Crystal Display）や、ＥＬディスプレイ等の表示装置を含む。通信部１５０は、ネットワークを介した通信を行う。
【００３０】
ジャンルスコア算出プログラムを実行している制御部１１０は、生成部１２、呼出部１４、および算出部１５の一例である。通信部１５０は、出力部１６の一例である。制御部１１０と協働している記憶部１２０は、記憶部１１および記憶部１３の一例である。
【００３１】
検索サーバ２０は、クライアント３０等の他の装置からの検索要求に応じて、検索結果を出力する。検索要求は、クエリを含む。検索結果は、そのクエリを用いて検索された文書のＵＲＬおよびその文書の順位を含む。検索サーバ２０は、この機能を実現するためのハードウェア要素（ＣＰＵ、ＲＯＭ、ＲＡＭ、記憶部、入出力部など）およびソフトウェアを有する（図示略）。
【００３２】
クライアント３０は、ユーザによって操作される装置、例えばパーソナルコンピュータまたは携帯電話機である。クライアント３０は、ユーザから入力されたクエリを含む検索要求を検索サーバ２０に送信する。クライアント３０は、検索サーバ２０から送信された検索結果を表示する。また、クライアント３０は、ジャンル識別子を含むジャンルスコアの算出要求を、ジャンルサーバ１０に送信する。クライアント３０は、ジャンルサーバ１０から送信されたジャンルスコアを用いて、クエリの提案を行う。クライアント３０は、この機能を実現するためのハードウェア要素（ＣＰＵ、ＲＯＭ、ＲＡＭ、記憶部、入出力部、表示部など）およびソフトウェアを有する（図示略）。
【００３３】
２．動作
図７は、検索システム１におけるジャンルスコア算出処理を示すフローチャートである。この例では、図７のフローが開始される以前に記憶部１３は図５に示されるジャンル辞書を記憶している。
【００３４】
ステップＳ１００において、ジャンルサーバ１０は、検索ログを蓄積する。すなわち、記憶部１１は、検索サーバから検索ログを受け取り、受け取った検索ログを、記憶している検索ログに追加して蓄積する。検索ログの蓄積は、検索サーバ２０において検索が行われる度、または、前回の蓄積から一定期間経過後など、所定のタイミングで行われる。
【００３５】
ステップＳ１１０において、呼出部１４は、クライアント３０からジャンル識別子を取得する。ジャンル識別子は、クライアント３０から送信されるジャンルスコアの算出要求に含まれる。ここでは、呼出部１４が取得したジャンル識別子が「１５６７」であった場合を例に説明する。この場合、呼出部１４は、ジャンル辞書（図５）に含まれるデータセットの中から、取得したジャンル識別子に対応するクエリを抽出する（ステップＳ１２０）。この例では、クエリｑ１、ｑ３およびｑ４が抽出される。呼出部１４は、抽出したクエリおよびそのジャンルスコアを含むデータセットを、算出部１５に出力する。
【００３６】
ステップＳ１３０において、生成部１２は、記憶部１１に記憶されている検索ログを用いてグラフおよび付随データを生成する。
ステップＳ１４０において、算出部１５は、生成部１２が生成したグラフを用いて、他のクエリからジャンルスコアを伝播させることによって、対象となるクエリのジャンルスコアを算出する。詳細には以下のとおりである。まず、算出部１５は、生成部１２からグラフを取得する。
【００３７】
図８は、この例で取得されたグラフを示す図である。この例で、グラフは、クエリノードおよびドメインノードを含んでいる。クエリノードは、クエリｑ１、ｑ２、ｑ３、およびｑ４のノードを含んでいる。ドメインノードは、ドメインｄ１、ｄ２およびｄ３のノードを含んでいる。クエリノードｑ１は、ドメインノードｄ１およびｄ２と接続されている。クエリノードｑ２は、ドメインノードｄ１およびｄ２と接続されている。クエリノードｑ３は、ドメインノードｄ１と接続されている。クエリノードｑ４は、ドメインノードｄ２およびｄ３と接続されている。
【００３８】
図９は、図８のグラフの付随データを示す図である。付随データは、複数のデータセットを含む。各データセットは、クエリ、ドメイン、ユニークユーザ数（ＮＵＵ）、ユニークユーザ率（ＲＵＵ）、および検索回数（Ｓｅａｒｃｈ）のデータを含む。ユニークユーザ数は、対応するクエリを用いて検索された文書のうち、対応するドメインに属する文書を閲覧したユニークユーザ数を示す。ユニークユーザとは、ある文書を特定の期間のうちに訪れた人のユニークな数をいう。同一期間内に同一人物がその文書を例えば５回閲覧した場合でも、ユニークユーザ数は１人である。図９の第１番目のデータセットは、クエリｑ１を用いて検索された文書のうち、ドメインｄ１に属する文書を閲覧したユニークユーザ数が９０人であることを示している。ユニークユーザ率は、対応するクエリを用いて検索された文書のうち、対応するドメインに属する文書を閲覧したユニークユーザの割合を示す。図９の第１番目のデータセットは、クエリｑ１を用いて検索された文書のうち、ドメインｄ１に属する文書を閲覧したユニークユーザの割合が０．９（＝９０％）であることを示している。これは、クエリｑ１を用いて検索された文書を閲覧した全ユニークユーザ（９０＋１０＝１００人）のうち、ドメインｄ１に属する文書を閲覧したユニークユーザ（９０人）が占める割合である。検索回数は、対応するクエリを用いて検索が行われた回数を示す。図９の第１番目のデータセットは、クエリｑ１を用いて２００回の検索が行われたことを示す。
【００３９】
再び図７を参照し、ステップＳ１４０の処理を引き続き説明する。算出部１５は、クエリおよびジャンルスコアを含むデータセットを呼出部１４から取得する。ステップＳ１３０において、算出部１５は、取得したデータセットに含まれるクエリのうち対象となるクエリについて、グラフの付随データを用いてジャンルスコアを算出する処理を行う。この例では、算出部１５は、クエリｑ１、ｑ２およびｑ３のそれぞれについて、ジャンルスコアを算出する。
【００４０】
図１０は、ステップＳ１４０のジャンルスコア算出処理の一例を示すフローチャートである。ステップＳ２００において、算出部１５は、グラフに含まれるすべてのクエリについて、ジャンルスコアの初期値を決定する。初期値は、以下のとおり決定される。まず、ステップＳ１１０において出力されたデータセットに含まれるクエリ（クエリｑ１、ｑ２、ｑ４）については、このデータセットに含まれるジャンルスコアが初期値として用いられる。次に、このデータセットに含まれないクエリ（クエリｑ３）、すなわち、ジャンル辞書にジャンルスコアが記載されていないクエリについては、初期値として０．００が用いられる。この例では、図５のジャンル辞書に基づいて、クエリｑ１−ｑ４のジャンルスコアの初期値ＪＳiniが次式（１）のように決定される。
【数１】
0005519406.tif 000002
【００４１】
ステップＳ２１０において、算出部１５は、ジャンルスコアの伝播処理の対象となるクエリ（以下「対象クエリ」という）を特定する。算出部１５は、所定の条件を満たすクエリを、対象クエリとして特定する。この例では、「ジャンルスコアの初期値がゼロである」（＝ジャンル辞書にジャンルスコアが記録されてない）という条件が、対象クエリを特定する条件として用いられる。式（１）の例では、クエリｑ３だけが伝播処理の対象として特定され、クエリｑ１、ｑ２およびｑ４は伝播処理の対象とはならない。ここで、「ジャンルスコアの伝播」とは、あるクエリのジャンルスコアを、他のクエリのジャンルスコアを用いて算出することをいう。例えば、クエリｑ１およびｑ３のジャンルスコアを用いてクエリｑ２のジャンルスコアを算出することを、「クエリｑ１およびｑ３のジャンルスコアをクエリｑ２に伝播させる」という。
【００４２】
ステップＳ２２０において、算出部１５は、対象クエリの中から、基点となるクエリを特定する。以下、基点となるクエリを「基点クエリ」といい、基点クエリのノードを「基点ノード」という。基点クエリは、あらかじめ決められたアルゴリズムにより決定される。このアルゴリズムは、例えば、対象クエリの中から、クエリを順番に一つずつ基点クエリとして特定するアルゴリズムである。この場合、対象クエリはアイウエオ順、アルファベット順、文字コード順、またはＩＤ番号順などの規則にしたがってソートされる。この例では、対象クエリがクエリｑ２だけなので、クエリｑ２が基点クエリとして特定される。
【００４３】
ステップＳ２３０において、算出部１５は、基点クエリを含む経路についてエッジの重みを算出する。ここで、「経路」とは、グラフ上の２つのノードについて、エッジおよびノードを介した接続関係をいう。図８の例で、クエリノードｑ２は、クエリノードｑ１およびｑ３と、ドメインノードを介して接続されている。この接続は、以下の（Ａ）〜（Ｃ）の３つの経路を含んでいる。
（Ａ）ドメインノードｄ１を中継ノードとしてクエリノードｑ１と接続される経路Ａ。
（Ｂ）ドメインノードｄ１を中継ノードとしてクエリノードｑ３と接続される経路Ｂ。
（Ｃ）ドメインノードｄ２を中継ノードとしてクエリノードｑ１と接続される経路Ｃ。
これらの経路は、中継ノードとなるノードによって以下の２つに分類される。
（１）ドメインノードｄ１を中継ノードとする経路群１（経路ＡおよびＢ）。
（２）ドメインノードｄ２を中継ノードとする経路群２（経路Ｃ）。
【００４４】
算出部１５は、基点ノードｑｒと、中継ノードであるドメインノードｄｊと、他のクエリノードｑｉとを結ぶ経路のエッジの重みＰqi,dj,qrを、次式（２）により算出する。
【数２】
0005519406.tif 000003
ここで、ＲＵＵqi,djは、クエリｑｉを用いて検索された文書の中からドメインｄｊに属する文書を閲覧したユニークユーザの割合を示す。
【００４５】
ステップＳ２４０において、算出部１５は、次式（３）により、基点クエリｑｒのジャンルスコアＪＳ（ｑｒ）を算出する。すなわち、算出部１５は、他のクエリのジャンルスコアを起点クエリに伝播させる。
【数３】
0005519406.tif 000004
ここで、Ｓｅａｒｃｈqiは、クエリｑｉを用いて検索が行われた回数を示す。なお、式（３）においてｑｉはｑｉ＝ｑｒとなる場合を含まない。
【００４６】
式（２）および式（３）を用いた計算例を、基点クエリがクエリｑ２である場合を例として具体的に説明する。算出部１５は、各経路について、式（２）を用いてエッジの重みＰを算出する。
【数４】
0005519406.tif 000005
次に、算出部１５は、式（３）を用いてジャンルスコアＪＳを算出する。ここでは紙面の都合により、経路群１と経路群２を分けて計算する。まず、経路群１については、
【数５】
0005519406.tif 000006
である。経路群２については、
【数６】
0005519406.tif 000007
である。式（５）および式（６）から、
【数７】
0005519406.tif 000008
が得られる。
【００４７】
ステップＳ２５０において、算出部１５は、すべての対象クエリについて、そのクエリを基点クエリとしてジャンルスコアの伝播処理を行ったか判断する。まだ基点クエリとなっていない対象クエリがあった場合（Ｓ２５０：ＮＯ）、算出部１５は、処理をステップＳ２２０に移行する。すべての対象クエリを基点クエリとして伝播処理が行われた場合（Ｓ２５０：ＹＥＳ）、算出部１５は、処理をステップＳ２６０に移行する。
【００４８】
ステップＳ２６０において、算出部１５は、終了条件が満たされたか判断する。終了条件が満たされたと判断された場合（Ｓ２６０：ＹＥＳ）、算出部１５は、図１０の処理を終了する。終了条件が満たされていないと判断された場合（Ｓ２６０：ＮＯ）、算出部１５は、処理を再びステップＳ２２０に移行する。この例で、終了条件は、（１）ジャンルスコアが収束した、および（２）ステップＳ２２０−２５０の処理を一定回数（例えば１０周）繰り返した、という条件の少なくともいずれか一方が満たされた、という条件である。
【００４９】
例えば、対象クエリがｑ１、ｑ２、…、ｑ１０の１０個である場合、まずクエリｑ１を対象クエリとして、ジャンルスコアの伝播処理が行われる。次に、クエリｑ２を対象クエリとして、ジャンルスコアの伝播処理が行われる。以下同様に、クエリｑ１０まで、一つずつ順番に対象クエリとして、ジャンルスコアの伝播処理が行われる。クエリｑ１、ｑ２、…、ｑ１０の各々について１回ずつ伝播処理が終了したとき、「伝播処理を１周させた」という。伝播処理を１周させると、終了条件が満たされたか判断される。終了条件が満たされていなかった場合、第２周の伝播処理が行われる。以下、終了条件が満たされるまで、第３周、第４周、…と伝播処理が繰り返し行われる。
【００５０】
ふたたび図７を参照する。ステップＳ１５０において、出力部１６は、ジャンルスコアを含むデータをクライアント３０に出力する。さらに、出力部１６は、更新されたジャンルスコアをジャンル辞書に書き込む。
【００５１】
図１１は、ジャンルサーバ１０からの出力データを例示する図である。出力データは、複数のデータセットを含む。各データセットは、クエリと、そのクエリのジャンルスコアとを含む。クライアント３０は、ジャンルサーバ１０から出力データを受信する。こうして、クライアント３０は、ジャンルスコアの算出要求に対してジャンルスコアを得ることができる。クライアント３０は、受信した出力データに含まれるクエリのうち、所定の条件を満たすもの（例えば、ジャンルスコアが上位の５件）を、推薦クエリとして表示する。
【００５２】
図１２は、対比例としてのグラフを示す図である。この対比例で、グラフは、クエリノードおよびＵＲＬノードを含んでいる。このグラフに基づいて、式（２）および（３）を用いてジャンルスコアを算出することも可能である（この場合、数式中のドメインノードに関する項はＵＲＬノードに置き換えられる）。しかし、ＵＲＬノードを用いた場合、ドメインノードを用いた場合と比較してエッジの密度は粗となる。これは、多くの場合、検索サービスを通して検索できる文書がスパース（まばら、わずか）であることによる。ある２つのクエリについて、一方のクエリから他方のクエリにジャンルスコアを伝播させようとした場合、これらのクエリのクエリノードが共通のＵＲＬノードに接続されていないと、ジャンルスコアを伝播させることができない。すなわち、図１２のグラフを用いた場合、共通のＵＲＬノードに接続されていないクエリノードに対しては、ジャンルスコアを伝播させることができないという問題がある。これに対し、ジャンルサーバ１０によれば、共通のＵＲＬノードに接続されていないクエリノードであっても、共通のドメインノードに接続されているクエリノードに対しては、ジャンルスコアを伝播させることができる。このような構成により、より柔軟にグラフを作成することが可能になる。また、ジャンルスコアの算出の際に複数のクエリからジャンルスコアが伝播される場合には、複数のクエリとの関連性を示す指標を一時に算出することができる。
【００５３】
別の対比例として、検索ログの内容が制限される場合がある。例えば、クエリ毎の検索回数はログとして記録されるが、ユーザ毎の検索行動履歴または文書毎の閲覧率はログとして記録されない場合がある。このような制限は、例えばハードウェアまたはソフトウェアのリソース不足または検索サーバの仕様に起因する。例えば、文書毎の閲覧率がログとして記録されることが前提となっており、これを用いて文書毎の重要度を算出し、さらに重要度を用いてジャンルスコアを算出する技術は、検索ログの内容が制限される環境には適用できないという問題がある。これに対し、ジャンルサーバ１０によれば、ユーザ毎の検索行動履歴または文書毎の閲覧率がログとして記録されない場合であっても、ジャンルスコアを伝播させることができる。
【００５４】
以上で説明したように、ジャンルサーバ１０によれば、従来ジャンルスコアを算出することができなかったクエリについても、ジャンルスコアを算出することができる。ドメインノードを含むグラフを用いた場合には、ＵＲＬノードを用いた場合と比較して、より広範囲にジャンルスコアを伝播させることができる。
【００５５】
３．他の実施形態
本発明は上述の実施形態に限定されるものではなく、種々の変形実施が可能である。以下、変形例をいくつか説明する。以下の変形例のうち、２つ以上のものが組み合わせて用いられてもよい。
【００５６】
３−１．変形例１
図１３は、変形例１に係るグラフを例示する図である。生成部１２が生成するグラフの構造は、図３で例示したものに限定されない。図１３の例で、グラフは、クエリノード、ＵＲＬノードおよびドメインノードを含む。これらのノードは、階層的に配置されている。この例では、下位から、クエリノード、ＵＲＬノード、ドメインノードの順で配置されている。この例では、算出部１５は、クエリノードとＵＲＬノードのエッジも考慮して、ジャンルスコアを伝播する。
【００５７】
図１４は、図１３のグラフに付随するデータを示す図である。このデータは、複数のデータセットを含む。各データセットは、クエリ、ＵＲＬ、ドメイン、ＮＵＵ、ＲＵＵ、検索回数、およびページビュー（ＰＶ）のデータを含む。この例で、ユニークユーザ数は、対応するクエリを用いて検索された文書のうち、対応するＵＲＬにある文書を閲覧したユニークユーザ数を示す。図１４の第１番目のデータセットは、クエリｑ１を用いて検索された文書のうち、ＵＲＬｓ１にある文書を閲覧したユニークユーザが９０人いたことを示している。また、ページビューは、対応するＵＲＬにある文書が閲覧された回数を示す。図１４の第１番目のデータセットは、ＵＲＬｓ１にある文書が８０回閲覧されたことを示す。
【００５８】
算出部１５は、式（２）に代わり次式（８）に従ってエッジの重みＰを算出する。
【数８】
0005519406.tif 000009
次に、算出部１５は、式（３）に従ってジャンルスコアＪＳを算出する。
【００５９】
ここで、クエリｑ２が基点クエリである場合を例に、計算の具体例を示す。図１４のデータと式（２）から、エッジの重みＰq1,s1,d1,s2,q2は以下のとおり算出される。
【数９】
0005519406.tif 000010
さらに、式（３）から、ジャンルスコアＪＳは以下のとおり算出される。
【数１０】
0005519406.tif 000011
【００６０】
３−２．変形例２
ジャンルスコアを算出する式は式（３）に限定されない。重み付け係数を用いて式（３）が修正されてもよい。変形例２では、次式（１１）によりジャンルスコアが算出される。
【数１１】
0005519406.tif 000012
ここで、係数Ｗｅｉｇｈｔdjは、ドメインｄｊと対象となるジャンルとの間の相関を示すパラメータ（以下「伝播調整パラメータ」という）である。この例で、係数Ｗｅｉｇｈｔdjは、相関係数βであり、ジャンルスコアＪＳ、検索回数Ｓｅａｒｃｈ、ユニークユーザ率ＲＵＵの関数である。
【数１２】
0005519406.tif 000013
以下、式（１１）によるジャンルスコアの算出を、具体例を用いて説明する。
【００６１】
図１５は、検索システム１の変形例２に係る動作を示すフローチャートである。図１５のフローは、ステップＳ２２０とＳ２３０との間にステップＳ３００が挿入されている点において図１０のフローチャートと相違している。ステップＳ３００において、算出部１５は、式（１２）に従って、各ドメインについて伝播調整パラメータを算出する。ステップＳ２４０において、算出部１５は、式（１１）に従ってジャンルスコアを算出する。以下、計算の具体例を説明する。
【００６２】
図１６は、変形例２に係るグラフを例示する図である。この例のグラフは、図１３のグラフと同じ階層構造を有している。
【００６３】
図１７は、図１６のグラフに付随するデータを示す図である。このデータは、複数のデータセットを含む。各データセットは、クエリ、ＵＲＬ、ドメイン、ＮＵＵ、ＲＵＵ、および検索回数のデータを含む。
【００６４】
算出部１５は、ステップＳ３００において伝播調整パラメータＷｅｉｇｈｔを算出する。図１７のデータと式（１２）から、伝播調整パラメータＷｅｉｇｈｔd2は以下のとおり算出される。
【数１３】
0005519406.tif 000014
ここでは、Ｗｅｉｇｈｔd2＝０．００１であった場合を例に説明する。
【００６５】
算出部１５は、ステップＳ２３０において式（２）に従ってエッジの重みＰを算出する。ここで、クエリｑ２が基点クエリである場合を例に、計算の具体例を示す。図１７のデータと式（２）から、エッジの重みＰq1,q2は以下のとおり算出される。
【数１４】
0005519406.tif 000015
【００６６】
算出部１５は、ステップＳ２４０においてジャンルスコアＪＳを算出する。図１７のデータと式（１１）から、ジャンルスコアＪＳ（ｑ２）は以下のとおり算出される。
【数１５】
0005519406.tif 000016
【００６７】
別の例で、図１６のグラフでクエリノードｑ２とクエリノードｑ４がドメインノードｄ４に属するＵＲＬノードを介して接続されていた場合、ジャンルスコアＪＳ（ｑ２）は以下のとおり算出される。
【数１６】
0005519406.tif 000017
【００６８】
例えばWikipedia（登録商標）のような特定のジャンルとの関連性が薄い文書があった場合、従来のように単にクエリノードとＵＲＬノードだけを含むグラフを用いたのでは、ジャンルとの関連性を正確に評価できなかった。例えば、図１２のグラフだけを用いてジャンル辞書を用いなかった場合、あるＵＲＬ（すなわち文書そのもの）が特定のジャンルに属するかどうかを判断するのは容易ではない。一例として、Wikipediaのような辞書サイトがある。辞書サイトは種々のジャンルのクエリに紐付いていると考えられるので、特定の単一のジャンルを有さない場合がある。ＵＲＬノードとクエリノードの繋がりだけを考慮した場合、特定のジャンルを有さないＵＲＬノードを介してジャンルスコアが伝播されるという問題がある。ジャンルサーバ１０によれば、共通するジャンルに関連付けられたクエリノードからジャンルスコアが伝播される。本変形例の構成によれば、ドメイン毎に集約された伝播調整パラメータを用いることで伝播されるジャンルスコアをドメイン単位で抑制し、より精度の高いジャンルスコアを算出することができる。
【００６９】
３−３．変形例３
図１８は、変形例３に係るグラフを例示する図である。図１８の例で、グラフは、クエリノード、ＵＲＬノード、ドメインノードおよびユーザノードを含む。これらのノードは、階層的に配置されている。この例では、下位から、クエリノード、ＵＲＬノード、ドメインノードおよびユーザノードの順で配置されている。ドメインノードとユーザノードは同じ階層に配置されている。
【００７０】
この例で、ジャンルスコアは、ドメインノードを介する経路に加え、ＵＲＬノードおよびユーザノードを介して伝播される。例えば、クエリｑ１のジャンルスコアは、ＵＲＬノードｓ２、ユーザノードｕ２、およびＵＲＬノードｓ３を介して、クエリｑ２に伝播される。クエリｑ２のジャンルスコアは、変形例２で説明したように、ドメインノードを基準とする重み付け係数を用いて算出される。
【００７１】
この構成によれば、クエリノードはＵＲＬノードまたはユーザノードを介して伝播されるので、単にクエリノードとＵＲＬノードとのみを含むグラフを用いた場合と比較して、より網羅性の高いグラフが生成される。すなわち、より多くのクエリにジャンルスコアを与えることが可能である。
【００７２】
３−４．変形例４
図１９は、変形例４に係る検索システム１の構成を示す図である。この例で、ジャンルサーバ１０は、図１の構成に加え、さらに記憶部１７を有する。記憶部１７は、生成部１２が生成したグラフのデータを記憶する。
【００７３】
図２０は、変形例４に係る検索ログを例示する図である。この例の検索ログにおいて、各データセットは、クエリおよび検索回数のデータを含むが、ユーザおよび閲覧された文書（ＵＲＬ）のデータは含まれていない。上述の実施形態において、エッジの重みＰは、クエリの検索回数や、文書を閲覧したユニークユーザ数を用いて算出された。しかし、この例のように、検索ログがユーザおよび閲覧された文書（ＵＲＬ）のデータを含んでいない場合には、上述の実施形態と同様の方法ではエッジの重みＰを算出することができない。そこでこの例で、生成部１２は、記憶部１１に記憶されている検索ログに加え、検索サーバ２０から取得したデータを用いて、グラフを生成する。詳細には以下のとおりである。
【００７４】
生成部１２は、記憶部１１から検索ログを取得する。生成部１２は、取得した検索ログから、クエリを抽出する。図２０の例では、クエリｑ１およびｑ２が抽出される。生成部１２は、抽出したクエリを含む検索要求を、検索サーバ２０に送信する。生成部１２（ジャンルサーバ１０）から検索要求を受信すると、検索サーバ２０は、検索を行い、その結果をジャンルサーバ１０に送信する。
【００７５】
図２１は、検索結果を例示する図である。この例で、検索結果は、複数のデータセットを含む。各データセットは、クエリ、ＵＲＬ、および順位のデータを含む。図２１の例で第１−第２番目のデータセットは、クエリｑ１を用いて検索を行うと、ＵＲＬｓ１の文書が第１位、ＵＲＬｓ２の文書が第２位であることを示している。
【００７６】
生成部１２は、検索結果から、欠損データの推定値を算出する。欠損データとは、ジャンルスコアの算出に用いられるデータのうち、検索ログに含まれていないデータをいう。例えば、式（２）および（３）に従ってジャンルスコアを算出する場合、ユニークユーザ率ＲＵＵが欠損データである。欠損データの推定値は、例えば以下のように算出される。各ＵＲＬには、順位に応じて検索回数が割り当てられる。例えば、第１位：第２位＝２：１の割合で検索回数が割り当てられる。図２０の例では、１５８回が、ＵＲＬｓ１（第１位の文書）とＵＲＬｓ２（第２位の文書）に２：１の割合でユニークユーザ数が割り当てられる。すなわち、生成部１２は、クエリｑ１を用いて行われた全１５８回の検索のうち、１０５．３３人のユニークユーザがＵＲＬｓ１に割り当てられ、５２．６７人のユニークユーザがＵＲＬｓ２に割り当てられる。生成部１２は、このようにして割り当てられたユニークユーザ数を用いて、ユニークユーザ率の推定値を算出する。
【００７７】
図２２は、算出された推定値を含むテーブルを例示する図である。生成部１２は、このようにして算出されたユニークユーザ率の推定値を用いてグラフの付随データを生成する。
【００７８】
この構成によれば、検索ログが図２に例示したデータを完全に含んでいない場合であっても、欠損しているデータを推定することにより、ジャンルスコアを算出することができる。
【００７９】
３−５．他の変形例
検索ログの生成は、ジャンルサーバ１０自身によって行われてもよいし、ジャンルサーバ１０以外の装置（例えば検索サーバ２０）によって行われてもよい。ジャンルサーバ１０が検索ログを生成する場合、検索サーバ２０は、検索を行う度に、検索結果をジャンルサーバ１０に送信する。ジャンルサーバ１０の算出部１５は、受信した検索結果を、記憶部１１に記憶されている検索ログに追加する。検索サーバ２０が検索ログを生成する場合、検索サーバ２０は、検索ログを記憶する記憶部を有している。検索サーバ２０は、検索を行う度に、検索結果を検索ログに追加する。検索サーバ２０は、所定のタイミング（前回検索ログを送信してから一定期間経過後や、ジャンルサーバ１０から要求があった時など）で、検索ログをジャンルサーバ１０に送信する。ジャンルサーバ１０の記憶部１１は、受信した検索ログを記憶する。
【００８０】
検索ログの書式は、図２で例示したものに限定されない。例えば、図２の例では、検索の結果として得られた文書のＵＲＬが第１位〜第３位まで記録されているが、記録されるＵＲＬの数はこれに限定されない。検索ログに記録されるＵＲＬの数は、例えば、システムの構成（例えばハードウェアリソースの量）により制限される。
【００８１】
また、ジャンルサーバ１０は、記憶部１１を有していなくてもよい。この場合、ジャンルサーバ１０とは異なる別の装置が、記憶部１１を有する。ジャンルサーバ１０は、検索ログにアクセスするときは、その別の装置を介して検索ログにアクセスする。
【００８２】
ジャンル識別子の指定方法は、実施形態で説明したものに限定されない。すなわち、呼出部１４への入力はジャンル識別子に限定されない。ジャンル識別子ではなく、クエリが呼出部１４に入力されてもよい。この場合、呼出部１４は、ジャンル辞書を参照し、入力されたクエリに対応するジャンルと同じジャンルに対応するクエリを抽出する。図５の例では、クエリｑ１が入力されると、呼出部１４は、クエリｑ１に対応するジャンル（「お笑い」）と同じジャンルに対応する、クエリｑ３およびｑ４を抽出する。
【００８３】
検索対象となる文書は、インターネット上のファイルに限定されない。ローカルネットワークまたはスタンドアローンコンピュータ上のファイルに対し、実施形態で説明したジャンルスコア算出技術が適用されてもよい。例えばスタンドアローンコンピュータ上のファイルに対してこのジャンルスコア算出技術を適用する場合、ジャンルサーバ１０、検索サーバ２０およびクライアント３０としての機能をすべて、単一のコンピュータが有する。ＵＲＬは、ドライブ名およびフォルダ（ディレクトリ）名を含めたファイル名に読み替えられる。ドメインは、より上位の階層のフォルダ名に読み替えられる。
【００８４】
ＵＲＬからドメインを抽出する方法は、実施形態で説明したものに限定されない。例えば、ＵＲＬの先頭から、「://」の次の２番目の「/」の前までの文字列がドメインとして抽出されてもよい。この場合、ＵＲＬが「aaa://bbb.ccc.ddd/eee/fff」であったときは、「aaa://bbb.ccc.ddd/eee」という文字列がドメインとして抽出される。
【００８５】
ジャンル辞書のデータ構造は図５に示されるものに限定されない。例えば、ジャンル識別子とジャンルのうちどちらか一方は省略されてもよい。あるいは、一のクエリに複数のジャンルが関連付けられていてもよい。この場合、複数のジャンルが関連づけられたクエリに対して、呼出部１４は、ステップＳ１２０において、対象となっているジャンルを含むデータセットだけを抽出する。
【００８６】
ジャンル識別子（ジャンルスコアの算出要求）の入力元と、ジャンルスコアの出力先の装置は同一でなくてもよい。例えば、ジャンルサーバ１０は、ジャンル識別子の入力元であるクライアント３０とは別の装置に、ジャンルスコアを出力してもよい。あるいは、ジャンルサーバ１０は、クライアント３０とは別の装置から入力されたジャンル識別子に対して、クライアント３０にジャンルスコアを出力してもよい。
【００８７】
グラフのデータ構造は実施形態で説明したものに限定されない。実施形態で付随データとして説明したテーブルだけが、グラフとして処理されてもよい。
【００８８】
対象クエリを特定する条件は、実施形態で説明したものに限定されない。実施形態において、算出部１５は、ジャンルスコアの初期値がゼロのクエリを対象クエリとしたが、ジャンルスコアの初期値が所定のしきい値以下のクエリを対象クエリとしてもよい。あるいは、算出部１５は、ジャンルスコアの初期値を算出せず、単にジャンル辞書にジャンルスコアが記載されていないクエリを対象クエリとしてもよい。さらに別の例で、算出部１５は、ユーザにより指定されたクエリを対象クエリとして特定してもよい。
【００８９】
中継ノードとなるノードは、ドメインノードに限定されない。ユーザノード、ＵＲＬノード等、ドメインノード以外のノードが中継ノードとなってもよい。
【００９０】
エッジの重み（すなわちノード間の繋がりの強さ）の算出に用いられるアルゴリズムは実施形態で説明したものに限定されない。例えば、ハイパーリンクの構造分析に用いられるPageRank、HITS algorithm、SALSA、またはTrustRankなど、周知のアルゴリズムが用いられてもよい。
また、エッジの重みは、グラフを生成する際にあわせて計算されてもよい。すなわち、図１０のフローにおいて、ステップＳ２３０の処理は、ステップＳ２２０−Ｓ２５０の処理ループの外側にあってもよい。
【００９１】
ジャンルスコア算出処理のフローは、図７に示されるものに限定されない。例えば、ステップＳ１５０におけるジャンル辞書の書き込み、すなわちジャンル辞書の更新は省略されてもよい。また別の例で、ステップＳ１２０の処理とステップＳ１３０の処理の順番は入れ替えられてもよい。
【００９２】
ジャンルスコアの算出要求（ジャンル識別子）を送信する装置と、この要求に対する応答を受信する装置とは異なっていてもよい。
【００９３】
クライアント３０におけるジャンルスコアの利用方法は、クエリの推薦に限定されない。ジャンルスコアを表示する処理、またはジャンルを推薦する処理等、クエリの推薦以外の処理が行われてもよい。
【００９４】
図１に示される機能を実現するためのハードウェア構成は、図６で説明されたものに限定されない。例えば、汎用のＣＰＵに代わり、特定の処理を行うプロセッサが用いられてもよい。
【００９５】
上述の実施形態においてＣＰＵ１１１によって実行されるプログラムは、磁気記録媒体（磁気テープ、磁気ディスク（ＨＤＤ、ＦＤ（Flexible Disk））など）、光記録媒体（光ディスク（ＣＤ（Compact Disk）、ＤＶＤ（Digital Versatile Disk））など）、光磁気記録媒体、半導体メモリ（フラッシュＲＯＭなど）などのコンピュータ読取り可能な記録媒体に記憶した状態で提供されてもよい。また、このプログラムは、インターネットのようなネットワーク経由でダウンロードされてもよい。
【符号の説明】
【００９６】
１…検索システム、１０…ジャンルサーバ、１１…記憶部、１２…生成部、１３…記憶部、１４…呼出部、１５…算出部、１６…出力部、１７…記憶部、２０…検索サーバ、３０…クライアント、１１０…制御部、１１１…ＣＰＵ、１１２…ＲＡＭ、１１３…ＲＯＭ、１２０…記憶部、１３０…入力部、１４０…表示部、１５０…通信部
【図１】
0005519406.tif 000018
【図２】
0005519406.tif 000019
【図３】
0005519406.tif 000020
【図４】
0005519406.tif 000021
【図５】
0005519406.tif 000022
【図６】
0005519406.tif 000023
【図７】
0005519406.tif 000024
【図８】
0005519406.tif 000025
【図９】
0005519406.tif 000026
【図１０】
0005519406.tif 000027
【図１１】
0005519406.tif 000028
【図１２】
0005519406.tif 000029
【図１３】
0005519406.tif 000030
【図１４】
0005519406.tif 000031
【図１５】
0005519406.tif 000032
【図１６】
0005519406.tif 000033
【図１７】
0005519406.tif 000034
【図１８】
0005519406.tif 000035
【図１９】
0005519406.tif 000036
【図２０】
0005519406.tif 000037
【図２１】
0005519406.tif 000038
【図２２】
0005519406.tif 000039