Top > Search of International Patents > PARTIAL GRAPH DETECTION DEVICE, PARTIAL GRAPH DETECTION METHOD, PROGRAM, DATA STRUCTURE OF DATA AND INFORMATION RECORDING MEDIUM

PARTIAL GRAPH DETECTION DEVICE, PARTIAL GRAPH DETECTION METHOD, PROGRAM, DATA STRUCTURE OF DATA AND INFORMATION RECORDING MEDIUM

Foreign code F120006556
File No. S2009-0457-C0
Posted date May 10, 2012
Country WIPO
International application number 2009JP067476
International publication number WO 2010/041678
Date of international filing Oct 7, 2009
Date of international publication Apr 15, 2010
Priority data
  • P2008-260827 (Oct 7, 2008) JP
Title PARTIAL GRAPH DETECTION DEVICE, PARTIAL GRAPH DETECTION METHOD, PROGRAM, DATA STRUCTURE OF DATA AND INFORMATION RECORDING MEDIUM
Abstract Provided is a partial graph detection device which enables, for example, acquisition of a list of genes showing changes in expression in common caused by the administration of specific drug(s) while considering the relationship among the genes (for example, the interacting relationship among the genes), acquisition of a list of proteins showing changes in expression in common caused by the administration of specific drug(s) while considering the relationship among the proteins (for example, the interacting relationship among the proteins), or acquisition of a list of users buying the same commercial product(s) while considering the relationship among the users (for example, friendships). A graph data-acquiring section (20) acquires graph data showing a graph including a plurality of vertexes. A vertex data-acquiring section (22) acquires vertex data wherein the vertexes are associated with information. Based on the graph data and the vertex data, a partial graph-detecting section (24) detects a partial graph which is a partial graph of the aforesaid graph and in which the sets of information associated with the individual vertexes have a specific relationship.
Scope of claims (In Japanese)
【請求項1】複数の頂点と1又は複数のエッジとを含むグラフを示すグラフデータを取得するグラフデータ取得手段と、前記頂点に情報を関連づけてなる頂点データを取得する頂点データ取得手段と、前記グラフデータと、前記頂点データと、に基づいて、前記グラフの部分グラフであって、該部分グラフの各頂点に関連付けられた前記情報が所定関係を有する部分グラフを検出する部分グラフ検出手段と、を含むことを特徴とする部分グラフ検出装置。

【請求項2】前記情報は、少なくとも一種の要素を含む要素集合を示し、前記部分グラフ検出手段は、前記グラフの部分グラフであって、該部分グラフの各頂点に関連づけられた要素集合の積集合がN(N≧1)種以上の要素を含む部分グラフの検出を実行すること、を特徴とする請求項1に記載の部分グラフ検出装置。

【請求項3】前記部分グラフ検出手段は、各ノードが前記グラフの頂点の集合を示す探索木であって、かつ、親ノードが示す頂点集合に当該頂点集合のうちの末端頂点に隣接する一つの頂点を新たな末端頂点として追加してなる頂点集合を当該親ノードの子ノードとして有する探索木の各ノードを、深さ優先探索アルゴリズムに従った探索順序で判定対象とし、前記判定対象のノードが示す頂点集合が複数の頂点を含む場合に該頂点集合の各頂点に関連づけられた要素集合の積集合がN種以上の要素を含むか否かの判定を実行する判定手段と、前記判定手段の判定結果に基づいて前記検出を実行する手段と、を含み、前記判定手段は、前記探索木のうちの第1のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合が、前記第1のノードが示す頂点集合のうちの末端頂点と同じ頂点を末端頂点とする頂点集合を示すノードであって、かつ、前記第1のノードよりも探索順序が前のノードである第2のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合に含まれる場合、前記第1のノードの子孫のノードが示す頂点集合を前記判定対象とした前記判定を実行しないこと、を特徴とする請求項2に記載の部分グラフ検出装置。

