High-speed term and phrase matching via successive complexity reduction

[0001] This application claims priority to U.S. Provisional Application No. 60/382,071, titled “High-Speed Token And Phrase Matching Via Successive Complexity Reduction”, filed on May 20, 2002, and U.S. Provisional Application No. 60/384,616, titled “Automatic Securities Program Trading Using Tokens Or Match Phrases”, filed on May 29, 2002 which are both hereby fully incorporated by reference.

[0002] 1. Field of the Invention

[0003] The invention relates to the field of information processing. More specifically this invention relates to the field of disseminating electronic information via a computer network.

[0004] 2. Background Information

[0005] Networking advances have brought about significant improvements in the way information is communicated. As recently as the 1990s information was transmitted to users routinely via phone calls, scheduled news broadcasts or a postal service. This made the process of real time decision making difficult due to a lack of confidence in the currency of information. Indeed frequently, the only people with a reasonably complete picture on a situation were those people with dedicated, usually expensive, resources for the collection of real time data.

[0006] The modern commercial development of the global communications network referred to as the Internet has dramatically changed the availability of information. Today users can obtain news information by using a computer to access news sites via the Internet and specifically via the World Wide Web. This allows users to obtain information when the user wishes to obtain information vis-à-vis obtaining information at predetermined times. Notwithstanding this increase in information availability, several issues still remained. Specifically the ability of a user to obtain data in a timely matter and the ability to distinguish relevant information from the vast quantity of information available via the Internet and the World Wide Web are both significant challenges.

[0007] Various information sources offer an ability to push information to a user. A typical example of this is the provision of information via a stream of data. Specifically, real time stock pricing information is available whereby a user may obtain real time stock pricing for purposes of determining an action to be taken on a particular stock of interest. While this is plausible for the specific example of monitoring a specific data source for a specific security of interest, this method of operation for working with large volumes of information available from multiple data sources is untenable.

[0008] Consequently an efficient method of dealing with the vast quantities of information available via today's information networks is required.

[0021] Processes for matching sources of information with user match criteria are advantageously decomposed into stages such that more compute-intensive operations are performed on reduced data sets. In addition, the news information is received and, by utilizing user match criteria, automated securities transactions are advantageously performed. In the following description, numerous specific details are set forth to provide a thorough understanding of embodiments of the invention. One skilled in the relevant art will recognize, however, that the invention can be practiced without one or more of the specific details, or with other methods, components, materials, etc. In other instances, well-known structures, materials, or operations are not shown or described in detail to avoid obscuring aspects of the invention.

[0022] Reference throughout this specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the present invention. Thus, the appearances of the phrases “in one embodiment” or “in an embodiment” in various places throughout this specification are not necessarily all referring to the same embodiment. Furthermore, the particular features, structures, or characteristics may be combined in any suitable manner in one or more embodiments.

[0023] FIG. 1 illustrates an operational flow of a server with a matching engine, in accordance with one embodiment. A composite match criteria list is created 110. As described in further detail below, this composite match criteria list is comprised of match criteria from a number of users. Upon creating a composite match criteria list, the server begins processing messages from an informational source. After receiving a message 120, the server generates a message term list from the message 130. For example, in the case where a message is a header for a news story, the header is divided into terms. Each term is a word of the header. A set of matching terms can be created from the composite list and the message term list 140. From this list of matching terms, a determination can be made as to whether any of the user criteria are satisfied 150. If there are user criteria which are satisfied, the message is sent to users corresponding to the matching criteria.

[0024] FIG. 2 illustrates the steps in the generation of a composite user list, in accordance with one embodiment. An agent waits for a user criteria list to be received from a user 210. The agent then reads a term from the user criteria list 220. The agent determines if the term is in a composite term list 230. If the term is not in the composite term list, the agent will add the term to the composite list of terms 240. If the term is in the composite term list, this addition to the composite term list is skipped. Next, the agent will add the term to a user's cross reference list 250 indicating that the term is to be associated with the user. The agent determines if there are more terms to be processed in this user's criteria list 260, if so, the agent processes these in the manner described above. If not, the agent waits for another user criteria list to be received for processing.

