Data typing with probabilistic maps having imbalanced error costs

• US 9,760,836 B2
• Filed: 09/15/2014
• Issued: 09/12/2017
• Est. Priority Date: 09/16/2013
• Status: Active Grant

• Current Assignee: Guavus, Inc. (Thales SA)
• Original Assignee: Guavus, Inc. (Thales SA)
• Inventors: Ketkar, Nikhil Shirish, Bharti, Vineet, Mishra, Gaurav, Mirandette, Olivier
• Primary Examiner(s): OBISESAN, AUGUSTINE KUNLE
• Application Number:
  US14/486,212
• Publication Number:
  US 20150081710A1
• Time in Patent Office: 1,093 Days
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks

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

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.

2. The method of claim 1, wherein the mapping of the data key to the type value is performed in an order based on the query frequencies associated with the data keys in each probabilistic data structure.

3. The method of claim 1, further comprising iterating the mapping over the tranches.

4. The method of claim 3, wherein the mapping is performed in an order based on the queried frequencies of the data keys contained within each tranche.

5. The method of claim 4, wherein the mapping is performed in an ascending order of the queried frequencies of the data keys contained within each tranche.

6. The method of claim 1, further comprising caching the data keys and the associated type values in a least-recently-used cache.

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.

8. The system of claim 7, wherein the processor is configured to perform the mapping in an order based on the queried frequencies associated with the data keys in each probabilistic data structure.

9. The system of claim 7, wherein the processor is further configured to iterate the mapping over the tranches.

10. The system of claim 9, wherein the processor is configured to perform the mapping in an order based on the queried frequencies of the data keys contained within each tranche.

11. The system of claim 10, wherein the processor is configured to perform the mapping in an ascending order of the queried frequencies of the data keys contained within each tranche.

12. The system of claim 7, further comprising a cache memory for caching the data keys and the associated type values.