JP5252555B2 - Context search method and apparatus - Google Patents

Description

  The present invention relates to a context search method and apparatus, and more particularly, to provide a context search method and apparatus capable of finding a sufficient number of peer nodes satisfying a context search condition even when the number of peer nodes participating in a peer-to-peer network is small. It is in.

  When searching for a peer node having a desired context on a peer-to-peer network, the search source peer node broadcasts a search request message describing the context search condition with restrictions such as the maximum allowable hop count, and the context search condition is set. Non-Patent Document 1 discloses a technology in which a satisfied search destination peer node returns a search response message in which a search result is described to a search source peer node in response to the search request message.

The context information is one of search parameters used for the content receiver to narrow down the content desired to be distributed and the content sender to narrow down the distribution destination of the content. The context item and its context value are Including. The context items are, for example, the content type desired by the content receiver, the installation location of the reception node, the desired reception time of the content, the communication means to be used, the sex, the age, the hobby preference, the occupation, family information, and the like. The context value is a specific value of the context item. For example, when the content type desired to be received is used as the context item, content such as “sports”, “travel”, and “music” is stored. It is a value or code indicating the type.
Y. Chawathe, S. Ratnasamy, L. Breslau, and S. Shenker, “Making Gnutella-like P2P Systems Scalable”, ACM SIGCOMM 2003.

The prior art described above has the following technical problems.
(1) In a peer-to-peer network configured with a mobile terminal as a peer note, each peer node participates in the network less frequently, and as a result, the search responsiveness of each peer node is low, so a sufficient number having a desired context Unable to find peer node.
(2) When there are few peer nodes that satisfy the search conditions, such as when performing a context search with complex search conditions, the maximum allowable number of hops in the search request message is set large in order to search for a sufficient number of peer nodes. This increases the amount of communication for context search. On the other hand, if the amount of communication is reduced, a sufficient number of peer nodes having a desired context cannot be found.

  The object of the present invention is to solve the above-mentioned problems of the prior art, and even when the number of peer nodes participating in the peer-to-peer network is small or when searching with complicated context search conditions, the context search is performed without increasing the traffic. It is an object of the present invention to provide a context search method and apparatus capable of finding a sufficient number of peer nodes satisfying a condition.

  In order to achieve the above object, according to the present invention, a search source peer node transmits a search request including a context search condition to a search destination peer node, and each search destination peer node records a search solution that satisfies the context search condition. The context search device that returns the search response to the search source peer node is characterized in that the following measures are taken.

  (1) The search source peer node has a context table in which context information unique to the local node is stored, a search history table in which a history of search solutions is stored for each context search condition, and a search request in which the context search condition is described , A means for receiving a search response returned from the search destination peer node, a means for extracting a search solution and a search solution candidate from the search response, and a search solution from the search solution candidate based on the search history table It is characterized by comprising means for specifying and means for registering a context search condition and a search solution in association with a search history table.

  (2) The search-destination peer node receives a search request from the search source peer node and the context table storing the context information unique to the node, the search history table storing the search solution history for each context search condition Means for extracting a context search condition from the search request, means for extracting a search solution satisfying the context search condition based on the context table and the search history table, and a search solution satisfying a part of the context search condition Characterized in that it comprises means for extracting candidates based on a search history table, means for generating a search solution in which the search solution and search solution candidates are described, and means for returning the search response to the search source peer node. To do.