[0025] FIG. 3 illustrates a composite match criteria list 350 generated from user criteria lists, in accordance with one embodiment. A server has processed four separate user match criteria lists 310-340 each containing a list of terms to be matched. Upon processing the first user match criteria list 310, none of the terms listed in the first user match criteria list 310 are present in the, initially empty, composite match criteria list 350. Thus, after processing the first user match criteria list 310, the composite match criteria list contains a first set of terms 315. The server then processes the second user match criteria list 320. During the processing of the second user match criteria list 320, the server advantageously determines that there is only one term 325 in the second user match criteria list 320 not already present in the composite match criteria list 350. Thus, only one term 325 is added to the composite match criteria list 350. Consequently, as the number of user match criteria lists increases, the number of terms in the composite match criteria list does not grow in the manner that it would otherwise. In the embodiment shown, two additional user match criteria list 330 340 are processed by the server. This results in the addition of several terms 335 345 to the composite match criteria list 350.

[0026] FIG. 4 illustrates the relationship between the composite number of user match criteria and the number of users utilizing a matching engine. As the number of users grows, due to redundancies in the terms that will be used by different users, the increase in the number of terms in the composite user match list does not grow linearly. A smaller composite match criteria list results in a decreased processing time for determination matching terms in a message. Consequently, this results in a decreased processing time of the determination of the satisfaction of any entries in a user match criteria list. Thus by reducing the set of terms to be searched, increased efficiency in the matching process occurs.

[0027] FIG. 5 shows a flow diagram illustrating the procedure for creating a message term list from a message, in accordance with one embodiment. A message processing routine receives a new message for processing 510. The message processing routine extracts a term from the new message for processing 520.

[0028] The message processing routine consults a list of undesirable terms for matching. In various embodiments, it is desirable to remove terms from matching consideration that are necessary to properly convey meaning to a reader, but do not necessarily contribute to the user match criteria. Such terms frequently include articles such as “an”, “a” and “the”. However, the list of undesirable terms may include other parts of speech in addition to articles. Thus, the message processing routine can employ discrete lists of undesirable terms. Alternatively, the message processing routine can apply “rules” to a message when processing the terms. For example, the rules may stipulate that the message processing routine is to remove all articles and pronouns from a message. By removing undesirable terms from the message term list, further complexity reduction is accomplished for the matching process.

[0029] Returning now to FIG. 5, regardless of the method of determination, a determination is made as to whether the currently processed term is an undesirable term 530. If the term is not undesirable, then it is added to the reduced message term list 540. A check is made to determine if there are additional terms in the message to process 550 and, if so, the process is repeated for each term.

[0030] FIG. 6 shows lists maintained by a server illustrating phrase matching capability, in accordance with one embodiment. Four lists are shown. The first list is the composite user term list 610. This list contains the reduced list of terms as previously discussed. The second list contains a composite ordered user phrase list 620. In this embodiment, the server contains support for handling ordered phrase lists of terms. Thus, when a user match criteria list is obtained, a composite ordered phrase list 620 is also created in addition to the composite user match criteria list, as previously described.

[0031] FIG. 6 also illustrates the generation of cross reference listings. As part of the generation of user term and user phrase lists, user term cross reference 630 and user phrase cross reference 640 lists are generated. When a composite user term list is created, a user term cross reference list is also created to identify associations between terms and users. This facilitates the determination of which user is to be sent a message when a match occurs between the composite user term list and the message term list. A similar list is created for phrases as illustrated.

[0032] For example, assume that the phrase “preferred stock” occurs in a user criteria list for a user with a userid of 3. In addition, assume that a message containing the phrase “preferred stock” is processed. A matching engine can use the composite user phrase list 620 to determine that the phrase “preferred stock” is to be matched 625. The matching engine can then use the user phrase cross reference list 640 to determine that user 3 545 is the user to whom the phrase match occurred.

[0033] In another embodiment, support for having terms that are not allowed to be in the phrase as well as the ability to perform proximity searching is also present. In yet another embodiment, industry specific term and phrase lists are created and distributed with a system. In this case, a user has the ability to specify that all or a portion of a given industries default criteria are to be included in the user criteria list.

