Methods and apparatus to estimate large scale audience deduplication

An example apparatus includes an association controller to generate a tree structure association for a total audience size that accessed a plurality of media items, the tree structure association including a first node representative of a first media item accessed by first audience members of the total audience size and a second node representative of a second media item accessed by second audience members of the total audience size, a matrix generator to generate a matrix by selecting a sum of probabilities value corresponding to the tree structure association, the sum of probabilities value representative of a probability of the first audience members accessing the first media item and storing the sum of probabilities value in an element of the matrix, and a commercial solver to estimate a deduplicated audience size of the total audience size using the matrix.

FIELD OF THE DISCLOSURE

This disclosure relates generally to monitoring computer-based media delivery, and, more particularly, to methods and apparatus to estimate large scale audience deduplication.

BACKGROUND

Determining a size and demographics of an audience of a media presentation helps media providers and distributors schedule programming and determine a price for advertising presented during the programming. In addition, accurate estimates of audience demographics enable advertisers to target advertisements to certain types and sizes of audiences. To collect these demographics, an audience measurement entity enlists a group of media consumers (often called panelists) to cooperate in an audience measurement study (often called a panel) for a predefined length of time. In some examples, the audience measurement entity obtains (e.g., directly, or indirectly from a media service provider) return path data (e.g., census data representative of a population of users) from media presentation devices (e.g., set-top boxes) that identifies tuning data from the media presentation devices. In such examples, because the return path data may not be associated with a known panelist, the audience measurement entity models and/or assigns viewers to represent the return path data. Additionally, the media consumption habits and demographic data associated with the enlisted media consumers are collected and used to statistically determine the size and demographics of the entire audience of the media presentation. In some examples, this collected data (e.g., data collected via measurement devices) may be supplemented with survey information, for example, recorded manually by the presentation audience members.

DETAILED DESCRIPTION

Audience measurement entities seek to understand the composition and audience size of media, such as television programming. Such information allows audience measurement entity researchers to, for example, report advertising delivery and/or targeting statistics to advertisers that target their media (e.g., advertisements) to particular audiences. Additionally, such information helps to establish advertising prices commensurate with audience exposure and demographic makeup (referred to herein collectively as “audience configuration”). One way to gather media presentation information is to gather the media presentation information from media output devices (e.g., gathering television presentation data from a set-top box (STB) connected to a television). As used herein, media presentation includes media output by a media device regardless of whether an audience member is present (e.g., media output by a media output device at which no audience is present, media exposure to an audience member(s), etc.).

A media presentation device (e.g., a STB) provided by a service provider (e.g., a cable television service provider, a satellite television service provider, an over-the-top (OTT) service provider, a music service provider, a movie service provider, a streaming media provider, etc.) or purchased by a consumer may contain processing capabilities to monitor, store, and/or transmit tuning data (e.g., which television channels are tuned by the media presentation device at a particular time) back to the service provider. The service provider can then aggregate and provide such return path data to an audience measurement entity (e.g., The Nielsen Company (US), LLC) to analyze media presentation activity and/or generate audience metrics. Data transmitted from a media presentation device back to the service provider is referred to herein as return path data which may include census data. Return path data includes tuning data. Tuning data is based on data received from the media presentation device while the media presentation device is on (e.g., powered on, switched on, and/or tuned to a media channel, streaming, etc.). Although return path data includes tuning data, return path data may not include data related to the user viewing the media corresponding to the media presentation device. Accordingly, return path data may not be able to be associated with specific viewers, demographics, locations, etc. However, census data may be derived or extracted from return path data. Census data is indicative of the total percentage of a population of users (e.g., based on the return path data) that was exposed to media at a particular margin. For example, if 20% of a population was exposed to a first margin (e.g., a first a television show), the census data may be indicative of the 20% exposure.

To determine aspects of media presentation data (e.g., which household member is currently consuming a particular media and the demographics of that household member), market researchers may perform audience measurements by enlisting a subset of the media consumers as panelists. Panelists or monitored panelists are audience members (e.g., household members, users, panelists, etc.) enlisted to be monitored, who divulge and/or otherwise share their media activity and/or demographic data to facilitate a market research study. An audience measurement entity typically monitors media presentation activity (e.g., viewing, listening, etc.) of the monitored panelists via audience measurement system(s), such as a metering device(s) and/or a local people meter (LPM). Audience measurement typically includes determining the identity of the media being presented on a media output device (e.g., a television, a radio, a computer, etc.), determining data related to the media (e.g., presentation duration data, timestamps, channel data, etc.), determining demographic information of an audience, and/or determining which members of a household are associated with (e.g., have been exposed to) a media presentation. In this manner, audience measurement data includes demographic impressions which are generated by logging impressions in association with demographic information of panelists. An LPM in communication with an audience measurement entity communicates audience measurement data (e.g., metering data) to the audience measurement entity. As used herein, the phrase “in communication,” including variances thereof, encompasses direct communication and/or indirect communication through one or more intermediary components and does not require direct physical (e.g., wired) communication and/or constant communication, but rather additionally includes selective communication at periodic or aperiodic intervals, as well as one-time events.

In some examples, metering data (e.g., including media presentation data) collected by an LPM or other meter is stored in a memory and transmitted via a network, such as the Internet, to a datastore managed by the audience measurement entity. Typically, such metering data is combined with additional metering data collected from a group of LPMs monitoring a group of panelist households. The metering data may include, but is not limited to, a number of minutes a household media presentation device was tuned to a particular channel, a number of minutes a household media presentation device was used (e.g., consumed) by a household panelist member and/or a visitor (e.g., a presentation session), demographics of the audience (which may be statistically projected based on the panelist data), information indicative of when the media presentation device is on or off, and/or information indicative of interactions with the media presentation device (e.g., channel changes, station changes, volume changes, etc.), etc. As used herein, a channel may be a tuned frequency, a selected stream, an address for media (e.g., a network address), and/or any other identifier for a source and/or carrier of media.

In other examples, examples disclosed herein can be implemented with census-level impression data logged by an AME and panel impression data. The impression data is logged using internet media monitoring techniques including those disclosed in U.S. Pat. No. 8,370,489 to Mazumdar et al., and entitled “Methods and apparatus to determine impressions using distributed demographic information,” which is hereby incorporated herein by reference in its entirety. In such examples, census data corresponds to impressions (e.g., exposures to a media item by an audience member) logged for a general audience in a population regardless of whether the impressions correspond to audience members that are identifiable by the AME. In such examples, census-level impressions are collected as anonymous impression data. Panel impression data is logged by the AME from panelist enrolled in the panel that agreed to having their media access activities monitored for audience analysis. In this manner, the AME uses its panel data to generate demographic impression data. In other examples, instead of using panel data of the AME, demographic impression data can be generated by a third-party database proprietor that monitors media accesses and logs corresponding impressions in association with demographic data collected from its subscribers.

