図面 (/)

技術 検索要求制御装置、検索要求制御プログラム及び検索要求制御方法

出願人 富士通株式会社
発明者 山田樹一
出願日 2011年1月28日 (8年5ヶ月経過) 出願番号 2011-017223
公開日 2012年8月23日 (6年10ヶ月経過) 公開番号 2012-159887
状態 特許登録済
技術分野 検索装置
主要キーワード パス参照 部分集合毎 平均レスポンス 参照パス 到着イベント 各検索要求 一括検索 マップ構造
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(2012年8月23日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (17)

課題

ハイトラフィック技術にインデックス技術を採用した場合のデータの検索効率を向上させる。

解決手段

検索要求制御装置1は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割部11と、検索要求集合分割部11によって分割された複数の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出部12と、平均レスポンス算出部12によって算出された平均レスポンスが最短の複数の部分集合について、処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理部13とを備える。

概要

背景

近年、データベースシステム等のデータの検索において、検索要求が同時に送られてくる場合であってもデータの検索時間を短縮できるハイトラフィック技術が用いられることがある。ハイトラフィック技術とは、複数の検索要求から1つのオートマトンを生成し、生成したオートマトンを利用して検索対象データマッチングさせる技術である。図13は、ハイトラフィック技術を用いたデータの検索の一例を説明する図である。

図13に示すように、例えばデータベースシステムは、同時に送られてくる複数の検索要求1〜4を一体化して、一体化した検索要求に対するデータを検索対象データから一括して検索し、検索した結果を検索要求に振り分ける。これにより、同時に送られてくる検索要求の多重度が上がっても、検索要求に対するデータを一括して検索するので、データの検索時間の予測を可能とする。

また、データの検索時間を短縮する他の技術として、インデックス技術がある。インデックス技術とは、リレーショナルデータベースにおけるテーブルにおいて、カラムにある値を持つレコードを直接選択(検索)したり、XML文書等の構造を持つデータにおいて、特定のパス指し示すデータを直接検索させたりする技術である。図14は、インデックス技術を用いたデータの検索の一例を説明する図である。

図14に示すように、検索要求1では、インデックスのパス2及びパス4が指し示すデータd2、d4(d2’、d4’)を検索し、検索要求2では、インデックスのパス3及びパス4が指し示すデータd3、d4(d3’、d4’)を検索する。このため、検索要求1及び検索要求2は、全体のデータを検索することなく最低限必要なデータだけを検索するので、データの検索時間を短縮できる。

ところが、各検索要求において、検索するデータが重複する場合がある。図14の例では、検索要求1及び検索要求2では、パス4が指し示すデータd4(d4’)がD1(D1’)に示すように重複している。この場合には、重複したデータd4(d4’)が2回検索されるので、検索に無駄が生じる分、データの検索効率が悪くなる。

そこで、データの検索時間を短縮する他の技術として、ハイトラフィック技術にインデックス技術を採用した技術も考えられる。この技術では、同時に送られてくる複数の検索要求を一体化して、一体化した検索要求のインデックスのパスの和集合を作成し、作成したパスの和集合に属するパスが指し示すデータを一括して検索する。図15は、ハイトラフィック技術にインデックス技術を採用した技術を説明する図である。

図15に示すように、検索要求1では、インデックスのパス2及びパス4が指し示すデータを検索し、検索要求2では、インデックスのパス3及びパス4が指し示すデータを検索する。この場合には、検索要求1及び検索要求2のインデックスのパスの和集合パス2〜4を作成し、作成した和集合に属するパスが指し示すデータd2〜d4(d2’〜d4’)を一括して検索する。これにより、各検索要求において、検索するデータが重複する場合であっても、D2(D2’)に示すように重複するデータを1度だけ検索するので、データの検索効率が向上する。

また、ほぼ同時に送られてくる複数の検索要求である検索式を、それぞれの予測検索速度に基づき複数の検索式集合に振り分け、予測検索速度の速い集合から順次検索を行い、対応する検索式集合内の検索式を纏めて一括検索する技術が開示されている。

概要

ハイトラフィック技術にインデックス技術を採用した場合のデータの検索効率を向上させる。検索要求制御装置1は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割部11と、検索要求集合分割部11によって分割された複数の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出部12と、平均レスポンス算出部12によって算出された平均レスポンスが最短の複数の部分集合について、処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理部13とを備える。

目的

なお、上記課題は、データベースシステムにおけるデータの検索だけではなく、インターネット等の検索エンジンにおけるデータの検索にも同様に生じる課題である

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割部と、前記検索要求集合分割部によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出部と、前記平均レスポンス算出部によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理部とを有することを特徴とする検索要求制御装置

請求項2

前記検索要求集合分割部は、前記検索要求集合を、当該検索要求集合の直前に取得された検索要求集合に関わる検索要求の実行中に、複数の部分集合に分割することを特徴とする請求項1に記載の検索要求制御装置。

請求項3

前記検索処理部は、前記処理順序が先行する部分集合に含まれる検索要求を前記検索要求集合の直前に取得された検索要求の処理後に処理し、前記処理順序が後行する部分集合に含まれる検索要求を前記検索要求集合の直後に取得された検索要求と併合して処理することを特徴とする請求項1または請求項2に記載の検索要求制御装置。

請求項4

所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割手順と、前記検索要求集合分割手順によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出手順と、前記平均レスポンス算出手順によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理手順とをコンピュータに実行させることを特徴とする検索要求制御プログラム

請求項5

検索要求制御装置が検索要求を制御する検索要求制御方法であって、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割工程と、前記検索要求集合分割工程によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出工程と、前記平均レスポンス算出工程によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理工程とを含むことを特徴とする検索要求制御方法。

技術分野

0001

本発明は、検索要求制御装置検索要求制御プログラム及び検索要求制御方法に関する。

背景技術

0002

近年、データベースシステム等のデータの検索において、検索要求が同時に送られてくる場合であってもデータの検索時間を短縮できるハイトラフィック技術が用いられることがある。ハイトラフィック技術とは、複数の検索要求から1つのオートマトンを生成し、生成したオートマトンを利用して検索対象データマッチングさせる技術である。図13は、ハイトラフィック技術を用いたデータの検索の一例を説明する図である。

0003

図13に示すように、例えばデータベースシステムは、同時に送られてくる複数の検索要求1〜4を一体化して、一体化した検索要求に対するデータを検索対象データから一括して検索し、検索した結果を検索要求に振り分ける。これにより、同時に送られてくる検索要求の多重度が上がっても、検索要求に対するデータを一括して検索するので、データの検索時間の予測を可能とする。

0004

また、データの検索時間を短縮する他の技術として、インデックス技術がある。インデックス技術とは、リレーショナルデータベースにおけるテーブルにおいて、カラムにある値を持つレコードを直接選択(検索)したり、XML文書等の構造を持つデータにおいて、特定のパス指し示すデータを直接検索させたりする技術である。図14は、インデックス技術を用いたデータの検索の一例を説明する図である。

0005

図14に示すように、検索要求1では、インデックスのパス2及びパス4が指し示すデータd2、d4(d2’、d4’)を検索し、検索要求2では、インデックスのパス3及びパス4が指し示すデータd3、d4(d3’、d4’)を検索する。このため、検索要求1及び検索要求2は、全体のデータを検索することなく最低限必要なデータだけを検索するので、データの検索時間を短縮できる。

0006

ところが、各検索要求において、検索するデータが重複する場合がある。図14の例では、検索要求1及び検索要求2では、パス4が指し示すデータd4(d4’)がD1(D1’)に示すように重複している。この場合には、重複したデータd4(d4’)が2回検索されるので、検索に無駄が生じる分、データの検索効率が悪くなる。

0007

そこで、データの検索時間を短縮する他の技術として、ハイトラフィック技術にインデックス技術を採用した技術も考えられる。この技術では、同時に送られてくる複数の検索要求を一体化して、一体化した検索要求のインデックスのパスの和集合を作成し、作成したパスの和集合に属するパスが指し示すデータを一括して検索する。図15は、ハイトラフィック技術にインデックス技術を採用した技術を説明する図である。

0008

図15に示すように、検索要求1では、インデックスのパス2及びパス4が指し示すデータを検索し、検索要求2では、インデックスのパス3及びパス4が指し示すデータを検索する。この場合には、検索要求1及び検索要求2のインデックスのパスの和集合パス2〜4を作成し、作成した和集合に属するパスが指し示すデータd2〜d4(d2’〜d4’)を一括して検索する。これにより、各検索要求において、検索するデータが重複する場合であっても、D2(D2’)に示すように重複するデータを1度だけ検索するので、データの検索効率が向上する。

0009

また、ほぼ同時に送られてくる複数の検索要求である検索式を、それぞれの予測検索速度に基づき複数の検索式集合に振り分け、予測検索速度の速い集合から順次検索を行い、対応する検索式集合内の検索式を纏めて一括検索する技術が開示されている。

先行技術

0010

特開2009−251686号公報
特開2007−241516号公報
特開平11−232302号公報

発明が解決しようとする課題

0011

しかしながら、ハイトラフィック技術にインデックス技術を採用した場合では、データの検索効率が向上しないことがあるという問題があった。すなわち、同時に送られてくる複数の検索要求で検索するデータに重複が少ない場合、重複するデータを1度だけ検索するという効果が少ないので、データの検索効率が向上しないことがある。

0012

具体的な例として、データの検索効率が向上しないという問題を、図16を用いて説明する。図16は、ハイトラフィック技術にインデックス技術を採用した場合の課題を説明する図である。図16に示すように、検索要求1では、インデックスのパス2及びパス4が指し示すデータを検索し、検索要求2では、インデックスのパス1及びパス3が指し示すデータを検索する。この場合には、検索要求1及び検索要求2のインデックスのパスの和集合パス1〜4を作成し、作成した和集合に属するパスが指し示すデータd1〜d4(d1’〜d4’)を一括して検索する。ところが、検索要求1及び検索要求2で検索するデータに重複がないので、重複するデータを1度だけ検索するという効果がなくなり、データの検索効率が向上しない。

0013

また、予測検索速度の速い検索式集合から順次検索を行なう技術であっても、検索式集合に含まれる検索式がそれぞれ全く重複しないデータを検索する場合には、データの検索効率が向上しない。

0014

なお、上記課題は、データベースシステムにおけるデータの検索だけではなく、インターネット等の検索エンジンにおけるデータの検索にも同様に生じる課題である。

0015

1つの側面では、ハイトラフィック技術にインデックス技術を採用した場合のデータの検索効率を向上させる検索要求制御装置等を提供することを目的とする。

課題を解決するための手段

0016

本願の開示する検索要求制御装置は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割部と、前記検索要求集合分割部によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出部と、前記平均レスポンス算出部によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して実行する検索要求実行部とを備える。

発明の効果

0017

本願の開示する検索要求制御装置の一つの態様によれば、ハイトラフィック技術にインデックス技術を採用した場合のデータの検索効率を向上させることができる。

図面の簡単な説明

0018

図1は、実施例1に係る検索要求制御装置の構成を示す機能ブロック図である。
図2は、分割による平均レスポンスの向上を説明する図である。
図3は、検索要求制御のタイムチャートを説明する図である。
図4は、実施例2に係る検索要求制御装置の構成を示す機能ブロック図である。
図5は、検索要求部分集合及び参照データ量対応表データ構造の一例を示す図である。
図6は、検索要求部分集合の参照データ量の算出方法を説明する図である。
図7は、分割パターン及び平均レスポンスの対応表のデータ構造の一例を示す図である。
図8は、分割により平均レスポンスが向上するための条件を説明する図である。
図9は、実施例2に係る検索要求制御処理の手順を示すフローチャートである。
図10は、検索スケジュール制御処理の手順を示すフローチャートである。
図11は、検索要求集合化探索処理の手順を示すフローチャートである。
図12は、検索要求制御プログラムを実行するコンピュータハードウェア構成を示す図である。
図13は、ハイトラフィック技術を説明する図である。
図14は、インデックス技術を説明する図である。
図15は、ハイトラフィック技術にインデックス技術を採用した技術を説明する図である。
図16は、ハイトラフィック技術にインデックス技術を採用した場合の課題を説明する図である。

0019

以下に、本願の開示する検索要求制御装置、検索要求制御プログラム及び検索要求制御方法の実施例を図面に基づいて詳細に説明する。なお、以下の実施例では、データベースシステムにおけるデータの検索要求を制御する検索要求制御装置に適用した場合を示す。しかし、本実施例によりこの発明が限定されるものではなく、本発明は、例えばインターネットやイントラネット等を組み込んだシステムにおける検索エンジンにも適用可能である。また、以下の実施例では、ハイトラフィック技術にインデックス技術を採用した場合について説明するものとする。

0020

図1は、本実施例1に係る検索要求制御装置の構成を示す機能ブロック図である。図1に示すように、検索要求制御装置1は、検索要求集合分割部11、平均レスポンス算出部12及び検索処理部13を有する。

0021

検索要求集合分割部11は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する。なお、所定期間とは、ほぼ同時となる期間を意味するが、検索要求を一括して処理するのに支障のない期間であれば良い。

0022

平均レスポンス算出部12は、検索要求集合分割部11によって分割された複数の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する。

0023

検索処理部13は、平均レスポンス算出部12によって算出された平均レスポンスが最短の複数の部分集合について、処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する。

0024

このようにして、検索要求制御装置1は、一括処理する単位となる部分集合への分割に検索要求が検索するデータの重複する度合いを用いることにより、部分集合における検索データ局所性を高めるので、データの検索効率の向上を図ることができる。さらに、検索要求制御装置1は、検索要求の平均レスポンスがより短くなるように検索要求集合を部分集合に分割しているので、分割した部分集合をそれぞれ処理することで検索要求の平均レスポンスを向上させることができる。

0025

ここで、検索要求集合を部分集合に分割することにより平均レスポンスが向上することについて、図2を参照しながら説明する。図2は、分割による平均レスポンスの向上を説明する図である。図2の例では、ほぼ同時に3個の検索要求1〜3が到着するものとする。図2に示すように、検索要求1、2は、インデックスのパス1〜3が指し示すデータを検索し、検索要求3は、インデックスのパス3〜5が指し示すデータを検索する。なお、パス1〜5が指し示すデータのサイズは、全て等しいものとする。また、パス1〜5が指し示すデータ、すなわち検索対象データのサイズを「S」、検索対象データのサイズあたりにかかる検索時間を「k」として説明するものとする。

0026

まず、検索要求1〜3を纏めて処理する場合について、検索要求の平均レスポンスを算出する。検索要求の平均レスポンスは、検索要求1〜3を纏めて処理するので、パス1〜5を指し示すデータを一括して検索する時間となる。すなわち、検索要求の平均レスポンスは、式(1)に示すとおりである。
検索要求の平均レスポンス=k×S・・・・・式(1)

0027

次に、検索要求1〜3を分割して処理する場合について、検索要求の平均レスポンスを算出する。検索要求集合分割部11は、ほぼ同時に取得された検索要求1〜3を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する。ここでは、検索要求集合分割部11は、パス1〜3が指し示すデータが重複する検索要求1、2を同じ部分集合とする。また、検索要求集合分割部11は、パス3が検索要求1、2と重複するが、パス4、5が検索要求1、2と重複しない検索要求3を、検索要求1、2と異なる部分集合とする。

0028

そして、平均レスポンス算出部12は、検索要求集合分割部11によって分割された2個の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する。ここでは、平均レスポンス算出部12は、処理順序の先行を検索要求1、2を含む部分集合、処理順序の後行を検索要求3を含む部分集合として、2個の部分集合を含む検索要求集合に含まれる検索要求の平均レスポンスを算出する。この結果、検索要求の平均レスポンスは、式(2)に示すとおりである。
検索要求の平均レスポンス={2×(k×S×3/5)+1×(k×S×3/5+k×S×3/5)}/3=k×S×4/5・・・・・式(2)

0029

したがって、式(1)及び式(2)を比較すると、検索要求1〜3を分割して処理する場合には、検索要求1〜3を纏めて処理する場合に比べて、検索要求の平均レスポンスが20%向上する。

0030

複数の検索要求を分割して処理する場合の検索要求のタイムチャートを、図3を参照しながら説明する。図3は、検索要求のタイムチャートを説明する図である。図3(A)では、複数の検索要求を分割しない場合のタイムチャートを示し、図3(B)では、複数の検索要求を分割する場合のタイムチャートを示す。なお、図3(A)(B)で示されるQ0〜Q3は、それぞれほぼ同時に到着する複数の検索要求を含む検索要求集合であるものとする。また、Q1−1、Q1−2は、検索要求集合Q1を分割した複数の部分集合であり、Q2−1、Q2−2は、検索要求集合Q2を分割した複数の部分集合であるものとする。

0031

図3(A)に示すように、複数の検索要求を分割しない場合、例えば新たに到着した検索要求集合Q1は、到着の際検索処理中の検索要求集合Q0の検索処理後に検索処理される。

0032

一方、図3(B)に示すように、複数の検索要求を分割する場合、新たに到着した検索要求集合Q1に含まれる部分集合Q1−1は、到着の際検索処理中の検索要求集合Q0の検索処理後に検索処理される。このとき、検索要求集合Q1に含まれる部分集合Q1−2は、部分集合Q1−1の検索処理が終わるまで待機することとなる。そして、待機中の部分集合Q1−2は、検索要求集合Q1の到着後新たに到着した検索要求集合Q2に含まれる部分集合Q2−1と併合され、部分集合Q1−1の検索処理後に検索処理されることとなる。

0033

[実施例2に係る検索要求制御装置の構成]
図4は、本実施例2に係る検索要求制御装置の構成を示す機能ブロック図である。図4に示すように、検索要求制御装置2は、検索要求受付部21、検索スケジュール制御部22、検索要求集合化探索部23、検索処理部24、検索結果出力部25、不揮発性記憶部26及び揮発性記憶部27を有する。

0034

不揮発性記憶部26は、検索対象データ41bとこれらを検索するために必要なインデックス41aとを記憶するデータベース41及びインデックスパス別データ量42を有する。インデックスパス別データ量42は、インデックス41aを構成するパス毎に、各パスが指し示すデータのデータ量をあらかじめ記憶する。ここで、パスとは、検索対象のデータを参照する際にデータを指し示す経路を意味する。なお、不揮発性記憶部26は、例えば、ハードディスク光ディスクなどの記憶装置、又は、フラッシュメモリ(flash memory)等の不揮発性半導体メモリ素子である。

0035

揮発性記憶部27は、検索要求部分集合及び参照データ量の対応表51、分割パターン及び平均レスポンスの対応表52、分割対象検索要求集合53及び実行待機中要求集合54を有する。なお、揮発性記憶部27は、例えば、RAM(Random Access Memory)等の揮発性の半導体メモリ素子である。

0036

検索要求受付部21は、外部のアプリケーションから送信された検索要求を受け付け、受け付けた検索要求を待ち行列である要求キューに入力する。

0037

検索スケジュール制御部22は、非同期的に発生するイベントを取得し、取得したイベントの種類に応じて検索要求の検索のスケジュールを制御する。具体的には、検索スケジュール制御部22は、検索要求受付部21から検索要求の到着イベントを取得すると、要求キューに入力されている検索要求を取り出し、取り出した検索要求を後述する検索要求集合化探索部23に出力する。また、検索スケジュール制御部22は、後述する検索処理部24から検索要求の検索完了イベントを取得すると、検索要求を一括して処理する検索要求の集合の取得依頼を検索要求集合化探索部23に出力する。そして、検索スケジュール制御部22は、検索要求の集合の取得依頼に対する集合を検索要求集合化探索部23から取得すると、取得した集合に含まれる検索要求を検索処理部24に出力する。

0038

検索要求集合化探索部23は、検索スケジュール制御部22からほぼ同時に取得した複数の検索要求に対し、平均レスポンスが向上するような分割案を探索する。さらに、検索要求集合化探索部23は、イベント振分部31、参照パス判定部32、検索要求集合分割部33、平均レスポンス算出部34、平均レスポンス判定部35及び分割パターン選択部36を有する。

0039

イベント振分部31は、イベントを取得し、取得したイベントの種類に応じて処理を振り分ける。具体的には、イベント振分部31は、検索スケジュール制御部22からほぼ同時に取得した複数の検索要求を検索要求集合として、分割対象検索要求集合53に記憶する。

0040

ここで、分割対象検索要求集合53は、複数の部分集合に分割される検索要求集合を記憶する。例えば、分割対象検索要求集合53は、検索要求集合に一意割り振られた識別番号に、検索要求集合に含まれる複数の検索要求を対応付けて記憶する。

0041

また、イベント振分部31は、検索スケジュール制御部22から検索要求の集合の取得依頼を取得すると、検索要求集合の分割パターンを選択させるべく、当該取得依頼を分割パターン選択部36に出力する。また、イベント振分部31は、直近のイベントを取得したときから一定期間イベントの取得がない場合には、分割対象検索要求集合53に記憶された検索要求集合を複数の部分集合に分割させるべく、検索要求集合の分割依頼を参照パス判定部32に出力する。

0042

参照パス判定部32は、イベント振分部31から検索要求集合の分割依頼を取得すると、分割対象検索要求集合53に記憶された検索要求集合に含まれる各検索要求について、データを参照する際に用いるパスを判定する。そして、参照パス判定部32は、各検索要求について、判定したパスを一時的に揮発性記憶部27に記憶する。例えば、参照パス判定部32は、各検索要求について、パス毎に参照の有無を表すフラグの列を記憶する。ここで、参照が有ることを表すフラグの値は「1」とし、参照が無いことを表すフラグの値は「0」とする。

0043

検索要求集合分割部33は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する。具体的には、検索要求集合分割部33は、パス参照判定部32によってパスの判定がされた複数の検索要求を、各検索要求が参照するパスが指し示すデータの重複する度合いに基づいて複数の部分集合に分割する。例えば、検索要求集合分割部33は、参照するパスが指し示すデータが所定の割合以上重複する検索要求同士を同一の部分集合に集合化し、所定の割合以上重複しない検索要求同士を異なる部分集合に分割する。分割した2個の部分集合の組み合わせは、1個の分割パターンとなる。なお、所定の割合とは、例えば8割や9割であるが、随時変動しても良い。また、1個の分割パターンを形成する2個の部分集合は、積集合が空、且つ和集合が検索要求集合となる組み合わせであるものとする。

0044

また、検索要求集合分割部33は、検索要求集合を分割した部分集合毎に、参照するデータのデータ量を算出する。具体的には、検索要求集合分割部33は、検索要求毎のフラグの列を用いて、部分集合に含まれる検索要求について、パス毎のフラグの論理和を算出する。なお、検索要求毎のフラグの列は、参照パス判定部32によって揮発性記憶部27に記憶されているものとする。そして、検索要求集合分割部33は、算出されたパス毎のフラグの値に基づいて、インデックスパス別データ量42を用いてパス毎の参照データ量を算出する。そして、検索要求集合分割部33は、算出したパス毎の参照データ量を加算し、「検索要求部分集合の参照データ量」を求める。

0045

また、検索要求集合分割部33は、「検索要求部分集合の参照データ量」を部分集合に対応付けて、検索要求部分集合及び参照データ量の対応表51に記憶する。ここで、検索要求部分集合及び参照データ量の対応表51のデータ構造について、図5を参照しながら説明する。

0046

図5は、検索要求部分集合及び参照データ量の対応表51のデータ構造の一例を示す図である。図5に示すように、検索要求部分集合及び参照データ量の対応表51は、キー51a及び参照データ量51bを対応付けて記憶する。すなわち、検索要求部分集合及び参照データ量の対応表51は、キー51aに対応する値を参照データ量51bとするハッシュテーブル等のマップ構造となっている。キー51aは、検索要求の部分集合に含まれる検索要求の識別子の集合を示す。参照データ量51bは、検索要求の部分集合が参照するデータのデータ量を示す。

0047

また、検索要求の部分集合(検索要求部分集合)が参照するデータのデータ量を算出する方法を、図6を参照しながら説明する。図6は、検索要求部分集合の参照データ量の算出方法を説明する図である。図6では、検索要求部分集合Qに検索要求q1〜q3が含まれる場合を例として、検索要求部分集合Qの参照データ量の算出方法を説明する。図6に示すように、検索要求q1のフラグの列は、パス2を参照有りの「1」とし、パス2以外のパスを参照無しの「0」とする。検索要求q2のフラグの列は、パス1、2を参照有りの「1」とし、パス1、2以外のパスを参照無しの「0」とする。検索要求q3のフラグの列は、パス1、Nを参照有りの「1」とし、パス1、N以外のパスを参照無しの「0」とする。

0048

検索要求集合分割部33は、検索要求q1〜q3のそれぞれのフラグの列を用いて、パス毎のフラグの論理和を算出する。ここでは、算出されたパス毎のフラグの列は、パス1、2、Nを参照有りの「1」とし、パス1、2、N以外のパスを参照無しの「0」となる。そして、検索要求集合分割部33は、算出されたパス毎のフラグの列の各値とインデックスパス別データ量42に記憶されたパス毎のデータ量との内積を算出する。ここでは、算出されたパス毎のフラグの列の各値は{1、1、0、・・・、1}であり、インデックスパス別データ量42に記憶されたパス毎のデータ量は{123、456、789、・・・、321}である。したがって、パス毎の積を求めると、結果は{123、456、0、・・・、321}となる。さらに、検索要求集合分割部33は、計算の結果得られたパスごとのデータ量を加算し、「検索要求部分集合の参照データ量」を求める。ここでは、「検索要求部分集合の参照データ量」は、「900」となる。

0049

図4に戻って、平均レスポンス算出部34は、検索要求集合分割部33によって分割された複数の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する。具体的には、平均レスポンス算出部34は、検索要求集合分割部33によって分割された分割パターンの中から順次1個の分割パターンを選択する。そして、平均レスポンス算出部34は、選択した分割パターンに含まれる2個の部分集合の処理順序を決定する。また、平均レスポンス算出部34は、処理順序が先行する部分集合(以降、「先行部分集合」という。)に含まれる検索要求の参照データ量を、検索要求部分集合及び参照データ量の対応表51から読み出す。そして、平均レスポンス算出部34は、読み出した参照データ量に基づいて、先行部分集合の検索時間を算出する。また、平均レスポンス算出部34は、処理順序が後行する部分集合(以降、「後行部分集合」という。)に含まれる検索要求の参照データ量を、検索要求部分集合及び参照データ量の対応表51から読み出す。そして、平均レスポンス算出部34は、読み出した参照データ量に基づいて、後行部分集合の検索時間を算出する。

0050

そして、平均レスポンス算出部34は、先行部分集合の検索時間及び後行部分集合の検索時間に基づいて、先行部分集合及び後行部分集合の和集合である検索要求集合に含まれる検索要求の平均レスポンスを算出する。例えば、先行部分集合の検索時間をr1、後行部分集合の検索時間をr2とし、先行部分集合に含まれる検索要求の数をN1、後行部分集合に含まれる検索要求の数をN2とする。また、検索要求集合に含まれる検索要求の数をN0とする。すなわち、N0は、N1及びN2を加算した値である。このような例において、検索要求集合に含まれる検索要求の平均レスポンスr12は、式(3)で表される。
r12={N1×r1+N2×(w2+r2)}/N0=r1+r2×N2/N0・・式(3)
なお、w2は、先行部分集合の検索処理後に処理される後行部分集合の待ち時間であり、先行部分集合の検索時間r1と同値となる。

0051

また、平均レスポンス算出部34は、算出した検索要求の平均レスポンスを、分割パターンに対応付けて、分割パターン及び平均レスポンスの対応表52に記憶する。ここで、分割パターン及び平均レスポンスの対応表52のデータ構造について、図7を参照しながら説明する。

0052

図7は、分割パターン及び平均レスポンスの対応表52のデータ構造の一例を示す図である。図7に示すように、分割パターン及び平均レスポンスの対応表52は、分割パターン52a及び平均レスポンス52bを対応付けて記憶する。すなわち、分割パターン及び平均レスポンスの対応表52は、分割パターン52aをキー、平均レスポンス52bを値とするB−Tree等のマップ構造となっている。分割パターン52aは、処理順序に応じた2個の部分集合を示す。この2個の部分集合は、積集合が空、すなわち重複した検索要求を持たない集合同士となっている。平均レスポンス52bは、分割パターン52aで示される2個の部分集合における検索要求の平均レスポンスを示す。

0053

平均レスポンス判定部35は、検索要求集合を分割した2個の部分集合の平均レスポンスが検索要求集合を分割しない場合より向上しているか否かを判定する。具体的には、平均レスポンス判定部35は、検索要求集合を分割しない場合の平均レスポンスを算出する。そして、平均レスポンス判定部35は、平均レスポンス算出部34によって平均レスポンスが算出された分割パターンについて、この平均レスポンスが検索要求集合を分割しない場合の平均レスポンスより短いか否かを判定する。そして、平均レスポンス判定部35は、分割パターンについての平均レスポンスが検索要求集合を分割しない場合より短いと判定した場合に、分割しない場合より平均レスポンスが向上すると判断する。一方、平均レスポンス判定部35は、分割パターンについての平均レスポンスが検索要求集合を分割しない場合より短いと判定した場合に、分割しない場合より平均レスポンスが向上しないと判断する。

0054

ここで、検索要求集合を分割した場合における平均レスポンスが、検索要求集合を分割しない場合における平均レスポンスより向上するために満たすべき条件について、図8を参照して説明する。図8は、分割により平均レスポンスが向上するための条件を説明する図である。図8(A)では、分割しない場合の検索処理コストを示し、図8(B)では、分割する場合の検索処理コストを示し、図8(C)では、分割しない場合と分割する場合の差を示す図である。なお、図8では、検索要求集合に含まれる検索要求の数をN0、先行部分集合に含まれる検索要求の数をN1、後行部分集合に含まれる検索要求の数をN2とする。また、検索要求集合の全体の参照データをD0、先行部分集合の参照データをD1、後行部分集合の参照データをD2とする。さらに、S(Dn)(nは、1、2)を参照データDnの参照データ量とし、r(S(Dn))を参照データDnの参照データ量を検索する際の検索時間とする。

0055

図8(A)に示すように、分割しない場合の検索処理コストは、検索要求集合に含まれる全検索要求の参照データ量S(D0)を検索する際の検索時間r(S(D0))と検索要求の数N0との積で表される。ここでは、T0で示される領域となる。すなわち、ハイトラフィック技術では、検索要求集合に含まれる複数の検索要求を一括して処理するので、検索時間は一括して処理する参照データ量に比例することとなり、検索要求集合の検索処理コストは参照データ量と検索要求の数から求められる。

0056

次に、図8(B)に示すように、分割する場合の検索処理コストは、先行部分集合の検索処理コスト、後行部分集合の検索処理コスト及び後行部分集合の待ちコストの和で表される。先行部分集合の検索処理コストは、先行部分集合に含まれる検索要求の参照データ量S(D1)を検索する際の検索時間r(S(D1))(以降、「r1」)と検索要求の数N1との積で表される。ここでは、T1で示される領域となる。また、後行部分集合の検索処理コストは、後行部分集合に含まれる検索要求の参照データ量S(D2)を検索する際の検索時間r(S(D2))(以降、「r2」)と検索要求の数N2との積で表される。ここでは、T2で示される領域となる。さらに、後行部分集合の待ちコストは、後行部分集合が検索処理を実行するまでの待ち時間と一致する先行部分集合の検索時間r1(以降、「w2」)と検索要求の数N2の積で表される。ここでは、T3で示される領域となる。

0057

次に、図8(C)に示すように、分割しない場合と分割する場合の差は、分割により検索処理コストが減少することとなる「分割によるベネフィット」T4と分割により検索処理コストが増加することとなる「分割によるコスト」T5との差分となる。ここでは、「分割によるベネフィット」T4は、後行部分集合の参照データD2から先行部分集合の参照データD1を引いたデータを検索する際の検索時間r(S(D2−D1))と先行部分集合に含まれる検索要求の数N1との積となる。また、分割によりコストT5は、後行部分集合の参照データD2と先行部分集合の参照データD1とが共に参照するデータを検索する際の検索時間r(S(D2∩D1))と後行部分集合に含まれる検索要求の数N2との積となる。

0058

したがって、分割しない場合と分割する場合の差J0は、「分割によるベネフィット」T4及び「分割によるコスト」T5を用いて、式(4)で表される。
J0=T4−T5=N1×r(S(D2−D1))−N2×r(S(D2∩D1))・・・式(4)
そして、分割しない場合と分割する場合の差J0が正値となる場合、すなわち「分割によるベネフィット」T4が「分割によるコスト」T5より大きい場合に、分割により平均レスポンスが向上することとなる。つまり、「分割によるコスト」T5が小さいほど、言い換えれば後行部分集合の参照データD2と先行部分集合の参照データD1とが共に参照するデータS(D2∩D1)が小さいほど、分割によるメリットがより大きくなる。また、後行部分集合のみ参照し先行部分集合が参照しないデータS(D2−D1)が大きいほど、分割によるメリットがより大きくなる。

0059

分割パターン選択部36は、平均レスポンス判定部35によって平均レスポンスが分割しない場合より向上すると判断された分割パターンの中から最短の平均レスポンスとなる分割パターンを選択する。具体的には、分割パターン選択部36は、イベント振分部31から検索要求の集合の取得依頼を取得すると、分割パターン及び平均レスポンスの対応表52に基づいて、最短の平均レスポンスに対応付けられた分割パターンを選択する。そして、分割パターン選択部36は、選択した分割パターンのうち先行部分集合を、先行して検索処理させるべく、検索スケジュール制御部22に出力する。このとき、分割パターン選択部36は、選択した分割パターンのうち後行部分集合を、実行待機中要求集合54に記憶する。

0060

ここで、実行待機中要求集合54は、検索要求集合の分割パターンのうち先行部分集合が先行して検索処理されているとき、後続して検索処理される後行部分集合を待機させるために記憶する。例えば、実行待機中要求集合54は、検索要求集合に一意に割り振られた識別番号に、後行部分集合に含まれる複数の検索要求を対応付けて記憶する。なお、分割パターン選択部36は、既に実行待機中要求集合54に直前の検索要求集合における後行部分集合が記憶されている場合には、この後行部分集合を、現在処理中の検索要求集合における先行部分集合とともに検索スケジュール制御部22に出力する。これらの部分集合が、後述する検索処理部24によって併合して処理されるためである。

0061

検索処理部24は、検索スケジュール制御部22から部分集合に含まれる検索要求を取得すると、データベース41からこれら検索要求について一括して検索処理を実行する。そして、検索処理部24は、部分集合に含まれる検索要求について検索処理が完了すると、検索要求の検索完了イベントを検索スケジュール制御部22に出力する。

0062

検索結果出力部25は、検索処理部24によって一括して検索処理された部分集合毎に、各部分集合に含まれる検索要求の検索結果を出力する。

0063

[実施例2に係る検索要求制御処理の手順]
次に、検索要求制御処理の手順を、図9を参照して説明する。図9は、実施例2に係る検索要求制御処理の手順を示すフローチャートである。

0064

まず、検索要求制御処理は、検索要求の検索状況を判定する(ステップS11)。そして、検索要求制御処理は、検索要求の検索状況が検索中であると判定する場合には(ステップS11;検索中)、新たな検索要求が到着していれば分割対象の検索要求集合に加える(ステップS12)。すなわち、検索要求制御処理は、検索要求集合の直前に到着した検索要求集合に関わる検索要求の検索中に、ほぼ同時を示す所定期間に到着した新たな検索要求を検索要求集合として分割対象検索要求集合53に記憶する。そして、検索要求制御処理は、分割対象検索要求集合53に記憶された分割対象の検索要求集合に対して、平均レスポンスが向上するような分割パターンの探索処理を行う(ステップS13)。そして、検索要求制御処理は、ステップS11に移行する。

0065

一方、検索要求制御処理は、検索要求の検索状況が検索完了であると判定する場合には(ステップS11;検索完了)、検索結果を出力する(ステップS14)。そして、検索要求制御処理は、分割対象検索要求集合53に記憶された検索要求集合について、現段階で探索された分割パターンのうち平均レスポンスが最短の分割パターンにおける先行部分集合に対して、検索処理を開始させる(ステップS15)。そして、検索要求制御処理は、ステップS11に移行する。

0066

[検索スケジュール制御処理の手順]
次に、検索スケジュール制御部22による検索スケジュール制御処理の手順を、図10を参照して説明する。図10は、検索スケジュール制御処理の手順を示すフローチャートである。

0067

まず、検索スケジュール制御部22は、イベントを待ち(ステップS21)、イベントを取得したとき、取得したイベントを判定する(ステップS22)。

0068

そして、検索スケジュール制御部22は、取得したイベントが検索要求の到着イベントであると判定する場合には(ステップS22;検索要求の到着)、要求キューに入力されている検索要求を取り出す(ステップS23)。そして、検索スケジュール制御部22は、検索要求の検索処理中であるか否かを判定する(ステップS24)。そして、検索スケジュール制御部22は、検索要求が検索処理中であると判定する場合には(ステップS24;Yes)、要求キューから取り出した全検索要求を分割させるべく、当該全検索要求を検索要求集合化探索部23に出力する(ステップS25)。そして、検索スケジュール制御部22は、ステップS21に処理を移行する。

0069

一方、検索スケジュール制御部22は、検索要求が検索処理中でないと判定する場合には(ステップS24;No)、要求キューから取り出した全検索要求を検索処理させるべく、当該全検索要求を検索処理部24に出力する(ステップS26)。そして、検索スケジュール制御部22は、ステップS21に処理を移行する。

0070

一方、検索スケジュール制御部22は、取得したイベントが検索要求の検索完了イベントである場合には(ステップS22;検索完了)、次に検索する検索要求を促すべく、検索要求の集合の取得依頼を検索要求集合化探索部23に出力する(ステップS27)。そして、検索スケジュール制御部22は、検索要求集合化探索部23からの検索要求の集合を待つ(ステップS28)。

0071

続いて、検索スケジュール制御部22は、検索要求集合化探索部23から検索要求の集合を取得すると、取得した集合が空集合か否かを判定する(ステップS29)。そして、検索スケジュール制御部22は、取得した集合が空集合であると判定する場合には(ステップS29;Yes)、次のイベントを待つべく、ステップS21に移行する。一方、検索スケジュール制御部22は、取得した集合が空集合でないと判定する場合には(ステップS29No)、取得した集合に含まれる検索要求を検索処理部24に出力する(ステップS30)。

0072

[検索要求集合化探索処理の手順]
次に、検索要求集合化探索部23による検索要求集合化探索処理の手順を、図11を参照して説明する。図11は、検索要求集合化探索処理の手順を示すフローチャートである。

0073

まず、探索要求集合化探索部23は、分割対象検索要求集合53を空集合で初期化する(ステップS41)。そして、探索要求集合化探索部23のイベント振分部31は、イベントを待ち(ステップS42)、イベントを取得したとき、取得したイベントを判定する(ステップS43)。

0074

そして、イベント振分部31は、取得したイベントが検索要求の取得イベントであると判定する場合(ステップS43;検索要求の取得)、取得した検索要求を分割対象検索要求集合53に追加する(ステップS44)。すなわち、イベント振分部31は、取得した複数の検索要求を検索要求集合として、分割対象検索要求集合53に記憶する。

0075

そして、平均レスポンス算出部34は、取得した検索要求を加えた分割パターンでの平均レスポンスを再計算し、分割パターンに対応付けた計算結果を分割パターン及び平均レスポンスの対応表52に更新する(ステップS45)。そして、平均レスポンス算出部34は、処理をステップS42に移行する。

0076

また、イベント振分部31が直近のイベントの取得から一定期間イベントの取得がないと判定する場合(ステップS43;イベントなし)、検索要求集合分割部33は、分割対象検索要求集合53の検索要求集合から分割パターンを生成する(ステップS46)。すなわち、検索要求集合分割部33は、それぞれの検索要求が検索するデータの重複する度合いに基づいて検索要求集合を2個の部分集合に分割し、分割パターンを生成する。例えば、検索要求集合分割部33は、参照するパスが指し示すデータが所定の割合以上重複する検索要求同士を同一の部分集合に集合化し、所定の割合以上重複しない検索要求を異なる部分集合に分割し、これらの部分集合の組を1個の分割パターンとする。

0077

続いて、検索要求集合分割部33は、生成した分割パターンを1個選択する(ステップS47)。そして、検索要求集合分割部33は、選択した分割パターンに含まれる部分集合毎に、参照するデータのデータ量を計算し、検索要求部分集合及び参照データ量の対応表51に追加する(ステップS48)。

0078

そして、平均レスポンス算出部34は、選択した分割パターンに含まれる2個の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する(ステップS49)。具体的には、平均レスポンス算出部34は、分割パターンに含まれる2個の部分集合の処理順序を決定し、決定した処理順序が先行する先行部分集合及び処理順序が後行する後行部分集合の参照データ量を検索要求部分集合及び参照データ量の対応表51から読み出す。そして、平均レスポンス算出部34は、読み出した先行部分集合及び後行部分集合の参照データ量に基づいて、それぞれのデータの検索時間を算出する。さらに、平均レスポンス算出部34は、先行部分集合及び後行部分集合のそれぞれの検索時間に基づいて、検索要求集合に含まれる検索要求の平均レスポンスを算出する。

0079

そして、平均レスポンス算出部34は、算出した平均レスポンスを、分割パターンに対応付けて、分割パターン及び平均レスポンスの対応表52に追加し(ステップS50)、処理をステップS42に移行する。

0080

また、イベント振分部31が検索要求の集合の取得依頼イベントであると判定する場合(ステップS43;要求集合の取得依頼)、分割パターン選択部36は、平均レスポンスが最短となる分割パターンを選択する(ステップS51)。具体的には、分割パターン選択部36は、分割パターン及び平均レスポンスの対応表52に基づいて、最短の平均レスポンスに対応付けられた分割パターンを選択する。

0081

そして、分割パターン選択部36は、選択した分割パターンのうち先行部分集合に含まれる検索要求を、先行して検索処理させるべく、検索スケジュール制御部22に出力する(ステップS52)。このとき、分割パターン選択部36は、選択した分割パターンのうち後行部分集合に含まれる検索要求を、実行待機中要求集合54に移動する(ステップS53)。そして、分割パターン選択部36は、処理をステップS41に移行する。なお、分割パターン選択部36は、既に実行待機中要求集合54に直前の検索要求集合における後行部分集合が記憶されている場合には、この後行部分集合を、現在処理中の検索要求集合における先行部分集合とともに検索スケジュール制御部22に出力する。

0082

[実施例2の効果]
上記実施例2によれば、検索要求集合分割部33は、ほぼ同時に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する。そして、平均レスポンス算出部34は、検索要求集合分割部33によって分割された複数の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する。さらに、検索処理部24は、平均レスポンス算出部34によって算出された平均レスポンスが最短の複数の部分集合について、処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する。

0083

かかる構成によれば、検索要求集合分割部33は、一括処理する単位となる部分集合への分割に検索要求が検索するデータの重複する度合いを用いることとした。このため、検索要求集合分割部33は、部分集合における検索データの局所性を高めることができるので、データの検索効率の向上を図ることができる。さらに、検索要求集合分割部33は、検索要求の平均レスポンスがより短くなるように検索要求集合を部分集合に分割することとなるので、分割した部分集合をそれぞれ処理することで検索要求の平均レスポンスを向上させることができる。

0084

また、上記実施例2によれば、検索要求集合分割部33は、検索要求集合を、当該検索要求集合の直前に取得された検索要求集合に関わる検索要求の実行中に、複数の部分集合に分割する。そして、平均レスポンス算出部34は、検索要求集合分割部33によって分割された複数の部分集合の処理順序に応じて、検索要求集合に含まれる検索要求の平均レスポンスを算出する。かかる構成によれば、検索要求集合の直前に取得された検索要求集合の実行完了後に次に実行すべき検索要求集合について平均レスポンスがより短くなる部分集合を選択できるので、全体の検索要求の平均レスポンスを向上させることができる。

0085

また、上記実施例2によれば、検索処理部24は、処理順序が先行する部分集合に含まれる検索要求を検索要求集合の直前に取得された検索要求の処理後に実行する。そして、検索処理部24は、処理順序が後行する部分集合に含まれる検索要求を検索要求集合の直後に取得された検索要求と併合して処理する。かかる構成によれば、検索処理部24は、処理順序が後行する部分集合を検索要求集合の直後に取得された検索要求と併合して処理することとした。このため、検索処理部24は、処理順序が後行する部分集合の処理時期を無期限延期しないので、当該部分集合を含む検索要求集合の平均レスポンスを確実に向上させることができる。

0086

また、上記実施例2によれば、検索要求部分集合及び参照データ量の対応表51は、部分集合毎にそれぞれの部分集合に含まれる検索要求が一括して検査するデータのデータ量を記憶する。そして、平均レスポンス算出部34は、処理順序が先行する部分集合に関わるデータ量のデータを検索する検索時間及び処理順序が後行する部分集合に関わるデータ量のデータを検索する検索時間を用いて、平均レスポンスを算出する。かかる構成によれば、仮に処理順序が先行する部分集合及び処理順序が後行する部分集合に関わるデータ量が重複しない場合には、平均レスポンス算出部34は、各部分集合に関わるデータ量のデータを検索する検索時間を要するのみとなる。このため、平均レスポンス算出部34は、検索要求集合を分割しない場合と比べて、検索時間が短くなり、平均レスポンスを向上させることができる。

0087

なお、実施例2では、分割パターン選択部36は、分割パターン及び平均レスポンスの対応表52に基づいて、最短の平均レスポンスに対応付けられた分割パターンを選択するものとして説明した。しかしながら、分割パターン選択部36は、分割パターンに対応付けられた最短の平均レスポンスが分割しない場合の平均レスポンスより長い場合には、分割しないままの検索要求集合を選択するようにするようにしても良い。この場合には、平均レスポンス算出部34が、分割しない場合の検索要求の平均レスポンスを検索要求集合に対応付けて分割パターン及び平均レスポンスの対応表52に記憶しておく。そして、分割パターン選択部36は、分割しない場合の検索要求の平均レスポンスを含めて最短の平均レスポンスとなる分割パターンを選択するようにすれば良い。これにより、分割パターン選択部36は、分割しない場合の検索要求の平均レスポンスよりも長くなることがなくなり平均レスポンスを安定させることができる。

0088

また、実施例2では、分割パターン選択部36は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて2個の部分集合に分割するものとして説明した。しかしながら、分割パターン選択部36は、所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて3個の部分集合に分割するようにしても良い。

0089

プログラム等]
また、この検索要求制御装置2は、既知パーソナルコンピュータワークステーションなどの情報処理装置に、上記した検索スケジュール制御部22、検索要求集合化探索部23等の各機能を搭載することによって実現することができる。