According to the present invention, the following effects are achieved.
(1) A sufficient number of peer nodes having a desired context can be found even when the frequency with which each peer node participates in the network is low, as in a peer-to-peer network composed of mobile terminals.
(2) A sufficient number of peer nodes can be found with a small amount of communication even when the number of peer nodes having a desired context is scarce as in the case of searching with complicated context search conditions.

  Hereinafter, the best embodiment of the present invention will be described in detail with reference to the drawings. FIG. 1 is a diagram schematically showing the configuration of a peer-to-peer network to which the context search method and apparatus of the present invention is applied. A plurality of peer nodes Xi are connected to each other by a peer-to-peer network.

  Here, a case will be described as an example where peer node X0 is a search source peer node and peer nodes X1, X2, X3... Are search destination peer nodes. The search source peer node X0 stores a context table 1 in which context information (context items and context values thereof) unique to the user managing the peer node is stored, and a past search solution is stored for each searched context search condition as a search history. And a search source function unit 3 including various configurations for the peer node to operate as a search source peer node. The search destination peer nodes X1, X2, X3... Include a search destination function unit 4 including various configurations for the peer node to operate as a search destination peer node, together with the context table 1 and the search history table 2.

  In order to simplify the explanation here, each peer node is described as acting as either a search source peer node or a search destination peer node, but the search source peer node X0 can behave as a search destination peer node, and the search destination The peer nodes X1, X2, X3... Can act as search source peer nodes. Therefore, in FIG. 1, the search source peer node X0 also includes the search destination function unit 4, and the search destination peer nodes X1, X2, X3.

  FIG. 2 is a functional block diagram showing the configuration of the main parts of the search source function unit 3 and the search destination function unit 4, and here, the configuration unnecessary for the description of the present invention is omitted.

  In the search source function unit 3, the search request generation unit 301 includes a search condition expression of context input separately and a search history related to the context search condition among the search histories stored in the search history table 2. The search request message described in the above is generated. This search request message is distributed by broadcast from the search request distribution unit 302 to the surrounding search destination peer nodes X1, X2, X3... Via the interface IF5.

Here, it is assumed that “contains all context values a0 and b0” as the context search condition, that is, the logical expression of the following expression (1) is given as the context search condition and is described and distributed in the search request message. to continue.

a0 AND b0… (1)

  In the search destination function unit 4, the search request reception unit 401 receives the search request message distributed from the search source peer node X0. The search condition extraction unit 402 extracts the context search condition expression [a0 AND b0] from the search request message. The search history extraction unit 403 extracts a search history from the search request message.

  The solution search unit 404 determines whether or not the context information registered in the context table 1 of the own node matches the context search condition. If the information matches, the ID of the own node is recognized as one of the search solutions. To do. For example, if the context registered in the context table 1 of the search destination peer node X1 is as shown in FIG. 3A, the context search condition is satisfied, so that the peer node ID of the search destination peer node X1 is recognized as the search solution. The On the other hand, if the context information registered in the context table 1 is as shown in FIG. 3B, it is determined that the context search condition is not satisfied.

  The solution search unit 404 further determines whether or not a search condition that logically satisfies the context search condition is already registered in the search history table 2 of its own node. The peer node ID registered as a past search solution is recognized as one of the search solutions. That is, if the search history registered in the search history table 2 of the own node is as shown in FIG. 4, the peer node IDs of the peer nodes X1 and X2 are recognized as the search solution.

  The solution candidate search unit 405 determines whether or not a search condition that logically satisfies a part of the context search condition is already registered in the search history table 2 of its own node. A past search solution for the condition is recognized as a search solution candidate. That is, if the search history registered in the search history table 2 of its own node is as shown in FIG. 4, the peer node X3 including the context value “a0” and the peer node X4 including the context value “b0” are the search solution candidates. The context values “a0” and “b0” are recognized as the ground conditions. Then, the pair [a0, X3] of the ground condition a0 and the search solution candidate X3 and the pair [b0, X4] of the ground condition b0 and the search solution candidate X4 are output as search solution candidate information.

  The search response generation unit 406 generates a search response message in which [peer node ID] is described for the search solution and [foundation condition, peer node ID] is described for the search solution candidate. The search response reply unit 407 returns the search response message to the search source peer node X0 via the interface IF5.

  Returning to the search source function unit 3, the search response receiving unit 303 receives the search response message returned from the search destination peer node. The search solution extraction unit 304 extracts a search solution [peer node ID] from the search response message. The solution candidate extraction unit 305 extracts information [foundation condition, peer node ID] of the search solution candidate from the search response message. The search solution specifying unit 306 compares the extracted search solution candidate information with the search history stored in the search history table 2, and specifies a search solution from the search solution candidates.

  That is, if the search history table 2 of the search source peer node X0 is as shown in FIG. 5A, it can be seen from the search solution candidate information [a0, X3] that the peer node X3 has the context value a0. Since it can be seen from the search history table 2 that the peer node X3 has the context value b0, the peer node X3 is newly recognized as a search solution.

  Similarly, the search solution candidate information [b0, X4] shows that the peer node X4 has the context value b0, and the search history table 2 shows that the peer node X4 has the context value a0. Peer node X4 is newly certified as a search solution.

  On the other hand, if the search history table 2 of the search source peer node X0 is as shown in FIG. 5B, it is not found that the peer node X3 has the context value b0, and the peer node X4 has the context value a0. Therefore, neither of the search solution candidates X3 and X4 is taken as a search solution.

  Next, the operation of the embodiment of the present invention will be described in more detail with reference to a flowchart. 6 is a flowchart showing the operation of the search source peer node X0, and FIG. 7 is a flowchart showing the operation of the search destination peer nodes X1, X2, X3. Here, the registered contents of the context table 1 and the search history table 2 of the search source peer node X0 are as shown in FIGS. 8A and 8B, respectively, and the context table 1 of the search destination peer nodes X1, X2, and X3. The search history table 2 is assumed to be as shown in FIGS. 9A, 9B, 10A, 10B, 11A, and 11B, respectively.

