NON-EXACT CACHE MATCHING

• US 20100205213A1
• Filed: 02/12/2009
• Published: 08/12/2010
• Est. Priority Date: 02/12/2009
• Status: Abandoned Application

• Current Assignee: Oath Inc. (Verizon Communications Inc.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Chierichetti, Flavio, Ravikumar, Shanmugasundaram, Pandey, Sandeep, Josifovski, Vanja, Broder, Andrei, Vassilvitskii, Serguei
• Application Number:
  US12/370,306
• Publication Number:
  US 20100205213A1
• Time in Patent Office: Days
• US Class Current: 707/780
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 30/0251 Targeted advertisements

Abstract

The subject matter disclosed herein relates to returning cached object results based at least in part on a non-exact comparison with a query key.

Claims

1. A method, comprising:

with a computing platform;

determining a similarity of a query key associated with an object query to a representative cache key associated with one or more cached object results in an object cache, wherein said determination of similarity comprises a non-exact comparison; and

returning one or more of said cached object results based at least in part on said non-exact comparison.

2. The method of claim 1, wherein said computing platform comprises a special purpose computing platform.

3. The method of claim 1, wherein said returning said one or more of said cached object results comprises returning said one or more of said cached object results from said computing platform to a user device for presentation of one or more ads to a user.

4. The method of claim 1, wherein said non-exact comparison of said similarity is based at least in part on determining if said similarity of said query key falls within a given tolerance as compared to said representative cache key.

5. The method of claim 1, further comprising:

replacing said representative cache key with said query key based at least in part on determining that similarity between said query cache key and cached object results associated with said representative cache key fall within a given tolerance.

6. The method of claim 1, further comprising:

wherein said object cache comprises a ball-like organization comprising two or more balls, wherein individual balls of said object cache are associated with respective representative cache keys;

identifying a closest matching ball based at least in part on a comparison of said query key to said representative cache keys, wherein said non-exact comparison of said similarity is based at least in part on a comparison of said query key to said representative cache keys;

tentatively updating a set of one or more keys with said query key, wherein said set of keys comprises said representative cache key and past cache keys, wherein said set of keys is associated with said closest matching ball;

determine a prospective key from said updated set of keys based at least in part on a maximum sum of similarities between individual keys from said updated set of keys and cached object results associated with said closest matching ball; and

replacing said representative cache key with said prospective key based at least in part on determining that similarity between said prospective key and cached object results associated with said closest matching ball fall within a given tolerance.

7. The method of claim 1, further comprising:

wherein said object cache comprises a ball-like organization comprising two or more balls, wherein individual balls of said object cache are associated with respective representative cache keys; and

forming a new ball associated with said query key based at least in part on determining that similarity between said query key and cached object results associated with said representative cache key fall outside a given tolerance.

8. The method of claim 1, further comprising:

wherein said object cache comprises a ball-like organization comprising two or more balls, wherein individual balls of said object cache are associated with respective representative cache keys;

identifying a closest matching ball based at least in part on a comparison of said query key to said representative cache keys, wherein said non-exact comparison is based at least in part on a comparison of said query key to said representative cache keys;

tentatively updating a set of one or more keys with said query key, wherein said set of keys comprises said representative cache key and past cache keys, wherein said set of keys is associated with said closest matching ball;

determine a prospective key from said updated set of keys based at least in part on a maximum sum of similarities between individual keys from said updated set of keys and cached object results associated with said closest matching ball; and

deleting said prospective key from said updated set of keys and form a new ball associated with said prospective key based at least in part on determining that similarity between said prospective key and cached object results associated with said closest matching ball fall outside a given tolerance.

9. The method of claim 1,

determining a quantification of a utility of said object query based at least in part on a frequency of said object query;

and

wherein said returning said one or more of said cached object results comprises returning said one or more of said cached object results based at least in part said quantification of utility of said object query.

10. The method of claim 1, further comprising:

determining a quantification of a utility of said object query based at least in part on a frequency of said object query; and

declaring a cache miss based at least in part said quantification of utility of said object query.

11. The method of claim 1, further comprising:

determining a quantification of a utility of said object query based at least in part on a frequency of said object query;

declaring a cache miss based at least in part said quantification of utility of said object query; and

incorporating a new object result into said object cache based at least in part on said declared cache miss.

12. The method of claim 1, wherein said non-exact comparison is based at least in part on locality sensitive hashing.

13. An article comprising:

a storage medium comprising machine-readable instructions stored thereon, which, if executed by one or more processing units, operatively enable a computing platform to;

determine a similarity of a query key associated with an object query to a representative cache key associated with one or more cached object results in an object cache, wherein said determination of similarity comprises a non-exact comparison; and

return one or more of said cached object results based at least in part on said non-exact comparison.

14. The article of claim 13, wherein said non-exact comparison is based at least in part on a determination if said similarity of said query key falls within a given tolerance as compared to said representative cache key.

15. The article of claim 13,

wherein said object cache comprises a ball-like organization comprising two or more balls, wherein individual balls of said object cache are associated with respective representative cache keys;

and

wherein said machine-readable instructions, if executed by the one or more processing units, operatively enable the computing platform to;

form a new ball associated with said query key based at least in part on determining that similarity between said query key and cached object results associated with said representative cache key fall outside a given tolerance.

16. The article of claim 13, wherein said machine-readable instructions, if executed by the one or more processing units, operatively enable the computing platform to:

determine a quantification of a utility of said object query based at least in part on a frequency of said object query;

declare a cache miss based at least in part said quantification of utility of said object query; and

incorporate a new object result into said object cache based at least in part on said declared cache miss.

17. An apparatus comprising:

a computing platform, said computing platform being operatively enabled to;

determine a similarity of a query key associated with an object query to a representative cache key associated with one or more cached object results in an object cache, wherein said determination of similarity comprises a non-exact comparison; and

return one or more of said cached object results based at least in part on a non-exact comparison.

18. The apparatus of claim 17, wherein said non-exact comparison is based at least in part on a determination if said similarity of said query key falls within a given tolerance as compared to said representative cache key.

19. The apparatus of claim 17,

wherein said object cache comprises a ball-like organization comprising two or more balls, wherein individual balls of said object cache are associated with respective representative cache keys;

and

wherein said computing platform is further operatively enabled to;

form a new ball associated with said query key based at least in part on determining that similarity between said query key and cached object results associated with said representative cache key fall outside a given tolerance.

20. The apparatus of claim 17, wherein said computing platform is further operatively enabled to:

determine a quantification of a utility of said object query based at least in part on a frequency of said object query;

declare a cache miss based at least in part said quantification of utility of said object query; and

incorporate a new object result into said object cache based at least in part on said declared cache miss.