Dataset intersection determination

• US 10,572,940 B2
• Filed: 02/26/2018
• Issued: 02/25/2020
• Est. Priority Date: 09/18/2013
• Status: Active Grant

• Current Assignee: Chicago Mercantile Exchange, Inc. (CME Group Incorporated)
• Original Assignee: Chicago Mercantile Exchange, Inc. (CME Group Incorporated)
• Inventors: Meacham, Paul, Doornebos, Jacques
• Primary Examiner(s): Ly, Anh
• Application Number:
  US15/905,253
• Publication Number:
  US 20180189881A1
• Time in Patent Office: 729 Days
• CPC Class Codes: G06F 12/0868 Data transfer between cache memory and other subsystems, e.g. storage devices or host systems
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 2212/1016 Performance improvement
• CPC Class Codes: G06F 2212/465 Structured object, e.g. database record
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange

Abstract

An item is determined to exist in a dataset by arranging the dataset into a plurality of subsets, each bounded by the minimum amount of memory that may be transferred between levels of memory in a memory configuration. The item and the subsets have attributes that allow for a determination of which subset the item would exist in if the item were in the dataset. A singular subset is transferred between levels of memory to determine whether the item exists in the transferred subset. If the item does not exist in the transferred subset, it is determined that the item does not exist in the dataset.

Claims

1. A computer implemented method for a financial electronic market to determine if a received order to buy or sell a financial instrument matches with one or more of a plurality of previously received but unsatisfied orders counter thereto, data indicative of which is stored in an order book database in a first arrangement, the order book database being stored in a first memory, each of the received order and the plurality of previously received but unsatisfied orders being characterized by an attribute, the method comprising:

receiving, by a processor coupled with the first memory and a second memory also coupled with the first memory, an order to buy or sell a financial instrument characterized by an attribute;

rearranging, by the processor, the data indicative of the plurality of previously received but unsatisfied orders stored in the order book database into a second arrangement different from the first arrangement, the second arrangement comprising a plurality of disjoint subsets of the previously received but unsatisfied orders, such that the amount of data of each of the plurality of disjoint subsets does not exceed a minimum amount of data which must be transferred between the first and second memories in a single transfer operation, wherein each of the plurality of disjoint subsets is characterized by a subset attribute determined therefore based on the attributes of the plurality of previously received but unsatisfied orders included therein;

identifying, by the processor, based on the attribute of the received order and the subset attributes of each of the plurality of subsets, a particular subset of the plurality of subsets which would include one or more previously received but unsatisfied orders counter to the received order if such previously received but unsatisfied orders counter to the received order were within the plurality of previously received but unsatisfied orders stored in the order book database;

causing, by the processor, a transfer of the particular subset from the first memory to the second memory; and

evaluating, by the processor subsequent to the transfer, the particular subset transferred to the second memory to determine whether one or more previously received but unsatisfied orders counter to the received order are included therein, one or more previously received but unsatisfied orders counter to the received order being determined to not exist in the order book database when the one or more previously received but unsatisfied orders counter to the received order are determined to not be included in the particular subset.

2. The method of claim 1, wherein the second arrangement comprises a hash table and an associated hash function, the identifying of the particular subset further comprises using the hash function to correlate the item attribute of the particular item with the subset attributes of each of the plurality of subsets.

3. The method of claim 1, wherein the attribute comprises a value representative of the order characterized thereby, and the identifying of the particular subset further comprises correlating the value with a subset attribute of each of the plurality of disjoint subsets.

4. The method of claim 1, wherein the fixed amount of data which may be transferred is determined by a minimum amount of data which can be moved from the first memory to the second memory with a single memory operation.

5. The method of claim 4, wherein the first memory is a computer main memory, the second memory is a cache memory, and the minimum amount of data is a cache line size.

6. The method of claim 1, wherein the attribute comprises price, side or a combination thereof.

7. The method of claim 6, wherein a previously received but unsatisfied order is determined to be counter to the received order when the attribute thereof is indicative of an opposite side of the received order and a price equal to or better than a price indicated by the attribute of the received order.

8. The method of claim 1, further comprising storing, by the processor, the received order in the order book database when the processor determines that one or more previously received but unsatisfied orders counter to the received order do not exist in the order book database.

9. The method of claim 1, wherein at least the identifying, causing, and evaluating are repeated for each subsequently received order.

10. The method of claim 1, wherein the rearranging into the second arrangement further comprises determining a fewest number of subsets required to store the plurality of items in the dataset based on the minimum amount of data, and bounding the total number of subsets in the second arrangement by the determined fewest number of subsets.

