Browse Prior Art Database

Method and System for supporting Sub-Queries in Boolean Expression Indexing

IP.com Disclosure Number: IPCOM000197529D
Publication Date: 2010-Jul-13
Document File: 2 page(s) / 18K

Publishing Venue

The IP.com Prior Art Database

Related People

Srihari Venkatesan: INVENTOR [+7]

Abstract

A method and system for supporting sub-queries in Boolean expression indexing is disclosed. The method involves modeling an opportunity as a query, with sub-queries i.e., one sub-query per Ad slot thereby reducing the computation.

This text was extracted from a Microsoft Word document.
This is the abbreviated version, containing approximately 53% of the total text.

Method and System for supporting Sub-Queries in Boolean Expression Indexing

Abstract

A method and system for supporting sub-queries in Boolean expression indexing is disclosed.  The method involves modeling an opportunity as a query, with sub-queries i.e., one sub-query per Ad slot thereby reducing the computation.

Description

Disclosed is a method and system for supporting sub-queries in Boolean expression indexing.  The method involves modeling an opportunity as a query, with sub-queries i.e., one sub-query per Ad slot thereby reducing the computation.

Typically in display advertising, consider an opportunity where a visited page has two ad slots, and the user is a male in California.  Then a following query may be issued:

Gender=Male, Geo=CA, (SlotSize=300x300 Position = 1), (SlotSize=100x200 Position = 2)

The query may be broken down into two independent queries as follows:

Gender=Male, Geo=CA, SlotSize=300x300
Gender=Male, Geo=CA, SlotSize=100x200

In this case, there is one query per Ad slot.

However, the disclosed method evaluates this opportunity query in one pass, as a single query.  The method can be applied for the "page view" support in display advertising systems, where each opportunity can be viewed as a single query, as opposed to one query per ad slot. Thus, page view queries are executed at once to reduce overall throughput.

In this method, the queries generated are a list of pairs (fid, bitmap) where the bitmap indicates the positions for which feature applies.  In the case of the position independent features (such as, targeting), all position bits may be set.  Further, for the position dependent features (such as, size and delivery mode), only the appropriate position bit may be set.

A WAND algorithm is used for query evaluation, as described in [1]. During evaluation, while counting and finding a match, an AND operation is performed on the bitmaps for the K features that matched.  In this case, K is the size of the conjunction.  Thus, when the resulting bitmap is non-zero, the method provides a real match.  Thereafter, the method adds the AND operation performed on the bitmap to the list to be processed by the interval.  The method then generates a list of contract id, begin, end, bitmap.
Thereafter, the method utilizes an interval algorithm [2], to extend the fron...