System and Method for Efficiently Evaluating Complex Boolean Expressions

• US 20110225038A1
• Filed: 03/15/2010
• Published: 09/15/2011
• Est. Priority Date: 03/15/2010
• Status: Abandoned Application

• Current Assignee: Excalibur IP, LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Vassilvitskii, Serguel, Zien, Jason, Shanmugasundaram, Jayavel, Vee, Erik, Fontoura, Marcus
• Application Number:
  US12/724,415
• Publication Number:
  US 20110225038A1
• Time in Patent Office: Days
• US Class Current: 705/14.49
• CPC Class Codes: G06F 16/24561 Intermediate data storage techniques for performance improvement
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0251 Targeted advertisements

Abstract

An improved system and method for efficiently evaluating complex Boolean expressions is provided. Leaf nodes of Boolean expression trees for objects represented by Boolean expressions of attribute-value pairs may be assigned a positional identifier that indicates the position of a node in the Boolean expression tree. The positional identifiers of each object may be indexed by attribute-value pairs of the leaf nodes of the Boolean expression trees in an inverted index. Given an input set of attribute-value pairs, a list of positional identifiers for leaf nodes of virtual Boolean expression trees may be found in the index matching the attribute-value pairs of the input set. The list of positional identifiers of leaf nodes may be sorted in order by positional identifier for each contract. An expression evaluator may then verify whether a virtual Boolean expression tree for each contract is satisfied by the list of positional identifiers.

Claims

1. A computer system for evaluating Boolean expressions, comprising:

an index search engine that accesses an index by each of a plurality of attribute-value pairs to retrieve a plurality of positional identifiers for the plurality of attribute-value pairs to find a plurality of objects each represented by a Boolean expression of at least one of the plurality of attribute-value pairs, each of the plurality of positional identifiers indicating a position of a node in a plurality of virtual Boolean expression trees that each encode the plurality of objects each represented by the Boolean expression of the at least one of the plurality of attribute-value pairs;

an expression evaluator operably coupled to the index search engine that determines whether the plurality of positional identifiers found in the index for the plurality of attribute-value pairs satisfy a virtual Boolean expression tree of at least one of the plurality of objects; and

a storage operably coupled to the index search engine that stores the index with each of the plurality of positional identifiers for each of the plurality of attribute-value pairs in sorted order by at least one object identifier of the plurality of objects.

2. The system of claim 1 further comprising an index builder operably coupled to the storage that generates the index with each of the plurality of positional identifiers for each of the plurality of attribute-value pairs in sorted order by the at least one object identifier of the plurality of objects.

3. The system of claim 1 further comprising an expression annotator operably coupled to the storage that assigns each of the plurality of positional identifiers indicating the position of the node in the plurality of virtual Boolean expression trees that each encode the plurality of objects each represented by the Boolean expression of the at least one of the plurality of attribute-value pairs.

4. The system of claim 1 further comprising an advertisement serving engine operably coupled to the storage that serves one or more advertisements of at least one of a plurality of advertisement contracts encoded as one of the plurality of objects with the plurality of positional identifiers indicating the position of the node in the plurality of virtual Boolean expression trees for which the plurality of positional identifiers found in the index for the plurality of attribute-value pairs satisfy the virtual Boolean expression tree of the at least one of the plurality of objects.

5. The system of claim 4 further comprising a web browser operably coupled to the advertisement serving engine that displays at a web page location on a client device the one or more advertisements of the plurality of advertisement contracts that match the Boolean expression of the plurality of feature-value pairs.

6. A computer-implemented method for evaluating Boolean expressions, comprising:

receiving a plurality of attribute-value pairs;

retrieving a plurality of positional identifiers for the plurality of attribute-value pairs from an index accessed by each of the plurality of attribute-value pairs, each of the plurality of positional identifiers indicating a position of a node in a plurality of virtual Boolean expression trees that each encode a plurality of objects each represented by a Boolean expression of at least one of the plurality of attribute-value pairs;

verifying that at least one of the plurality of positional identifiers satisfy a virtual Boolean expression tree of at least one of the plurality of objects from the plurality of the virtual Boolean expression trees that encode each of the plurality of objects; and