In the search source peer node X0, when the input of the context search condition is detected in step S1 of FIG. 6, in step S2, the logical expression of the context search condition is converted into a form in which a plurality of logical product terms are connected by logical sum. Is done. Here, the description will be continued on the assumption that the context search condition of the following expression (1) is converted into the logical expression of the following expression (2).

(a0 OR a1) AND (b0 OR b1) AND c0… (1)

(a0 AND b0 AND c0) OR (a0 AND b1 AND c0) OR (a1 AND b0 AND c0) OR (a1 AND b1 AND c0)… (2)

  In step S <b> 3, a search history related to the logical expression of the context search condition is extracted from the search history table 2. In this embodiment, a context condition including each element a0, a1, b0, b1, c0 of the context search condition and its peer node ID pair are extracted as a related search history. In step S4, a search request message in which the context search condition and the search history are described is generated by the search request generation unit 301. In step S5, the search request distribution unit 302 moves to the search destination peer nodes X1, X2, X3. be delivered.

  Each of the search destination peer nodes X1, X2, X3... Proceeds to step S42 when the search request message is received by the search request receiving unit 401 in step S41 of FIG. In step S42, the search condition extraction unit 402 extracts a context search condition from the search request message, and the search history extraction unit 403 extracts a search history from the search request message. In step S43, the solution search unit 404 searches whether the context registered in the context table 1 of the own node satisfies the context search condition.

  If it is the search destination peer node X1, as shown in FIG. 9A, since the context satisfies the second term of the above formula (2), it is determined that the context search condition is satisfied, and the process proceeds to step S44. The peer node ID [X1] of the own node is stored in the search solution set U1 as one of the search solutions. In step S45, the search history of the search source peer node X0 extracted from the search request message in step S42 is added to the search history table 2 of its own node.

  In contrast, the context of the search destination peer node X2 shown in FIG. 10 (a) and the context of the search destination peer node X3 shown in FIG. 11 (a) both satisfy the context search condition of the above formula (2). Since it does not carry out, it progresses to step S46.

  In step S46, the solution search unit 404 determines again whether or not a search history satisfying the context search condition is registered in the search history table 2 of its own node. In the present embodiment, the search history table 2 of the search destination peer node X1 shown in FIG. 9B and the search history table 2 of the search destination peer node X2 shown in FIG. The search history that satisfies the context search condition is not registered.

  On the other hand, in the search history table 2 of the search destination peer node X3 shown in FIG. 11 (b), a context search condition that satisfies the third term [a1 AND b0 AND c0] of the above formula (2) and its search Since the result is registered as a search history, the process proceeds to step S47. In step S47, the peer node ID “X5” of the search solution in the search history is stored in the search solution set U1 as one of the search solutions.

  In step S48, a search history satisfying a part of the context search condition of the above equation (2) is searched from the search history table 2 by the solution candidate search unit 405. For the search destination peer node X1, as shown in FIG. 9 (b), the search is performed for the context search condition [b0 AND c0] partially matching the first and third terms of the context search condition of the above formula (2). Since it is registered as a history and a search history including the element b1 of the context search condition of the above equation (2) is registered, the process proceeds to step S49. In step S49, the context search condition (foundation condition) [b0 AND c0] as the basis and the pair [b0 AND c0, X3] of the search solution candidate node ID [X3] and the context search condition [b1] as the basis And the pair [b1, X2] of the search solution candidate node ID [X2] are stored in the search solution candidate set U2 as search solution candidate information.

  In the search history table 2 of the search destination peer node X2 shown in FIG. 10B, the context search condition including the element c0 of the context search condition of the above equation (2) is registered as the search history, and the process proceeds to step S49. The pair [c0, X2] of the context search condition [c0] as the basis and the node ID [X2] of the search solution candidate is stored in the search solution candidate set U2 as search solution candidate information.

  On the other hand, in the search history table 2 of the search destination peer node X3 shown in FIG. 11B, the search history including the element of the context search condition of the above formula (2) has already been extracted as the search solution. It is determined that it is not registered other than the search history.

  In step S50, the search response message in which the search solution stored in the search solution set U1 and the search solution candidates stored in the search solution candidate set U2 are described is generated by the search response generation unit 406. The search response reply unit 407 returns a reply to the search source peer node X0.

  Returning to FIG. 6, when the search response message is received by the search response receiving unit 303 in step S6, the search source peer node X0 proceeds to step S7. In step S7, the search solution extraction unit 304 extracts a search solution from the search response message, and the solution candidate extraction unit 305 extracts search solution candidate information from the search response message. In step S8, the search solution specifying unit 306 searches among the search solution candidates based on the search history registered in the search history table 2 of the own node, the extracted search solution candidates and the ground conditions. A solution is identified.

  In this embodiment, as schematically shown in FIG. 12, the information [b0 AND c0, X3] of the search solution candidate acquired from the search destination peer node X1 and the context search condition [a0 in the search history table 2 of its own node ] Is registered as a search solution that satisfies the first term of the context search condition of the above equation (2).

  Further, search solution candidate information [c0, X2] acquired from the search destination peer node X1, search solution candidate information [b1, X2] acquired from the search destination peer node X2, and context search in the search history table 2 of the own node Based on the fact that peer node X2 is registered as a search solution for condition [a0], peer node X2 that is a search solution candidate is recognized as a search solution that satisfies the second term of the context search condition of equation (2). .