To overcome such inconsistencies, examples disclosed herein estimate deduplicated audience sizes based on margins and unions. As used herein, a margin is a subpart of media, and marginal data is data related to margins of media. For example, if the media corresponds to an advertisement, the margins may be different websites (e.g., different media items) that include the advertisement. In another example, a first media item (e.g., a first television show) may correspond to a first margin and a second media item (e.g., a second television show different than the first media) may correspond to a second margin. In yet another example, if the media corresponds to a one-hour program, the margins may be four 15-minute increments of the one-hour program. As used herein, a union is data corresponding to a combination of margins. In some examples, a union can be made up of smaller unions (e.g., a union of smaller unions of margins, such as a union of smaller unions of time-periods) and/or individual margins (e.g., time-periods, such as quarter-hours). For example, a first union may include a first television show and a second television show, a second union may include third, fourth, and fifth television shows, and a third union may include the first union and the second union. As used herein, child unions or children are the smaller unions that make up a larger union, and a parent union or a parent is a larger union that includes the child union(s) and/or children. Using the above example, the children of the first union include the first television show and the second television show, and the parent of the first union is the third union. As used herein, reach is a cumulative percentage or total of a population that has been counted as an audience member (e.g., a viewer, a listener, a reader, an observer, etc.) of the media at least once during a specified time interval (e.g., hourly, daily, weekly, monthly, etc.).

In some examples, an audience measurement entity receives marginal media exposure data (e.g., different episodes of a television series, different network channels, different quarter-hour time slots of a television program, a radio program, etc.) for different unions of marginal data and/or smaller unions of audience members (e.g., total audience, panel audience, etc.) and estimates a total population reach (e.g., a total number of deduplicated users that were exposed to media) across all of the different unions. However, in some examples, the deduplicated audience size for one or more margins and/or one or more combinations of margins may be unknown and/or otherwise missing. Examples disclosed herein estimate one or more deduplicated audience sizes of media given partial information of the relationships to the received known audience size data.

As used herein, an audience size is defined as a number of deduplicated or unique audience members exposed to a media item of interest for audience metrics analysis. A deduplicated or unique audience member is one that is counted only once as part of an audience size. Thus, regardless of whether a particular person is detected as accessing a media item once or multiple times, that person is only counted once in the audience size for that media item. Audience size may also be referred to as unique audience or deduplicated audience.

To estimate the deduplicated audience sizes of media given partial information from the audience, examples disclosed herein utilize a tree graph association or tree structure association for the margins and union(s). The tree graph association corresponds to the structure of the margins and/or unions where each margin and each union corresponds to a node. Examples disclosed herein tag each node (e.g., store an identifier in association with) as a descendant (e.g., a child, a grandchild, etc.) and/or an ancestor (e.g., a parent, a grandparent, etc.) depending on the structure of the unions corresponding to stored panel data. For example, if panel data includes a unique audience number or percentage corresponding to three margins (e.g., A, B, and C), and the panel data further includes a unique audience number or percentage corresponding to a first union (e.g., AB) and a second union (e.g., ABC), examples disclosed herein may tag (1) nodes A and B as having parent AB and grandparent ABC, (2) node C as having parent ABC, (3) node AB as having children A and B and parent ABC, and (4) node ABC as having children AB and C and grandchildren A and B. Additionally, examples disclosed herein may tag the margin nodes (e.g., A, B, and C) as leaves, and tag ABCD as a root. As used herein, a leaf is a node that does not have children (e.g., a terminal node) and a root is a node that has no parents.

Traditional methods to estimate deduplicated audience sizes can do so by solving a maximum entropy problem. Accordingly, traditional methods may solve Equation 1 and Equation 2, below.
maximizePH=—Σi=1n(pilog(pi))  Equation 1
subject to Σi=1n(cjipi)=djj=0, . . . ,mEquation 2

In Equation 1 above, a matrix p corresponds to the probabilities that identify a distribution of total people that are exposed to media (e.g., exposed to a margin, exposed to a union, viewed a television show, etc.), the variable n corresponds to the number of probabilities, the variables j and i index constraints c in a constraint matrix cji, and the variable m corresponds to the audience demographic information known from the constraints c. Example constraints c specify the numerical limits for use in modeling the audience sizes and exposures to various media. In examples disclosed herein, constraints correspond to limits in audience sizes associated with various media. For example, a first margin corresponding to a first television show may be associated with a first constraint of 0.1. In such an example, the constraint, 0.1, identities a limit of ten percent of an audience size exposed to the first margin.

In Equation 2 above, a matrix c represents the constraints of the system, a matrix d represents the constraint limits. In Equation 1 or Equation 2 above, the coefficients of the matrix c can be either zero or one for any index of “i” or “j”. Equation 3 below illustrates this concept.
cji={0,1}∀{j,i}Equation 3