[0034] FIG. 7 illustrates an information source 710 providing information to a server containing a matching engine 740, in accordance with one embodiment. An information source 710 that provides real-time information is connected to a client 740 via a network 720. Information source 710 can be any provider of information. For example, in one embodiment, the information source can be a real-time news provider such as Reuters News Service. The information source is provided an address on the network 720 for transferring information to a node containing a storage location 730. In this manner, the information source 710 does not need to be dependant upon the processing speed of the server with the matching engine 740. For example, information source 710 is provided with an address of a node containing a storage location 730 which supporting communications via the File Transfer Protocol (FTP). Information source 710 feeds information to the FTP node asynchronously to the server with matching engine 740. The server with matching engine 740 can then process the information as it is able to do so. By having an optimized term and phrase matching routine, as disclosed herein, a server with matching engine 740 is better able to timely serve the information as it is received.

[0035] FIG. 8 illustrates a system compatible with the disclosed term and phrase matching methodology. Sources of news 812-816 provide information to a number of news servers containing matching engines 822-824. In this embodiment, the news servers with matching engine 822-824 have a direct, dedicated feed from the sources 812-816 to minimize the delay in receiving the news information that would otherwise occur as a result of network slow downs. In the embodiment shown, information is shown as being pushed to the servers. In other embodiments, as discussed subsequently, information is actively obtained by a scanner accompanying a matching engine. The news servers with matching engine 812-816 process the information to determine if there is a match to user criteria. If there is a user criteria which is matched, a cross reference is made to the news server's databases to determine the proper user and the corresponding destination client 842 848 for that user. Upon determination of the corresponding destination client 842 848, a proper broadcaster 830 832 is ascertained. The new servers with matching engines 822-824 then forward the message to the appropriate clients 842-848 through one or more broadcasters 830-838. In one embodiment, the broadcaster contains queue managers. The queue managers provides the ability to store messages for clients to retrieve at a later time if the client is offline when an initial attempt to deliver a message occurs.

[0036] The information that is received by the client 842-848 can then be provided to the user in any number of manners. Due to the advantageous processing of information in a time efficient fashion by the disclosed matching engine, provision of the matched information to a client in a timely manner is also possible. Thus in one embodiment, a pop-up window is utilized to alert the user to the presence of information from the matching engine. In addition, the use of the matching information to perform automatic actions wherein the timely performance of such actions, as subsequently described, is a benefit of the disclosed methodology.

[0037] FIG. 9 illustrates a system utilizing scanners and match engines 922-926 along with a brokerage engine 930 to perform automatic securities trading, in accordance with one embodiment. In this embodiment, the scanners are source type specific. For example, one scanner with its matching engine 922 contains a Uniform Resource Locator (URL) scanner. This URL scanner looks at pages from the World Wide Web 912 and checks for changes in links. When a change occurs, this changed page is processed by the matching engine. In this embodiment, a second scanner with its matching engine 924 scans a file system 914. The information on the file system is “pushed” there from a news source (not shown) as previously discussed in connection with FIG. 7. Also illustrated is a third scanner with matching engine 926. This scanner with matching engine 926 receives a direct feed from news source 916. Other possibilities (not shown) include the ability of a matching engine to have more than one scanner. For example, a single matching engine can have one scanner for scanning a file system 914 and a second scanner for receiving a direct feed from a news source 916.

[0038] Information 912-914 is obtained by the scanners with match engines 922 924. The scanners with match engines 922 924 determine if criteria have been satisfied for the purchase of securities. If so, a brokerage engine 930 is utilized to perform securities purchase and monitoring. FIG. 10 illustrates a flow diagram for a match engine 922 924 and brokerage engine 930, in accordance with one embodiment. A scanner 924 receives a message and the matching engine processes the message 1010. For example, in one embodiment, the processing includes removing undesired matching terms and determining if a user match criteria for terms and/or phrases are satisfied. If there are no user criteria satisfied by the matching terms 1020 then the scanner 924 will obtain another message for processing 1010. If there is a satisfied user criteria, a corresponding transaction criteria list is read 1030 and checked 1040 to see if there is a company match between the satisfied match criteria and those in the transaction criteria list. If there is a match, then the user's transaction criteria are checked to determine if a stock sale is to be performed based on this message.