0090

また、図示した各装置の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合具体的態様は図示のものに限られず、その全部又は一部を、各種の負荷使用状況などに応じて、任意の単位で機能的又は物理的に分散・統合して構成することができる。例えば、平均レスポンス算出部34と平均レスポンス判定部35とを1個の部として統合しても良い。一方、平均レスポンス算出部34を、複数の部分集合の処理順序を並び替える並び替え部と、処理順序を並び替えた複数の部分集合について平均レスポンスを算出する算出部とに分散しても良い。また、不揮発性記憶部26等の記憶部を検索要求制御装置2の外部装置としてネットワーク経由で接続するようにしても良い。

0091

また、上記実施例で説明した各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。そこで、以下では、図12を用いて、図4に示した検索要求制御装置2と同様の機能を有する検索要求制御プログラムを実行するコンピュータの一例を説明する。

0092

図12は、検索要求制御プログラムを実行するコンピュータのハードウェア構成を示す図である。図12に示すように、コンピュータ1000は、RAM(Random Access Memory)1010と、ネットワークインタフェース装置1020と、HDD1030と、CPU(Central Processing Unit)1040、媒体読取装置1050と、入力装置1060と、出力装置1070とを有する。RAM1010、ネットワークインタフェース装置1020、HDD1030、CPU1040、入力装置1060及び出力装置1070は、バス1080によって接続されている。