When optimizing Equation 1, in view of Equation 2 and Equation 3, the probabilities can be enumerated as illustrated below, in Equation 4.
pi=exp(Σj=1m(cijλj)  Equation 4

In Equation 4, the variable A corresponds to a Lagrange multiplier, which is initialized to zero. In some applications, commercial solvers are utilized to solve for the Lagrange multipliers, λ. Alternatively, some applications utilize the Jacobian matrix as in input to commercial solvers to improve processing efficiency when solving for and/or otherwise identifying the Lagrange multipliers, λ. Equation 5 below can be used to solve for the Lagrange multipliers, λ, while satisfying the constraints, c.
fj(λ)=Σi=1n(cijpi)=Σi=1n(cij(exp(Σj=1m(cijλj)))  Equation 5

In Equation 5 above, the variable f corresponds to a sum of probabilities associated with each “jth” index. For example, each node in a tree structure association (e.g., each margin and/or union) may be associated with an index value. In examples disclosed herein, a sum of probabilities, f, may be identified with an index value corresponding to the associated node being analyzed. For example, if a first node (e.g., a first margin) is tagged with an index value of one, the corresponding sum of probabilities may be enumerated as f1. Further, the Lagrange multipliers, λ, can be solved such that the Equation 6 below is satisfied.
fj(λ)=djj=0, . . . ,mEquation 6

In Equation 6 above, the variable d corresponds to known probabilities obtained via panelist data. The known probabilities are probabilities that an audience member and/or audience size accessed media known to be true. These are known probabilities because they are based on audience measurement data for which identities of audiences and corresponding assessed media are known. In an alternate example, the sum of probabilities, f, may be defined in a manner similar to Equation 7, below.
Fj(λ)=fj−djEquation 7

Accordingly, such a solution can be solved using Newton's Method for solving systems of non-linear equations. Newton's method for solving a system of non-linear equations is illustrated in Equation 8, below.
JF(λn)(λn+1−λn)=−F(λn)  Equation 8

In Equation 8 above, the variable n corresponds to the “nth” index value, the variable λ corresponds to the vector of individual Lagrange multipliers associated with a jth index {λ}j, and the matrix J corresponds to the Jacobian matrix. The Jacobian matrix, J, is calculated to substantially reduce or eliminate error in audience size measurements. The Jacobian matrix, J, is a matrix representative of the amount of transformation performed to audience data.

The Jacobian matrix, J, can be defined as a partial derivative of a sum of the probabilities, f, with respect to a partial derivative of the Lagrange multipliers, λ. The Jacobian matrix, J, is illustrated below in Equation 9.

In Equation 9 above, the sum of probabilities, f, can be expanded utilizing Equation 6, as shown in Equation 10 below.

Furthermore, Equation 10 can be rewritten as shown below in Equation 11.

Equation 11 can be rewritten as shown below in Equation 12, and further in Equation 13.
Jjk=Σi=1ncjicki(exp(Σj=1m(cijλj))  Equation 12
Jjk=Σi=1n(cjicki)piEquation 13

In examples disclosed herein, the Jacobian matrix, J, can be an input to one or more commercial solvers to reduce processing time relative to prior techniques when solving large-scale audience deduplication problems. Examples disclosed herein employ methods and apparatus to approximate the Jacobian matrix more efficiently than prior techniques by utilizing a sum of probabilities, or a function of a sum of probabilities, associated with margins and/or unions of media as elements in the Jacobian matrix.

Examples disclosed herein utilize methods and apparatus to determine diagonal elements in a Jacobian matrix (e.g., elements in which the row and column index are identical) based on a first sum of probabilities obtained from a tree graph association or tree structure association for the margins and union(s). For example, in a tree graph association or tree structure association, examples disclosed herein determine elements in a Jacobin matrix for descendant nodes (e.g., one or more child node(s) that is/are descendent(s) of one or more parent node(s)) using a second sum of probabilities. Additionally, examples disclosed herein can use a tree graph association or tree structure association to determine non-diagonal elements and non-descendant elements in a Jacobin matrix using a third sum of probabilities.

FIG.1is a block diagram of an environment in which example return path data100and example meter data102are collected to determine unknown total audience sizes based on known marginal and/or union totals.FIG.1includes the example return path data100, the example meter data102, an example media provider104, an example media presentation device106, example media output devices108,110, an example local people meter (LPM)112, and an example audience measurement entity (AME)114. The example audience measurement entity114includes an example return path data (RPD) audience storage116(e.g., a database), an example panelist data storage118(e.g., a database), and an example audience size determiner120. Although the example audience size determiner120ofFIG.1is illustrated as determining deduplicated audiences size totals for margins and/or unions of return path data and/or panelist data, examples disclosed herein may be utilized with any type of data where audience size information is known for some margins and/or unions and unknown for other margins and/or unions (e.g., exposures to websites, purchasing products, store visits, etc.).

The example media provider104ofFIG.1is a service provider (e.g., a cable media service provider, a radio frequency (RF) media provider, a satellite media service provider, etc.) that delivers media to be accessed by an audience member via the example media presentation device106. The media provided by the example media provider104is transmitted (e.g., via a wired and/or wireless network connection) to the media presentation device106. The media presentation device106is connected, via a wired and/or wireless connection, to the example media output device108to output the media to an audience member. The media output device108is a device capable of outputting the received media. For example, the media output device108may be a television, a radio, speakers, a projector, a computer, a computing device, a tablet, a mobile device, and/or any other device capable of outputting media.

When the example media presentation device106ofFIG.1is operating to access media, the media presentation device106receives media corresponding to a station, a program, a website, etc., based on the tuning of the example media presentation device106. For example, the media presentation device106may be a set-top box. Additionally or alternatively, the example media presentation device106may be an over-the-top (OTT) device, a video game console, a digital video recorder (DVR), a digital versatile disc (DVD) player, a receiver, a router, a server, a computer, a mobile device, software executed by a website, computer, and/or application, and/or any device that receives media from a service provider. For example, the media presentation device106may be a website and/or application that provides media to users via the media output device108. In some examples, the media presentation device106may implement a DVR and/or a DVD player. In some examples, the media presentation device106includes a unique serial number that, when associated with subscriber information, allows an audience measurement entity, a marketing entity, and/or any other entity to ascertain specific subscriber behavior information.

By way of example, the media presentation device106may be tuned to channel 5. In such an example, the media presentation device106outputs media (e.g., from the example media provider104) corresponding to the tuned channel 5. The media presentation device106may gather tuning data corresponding to channels, stations, websites, etc., to which the example media presentation device106is tuned. The example media presentation device106generates and transmits the example return path data100(e.g., census data corresponding to the total population of users) to the example media provider104. The example return path data100includes the tuning data and/or data corresponding to the example media provider104. Although the illustrated example ofFIG.1includes the example media provider104receiving the example return path data100from one media presentation device (e.g., the example media presentation device106), at one location, corresponding to one media provider (e.g., the example media provider104), the example media provider104may receive return path data100from any number or type(s) of media presentation devices, at any number of locations. The media provider104transmits the collected return path data100to the example audience measurement entity114for storing in the RPD audience storage116. Additionally or alternatively, the example RPD audience storage116may be hosted by any other entity or may be co-hosted by another entity(ies). For example, the example return path data100may be collected from the example media presentation devices106by a media provider (e.g., a cable television provider, a satellite television provider, etc.) and the example meter data102may be collected from an LPM (e.g., such as the example LPM112) by the example audience measurement entity114cooperating with the media provider to gain access to the tuning data.

The example media output device110ofFIG.1is a device capable of outputting the received media. For example, the media output device110may be a television, a radio, speakers, a projector, a computer, a computing device, a tablet, a mobile device, and/or any other device capable of outputting media. In some examples, the media output device110receives media over-the-air. In this manner, the media output device110receives media via an antenna and does not correspond to a media provider (e.g., including the example media provider104). In the illustrated example ofFIG.1, the media output device110corresponds to one or more monitored panelists. The example LPM112monitors the panelists' exposure to media output by the example media output device110. For example, the example LPM112is in communication with the example media output device110to collect and/or capture signals emitted externally by the media output device110. The LPM112may be coupled with the media output device110via wired and/or wireless connection. The example LPM112may be implemented in connection with additional and/or alternative types of media presentation devices, such as, for example, a radio, a computer monitor, a video game console, and/or any other device capable of presenting media to a user. The LPM112may be a portable people meter, a cell phone, a computing device, a sensor, and/or any other device capable of metering (e.g., monitoring) audience exposure to media. In some examples, a media presentation location (e.g., a household, a retail establishment, a commercial establishment, etc.) may include a group of LPMs112. In such examples, the group of the LPMs112may be used to monitor media exposure for multiple audience members and/or media output devices110. Additionally, the example panelist data storage118receives and stores the example meter data102from the example LPM112.

In some examples, the example LPM112ofFIG.1includes buttons assigned to audience members to determine which of the audience members is watching the example media output device110. The LPM112may periodically prompt the audience members via LEDs, a display screen, and/or an audible tone, to indicate that the audience member is present at a first media presentation location by pressing an assigned button. In some examples, to decrease the number of prompts and, thus, the number of intrusions imposed upon the media consumption experience of the audience members, the LPM112prompts only when unidentified audience members are located at the first media presentation location and/or only after the LPM112detects a channel change and/or a change in state of the media output device110. In other examples, the LPM112may include at least one sensor (e.g., a camera, a 3-dimensional sensor, etc.) and/or be communicatively coupled to at least one sensor that detects a presence of the user in a first example media presentation location. The example LPM112transmits the example meter data102to a media researcher and/or a marketing entity. The example meter data102includes the media presentation data (e.g., data related to media presented while the media output device110is on and a user is present). The example meter data102may further include a household identification, a tuner key, a presentation start time, a presentation end time, a channel key, etc. Although the illustrated example illustrates the example audience measurement entity114collecting the example meter data102from one LPM112at one location, the example audience measurement entity114may collect meter data from any number or type of meters at any number of locations.

The example return path data100ofFIG.1from the example media presentation device106and/or the example meter data102from the example LPM112is transmitted to the example audience measurement entity114via a network. The network may be implemented using any type of public or private network, such as, but not limited to, the Internet, a telephone network, a local area network (LAN), a cable network, and/or a wireless network. To enable communication via the network, the example media presentation device106includes a communication interface that enables a connection to an Ethernet medium, a digital subscriber line (DSL), a telephone line, a coaxial cable, or any wireless connection, etc.

The example return path data audience storage116of the example AME114ofFIG.1collects the example return path data100corresponding to the example media presentation device(s)106. As described above, the example return path data100includes tuning data of the example media presentation device106. However, in some examples, the example return path data100may not include specific data identifying any information relating to the audience of the example media output device108. In such examples, another device and/or processor models such audience information prior to storing in the example return path data audience storage116. For example, the device and/or processor may assign and/or model virtual users to augment the example return path data100, thereby generating audience-assigned return path data.

The example audience size determiner120ofFIG.1receives the recorded total audience sizes for different margins (e.g., media items such as a first television show, a second television show, a first website, a second website, etc.) and/or unions of different margins from the example panelist data storage118, the total audience sizes for the population (e.g., based on census data) for the different margins (e.g., media items) of the media from the RPD audience data storage116, and a total population size (e.g., the universe estimate) from one or more devices from either the RPD audience data storage116, the panelist data storage118, and/or any other storage. In examples disclosed herein, the audience size determiner120may implement an example means for determining.

Unions may be representative of any combination of media items (e.g., margins) which an audience member and/or a plurality of audience members may access (e.g., be exposed to). In some examples, a union may include multiple unions. For example, union ABCD (e.g., four different television channels) may be a union of union AB (e.g., a first television channel and a second television channel) and union CD (e.g., a third television channel and a fourth television channel), where union AB is a union of margin A and margin B, and union CD is a union of margin C and margin D. Each union may have corresponding descendants nodes and/or ancestor nodes. Using the above example, the parent of union AB is union ABCD, and the children of union AB are A and B. Each union corresponds to a union reach or total audience size.

The example audience size determiner120ofFIG.2generates a tree structure association by tagging each node (e.g., each margin or union) with the corresponding descendants and/or ancestors. For example, the audience size determiner120stores an index value in association with each node with index values corresponding to the corresponding descendants and/or ancestors in a record (e.g., in a register, storage, a database, memory, cache, etc.). Accordingly, each node corresponds to known or unknown total audience sizes in a tree structure association that corresponds to unions of margins for media. An example tree structure association in conjunction with known and unknown total audience sizes for media is further shown in conjunction withFIG.2. The example audience size determiner120determines deduplicated audience member totals for all margins and/or unions of media. For example, when an audience member is exposed to a first television show (e.g., a first margin) and a second television show (e.g., a second margin), rather than duplicating a total audience member count, the audience size determiner120can estimate a total deduplicated audience size. In doing so, the audience size determiner is configured to solve a matrix (e.g., a Jacobian matrix) based on one or more sum(s) of probabilities associated with each node in the tree structure association. Once the matrix (e.g., a Jacobian matrix) is solved, the audience size determiner120can determine audience member totals for all margins and/or unions of media. The example audience size determiner120is further described below in conjunction withFIG.4.

FIG.2includes example marginal and union total audience size data200. The example marginal and union total audience size data200ofFIG.2corresponds to the deduplicated total audience sizes of the panel, the population, or any other group of audience that was exposed to media at different margins and/or unions based on the return path data100stored in the example RPD audience data storage116, the meter data102stored in the example panelist data storage118, or other audience data stored in other storage. For example, the audience size determiner120obtains the marginal and union total audience size data200corresponding to total audience sizes with both known (e.g., the total audience sizes for margin A=10 people, B=20 people, and C=30 people and the total audience sizes for union (AB)=27 people and (ABC)=40 people).

For example, if A, B, and C represent different media items (e.g., margins), the marginal and union total audience size data200ofFIG.2shows that ten people were exposed to the first media item (A), twenty people were exposed to the second media item (B), thirty people were exposed to the third media item (C), twenty-seven deduplicated people were exposed to both the first and second media items (D), and forty deduplicated people were exposed to the first, second, and third media items, where the universe estimates of people is one hundred.

FIG.3illustrates an example tree structure association300representing the tree structure of the margins and unions of the example marginal and union total audience size data200ofFIG.2. The tree structure association300corresponds to a tree linkage of margins and unions based on the unions identified in the example marginal and union total audience size data200. Alternatively, other tree structures can be generated based on different combinations of margins and/or unions. The example audience size determiner120(FIG.1) generates a tree structure association or tree structure associations corresponding to the example tree structure association300by tagging (e.g., associating index values) the margins and/or unions with corresponding node numbers, ancestors, and/or descendants. For example, the audience size determiner120may tag the AB union with a node number (e.g., 4) and may tag the AB node as having a parent union of ABC (e.g., node5) and children margins A and B (e.g., nodes1and2). In this manner, commercial solvers of the audience size determiner120can utilize the values of the example marginal and union total audience size data200for the corresponding variables of the above Equations 1-8. After the example audience size determiner120generates the tree structure association300based on the marginal and union total audience size data200, the example audience size determiner120determines the total deduplicated audience sizes for the audience nodes (e.g., nodes1,2,3,4, and/or5).

FIG.4is a block diagram of the example audience size determiner120ofFIG.1to determine (e.g., estimate) total deduplicated audience sizes for margins and/or unions based on known total audience sizes. As used herein, a known total audience size (e.g., total deduplicated audience size) corresponds to a number of audience members known to be exposed to at least one media item (e.g., a margin). In examples disclosed herein, each margin may be associated with a known total audience size when audience measurement data for a media item is generated by logging impressions based on known audience members that accessed that media item. Further, each union of margins may be associated with a known total audience size when audience measurement data for multiple media items is generated by logging impressions based on known audience members that accessed those multiple media items. The example audience size determiner120includes an example interface(s)400, an example association controller402, an example probability manager404, an example matrix generator406, an example commercial solver(s)408, and an example local memory410. Although the example audience size determiner120is described in conjunction with return path data or panelist data, the example audience size determiner120may estimate total audience sizes based on information provided by any device that measures accesses to subjects of interest in terms of different margins and/or unions. For example, the example audience size determiner120may determine (e.g., estimate) one or more total audience sizes from different programs, store visits for different stores, website visits, time intervals of media exposure, etc.

The example interface(s)400ofFIG.4receives total audience sizes (e.g., panel total audience sizes, RPD total audience sizes, and/or any other total audience sizes) for margins and/or unions from a database (e.g., the RPD audience data storage116, the panelist data storage118, or another storage). The margins may be separated based on media item. For example, the total audience sizes may correspond to four margins each associated with a different media item. Additionally, the interface(s)400obtains a universe estimate (UE) corresponding to the universe of users/viewers/listeners. The universe is representative of all the audience members being measured. Further, the universe is representative of the total number of people or population available to access the media item(s) under analysis regardless of whether such persons actually accessed the media items(s) under analysis. The UE values may be derived from prior audience size measurements. Additionally, the example interface(s)400may output total audience sizes that have been calculated by the commercial solver(s)408. In some examples, the interface(s)400transmit the total audience sizes back to the RPD audience data storage116or the panelist data storage118to add the estimated total audience sizes to the dataset to eliminate the unknown total audience sizes. In examples disclosed herein, the interface(s)400may implement example means for interfacing.

The example association controller402ofFIG.4is provided to generate the tree structure association based on the margins and selected unions. For example, using the unions and margins of the example ofFIG.2, the association controller402tags each margin and union with (i) a number, an index value, or other identifier and (ii) with corresponding ancestors and/or descendants. For example, the association controller402tags the AB union (e.g., a node of the tree structure association300ofFIG.3) with a node index value (e.g., “4” for node4inFIG.3) and tags the AB node/union as having a parent union of ABC (e.g., node5inFIG.3) and children margins A and B (e.g., nodes1and2inFIG.3). The association controller402stores the tags in conjunction with the total audience sizes in the example local memory410. In this manner, the commercial solver(s)408can solve a system of equations using the tagged margin and/or union total audience sizes stored in the example local memory410. In examples disclosed herein, the association controller402may implement example means for controlling.

The example probability manager404ofFIG.4is provided to determine and/or otherwise identify estimated probabilities associated with each margin and/or union in the tree structure association300. Initially, the example probability manager404identifies current estimates of the Lagrange multipliers. For example, the probability manager404is configured to determine the current state of the Lagrange multipliers. After the example probability manager404identifies the current estimates of the Lagrange multipliers, the probability manager404computes estimated probabilities associated with each margin(s) and/or union(s) of media. In this manner, the example probability manager404stores the estimated probabilities associated with each margin(s) and/or union(s) of media in the local memory410. In examples disclosed herein, the probability manager404may implement example means for managing.

The example matrix generator406ofFIG.4is provided to determine a matrix (e.g., a Jacobian matrix) based on the estimated probabilities determined by the probability manager404. The example matrix generator406may store the matrix (e.g., the Jacobian matrix) in the local memory410for use by the commercial solver(s)408. In some examples, the matrix generator406is configured to determine, analyze, update, store, and/or otherwise calculate each element in the matrix (e.g., the Jacobian matrix). In examples disclosed herein, the matrix (e.g., Jacobian matrix) is a m×m matrix in which the variable m represents a number of nodes equivalent to a sum of (1) the number of nodes in a tree structure association (e.g., the number of margin(s) and/or union(s) in the tree structure association300ofFIG.3) and (2) an additional node corresponding to the UE. For example, the tree structure association300ofFIG.3includes three margins (e.g., nodes A, B, and C) and two unions (e.g., nodes AB and ABC) and, thus, the corresponding matrix is a six-by-six matrix. In examples disclosed herein, the probability matrix generator406may implement example means for generating.

Accordingly, the example matrix generator406is configured to traverse through all possible combinations of margins and/or unions when generating the matrix (e.g., the Jacobian matrix). The example matrix generator406is configured to analyze each element of the matrix (e.g., the Jacobian matrix) individually to identify example index values associated with each element. For example, each element in the matrix (e.g., the Jacobian matrix) is associated with a jth and kth index value (e.g., a jth index value to identify a row and a kth index value to identify a column). Accordingly, when an element is a diagonal element in the matrix (e.g., when the jth and kth index values are equivalent), the matrix generator406stores a value in the element equivalent to the sum of probabilities associated with the node having the same index value as the element. For example, if the element being analyzed corresponds to position (1,1) (e.g., the jth index value is 1 and the kth index value is 1) of the matrix, then the element is a diagonal and, thus, the matrix generator406stores a value in the element that is equivalent to the sum of probabilities associated with the margin and/or union having the same index value. The example matrix generator406may execute Equations 15-18 below for elements that are diagonal elements.
Jjk=Σi=1n(cjicki)piEquation 15
Jjk=Σi=1n(cji)2piEquation 16
Jjk=Σi=1ncjipiEquation 17
Jjk=fjEquation 18

Since Equations 15-18 above are used to analyze diagonal elements, the index values j and k are equivalent. Accordingly, the matrix, J, at the element defined by the index value (j,k) (e.g., (j,j), or (k,k)) can be identified as being the current sum of probabilities associated with the jth margin and/or union. For example, the element (1,1) of the matrix (e.g., the Jacobian matrix) can be identified by the matrix generator406as being equivalent to the sum of probabilities associated with the node having an index value of 1 (e.g., node A ofFIG.3).

Additionally, in examples disclosed herein, when the jth index value of the element is associated with a node that is a descendant of a node associated with the kth index value, the matrix generator406stores a value in the element equivalent to the sum of probabilities associated with the node having the same index value as the jth index value. For example, if the element being analyzed corresponds to position (2,4) of the matrix, and the node having an index value of two is a descendant of the node having an index value of four, then the matrix generator406may store a value in the element equivalent to the sum of probabilities associated with the node having an index value of two. The example matrix generator406may execute Equations 19-21 below when the jth index value of the element corresponds to a node that is a descendant of a node associated with the kth index value.
Jjk=Σi=1n(cjicki)piEquation 19
Jjk=Σi=1ncjipiEquation 20
Jjk=fjEquation 21

In Equations 19-21 above, since the jth index value of the element corresponds to a node that is a descendant of a node associated with the kth index value, the node associated with the kth index value includes all audience members of the jth index value. Accordingly, the matrix, J, at element (j,k) can be identified as being the current sum of probabilities associated with the jth node. For example, the element (2,4) of the matrix (e.g., the Jacobian matrix) can be identified by the matrix generator406as being equivalent to the sum of probabilities associated with the second node (e.g., node B ofFIG.3).

Additionally, in examples disclosed herein, when the jth index value of the element is not associated with a node that is a descendant of a node associated with the kth index value, and the element is not a diagonal element, the matrix generator406stores a value in the element equivalent to a quotient of: (A) (i) the sum of probabilities associated with the node having the jth index value multiplied by (ii) the sum of probabilities associated with the node having the kth index value, and (B) a second sum of probabilities associated with a node being an ancestor of the nodes associated with the jth and kth index values. The example matrix generator406may execute Equations 22-24 below when the jth index value of the element is not indicative of a descendant of the kth index value and the element is not a diagonal element.
Jjk=Σi=1n(cjicki)piEquation 22
Jjk=fj∧kEquation 23
Jjk=fj+fk−fj∨kEquation 24

In Equations 22-24 above, determining the sum of probabilities associated with the node corresponding to jth index or the node corresponding to the kth index may be computationally intensive. Accordingly, the example matrix generator406may alternatively execute Equations 25-32 below when the jth index value of the element is not indicative of a descendant of the kth index value and the element is not a diagonal element.

In examples disclosed herein, the matrix generator406traverses through each element in the matrix. The example matrix generator406determines whether the jth and kth index values are indicative of: (1) a diagonal entry, (2) a descendant entry, or (3) neither a diagonal entry nor a descendent entry. The matrix generator406may execute Equations 15-18 when the element is a diagonal entry (e.g., the jth and kth index values are equivalent). The example matrix generator406may execute Equations 19-21 when the element is a descendent entry (e.g., jth index value of the element corresponds to a node that is a descendant of the node associated with the kth index value). The matrix generator406may execute Equations 22-24 or 25-32 when the element is neither a diagonal entry nor a descendent entry. Once fully traversed, the matrix generator406provides the matrix (e.g., the Jacobain matrix) to the local memory410.

The example commercial solver(s)408ofFIG.4may be implemented using optimization software packet(s) that solve(s) one or more system(s) of equations using the tagged margin and/or union total audience sizes stored in the example local memory410to estimate the total deduplicated audience sizes for margin and/or union total audience sizes. For example, the commercial solver(s)408may be a CPLEX optimizer, a GNU linear programming kit (GLPK), a Gurobi Optimizer, a solving constraint integer program, and/or any type of mixed integer programming optimizer. In some examples, the commercial solver(s)408may be implemented by an arithmetic logic unit (ALU). In examples disclosed herein, the commercial solver(s)408may execute control based on Equations 1-8 to estimate the total deduplicated audience sizes for margin and/or union total audience sizes. In examples disclosed herein, the commercial solver(s)408may implement example means for determining a deduplicated audience size. Additionally or alternatively, the commercial solver(s)408may implement example means for determining an audience size. Additionally or alternatively, the commercial solver(s)408may implement example means for estimating deduplicated audience sizes. In examples disclosed herein, the local memory410may implement example means for storing.

While an example manner of implementing the audience size determiner120ofFIG.1is illustrated inFIG.4, one or more of the elements, processes and/or devices illustrated inFIG.4may be combined, divided, re-arranged, omitted, eliminated and/or implemented in any other way. Further, the example interface(s)400, the example association controller402, the example probability manager404, the example matrix generator406, the example commercial solver(s)408, the example local memory410, and/or, more generally, the example audience size determiner120ofFIG.4may be implemented by hardware, software, firmware and/or any combination of hardware, software and/or firmware. Thus, for example, any of the example interface(s)400, the example association controller402, the example probability manager404, the example matrix generator406, the example commercial solver(s)408, the example local memory410, and/or, more generally, the example audience size determiner120ofFIG.4could be implemented by one or more analog or digital circuit(s), logic circuits, programmable processor(s), programmable controller(s), graphics processing unit(s) (GPU(s)), digital signal processor(s) (DSP(s)), application specific integrated circuit(s) (ASIC(s)), programmable logic device(s) (PLD(s)) and/or field programmable logic device(s) (FPLD(s)). When reading any of the apparatus or system claims of this patent to cover a purely software and/or firmware implementation, at least one of the example, the example interface(s)400, the example association controller402, the example probability manager404, the example matrix generator406, the example commercial solver(s)408, and/or the example local memory410is/are hereby expressly defined to include a non-transitory computer readable storage device or storage disk such as a memory, a digital versatile disk (DVD), a compact disk (CD), a Blu-ray disk, etc. including the software and/or firmware. Further still, the example audience size determiner120ofFIGS.1and/or4may include one or more elements, processes and/or devices in addition to, or instead of, those illustrated inFIG.4, and/or may include more than one of any or all of the illustrated elements, processes and devices. As used herein, the phrase “in communication,” including variations thereof, encompasses direct communication and/or indirect communication through one or more intermediary components, and does not require direct physical (e.g., wired) communication and/or constant communication, but rather additionally includes selective communication at periodic intervals, scheduled intervals, aperiodic intervals, and/or one-time events.

FIG.5is a flowchart500representative of example machine readable instructions that may be executed by a processor to implement the example audience size determiner120ofFIGS.1and/or4to estimate deduplicated audience sizes for margin(s) and/or union(s). The example flowchart500is described in conjunction with the example marginal and union total audience size data200ofFIG.2. However, the example flowchart500may be implemented in conjunction with any panelist data, census data, margins, and/or unions.

At block502, the example interface(s)400(FIG.4) obtains total audience sizes for margins and/or union(s) of media, and a universe estimate. As described above, the total audience sizes may correspond to panelist total audience size, RPD total audience sizes, and/or any other kind of total audience sizes for margins and/or union(s) of media. Using the example ofFIG.2, the interface(s)400obtain(s) the marginal and union total audience size data200corresponding to particular media (e.g., a first television show, a second television show, and a third television show) at margins A, B, and E and at unions AB and ABC. Additionally, using the example ofFIG.2, the interface(s)400obtain(s) the UE from RPD audience data storage116based on the return path data100.

At block504, the example association controller402(FIG.4) generates a tree structure association of the unions and margins. As described above in conjunction withFIG.4, the example association controller402generates a tree structure association (e.g., the tree structure association300ofFIG.3) by tagging the margins and unions with index values and/or identifiers and tagging each node with corresponding ancestor and/or descendant information. The tree structure association information is stored in the example local memory410. The example tree structure association300ofFIG.3illustrates an example tree structure corresponding to the marginal and union total audience size data200ofFIG.2.

At block506, the example probability manager404(FIG.4) identifies estimated probabilities associated with each margin(s) and/or union(s) of media. Using the example ofFIG.2, the probability manager404obtain(s) the marginal and union total audience size data200corresponding to particular media (e.g., a first television show, a second television show, and a third television show) at margins A, B, and E and at unions AB and ABC to determine an estimated probability of audience size associated with each margin and/or union. Example machine readable instructions that may be executed to implement block506are described below in connection withFIG.6.

At block508, the example matrix generator406(FIG.4) generates and/or otherwise determines a matrix (e.g., the Jacobian matrix) based on the estimated probabilities. For example, responsive to the probability manager404identifying estimated probabilities associated with each margin(s) and/or union(s) of media, the matrix generator406determines the elements in the matrix (e.g., the Jacobian matrix). Example machine readable instructions that may be executed to implement block508are described below in connection withFIG.6.

At block510, the example commercial solver(s)408determines(s) Lagrange multipliers λs. For example, the commercial solver(s)408solve(s) for (e.g., determines) the Lagrange multipliers using Equations 8 based on the panelist data (obtained at block502), the tree structure association data (generated at block504), and the matrix (e.g., the Jacobian matrix) (generated at block508) stored in the local memory410(FIG.4).

At block512, the example commercial solver(s)408(FIG.4) estimate the deduplicated audience total for the one or more of the margins and/or unions (e.g., A, B, C, AB, ABC) based on the determined Lagrange multipliers λs determined at block510. The example instructions ofFIG.4end.

FIG.6is an example flowchart506representative of example machine readable instructions that may be executed by a processor to implement the example audience size determiner120ofFIGS.1and/or4to identify estimated probabilities associated with each margin(s) and/or union(s) of margin. In the illustrated example, the estimated probabilities represent a probability associated with a likelihood that an audience member accessed and/or otherwise was exposed to a margin and/or union of margins. The instructions ofFIG.6may be used to implement block506ofFIG.5. The example flowchart506is described in conjunction with the example marginal and union total audience size data200ofFIG.2. However, the example flowchart506may be implemented in conjunction with any panelist data, census data, margins, and/or unions.

At block602, the example probability manager404identifies the current estimate of the Lagrange multipliers. For example, initially the Lagrange multipliers may be zero. However, after an initial iteration (e.g., executing Equations 1-8), the probability manager404may determine non-zero values for the estimated Lagrange multipliers.

At block604, the example probability manager404utilizes the estimated Lagrange multipliers to compute estimated probabilities associated with the margin(s) and/or union(s) of media. For example, the probability manager404may determine an estimated probability for each node in the tree structure association300(FIG.3) (e.g., margins A, B, and/or C, and/or unions AB, and/or ABC). The example instructions ofFIG.6then end and control returns to block508ofFIG.5.

FIG.7is an example flowchart508representative of example machine readable instructions that may be executed by a processor to implement the example audience size determiner120ofFIGS.1and/or4to generate a matrix (e.g., the Jacobian matrix) based on estimated probabilities. The example instructions ofFIG.7may be used to implement block508ofFIG.5. The example flowchart508is described in conjunction with the example marginal and union total audience size data200ofFIG.2. However, the example flowchart508may be described in conjunction with any panelist data, census data, margins, and/or unions.

At block702, the matrix generator406(FIG.4) selects an element of the matrix (e.g., the Jacobian matrix) having example jth and kth index values. For example, each element in the matrix (e.g., the Jacobian matrix) is associated with a unique combination of jth and kth index values. Such an element is selected by the matrix generator406.

At block704, the matrix generator406determines whether the jth index value equals the kth index value for the selected element. For example, the matrix generator406performs this comparison of the jth and kth index values to determine whether the element to be analyzed is a diagonal element in the matrix (e.g., the Jacobian matrix). In response to the matrix generator406determining the jth and kth index values are equivalent (e.g., the control of block704returns a result of YES), control proceeds to block708. The control of block708is explained below. Alternatively, in response to the matrix generator406determining the jth index values does not equal the kth index value (e.g., the control of block704returns a result of NO), control proceeds to block706in which the matrix generator406determines whether the node associated with the jth index value of the element is a descendant of the node associated with the kth index value. As used herein, an element refers to an element in the matrix (e.g., the Jacobian Matrix) associated with jth and kth index values. Furthermore, a node corresponds to a node in a tree structure association (e.g., the tree structure association300ofFIG.3) associated with a corresponding index value. Thus, an element having jth and kth index values (e.g., the element (1,2) in a Jacobian matrix) is associated with nodes in the tree structure association having index values equivalent to the jth and kth index values (e.g., a first node having an index value of 1 and a second node having an index value of 2).

In response to the matrix generator406determining the node associated with the jth index value of the element is a descendant of the node associated with the kth index value (e.g., the control of block706returns a result of YES), control proceeds to block710. Alternatively, in response to the matrix generator406determining the node associated with the jth index value of the element is not a descendant of the node associated with the kth index value (e.g., the control of block706returns a result of NO), control proceeds to block712. The control of blocks710and712are explained below.

At block708, the matrix generator406selects a value equivalent to the sum of probabilities associated with a node having the same index value as the jth or kth index values. For example, if the jth index value is one, the matrix generator406may identify the estimated sum of probabilities associated with the node having an index value of one (e.g., node A). Accordingly, the sum of probabilities associated with the node having an index value of one may be stored in the element. Furthermore, the matrix generator406may execute Equations 15-18, above, to select a value equivalent to the sum of probabilities associated with a node having the same index value as the jth or kth index values. Control proceeds to block714responsive to execution of the control illustrated in block708.

At block710, the matrix generator406selects a value equivalent to the sum of probabilities associated with a node having the same index value as the jth index value. For example, if the jth index value is one, the matrix generator406may identify the estimated sum of probabilities associated with the node having an index value of one (e.g., margin A). Accordingly, the sum of probabilities associated with the node having an index value of one may be stored in the element. Furthermore, the matrix generator406may execute Equations 19-21, above, to select a value equivalent to the sum of probabilities associated with a node having the same index value as the jth index value. Control proceeds to block714responsive to execution of the control illustrated in block710.

At block712, the matrix generator406selects a value equivalent to the sum of probabilities associated with a node having the same index value as the jth index value and a node having the same index value as the kth index value. For example, the matrix generator406may store a value equivalent to a sum of: (1) probabilities associated with a node having the same index value as the jth index value and (2) probabilities associated with a node having the same index value as the kth index value. Furthermore, the matrix generator406may execute Equations 22-24 or Equations 25-32 above to select a value equivalent to the sum of probabilities associated with a node having the same index value as the jth index value and a node having the same index value as the kth index value. Control proceeds to block714responsive to execution of the control illustrated in block708.

At block714, the matrix generator406stores the value in the selected element. Responsive to the execution of the control executed in block714, control proceeds to block716.

At block716, the matrix generator406determines whether there are additional elements to identify. In response to the matrix generator406determining there are additional elements to identify (e.g., the control of block716returns a result of YES), control returns to block702. Alternatively, in response to the matrix generator406determining there are not additional elements to identify (e.g., the control of block716returns a result of NO), the instructions ofFIG.7end and control returns to block510ofFIG.5.

FIG.8is a block diagram of an example processor platform800structured to execute the instructions ofFIGS.5,6, and/or7to implement the audience size determiner120ofFIGS.1and/or4. The processor platform800can be, for example, a server, a personal computer, a workstation, a self-learning machine (e.g., a neural network), a mobile device (e.g., a cell phone, a smart phone, a tablet such as an iPad™), a personal digital assistant (PDA), an Internet appliance, or any other type of computing device.

The processor platform800of the illustrated example includes a processor812. The processor812of the illustrated example is hardware. For example, the processor812can be implemented by one or more integrated circuits, logic circuits, microprocessors, GPUs, DSPs, or controllers from any desired family or manufacturer. The hardware processor may be a semiconductor based (e.g., silicon based) device. In this example, the processor implements the example interface(s)400, the example association controller402, the example probability manager404, the example matrix generator406, the example commercial solver(s)408, the example local memory410, and/or, more generally, the example audience size determiner120ofFIG.4.

The processor platform800of the illustrated example also includes an interface circuit820. The interface circuit820may be implemented by any type of interface standard, such as an Ethernet interface, a universal serial bus (USB), a Bluetooth® interface, a near field communication (NFC) interface, and/or a PCI express interface.

In the illustrated example, one or more input devices822are connected to the interface circuit820. The input device(s)822permit(s) a user to enter data and/or commands into the processor812. The input device(s) can be implemented by, for example, an audio sensor, a microphone, a camera (still or video), a keyboard, a button, a mouse, a touchscreen, a track-pad, a trackball, isopoint and/or a voice recognition system.

The processor platform800of the illustrated example also includes one or more mass storage devices828for storing software and/or data. Examples of such mass storage devices828include floppy disk drives, hard drive disks, compact disk drives, Blu-ray disk drives, redundant array of independent disks (RAID) systems, and digital versatile disk (DVD) drives.

The machine executable instructions832ofFIGS.5,6, and/or7may be stored in the mass storage device828, in the volatile memory814, in the non-volatile memory816, and/or on a removable non-transitory computer readable storage medium such as a CD or DVD.

From the foregoing, it will be appreciated that example methods, apparatus and articles of manufacture have been disclosed that estimate large scale audience deduplication. The disclosed methods, apparatus and articles of manufacture improve the efficiency of using a computing device by generating a matrix using a sum of probabilities obtained from a tree graph association or tree structure association for the margin(s) and union(s). In this manner, the matrix can be utilized to efficiently calculate one or more Lagrange multipliers. The disclosed methods, apparatus, and articles of manufacture generate the matrix using significantly less processing power than prior techniques, thereby improving the functioning of a computer. For example, rather than computing the matrix by solving a large number of partial derivative equations, examples disclosed herein utilize algebraic functions based on a sum of one or more probabilities associated with one or more nodes in a tree structure association. The disclosed methods, apparatus and articles of manufacture are accordingly directed to one or more improvement(s) in the functioning of a computer.

Example methods, apparatus, systems, and articles of manufacture to estimate large scale audience deduplication are disclosed herein. Further examples and combinations thereof include the following:

Example 1 includes an apparatus comprising an association controller to generate a tree structure association for a total audience size that accessed a plurality of media items, the tree structure association including a first node representative of a first media item accessed by first audience members of the total audience size and a second node representative of a second media item accessed by second audience members of the total audience size, a matrix generator to generate a matrix by selecting a sum of probabilities value corresponding to the tree structure association, the sum of probabilities value representative of a probability of the first audience members accessing the first media item, and storing the sum of probabilities value in an element of the matrix, and a commercial solver to estimate a deduplicated audience size of the total audience size using the matrix.

Example 2 includes the apparatus of example 1, wherein the first node includes a first index value, the second node includes a second index value, and the element includes a third index value and a fourth index value.

Example 3 includes the apparatus of example 2, wherein, when the third index value of the element equals the fourth index value of the element, the sum of probabilities value corresponds to the first node when the first index value of the first node equals the third index value of the element, and the second node when the second index value of the second node equals the fourth index value of the element.

Example 4 includes the apparatus of example 2, wherein the tree structure association further includes a union node representative of a union of the first node and the second node, the union node having a fifth index value, and when (1) the third index value of the element equals the fifth index value of the union, and (2) the fourth index value of the element equals the first index value of the first node, the sum of probabilities value corresponds to the first node.

Example 5 includes the apparatus of example 2, wherein, when the third index value of the element equals the first index value of the first node, the fourth index value of the element equals the second index value of the second node, the sum of probabilities value is equivalent to a quotient of a second sum of probabilities value of the first node multiplied by a third sum of probabilities value of the second node, and a fourth sum of probabilities value of an ancestor node of the first node and the second node.

Example 6 includes the apparatus of example 1, wherein the commercial solver is to determine Lagrange multipliers using the matrix.

Example 7 includes the apparatus of example 6, wherein the commercial solver is to use the Lagrange multipliers to solve a maximum entropy problem to estimate the deduplicated audience size.

Example 8 includes a non-transitory computer readable storage medium comprising instructions which, when executed, cause at least one processor to at least generate a tree structure association for a total audience size that accessed a plurality of media items, the tree structure association including a first node representative of a first media item accessed by first audience members of the total audience size and a second node representative of a second media item accessed by second audience members of the total audience size, generate a matrix by selecting a sum of probabilities value corresponding to the tree structure association, the sum of probabilities value representative of a probability of the first audience members accessing the first media item, and storing the sum of probabilities value in an element of the matrix, and determine a deduplicated audience size of the total audience size using the matrix.

Example 9 includes the computer readable storage medium of example 8, wherein the first node includes a first index value, the second node includes a second index value, and the element includes a third index value and a fourth index value.

Example 10 includes the computer readable storage medium of example 9, wherein the instructions, when executed, cause the at least one processor to, when the third index value of the element equals the fourth index value of the element, select the sum of probabilities value as corresponding to the first node when the first index value of the first node equals the third index value of the element, and the second node when the second index value of the second node equals the fourth index value of the element.

Example 11 includes the computer readable storage medium of example 9, wherein the instructions, when executed, cause the at least one processor to generate the structure association further including a union node representative of a union of the first node and the second node, the union node having a fifth index value, when (1) the third index value of the element equals the fifth index value of the union, and (2) the fourth index value of the element equals the first index value of the first node, select the sum of probabilities value as corresponding to the first node.

Example 12 includes the computer readable storage medium of example 9, wherein the instructions, when executed, cause the at least one processor to, when the third index value of the element equals the first index value of the first node and the fourth index value of the element equals the second index value of the second node, select the sum of probabilities value as equivalent to a quotient of a second sum of probabilities value of the first node multiplied by a third sum of probabilities value of the second node, and a fourth sum of probabilities value of an ancestor node of the first node and the second node.

Example 13 includes the computer readable storage medium of example 9, wherein the instructions, when executed, cause the at least one processor to determine Lagrange multipliers using the matrix.

Example 14 includes the computer readable storage medium of example 13, wherein the instructions, when executed, cause the at least one processor to use the Lagrange multipliers to solve a maximum entropy problem for use in determining the deduplicated audience size.

Example 15 includes a method comprising generating a tree structure association for a total audience size that accessed a plurality of media items, the tree structure association including a first node representative of a first media item accessed by first audience members of the total audience size and a second node representative of a second media item accessed by second audience members of the total audience size, generating a matrix by selecting a sum of probabilities value corresponding to the tree structure association, the sum of probabilities value representative of a probability of the first audience members accessing the first media item, and storing the sum of probabilities value in an element of the matrix, and determining a deduplicated audience size of the total audience size using the matrix.

Example 16 includes the method of example 15, wherein the first node includes a first index value, the second node includes a second index value, and the element includes a third index value and a fourth index value.

Example 17 includes the method of example 16, further including, when the third index value of the element equals the fourth index value of the element, selecting the sum of probabilities value as corresponding to the first node when the first index value of the first node equals the third index value of the element, and the second node when the second index value of the second node equals the fourth index value of the element.

Example 18 includes the method of example 16, further including generating the structure association further including a union node representative of a union of the first node and the second node, the union node having a fifth index value, when (1) the third index value of the element equals the fifth index value of the union, and (2) the fourth index value of the element equals the first index value of the first node, selecting the sum of probabilities value as corresponding to the first node.

Example 19 includes the method of example 16, further including, when the third index value of the element equals the first index value of the first node and the fourth index value of the element equals the second index value of the second node, selecting the sum of probabilities value as equivalent to a quotient of a second sum of probabilities value of the first node multiplied by a third sum of probabilities value of the second node, and a fourth sum of probabilities value of an ancestor node of the first node and the second node.

Example 20 includes the method of example 16, further including determining Lagrange multipliers using the matrix.

Example 21 includes the method of example 20, further including using the Lagrange multipliers to solve a maximum entropy problem for use in determining the deduplicated audience size.

Example 22 includes an apparatus comprising means for controlling to generate a tree structure association for a total audience size that accessed a plurality of media items, the tree structure association including a first node representative of a first media item accessed by first audience members of the total audience size and a second node representative of a second media item accessed by second audience members of the total audience size, means for generating a matrix to select a sum of probabilities value corresponding to the tree structure association, the sum of probabilities value representative of a probability of the first audience members accessing the first media item, and store the sum of probabilities value in an element of the matrix, and means for determining a deduplicated audience size of the total audience size using the matrix.

Example 23 includes the apparatus of example 22, wherein the first node includes a first index value, the second node includes a second index value, and the element includes a third index value and a fourth index value.

Example 24 includes the apparatus of example 23, wherein the means for generating is to, when the third index value of the element equals the fourth index value of the element, select the sum of probabilities value as corresponding to the first node when the first index value of the first node equals the third index value of the element, and the second node when the second index value of the second node equals the fourth index value of the element.

Example 25 includes the apparatus of example 23, wherein the means for controlling is to generate the structure association further including a union node representative of a union of the first node and the second node, the union node having a fifth index value, and wherein the means for generating is to when (1) the third index value of the element equals the fifth index value of the union, and (2) the fourth index value of the element equals the first index value of the first node, select the sum of probabilities value as corresponding to the first node.

Example 26 includes the apparatus of example 23, wherein the means for generating is to, when the third index value of the element equals the first index value of the first node and the fourth index value of the element equals the second index value of the second node, select the sum of probabilities value as equivalent to a quotient of a second sum of probabilities value of the first node multiplied by a third sum of probabilities value of the second node, and a fourth sum of probabilities value of an ancestor node of the first node and the second node.

Example 27 includes the apparatus of example 23, wherein the means for determining the estimated audience deduplication size is to determine Lagrange multipliers using the matrix.

Example 28 includes the apparatus of example 27, wherein the means for generating is to solve a maximum entropy problem for use in determining the deduplicated audience size.