Patent ID: 9070139
Filing Date: 2015-06-30
Classification: G06Q,H04N

Abstract:
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.