【請求項4】前記部分グラフ検出手段は、前記判定が実行された場合に、前記判定対象の頂点集合の各頂点に関連づけられた要素集合の積集合を、基準集合として、当該判定対象の頂点集合のうちの末端頂点に関連づけて基準集合記憶手段に記憶させる手段を含み、前記判定手段は、前記第1のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合が、前記第1のノードが示す頂点集合のうちの末端頂点に関連づけて前記基準集合記憶手段に記憶される基準集合に含まれる場合、前記第1のノードの子孫のノードが示す頂点集合を前記判定対象とした前記判定を実行しないこと、を特徴とする請求項3に記載の部分グラフ検出装置。

【請求項5】前記部分グラフ検出手段は、各ノードが前記グラフの頂点の集合を示す探索木であって、かつ、親ノードが示す頂点集合に当該頂点集合のうちの末端頂点に隣接する一つの頂点を新たな末端頂点として追加してなる頂点集合を当該親ノードの子ノードとして有する探索木の各ノードを、深さ優先又は幅優先探索アルゴリズムに従った探索順序で判定対象とし、前記判定対象のノードが示す頂点集合が複数の頂点を含む場合に該頂点集合の各頂点に関連づけられた要素集合の積集合がN種以上の要素を含むか否かの判定を実行する判定手段と、前記判定手段の判定結果に基づいて前記検出を実行する手段と、を含み、前記判定手段は、前記探索木のうちの第1のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合が、前記第1のノードが示す頂点集合のうちの末端頂点と同じ頂点を末端頂点とする頂点集合を示すノードであって、かつ、前記第1のノードが示す頂点集合を含む頂点集合を示す第2のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合に含まれる場合、前記第1のノードの子孫のノードが示す頂点集合を前記判定対象とした前記判定を実行しないこと、を特徴とする請求項2に記載の部分グラフ検出装置。

【請求項6】前記部分グラフ検出手段は、各ノードが前記グラフの頂点の集合を示す探索木であって、かつ、親ノードが示す頂点集合に当該頂点集合のうちの末端頂点に隣接する一つの頂点を新たな末端頂点として追加してなる頂点集合を当該親ノードの子ノードとして有する探索木の各ノードを、深さ優先探索アルゴリズムに従った探索順序で判定対象とし、前記判定対象のノードが示す頂点集合が複数の頂点を含む場合に該頂点集合の各頂点に関連づけられた要素集合の積集合がN種以上の要素を含むか否かの判定を実行する判定手段と、前記判定手段の判定結果に基づいて前記検出を実行する手段と、を含み、前記判定手段は、前記探索木のうちの第3のノードが示す頂点集合が一つの頂点のみを含み、かつ、当該頂点に関連づけられた要素集合が、当該頂点を末端頂点とする頂点集合を示すノードであって、かつ、前記第3のノードよりも探索順序が前のノードである第4のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合に含まれる場合、前記第3のノードの子孫のノードが示す頂点集合を前記判定対象とした前記判定を実行しないこと、を特徴とする請求項2に記載の部分グラフ検出装置。

【請求項7】前記部分グラフ検出手段は、前記判定が実行された場合に、前記判定対象のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合を、基準集合として、前記判定対象のノードが示す頂点集合のうちの末端頂点に関連づけて基準集合記憶手段に記憶させる手段を含み、前記判定手段は、前記第3のノードが示す頂点集合が一つの頂点のみを含み、かつ、当該頂点に関連づけられた要素集合が、当該頂点に関連づけて前記基準集合記憶手段に記憶される基準集合に含まれる場合に、前記第3のノードの子孫のノードが示す頂点集合を前記判定対象とした前記判定を実行しないこと、を特徴とする請求項6に記載の部分グラフ検出装置。

