Efficient Trade Matching Algorithms
Problem
A brokerage firm places a large derivatives order for one of their clients. That order is filled in the order book of the brokerage firm. At some later time, the client sends in a file with their trade reconciliation history. The time to match the order book data to the client file was increasing exponentially as the size of the client file increased.
Analysis
The initial assumption was that there was inefficient code that was making several database calls causing an increase in processing time. Through analysis of the code, it was determined that there was not an excess of database calls, but rather the matching algorithm that was employed was not efficient.
Solution
PSC consultants reviewed the system and created a way to reliably isolate the code in question. Further analysis, coupled with a deep understanding of computer science principles, recognized that this problem is best solved by employing a master-detail matching algorithm. By ordering both the client and the order book data using the same key, both lists can be traversed simultaneously. When a match is found, both lists are incremented and the match is processed. When the lists do not match, the list with the lower key value is incremented. The new algorithm resulted in a significant performance improvement over the old. A file that used to take over an hour was processed in about 90 seconds.