Dataset intersection determination

• US 9,940,671 B2
• Filed: 10/21/2016
• Issued: 04/10/2018
• 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/331,009
• Publication Number:
  US 20170039651A1
• Time in Patent Office: 536 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 of determining inclusion of a particular item in a dataset comprising a plurality of items in a first arrangement, the particular item and each of the plurality of items being characterized by an item attribute, the method comprising:

rearranging, by a processor coupled with a first and a second memory which are coupled together and characterized by a fixed amount of data which may be transferred there between in a single memory operation, the plurality of items of the dataset into a second arrangement different from the first arrangement and comprising a plurality of disjoint subsets of the plurality of items, such that that the amount of data of each disjoint subset does not exceed the fixed amount of data, wherein each of the plurality of disjoint subsets is characterized by a subset attribute correlated with the item attributes of the plurality of items included therein;

identifying, by the processor, based on the item attribute of the particular item and the subset attributes of each of the plurality of subsets, a particular subset of the plurality of subsets which would include the particular item if the particular item was one of the plurality of items of the dataset;

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 the particular item is included therein, the particular item being determined to not exist in the dataset when the particular item is 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 item attribute comprises a value representative of the item 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 particular item comprises data indicative of an order to buy or sell a financial instrument in a financial market that is counter to an order received by an electronic trading system and the plurality of items of the dataset comprise data indicative of previously received but not yet satisfied orders to buy or sell financial instruments in the financial market, the inclusion of particular item in the dataset is indicative of a match of the received order with one of the previously received but unsatisfied orders.

7. The method of claim 1, the identifying, causing, and evaluating are repeated for each of a plurality of items in a target dataset, wherein the method further comprises generating an intersection dataset of all items from the target dataset that are determined to exist in the dataset.

8. 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 fixed amount of data, and bounding the total number of subsets in the second arrangement by the determined fewest number of subsets.

9. 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.

10. The method of claim 1, wherein:

the particular item and the plurality of items each have corresponding item content,

the item attribute is a binary value representative of the item content, and

identifying the subset further comprises correlating the value with a subset attribute value range.

11. The method of claim 10, wherein the subset attribute value range is defined by a binary masking function.

12. The method of claim 1, wherein the dataset represents archival market data, and the plurality of items of the dataset represent historical values of at least one market parameter of one or more products traded on an exchange.

13. The method of claim 12, wherein the particular item belongs to a search dataset of a plurality of items that may be included in the archival market data.

14. The method of claim 1, wherein evaluating further comprises the particular item being determined to exist in the dataset when the particular item is determined to be included in the particular subset.

15. A system for determining inclusion of a particular item in a dataset comprising a plurality of items in a first arrangement, the particular item and each of the plurality of items being characterized by an item attribute, the system comprising:

a first memory coupled with a second 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 plurality of items of the dataset into a second arrangement different from the first arrangement and comprising a plurality of disjoint subsets of the plurality of items such that the amount of data of each disjoint subset does not exceed the fixed amount of data, wherein each of the plurality of disjoint subsets is characterized by a subset attribute based on the item attributes of the plurality of items included therein;

identify based on the item attribute of the particular item and the subset attributes of each of the plurality of subsets, a particular subset of the plurality of subsets which would include the particular item if the particular item was one of the plurality of items of the dataset;

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

evaluate, subsequent to the transfer, the particular subset in the second memory to determine whether the particular item is included therein, the particular item being determined to not exist in the dataset when the particular item is determined to not be included in the particular subset.

16. The system of claim 15, 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.

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

18. The system of claim 15, 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.

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

20. The system of claim 15, wherein the particular item comprises data indicative of an order to buy or sell a financial instrument in a financial market that is counter to an order received by an electronic trading system and the plurality of items of the dataset comprise data indicative of previously received but not yet satisfied orders to buy or sell financial instruments in the financial market, the inclusion of particular item in the dataset is indicative of a match of the received order with one of the previously received but unsatisfied orders.

21. The system of claim 15, wherein the processor is further configured to repeat the identifying, causing, and evaluating for each of a plurality of items in a target dataset, wherein the computer executable program code is executable by a processor to further cause the processor to generate an intersection dataset of all items from the target dataset that are determined to exist in the dataset.

22. The system of claim 15, 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 15, 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 determining inclusion of a particular item in a dataset comprising a plurality of items in a first arrangement, the particular item and each of the plurality of items being characterized by an item attribute, the system comprising:

a data arranger coupled with a 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 plurality of items of the data set into a second arrangement different from the first arrangement and comprising a plurality of disjoint subsets of the plurality of items, such that the amount of data of each disjoint subset does not exceed the fixed amount of data, wherein each of the plurality of disjoint subsets contains data only from the dataset and is characterized by a subset attribute based on the item attributes of the items of the plurality items included therein;

the system further comprising;

a data locator, coupled with the first and second memories, configured to locate based on the item attribute of the particular item and the subset attributes of the plurality of subsets, a particular subset of the plurality of subsets which would include the particular item if the particular item was one of the plurality of items of the dataset; 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 in the second memory to determine whether the particular item is included therein, the particular item being determined to not exist in the dataset when the particular item is 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 determining inclusion of a particular item in a dataset comprising a plurality of items in a first arrangement, the particular item and each of the plurality of items being characterized by an item attribute, the plurality of items being stored in a first memory that is coupled with a second memory, the first and second memories being characterized by a fixed amount of data which may be transferred there between in a single transfer operation, the system comprising:

means for rearranging the plurality of items of the dataset into a second arrangement different from the first arrangement, the second arrangement comprising a plurality of disjoint subsets of the plurality of items such that the amount of data of each disjoint subset does not exceed the fixed amount of data, wherein each of the plurality of disjoint subsets is characterized by a subset attribute correlated with the item attributes of the items of the plurality items included therein;

means for identifying based on the item attribute of the particular item and the subset attributes of each of the plurality of subsets, a particular subset of the plurality of subsets which would include the particular item if the particular item was one of the plurality of items of the dataset;

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

means for evaluating the particular subset in the second memory to determine whether the particular item is included therein, the particular item being determined to not exist in the dataset when the particular item is determined to not be included in the particular subset.

27. A computer implemented method of matching an incoming order to buy or sell a financial instrument to a resting order stored in an order book comprising a plurality of resting orders in a first arrangement, wherein the incoming order and the plurality of resting orders are each characterized by an order 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 fixed amount of data which may be transferred there between in a single memory operation, the incoming order;

rearranging, by the processor, the plurality of resting orders of the order book into a second arrangement different from the first arrangement, the second arrangement comprising a plurality of disjoint subsets of the resting orders, such that the amount of data of each of the plurality of disjoint subsets does not exceed the fixed amount of data, wherein each of the plurality of disjoint subsets is characterized by a subset attribute correlated with the order attributes of the plurality of resting orders included therein;

identifying, by the processor, based on the order attribute of the incoming order and the subset attributes of each of the plurality of subsets, a particular subset of the plurality of subsets which would include a suitable order counter to the incoming order if a suitable counter order was one of the plurality of resting orders in the order book;

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 suitable order counter to the incoming order is included therein, a suitable counter order being determined to not exist in the order book when it is determined to not be included in the particular subset.