0093

そして、HDD1030には、図4に示した検索要求制御装置2と同様の機能を有する検索要求制御プログラム1031が記憶される。また、HDD1030には、図4に示した不揮発性記憶部26内の情報(データベース41、インデックスパス別データ量42)に対応する検索対象データ情報1032が記憶される。

0094

そして、CPU1040が検索要求制御プログラム1031をHDD1030から読み出してRAM1010に展開することにより、検索要求制御プログラム1031は、検索要求制御プロセス1011として機能するようになる。そして、検索要求制御プロセス1011は、検索対象データ情報1032から読み出した情報等を適宜RAM1010上の自身に割り当てられた領域に展開し、この展開したデータ、例えば検索要求制御情報1012等に基づいて各種データ処理を実行する。

0095

媒体読取装置1050は、検索要求制御プログラム1031がHDD1030に記憶されていない場合であっても、検索要求制御プログラム1031を記憶する媒体等から検索要求制御プログラム1031を読み取る。媒体読取装置1050には、例えばCD−ROM光ディスク装置がある。

0096

ネットワークインタフェース装置1020は、外部装置とネットワーク経由で接続する装置であり、有線に対応するものであっても、無線に対応するものであっても良い。また、入力装置1060には、例えばキーボードマウスがあり、出力装置1070には、例えばディスプレイがある。

