DATA TYPING WITH PROBABILISTIC MAPS HAVING IMBALANCED ERROR COSTS
First Claim
Patent Images
1. A method of retrieving a type value associated with a queried data key comprising:
- receiving, via a computer network, a plurality of data keys and type values and query frequencies associated therewith;
creating a tranche data structure within a computer memory, the tranche data structure comprising a plurality of memory tranches;
storing a different set of data keys in each of the memory tranches based on query frequencies associated with the data keys, each tranche having a size also based on the query frequencies and wherein at least two tranches have different sizes;
determining, using a computer processor, a memory-size cost of each tranche based on the query frequencies associated with the data keys contained in each grouping;
creating and storing, in a computer memory, a probabilistic data structure for a memory tranche that maps a data key to a type value with a given probability of accuracy, wherein the probabilistic data structure is created based at least on (i) the memory-size cost, (ii) a number of represented data keys, and (iii) an error probability, and wherein at least two tranches have different memory-size costs; and
querying the probabilistic data structure to determine a type value associated with a data key of unknown type value.
1 Assignment
0 Petitions
Accused Products
Abstract
A plurality of data keys are associated with a plurality of type values; query frequencies of the data keys are known. A computer memory is divided into a plurality of tranches, each tranche including a probabilistic or non-probabilistic data structure. The data keys are stored in the tranches in accordance with their query frequencies such that, e.g., frequently queried data keys are stored in data structures having higher accuracy and infrequently queried keys are stored in data structure having less accuracy (and consequently require less memory space).
-
Citations
12 Claims
-
1. A method of retrieving a type value associated with a queried data key comprising:
-
receiving, via a computer network, a plurality of data keys and type values and query frequencies associated therewith; creating a tranche data structure within a computer memory, the tranche data structure comprising a plurality of memory tranches; storing a different set of data keys in each of the memory tranches based on query frequencies associated with the data keys, each tranche having a size also based on the query frequencies and wherein at least two tranches have different sizes; determining, using a computer processor, a memory-size cost of each tranche based on the query frequencies associated with the data keys contained in each grouping; creating and storing, in a computer memory, a probabilistic data structure for a memory tranche that maps a data key to a type value with a given probability of accuracy, wherein the probabilistic data structure is created based at least on (i) the memory-size cost, (ii) a number of represented data keys, and (iii) an error probability, and wherein at least two tranches have different memory-size costs; and querying the probabilistic data structure to determine a type value associated with a data key of unknown type value. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A system for retrieving a type value associated with a queried data key comprising:
-
a computer memory for storing a plurality of data keys and type values and query frequencies associated therewith; a computer processor configured to execute computer instructions for; (i) creating a tranche data structure within the computer memory, the tranche data structure comprising a plurality of memory tranches; (ii) storing a different set of data keys in each of the memory tranches based on query frequencies associated with the data keys, each tranche having a size also based on the query frequencies and wherein at least two tranches have different sizes; (iii) determining, using a computer processor, a memory-size cost of each tranche based on the query frequencies associated with the data keys contained in each grouping; (iv) creating and storing, in a computer memory, a probabilistic data structure for each tranche that maps a data key to a type value with a given probability of accuracy, wherein the probabilistic data structure is created based at least on (i) the memory-size cost, (ii) a number of represented data keys, and (iii) an error probability, and wherein at least two tranches have different memory-size costs; and (vi) querying the probabilistic data structure to determine a type value associated with a data key of unknown type value. - View Dependent Claims (8, 9, 10, 11, 12)
-
Specification