Dataset intersection determination
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
27 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
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. - View Dependent Claims (16, 17, 18, 19, 20, 21, 22, 23)
-
-
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. - View Dependent Claims (25)
-
-
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.
-
Specification