Ad insertion in automatically composed documents

Niranjan Damera-Venkata, José BentoACM Symposium on Document Engineering 2012 · DOI

TL;DR

This paper tackles the challenge of automatically inserting advertisements into machine-composed documents, focusing on the fundamental tradeoff between maximizing ad revenue and maintaining document quality. They introduce the concept of an "efficient-frontier" to represent this optimal tradeoff and develop algorithms for both "ad-pull" (ads selected before composition) and "ad-push" (ads inserted after composition) business models.

What Problem Does This Paper Address?

Traditionally, high-quality document design, especially for personalized content, is expensive due to manual graphic design. With the rise of personalized content, publishers want to leverage advertisements for revenue. However, simply inserting ads can degrade document quality (e.g., by shrinking content or increasing whitespace). Conversely, sometimes ads can even improve quality by filling awkward empty spaces. This paper addresses the core problem of how to automatically insert ads in a way that balances these competing goals: maximizing revenue while preserving or even enhancing document aesthetics and readability. They frame this as finding an optimal "efficient-frontier" in the revenue-quality space.

Methods

The authors propose a Probabilistic Document Model (PDM), a Bayesian network that models designer choices in document layout. This model is extended to incorporate advertisements. For ad insertion, they define two main scenarios:

  • Ad-Pull: Advertisers bid on ad placements, creating an ad pool. The algorithm then selects ads from this pool and composes documents that lie on the efficient-frontier. This involves complex combinatorial optimization to select subsets of ads and their order.
  • Ad-Push: Document composition happens first, creating ad "slots" or inventory. The algorithm then estimates ad prices and determines the optimal placement and size of these slots to maximize expected revenue while maintaining quality. This approach is shown to be more computationally efficient.

Both approaches utilize dynamic programming and algorithms similar to the "skyline" or "maximal vector" computation to efficiently determine the efficient-frontier. They also introduce the concept of a "stochastic efficient-frontier" to represent average revenue and quality across multiple subscribers, achieved by averaging over different document compositions.

Datasets

Not discussed in the paper. The paper uses synthetic examples and discusses the structure of the problem rather than relying on specific datasets.

Key Insights and Ideas

  • Revenue vs. Quality Tradeoff: The central insight is that there's an inherent, quantifiable tradeoff between ad revenue and document quality. This isn't a simple linear relationship but can be visualized as an "efficient-frontier."
  • Efficient-Frontier: This concept, borrowed from finance, represents the set of optimal document compositions where you can't increase revenue without decreasing quality, or vice-versa.
  • Ad-Pull vs. Ad-Push: The paper highlights that the "ad-push" model (composing first, then selling slots) is generally more computationally efficient for finding optimal ad placements compared to the "ad-pull" model (selling first, then composing based on bids).
  • Stochastic Frontier: For publishers serving many subscribers, averaging across different compositions (stochastic composition) can create a continuous, convex efficient-frontier, offering more flexibility.
  • Quality as Probability: Document quality is modeled probabilistically, where higher probability indicates better aesthetic choices and content fit.

Key Results

The paper presents algorithms for computing the efficient-frontier for both ad-pull and ad-push scenarios. They demonstrate through examples (Figures 4, 6) how their algorithms can generate document compositions that lie on this frontier, showing how revenue increases as quality drops. They also show examples of "inefficient" compositions that are dominated by frontier compositions. The complexity analysis suggests that the ad-push model scales better with increasing ad density than the ad-pull model.

Limitations and Future Work

  • Ad-Pull Complexity: The ad-pull algorithm's complexity grows combinatorially with the number of ads, making it potentially prohibitive for large ad pools. Heuristic algorithms are suggested as a practical alternative.
  • Quality Definition: While the PDM models aesthetic quality, the authors suggest expanding the notion of quality to include relevance of ads to the target audience (e.g., keyword relevance).
  • Keyword-Based Bidding: Future work could explore advertisers bidding on keywords within documents, similar to current internet advertising models, enabling dynamic ad insertion based on content.
  • Unsold Inventory (Ad-Push): The ad-push model faces the challenge of potential unsold ad inventory, which might require filler content.

Summary updated

BibTeX
@inproceedings{dameravenkata2012ad,
  author = {Niranjan Damera-Venkata and José Bento},
  title = {{Ad insertion in automatically composed documents}},
  booktitle = {ACM Symposium on Document Engineering},
  year = {2012},
  doi = {10.1145/2361354.2361358},
}

Loading related content...

Figure