JPH0877057A - Searching method for hypermedia - Google Patents
Searching method for hypermediaInfo
- Publication number
- JPH0877057A JPH0877057A JP6206548A JP20654894A JPH0877057A JP H0877057 A JPH0877057 A JP H0877057A JP 6206548 A JP6206548 A JP 6206548A JP 20654894 A JP20654894 A JP 20654894A JP H0877057 A JPH0877057 A JP H0877057A
- Authority
- JP
- Japan
- Prior art keywords
- node
- destination
- search
- data
- link
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
- 238000000034 method Methods 0.000 title claims abstract description 91
- 230000008569 process Effects 0.000 claims abstract description 73
- 238000012217 deletion Methods 0.000 claims description 4
- 230000037430 deletion Effects 0.000 claims description 4
- 238000004904 shortening Methods 0.000 abstract 1
- 238000007726 management method Methods 0.000 description 19
- 238000010586 diagram Methods 0.000 description 3
- 230000008901 benefit Effects 0.000 description 2
- 230000004913 activation Effects 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 238000010276 construction Methods 0.000 description 1
- 238000013500 data storage Methods 0.000 description 1
- 230000014509 gene expression Effects 0.000 description 1
- 230000004044 response Effects 0.000 description 1
Landscapes
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
Description
【０００１】[0001]
【産業上の利用分野】本発明は、ハイパーメディアの探
索方法に関するものである。BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a hypermedia search method.
【０００２】[0002]
【従来の技術】従来、このような分野の技術としては、
例えば、次のような文献に記載されるものがあった。 文献；ＩＥＥＥ ＣＯＭＰＵＴＥＲ、１９８８−１、
（米）、N.Yankelovich,B.J.Haan,N.K.Meyrowitz,and
S.M.Drucker著、"Intermedia:The Concept and the Con
struction of a Seamless Information Environment"
、Ｐ８１−９６ ハイパーメディアは、マルチメディアのデータがノード
と呼ばれる単位でまとめられ、関連あるノード同士がリ
ンクで結合された構造をしており、利用者はその中を主
としてリンクを辿ること（以下、ナビゲーションと呼
ぶ）によりデータを探索する。ナビゲーションの内部処
理としては、前記文献に代表されるように、利用者があ
るノードの任意のリンクを選択し、ナビゲートコマンド
を入力した時点で、システムが宛先のノードに相当する
ファイルを開き、内容を利用者に提示するというハイパ
ーメディアの探索方法が一般的である。この場合、内容
を利用者に提示するシステム提示処理を専門に行なう提
示プロセスを起動してもよい。また、データの格納先は
通常のファイルではなく、データベースでもよい。すな
わちシステムは利用者のナビゲートコマンドの入力によ
り、宛先ノードの内容を表示するためのデータ提示プロ
セスを起動する。提示プロセスは宛先ノードの内容とな
るデータをファイルまたはデータベースからメモリ上へ
ロードし、出力装置へデータを提示する。なお、ノード
が持つデータは一般にテキストのみならず、画像、音
声、グラフィクスなどを統合的に含むマルチメディアの
データである。2. Description of the Related Art Conventionally, techniques in such a field include:
For example, some documents were described in the following documents. Reference; IEEE COMPUTER, 1988-1,
(US), N.Yankelovich, BJHaan, NKMeyrowitz, and
SMDrucker, "Intermedia: The Concept and the Con
construction of a Seamless Information Environment "
, P81-96 Hypermedia has a structure in which multimedia data is collected in a unit called a node, and related nodes are linked by a link, and a user mainly follows a link (hereinafter referred to as a link). , Called navigation). As the internal processing of the navigation, as typified by the above literature, when the user selects an arbitrary link of a node and inputs a navigation command, the system opens a file corresponding to the destination node, A hypermedia search method of presenting contents to a user is common. In this case, a presentation process that specializes in system presentation processing for presenting the contents to the user may be activated. Further, the data storage destination may be a database instead of an ordinary file. That is, the system activates a data presentation process for displaying the contents of the destination node in response to the user's input of a navigation command. The presentation process loads the data that is the contents of the destination node from the file or database onto the memory, and presents the data to the output device. The data that the node has is generally not only text but also multimedia data that integrally includes images, sounds, graphics, and the like.
【０００３】[0003]
【発明が解決しようとする課題】しかしながら、従来の
ハイパーメディアの探索方法においては、次のような課
題があった。ハイパーメディアをナビゲートする時にデ
ータのデータベースからメモリへのローディングに時間
がかかるといった問題点がある。そのため、利用者がリ
ンクを辿って別のノードへ移ろうとするたびに、待ち時
間が生じ、利用者にとって使いづらいシステムになる。
特に、この問題はリアルタイム性が要求されるシステム
では切実である。However, the conventional hypermedia searching method has the following problems. There is a problem that it takes time to load the data from the database to the memory when navigating the hypermedia. Therefore, each time the user tries to move to another node by following the link, a waiting time occurs and the system becomes difficult for the user to use.
In particular, this problem is urgent in a system that requires real-time processing.
【０００４】[0004]
【課題を解決するための手段】第１の発明は、前記課題
を解決するために、マルチメディアのデータがノードの
単位でまとめられ関連あるノード同士がリンクで結合さ
れた構造を有し、前記リンクを辿りながらノードのデー
タを探索するハイパーメディアの探索方法において、以
下の処理を実行するようにしている。すなわち、前記各
ノードについてそのノードと結合する全ての宛先ノード
の探索確率の初期値を設定する初期値設定処理と、ある
ノードからある宛先ノードへ探索された時、そのノード
と結合する全ての宛先ノードの探索確率を更新する探索
時更新処理と、あるノードからある宛先ノードへのリン
クが追加された時、そのノードからの全ての宛先ノード
の探索確率を更新する追加時更新処理と、あるノードか
らある宛先ノードへのリンクが削除された時、そのノー
ドからの全ての宛先ノードの探索確率を更新する削除時
更新処理とを実行するようにしている。そして、あるノ
ードが探索された時、このノードからの宛先ノードへの
前記探索確率の大きい１つまたは複数の宛先ノードのデ
ータをあらかじめメモリ内にロードする予測ロード処理
と、あるノードからある宛先ノードへ探索した時に、そ
の宛先ノードのデータが前記予測ロード処理によってメ
モリにロードされているかどうかを判別し、ロードされ
ていればロードされたデータの提示を行い、ロードされ
ていなければその宛先ノードのデータをメモリ内にロー
ドしてその宛先ノードのデータの提示を行う提示処理を
実行するようにしている。In order to solve the above-mentioned problems, the first invention has a structure in which multimedia data is collected in units of nodes and related nodes are linked by links. In the hypermedia search method for searching the data of a node while following a link, the following processing is executed. That is, for each node, an initial value setting process for setting initial values of search probabilities of all destination nodes connected to the node, and all destinations connected to the node when a certain node is searched for An update-time update process that updates the search probability of a node, an add-time update process that updates the search probabilities of all destination nodes from a node when a link from a node is added, and a node When a link to a certain destination node is deleted from, a deletion time update process for updating the search probabilities of all the destination nodes from that node is executed. Then, when a certain node is searched for, a predictive load process of preliminarily loading the data of one or a plurality of destination nodes having a large search probability from this node to the destination node into the memory, and a certain destination node from the certain node When searching, the destination node data is judged whether or not it has been loaded into the memory by the predictive load processing, and if it is loaded, the loaded data is presented, and if it is not loaded, the destination node The data is loaded into the memory and the presentation process of presenting the data of the destination node is executed.
【０００５】第２の発明は、第１の発明の初期値設定処
理は、式（８）により探索確率を設定し、第１の発明の
探索時更新処理は、式（９）、（１０）により探索確率
を更新し、第１の発明の追加時更新処理は、式（１
１）、（１２）により探索確率を更新し、第１の発明の
削除時更新処理は、式（１３）、（１４）により探索確
率を更新するようにしている。 Ｐ1 ＝Ｐ2 ＝Ｐ3 ＝…＝Ｐn ＝１／ｎ ・・・（８） ここで、Ｐi （1=1,2,…，n)は、ノードからの宛先ノー
ドへの探索確率であり、ｎはノードからの宛先ノードの
数を表す。 Ｐk ＝αＰk ＋１−α ・・・（９） Ｐi ＝αＰi (i=1,2,…,n ただしi ≠k ) ・・・（10） ここで、Ｐk はあるノードからある宛先ノードへ探索さ
れた時の、そのノードからその宛先ノードへの探索確率
であり、Ｐk （i ≠k)はその宛先ノードを除く宛先ノー
ドへの探索確率であり、ｎはそのあるノードからの宛先
ノードの数を表す。また、αは０＜α＜１なる定数であ
り、αが小さい程、更新量は大きいという性質をもつ更
新のためのパラメータである。一般には、リンクを辿る
たびに大きく探索確率を変動させないように、αには１
に近い値を設定しておく。In the second invention, the initial value setting process of the first invention sets the search probability by the equation (8), and the update process at the time of the search of the first invention is performed by the equations (9) and (10). The search probability is updated according to
The search probability is updated by 1) and (12), and the deletion-time update process of the first invention updates the search probability by equations (13) and (14). P 1 = P 2 = P 3 = ... = P n = 1 / n (8) where P i (1 = 1,2, ..., n) is the search probability from the node to the destination node And n represents the number of destination nodes from the node. P k = αP k + 1−α (9) P i = αP i (i = 1,2, ..., n where i ≠ k) (10) where P k is from a certain node When a destination node is searched, it is the search probability from that node to that destination node, P k (i ≠ k) is the search probability to the destination nodes other than that destination node, and n is from that certain node Represents the number of destination nodes of. Further, α is a constant such that 0 <α <1, and is a parameter for updating having a property that the smaller α is, the larger the updating amount is. Generally, α is set to 1 so that the search probability does not change significantly each time a link is followed.
Set a value close to.
【０００６】 Ｐi ＝Ｐi （１−１／ｎ） (i=1,2,…,n-1) ・・・（11） Ｐn ＝１／ｎ ・・・（12） ここで、Ｐn は、あるノードにリンクが追加された宛先
ノードへの探索確率であり、Ｐi はそのノードにリンク
が追加された宛先ノード以外の宛先ノードへの探索確率
であり，ｎは追加された宛先ノードを含む宛先ノードの
数である。 Ｐk ≠１のとき Ｐi ＝Ｐi ／（１−Ｐk ） （i=1,2,…，n ただしi ≠k) ・・・（13） Ｐk ＝１のとき Ｐi ＝１／（ｎ−１） （i=1,2,…，n ただしi ≠k) ・・・（14） ここで、Ｐk は、あるノードからリンクが削除された宛
先ノードへの探索確率であり、Ｐi はそのノードからの
リンクが削除された宛先ノード以外の宛先ノードへの探
索確率であり、ｎはリンクが削除された宛先ノードを含
む宛先ノードの数である。P i = P i (1-1 / n) (i = 1,2, ..., n-1) (11) P n = 1 / n (12) Here, P i n is a search probability to a destination node to which a link is added to a certain node, P i is a search probability to a destination node other than the destination node to which a link is added to that node, and n is a added destination The number of destination nodes, including nodes. When P k ≠ 1, P i = P i / (1-P k ) (i = 1,2, ..., n where i ≠ k) (13) When P k = 1 P i = 1 / (N-1) (i = 1,2, ..., n where i ≠ k) (14) Here, P k is a search probability from a certain node to the destination node where the link is deleted, P i is a search probability from the node to a destination node other than the destination node in which the link is deleted, and n is the number of destination nodes including the destination node in which the link is deleted.
【０００７】[0007]
【作用】第１の発明によれば、以上のようにハイパーメ
ディアの探索方法を構成したので、初期値設定処理によ
り前記各ノードについてそのノードと結合する全ての宛
先ノードの探索確率の初期値を設定する。探索時更新処
理により、あるノードからある宛先ノードへ探索された
時、その探索された宛先ノードの探索確率を大きくし、
それ以外の宛先ノードの探索確率を小さくするように更
新して探索された宛先ノードがより予測探索されるよう
にする。追加時更新処理により、あるノードからある宛
先ノードへのリンクが追加された時、そのノードからの
全ての宛先ノードの探索確率を更新し、削除時更新処理
により、あるノードからある宛先ノードへのリンクが削
除された時、そのノードからの全ての宛先ノードの探索
確率を更新する。そして、あるノードが探索された時、
予測ロード処理により、そのノードからの宛先ノードへ
の探索確率の大きい１つまたは複数の宛先ノードのデー
タをあらかじめメモリ内にロードして予測探索する。判
別処理により、あるノードからある宛先ノードへ探索し
た時に、その宛先ノードのデータが前記予測ロード処理
によってメモリにロードされているかどうかを判別す
る。提示処理により、ロードされていればロードされた
データの提示を行い、ロードされていなければその宛先
ノードのデータをメモリ内にロードしてその宛先ノード
のデータの提示を行う。従って、前記課題を解決できる
のである。According to the first aspect of the present invention, since the hypermedia search method is configured as described above, the initial values of the search probabilities of all the destination nodes connected to the node are set to the initial values by the initial value setting process. Set. By the update process at the time of search, when a certain node is searched to a certain destination node, the search probability of the searched destination node is increased,
Updating is performed so as to reduce the search probabilities of the other destination nodes so that the searched destination nodes are more predictively searched. When a link from a certain node to a certain destination node is added by the add time update process, the search probabilities of all the destination nodes from that node are updated, and by the delete time update process, a certain node to a certain destination node is updated. When a link is deleted, it updates the search probabilities of all destination nodes from that node. And when a node is searched,
By the predictive load processing, data of one or a plurality of destination nodes having a high search probability from that node to the destination node is loaded in the memory in advance and a predictive search is performed. By the determination processing, when searching from a certain node to a certain destination node, it is determined whether or not the data of the destination node is loaded in the memory by the predictive loading processing. By the presentation process, the loaded data is presented if it is loaded, and if it is not loaded, the data of the destination node is loaded into the memory and the data of the destination node is presented. Therefore, the above problem can be solved.
【０００８】[0008]
【実施例】図１は、本発明の実施例を示すハイパーメデ
ィアを探索方法を実施するためのハイパーメディアシス
テムの構成図である。このハイパーメディアシステムで
は、入力部１を有している。入力部１の出力側には、ユ
ーザインタフェース管理部２が接続されている。ユーザ
インタフェース管理部２の出力側には、データ提示部３
及びハイパーメディア制御部４が接続されている。ハイ
パメディア制御部４の出力側には、ユーザインタフェー
ス管理部２及びデータベース部５が接続されている。デ
ータベース部５はノード情報管理部５−１，リンク情報
管理部５−２，メディア情報管理部５−３などによって
構成されている。入力部１は利用者がキーボードやマウ
スを使用して入力したハイパーメディアでの探索やナビ
ゲーションのためのコマンドをユーザインタフェース管
理部２へ供給するものである。ユーザインタフェース管
理部２は入力部１からのコマンドを受け付け、ノードの
内容や探索結果などのデータの表示を行なうためのデー
タをデータ提示部３へ供給するものである。データ提示
部３は利用者がナビケーションしたノードのデータを利
用者に提示処理を行うものである。1 is a block diagram of a hypermedia system for implementing a hypermedia search method according to an embodiment of the present invention. This hypermedia system has an input unit 1. The user interface management unit 2 is connected to the output side of the input unit 1. The data presentation unit 3 is provided on the output side of the user interface management unit 2.
And the hypermedia control unit 4 is connected. The user interface management unit 2 and the database unit 5 are connected to the output side of the hypermedia control unit 4. The database unit 5 is composed of a node information management unit 5-1, a link information management unit 5-2, a media information management unit 5-3 and the like. The input unit 1 supplies the user interface management unit 2 with commands for searching and navigation in hypermedia input by the user using a keyboard and a mouse. The user interface management unit 2 receives a command from the input unit 1 and supplies the data presenting unit 3 with data for displaying data such as contents of nodes and search results. The data presenting unit 3 presents the data of the node navigated by the user to the user.
【０００９】ハイパーメディア制御部４はあるノードか
ら宛先ノードへのナビゲーションの探索確率を設定し、
あるノードが探索された時，このノードからの宛先ノー
ドへの探索確率の大きい１つまたは複数の宛先ノードの
データをあらかじめメモリ内にデータベースからロード
する予測ロード処理をするものである。データベース部
５はノード情報管理部５−１，リンク情報管理部５−
２，メディア情報管理部５−３によって構成されてい
る。ノード情報管理部５−１はノードの情報を管理する
ものである。ノードの情報としては、ノード識別子、ノ
ードが保持するデータの識別子、リンクの識別子などが
ある。リンク情報管理部５−２はノード間のリンクに関
する情報を管理するものである。リンクの情報として
は、リンク識別子、リンクの始点となるノードの識別
子、リンクの終点となるノードの識別子、リンク探索確
率などである。メディア情報管理部５−３はそれぞれの
メディアに応じたデータを持ち、メディアの数だけメデ
ィア情報管理部５−３を持つ。たとえば、テキストデー
タ、グラフィクスデータ、動画像データ、静止画像デー
タ、音声データの管理部などがある。The hypermedia control unit 4 sets a search probability of navigation from a certain node to a destination node,
When a certain node is searched, a predictive load process is performed in which the data of one or a plurality of destination nodes having a high search probability from this node to the destination node is loaded in advance from the database in the memory. The database unit 5 includes a node information management unit 5-1 and a link information management unit 5-.
2. Media information management unit 5-3. The node information management unit 5-1 manages node information. The node information includes a node identifier, an identifier of data held by the node, a link identifier, and the like. The link information management unit 5-2 manages information about links between nodes. The link information includes a link identifier, an identifier of a node serving as a link start point, an identifier of a node serving as a link end point, a link search probability, and the like. The media information management unit 5-3 has data corresponding to each media, and has the media information management unit 5-3 as many as the number of media. For example, there is a management unit for text data, graphics data, moving image data, still image data, and audio data.
【００１０】図２は本発明の実施例を示すハイパーメデ
ィアの探索方法のフローチャートである。以下、これら
の図を参照しつつ本実施例のハイパーメディアの探索方
法を（１）〜（１８）に説明する。 （１） ステップＳ１の処理 図１中の入力部１は、利用者からの起動コマンドが入力
されると、ハイパーメディアシステムが起動した時点
で、ハイパーメディア制御部４へ制御が渡されてハイパ
ーメディア制御部４での処理が開始する。 （２） ステップＳ２の処理（初期値設定処理） ハイパーメディア制御部４は、ハイパーメディアネット
ワークを初期化する。このとき、ハイパーメディア制御
部４はデータベース部５のノード情報管理部５−１とリ
ンク情報管理部５−２を介してノード情報とリンク情報
を参照し、各ノードの出力リンクに探索確率が設定され
ているか調べる。もし、設定されていないなら、探索確
率の初期値を設定する。図３は一般的なハイパメディア
構造の一部分である。ノードＯからｎ個の宛先ノードＡ
1 ，Ａ2 ，Ａ3 ，…，Ａn へ出力リンクＬ1 ，Ｌ2 ，Ｌ
3 ，…，Ｌn で結合され、ｍ個のノードＢ1 ，Ｂ2 ，Ｂ
3 ，…，Ｂm からノードＯへ入力リンクｌ1 ，ｌ2 ，ｌ
3 ，…，ｌm で結合されている。このようにノードの出
力リンクの数（以下、出力次数と呼ぶ）がｎであるとき
に、ノードＯにおける宛先ノードＡi への各出力リンク
の探索確率Ｐi （i=1,…，n)は等しいとして、初期値は
１／ｎとおく。すなわち、探索確率Ｐi は式（８）のよ
うになる。この探索確率Ｐi はリンク情報管理部５−２
に格納する。FIG. 2 is a flow chart of a hypermedia search method showing an embodiment of the present invention. Hereinafter, the hypermedia search method of this embodiment will be described in (1) to (18) with reference to these drawings. (1) Process of Step S1 When the activation command from the user is input, the input unit 1 in FIG. 1 transfers control to the hypermedia control unit 4 when the hypermedia system is activated, and the hypermedia control unit 4 receives the hypermedia. The processing in the control unit 4 starts. (2) Process of Step S2 (Initial Value Setting Process) The hypermedia control unit 4 initializes the hypermedia network. At this time, the hypermedia control unit 4 refers to the node information and the link information via the node information management unit 5-1 and the link information management unit 5-2 of the database unit 5, and sets the search probability in the output link of each node. Check if it is done. If not set, set the initial value of the search probability. FIG. 3 is a part of a general hypermedia structure. N destination nodes A from node O
1, A 2, A 3, ..., output to A n link L 1, L 2, L
3 , ..., L n , and m nodes B 1 , B 2 , B
3, ..., input from the B m to node O links l 1, l 2, l
3 , ..., L m are combined. In this way, when the number of output links of the node (hereinafter, referred to as output order) is n, the search probability P i (i = 1, ..., N) of each output link to the destination node A i in the node O Are equal, the initial value is set to 1 / n. That is, the search probability P i is as shown in equation (8). The search probability P i is the link information management unit 5-2.
To be stored.
【００１１】（３） ステップＳ３の処理 ハイパーメディア制御部５は、データベース部５を参照
し、利用者が現在訪れているノード（以下、カレントノ
ードと呼ぶ）として著者がハイパーメディアへの入り口
として設定したノード（以下、ホームノードと呼ぶ）を
設定する。そして、ハイパーメディア制御部５では、カ
レントノード用のデータ提示プロセスを起動する。 （４） ステップＳ４の処理（提示処理） ハイパーメディア制御部５は、ユーザインイタフェース
部２を通してデータ提示部３のデータ提示プロセスにデ
ータの提示を行なわせる。 （５） ステップＳ５の処理（予測ロード処理） ハイパーメディア制御部５は、カレントノードの各出力
リンクの探索確率Ｐ1，Ｐ2 ，Ｐ3 ，…Ｐn を調べ、探
索確率が最大のリンクを見つける。探索確率が最大のリ
ンクが複数あれば、その中からランダムに選択する。こ
のリンクの宛先ノードのデータを予測ノードとして選択
し、この予測ノードを提示プロセスを起動する。起動さ
れた提示プロセスは、そのノードのデータをメモリ空間
へロードする。ただし、出力装置へのそのノードのデー
タの提示はまだしない。もし、メモリ空間に余裕がある
場合には、２番目に探索確率の大きいリンクの宛先ノー
ドも予測ノードとし、同様の処理を行なう。さらに、メ
モリ空間に余裕があるなら以下、メモリ空間が充溢する
まで同様の処理を繰り返す。(3) Processing of step S3 The hypermedia control unit 5 refers to the database unit 5 and sets the author as a node currently visited by the user (hereinafter referred to as the current node) as an entrance to the hypermedia. The node (hereinafter referred to as the home node) that has been set is set. Then, the hypermedia control unit 5 activates the data presentation process for the current node. (4) Process of Step S4 (Presentation Process) The hypermedia control unit 5 causes the data presentation process of the data presentation unit 3 to present data through the user interface unit 2. (5) Process of Step S5 (Predictive Load Process) The hypermedia control unit 5 checks the search probabilities P 1 , P 2 , P 3 , ... P n of each output link of the current node, and finds the link with the maximum search probability. locate. If there are multiple links with the highest search probability, they are randomly selected from them. The data of the destination node of this link is selected as the prediction node and this prediction node triggers the presentation process. The activated presentation process loads the data of that node into the memory space. However, it does not yet present the data of the node to the output device. If the memory space is large, the destination node of the link having the second highest search probability is also set as the prediction node and the same process is performed. Further, if the memory space has a margin, the same processing is repeated until the memory space is full.
【００１２】（６） ステップＳ６の処理 ハイパメディア制御部５は、ユーザインタフェース制御
部２を通して利用者からの入力を受け付ける。そして、
利用者からの入力がリンクの探索であれば、ステップＳ
１０の処理へ進み、リンクの追加であれば、ステップＳ
２０の処理へ進み、リンクの削除であれば、ステップＳ
３０へ進み、終了であればステップＳ４０へ進む。 （７） ステップＳ１０の処理（探索時更新処理） 入力コマンドがリンクの探索であれば、ハイパーメディ
ア制御部４では、以下に述べる方法でカレントノードの
出力リンクの探索確率を更新する。利用者がある時点で
ノードＯからノードＡk へのリンクを辿ったとする。こ
の時、ハイパーメディア制御部４は、式（９），（１
０）のように探索確率を更新する。また、式（９），
（１０）より、更新前と更新後の探索確率の和はいずれ
も１となるように設定される。 （８） ステップＳ１１の処理 ハイパーメディア制御部４は、データベース部５を参照
して、利用者の要求したリンクの宛先ノードをカレント
ノードとする。(6) Process of Step S6 The hypermedia control unit 5 receives an input from the user through the user interface control unit 2. And
If the input from the user is a link search, step S
If the link is added, the process proceeds to step S10.
If the link is deleted, the process proceeds to step 20 and step S
30, the process proceeds to step S40 if completed. (7) Process of Step S10 (Update Process at Search) If the input command is a link search, the hypermedia control unit 4 updates the search probability of the output link of the current node by the method described below. It is assumed that the user has followed the link from the node O to the node A k at some point. At this time, the hypermedia control unit 4 uses the expressions (9), (1
The search probability is updated as in 0). Also, equation (9),
From (10), the sum of the search probabilities before and after the update is set to 1. (8) Process of Step S11 The hypermedia control unit 4 refers to the database unit 5 and sets the destination node of the link requested by the user as the current node.
【００１３】（９） ステップＳ１２の処理（判別処
理） ハイパーメディア制御部４は、カレントノードに対応す
る提示プロセスが予測ロード処理によって既に起動され
ているかどうかを調べる。 （１０） ステップＳ１３の処理 カレントノードに対応する提示プロセスが起動していな
いなら起動する。 （１１） ステップＳ１４の処理 カレントノードに対応する提示プロセス以外のプロセス
を強制終了し、ステップＳ４に戻る。 （１２） ステップＳ２０の処理 入力コマンドがリンクの追加であれば、利用者の要求に
従いリンクを追加し、データベース部５を書き換える。 （１３） ステップＳ２１の処理（追加時更新処理） ハイパーメディア制御部４は、以下に述べる方法でカレ
ントノードの出力シンクの探索確率を更新し、ステップ
Ｓ５へ戻る。ノードＯには出力リンクＬ1 ，Ｌ2 ，
Ｌ3 ，…，Ｌn-1 が結合されており、対応する探索確率
がＰ1 ，Ｐ2 ，…，Ｐn-1 で与えられているとする。こ
の時、利用者がハイパーメディアの中で新規にノードＯ
からノードＯ´へのリンクＬn を追加したとする。この
結果、各リンクに対応する探索確率を式（１１），（１
２）のように更新する。(9) Process of Step S12 (discrimination process) The hypermedia control unit 4 checks whether the presentation process corresponding to the current node has already been activated by the predictive loading process. (10) Process of Step S13 If the presentation process corresponding to the current node is not activated, it is activated. (11) Process of step S14 Processes other than the presentation process corresponding to the current node are forcibly terminated, and the process returns to step S4. (12) Processing of Step S20 If the input command is the addition of a link, the link is added according to the user's request, and the database unit 5 is rewritten. (13) Process of step S21 (update process at the time of addition) The hypermedia control unit 4 updates the search probability of the output sink of the current node by the method described below, and returns to step S5. Output links L 1 , L 2 ,
It is assumed that L 3 , ..., L n-1 are combined and the corresponding search probabilities are given by P 1 , P 2 , ..., P n-1 . At this time, the user newly creates a node O in the hypermedia.
It is assumed that a link L n from the node to the node O ′ has been added. As a result, the search probabilities corresponding to the respective links are calculated by the equations (11) and (1
Update as in 2).
【００１４】（１４） ステップＳ３０の処理 入力コマンドがリンクの削除であれば、利用者の要求に
従いリンクを削除し、データベース部５を書き換える。 （１５） ステップＳ３１の処理（削除時更新処理） ハイパーメディア制御部４は、以下に述べる方法でカレ
ントノードの出力リンクの探索確率を更新する。ノード
Ｏには出力リンクＬ1 ，Ｌ2 ，Ｌ3 ，…，Ｌn が結合さ
れており、対応する探索確率がＰ1 ，Ｐ2 ，…，Ｐn で
与えられているとする。この時、利用者がハイパーメデ
ィアの中でノードＯからノードＯ´へのリンクＬk を削
除したとする。この結果、各リンクに対応する探索確率
を式（１３），（１４）のように更新する。 （１６） ステップＳ３２の処理 ハイパメディア制御部４では削除したリンクの宛先ノー
ドの提示プロセスが既に起動されているかどうかを調べ
る。起動されていなければ、ステップＳ６へ戻る。(14) Processing in step S30 If the input command is to delete the link, the link is deleted and the database unit 5 is rewritten according to the user's request. (15) Process of Step S31 (update process at the time of deletion) The hypermedia control unit 4 updates the search probability of the output link of the current node by the method described below. Node in O output link L 1, L 2, L 3 , ..., L n are coupled, P 1, P 2 corresponding search probability, ..., and are given by P n. At this time, it is assumed that the user deletes the link L k from the node O to the node O ′ in the hypermedia. As a result, the search probabilities corresponding to the links are updated as shown in equations (13) and (14). (16) Processing of Step S32 The hypermedia control unit 4 checks whether or not the presentation process of the destination node of the deleted link has already been started. If it has not been activated, the process returns to step S6.
【００１５】（１７） ステップＳ３３の処理 もし起動されていれば、その提示プロセスを強制終了
し、ステップＳ５へ戻る。 （１８） ステップＳ４０の処理 入力コマンドが終了であれば、終了処理を行う。以上の
ように、本実施例では、ハイパーメディア利用者がリン
クを辿った時に、すでに提示プロセスが起動されていれ
ば、ローディング時間が短縮でき、提示処理だけで済む
ので利用者の目からは円滑に目的のノードへ移行できた
ように見えるという利点がある。通常、利用者は１つの
ノードに到着すればしばらくはそのノードに滞在してい
るので、その間を利用してシステムが別の処理を行うの
は、利用者には害にはならない。また、起動をかける提
示プロセスは過去の探索に基づき確率を推定して選択し
ているので、ランダムに選択するよりも予測の的中率が
高いという利点がある。(17) Processing of Step S33 If it has been activated, the presentation process is forcibly terminated and the process returns to Step S5. (18) Process of Step S40 If the input command is completed, the ending process is performed. As described above, in the present embodiment, if the presentation process is already activated when the hypermedia user follows the link, the loading time can be shortened and only the presentation process is required, which is smooth from the user's eyes. Has the advantage of appearing to have migrated to the desired node. Normally, when a user arrives at one node, he or she stays at that node for a while, so that it is not harmful to the user that the system performs another processing while using that interval. In addition, since the presentation process for invoking is selected by estimating the probability based on the past search, there is an advantage that the prediction hit rate is higher than that of selecting randomly.
【００１６】[0016]
【発明の効果】以上詳細に説明したように、第１〜第２
の発明によれば、ノードと結合する全ての宛先ノードへ
の探索確率を求め、あるノードが探索された時、このノ
ードからの宛先ノードへの前記探索確率の大きい１つま
たは複数の宛先ノードのデータをあらかじめメモリ内に
ロードする予測ロード処理を実行し、あるノードからあ
る宛先ノードへ探索した時に、その宛先ノードのデータ
が前記予測ロード処理によってメモリにロードされてい
るかどうかを判別し、ロードされていればロードされた
データの提示を行い、ロードされていなければその宛先
ノードのデータをメモリ内にロードしてその宛先ノード
のデータの提示を行う提示処理するようにした。よっ
て、ローディング時間が短縮できて円滑にナビゲーショ
ンできる。As described in detail above, the first to second
According to the invention, the search probabilities to all the destination nodes connected to the node are obtained, and when a certain node is searched, one or more destination nodes having a large search probability from this node to the destination node are searched. Predictive load processing that loads data into memory in advance is executed, and when searching from a certain node to a certain destination node, it is determined whether the data of the destination node has been loaded into the memory by the predictive load processing, and the data is loaded. If so, the loaded data is presented, and if it is not loaded, the data of the destination node is loaded in the memory and the data of the destination node is presented. Therefore, loading time can be shortened and smooth navigation can be performed.
【図１】本発明の実施例を示すハイパーメディアの探索
方法を実施するためのハイパーメディアシステムの構成
図である。FIG. 1 is a configuration diagram of a hypermedia system for implementing a hypermedia search method according to an embodiment of the present invention.
【図２】本発明の実施例を示すハイパーメディアの探索
方法のフローチャートである。FIG. 2 is a flowchart of a hypermedia search method according to an embodiment of the present invention.
【図３】一般的なハイパーメディアの部分構造を示す図
である。FIG. 3 is a diagram showing a partial structure of a general hypermedia.
１ 入力部 ２ ユーザインタフェース制御部 ３ データ提示部 ４ ハイパーメディア制御部 ５ データベース部 1 input unit 2 user interface control unit 3 data presentation unit 4 hypermedia control unit 5 database unit
Claims (2)
でまとめられ関連あるノード同士がリンクで結合された
構造を有し、前記リンクを辿りながらノードのデータを
探索するハイパーメディアの探索方法において、 前記各ノードについてそのノードと結合する全ての宛先
ノードの探索確率の初期値を設定する初期値設定処理
と、 あるノードからある宛先ノードへ探索された時、そのノ
ードと結合する全ての宛先ノードの探索確率を更新する
探索時更新処理と、 あるノードからある宛先ノードへのリンクが追加された
時、そのノードからの全ての宛先ノードの探索確率を更
新する追加時更新処理と、 あるノードからある宛先ノードへのリンクが削除された
時、そのノードからの全ての宛先ノードの探索確率を更
新する削除時更新処理と、 あるノードが探索された時、このノードからの宛先ノー
ドへの前記探索確率の大きい１つまたは複数の宛先ノー
ドのデータをあらかじめメモリ内にロードする予測ロー
ド処理と、 あるノードからある宛先ノードへ探索した時に、その宛
先ノードのデータが前記予測ロード処理によってメモリ
にロードされているかどうかを判別する判別処理と、 予測ロード処理によりロードされていればロードされた
データの提示を行い、ロードされていなければその宛先
ノードのデータをメモリ内にロードしてその宛先ノード
のデータの提示を行う提示処理とを、 実行することを特徴とするハイパーディアの探索方法。1. A hypermedia search method for searching multimedia data, which has a structure in which multimedia data is collected in units of nodes and related nodes are linked by links, and the data of the nodes are searched while following the links, For each node, an initial value setting process that sets the initial value of the search probability of all destination nodes connected to that node, and when searching from a certain node to a certain destination node, the search for all the destination nodes connected to that node Search-time update process that updates the probability, add-time update process that updates the search probability of all destination nodes from a node when a link from a node to a destination node is added, and a destination from a node When a link to a node is deleted, update processing at the time of deletion that updates the search probabilities of all destination nodes from that node, When a node is searched, a predictive load process of preliminarily loading the data of one or a plurality of destination nodes having a high search probability from this node to the destination node into the memory, and searching from a certain node to a certain destination node Occasionally, a determination process is performed to determine whether or not the data of the destination node has been loaded into the memory by the predictive load process, and if the data has been loaded by the predictive load process, the loaded data is presented. A method for searching for hyperdia, characterized by: performing a presentation process of loading the data of the destination node into a memory and presenting the data of the destination node.
探索確率を設定し、 前記探索時更新処理は、式（２）、（３）により探索確
率を更新し、 前記追加時更新処理は、式（４）、（５）により探索確
率を更新し、 前記削除時更新処理は、式（６）、（７）により探索確
率を更新する、 ようにしたことを特徴とする請求項１記載のハイパーメ
ディアの探索方法。 Ｐ1 ＝Ｐ2 ＝Ｐ3 ＝…＝Ｐn ＝１／ｎ ・・・（１） ここで、Ｐi （1=1,2,…，n)は、ノードからの宛先ノー
ドへの探索確率であり、ｎはノードからの宛先ノードの
数を表す。 Ｐk ＝αＰk ＋１−α ・・・（２） Ｐi ＝αＰi (i=1,2,…,n ただしi ≠k ) ・・・（３） ここで、Ｐk はあるノードからある宛先ノードへ探索さ
れた時の、そのノードからその宛先のノードへの探索確
率であり、Ｐk （i ≠k)はその宛先ノードを除く宛先ノ
ードへの探索確率であり、ｎはそのあるノードからの宛
先ノードの数を表し、αは０＜α＜１なる定数である。 Ｐi ＝Ｐi （１−１／ｎ） (i=1,2,…,n-1) ・・・（４） Ｐn ＝１／ｎ ・・・（５） ここで、Ｐn は、あるノードにリンクが追加された宛先
ノードへの探索確率であり、Ｐi はそのノードにリンク
が追加された宛先ノード以外の宛先ノードへの探索確率
であり，ｎは追加された宛先ノードを含む宛先ノードの
数である。 Ｐk ≠１のとき Ｐi ＝Ｐi ／（１−Ｐk ） （i=1,2,…，n ただしi ≠k) ・・・（６） Ｐk ＝１のとき Ｐi ＝１／（ｎ−１） （i=1,2,…，n ただしi ≠k) ・・・（７） ここで、Ｐk は、あるノードからリンクが削除された宛
先ノードへの探索確率であり、Ｐi はそのノードからの
リンクが削除された宛先ノード以外の宛先ノードへの探
索確率であり、ｎはリンクが削除された宛先ノードを含
む宛先ノードの数である。2. The initial value setting process sets a search probability according to equation (1), the search time update process updates the search probability according to formulas (2) and (3), and the addition time update process is performed. Is updated by equations (4) and (5), and the update processing at the time of deletion is updated by equations (6) and (7). The hypermedia search method described. P 1 = P 2 = P 3 = ... = P n = 1 / n (1) where P i (1 = 1,2, ..., n) is the search probability from the node to the destination node And n represents the number of destination nodes from the node. P k = αP k + 1−α (2) P i = αP i (i = 1,2, ..., n where i ≠ k) (3) where P k is from a certain node When a destination node is searched, it is a search probability from that node to the destination node, P k (i ≠ k) is a search probability to a destination node excluding the destination node, and n is the certain node Represents the number of destination nodes, and α is a constant 0 <α <1. P i = P i (1-1 / n) (i = 1,2, ..., n-1) (4) P n = 1 / n (5) Here, P n is A search probability to a destination node to which a link is added to a certain node, P i is a search probability to a destination node other than the destination node to which a link is added to that node, and n includes the added destination node The number of destination nodes. When P k ≠ 1, P i = P i / (1-P k ) (i = 1,2, ..., n where i ≠ k) (6) When P k = 1 P i = 1 / (N-1) (i = 1,2, ..., n where i ≠ k) (7) Here, P k is a search probability from a certain node to the destination node where the link is deleted, P i is a search probability from the node to a destination node other than the destination node in which the link is deleted, and n is the number of destination nodes including the destination node in which the link is deleted.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP20654894A JP3692154B2 (en) | 1994-08-31 | 1994-08-31 | How to search hypermedia |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP20654894A JP3692154B2 (en) | 1994-08-31 | 1994-08-31 | How to search hypermedia |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0877057A true JPH0877057A (en) | 1996-03-22 |
| JP3692154B2 JP3692154B2 (en) | 2005-09-07 |
Family
ID=16525214
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP20654894A Expired - Fee Related JP3692154B2 (en) | 1994-08-31 | 1994-08-31 | How to search hypermedia |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3692154B2 (en) |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH03149634A (en) * | 1989-11-07 | 1991-06-26 | Toshiba Corp | Hypertext system |
| JPH06110926A (en) * | 1992-09-29 | 1994-04-22 | Oki Electric Ind Co Ltd | Information retrieving device |
-
1994
- 1994-08-31 JP JP20654894A patent/JP3692154B2/en not_active Expired - Fee Related
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH03149634A (en) * | 1989-11-07 | 1991-06-26 | Toshiba Corp | Hypertext system |
| JPH06110926A (en) * | 1992-09-29 | 1994-04-22 | Oki Electric Ind Co Ltd | Information retrieving device |
Also Published As
| Publication number | Publication date |
|---|---|
| JP3692154B2 (en) | 2005-09-07 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JP3315781B2 (en) | User information management device, information filter, information classification device, information reproduction device, information search device, and kana-kanji conversion device | |
| JP2010102593A (en) | Information processing device and method, program, and storage medium | |
| JPH11316780A (en) | Workflow system with hierarchical business process definition | |
| JP2001159993A (en) | Data storage method and device capable of referring to state at arbitrary time | |
| JP2002342142A (en) | Writing control method, structured document management device, structured document editing device, and program | |
| JP2004145706A (en) | Multimedia data retrieval system | |
| JPH0877057A (en) | Searching method for hypermedia | |
| JP2624170B2 (en) | Logical deletion data physical deletion method | |
| JP2925042B2 (en) | Information link generation method | |
| JP2003331043A (en) | Service providing system, service providing method, and software program | |
| JP2812357B2 (en) | Database search system | |
| JP2000222436A (en) | Information search support method and information search support device using ontology, and recording medium storing information search support program | |
| JPH07271569A (en) | Program specification preparation system | |
| JPH10222334A (en) | Screen control device and recording medium | |
| JP2001282811A (en) | Knowledge data search device, knowledge data search method, and computer-readable recording medium storing program for searching knowledge data | |
| JPH09305611A (en) | Database search device | |
| CN111897617B (en) | Picture loading method and device, computer equipment and storage medium | |
| JP2007025831A (en) | Content search apparatus and method | |
| JP3457502B2 (en) | Transfer file selection device and computer-readable recording medium recording transfer file selection program | |
| JP2913933B2 (en) | Database selection processor | |
| JPH07334406A (en) | Multimedia database system | |
| JP3305782B2 (en) | Software standardization method and software product analysis method | |
| JP2000207402A (en) | Information retrieval system, information retrieving method and program recording medium for information retrieval | |
| JP2001034515A (en) | Document management method and storage medium storing the document management method | |
| JPH08314949A (en) | Data management device |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20040727 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20040921 |
|
| TRDD | Decision of grant or rejection written | ||
| A01 | Written decision to grant a patent or to grant a registration (utility model) |
Free format text: JAPANESE INTERMEDIATE CODE: A01 Effective date: 20050614 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20050620 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090624 Year of fee payment: 4 |
|
| LAPS | Cancellation because of no payment of annual fees |