【請求項8】前記部分グラフ検出手段は、各ノードが前記グラフの頂点の集合を示す探索木であって、かつ、親ノードが示す頂点集合に当該頂点集合のうちの末端頂点に隣接する一つの頂点を新たな末端頂点として追加してなる頂点集合を当該親ノードの子ノードとして有する探索木の各ノードを、深さ優先又は幅優先探索アルゴリズムに従った探索順序で判定対象とし、前記判定対象のノードが示す頂点集合が複数の頂点を含む場合に該頂点集合の各頂点に関連づけられた要素集合の積集合がN種以上の要素を含むか否かの判定を実行する判定手段と、前記判定手段の判定結果に基づいて前記検出を実行する手段と、を含み、前記判定手段は、前記探索木のうちの第3のノードが示す頂点集合が一つの頂点のみを含み、当該頂点に関連づけられた要素集合が、当該頂点を末端頂点とする頂点集合を示す第4のノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合に含まれる場合、前記第3のノードの子孫のノードが示す頂点集合を前記判定対象とした前記判定を実行しないこと、を特徴とする請求項2に記載の部分グラフ検出装置。

【請求項9】前記部分グラフ検出手段は、各ノードが前記グラフの頂点の集合を示す探索木であって、かつ、親ノードが示す頂点集合に当該頂点集合の末端頂点に隣接する一つの頂点を新たな末端頂点として追加してなる頂点集合を当該親ノードの子ノードとして有する探索木の各ノードを、深さ優先探索又は幅優先探索アルゴリズムに従った探索順序で判定対象とし、前記判定対象のノードが示す頂点集合が複数の頂点を含む場合に該頂点集合の各頂点に関連づけられた要素集合の積集合がN種以上の要素を含むか否かの判定を実行する判定手段と、前記判定手段の判定結果に基づいて前記検出を実行する手段と、を含み、前記判定手段は、前記ノードが示す頂点集合の各頂点に関連づけられた要素集合の積集合がN種以上の要素を含んでいない場合、当該ノードの子孫のノードが示す頂点集合を前記判定対象とした前記判定を実行しないこと、を特徴とする請求項2に記載の部分グラフ検出装置。

【請求項10】複数の頂点と1又は複数のエッジとを含むグラフを示すグラフデータを取得するグラフデータ取得ステップと、前記頂点に情報を関連づけてなる頂点データを取得する頂点データ取得ステップと、前記グラフデータと、前記頂点データと、に基づいて、前記グラフの部分グラフであって、該部分グラフに含まれる各頂点に関連付けられた前記情報が所定関係を有する部分グラフを検出する部分グラフ検出ステップと、を含むことを特徴とする部分グラフ検出方法。

【請求項11】複数の頂点と1又は複数のエッジとを含むグラフを示すグラフデータを取得するグラフデータ取得手段、前記頂点に情報を関連づけてなる頂点データを取得する頂点データ取得手段、及び、前記グラフデータと、前記頂点データと、に基づいて、前記グラフの部分グラフであって、該部分グラフに含まれる各ノードに関連付けられた前記情報が所定関係を有する部分グラフを検出する部分グラフ検出手段、としてコンピュータを機能させるプログラム。

【請求項12】複数の頂点と1又は複数のエッジとを含むグラフを示すグラフデータを取得するグラフデータ取得手段、前記頂点に情報を関連づけてなる頂点データを取得する頂点データ取得手段、及び、前記グラフデータと、前記頂点データと、に基づいて、前記グラフの部分グラフであって、該部分グラフに含まれる各ノードに関連付けられた前記情報が所定関係を有する部分グラフを検出する部分グラフ検出手段、としてコンピュータを機能させるプログラムを記録したコンピュータ読み取り可能な情報記憶媒体。

【請求項13】複数の頂点と1又は複数のエッジとを含むグラフを示すグラフデータと、前記頂点に情報を関連づけてなる頂点データと、を含むことを特徴とするデータのデータ構造。

【請求項14】複数の頂点と1又は複数のエッジとを含むグラフを示すグラフデータと、前記頂点に情報を関連づけてなる頂点データと、を含むことを特徴とするデータを記録したコンピュータ読み取り可能な情報記憶媒体。
  • Applicant
  • ※All designated countries except for US in the data before July 2012
  • OCHANOMIZU UNIVERSITY
  • Inventor
  • SESE, Jun
  • SEKI, Mio
