JP3692154B2 - How to search hypermedia - Google Patents

Description

[0001]
[Industrial application fields]
The present invention relates to a hypermedia search method.
[0002]
[Prior art]
Conventionally, as a technique in such a field, for example, there are those described in the following documents.
Literature: IEEE COMPUTER, 1988-1, (US), N. Yankelovic h, BJHaan, NK Meyrowitz, and SMDrucker, "Intermedia: The Concept and the Construction of a Seamless Information Environment", P81-96
Hypermedia has a structure in which multimedia data is grouped in units called nodes, and related nodes are connected by links, and users mainly follow links (hereinafter referred to as navigation). ) To search for data. As an internal process of navigation, as represented by the above document, when a 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 in which contents are presented to a user is common.
In this case, you may start the presentation process which specializes in the system presentation process which shows a content to a user. The data storage destination may be a database instead of a normal 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 data as the contents of the destination node from a file or database onto a memory and presents the data to an output device.
Note that data held by a node is generally multimedia data including not only text but also images, sounds, graphics, and the like.
[0003]
[Problems to be solved by the invention]
However, the conventional hypermedia search method has the following problems.
When navigating hypermedia, it takes time to load data from a database into memory. Therefore, each time the user tries to move to another node by following the link, a waiting time is generated, which makes the system difficult for the user to use. This problem is particularly acute in systems that require real-time performance.
[0004]
[Means for Solving the Problems]
The present invention, in order to solve the above problems, relevant nodes between the data of the multimedia are combined in units of node has a bonded structure by a link, to explore the data of the node by following the link In the hypermedia search method, the following processing is executed.
That is, for each of the nodes, search probabilities with respect to all destination nodes coupled with the node (in the present invention, for example, when hypermedia is inked from node A to nodes B, C, and D, node A is viewed. to the user that is, the probability that the next searching for a node B, a initial value setting processing for setting the equation (8) the initial value of the search probability and called.) from the node a to a node B, there said node when the has been searched to the destination node from the search probabilities of all of the destination nodes that binds to the node equation (9), the destination node from the search time of the update process, there is the node to be updated (10) when a link to has been added, the search probabilities of all of the destination node from the node equation (11), the additional time update process for updating the (12), there the nO When the link to the destination node from is deleted, the search probabilities of all of the destination node from the node equation (13), executes a deletion time update process for updating the (14).
Further, when there the node is searched, and the predicted load process to said load data in advance in the memory of one or more of the destination node large search probability to the destination node from the node, is the node wherein when searching the destination node, the discrimination process and the data loaded if it is loaded by the prediction load process to determine if the data of the destination node is loaded into the memory by the predicted load operation from perform presentation, performing a presentation process if it is not loaded to load the data of the destination node in the memory performs presentation of the data of the destination node.
[0005]
The formulas (8) to (14) are as follows.
P ₁ = P ₂ = P ₃ = ... = P _n = 1 / n (8)
Here, P _i (1 = 1, 2,..., N) is a 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)
Here, P _k is a search probability from the node to the destination node when searching from the node to the destination node, and P _k (i ≠ k) is a search to the destination node excluding the destination node. A probability, where n represents the number of destination nodes from that node. Further, α is a constant of 0 <α <1, and is a parameter for updating having a property that the amount of updating is larger as α is smaller. In general, α is set to a value close to 1 so that the search probability does not fluctuate greatly every time the link is followed.
[0006]
P _i = P _i (1-1 / n) (i = 1, 2,..., N−1) (11)
P _n = 1 / n (12)
Here, P _n is the search probability to the destination node a link to a node is added, P _i is the search probability to the destination node other than the destination node linked to that node has been added, n represents The number of destination nodes including the added destination node.
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 to a destination node from which a link is deleted from a certain node, P _i is a search probability to a destination node other than the destination node from which the link from that node is deleted, and n Is the number of destination nodes including the destination node from which the link has been deleted.
[0007]
[Action]
According to the present invention, since the hypermedia search method is configured as described above, initial values of search probabilities of all destination nodes that are combined with the node are set for each node by the initial value setting process. When a search is performed from a certain node to a certain destination node by the search update process, the search is performed so that the search probability of the searched destination node is increased and the search probability of other destination nodes is decreased. The destination node is searched more predictably. When a link from a certain node to a certain destination node is added by the update process at the time of addition, search probabilities of all the destination nodes from that node are updated, and from a certain node to a certain destination node by the update process at the time of deletion When a link is deleted, the search probabilities of all destination nodes from that node are updated.
Then, when a certain node is searched, the prediction load process performs a prediction search by loading data of one or a plurality of destination nodes having a high search probability from the node to the destination node in advance in the memory. When searching from a certain node to a certain destination node by the determination process, it is determined whether or not the data of the destination node is loaded into the memory by the predictive load process. If it is loaded, the loaded data is presented by the presenting process, and if not loaded, the data of the destination node is loaded into the memory and the data of the destination node is presented. Therefore, the problem can be solved.
[0008]
【Example】
FIG. 1 is a configuration 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. A user interface management unit 2 is connected to the output side of the input unit 1. A data presentation unit 3 and a hypermedia control unit 4 are connected to the output side of the user interface management unit 2. A user interface management unit 2 and a database unit 5 are connected to the output side of the hypermedia control unit 4. The database unit 5 includes 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 navigating through hypermedia input by a user using a keyboard and mouse. The user interface management unit 2 receives commands from the input unit 1 and supplies data for displaying data such as node contents and search results to the data presentation unit 3. The data presentation unit 3 performs processing for presenting data of nodes navigated by the user to the user.
[0009]
Set search probability navigation from hypermedia control unit 4 one node to the destination node, when a node is searched, the one or more destination nodes large search probability to this node or al destination node Predictive load processing is performed in which data is loaded from a database into memory in advance.
In the database unit 5 , 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 related to links between nodes. The link information includes a link identifier, an identifier of a node that is a start point of the link, an identifier of a node that is an end point of the link, a link search probability, and the like. The media information management unit 5-3 has data corresponding to each medium, and has as many media information management units 5-3 as the number of media. For example, there is a management unit for text data, graphics data, moving image data, still image data, audio data, and the like.
[0010]
FIG. 2 is a flowchart of a hypermedia search method showing an embodiment of the present invention.
Hereinafter, the hypermedia search method of the present embodiment will be described in (1) to (18) with reference to these drawings.
(1) Processing in Step S1 When the activation command from the user is input, the input unit 1 in FIG. 1 passes control to the hypermedia control unit 4 when the hypermedia system is activated, and the hypermedia. Processing in the control unit 4 starts.
(2) Processing in step S2 (initial value setting processing)
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 to the output link of each node. Find out what has been done. If not set, the initial value of the search probability is set.
FIG. 3 is a part of a general hypermedia structure. Node n-number of the destination node from _{O A 1, A 2, A} 3, ..., output to the A _n links _{L 1, L 2, L 3} , ..., are coupled with L _n, m-number of Node B _1, B ₂ , B _3, ..., input from the B _m to node O links _{l 1, l 2, l 3} , ..., it is coupled with l _m.
Thus, when the number of output links of a 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, and the initial value is 1 / n. That is, the search probability P _i is as shown in Equation (8).
This search probability P _i is stored in the link information management unit 5-2.
[0011]
(3) Processing in Step S3 The hypermedia control unit 4 refers to the database unit 5, and refers to a node that the author has set as an entrance to hypermedia as a node that the user is currently visiting (hereinafter referred to as the current node). (Hereinafter referred to as home node). Then, the hypermedia control unit 4 starts a data presentation process for the current node.
(4) Step S4 processing (presentation processing)
The hypermedia control unit 4 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 4 examines the search probabilities P ₁ , P ₂ , P ₃ ,... , P _n of each output link of the current node, and finds the link having the maximum search probability. If there are a plurality of links having the maximum search probability, a link is selected at random. The data of the destination node of this link is selected as a prediction node , and the process of presenting this prediction node is activated. The activated presentation process loads the node data into the memory space. However, the node's data is not yet presented to the output device. If there is a margin in the memory space, the destination node of the link with the second highest search probability is set as the prediction node, and the same processing is performed. Further, if there is room in the memory space, the same processing is repeated until the memory space is full.
[0012]
(6) Processing in Step S6 The hypermedia control unit 4 receives input from the user through the user interface control unit 2. If the input from the user is a link search, the process proceeds to step S10. If a link is added, the process proceeds to step S20. If the link is deleted, the process proceeds to step S30. If there is, the process proceeds to step S40.
(7) Step S10 processing (search update processing)
If the input command is a link search, the hypermedia control unit 4 updates the output link search probability of the current node by the method described below.
And followed a link from node O to node A _k at some point the user. At this time, the hypermedia control unit 4 updates the search probability as shown in equations (9) and (10). Further, from the formulas (9) and (10), the sum of the search probabilities before and after the update is set to be 1.
(8) Processing in 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.
[0013]
(9) Step S12 processing (discrimination processing)
The hypermedia control unit 4 checks whether the presentation process corresponding to the current node has already been activated by the predictive load process.
(10) Processing in Step S13 If the presentation process corresponding to the current node is not activated, activate it.
(11) Processing in 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 in Step S20 If the input command is to add a link, the link is added according to the user's request, and the database unit 5 is rewritten.
(13) Processing in step S21 (additional update processing)
The hypermedia control unit 4 updates the search probability of the output link of the current node by the method described below, and returns to step S5.
Node in O output link _{L 1, L 2, L 3} , ..., L n-1 is coupled, P _1, P ₂ corresponding search probability, ..., when given in P _n-1 To do. At this time, it is assumed that the user newly adds a link L _n from the node O to the node O ′ in the hypermedia. As a result, the search probability corresponding to each link is updated as shown in equations (11) and (12).
[0014]
(14) Processing in Step S30 If the input command is to delete a link, the link is deleted according to the user's request, and the database unit 5 is rewritten.
(15) Processing in step S31 (deletion update processing)
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 ₂ 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 probability corresponding to each link is updated as shown in equations (13) and (14).
(16) Processing in 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 activated. If not started, the process returns to step S6.
[0015]
(17) If the process of step S33 is activated, the presenting process is forcibly terminated and the process returns to step S5.
(18) If the process input command in step S40 is completed, an end process is performed.
As described above, in this embodiment, when the presentation process is already started when the hypermedia user follows the link, the loading time can be shortened, and only the presentation process is required. There is an advantage that it seems that it has moved to the target node. Normally, if a user arrives at one node, he / she stays at that node for a while. Therefore, it is not harmful to the user to perform another process using the system. In addition, since the presentation process to be activated is selected by estimating the probability based on the past search, there is an advantage that the predictive hit rate is higher than the random selection.
[0016]
【The invention's effect】
As described above in detail, according to the present invention, search probabilities for all destination nodes combined with a node are obtained, and when a certain node is searched, the search probabilities from this node to the destination node are large. When a predictive load process for preloading data of one or a plurality of destination nodes into a memory is executed and a search is made from a node to a destination node, the data of the destination node is loaded into the memory by the predictive load process. whether determined, performs presentation of data loaded if it is loaded, to the presentation processing to load the data of the destination node in the memory if it is not loaded performs presentation of the data of the destination node are . Thereby, the loading time can be shortened and navigation can be smoothly performed.
[Brief description of the drawings]
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.
[Explanation of symbols]
1 Input unit 2 User interface management unit 3 Data presentation unit 4 Hypermedia control unit 5 Database unit