[0039] FIG. 11 illustrates a user transaction criteria list compatible with the embodiment illustrated in FIGS. 9 and 10. The rows in the table illustrate separate transaction criteria for a user, in this case user10. The first column illustrates the various user match criteria against which a message is checked 1110. The following two columns 1120 1130 in the table indicate the security to which the criteria apply. In the case of the first two rows, the corresponding user match criteria apply to any company. The fourth column specifies the price at which the securities are to be purchased 1140. For example, in the third row, the securities are to be purchased at market value 1142. In the second row, however, a not-to-exceed amount 1144 is placed on the price at which the securities can be purchased. The fifth column specifies the number of shares to be transacted 1150. The remaining columns specify when the securities should be sold. The sixth column specifies the upper percentage limit on the stock price at which the security should be sold 1160. For example, in the first row's transaction criteria, the stock should be sold if it increases in value by 5% from the purchase price 1165. The seventh column specifies the percentage loss limit on the stock price at which the security should be sold 1170. For example, in the first row's transaction criteria, the stock should be sold if it decreases in value by 3% from the purchase price 1175. Such a limit can be used to minimize losses in the cases where the market does not react as expected to the news. The final column indicates a time at which the stock should be sold, if the two previously mentioned conditions have not been met 1180. For example, in the first row's transaction criteria, the stock should be sold after 4 hours and 30 minutes if it has not increased by 5% or decreased by 3% from the time it was purchased 1185. These set of transaction criteria for the processing of the securities is exemplary and not intended to limit in any manner. Others types of investment exercises such as options purchases and sales as well as shorts sales are possible.

[0040] For illustration, assume a news message obtained via URL scanner 912 containing the phrase “XYZ Corporation Announces Stock Split” is received and processed by a scanner with a matching engine 922. This scanner with matching engine 922 contains a composite user criteria list (not shown) containing, among other criteria from other users, the match criteria 1110 of user10. Thus, this composite user criteria list will include terms “stock” and “split”. Moreover, the phrase “stock split” is noted and associated with user10. In addition to the term and phrase matching criteria, the scanner contains the transaction criteria for user10 as illustrated in FIG. 11. In the embodiment shown, upon receipt and processing of the message “XYZ Corporation Announces Stock Split”, a resulting match of the “stock split” phrase occurs. Upon determination that user10's match criteria 1110 have been satisfied, user10's transaction criteria are checked. As shown in FIG. 11, when a match is made to the phrase “stock split”, a corresponding company name match is checked. As shown, any company name 1120 or company stock symbol 1130 listed as part of the message containing “stock split” will match 1040.

[0041] After a company match is determined, a check is made to determine if a previous purchase of shares of stock has occurred as a result of the same news information, but from a different message 1060. If so, a purchase does not occur. If, however, no purchase has been made based on this information, 1000 shares of XYZ corporation are purchased at market price 1070. After the purchase is performed, a monitor process will be started for tracking the 1000 purchased shares 1080. The scanner will then determine if there are more users with matching criteria 1050 and, if there are, process those users' match criteria as discussed. If not, the scanner will process another message.

[0042] FIG. 12 illustrates a purchase and monitoring process in accordance with one embodiment. Once a determination is made by a matching engine that a securities purchase is to be made, a process for purchasing and monitoring the securities is established. The process receives a buy order and a set of monitor criteria for the noted securities 1210. The process purchases the securities as indicated in the buy order 1220. The process then monitors the current price of the stock in addition to the elapsed time since the securities were purchased. If the stock price rises by a predetermined amount 1230, the process sells the securities 1260. Similarly, if a loss amount is specified, then the if the stock price drops by the loss amount 1240, the process sells the securities 1260 to minimize the loss. Finally, if a time limit is specified 1250, and the other criteria 1230 1240 have not yet been satisfied, the process sells the securities 1260.

[0043] Thus, a method of performing optimized matching operations on reduced matching data sets has been described. While the present invention has been described in terms of the above-illustrated embodiments, those skilled in the art will recognize that the invention is not limited to the embodiments described. The present invention can be practiced with modification and alteration within the spirit and scope of the appended claims. Thus, the description is to be regarded as illustrative instead of restrictive on the present invention.