Estimating unique impressions in an online video distribution system

Patent metadata

Field	Value
Publication number	US-9070139-B2
Application number	US-201213622984-A
Country	US
Kind code	B2
Filing date	Sep 19, 2012
Priority date	Sep 19, 2012
Publication date	Jun 30, 2015
Grant date	Jun 30, 2015

Abstract

Estimating a number of unique ad impressions in a streaming video system includes defining parameters of an ad campaign and a desired number of ad impressions for the campaign. A computer system determines a discrete probability distribution of video advertising segments per unit time per client device in a population of video advertising segments streamed to a plurality of client devices, based on historical data. The system randomly samples the probability distribution without replacement, based on the defined number of desired ad impressions. An enhanced binary search algorithm may be used for the sampling. Each sample of the probability distribution identifies a number of ads streamed to a different client device in the probability distribution. The system determines, based on the sampling, a number of unique client devices included the samples, thus obtaining an estimate of unique ad impressions for the defined ad campaign.

First claim

What is claimed is:

1. A method, comprising:
streaming video content including the video advertising segments to a plurality of client devices;
receiving, by a computing device, a query defining a time period and an integer ‘N’;
determining, by the computing device, in response to the query, a discrete probability distribution of video advertising segments per unit time per client device in a population of the video advertising segments streamed to the plurality of client devices during ad slots in the video content streamed to the plurality of client devices, based on a count of video advertising segments per unit time streamed to each of the plurality of client devices by a streaming video system;
storing, by the computing device, a first data structure including a set of nodes used for randomly sampling the probability distribution as a search tree, wherein the set of nodes include a count where every node in a left sub-tree of a node has a smaller partial sum, and every node in a right sub-tree has a larger partial sum;
modifying, by the computing device, the first data structure to generate a second data structure such that nodes of the search tree in each right sub-tree include a count representing a delta from a partial sum from an adjacent node of the search tree;
randomly sampling, by the computing device, the probability distribution ‘N’ times without replacement, wherein each sample of the probability distribution identifies a number of video advertising segments streamed to a client device during the ad slots in the probability distribution;
determining, by the computing device, based on the random sampling, ‘N’ client devices using a binary search algorithm on the search tree based on an implied value of nodes that is calculated each sample using deltas of the second data structure to determine the count of the nodes in the first data structure, enabling completing the ‘N’ samples in an amount of time proportional to log(N);
updating, by the computing device, a value of only one node of the search tree in the second data structure for each sample taken in the random sampling;
determining, by the computing device, based on the sampling, a number ‘U’ of unique client devices included the N client devices, wherein unique client devices are determined to view at least one video advertising segment and a same client device is not represented more than once in the number U; and
storing, by the computing device, the number ‘U’ in a computer memory.

2. The method of claim 1 , further comprising maintaining, in the computer memory, the count of the video advertising segments per unit time streamed to each of the plurality of client devices by the streaming video system.

3. The method of claim 1 , obtaining a targeted ad impression profile from the query.

4. The method of claim 3 , further comprising limiting determination of the discrete probability distribution to video advertising segments streamed to a subset of a plurality of client devices matching the targeted ad impression profile.

5. The method of claim 1 , further comprising defining the unit time in the discrete probability distribution by a unit selected from the group consisting of: an hour, a period of two or more hours, and a 24 hour day.

6. The method of claim 1 , further comprising outputting the number ‘U’ in a user interface, with an indication that the number ‘U’ represents a number of unique ad impressions forecast for N number of ads.

7. The method of claim 1 , further comprising arranging the search tree so that nodes with higher counts are placed near a root node of the tree.

8. An apparatus, comprising:
at least one computer processor configured for:
streaming video content including the video advertising segments to a plurality of client devices;
receiving a query defining a time period and an integer ‘N’;
determining, in response to the query, a discrete probability distribution of video advertising segments per unit time per client device in a population of the video advertising segments streamed to the plurality of client devices during ad slots in the video content streamed to the plurality of client devices, based on a count of video advertising segments per unit time streamed to each of the plurality of client devices by a streaming video system;
storing a first data structure including a set of nodes used for randomly sampling the probability distribution as a search tree, wherein the set of nodes include a count where every node in a left sub-tree of a node has a smaller partial sum, and every node in a right sub-tree has a larger partial sum;
modifying the first data structure to generate a second data structure such that nodes of the search tree in each right sub-tree include a count representing a delta from a partial sum from an adjacent node of the search tree;
randomly sampling the probability distribution ‘N’ times without replacement, wherein each sample of the probability distribution identifies a number of video advertising segments streamed to a client device during the ad slots in the probability distribution;
determining based on the random sampling, ‘N’ client devices using a binary search algorithm on the search tree based on an implied value of nodes that is calculated each sample using deltas of the second data structure to determine the count of the nodes in the first data structure, enabling completing the ‘N’ samples in an amount of time proportional to log(N);
updating a value of only one node of the search tree in the second data structure for each sample taken in the random sampling;
determining, based on the sampling, a number ‘U’ of unique client devices included the N client devices, wherein unique client devices are determined to view at least one video advertising segment and a same client device is not represented more than once in the number U;
storing the number ‘U’ in a computer memory; and
a memory coupled to the at least one computer processor for storing data.

9. The apparatus of claim 8 , wherein the processor is further configured for maintaining, in the computer memory, the count of the video advertising segments per unit time streamed to each of the plurality of client devices by the streaming video system.

10. The apparatus of claim 8 , wherein the processor is further configured for processing the query thereby obtaining a targeted ad impression profile.

11. The apparatus of claim 10 , wherein the processor is further configured for limiting determination of the discrete probability distribution to video advertising segments streamed to a subset of a plurality of client devices matching the targeted ad impression profile.

12. The apparatus of claim 8 , wherein the processor is further configured for defining the unit time in the discrete probability distribution by a unit selected from the group consisting of: an hour, a period of two or more hours, and a 24 hour day.

13. The apparatus of claim 8 , wherein the processor is further configured for outputting the number ‘U’ in a user interface, with an indication that the number ‘U’ represents a number of unique ad impressions forecast for N number of ads.

14. The apparatus of claim 8 , wherein the processor is further configured for arranging the search tree so that nodes with higher counts are placed near a root node of the tree.

15. A computer program product, comprising:
a non-transitory computer-readable medium holding coded instructions, that when executed by a computer processor, cause a computer to perform the operations of:
streaming video content including the video advertising segments to a plurality of client devic

Assignees

• Hulu Llc

Inventors

• Zhang Tony T

Classifications

• H04N21/26266

  for determining content or additional data repetition rate, e.g. of a file in a DVB carousel according to its importance (arrangements for broadcast or for distribution of identical information repeatedly in broadcast distribution systems H04H20/16) · CPC title

• H04N21/26241

  involving the time of distribution, e.g. the best time of the day for inserting an advertisement or airing a children programme · CPC title

• G06Q30/02

  Marketing; Price estimation or determination; Fundraising · CPC title

• H04N21/812

  involving advertisement data (advertising per se G06Q30/02) · CPC title

• G06Q30/0241 Primary

  Advertisements · CPC title