Dataset intersection determination

• US 9,501,796 B2
• Filed: 09/18/2013
• Issued: 11/22/2016
• 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:
  US14/030,377
• Publication Number:
  US 20150081622A1
• Time in Patent Office: 1,161 Days
• Field of Search: 707/752, 707/607
• US Class Current: 1/1
• 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, each of the particular item and the plurality of items being characterized by an item attribute, the plurality of items being characterized by a first arrangement and stored in a first memory coupled with a second memory, the first and second memories being characterized by a minimum number of items which may be transferred from the first memory to the second memory by a single transfer operation therebetween, the method comprising:

rearranging, by a processor coupled with the first and second memories, the plurality of items of the dataset into a second arrangement different from the first arrangement, the second arrangement comprising a plurality of non-overlapping subsets of the plurality of items such that a number of items of the plurality of items included in each non-overlapping subset does not exceed the minimum number of items, wherein each of the plurality of non-overlapping subsets is characterized by a subset attribute correlated with the item attributes of the items of the plurality 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 subset of the plurality of subsets which would include the particular item if the particular item was one of the plurality of items;

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

evaluating, by the processor, the identified subset in the second memory to determine whether the particular item is included therein, the particular item being determined to not exist in the plurality of items when the particular item is determined to not be included in the identified subset in the second memory.

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

3. The method of claim 1, 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.

4. The method of claim 1, wherein the first memory is a computer main memory, the second memory is a cache memory, and the minimum size of data which can be moved from the first memory to the second memory is a cache line size.

5. The method of claim 1, wherein the minimum number of items which may be transferred is determined by a minimum amount of data which can be moved from the first memory to the second memory.

6. The method of claim 1, wherein the plurality of items of the dataset comprise data indicative of orders to buy or sell financial instruments in a financial market.

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 comprises determining a fewest number of subsets required to store the plurality of items in the dataset based on the minimum number of items which may be transferred in a single transfer operation, 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 identified subset comprises a forward iteration method, a recursive method, a reverse order method, a sentinel method, or a combination thereof.

10. A system for determining inclusion of a particular item in a dataset comprising a plurality of items, each of the particular item and the plurality of items being characterized by an item attribute, the plurality of items being characterized by a first arrangement, the plurality of items being stored in a first memory having a first size and a first access latency, the first memory being coupled with a second memory having a second size smaller than the first size and a second access latency smaller than the first access latency, the second memory further being characterized by a minimum amount of data which can be moved from the first memory to the second memory, the system comprising:

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 the second arrangement different from the first arrangement, a second arrangement comprising a plurality of non-overlapping subsets of the plurality of items such that the amount of data of each non-overlapping subset does not exceed the minimum amount of data which can be moved from the first memory to the second memory, wherein each of the plurality of non-overlapping subsets is characterized by a subset attribute based on the item attributes of the items of the plurality 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 subset of the plurality of subsets which would include the particular item if the particular item was one of the plurality of items,

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

evaluate the identified subset in the second memory to determine whether the particular item is included therein, the particular item being determined to not exist in the plurality of items when the particular item is determined to not be included in the identified subset in the second memory.

11. The system of claim 10, wherein the second arrangement comprises a hash table and an associated hash function, and identifying a subset comprises using the hash function to correlate the particular item attribute with the subset attribute.

12. The system of claim 10, 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.

13. The system of claim 10, wherein the first memory is a computer main memory, the second memory is a cache memory, and the minimum size of data which can be moved from the first memory to the second memory is a cache line size.

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

15. The system of claim 10, wherein the plurality of items of the dataset comprise data indicative of orders to buy or sell financial instruments in a financial market.

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

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

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

19. A system for determining inclusion of a particular item in a dataset comprising a plurality of items, each of the particular item and the plurality of items being characterized by an item attribute, the plurality of items being characterized by a first arrangement and stored in a first memory coupled with a second memory, the first and second memories being characterized by a minimum number of items which may be transferred from the first memory to the second memory by a single transfer operation therebetween, the system comprising:

a data arranger, coupled with the first and second memories, configured to rearrange the plurality of items of the data set into a second arrangement different from the first arrangement, the second arrangement comprising a plurality of non-overlapping subsets of the plurality of items such that a number of items of the plurality of items included in each non-overlapping subset does not exceed the minimum number of items, wherein each of the plurality of non-overlapping subsets is characterized by a subset attribute based on the item attributes of the items of the plurality items included therein;

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 each of the plurality of subsets, a subset of the plurality of subsets which would include the particular item if the particular item was one of the plurality of items; and

a data comparator, coupled with the first and second memories, configured to cause the transfer of the identified subset from the first memory to the second memory, and evaluate the identified subset in the second memory to determine whether the particular item is included therein, the particular item being determined to not exist in the plurality of items when the particular item is determined to not be included in the identified subset in the second memory.

20. The system of claim 19, wherein the first memory is a computer main memory, the second memory is a cache memory, the minimum size of data which can be moved from the first memory to the second memory is a cache line size, and the minimum number of items which may be transferred is the maximum number of items which can be stored in the cache line size.

21. A system for determining inclusion of a particular item in a dataset comprising a plurality of items, each of the particular item and the plurality of items being characterized by an item attribute, the plurality of items being characterized by a first arrangement and stored in a first memory coupled with a second memory, the first and second memories being characterized by a minimum number of items which may be transferred from the first memory to the second memory by a single transfer operation therebetween, 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 non-overlapping subsets of the plurality of items such that a number of items of the plurality of items included in each non-overlapping subset does not exceed the minimum number of items, wherein each of the plurality of non-overlapping 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 subset of the plurality of subsets which would include the particular item if the particular item was one of the plurality of items;

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

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