11. The method of claim 1, wherein evaluating the particular subset comprises a forward iteration method, a recursive method, a reverse order method, a sentinel method, or a combination thereof.

12. The method of claim 1, wherein evaluating further comprises the one or more previously received but unsatisfied orders counter to the received order being determined to exist in the order book database when the one or more previously received but unsatisfied orders counter to the received order are determined to be included in the particular subset.

13. A system for use by a financial electronic market to determine if a received order to buy or sell a financial instrument matches with one or more of a plurality of previously received but unsatisfied orders counter thereto, data indicative of which is stored in an order book database in a first arrangement, the order book database being stored in a first memory, each of the received order and the plurality of previously received but unsatisfied orders being characterized by an attribute, the system comprising:

a second memory coupled with the first memory and characterized by a fixed amount of data which may be transferred there between in a single memory operation;

computer executable program code stored in a third memory and executable by a processor to cause the processor to;

rearrange the data indicative of the plurality of previously received but unsatisfied orders stored in the order book database into a second arrangement different from the first arrangement, the second arrangement comprising a plurality of disjoint subsets of the previously received but unsatisfied orders, such that the amount of data of each of the plurality of disjoint subsets does not exceed a minimum amount of data which must be transferred between the first and second memories in a single transfer operation, wherein each of the plurality of disjoint subsets is characterized by a subset attribute determined therefore based on the attributes of the plurality of previously received but unsatisfied orders included therein;

identify based on the attribute of the received order and the subset attributes of each of the plurality of subsets, a particular subset of the plurality of subsets which would include one or more previously received but unsatisfied orders counter to the received order if such previously received but unsatisfied orders counter to the received order were within the plurality of previously received but unsatisfied orders stored in the order book database;

request the transfer of the particular subset from the first memory to the second memory; and

evaluate, subsequent to the transfer, the particular subset transferred to the second memory to determine whether one or more previously received but unsatisfied orders counter to the received order are included therein, one or more previously received but unsatisfied orders counter to the received order being determined to not exist in the order book database when the one or more previously received but unsatisfied orders counter to the received order are determined to not be included in the particular subset.

14. The system of claim 13, wherein the second arrangement comprises a hash table and an associated hash function, the identifying of a particular subset further comprises using the hash function to correlate the item attribute of the particular item with the subset attributes of each of the plurality of subsets.

15. The system of claim 13, wherein the attribute is a value representative of the order, and identifying the subset comprises correlating the value with a subset attribute value range.

16. The system of claim 13, wherein the first memory is a computer main memory, the second memory is a cache memory, and the fixed amount of data which can be transferred there between is a cache line size.

17. The system of claim 16, wherein the cache line size being selected from the group consisting of 32 bytes, 64 bytes, 128 bytes, and 256 bytes.

18. The system of claim 13, wherein the attribute comprises price, side or a combination thereof.

19. The system of claim 18, wherein a previously received but unsatisfied order is determined to be counter to the received order when the attribute thereof is indicative of an opposite side of the received order and a price equal to or better than a price indicated by the attribute of the received order.

20. The system of claim 13 wherein the computer executable program code stored in the third memory is further executable by the processor to cause the processor to store the received order in the order book database when the processor determines that one or more previously received but unsatisfied orders counter to the received order do not exist in the order book database.

21. The system of claim 13, wherein the processor is further configured to repeat at least the identifying, causing, and evaluating for each subsequently received order.

22. The system of claim 13, wherein the processor is further configured to determine a fewest number of subsets required to store the plurality of items in the dataset based on the fixed amount of data which may be transferred between the first and second memory, and bounding the total number of subsets in the second arrangement by the determined fewest number of subsets.

23. The system of claim 13, wherein the processor is further configured to evaluate the particular subset using a forward iteration method, a recursive method, a reverse order method, or a sentinel method.

24. A system for use by a financial electronic market to determine if a received order to buy or sell a financial instrument matches with one or more of a plurality of previously received but unsatisfied orders counter thereto, data indicative of which is stored in an order book database in a first arrangement, the order book database being stored in a first memory, each of the received order and the plurality of previously received but unsatisfied orders being characterized by an attribute, the system comprising:

a data arranger coupled with the first memory and a second memory, the first memory being coupled with the second memory and characterized by a fixed amount of data which may be transferred there between in a single memory operation, the data arranger configured to;

