# US 9,519,614 B2 · Multi-layer multi-hit caching for long tail content

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 9,519,614 B2
- Document ID: US9519614B2
- Status: Granted
- Kind: B2
- Application number: 13/861,637
- Filed: 2013-04-12
- Published: 2013-08-29
- Granted: 2016-12-13
- Earliest claimed: 2012-01-10
- Assignees: Verizon Digital Media Services Inc.
- Applicants: Verizon Digital Media Services Inc.
- Inventors: Amir Khakpour; Robert J. Peters
- Web page: https://patentgrep.com/patent/US9519614B2

## CPC

- H04N 21/2408: {Monitoring of the upstream path of the transmission network, e.g. client requests (monitoring data switching networks utilization H04L43/0876; scheduling or organising the servicing of application requests H04L67/60)}
- G06F 15/167: using a common memory, e.g. mailbox
- G06F 16/9535: Search customisation based on user profiles and personalisation
- G06F 16/9574: {of access to content, e.g. by caching}
- H04L 67/568: Storing data temporarily at an intermediate stage, e.g. caching
- H04N 21/23106: {involving caching operations (prefetching while addressing of a memory level in which the access to the desired data or data block requires associative addressing means within memory systems or architectures G06F12/0862; caching at an intermediate stage in a data network H04L67/568)}
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

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

## Claims

### Claim 1

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.

### Claim 2 (depends on 1)

The computer-implemented method of claim 1 further comprising retrieving to the caching server, the particular content from an origin server and serving the particular content from the caching server to a requesting end user in response to the sum of the first count and the second count equaling N.

### Claim 3 (depends on 1)

The computer-implemented method of claim 1 further comprising serving the particular content without caching the particular content at the caching server in response to the sum of the first count and the second count equaling a total value less than N.

### Claim 4 (depends on 1)

The computer-implemented method of claim 1, wherein the first array is a first counting bloom filter and the second array is a second counting bloom filter and wherein each index of the plurality of indices for each array comprises multiple bits for counting up to at least N−1.

### Claim 5 (depends on 1)

The computer-implemented method of claim 1 further comprising overwriting the first array by copying values from the plurality of indices of the second array to the plurality of indices of the first array at expiration of the second interval.

### Claim 6 (depends on 5)

The computer-implemented method of claim 5 further comprising resetting values for the plurality of indices of the second array at the expiration of the second interval.

### Claim 7 (depends on 1)

The computer-implemented method of claim 1 further comprising resetting values of the second array and preserving values of the first array at expiration of the second interval.

### Claim 8 (depends on 7)

The computer-implemented method of claim 7 further comprising switching roles of the first array and second array by using the second array to track requests received during a third interval immediately following the second interval.

### Claim 9

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.

### Claim 10 (depends on 9)

The caching server of claim 9, wherein the first array is a first counting bloom filter and the second array is a second counting bloom filter, each counting bloom filter comprising at least a plurality of indices with different sets of the plurality of indices uniquely identifying different content.

### Claim 11 (depends on 9)

The caching server of claim 9, wherein the first array comprises a first plurality of multi-bit indices, wherein the first array tracks content request counts by incrementing different sets of the first plurality of multi-bit indices corresponding to different sets of indices that uniquely identify different instances of content that are requested during the current interval, wherein the second array comprises a second plurality of multi-bit indices, and wherein the second array tracks content request counts by incrementing different sets of the second plurality of multi-bit indices corresponding to different sets of indices that uniquely identify different instances of content that are requested during the previous interval.

### Claim 12 (depends on 11)

The caching server of claim 11 further comprising a processor (i) determining a request count for particular content during the current interval by identifying a minimum value for each index of the first plurality of indices that corresponds to an index of the particular set of indices uniquely identifying the particular content and (ii) determining a request count for the particular content during the previous interval by identifying a minimum value for each index of the second plurality of indices that corresponds to an index of the particular set of indices uniquely identifying the particular content.

### Claim 13 (depends on 11)

The caching server of claim 11 further comprising a processor determining M requests for particular content when a minimum value for a set of indices from the first plurality of indices that correspond to a particular set of indices uniquely identifying the particular content summed with a minimum value for a set of indices from the second plurality of indices that correspond to the particular set of indices uniquely identifying the particular content equals at least M−1.

### Claim 14 (depends on 9)

The caching server of claim 9 further comprising a networked interface forwarding content to a requesting end user in response to a request from the end user, wherein the networked interface (i) forwards the content from the first non-transitory storage medium when the content was previously requested N times during the current interval and the previous interval, (ii) forwards the content from the second non-transitory storage medium when the content was previously requested M times during the current interval and the previous interval, (iii) forwards the content from an origin server when the content was previously requested less than M times.

### Claim 15 (depends on 9)

The caching server of claim 9 further comprising a routine overwriting request counts of the second array with the request counts of the first array and erasing the request counts of the first array when restarting the current interval at expiration of the designated time span.

### Claim 16 (depends on 9)

The caching server of claim 9 further comprising a mapping table identifying the first non-transitory storage medium as caching content that is requested more than N times and identifying the second non-transitory storage medium as caching content that is requested between M and N−1 times.