Browse Prior Art Database

Method and System for Constraint based Partitioning of a Set of Advertisements

IP.com Disclosure Number: IPCOM000199154D
Publication Date: 2010-Aug-27
Document File: 5 page(s) / 136K

Publishing Venue

The IP.com Prior Art Database

Related People

Pei Ouyang: INVENTOR [+3]

Abstract

Disclosed is a method and system for constraint based partitioning of a set of advertisements.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 42% of the total text.

Method and System for Constraint based Partitioning of a Set of Advertisements

Abstract

Disclosed is a method and system for constraint based partitioning of a set of advertisements.

Description

A method and system for constraint based partitioning of a set of advertisements is disclosed.

Each advertisement has a set of associated constraints for demographic targeting, behavior targeting and geo-targeting.  When an advertisement request is received with user cookies, the user cookies are evaluated with respect to the constraints and advertisements with the constraints satisfying the user cookies are delivered. Each time an advertisement is delivered, a goal which is a measure of the number of impressions is updated. Generally, the set advertisements are sorted based on the goal and an appropriate advertisement is scanned for based on the associated constraints. However, when the number of advertisements is large, scanning the set of advertisements is a challenge.

Accordingly, the method and system disclosed herein partitions the set of advertisements into multiple priority queues based on their associated constraints. It is ensured that advertisement in a priority queue of the multiple priority queues have a common constraint called a gating constraint. An advertisement-server scans each of the priority queues by first evaluating the common constraint associated with a queue. If the constraint is not satisfied, then none of the advertisements in the priority queue are selected.  For example, a priority queue may contain advertisements with an age constraint from 20 to 30. The priority queue may also contain advertisements with additional constraints. For example, there may be another advertisement with an additional constraint as short-term interest in automobiles, in addition to the age constraint. In this case, when an advertisement request is from a user whose age is not between 20 and 30, all the advertisements in this priority queue can be skipped.

A constraint corresponding to an advertisement is modeled as an acyclic directed graph. For example, an age constraint may be specified as age (20,30), which depicts that age group of a user should be between 20 and 30 years for displaying an advertisement. Accordingly, graph representation is as shown in Fig. 1.

Figure 1

Similarly an advertisement with two constraints joined by an ‘AND’ operator may be represented as shown in Fig. 2. In this case, combined constraint is that age should be between 20 and 30 years, and the user is from NY, TX or CA.

Figure 2

The constraint illustrated in Fig. 2 is evaluated as follows:

  • The left child of the ‘AND’ node is evaluated to TRUE or FALSE.
  • Similarly, the right child of the ‘AND’ node is evaluated to TRUE or FALSE.
  • The ‘AND’ node gives TRUE if both children are TRUE.  Otherwise, it gives FALSE.

An advertisement has a reference or a pointer to a root node of its associated constraint graph.  The constraint graph which is used by two o...