0097

なお、上記の検索要求制御プログラム1031は、公衆回線、インターネット、LAN(Local Area Network)、WAN(Wide Area Network)等を介してコンピュータ1000に接続される他のコンピュータ(またはサーバ)等にこのプログラムを記憶させておいても良い。この場合には、コンピュータ1000がこれらからプログラムを読み出して実行する。

0098

以上の実施例に係る実施形態に関し、さらに以下の付記を開示する。

0099

(付記1)所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割部と、
前記検索要求集合分割部によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出部と、
前記平均レスポンス算出部によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理部と
を有することを特徴とする検索要求制御装置。

0100

(付記2)前記検索要求集合分割部は、
前記検索要求集合を、当該検索要求集合の直前に取得された検索要求集合に関わる検索要求の処理中に、複数の部分集合に分割することを特徴とする付記1に記載の検索要求制御装置。

0101

(付記3)前記検索処理部は、
前記処理順序が先行する部分集合に含まれる検索要求を前記検索要求集合の直前に取得された検索要求の処理後に処理し、前記処理順序が後行する部分集合に含まれる検索要求を前記検索要求集合の直後に取得された検索要求と併合して処理することを特徴とする付記1または付記2に記載の検索要求制御装置。

0102

(付記4)前記部分集合毎にそれぞれの部分集合に含まれる検索要求が一括して検索するデータのデータ量を記憶するデータ量記憶部を有し、
前記平均レスポンス算出部は、
前記処理順序が先行する部分集合に関わるデータ量のデータを検索する検索時間及び前記処理順序が後行する部分集合に関わるデータ量のデータを検索する検索時間を用いて、前記平均レスポンスを算出することを特徴とする付記1から付記3のいずれか1つに記載の検索要求制御装置。