It is the figure which showed the structure of the peer to peer network to which the context search method and apparatus of this invention are applied. It is the functional block diagram which showed the structure of the search origin functional part and the search destination functional part. It is the figure which showed an example of the context table of a search destination peer node. It is the figure which showed an example of the search history table of a search destination peer node. It is the figure which showed an example of the search history table of a search origin peer node. It is the flowchart which showed the operation | movement of the search origin peer node. It is the flowchart which showed the operation | movement of the search destination peer node. It is the figure which showed an example of the context table and search history table of search origin peer node X0. It is the figure which showed an example of the context table and search history table of search destination peer node X1. It is the figure which showed an example of the context table and search history table of search destination peer node X2. It is the figure which showed an example of the context table and search history table of search destination peer node X3. It is the figure which expressed typically the method of specifying a search solution from search solution candidates.

Explanation of symbols

  DESCRIPTION OF SYMBOLS 1 ... Context table, 2 ... Search history table, 3 ... Search origin functional part, 4 ... Search destination functional part, 301 ... Search request production | generation part, 302 ... Search request delivery part, 303 ... Search response receiving part, 304 ... Search solution Extraction unit, 305 ... solution candidate extraction unit, 306 ... search solution identification unit, 401 ... search request reception unit, 402 ... search condition extraction unit, 403 ... search history extraction unit, 404 ... solution search unit, 405 ... solution candidate search unit , 406 ... Search response generation unit, 407 ... Search response reply unit

Claims (11)

