情報検索装置、検索用プログラム、データベースの更新装置、データベース更新用プログラム

2022.10.17 By 神奈川大学

情報

技術概要

データ量の大幅圧縮と検索速度向上を実現するデータベースの構成法

用途・応用

ビッグデータに対しても高速に稼働するデータベース構造

背景

 従来、例えばネットスーパーで商品を検索するにあたり、顧客はまず先の選択カテゴリー(肉の種類)からいずれかの先選択項目(関係項目:「牛肉」、「豚肉」、「鶏肉」)を選択(指定)した後に、後の選択カテゴリー(部位の種類)からいずれかの後選択項目(関係項目:「サーロイン」、「タン」、「ヒレ」、「モモ」、「肩」、「ササミ」、「レバー」)を選択(指定)することで、選択された選択項目に該当する商品(検索対象項目:例えば牛のモモ肉)が表示される絞り込み商品検索システムが知られている。

 特許文献1には、先選択項目に対して重複して関連づけられる後選択項目の重複を減らすために、いくつかの先選択項目(関係項目)を上位の分類(上位項目)でグループ化したデータテーブルを含むデータ構造が開示されている。このデータ構造には、後選択項目(関係項目)を先選択項目や上位分類と関連づけたデータテーブルも含まれている。

 例えば、先の選択カテゴリー(肉の種類)について、「牛肉」及び「豚肉」の先選択項目を、「哺乳類」という上位分類でグループ化する。更に、「哺乳類」の上位分類及び「鶏肉」の先選択項目を、「動物(肉)」という上位分類でグループ化する。この場合、下記の表1(以下、表は詳細資料に記載)に示すようなデータテーブルが作成される。一方で、後の選択カテゴリー(部位の種類)については、上述した上位分類(「哺乳類」、「動物(肉)」)や先選択項目(「牛肉」、「豚肉」、「鶏肉」)と関連づけた下記の表2に示すようなデータテーブルを作成する。これらのデータテーブルを用いることで、例えば、先選択項目として「牛肉」が選択された場合、下記の表1のデータテーブルから、「牛肉」に関連づけられた「哺乳類」と、その「哺乳類」に関連付けられた「動物(肉)」とが選択される。その後、その選択結果である「哺乳類」、「動物(肉)」、更には選択された「牛肉」のいずれかに関連付けられた肉の部位を、下記の表2のデータテーブルから抽出し、後の選択カテゴリーとして顧客に提示される。これを受けて、顧客が後選択項目として「モモ」を選択した場合、下記の表3に示すようなデータテーブルから、「牛肉・モモ」に関連付けられた商品番号(検索対象項目)が検索され、商品番号4に対応する「牛のモモ肉」の商品が顧客に提示される。

【先行技術文献】
【特許文献】
【特許文献1】特許第4853797号公報

 

課題

 近年、複数の関係項目の中から指定された関係項目に関連付けられた検索対象項目を、複数の検索対象項目の中からコンピュータによって検索する検索処理において、処理の高速化が重要性を増している。特に、近年のコンピュータの処理能力の向上や記憶容量の向上に応じて、様々なデータベースは、蓄積される検索対象項目の数や関係項目の数が膨大になる一方、コンピュータの処理能力の向上スピードが従来と比べて鈍化していることから、より効率的な検索方法によって検索処理の高速化を実現することが望まれる。

 前記特許文献1で示された例における最終目的は、商品分類の区分けを記録するだけの表1や表2に示すようなデータテーブルよりもレコード数が圧倒的に多い前記表3に示すようなデータテーブルから、目的とする商品番号を検索することである。すなわち、前記特許文献1に開示のデータ構造において、指定された関係項目(選択された先選択項目(例えば「牛肉」)及び選択された後選択項目(例えば「モモ」))に関連づけられた検索対象項目(例えば「牛のモモ肉」の商品番号)を検索するために用いられるデータテーブルは、前記表3に示すように、各検索対象項目とその検索対象項目に関係する関係項目(先選択項目及び後選択項目)とが関連づけられた一般的なデータ構造と変わらない。したがって、前記特許文献1に開示のデータ構造を用いた検索処理では、検索処理の高速化を図ることはできない。

 本発明は、上述した課題に鑑みてなされたものであり、その目的とするところは、検索処理を高速化でき る 情 報検索装置、検索用プログラム 、 デ ータベースの 更 新 装置、データベース 更 新 用プログラムを提供することである。 

