Rule processing method, apparatus, and computer-readable medium to generate valid combinations for selection

• US 7,587,380 B2
• Filed: 09/28/2004
• Issued: 09/08/2009
• Est. Priority Date: 09/29/2003
• Status: Active Grant

• Current Assignee: Mineral Lassen LLC (Intellectual Ventures LLC)
• Original Assignee: Verde Sabor Assets LLC (Intellectual Ventures LLC)
• Inventors: Mair, Douglas M., Huelsman, David L., Love, Sharon E.
• Primary Examiner(s): Vincent; David R
• Assistant Examiner(s): Wong; Lut
• Application Number:
  US10/950,809
• Publication Number:
  US 20050080648A1
• Time in Patent Office: 1,806 Days
• Field of Search: 706/47
• US Class Current: 706/47
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions

Abstract

A method of providing, in response to user-selected ones of attributes and/or enumerations thereof, a list of product choices from products whose compatibility is characterized by a ZDD rule model having one or more Include and Exclude ZDDs. The method comprises creating a ZDD sub-tree by scanning the Include ZDDs and keeping paths having the selected enumerations set, determining complete paths through the sub-tree to produce potentially valid combinations, checking the potentially valid combinations against the Exclude ZDDs to exclude invalid combinations, and providing resulting valid combinations. The scanning optionally includes examining nodes of the Include ZDDs or of the sub-tree against Index values of the selected enumerations to create nodes in the sub-tree. Other aspects include an apparatus implementing the method, and a computer-readable medium including program instructions enabling a processing device to perform the method.

Claims

1. A computer-implemented method, comprising:

characterizing compatibility between one or more enumerations of one or more products using a Zero-suppressed binary Decision Diagram (ZDD) rule model including one or more Include rules and one or more Exclude rules;

receiving one or more enumerations of a product selected by a user using a graphical interface;

recursively creating a ZDD sub-tree by scanning the one or more Include rules and, for nodes traversed during the scanning, one or more of;

if an index matches one of the one or more enumerations of the product selected by the user or if the index matches one or more valid combinations of one or more enumerations of the product provided to the user, creating a new node in a ZDD sub-tree that includes the index and one or more graphs pointed to by the Then and Else legs of the node;

if a Constant node is encountered, returning the constant;

or

returning one or more graphs pointed to by the Else leg of the node;

determining complete paths through the ZDD sub-tree terminating at a One node to produce potentially valid combinations;

excluding some of the potentially valid combinations by applying the one or more Exclude rules to the potentially valid combinations as each of the potentially valid combinations is produced;

determining the one or more valid combinations of one or more enumerations of the product responsive to the excluding the some of the potentially valid combinations; and

providing the one or more valid combinations as the list of product choices to the user.

2. The computer-implemented method of claim 1, where the providing includes displaying at least some of the list of product choices on a display monitor.

3. The computer-implemented method of claim 1, where each of the potentially valid combinations includes ones of the nodes of the ZDD sub-tree on a respective one of the complete paths.

4. The method of claim 1 where determining complete paths through the ZDD sub-tree includes bookmarking potentially valid combinations by creating a collection of indexes on the complete paths of the ZDD sub-tree.

5. A system to provide a list of product choices from products whose compatibility is characterized by a Zero-suppressed binary Decision Diagram (ZDD) rule model having one or more Include rules and one or more Exclude rules, the apparatus comprising:

an input device to aid a user in selecting, from a list of attributes or enumerations of the products, a particular one or more of the enumerations;

a processor to execute instructions that enable the processor to;

recursively create a ZDD sub-tree by scanning the Include rules and keeping paths including the selected particular one or more of the enumerations and, for nodes of the Include rules traversed during the scanning, one or more of;

if an index matches the selected particular one or more of the enumerations or if the index matches one or more valid ones of potentially valid combinations of a list of product choices provided to the user, creating a new node in a ZDD sub-tree that includes the index and one or more graphs pointed to by the Then and Else legs of the node;

if a Constant node is encountered, returning the constant;

or

returning one or more graphs pointed to by the Else leg of the node;

determine complete paths through the ZDD sub-tree terminating at a One node to produce potentially valid combinations; and

check the potentially valid combinations against the Exclude rules to find valid ones of the potentially valid combinations as each of the potentially valid combinations is produced; and

an output device enabled to output the valid ones of the potentially valid combinations as the list of product choices to the user.

6. The system of claim 5,

where the input device comprises at least one of a keyboard and a pointing device;

and

where the output device comprises one of a display monitor and a printer.

7. The system of claim 5, where the processor includes an identification circuit to identify each of the potentially valid combinations as ones of the nodes of the ZDD sub-tree on a respective one of the complete paths.

8. A computer-readable medium having a set of instructions stored therein which, when executed by a processing device, causes the processing device to perform procedures comprising:

characterizing compatibility between one or more enumerations of one or more products using a Zero-suppressed binary Decision Diagram (ZDD) rule model including one or more Include rules and one or more Exclude rules;

receiving one or more enumerations selected by a user using a graphical interface;

recursively creating a ZDD sub-tree by scanning the Include rules and, for nodes traversed during the scanning, one or more of;

if an index matches one of the one or more enumerations of the product selected by the user or if the index matches one or more valid ones of potentially valid combinations of product choices provided to the user, creating a new node in a ZDD sub-tree that includes the index and one or more graphs pointed to by the Then and Else legs of the node;

if a Constant node is encountered, returning the constant;

or

returning one or more graphs pointed to by the Else leg of the node;

determining complete paths through the ZDD sub-tree terminating at a One node to produce potentially valid combinations;

checking the potentially valid combinations against the Exclude rules to determine valid ones of the potentially valid combinations by excluding ones of the potentially valid combinations that are excluded under the Exclude rules as each of the potentially valid combinations is produced; and

providing the valid ones of the potentially valid combinations as the product choices to the user.

9. The computer-readable medium of claim 8, where the providing includes displaying at least some of the product choices on a display monitor.

10. The computer-readable medium of claim 8, where each of the potentially valid combinations includes ones of the nodes of the ZDD sub-tree on a respective one of the complete paths.