The search source peer node transmits a search request including a context search condition to the search destination peer node, and each search destination peer node returns a search response in which a search solution satisfying the context search condition is recorded to the search source peer node. In the device
The search source peer node is
A context table storing context information unique to the node;
A search history table storing a history of search solutions for each context search condition;
Means for delivering a search request in which a context search condition is described;
Means for receiving a search response returned from the search destination peer node;
Means for extracting search solutions and search solution candidates from the search response;
Means for identifying a search solution from the search solution candidates based on the search history table;
Means for registering the context search condition and the search solution in association with the search history table. The search source peer node transmits a search request including a context search condition to the search destination peer node, and each search destination peer node returns a search response in which a search solution satisfying the context search condition is recorded to the search source peer node. In the device
The search source peer node is
A context table storing context information unique to the node;
A search history table storing a history of search solutions for each context search condition;
A search source function unit for functioning as a search source peer node;
A search destination function unit for functioning as a search destination peer node,
The search source function unit
Means for delivering a search request in which a context search condition is described;
Means for receiving a search response returned from the search destination peer node;
Means for extracting search solutions and search solution candidates from the search response;
Means for identifying a search solution from the search solution candidates based on the search history table;
Means for registering the context search condition and the search solution in association with the search history table;
The search destination function unit
Means for receiving a search request from a search source peer node;
Means for extracting a context search condition from the search request;
Means for extracting a search solution satisfying the context search condition based on the context table and the search history table;
Means for extracting search solution candidates that satisfy a part of the context search condition based on the search history table;
Means for generating a search response in which the search solution and search solution candidates are described;
Means for returning the search response to a search source peer node. The context search device according to claim 2 , wherein the search source function unit includes means for rewriting a context search condition given by a logical expression into a logical sum of logical product terms. The context search condition is given as a logical sum of logical product terms, and the means for extracting the search solution is a self-node when the context registered in the context table satisfies any logical product of the context search conditions. The context search apparatus according to claim 2 , wherein the search solution is a search solution. The context search condition is given as a logical sum of logical product terms, and the means for extracting the search solution satisfies the logical product of any of the context search conditions in the search history search condition registered in the search history table. The context search apparatus according to claim 2 , wherein a search solution of the search history is a search solution of the context search condition. The context search condition is given as a logical sum of logical product terms, and the means for extracting the search solution candidate is a search history search condition registered in a search history table that is one of the logical products of the context search conditions. 3. The context search apparatus according to claim 2 , wherein when a part is satisfied, a search solution of the search history is set as a search solution candidate of the context search condition. 3. The context search according to claim 2 , wherein the search source function unit extracts a search history related to the context search condition from a search history table of its own node and records the search history together with the context search condition in a search request. apparatus. The search destination function unit
A means for extracting a search history of the search source peer node from the search request;
3. The context search apparatus according to claim 2 , wherein when the context of the own node satisfies a context search condition, the search history of the extracted search source peer node is additionally registered in the search history table of the own node. 2. The context search apparatus according to claim 1, wherein the search source peer node includes means for rewriting a context search condition given by a logical expression into a logical sum of logical product terms. 2. The context search device according to claim 1, wherein the search source peer node extracts a search history related to the context search condition from a search history table of its own node and records it in a search request together with the context search condition. . The search source peer node transmits a search request including a context search condition to the search destination peer node, and each search destination peer node returns a search response in which a search solution satisfying the context search condition is recorded to the search source peer node. In the method
The search source peer node and the search destination peer node are:
A context table storing context information unique to the node;
A search history table storing a history of search solutions for each context search condition,
The source peer node is
Including a procedure for distributing a search request in which a context search condition is described to a search destination peer node;
The search destination peer node is
Receiving the search request and extracting a context search condition;
A procedure for extracting a search solution satisfying the context search condition based on the context table and the search history table;
A procedure for extracting search solution candidates that satisfy a part of the context search condition based on the search history table;
Returning a search response in which the search solution and the search solution candidate are described to the search source peer node,
The search source peer node
Receiving the search response and extracting a search solution and search solution candidates;
A procedure for identifying a search solution from the search solution candidates based on the search history table;
And a procedure for registering the context search condition and the search solution in association with the search history table.

Images