手段

 前記目的を達成するために、請求項1の発明は、複数の関係項目の中から指定された関係項目に関連付けられた検索対象項目を、複数の検索対象項目の中からコンピュータによって検索する 情 報 検 索 装 置 であって、前記複数の関係項目のうちの2つ以上の関係項目に同一の上位項目を関連づけた第一データと、前記複数の検索対象項目のうち、前記同一の上位項目が関連づけられた関係項目に関係する検索対象項目に、該上位項目を関連づけた第二データと、前記第一データ及び前記第二データでは関連づけられない関係項目と検索対象項目とを関連づけた第三データと、を有する デ ー タ 構 造 を も つ デ ー タ ベ ー ス を 用 い 、前 記 複 数 の 関 係 項 目 の 中 か ら 1 つ 以 上 の 関 係 項 目 が 指 定 さ れ た 所 定 の 検 索 条 件 で の 検 索 を行 う 場 合 、 前 記 コ ン ピ ュ ー タ が 、 前 記 第 一 デ ー タ を 参 照 し 、 該 1 つ 以 上 の 関 係 項 目 の う ちの 一 部 又 は 全 部 が 関 連 づ け ら れ た 上 位 項 目 が 存 在 す る と 判 断 し た と き は 、 少 な く と も 前 記第 二 デ ー タ を 検 索 し 、 前 記 関 連 づ け ら れ た 上 位 項 目 が 存 在 し な い と 判 断 し た と き は 、 前 記第 三 デ ー タ の み を 検 索 す る ことを特徴とするものである。
 本発明は、検索に用いられるデータベースが、上述した第一データ、第二データ及び第三データを含むデータ構造をもつことで、検索処理の高速化を実現するものである。
 詳しくは、本発明に係るデータ構造をもったデータベースでは、第一データを参照して、2つ以上の関係項目が関連づけられた上位項目と検索対象項目とが関連づけられた第二データと、第一データ及び第二データでは関連づけられない関係項目と検索対象項目とが関連づけられた第三データとから、指定された関係項目(指定関係項目)に関係する検索対象項目を検索する。
 第二データは、2つ以上の関係項目が上位項目にまとめられて検索対象項目と関連づけされたものであるため、第二データ及び第三データの両方を足し合わせたレコード数は、関係項目と検索対象項目との関連のすべてを両者の直接的な対応関係のみで記録した一般的なデータ構造をもつデータベースのレコード数よりも少ない。したがって、本発明に係るデータ構造をもったデータベースを用いた場合、第二データ及び第三データの両方から指定関係項目に関係する検索対象項目を検索するときの検索処理速度は、上述した一般的なデータ構造をもつデータベースを用いた場合よりも高速化できる。
 ここで、本発明において特筆すべきは、2つ以上の関係項目が指定された所定の検索条件の検索処理を行う場合に飛躍的な高速化が望める点である。

 例えば、第一データにおいて同一の上位項目に関連づけられた2つ以上の関係項目の全部に関係する検索対象項目を第二データに含めた場合、指定された2つ以上の関係項目をAND条件で検索する際には、その指定された2つ以上の関係項目が当該同一の上位項目に関連づけられた2つ以上の関係項目と一致するときは、第三データに対する検索を行わずに、その上位項目に関連づけられた検索対象項目を第二データから検索するだけで、検索処理を完了できる。この場合の第二データは、上位項目が関連づけられた2以上の関係項目の全部に関係する検索対象項目しか含まないので、そのレコード数が少なく、その検索処理速度は、一般的なデータ構造をもつデータベースを用いた場合よりも大幅に高速化できる。また、この場合、指定された2つ以上の関係項目が当該同一の上位項目に関連づけられた2つ以上の関係項目と一致しない場合には、第二データに対する検索を行わずに、その指定された2つ以上の関係項目に関連づけられた検索対象項目を第三データからAND条件で検索するだけで、検索処理を完了できる。第三データは、第一データ及び第二データでは関連づけられない関係項目と検索対象項目とを関連づけるレコードしか含まないので、そのレコード数は少なく、その検索処理速度は、一般的なデータ構造をもつデータベースを用いた場合よりも、大幅に高速化できる。
 また、例えば、第一データにおいて同一の上位項目に関連づけられた2つ以上の関係項目の少なくとも1つに関係する検索対象項目を第二データに含めた場合、指定された2つ以上の関係項目をOR条件で検索する際には、その指定された2つ以上の関係項目が当該同一の上位項目に関連づけられた2つ以上の関係項目に含まれているときは、第三データに対する検索を行わずに、その上位項目に関連づけられた検索対象項目を第二データから検索するだけで、検索処理を完了できる。この場合の第二データは、上位項目が関連づけられた2以上の関係項目の少なくとも1つに関係する検索対象項目しか含まないので、そのレコード数が少なく、その検索処理速度は、一般的なデータ構造をもつデータベースを用いた場合よりも大幅に高速化できる。また、この場合、指定された2つ以上の関係項目のいずれも当該同一の上位項目に関連づけられた2つ以上の関係項目に含まれていない場合には、第二データに対する検索を行わずに、その指定された2つ以上の関係項目に関連づけられた検索対象項目を第三データからOR条件で検索するだけで、検索処理を完了できる。第三データは、第一データ及び第二データでは関連づけられない関係項目と検索対象項目とを関連づけるレコードを含まないので、そのレコード数は少なく、その検索処理速度は、一般的なデータ構造をもつデータベースを用いた場合よりも、大幅に高速化できる。ただし、第一データにおいて同一の上位項目に関連づけられた2つ以上の関係項目の少なくとも1つに関係する検索対象項目をその上位項目と関連づけて記録する第二データのテーブル(以下「テーブルB」という。)は、第一データにおいて同一の上位項目に関連づけられた2つ以上の関係項目の全部に関係する検索対象項目をその上位項目と関連づけて記録する第二データのテーブル(以下「テーブルA」という。)とは別のテーブルで記録することが望ましい。両者の関連は内容的に異なるにもかかわらず、両者を同一のテーブルに記録するとその差異が区別できなくなるからである。また、第一データにおいて同一の上位項目に関連づけられた2つ以上の関係項目の少なくとも1つに関係する検索対象項目は、当然に第一データにおいて同一の上位項目に関連づけられた2つ以上の関係項目の全部に関係する検索対象項目を包含する。したがって、テーブルAに記録したレコードはテーブルBには記録しないようにすることが、データの重複記録防止の観点から望ましい。
 このように、上述したような所定の検索条件での検索処理が高速化する結果、本発明に係るデータ構造をもったデータベースを用いた場合の検索処理速度の期待値は、一般的なデータ構造をもつデータベースを用いた場合よりも大幅に向上する。
 そして、本発明によれば、このような所定の検索条件を見込んで、上位項目に関連づける2つ以上の関係項目を適切に設計すれば、単一条件での検索が可能な第二データに対する検索処理を行う頻度を高めることができる。単一条件での検索が可能な第二データに対する検索処理は、レコード数が同じ場合、AND条件やOR条件での検索を行う第三データに対する検索処理よりも高速な検索が可能である。したがって、検索処理速度の期待値は、より一層向上する。

 

 

効果

 本発明によれば、検索処理を高速化することができるという優れた効果が奏される。

問い合わせ・詳細資料閲覧

特許情報詳細や資料のダウンロード等については無料会員登録後に閲覧していただけます。

本研究に関するご質問や、話を聞いてみたいなどご興味をお持ちになりましたら、是非お気軽に以下のフォームにお問い合わせください。

特許情報

特許6269884

JPB 006269884-000000