0103

(付記5)所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割手順と、
前記検索要求集合分割手順によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出手順と、
前記平均レスポンス算出手順によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理手順と
をコンピュータに実行させることを特徴とする検索要求制御プログラム。

実施例

0104

(付記6)検索要求制御装置が検索要求を制御する検索要求制御方法であって、
所定期間に取得された複数の検索要求を含む検索要求集合を、それぞれの検索要求が検索するデータの重複する度合いに基づいて複数の部分集合に分割する検索要求集合分割工程と、
前記検索要求集合分割工程によって分割された複数の部分集合の処理順序に応じて、前記検索要求集合に含まれる検索要求の平均レスポンスを算出する平均レスポンス算出工程と、
前記平均レスポンス算出工程によって算出された平均レスポンスが最短の複数の部分集合について、前記処理順序に応じてこれら部分集合に含まれる検索要求を一括して処理する検索処理工程と
を含むことを特徴とする検索要求制御方法。

0105

1、2検索要求制御装置
11検索要求集合分割部
12平均レスポンス算出部
13検索処理部
21検索要求受付部
22検索スケジュール制御部
23 検索要求集合化探索部
24 検索処理部
25検索結果出力部
26不揮発性記憶部
27揮発性記憶部
31イベント振分部
32参照パス判定部
33 検索要求集合分割部
34 平均レスポンス算出部
35 平均レスポンス判定部
36分割パターン選択部
41データベース
41aインデックス
41b検索対象データ
42 インデックスパス別データ量
51 検索要求部分集合及び参照データ量の対応表
52 分割パターン及び平均レスポンスの対応表
53分割対象検索要求集合
54実行待機中要求集合

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 尾和剛一の「 特許文献集合の分析方法」が 公開されました。( 2019/05/23)

    【課題】特定のコア技術や、特定の出願人の特定の分野の全特許文献集合の文献件数時系列動向とは異なる動向を示す文献項目を抽出する方法を提供する。【解決手段】特定文献集合分折方法は、特定の文献集合の特許文献... 詳細

  • 株式会社大塚商会の「 画像解析システム」が 公開されました。( 2019/05/23)

    【課題】 画像解析システムを提供することを目的とする。【解決手段】 画像解析システムであって,対象物と対象物関連情報とを対応づけて記憶する対象物情報記憶部と,第1の画像情報と,少なくとも一以上の第... 詳細

  • ヤフー株式会社の「 情報処理装置、情報処理方法および情報処理プログラム」が 公開されました。( 2019/05/23)

    【課題】位置情報を付加したコンテンツを作成する際の利便性を高めることができる情報処理装置、情報処理方法および情報処理プログラムを提供する。【解決手段】情報処理装置1は、コンテンツ取得部31と、位置候補... 詳細

この 技術と関連性が強い技術

関連性が強い 技術一覧

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