IPC(International Patent Classification)
Specified countries AE(UTILITY MODEL),AG,AL(UTILITY MODEL),AM(PROVISIONAL PATENT)(UTILITY MODEL),AO(UTILITY MODEL),AT(UTILITY MODEL),AU,AZ(UTILITY MODEL),BA,BB,BG(UTILITY MODEL),BH(UTILITY MODEL),BR(UTILITY MODEL),BW(UTILITY MODEL),BY(UTILITY MODEL),BZ(UTILITY MODEL),CA,CH,CL(UTILITY MODEL),CN(UTILITY MODEL),CO(UTILITY MODEL),CR(UTILITY MODEL),CU(INVENTOR'S CERTIFICATE),CZ(UTILITY MODEL),DE(UTILITY MODEL),DK(UTILITY MODEL),DM,DO(UTILITY MODEL),DZ,EC(UTILITY MODEL),EE(UTILITY MODEL),EG(UTILITY MODEL),ES(UTILITY MODEL),FI(UTILITY MODEL),GB,GD,GE(UTILITY MODEL),GH(UTILITY CERTIFICATE),GM,GT(UTILITY MODEL),HN,HR(CONSENSUAL PATENT),HU(UTILITY MODEL),ID,IL,IN,IS,JP(UTILITY MODEL),KE(UTILITY MODEL),KG(UTILITY MODEL),KM,KN,KP(INVENTOR'S CERTIFICATE)(UTILITY MODEL),KR(UTILITY MODEL),KZ(PROVISIONAL PATENT)(UTILITY MODEL),LA,LC,LK,LR,LS(UTILITY MODEL),LT,LU,LY,MA,MD(UTILITY MODEL),ME,MG,MK,MN,MW,MX(UTILITY MODEL),MY(UTILITY-INNOVATION),MZ(UTILITY MODEL),NA,NG,NI(UTILITY MODEL),NO,NZ,OM(UTILITY MODEL),PE(UTILITY MODEL),PG,PH(UTILITY MODEL),PL(UTILITY MODEL),PT(UTILITY MODEL),RO,RS(PETTY PATENT),RU(UTILITY MODEL),SC,SD,SE,SG,SK(UTILITY MODEL),SL(UTILITY MODEL),SM,ST,SV(UTILITY MODEL),SY,TJ(UTILITY MODEL),TM(PROVISIONAL PATENT),TN,TR(UTILITY MODEL),TT(UTILITY CERTIFICATE),TZ,UA(UTILITY MODEL),UG(UTILITY CERTIFICATE),US,UZ(UTILITY MODEL),VC(UTILITY CERTIFICATE),VN(PATENT FOR UTILITY SOLUTION),ZA,ZM,ZW,EP(AT,BE,BG,CH,CY,CZ,DE,DK,EE,ES,FI,FR,GB,GR,HR,HU,IE,IS,IT,LT,LU,LV,MC,MK,MT,NL,NO,PL,PT,RO,SE,SI,SK,SM,TR),OA(BF(UTILITY MODEL),BJ(UTILITY MODEL),CF(UTILITY MODEL),CG(UTILITY MODEL),CI(UTILITY MODEL),CM(UTILITY MODEL),GA(UTILITY MODEL),GN(UTILITY MODEL),GQ(UTILITY MODEL),GW(UTILITY MODEL),ML(UTILITY MODEL),MR(UTILITY MODEL),NE(UTILITY MODEL),SN(UTILITY MODEL),TD(UTILITY MODEL),TG(UTILITY MODEL)),AP(BW(UTILITY MODEL),GH(UTILITY MODEL),GM(UTILITY MODEL),KE(UTILITY MODEL),LS(UTILITY MODEL),MW(UTILITY MODEL),MZ(UTILITY MODEL),NA(UTILITY MODEL),SD(UTILITY MODEL),SL(UTILITY MODEL),SZ(UTILITY MODEL),TZ(UTILITY MODEL),UG(UTILITY MODEL),ZM(UTILITY MODEL),ZW(UTILITY MODEL)),EA(AM,AZ,BY,KG,KZ,MD,RU,TJ,TM)
Please contact us by E-mail or facsimile if you have any interests on this patent.

PAGE TOP

close
close
close
close
close
close