US 9,519,614 B2Granted

Multi-layer multi-hit caching for long tail content

AssigneeVerizon Digital Media Services Inc.

InventorsAmir Khakpour, Robert J. Peters

Life of this patent

Estimating the term…

Loading patent…

Abstract

Some embodiments provide an optimized multi-hit caching technique that minimizes the performance impact associated with caching of long-tail content while retaining much of the efficiency and minimal overhead associated with first hit caching in determining when to cache content. The optimized multi-hit caching utilizes a modified bloom filter implementation that performs flushing and state rolling to delete indices representing stale content from a bit array used to track hit counts without affecting identification of other content that may be represented with indices overlapping with those representing the stale content. Specifically, a copy of the bit array is stored prior to flushing the bit array so as to avoid losing track of previously requested and cached content when flushing the bit arrays and the flushing is performed to remove the bit indices representing stale content from the bit array and to minimize the possibility of a false positive.

Claims16

Dependent claims

A computer-implemented method with which a caching server performs N hit caching of content, wherein N is an integer value greater than one, the computer-implemented method comprising:

configuring the caching server with a first array and a second array, each array comprising a plurality of indices;
for each of a plurality of requests requesting content from the caching server, identifying from the plurality of indices, a different set of indices that uniquely identifies each unique item of content;
incrementing indices of the first array that correspond to different sets of indices identifying content requested from the caching server during a first interval;
incrementing indices of the second array that correspond to different sets of indices identifying content requested from the caching server during a second interval immediately following the first interval;
and
obtaining at least a first count from a particular set of indices of the first array and at least a second count from the particular set of indices of the second array in response to a request for particular content, wherein the particular content is uniquely identified by the particular set of indices, and wherein the first count and the second count are different integer values greater than zero;
caching the particular content in a non-transitory storage medium of the caching server in response to a sum of the first count and the second count being at least N;
and
serving the particular content to the user.

6 more elements

A caching server comprising:

memory configured with (i) a first array tracking request counts for content requested during a current interval having a designated time span and (ii) a second array tracking request counts for content requested during a previous interval immediately preceding the current interval;
wherein the memory is configured to, for each of a plurality of requests requesting content from the caching server, identify from a plurality of indices in the first and second arrays, a different set of indices that uniquely identifies each unique item of content;
a first non-transitory storage medium caching content requested at least N times based on a sum total of request counts tracked to the first array during the current interval and request counts tracked to the second array during the previous interval;
and
a second non-transitory storage medium caching content requested at least M times based on a sum total of request counts tracked to the first array during the current interval and request counts tracked to the second array during the previous interval, wherein N is an integer value that is greater than M and the second non-transitory storage medium is slower than the first non-transitory storage medium.

2 more elements

Dependencies are inferred from the claim text.

Facts

Application: 13/861,637Filed 12 Apr 2013 · continuation in part
Priority: 10 Jan 2012
Published: US 2013/0179529 A129 Aug 2013
Granted: 13 Dec 2016
Term ends: Not estimatedThe source records don’t support an estimate.

Classification9 codes

H04N 21/2408
Monitoring of processes or resources, e.g. monitoring of server load, available bandwidth, upstream requests: monitoring of the upstream path of…
G06F 15/167
Interprocessor communication: using a common memory, e.g. mailbox
G06F 16/9535
Querying, e.g. by the use of web search engines: search customisation based on user profiles and personalisation
G06F 16/9574
Browsing optimisation, e.g. caching or content distillation: of access to content, e.g. by caching

Family

Application13/347,615Parent of this continuation · filed 10 Jan 2012
Application13/720,859Parent of this continuation-in-part · filed 19 Dec 2012
US 8,370,460 B1Parent of this continuation · filed 5 Feb 2013
US 2013/0227051 A1Pre-grant publication · published 29 Aug 2013
US 8,639,780 B2Parent of this continuation-in-part
Application13/720,859Parent of this continuation
US 2013/0179529 A1Published application
US 9,519,614 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key