Methods and systems for caching data using behavioral event correlations

• US 8,032,714 B2
• Filed: 06/18/2008
• Issued: 10/04/2011
• Est. Priority Date: 09/28/2007
• Status: Active Grant

• Current Assignee: Aggregate Knowledge Incorporated (Neustar Incorporated)
• Original Assignee: Aggregate Knowledge Incorporated (Neustar Incorporated)
• Inventors: Musumeci, Gian-Paolo, Wehner, Kristopher C.
• Primary Examiner(s): NGUYEN, THAN VINH
• Application Number:
  US12/214,511
• Publication Number:
  US 20090089259A1
• Time in Patent Office: 1,203 Days
• Field of Search: None
• US Class Current: 711/137
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 2212/602 Details relating to cache prefetching
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862

Abstract

A method is disclosed including a client accessing a cache for a value of an object based on an object identification (ID), initiating a request to a cache loader if the cache does not include a value for the object, the cache loader performing a lookup in an object table for the object ID corresponding to the object, the cache loader retrieving a vector of execution context IDs, from an execution context table that correspond to the object IDs looked up in the object table and the cache loader performing an execution context lookup in an execution context table for every retrieved execution context ID in the vector to retrieve object IDs from an object vector.

Claims

1. A method comprising:

a client accessing a cache for a value of an object based on an object identification (ID);

initiating a request to a cache loader if the cache does not include a value for the object;

the cache loader performing a lookup in an object table for the object ID corresponding to the object;

the cache loader retrieving a vector of execution context IDs from an execution context table that correspond to the object IDs looked up in the object table; and

the cache loader performing an execution context lookup in an execution context table for every retrieved execution context ID in the vector to retrieve object IDs from an object vector.

2. The method of claim 1, further comprising returning the value to the cache client if the cache includes a value for the object.

3. The method of claim 2, wherein accessing an existing object asynchronously triggers a cache load request.

4. The method of claim 2, wherein accessing an existing object performs a synchronous load request.

5. The method of claim 1, further comprising:

the cache loader performing an object lookup; and

performing a store lookup for the object ID.

6. The method of claim 1, further comprising:

the cache loader performing a store lookup;

returning an object value from the store lookup; and

performing an object lookup.

7. The method of claim 1, further comprising the cache loader performing an object lookup in the object table for a single current object ID being requested.

8. The method of claim 1, further comprising the cache loader performing an object lookup in the object table for a predetermined number of object IDs requested by two or more cache clients.

9. The method of claim 1, further comprising the cache loader performing an object lookup in the object table for a predetermined number of object IDs requested by the cache client.

10. The method of claim 1, wherein the execution context vector includes a set of execution context IDs that uniquely identify the execution context accessing an existing object.

11. The method of claim 10, wherein the values in execution context IDs and the object IDs in the execution context table are sorted by time of an event for a scoring algorithm that uses time data.

12. The method of claim 11, further comprising the cache loader using the execution context vectors and the object vectors with a scoring algorithm to select highly scored object values to load in the cache.

13. The method of claim 12, wherein the execution context vectors and object vectors include other metadata about the objects and execution vectors which are used in the scoring algorithm.

14. The method of claim 11, wherein the scoring algorithm is one of Cosine, Dice or Jaccard.

15. A system comprising:

a client;

a cache to receive access requests from the client to retrieve a value of an object based on an object identification (ID);

an object table;

an execution context table; and

a cache loader to receive a request if the cache does not include a value for the object, perform a lookup in the object table for the object ID corresponding to the object, retrieve a vector of execution context IDs from the execution context table that correspond to the object IDs looked up in the object table and perform an execution context lookup in an execution context table for every retrieved execution context ID in the vector to retrieve object IDs from an object vector.

16. The system of claim 15, wherein the cache loader performs an object lookup prior to performing a store lookup for the object ID.

17. The system of claim 15, wherein the cache loader a store lookup and returns an object value from the store lookup prior to performing an object lookup.

18. The system of claim 15, wherein the cache loader performs an object lookup in the object table for a single current object ID being requested.

19. The system of claim 15, wherein the cache loader performs an object lookup in the object table for a predetermined number of object IDs requested by two or more cache clients.

20. The system of claim 15, wherein the cache loader performs an object lookup in the object table for a predetermined number of object IDs requested by the cache client.

21. An article of manufacture comprising a computer-readable medium having associated data, wherein the data, when accessed, results in a machine performing operations comprising:

a client accessing a cache for a value of an object based on an object identification (ID);

initiating a request to a cache loader if the cache does not include a value for the object;

the cache loader performing a lookup in an object table for the object ID corresponding to the object;

the cache loader retrieving a vector of execution context IDs from an execution context table that correspond to the object IDs looked up in the object table; and

the cache loader performing an execution context lookup in an execution context table for every retrieved execution context ID in the vector to retrieve object IDs from an object vector.

22. The article of manufacture of claim 21, wherein the data, when accessed, results in a machine performing further operations comprising returning the value to the cache client if the cache includes a value for the object.

23. The article of manufacture of claim 21, wherein accessing an existing object asynchronously triggers a cache load request.

24. The article of manufacture of claim 21, wherein accessing an existing object performs a synchronous load request.

25. The article of manufacture of claim 21, wherein the execution context vector includes a set of execution context IDs that uniquely identify the execution context accessing an existing object.

26. The article of manufacture of claim 25, wherein the values in execution context IDs and the object IDs in the execution context table are sorted by time of an event for a scoring algorithm that uses time data.