outputting the identification of the at least one of the plurality of objects.

7. The method of claim 6 further comprising accessing the index by each of the plurality of attribute-value pairs to retrieve the plurality of positional identifiers for the plurality of attribute-value pairs.

8. The method of claim 6 further comprising sorting the plurality of positional identifiers in order by value of each of the plurality of positional identifier for each of the plurality of objects.

9. The method of claim 6 wherein verifying that the at least one of the plurality of positional identifiers satisfy the virtual Boolean expression tree of the at least one of the plurality of objects from the plurality of the virtual Boolean expression trees that encode each of the plurality of objects comprises evaluating a node of the virtual Boolean expression tree assigned a logical conjunction.

10. The method of claim 9 wherein evaluating the node of the virtual Boolean expression tree assigned the logical conjunction comprises recursively invoking a first routine for evaluating a child node of the virtual Boolean expression tree assigned a logical disjunction.

11. The method of claim 10 wherein evaluating the child node of the virtual Boolean expression tree assigned the logical disjunction comprises recursively invoking a second routine to evaluate a grandchild node of the virtual Boolean expression tree assigned another logical conjunction.

12. The method of claim 6 wherein verifying that the at least one of the plurality of positional identifiers satisfy the virtual Boolean expression tree of the at least one of the plurality of objects from the plurality of the virtual Boolean expression trees that encode each of the plurality of objects comprises evaluating a plurality of nodes of the virtual Boolean expression tree assigned a logical conjunction and a plurality of node of the virtual Boolean expression tree assigned a logical disjunction.

13. The method of claim 6 further comprising serving at least one advertisement of a plurality of advertisement contracts encoded with the plurality of positional identifiers each indicating the position of the node in the plurality of virtual Boolean expression trees for which at least one of the plurality of positional identifiers satisfy a virtual Boolean expression tree.

14. The method of claim 6 further comprising receiving the plurality of objects each represented by the Boolean expression of the at least one of the plurality of attribute-value pairs and generating a Boolean expression tree with at least one leaf node of the at least one of the plurality of attribute-value pairs for each of the plurality of objects from the Boolean expression of the at least one of the plurality of attribute-value pairs.

15. The method of claim 14 further comprising assigning at least one of the positional identifiers to the at least one leaf node of the at least one of the plurality of attribute-value pairs for the Boolean expression tree.

16. The method of claim 15 further comprising indexing the at least one of the positional identifiers in the index by the at least one of the plurality of attribute-value pairs of the at least one leaf nodes of the Boolean expression tree.

17. The method of claim 14 wherein receiving the plurality of objects each represented by the Boolean expression of the at least one of the plurality of attribute-value pairs comprises receiving a plurality of advertising contracts each represented by the Boolean expression of the at least one of the plurality of attribute-value pairs.

18. A computer-readable storage medium having computer-executable instructions for performing the method of claim 6.

19. A computer system for evaluating Boolean expressions, comprising:

means for indexing a plurality of positional identifiers assigned to a plurality of nodes in a plurality of virtual Boolean expression trees that each encode a plurality of objects each represented by a Boolean expression of a plurality of attribute-value pairs;

means for receiving at least one of the plurality of attribute-value pairs;

means for retrieving at least one of the plurality of positional identifiers for the at least one of the plurality of attribute-value pairs from an index;

means for verifying that the at least one of the plurality of positional identifiers satisfy at least one virtual Boolean expression tree of the plurality of virtual Boolean expression trees that each encode the plurality of objects each represented by the Boolean expression of the plurality of attribute-value pairs; and

means for outputting the identification of at least one of the plurality of objects for which the at least one of the plurality of positional identifiers that satisfy the at least one virtual Boolean expression tree.

20. The computer system of claim 19 further comprising:

means for selecting at least one of a plurality of advertisements from verifying that the at least one of the plurality of positional identifiers satisfy the at least one virtual Boolean expression tree of the plurality of virtual Boolean expression trees that each encode the plurality of objects each represented by the Boolean expression of the plurality of attribute-value pairs; and

means for serving the at least one of the plurality of advertisements for display on a client device.