Claims (1)

Has a relevant node between data gathered in units of a node of the multimedia is coupled by a link structure, in the search method of hypermedia to explore the data of the node by following the link,
An initial value setting process for setting, for each node , an initial value of a search probability, which is a probability of being a search target, for all destination nodes coupled to that node;
When searched to the destination node from some the node, the search probabilities of all of the destination nodes that binds to the node equation (2), a search during an update process for updating the (3),
When the link to the destination node with from one said node has been added, the search probabilities of all of the destination node from the node equation (4), the additional time updating process of updating (5),
When the link to the destination node from there the node is removed, the search probabilities of all of the destination node from the node equation (6), and remove when updating process for updating the (7),
When there the node is searched, and the predicted load process to said load data in advance in the memory of one or more of the destination node large search probability to the destination node from the node,
When searched to the destination node from some said node, a determination process of determining whether the data of the destination node is loaded into the memory by the predicted load process,
Wherein performs presentation of data loaded if it is loaded by the prediction loading process, and a presentation processing if it is not loaded to load the data of the destination node in the memory performs presentation of the data of the destination node ,
Method of searching for the hyper media, characterized in that to perform.
P ₁ = P ₂ = P ₃ = ... = P _n = 1 / n (1)
Here, P _i ( 1 = 1, 2, ..., N) is a 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)
Here, P _k is a search probability from a node to the destination node when searching from a node to a destination node, and P _k ( i ≠ k) is a destination node other than the destination node. It is a search probability, n represents the number of destination nodes from the certain node, and α is a constant of 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 for a destination node in which a link is added to a certain node, P _i is a search probability for a destination node other than the destination node in which a link is added to that node, and n is The number of destination nodes including the added destination node.
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 to a destination node from which a link is deleted from a certain node, P _i is a search probability to a destination node other than the destination node from which the link from that node is deleted, and n Is the number of destination nodes including the destination node from which the link has been deleted.

Images