rearrange the data indicative of the plurality of previously received but unsatisfied orders stored in the order book database into a second arrangement different from the first arrangement, the second arrangement comprising a plurality of disjoint subsets of the previously received but unsatisfied orders, such that the amount of data of each of the plurality of disjoint subsets does not exceed a minimum amount of data which must be transferred between the first and second memories in a single transfer operation, wherein each of the plurality of disjoint subsets is characterized by a subset attribute determined therefore based on the attributes of the plurality of previously received but unsatisfied orders included therein;

the system further comprising;

a data locator, coupled with the first and second memories, configured to locate based on the attribute of the received order and the subset attributes of each of the plurality of subsets, a particular subset of the plurality of subsets which would include one or more previously received but unsatisfied orders counter to the received order if such previously received but unsatisfied orders counter to the received order were within the plurality of previously received but unsatisfied orders stored in the order book database; and

a data comparator, coupled with the first and second memories, configured to cause the transfer of the particular subset from the first memory to the second memory, and subsequently evaluate the particular subset transferred to the second memory to determine whether one or more previously received but unsatisfied orders counter to the received order are included therein, one or more previously received but unsatisfied orders counter to the received order being determined to not exist in the order book database when the one or more previously received but unsatisfied orders counter to the received order are determined to not be included in the particular subset.

25. The system of claim 24, wherein the first memory is a computer main memory, the second memory is a cache memory, and the fixed amount of data which may be transferred there between in a single memory operation is the maximum number of items which can be stored in a cache line.

26. A system for a financial electronic market to determine if a received order to buy or sell a financial instrument matches with one or more of a plurality of previously received but unsatisfied orders counter thereto, data indicative of which is stored in an order book database in a first arrangement, the order book database being stored in a first memory, each of the received order and the plurality of previously received but unsatisfied orders being characterized by an attribute, the system comprising:

means for receiving an order to buy or sell a financial instrument characterized by an attribute;

means for rearranging the data indicative of the plurality of previously received but unsatisfied orders stored in the order book database in a first arrangement into a second arrangement different from the first arrangement, the second arrangement comprising a plurality of disjoint subsets of the previously received but unsatisfied orders, such that the amount of data of each of the plurality of disjoint subsets does not exceed a minimum amount of data which must be transferred between the first and a second memory coupled therewith in a single transfer operation, wherein each of the plurality of disjoint subsets is characterized by a subset attribute determined therefore based on the attributes of the plurality of previously received but unsatisfied orders included therein;

means for identifying, based on the attribute of the received order and the subset attributes of each of the plurality of subsets, a particular subset of the plurality of subsets which would include one or more previously received but unsatisfied orders counter to the received order if such previously received but unsatisfied orders counter to the received order were within the plurality of previously received but unsatisfied orders stored in the order book database;

means for causing a transfer of the particular subset from the first memory to the second memory; and

means for evaluating, subsequent to the transfer, the particular subset in the second memory to determine whether one or more previously received but unsatisfied orders counter to the received order are included therein, one or more previously received but unsatisfied orders counter to the received order being determined to not exist in the order book database when the one or more previously received but unsatisfied orders counter to the received order are determined to not be included in the particular subset.

27. A computer implemented method searching archival market data for a historical value of at least one market parameter, the archival market data comprising a plurality of data records stored in a database in a first arrangement, wherein the at least one market parameter to be searched for and the plurality of data records are each characterized by an attribute, the method comprising:

receiving, by a processor coupled with a first memory and a second memory, the first memory being coupled with the second memory and characterized by a minimum amount of data which must be transferred there between in a single memory operation, the at least one market parameter to search for;

rearranging, by the processor, the plurality of data records into a second arrangement different from the first arrangement, the second arrangement comprising a plurality of disjoint subsets of the data records, such that the amount of data of each of the plurality of disjoint subsets does not exceed the minimum amount of data, wherein each of the plurality of disjoint subsets is characterized by a subset attribute determine therefor based the attributes of the plurality of data records included therein;

identifying, by the processor, based on the attribute of the at least one market parameter to search for and the subset attributes of each of the plurality of subsets, a particular subset of the plurality of subsets which would include a value of the market parameter to be searched for if a value of the market parameter to be searched for existed in the archival market data;

causing, by the processor, a transfer of the particular subset from the first memory to the second memory; and

evaluating, by the processor subsequent to the transfer, the particular subset in the second memory to determine whether a value of the market parameter to be searched for is included therein, a value of the market parameter to be searched for being determined to not exist in the archival market data when it is determined to not be included in the particular subset.