System and method for conducting adaptive search using a peer-to-peer network7010534Abstract A distributed comparison shopping system is based on a decentralized, distributed architecture utilizing a peer-to-peer network. The system creates an active marketplace with real-time price comparisons, with the peer-to-peer nodes coordinating connectivity with other peers and building a dynamic network. Each message includes a fixed component and an adaptive update component. The adaptive update component contains search criteria and search status fields that are selectively modified as the message travels through the peer-peer network. A node that receives a message will interpret the search criteria and apply those criteria to a local search result. The node then either forwards the unmodified or the modified message to other nodes in its neighborhood, or, alternatively, requests an authorization to modify the message prior to rebroadcasting, from the source node. Claims What is claimed is: Description FIELD OF THE INVENTION Additional optimizations for query routing are possible. The use of channels for communication between nodes provides rich expressiveness in queries because the underlying format is XML. Digital signatures may be used to verify data integrity properties. The present system provides a marketplace for merchants and customers that does not require price crawlers. Because the connection between merchant and customer is "real time," the information provided to the customer is current. The present system has unlimited scalability; millions of nodes can be supported concurrently. Users can buy and sell products or services simultaneously. The present system is readily integrated into the existing Internet infrastructure. For example, a user other than a merchant wishes to sell an item such as a book. The user chooses a shopping channel. Once the information is entered, it is available for the adaptive search of the present invention. A merchant may provide products or services by providing a gateway to their legacy product database. This makes the information in the database available to the peer-to-peer network. The gateway performs the transcoding work required to communicate with other nodes in the network. To purchase a product, such as a book, the user enters a specific search request within a graphical user interface using a "book channel." The present system searches for the lowest available price for that item by transmitting the request to its neighborhood nodes on the peer-to-peer network. The nodes that wish to respond return the request with their offer and a URL to the product site. BRIEF DESCRIPTION OF THE DRAWINGS The various features of the present invention and the manner of attaining them will be described in greater detail with reference to the following description, claims, and drawings, wherein reference numerals are reused, where appropriate, to indicate a correspondence between the referenced items, and wherein: FIG. 1 is a schematic illustration of an exemplary operating environment in which a distributed comparison shopping system of the present invention can be used; FIG. 2 is a block diagram of a high-level architecture of the distributed comparison shopping system of FIG. 1; FIG. 3 is comprised of FIGS. 3A, 3B, and 3C, and represents a process flow chart illustrating a method of operation of the distributed comparison shopping system of FIGS. 1 and 2; FIG. 4 is represents a schematic illustration of the operation of the distributed comparison shopping system of FIGS. 1 and 2 within a peer-to-peer network; and FIG. 5 is a block diagram representation of an original message as modified by the system of FIG. 4. DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS The following definitions and explanations provide background information pertaining to the technical field of the present invention, and are intended to facilitate the understanding of the present invention without limiting its scope: Channel: Communications category within the peer-to-peer network. Nodes can form their own channels that they then broadcast to other nodes. These other nodes might or might not adopt this new channel. Node: A processing location in a network. In a peer-to-peer networks, a node can be a computer, server, or a gateway. Peer-to-peer Architecture: A type of network in which each workstation has equivalent capabilities and responsibilities. This differs from client/server architectures, in which some computers are dedicated to serving the others. Peer-to-peer networks are generally simpler, but they usually do not offer the same performance under heavy loads. XML: eXtensible Markup Language. A standard format used to describe semi-structured documents and data. During a document authoring stage, XML "tags" are embedded within the informational content of the document. When the XML document is subsequently transmitted between computer systems, the tags are used to parse and interpret the document by the receiving system. FIG. 1 portrays an exemplary overall environment in which a system 10 and associated method for conducting distributed comparison shopping using a peer-to-peer network according to the present invention may be used. System 10 includes a software programming code or computer program product that is typically embedded within, or installed on a host server 15. Alternatively, system 10 can be saved on a suitable storage medium such as a diskette, a CD, a hard drive, or like devices. While the system 10 will be described in connection with the WWW, the system 10 can be used with a stand-alone database of terms that may have been derived from the WWW and/or other sources. The cloud-like peer-to-peer network 20 is comprised of communication lines and switches connecting servers such as servers 25, 30, to gateways such as gateway 35. The servers 25, 30 and the gateway 35 provide the communication access to the WWW or Internet. Users, such as remote Internet users, are represented by a variety of computers such as computers 40, 45, 50, and can query the host server 15 for desired information through the peer-to-peer network 20. Computers 40, 45, 50 each include software that will allow the user to browse the Internet and interface securely with the host server 15. The host server 15 is connected to the peer-to-peer network 20 via a communications link 55 such as a telephone, cable, or satellite link. The servers 25, 30 can be connected via high-speed Internet network lines 60, 65 to other computers and gateways. System 10 could use the Internet for communication between computers and servers. Rather than using a server-client approach as used in the Internet, the peer-to-peer network 20 uses nodes. Each node can operate either as a server or as a client, publishing or receiving information. The host server 15 and computers 40, 45, 50 can be viewed as nodes in the peer-to-peer network 20. The high-level architecture for system 10 is shown in FIG. 2. System 10 generally comprises a request preprocessor 205, a main decision logic 210, a query engine 215, an updater 220, and a request forwarder 225. In addition, system 10 has access to a local database 230. System 10 connects to the peer-to-peer network 20 via a peer-to-peer communication core 235. The peer-to-peer communication core 235 could use known or available technology such as Gnutella, Freenet, or Sun Microsystems JXTA®. With further reference to FIG. 3 (FIGS. 3A, 3B, 3C), it illustrates a method of operation 300 of system 10 as implemented by a merchant's node (Node A, 406 in FIG. 4). The peer-to-peer (P2P) communication core 235 receives a message via the peer-to-peer network 20 at block 305, and forwards it to the request preprocessor 205 at block 310. The request preprocessor 205 then verifies the integrity of the message at block 315 by, for example, validating the contents and the electronic signatures. If method 300 determines at decision block 320 that the message is invalid, system 10 forwards it to the next node in the network 20 (block 325). Otherwise, system 10 proceeds to block 330 and forwards the message to the main decision logic 210 at block 330. The main decision logic 210 retrieves the subject ID (e.g., product and/or service identification) and search criteria from the message at block 335, then forwards the subject ID and search criteria to the query engine 215 at block 340. At block 345, the query engine 215 formulates the query using the subject ID and search criteria then queries the local database 230. The local database 230 returns the query results back to the query engine 215 at block 350, which, in turn, forwards the query results to the main decision logic 210 at block 355. The main decision logic 210 compares the query results with the search criteria at decision block 360. If the search criteria are met, i.e., the merchant has the item and can meet the price presented in the message, the node A, 406 can take, for example, one of two actions, as determined by the user and set as instructions in the message. According to a first embodiment (FIG. 3B), the main decision logic 210 forwards the results to the updater 220, at block 365. The updater 220 updates the search criteria and/or the search status within the message, resulting in a modified message, at block 366. The updater 220 forwards the modified message to the request forwarder 225 at block 367. The request forwarder 225 sends the modified message to the peer-to-peer communication core 235 at block 368, which, in turn, forwards the modified message to the next node or nodes in the peer-to-peer network 20 at block 369. For example, the merchant responds to the buyer with a lower price or better shipping terms. This new information is encoded in the original search request, which reflects that the dynamically changing nature of the adaptive search. According to another embodiment of the present invention (FIG. 3C), the main decision logic 210 forwards an authorization request to the request forwarder 225, at block 370. In turn, the request forwarder 225 forwards the authorization request back to the source or originating node, requesting confirmation or authorization to update the message, at block 372. If method 300 determines at decision block 373 that the authorization request has been approved by the source node, such as if the source node returns the authorization to the main decision logic 210, via the request pre-processor 205, at block 374, method 300 proceeds to block 365 and repeats the steps at block 366, 367, 368, and 369, as described earlier, forwarding the updated message to the next node or nodes in the peer-to-peer network. As an example, if the local found result is "better" in some aspect than the current criterion (or criteria), such as price, of the original message, the node contacts the originating node and sends a request to modify the original message. The modified message request contains, for example, the following information: If, however, method 300 determines at decision block 373 that the source node did not grant the request authorization, the source node B, 408, sends an instruction to node A, 406, to either (1) send forward the unmodified message to succeeding nodes in the network 20, or (2) not to forward the message to any other node in the peer-to-peer network 20. One function of the updater 220 is to negotiate a modified message from the search result and the original message. Three exemplary responses are possible. First, the merchant can provide the item for less than the current minimum. In which event, the main decision logic 210 instructs the updater 220 to modify the message and to replace the current minimum with the new minimum available from the merchant and to update the status field of the message. Second, the merchant can provide the item for the same value as the current minimum. In which event, the main decision logic 210 instructs the updater 220 to update the status part of the message. Third, the merchant can not match or beat the price value in the message, but can match one or more other criteria in the message, such as the shipping time, etc. In which event, the main decision logic 210 may instruct the updater 220 to modify the search criteria portion of the message, resulting in a modified message. Returning now to FIG. 3B, if method 300 determines at decision block 360 that the search criteria are not met, i.e., the merchant does not have the product requested, then the original message is sent unmodified to the request forwarder 225 at block 380. The request forwarder 225 then forwards the unmodified (or original) message to succeeding nodes. Optionally, the node A, 406, could modify the search status field of the message and forwards the updated information to the succeeding nodes in the neighborhood. An example that further illustrates the operation of system 10 is illustrated by FIGS. 4 and 5. The various nodes in FIG. 4 preferably have the same or similar design and operation using system 10. The peer-to-peer network 20 includes many neighborhoods such as neighborhood 402 and neighborhood 404. Each neighborhood 402, 404, contains clusters of peers or nodes within the peer-to-peer network 20. In this illustration, node A, 406, node B 408, node C, 410, and node D, 412, are in neighborhood 402. Node C, 410, is also in neighborhood 404 along with node E, 414, and node F, 416. In this example, node B 408 is the source node, and wishes to request quotes for an item (represented by the letter "X") such as a book, and sets the price limit for that book at $20. System 10 creates the request as a structured query, shown as original message 418. Message 418 and subsequent modified (or updated) messages preferably comprise two components: a fixed component 505 and an adaptive update component 510. In turn, the fixed component 505 comprises a subject identification (ID) 515, which is comprised of a product or service identification, encoded in XML. The adaptive update component 510 comprises a search criteria field (or fields) 520, encoded in Boolean Expression query language, and a search status field 525 that contains metadata collected as the message travels throughout the peer-to-peer network 20. The product or service identification may be very specific; i.e., "book; ISBN #1123413". Exemplary search criteria include price limits and delivery date limits. Message 418 comprises the structured message "X" and the criteria limit "20". The search status field 525 monitors the number of modifications the message receives, and includes values such as number of nodes traveled by the message, time stamp, etc. The search status field 525 is a bookkeeping value, and is not part of the search criteria. However, the search criteria 520 of the message can be formulated to include the search status. For example, the user at node B, 408, may limit the travel time of message 418 through the network 20 to a few hours, such as 4 hours. In which case, system 10 (at each node) will not rebroadcast the message after the time limit expires. System 10 at node A, 406, determines whether the merchant at node A, 406 has the product that the source node B, 408, is requesting by querying a local database 230 (or any other suitable database to which node A has access) at node A, 406 (block 345). If the merchant at node A, 406, has the product, system 10 at node A, 406, determines whether the search criteria goal of message 418 can be met. If not, node A, 406, forwards message 418 to one or more nodes in neighborhood 402. If node A, 406, can satisfy the criteria of message 418, node A, 406, modifies the search criteria 515 and/or the search status 525, as described earlier, resulting in modified message 555 that contains a modified search criteria component 520′ and/or a modified search status component 525′. A feature of system 10 is the ability to change the criteria goal of message 418 to reflect the new criteria 520. For example, the price of node A, 406, for the product requested by node B, 408, is $18. System 10 at node A, 406, changes the price criteria of message 418, to $18, as shown by the modified message 555. Node A, 406, then broadcasts (or rebroadcasts) the modified message 555 to node D, 412, via path 424, node C, 410, via path 426, and back to node B, 408, via path 428. Node D, 412, searches its local database for the product and price in modified message 555. Node D, 412, finds that it has the product, but the price is $24. However, the merchant at node D, 412, may be able to match or beat some other criteria such as shipping time or shipping cost. Node D, 412, then changes the modified message 555, creating another modified message 430. Node D, 412 returns the modified message 430 to node B, 408, via path 432 and forwards modified message 430 to other nodes in its neighborhood, as indicated by path 434. Node C, 410, also searches its local database for the product and price in modified message 555. The merchant at node C, 410, can match the price in modified message 555. Node C, 410, then sends a modified message 436 to node B, 408, via path 438, matching the search criteria of the modified message 555. Node C, 410, also sends the modified message 436 to node E, 414, via path 440 in neighborhood 404. Node E, 414, forwards the modified message 436 to node F, 416, via path 442. Node F, 416, can route a response back to node B, 408, through node C, 410, via path 444 and path 438 if the merchant at node F, 416, can meet the criteria of modified message 436. Node B, 408, is waiting for incoming search results. These incoming messages could take one of three modified message forms. First, the originator of the modified message may offer the product for more than the current minimum (node D, 412). Node B, 408, would update the search status component 525 of the modified message and replace it with the current minimum, then return the modified message to the originator of the modified message. Second, the originator of the modified message offers the product for the same price as the current message (i.e. node C, 410). Node B, 408, would update the status part of the incoming message and replace it with the current minimum. Node B, 408, would then add the merchant at that node (node C, 410) to the response list in the local database 230 at node B, 408. Third, the originator of the modified message offers the product for less than the current minimum (node A, 406). Node B, 408 updates the search status component of the obtained message, replaces it with the current minimum, and adds the seller to the list in the local database 230 at node B, 408. The user at node B 408 now has quotes from two merchants stored in the local database 230: the merchant at node A, 406, for $18 and the merchant at node C, 410, for $18. In addition, the original message 418 is stored in the local database for reference to incoming quotes. The user may now select either offer by using the URL included in the message to contact the merchant. In another embodiment, node C, 410, does not change the message but matches the search criteria. According to one embodiment, node C, 410, sends an authorization request to modify the message, informing node B 408 that node C 410 can offer the best price for the item. Node B 408 then decides whether or not to accept node B's offer, as explained earlier. The user at node B, 408, may investigate the credibility of the merchant at node C, 410, and find that the merchant at node C, 410, has a reputation for poor service or unethical business practices, etc. The user at node B, 408, may then refuse to allow node C, 410, to update the message. Otherwise, the user at node B 408 chooses to update the message from the merchant at node C, 410, and returns the appropriate authorization to node C, 410. It is to be understood that the specific embodiments of the invention that have been described are merely illustrative of certain application of the principle of the present invention. Numerous modifications may be made to the system and method for modifying a peer-to-peer network to accommodate distributed comparison shopping invention described herein without departing from the spirit and scope of the present invention.
|
Same subclass Same class Consider this |
||||||||||