(57)【要約】【課題】階層データ構造及び非階層データ構造を表示するための方法を提供すること。【解決手段】本発明の方法は、関連するノード間の階層関係または非階層関係を解析し、これらの関係に基づいて円錐グラフ構造を作成する方法である。円錐グラフ構造は三次元または擬似三次元オブジェクトであり、ユーザが操作し、変更を加えることができる。円錐グラフ構造は、ウェブサイト中のウェブページのファイル構造におけるファイルなどの、異なるノード間の関係に対する構造的な理解をユーザに提供するインタフェースである。【選択図】　　　　図１
2004005649.tif 000002
【特許請求の範囲】
【請求項１】
複数のノード間の関係を図形表示するコンピュータ実行方法であって、
前記複数のノードのうち少なくとも２つの間の少なくとも１つの階層関係を識別するステップと、
仮想三次元円錐を作成するステップとを含み、前記仮想三次元円錐が、
円錐の表面上の各ノードの図形表示と、
前記少なくとも１つの階層関係の図形表示とを含む、
コンピュータ実行方法。
【請求項２】
前記複数のノードのうち少なくとも２つの間の少なくとも１つの非階層関係を識別するステップと、
前記少なくとも１つの非階層関係の表示を作成するステップとをさらに含む、
請求項１記載のコンピュータ実行方法。
【請求項３】
前記ノードがウェブページである、請求項１記載の方法。
【請求項４】
階層的にリンクしたノード間の階層関係の図形表示が円錐の表面上の直線である、請求項１記載の方法。
【請求項５】
前記複数のノードのうちの同じ階層を有するノードが、円錐の周りの単一のリング上に表される、請求項１記載の方法。
【請求項６】
円錐の頂点がウェブサイトのホームページである、請求項１記載の方法。
【請求項７】
少なくとも１つの階層関係が、複数の関連する子ノードを有する親ノードを含む、請求項１記載の方法。
【請求項８】
前記複数のノードのうち少なくとも２つの間の少なくとも１つの階層関係を識別する前記ステップが、
頂点ノードと該頂点ノードの少なくとも１つの子ノードとの間の少なくとも１つの階層関係を識別するステップと、
前記少なくとも１つの子ノードと該少なくとも１つの子ノードの全ての子孫との間の少なくとも１つの階層関係を識別するステップとをさらに含む、
請求項１記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、階層データ及び非階層データを同時に表示し操作するためのシステム及び方法に関する。
【０００２】
【従来の技術】
従来、リンクしたオブジェクトの表示はツリー制御レイアウトを用いて行われている。ハードドライブに保存されているファイルのリストに提供されるようなこれらのツリー制御レイアウトは、ファイル又はプログラムなどの低レベル階層オブジェクトをファイルフォルダ又はドライブロケーションなどの高レベル階層オブジェクトに関連付ける階層情報を含む。例えば階層構造をａ：￥ｐｒｏｇｒａｍ　ｆｉｌｅｓ￥ｐｒｏｇｒａｍとすると、階層は以下のようになる。即ち、「ａ」ドライブには「ｐｒｏｇｒａｍ　ｆｉｌｅｓ」というタイトルのフォルダが保存されており、その中には「ｐｒｏｇｒａｍ」と呼ばれるプログラムが保存されていることになる。この構造において、「ａ」ドライブは低レベルのファイルフォルダノードにリンクする高レベルノードであり、そのファイルフォルダノードはさらに低レベルのファイルノードにリンクする。
【０００３】
あるコンピュータ記憶構造では、その記憶構造内のオブジェクト間に階層リンクと非階層リンクの両方が設けられる。階層リンクと非階層リンクの両方を含むコンピュータ記憶構造の例として、ファイル、ハイパーテキストシステム及びワールドワイドウェブのそれぞれの間にリンクを有するコンピュータファイルシステムが挙げられる。非階層リンクの使用はワールドワイドウェブ上のウェブサイトで例示することができる。そこでは、ハイパーリンクがウェブサイトの現在のハイパーテキストページに設けられ、現在のハイパーテキストページとそのウェブサイトの階層構造において現在のドキュメントに直接リンクしていないハイパーテキストページとのリンクを作成する。これらの非階層リンクは、典型的なツリー制御レイアウト構造では適切に表示されない。
【０００４】
【特許文献１】
米国特許第５２９５２４３号明細書
【非特許文献１】
Ｆａｉｒｃｈｉｌｄ，Ｋ．Ｍ．ほか著、「ＳｅｍＮｅｔ：Ｔｈｒｅｅ−Ｄｉｍｅｎｓｉｏｎａｌ　Ｇｒａｐｈｉｃ　Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ　ｏｆ　Ｌａｒｇｅ　Ｋｎｏｗｌｅｄｇｅ　Ｂａｓｅｓ」、Ｃｏｇｎｉｔｉｖｅ　Ｓｃｉｅｎｃｅ　ａｎｄ　ｉｔｓ　Ａｐｐｌｉｃａｔｉｏｎ　ｆｏｒ　Ｈｕｍａｎ　Ｉｎｔｅｒａｃｔｉｏｎ、米国、Ｌａｗｒｅｎｃｅ　Ｅｒｌｂａｕｍ出版、１９８８年、第２０１−２３３頁
【０００５】
【発明が解決しようとする課題】
本発明の目的は、階層データ構造及び非階層データ構造を表示するためのシステム及び方法を提供することである。
【０００６】
本発明の他の目的や利点は以下の記述に一部説明され、この記述より一部明らかになるであろう。或いは本発明の実施によって理解することもできる。特に添付の請求項で指摘した要素や組合せによって、本発明の目的と利点を実現し達成することができる。
【０００７】
【課題を解決するための手段】
上記の目的を達成するために、請求項１に係る発明は、複数のノード間の関係を図形表示するコンピュータ実行方法を提供する。この方法は、複数のノードのうち少なくとも２つの間の少なくとも１つの階層関係を識別するステップと、仮想三次元円錐を作成するステップとを含み、前記仮想三次元円錐が、円錐の表面上の各ノードの図形表示と、前記少なくとも１つの階層関係の図形表示とを含む。
【０００８】
また、請求項２に記載の発明によれば、前記複数のノードのうち少なくとも２つの間の少なくとも１つの非階層関係を識別するステップと、前記少なくとも１つの非階層関係の表示を作成するステップとをさらに含むことが可能である。
【０００９】
上述したノードの例として、請求項３に記載されているように、ウェブページが挙げられる。また、階層的にリンクしたノード間の階層関係の図形表示は、請求項４に記載されているように、円錐の表面上の直線であってもよい。更に、請求項５に記載されているように、前記複数のノードのうちの同じ階層を有するノードが、円錐の周りの単一のリング上に表されるようにしてもよい。請求項６に記載されているように、円錐の頂点をウェブサイトのホームページとすることが可能である。請求項７に記載の方法によれば、少なくとも１つの階層関係が、複数の関連する子ノードを有する親ノードを含むようになっている。
【００１０】
請求項８に記載の方法は、請求項１に記載の方法において、前記複数のノードのうち少なくとも２つの間の少なくとも１つの階層関係を識別する前記ステップが、頂点ノードと該頂点ノードの少なくとも１つの子ノードとの間の少なくとも１つの階層関係を識別するステップと、前記少なくとも１つの子ノードと該少なくとも１つの子ノードの全ての子孫との間の少なくとも１つの階層関係を識別するステップとをさらに含むことを特徴としている。
【００１１】
本発明によれば、階層データ構造及び非階層データ構造を図形表示することが可能となる。
【００１２】
上記の一般的な説明と以下の詳細な説明はどちらも例示と説明のためだけのものであり、請求項に記した本発明を制限するものではないことを理解されたい。
【００１３】
本明細書に組み込まれその一部を構成する添付図面は本発明の１実施形態を例示し、発明の記述と共に本発明の原理を説明する役目を果たす。
【００１４】
【発明の実施の形態】
本発明の好適な実施形態を詳細に参照し、この例を添付図面に例示する。どのような場合でも可能な限り、図面を通して同じ参照番号を用いて同一又は類似の部分について言及することとする。
【００１５】
以下は本発明に適用する定義である。
【００１６】
「プロセッサ」とは、処理機能を提供することができるコンポーネント又はシステムである。プロセッサの例は、汎用コンピュータの中央処理装置（ＣＰＵ）である。
【００１７】
「ユーザ入力装置」とは、ユーザにデータ入力機能を提供するコンピュータコンポーネントである。ユーザ入力装置の例として、キーボード、マウス、トラックボール、タッチパッド、ポインティングデバイスなどが挙げられる。
【００１８】
「構造」とは、ディスプレイ装置上にユーザに対して表示される単一のオブジェクト又は特徴である。表示された構造は、サブ特徴又はサブ構造からなることができる。
【００１９】
「ノードリンク構造」とは、局所化された「ノード」と、ノード間に延びてノードのペア間の接続を提供する「リンク」とに区別できる表示特徴を含む構造である。ノードは一般に点又は小さなオブジェクト構造としてディスプレイ装置に表示することができ、リンクはノードを結ぶ直線又は弧として表示することができる。ノードは、例えばツリーデータ構造又は他の有向グラフデータ構造におけるオブジェクトを表すことができる。ノード構造は「選択可能な構造」であるため、ユーザ側の動作によって、動作されるオブジェクトを「起動」又は選択することができる。ノードを選択する例示的な動作は、マウスボタンでノードをクリックすることである。
【００２０】
「階層構造」とは、多数の構造レベルを有するものとして認識される構造である。例えば階層ノードリンク構造は多数のレベルのノードを有することができ、リンクは低レベルのノードの各々を高レベルのノードに接続する。
【００２１】
「円錐構造」とは、円形又は多角形の準線を有する仮想三次元円錐形状として認識される表示構造である。準線は仮想三次元円錐形状のベースとして表示される。
【００２２】
例示的な円錐グラフ構造１００を図１に示す。円錐グラフ構造１００は、円錐表面１１０、階層経路１２０（円錐１００の表面１１０に実線で示す）、非階層経路１３０（円錐１００の内側に延びる点線で示す）、頂点ノード１４０及び子ノード１５０を含む。円錐１００のノードは、世代によって編成されている。換言すると、ノードの各世代は同一平面リング１５５によって識別され、１つ以上の階層経路１２０及び非階層経路１３０で他の世代から分離されている。ノードの世代が頂点ノード１４０から下へと進むにつれて各リング１５５の半径が十分に広がり、同じ世代のリングが同一平面方向に位置し、階層経路１２０が円錐１００の表面に対して同一平面方向に位置することができる。階層経路及び非階層経路は双方向でも一方向でもよい。即ち、ノード１４０はノード１５０に接続することはできるが、ノード１５０はノード１４０に接続できないかもしれない。これらの関係を種々の太さの直線や種々の色の直線を用いて三次元円錐グラフで表してもよい。
【００２３】
ウェブページ用の第２の例示的な円錐グラフ構造２００を図２に示す。円錐グラフ２００のノードはそれぞれ名前で識別される。ウェブページのノードの例示的な名前は、ＨＯＭＥＰＡＧＥ２１０、ＣＨＩＬＤＰＡＧＥ１２２０、ＣＨＩＬＤＰＡＧＥ２２３０、ＧＲＡＮＤＣＨＩＬＤＰＡＧＥ１２４０、ＧＲＡＮＤＣＨＩＬＤＰＡＧＥ２２５０、ＧＲＡＮＤＣＨＩＬＤＰＡＧＥ３２６０及びＧＲＡＮＤＣＨＩＬＤＰＡＧＥ４２７０を含む。或いは、ノードをアイコン又はノードの存在を識別する他の構造として表示することもできる。ノード自体は構造の選択可能な属性であるため、構造上のあるノードをクリック又は選択することで、この構造に依存するサブ構造を表示したり隠したりすることができる。このオプションにより、指定された点で表示構造の複雑さを増したり減らしたりする機会をユーザに与えることができる。
【００２４】
例示的な円錐グラフ構造２００を、ノード間の階層経路と非階層経路の両方を含む構造を特徴付けるデータを使用して構築することができる。これらの経路は例えばウェブページ（ノード）間のハイパーテキストリンクであり得る。
【００２５】
図３は、円錐グラフ構造を形成する動作の例示的なフローチャートを示す。図３の方法による動作を実行するための例示的なシステムは、中央処理装置（ＣＰＵ）、モニタ及びマウスを有する汎用コンピュータを含む。このフローチャートのために、ウェブサイトのデータをモデル化するために円錐グラフを使用するものとし、そこでは円錐グラフの最初の（頂点）ノードをウェブサイトのホームページとして選択する。
【００２６】
プロセスの第１のステップは、円錐グラフの頂点ノードとしてのノードを選択することである（３００）。上述のように、例示的な頂点ノードとはウェブサイトのホームページである。このノードを円錐の頂上に配置し、「親ノード」と呼ぶ。第２のステップは、親ノードと階層（親子）関係のある円錐グラフ３００上のノード全てを識別することである。次いで親ノードに関連する全ての子ノードからなる無制限リスト構造（ｕｎｂｏｕｎｄｅｄ　ｌｉｓｔ　ｓｔｒｕｃｔｕｒｅ）又はリングを作成する。子ノードはリングにシーケンシャルに配置されてもよいし、ランダムに配置されてもよいし、非階層経路１３０の描画のタスクを簡単にするために非階層関係にあるノードを最大限に互いに離すようにリングに配置されてもよい。図４を参照すると、複数の関連する子４１０を有する代表的な親ノード４００が示されている。一番左又は右の子は親へのポインタを含み、それらの間にある子はそれぞれすぐ左又は右の子を指す。或いは、各子ノード４１０が親４００へのポインタを含んでもよい。ページは以下のように識別することができる。即ち、ホームページからのハイパーテキストリンクと、このホームページを次に高いレベルのリンクとして組み込んだユニバーサルリソースロケータ（ＵＲＬ）とを有する全てのページをその親ノードに対する子ノードとして識別する。例えば、図２の円錐構造２００を構築するために使用する、ウェブページに基づいたハイパーテキストリンクはｈｔｔｐ：／／ｗｗｗ．ＨＯＭＥＰＡＧＥ・ＣＨＩＬＤＰＡＧＥ１．ｃｏｍとなる。このハイパーリンクは、ＣＨＩＬＤＰＡＧＥ１を階層構造においてＨＯＭＥＰＡＧＥの次に低いレベルのリンクとして識別する。親ノードに対する親子関係を全て識別するために、この判定をウェブサイトの全てのページに対して実行する。
【００２７】
親ノードに対する子全てを識別し無制限リストを作成すると、処理は１レベル下の子ノードにシフトする。各子ノードに対して、子ノードと親子関係を持つ円錐グラフ３００上の孫ノード全てを識別する。再び図２を参照すると、ＧＲＡＮＤＣＨＩＬＤＰＡＧＥ２、ＧＲＡＮＤＣＨＩＬＤＰＡＧＥ３及びＧＲＡＮＤＣＨＩＬＤＰＡＧＥ４を識別するＵＲＬがＣＨＩＬＤＰＡＧＥ２と親子関係にあることが示されている。各子ノードに対して孫ノードが識別されると、これらの孫ノードからなる無制限リスト構造又はリングを作成する。次いでこのプロセスを全ての孫ノードを識別するまで繰り返す。
【００２８】
親ノードに関連する子ノード全てを識別しこれらの子ノードからなる無制限リスト構造又はリングを作成するこのプロセスは、円錐グラフの全ての世代に対して下に向かって続けられる。階層（親子）関係の識別を上記のように幅優先で展開してもよいし、本発明の趣旨や範囲から逸脱しないならば、深さ優先（ある子に向かって階層を下へと進み、上に戻って隣の子に移り、さらに階層を下へと進む）で展開してもよい。
【００２９】
階層関係が識別されると処理はステップ３２０（図３）へと移り、そこでは非階層関係が識別される。先に示したように非階層経路１３０は、階層関係を持たない子ノードと親ノードとの間の経路である。ウェブページとの関係で言うと、非階層経路はウェブサイトのページ間のハイパーテキストリンクであり、そこではＵＲＬのどのリンクも相手を階層構造における次に高いレベルのページとして識別しない。例えば図２に示す構造に基づくと、ＧＲＡＮＤＣＨＩＬＤＰＡＧＥ１を識別するＵＲＬはＣＨＩＬＤＰＡＧＥ２に階層的にリンクしていないが、非階層リンク２８０はこれら２つのページを接続するものとして示されている。
【００３０】
階層関係及び非階層関係の全てが識別された後、処理はステップ３３０へと移り、そこで三次元円錐グラフ表現を階層関係及び非階層関係に基づいて構築する。１実施形態では、各ノードに多角形を、エッジに直線を割り当てることで三次元円錐グラフを描く。Ｘ、Ｙ及びＺ座標面の種々の位置で多角形を描く。Ｚ軸が円錐グラフの長手軸に対応する場合、Ｚは各世代で一定である。ＸとＹは各リング１５５に沿った各点のサインとコサインに基づいて変化する。
【００３１】
図５を参照すると、三次元円錐グラフを構築するための別のプロセスが示されている。図５に示すように、ソースノードと呼ばれる第１のノードを訪ねて（ステップ５００）それに接続するノード（ターゲットノード）を識別することで、三次元円錐グラフを描くことができる。ステップ５００で識別した各ターゲットノードに対して、そのターゲットノードが同じリンク上にあるか又は別のリング上にあるかを判定する（ステップ５１０）。そのターゲットノードが同じリング上にあるならば、そのノードはソースノードの兄弟（同世代）であり同じリング上に配置されるべきものである（ステップ５２０）。そのターゲットノードが別のリング上にあるならば、それがソースノードの祖先（ソースノードより上）であるか子孫（ソースノードより下）であるかを判定する（ステップ５３０）。次いで処理はステップ５４０に移り、そこでターゲットノードは、該ターゲットノードがソースノードよりも上又は下であるといった世代の数に基づいて、ソースノードから離れた円錐グラフの適切なリング上に配置される。次のステップは、訪れていない他のソースノードを選択することであり（ステップ５５０）、新しいソースノードに関連するターゲットノード全てを識別することである（ステップ５６０）。次いで処理はステップ５１０に移る。このプロセスを円錐グラフの全てのノードに対して繰り返す。
【００３２】
円錐グラフ構造が作成されると、それをコンピュータにより生成された三次元（又は擬似三次元）オブジェクトとして見たり操作したりできる。これらの操作には、回転、ズーム変更、構造のスライス（例えば構造の特定のセグメントに焦点を当てるために構造の層を視界から取り除くこと）及び構造の剥ぎ取り（ｓｋｉｎｎｉｎｇ、構造内の非階層リンクがより明確に見えるように階層リンクを含む構造の表面を取り除くこと）が含まれる。
【００３３】
円錐構造を形成するために使用するデータ中の特定の情報を強調したり別の方法で表示したりするために、種々の表示特性を円錐グラフ構造に対して選択することができる。これらのオプションには、円錐のユーザに向いた側の階層情報だけが見えるように、図６に示すように円錐グラフの表面を不透明にすることも含まれる。或いは、残りの情報がより詳細に見えるように階層リンク又は非階層リンクを取り除くこともできる。別のオプションは表面を透明することであり、それによって階層リンクと非階層リンクを両方とも別の方法で一緒に表示することができる。
【００３４】
ユーザにリングの高さや幅を変更するオプションを与えることもできる。これらの値を、ファイルサイズなどの、円錐グラフを作成するために使用するベースデータの特性にリンクさせることもできる。或いは、表示されるレベルに存在する子ノードの数を反映するように、リングの高さや幅のサイズを選択してもよい。
【００３５】
別の構成では図７に示すように円錐構造７００を上から見ることができ、この構造は同心円としてデータを表示し、ノード構造のルーツ７１０（頂点ノード）は同心円の中心に設けられ、リング上の子はこの中心から延びる。この構成を変更して、図８に示すように、円錐グラフ構造を円錐ツリー構造として提供することもできる。
【図面の簡単な説明】
【図１】円錐グラフの第１の例示的な実施形態を図形表示した図である。
【図２】円錐グラフの第２の例示的な実施形態を図形表示した図である。
【図３】円錐グラフを作成する例示的な方法のフローチャートである。
【図４】複数の関連する子ノード４１０を有する代表的な親ノードを示す図である。
【図５】円錐グラフを作成する別の方法のフローチャートである。
【図６】不透明な外面を有する例示的な円錐グラフを図形表示した図である。
【図７】上から見た例示的な円錐グラフを図形表示した図である。
【図８】ツリー構造として表示された例示的な円錐グラフを図形表示した図である。
【符号の説明】
１００、２００、６００、７００、８００　　円錐グラフ構造
１１０　　円錐表面
１２０　　階層経路
１３０、２８０　　非階層経路
１４０、２１０　　頂点ノード
１５０、４１０ａ〜４１０ｅ　　子ノード
４００　　親ノード
【図１】
2004005649.tif 000003
【図２】
2004005649.tif 000004
【図３】
2004005649.tif 000005
【図４】
2004005649.tif 000006
【図５】
2004005649.tif 000007
【図６】
2004005649.tif 000008
【図７】
2004005649.tif 000009
【図８】
2004005649.tif 000010