US007805461B2
`
`(12) United States Patent
`Gadamsetty et a].
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 7,805,461 B2
`Sep. 28, 2010
`
`(54)
`
`(75)
`
`(73)
`
`METHOD AND APPARATUS FOR DATABASE
`INDUCTION FOR CREATING FRAME BASED
`KNOWLEDGE TREE
`
`Inventors: Srikanth Gadamsetty, Nashville, TN
`(US); Rajesh Kommineni, Nashville,
`TN (US); John Russell Cook, Nashville,
`TN (US); Tim HoWland, Nashville, TN
`(Us)
`Assignee: Edgenet, Inc., Atlanta, GA (US)
`
`(*)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21)
`
`(22)
`
`(65)
`
`(63)
`
`(51)
`
`(52)
`(58)
`
`Appl. N0.: 11/733,344
`
`Filed:
`
`Apr. 10, 2007
`
`Prior Publication Data
`
`US 2007/0185900 A1
`
`Aug. 9, 2007
`
`Related US. Application Data
`
`Continuation of application No. 10/727,596, ?led on
`Dec. 5, 2003, now Pat. No. 7,219,100.
`
`Int. Cl.
`(2006.01)
`G06F 7/00
`(2006.01)
`G06F 17/30
`US. Cl. ...................... .. 707/797; 707/804; 707/805
`Field of Classi?cation Search ................... .. 707/3,
`707/100,101,102, 104.1, 7914793, 797,
`707/804, 796, 778, 805; 706/45, 57
`See application ?le for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,775,935 A 10/1988 Yourick
`5,526,522 A
`6/1996 Takeuchi
`
`(Continued)
`OTHER PUBLICATIONS
`
`Jennifer Neville, et al., Learning Relational Probability Trees, pp.
`625-630, (2003).
`Primary ExamineriDon Wong
`Assistant ExamineriMerilyn P Nguyen
`(74) Attorney, Agent, or Firmiloseph T. Leone, Esq.;
`DeWitt Ross & Stevens SC.
`
`(57)
`
`ABSTRACT
`
`An automated process (and system) for facilitating the cre
`ation of a frame based knowledge tree for use with a con?gu
`ration system is provided. In accordance with a preferred
`embodiment, a database induction module interacts with a
`user interface and a vendor provided database containing
`product information in the form of database ?les. The user
`sets induction preferences via a graphical user interface, and
`the induction module accesses product information from the
`client database ?le and automatically generates a frame based
`product knowledge tree in light of the user’s preferences,
`where the frame based product knowledge tree is intended for
`use with a con?guration system for con?guring certain
`desired products, services, or other assemblages.
`
`11 Claims, 4 Drawing Sheets
`
`I
`
`START >~300
`
`/»-~/305
`
`N
`
`AIIRIBUIES _
`IO INDUCI?
`
`END]
`
`K310
`
`‘K320
`
`USER-SPECIFIED
`SPLIIIIND
`
`AIIRIBUIES?
`
`N
`' ’
`
`r340
`
`QUERY FOR
`UNIDUE VALUES
`
`FOR EACH
`UNIQUE VALUE
`CREATE A
`NEW CHILD
`NODE
`
`* USING DOMAIN KNOWLEDGE / DISTINCT AIIRIBUIE VALUES COUNT
`
`WTS PARADIGM LLC EXHIBIT 1004
`1 of 12
`
`

`
`US 7,805,461 B2
`Page 2
`
`US. PATENT DOCUMENTS
`
`5,822,206 A 10/1998 Sebastian eta1~
`5,956,707 A
`9/1999 Chll
`6,260,048 B1
`7/2001 Carpenter et al.
`6,289,353 B1
`9/2001 Hazlehurstet a1,
`6,336,106 B1
`1/2002 Evans
`6,567,814 Bl* 5/2003 Bankieretal. ............ .. 707/101
`6,727,925 B1
`4/2004 Bourdelais
`
`6,810,401 B1 * 10/2004 Thompson et al. ........ .. 707/101
`6,865,524 B1
`3/2005 Shah etal.
`6,910,027 B2* 6/2005 Bromberg etal. ........... .. 706/46
`6,938,027 B1* 8/2005 BarritZ et al. ............... .. 706/50
`6,952,688 B1
`10/2005 Goldman etal.
`2002/0103777 A1* 8/2002 Zhang ....................... .. 706/59
`2003/0220949 A1 11/2003 Witt et al.
`2006/0041836 A1
`2/2006 Gordon eta1~
`* cited by examiner
`
`WTS PARADIGM LLC EXHIBIT 1004
`2 of 12
`
`

`
`US. Patent
`
`Sep. 28, 2010
`
`Sheet 1 of4
`
`US 7,805,461 B2
`
`,1 1o
`
`sAvED noocnon
`sEmNDg
`
`//1 15
`
`noucnoh sEmnDs
`
`
`
`./t F
`
`
`
`1/1 F
`
`= nouonon uDDuEE
`
`=
`
`ptidétDtJfétt :i?
`155/’
`
`USER INTERFACE
`100/
`
`/_A25
`- /
`_V
`DATABASE AoDEss
`MODULE
`FIG 1
`
`CLIENT DB
`W
`
`@Dotobose induction Wizard
`Product Split Questions
`Split Questions are used to creote the top-level Frames and Slots.
`Select and order the Questions by which the inducted data is
`most ef?cientty divided.
`
`[HE]
`
`Avoiioble Questions
`
`Spht Questions
`
`i
`
`?etect >>> }
`
`299
`
`2.21
`
`~~205
`Use intethgent split if compound slot om exceeds??
`
`[1 Use Domain Knowledge
`
`Qoncet
`
`< Back
`
`Eext >
`
`Hetp
`
`FIG. 2
`
`WTS PARADIGM LLC EXHIBIT 1004
`3 of 12
`
`

`
`US. Patent
`
`Sep. 28, 2010
`
`Sheet 2 of4
`
`US 7,805,461 B2
`
`(
`
`START >»-300
`
`\
`
`22/505
`
`N
`
`‘
`ATTRIBUTES
`T0 mow? ‘
`
`A
`
`K325
`NUMBER OF
`AUREBUTE VA! UFS
`L£SS THAN
`THRESHOLD?
`
`K535
`NEW
`COMPOUND
`M
`
`INTELLIGENT
`SPUHING * “330
`
`@345
`
`‘
`FOR £ACH
`UNIQUE VALU£
`CR£ATE A
`NEW CHILD
`NOD£
`
`* usmc DOMAIN KNOWLEDGE / DISTINCT ATTRIBUTE VALUES coum
`
`FIG. 3
`
`WTS PARADIGM LLC EXHIBIT 1004
`4 of 12
`
`

`
`US. Patent
`
`Sep. 28, 2010
`
`Sheet 3 of4
`
`US 7,805,461 B2
`
`“CALEGORY” FRAME V
`A
`
`K400
`FEATURE FRAME 1
`
`FEATURE FRAME 2
`
`ATERIBUTE L l
`ALERLBLNE 2
`ATERLBDTE H
`4L5!
`
`NNN
`
`500
`
`WHERE COLOR = BLUE’
`
`[/53 5
`
`WHERE COLOR = ‘BLUE’
`AND SLZE = ‘LARGE’
`
`WHERE COLOR :‘BLUE'
`AND SiZE I‘NEDLUM'
`
`x520
`
`WHERE COLOR =‘BLUE’
`AND SLZE :‘SMALL'
`
`W525
`
`K530
`WHERE COLOR = ‘BLUE’
`AND SIZE : :SNALL' I
`AND SHARE I SQUARE
`
`FIG. 5
`
`505
`R
`WHERE COLOR = ‘GREEN’
`
`WHERE COLOR =‘RED'
`510/
`
`WTS PARADIGM LLC EXHIBIT 1004
`5 of 12
`
`

`
`US. Patent
`
`Sep. 28, 2010
`
`Sheet 4 0f 4
`
`US 7,805,461 B2
`
`ROOT FRAME
`
`K600
`COLORjLUURAME
`
`COLOR = BLUE
`605/"
`
`K630
`SIZE LARGE FRAME
`
`832E I LARGE
`4
`635/
`
`F640
`SiZE MEDiUM FRAME
`
`SIZE = NEEDfUM
`
`6451 “[353
`SiZE SHAH FRAME
`
`SIZE = SMALL
`\655
`COLOR,GREEN,_,FRAME
`
`1,
`SHAPE SQUAR£ FRAME ‘
`
`SHAPE = SQUARE
`
`j COLOR = GREEN‘
`
`COLORHREDJRAME
`
`COLOR = RED
`
`625)
`
`FIG. 6
`
`WTS PARADIGM LLC EXHIBIT 1004
`6 of 12
`
`

`
`US 7,805,461 B2
`
`1
`METHOD AND APPARATUS FOR DATABASE
`INDUCTION FOR CREATING FRAME BASED
`KNOWLEDGE TREE
`
`REFERENCE TO RELATED APPLICATIONS
`
`This application is a continuation of application Ser. No.
`10/727,596, ?led Dec. 5, 2003 (now US. Pat. No. 7,219,100,
`issued May 15, 2007), which is related to application Ser. No.
`09/684,907, ?led Oct. 10, 2000 (now US. Pat. No. 6,810,401,
`issued Oct. 26, 2004), both of which are hereby incorporated
`by reference in their entireties.
`
`BACKGROUND
`
`The growing trend of mass customization in the manufac
`turing community has accentuated the importance of con?gu
`ration systems. Con?guration systems facilitate the con?gu
`ration of desired products, services, or other assemblages that
`require users to gather and assimilate disparate knowledge of
`makes, models, types, features, options, limitations, manu
`facturing constraints, etc. of a desired product/service (or
`group of the same) to be con?gured. In the manufacturing
`sector, for example, a con?guration system can reconcile the
`complexities involved with con?guring customiZable prod
`ucts that conform to certain known manufacturing con
`straints. Through the use of con?guration systems, a user can
`identify any potential manufacturing problems prior to the
`expenditure of funds.
`Typically, con?guration is facilitated through interaction
`by a user, via a user interface, with an inference engine that
`performs, for example, frame-based inferences to discern
`product knowledge stored in a knowledge base. The creation
`of the knowledge base containing the disparate product
`knowledge involves acquiring the product knowledge from
`numerous sources and encoding that knowledge using
`graphical user interface (GUI) tools.
`Such GUI tools allow the user (typically, a knowledge
`engineer) to model the product knowledge in a tree like struc
`ture where each node of the tree is known as a frame. The
`attributes that describe and specialiZe the frame are repre
`sented using slots. The node at each level in a tree inherits
`properties from its parent node(s) and allows the user to
`override, extend or specialiZe these properties at the current
`level. The level in a tree at which certain attributes are placed
`depends on the generality of those attributes. For example,
`attributes that are common to a number of con?gurable items
`are placed closer to the top of the tree. Attributes that special
`iZe a con?gurable item are placed at the lower levels of the
`tree. This process of creating a frame based knowledge tree is
`called the product knowledge design process and is imple
`mented by knowledge engineers.
`Typically, the process of creating a frame based knowledge
`tree includes the creation of product information ?les by
`acquiring the product knowledge from various product
`experts. These experts can include pricing experts, manufac
`turing process experts, product speci?cation experts, cus
`tomer service experts, etc. The process of amassing the dis
`parate product knowledge, organiZing that knowledge in
`some predetermined hierarchical system, and creating a
`frame based knowledge tree is very time consuming, cost
`intensive and requires the coordination of several individuals.
`
`SUMMARY
`
`A method for and apparatus for facilitating the creation of
`a frame based knowledge tree for use with a con?guration
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`system is provided. In accordance with a preferred embodi
`ment, a database induction module interacts with a user inter
`face and a customer-provided product database containing
`product information. The user sets induction preferences via
`the GUI, and the induction module accesses product infor
`mation from the client database ?les and automatically gen
`erates a frame based knowledge tree in light of the user’s
`preferences.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram illustrating a database induction
`system in accordance with a preferred embodiment of the
`invention;
`FIG. 2 is a screen shot of an exemplary graphical user
`interface used in the FIG. 1 database induction system in
`accordance with a preferred embodiment of the invention;
`FIG. 3 is an exemplary illustration of a ?owchart depicting
`an operational ?ow of the FIG. 1 database induction system in
`accordance with a preferred embodiment of the invention;
`FIG. 4 is an exemplary illustration of a frame tree of
`domain knowledge speci?cations in accordance with a pre
`ferred embodiment of the invention;
`FIG. 5 is an exemplary illustration of a frame tree con
`structed based on responses to SQL queries run during gen
`eration of a frame based knowledge tree in accordance with a
`preferred embodiment of the invention; and
`FIG. 6 is an exemplary illustration of a frame based knowl
`edge tree constructed in accordance with a preferred embodi
`ment of the invention.
`
`DETAILED DESCRIPTION
`
`Preferred embodiments and applications of the invention
`will be described herein. Other embodiments may be realiZed
`and structural or logical changes may be made to the embodi
`ments without departing from the spirit or scope of the inven
`tion. Although certain embodiments disclosed herein have
`beenpar‘ticularly described as applied to a knowledge base for
`speci?c exemplary products (e.g., plumbing supplies), it
`should be readily apparent that the invention may be embod
`ied to create a knowledge base for any number of products,
`services or the like.
`In accordance with a preferred embodiment of the inven
`tion, a database induction process for creating a frame based
`knowledge tree is implemented using a processor-based sys
`tem that may be supported in a stand-alone, networked, main
`frame, or client-server architecture. A single (or multiple)
`program memory module is provided for storing one or more
`computer programs used to perform the functionality
`described herein.
`In accordance with a preferred embodiment, one or more
`user interfaces are provided as part of (or in conjunction with)
`the database induction process to permit users to interact with
`one or more vendor databases and also with an induction
`module. Individual ones of a plurality of client devices (e. g.,
`network/stand-alone computers, personal digital assistants
`(PDAs), WebTV (or other Internet-only) terminals, set-top
`boxes, cellular/ PCS phones, screenphones, pagers, kiosks, or
`other known (wired or wireless) communication devices,
`etc.) may similarly be used to execute one or more computer
`programs (e.g., universal Internet browser programs, dedi
`cated interface programs, etc.) to allow users to interface with
`the vendor databases and the induction module.
`In accordance with a preferred embodiment, a user (e.g.,
`knowledge engineer, etc.) of the database induction process
`interacts with the system to create a frame based knowledge
`
`WTS PARADIGM LLC EXHIBIT 1004
`7 of 12
`
`

`
`US 7,805,461 B2
`
`3
`tree. The interaction with the system is preferably through a
`series of questions provided by the system with input answers
`provided by the user. The system may, however, support a
`variety of other methods of interaction (e.g., command
`driven, menu driven, script, etc.)
`FIG. 1 illustrates in block diagram form, a database induc
`tion system (and preferred apparatus for performing a pro
`cess) in accordance with a preferred embodiment of the
`invention. The system preferably contains a user interface
`1 00 for enabling the user to interact with an induction module
`120, in accordance with induction settings 115 speci?ed by
`the user, and also for interacting with a database access mod
`ule 125 enabling the system to access a client database 105. In
`accordance with a preferred embodiment, the induction set
`tings are also stored in memory (not shown) by the interface
`100 as saved induction settings 110 for future use.
`The database access module 125 interacts with the vendor
`database 105 to receive the disparate product knowledge that
`is to be inducted in the generated knowledge tree. The induc
`tion module 120 is preferably coupled to the product knowl
`edge output module 13 0, where the generated knowledge tree
`is con?gured as product knowledge ?les for use, for example,
`with a product con?guration system.
`In accordance with a preferred embodiment, the vendor of
`the product(s) to be con?gured provides the user (e.g., the
`knowledge engineer) with at least one database table repre
`senting speci?c information about the product(s) (e.g.,
`plumbing supplies). Below, four such database tables
`(TABLES 1-4) are described; however, the ?rst table (TABLE
`1) contains the data that is essential to the construction of the
`knowledge tree. Further, the vendor need not actively provide
`the database table(s) to the user, but, rather, the vendor need
`only make the underlying data for the table(s) available to the
`user via the client database 105.
`With reference to TABLE 1, a data table is depicted as
`containing product catalog data (e.g., product speci?cations)
`for a given category of product where each column represents
`a different attribute (e.g., diameter, length, material, ?nish,
`etc.) for the category of product (e.g., pipes), and where each
`row in the table describes up to four different attribute values
`such that each row describes a different product. If a certain
`product attribute is not applicable for a certain product, the
`attribute value is left blank. While TABLE 1 depicts product
`data for three different products, it should be readily under
`stood that many more rows and/or columns may be used to
`describe as many different product attributes and attribute
`values as are necessary for a given product category. Further,
`in accordance with a preferred embodiment of the invention,
`the user may update such data tables representing a vendor’ s
`single product line and/or multiple product lines.
`
`TABLE 1
`
`Data Table
`
`Product
`Attribute 1
`
`Product
`Attribute 2
`
`Attribute
`Value 1
`Attribute
`Value 2
`Attribute
`Value 3
`
`Attribute
`Value 12
`Attribute
`Value 22
`Attribute
`Value 32
`
`Product Attribute 3
`
`Product Attribute 4
`
`Attribute Value 13
`
`Attribute Value 14
`
`Attribute Value 23
`
`Attribute Value 24
`
`Attribute Value 33
`
`Attribute Value 34
`
`4
`With reference to TABLE 2, a frame table is depicted as
`maintaining items of similar type made by multiple vendors
`or multiple product lines from the same vendor. This table can
`be generated by the user to force all vendors of a particular
`product category (e.g., pipes, valves, etc.) to have the same
`top-level attributes (e.g., diameter, material, length, ?nish,
`etc.) for their respective products. The frame table can also be
`generated by the vendors who each have multiple product
`lines and want all the product lines to have common top level
`attributes (e. g., where such products are standardiZed in the
`given industry).
`
`TABLE 2
`
`Frame Table
`
`UNIQUE ID Product Category 1
`
`Product Category 2
`
`Table Name
`
`20
`
`1
`2
`3
`
`Category 1
`Category 2
`Category 3
`
`Category 12
`Category 22
`Category 32
`
`Product-table-l
`Product-table-2
`Product-table-3
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Each row of the frame table, for example, is assigned a
`unique identi?cation and is associated with a different prod
`uct category and also with a different product data table e. g.,
`such as TABLE 1) containing a unique set of product
`attributes and values for the associated product category. The
`columns labeled Product Category 1 and Product Category 2
`can represent the same category of product as supplied by two
`different vendors or different categories by the same vendor.
`The two product categories of row 1, for example, although
`supplied by two different vendors, may have common
`attributes as listed on Product-table-l. Of course, the frame
`table may have as many rows and/or columns as are necessary
`for a given application. Further, in accordance with a pre
`ferred embodiment of the invention, the user may update the
`frame table product lines (e.g., as vendors change).
`With reference to TABLE 3, a question repository table is
`depicted. The question repository table contains a list of ques
`tions generally asked in a particular industry to describe a
`certain product in a given product category. The underlying
`data for the question repository table is supplied by the vendor
`since the vendor is most familiar with the speci?c questions a
`customer will ask in order to arrive at a speci?c product. In
`addition, the vendor may choose to add or delete questions as
`required to describe their product differently. Each row con
`tains a separate question, where the Question ID column
`contains the unique value by which the question is identi?ed.
`Further, the Question Title, Question Description and Ques
`tion Prompt headings are self-explanatory and respectively
`describe those other attributes of a particular question.
`
`FIG. 2 illustrates a typical screen shot of a user interface
`100 implemented with a graphical user interface (GUI). The
`questions addressing product attributes to be included on the
`knowledge tree, which are stored by the question repository
`table, appear in display portions 200 of the GUI in order to
`prompt the knowledge engineer during interactive knowledge
`tree construction, as will be described more fully below.
`
`WTS PARADIGM LLC EXHIBIT 1004
`8 of 12
`
`

`
`US 7,805,461 B2
`
`TABLE 3
`
`Question Repository Table
`
`UNIQUE ID Question ID
`
`Question Title
`
`Question Description
`
`Question Prompt
`
`1
`
`CATEGORY Category
`
`This COlUIHH contains
`the question category
`
`Please select your
`category
`
`With reference to TABLE 4, a question linking table is
`depicted as containing references to the frame table (TABLE
`2), the question repository table (TABLE 3), and the product
`data table (TABLE 1). The underlying data for this table, as
`with TABLES 1-3, is preferably provided by the vendor in
`order to facilitate the creation of the frame based knowledge
`tree; however, this table is not necessary to practice this
`illustrated embodiment of the invention. In fact, the only table
`necessary for practicing the illustrated embodiment of the
`invention is TABLE 1, the product data table. TABLES 2-4
`facilitate the process of automatic knowledge tree construc
`tion but are not absolutely necessary to do so. Further, with
`regard to the product data table, the product data need not be
`presented in a single database table in order to practice this
`illustrated embodiment of the invention, but rather, the prod
`uct data may be in the form of a plurality of database tables
`made accessible by the vendor, or in a plurality of tables that
`follow a relational schema.
`
`TABLE 4
`
`Question Linking Table
`
`UNIQUE ID
`
`FraIne-table-id
`
`Question-table- Column
`unique id
`naIne/ColuInn-id
`
`1
`
`1
`
`1
`
`Product Attribute 1
`
`Referring back to FIG. 1, the induction module 120
`receives the product information from the vendor’s database
`105, including the information depicted above at TABLES
`1-4, via database access module 125. In one embodiment, an
`interactive (i.e., manual) knowledge tree construction may be
`utilized, where the user interface 100 prompts the user with a
`series of questions requiring the user to select from a list of
`product attributes, the answers to which determine the order,
`and manner in which the attributes are added to the frame
`based knowledge tree. In another embodiment, automatic
`construction (described below) may be utilized, where the
`process of knowledge tree construction is automatic based on
`user speci?ed generalization and optimization criteria.
`Referring again to FIG. 2, an exemplary screen shot of a
`GUI is depicted in accordance with a preferred embodiment
`of the invention. The user may set his preferences, including
`generalization and optimization criteria, via the FIG. 2 GUI.
`One example of a user preference may be the number of rows
`in a compound slot. The user is presented with a series of
`screens for completing the optimization process. In the series
`of screens, the user reviews the database tables present in the
`vendor’s database and selects those database tables required
`for the database induction process (e.g., TABLES 1-4) of the
`product(s) of interest.
`Once the system has identi?ed the necessary database
`tables for interactive construction, the user is presented with
`a list of product attributes (e.g., diameter, material, length,
`?nish, etc.). For more simple projects, a knowledgeable user
`can interactively construct the knowledge tree based on the
`product attributes by selecting them in the order with which
`
`10
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`they are to be added to the knowledge tree. For more complex
`projects, the user may let the system construct the knowledge
`tree automatically based on the product data table(s) or can do
`a combination of both. For example, with reference to FIG. 2,
`the user may specify at portion 205 a threshold number of
`rows in a compound slot based on which the induction mod
`ule 120 shifts from interactive to automatic knowledge tree
`construction.
`For interactively constructing the tree, the user selects the
`attributes from an attribute list displayed in the user interface
`at display portions 200, 201. Each attribute selected by the
`user serves to further split the knowledge tree into separate
`nodes, where each node may be further split into additional
`nodes. The following SQL query may be used to display the
`attribute list at display portions 200, 205:
`
`“SELECT QUESTIONID FROM QUESTIONiREPOSITORY-TABLE
`WHERE FRAME-TABLEPKTABLENAME =
`USERLDEFINEDLTABLE AND
`QUESTIONLLINKINGLTABLE.FRAME—TABLE-ID =
`FRAMELTABLEUNIQUELID AND
`QUES TIONiLINKINGiTABLE.UNIQUEiID =
`QUES TIONiREPOSITORYTABLEUNIQUELID.”
`
`It should be readily apparent that the SQL query is generic
`and may be tailored to a speci?c application and for speci?c
`database names.
`For each attribute selected by the user, the induction mod
`ule 120 queries the vendor database tables for unique values
`associated with that attribute. For example, where the
`attribute is color, unique values may be blue, red and green. In
`another example, where the attribute is shape, the unique
`values may be circle, square, rectangle, etc. The unique value
`dataset for each attribute forms the branches of the resultant
`knowledge tree (e.g., as depicted at FIG. 6 below).
`Preferably, in the case of automatic frame tree construc
`tion, the induction module 120 (as opposed to the user in the
`interactive construction) determines the order in which the
`attributes appear in the knowledge tree. For determining the
`order, the induction module 120 uses the following generali
`zation and optimization heuristics: 1) domain knowledge;
`and 2) count of distinct attribute values.
`The domain knowledge heuristic is premised on the fact
`that for a given product or product type, any number of
`vendors within a given domain will have the same attributes
`for the same type of product. For example, where the product
`type is pipes, it is known in the art of plumbing supplies that
`many vendors will have identi?ed a given pipe at least by
`diameter and material. In this example, diameter and material
`are used to split the tree twice. Therefore, at least the ?rst two
`nodes of the knowledge tree may be pre-speci?ed based on
`the domain knowledge. FIG. 4 depicts a default frame tree
`construction for a domain knowledge speci?cation. In this
`example, there are two nodes 400, 405 (feature frame 1,
`feature frame 2) where each node is an attribute of the prod
`uct. Each attribute further respectively includes a plurality of
`
`WTS PARADIGM LLC EXHIBIT 1004
`9 of 12
`
`

`
`US 7,805,461 B2
`
`7
`unique values 410, 415. Of course, the domain knowledge
`approach may be used to pre-specify any number of attributes
`common to a given type of product. The construction of any
`additional nodes on the knowledge tree beyond the domain
`knowledge speci?cation may be carried out, for example, by
`the induction module 120.
`The count of distinct attribute values option allows the user
`to specify the number of distinct values used for determining
`the level at which the attribute appears in the knowledge tree.
`For example, the user may specify that any attribute having
`greater than ?ve unique values should be located near the top
`of the knowledge tree, or, conversely, perhaps such an
`attribute should be included near the bottom of the knowledge
`tree. Further, the user has the ability to combine domain
`knowledge with count of distinct attribute values. If the user
`selects this option, whenever a con?ict exists between the
`two, the domain knowledge takes precedence over count of
`distinct attribute values. A (user-changeable) default value is
`set for the count of distinct attribute values. The following
`SQL query may be used to determine the count of distinct
`values:
`
`20
`
`“SELECT COLUMNLNAME FROM ATTRIBUTE TABLE GROUP BY
`COLUMNLNAME.”
`
`25
`
`Still referring to automatic knowledge tree construction,
`based on the user speci?ed criteria, the induction module 120
`parses through the vendor’s database tables to induct the
`attributes that fall under each of the frame nodes. As described
`above, the induction module 120 uses the above-described
`generaliZation and optimiZation heuristics to determine
`which of the attributes need to be inducted at or near the top
`of the tree and which attributes fall towards the bottom.
`FIG. 3 illustrates a method or process in accordance with a
`preferred embodiment of the invention. The process may be
`performed by any of a variety of apparatuses or systems. For
`convenience, the process will be described as being per
`formed by the database induction system illustrated in FIG. 1,
`in accordance with a preferred embodiment of the invention.
`The process begins at segment 300 and at segment 305, the
`induction module 120 determines whether there are any
`attributes to induct from the vendor’ s database tables. If there
`are none, the process ends at segment 315. However, if the
`induction module 120 determines there are attributes to
`induct (e.g., the database tables have not yet been exhausted
`of attributes), then at segment 310, the induction module 120
`determines whether the user has speci?ed any splitting
`attributes, such as, for example, in connection with interactive
`frame tree construction. If the user has speci?ed splitting
`attributes, then the module 120 queries the vendor’ s database
`tables for unique values associated with that new node at
`segment 340. At segment 345, for each unique value found in
`the database tables, the module 120 creates a new child node
`and the process returns to segment 305.
`In accordance with a preferred embodiment, the knowl
`edge tree may be made up of several nodes where each node
`is represented by a frame. Each frame contains a set of
`attributes that specialiZes the frame. Each frame may also
`have any number (e.g., 0, 1, 2, 3, etc.) of child frames. The
`attributes for each frame are called “slots.” There are three
`different types of slots.
`A ?rst type of slot is known as a “single slot.”A single slot
`contains a single attribute and one or more values (e. g., diam
`eter, and 1/2 inch, 3A inch, 1 inch). This value(s)-attribute pair
`specialiZes the frame.
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`A second type of slot is a “compound slot.” A compound
`slot is used to specialiZe a frame with attributes that depend on
`each other. The compound slot contains two or more depen
`dent attributes and combinations of values of these attributes
`that would de?ne a valid con?guration.
`A third type of slot is a “conditional slot.”A conditional slot
`is used to decide which of several frame sub-trees to include
`in the con?guration. The conditional slots are designed based
`on the value of the conditional attribute.
`If at segment 310, it is determined that there are no user
`speci?ed attributes to be added, then at segment 320, the
`induction module 120 queries the vendor’s database tables
`for all remaining attributes to be inducted. The induction
`module 120 then determines, at segment 325, whether the
`number of attributes remaining is less than a pre-speci?ed
`threshold number. If the number is less than the threshold,
`then a compound slot is created at segment 335, and the
`process returns to segment 305.
`If it is determined at segment 325 that the number of
`attributes remaining is not less than the pre-speci?ed thresh
`old number, then the induction module 120 conducts auto
`matic splitting based on the generaliZation and optimiZation
`heuristics described above (i.e., domain knowledge, count of
`distinct attribute values, or a combination of both). The induc
`tion module 120 then queries the vendor’ s database tables for
`unique values at segment 340 and creates a new node for each
`such unique value at segment 345.
`An exemplary implementation of a database induction pro
`cess in accordance with a preferred embodiment of the inven
`tion is explained in greater detail below in connection with
`TABLES 1A-4A, and also in connection with FIGS. 5 and 6.
`TABLES 1A-4A respectively depict a product data table, a
`frame table, a question repository table, and a question link
`ing table, each containing exemplary vendor data.
`TABLE 1A is an exemplary product data table that contains
`speci?c product data for eight different products. Each row
`de?nes a separate product. Each of the eight products have
`features that fall under the same three attributes. In this
`example, the ?rst attribute is color, the second attribute is siZe
`and the third attribute is shape. For example, the ?rst product
`listed is red, is small and is in the shape of a circle. The second
`product listed is blue, is small and is in the shape of a square,
`and so on.
`
`TABLE 1A
`
`Product Data Table
`
`Product-Attributel
`
`Product-AttributeZ
`
`Product-Attribute3
`
`Red
`Blue
`Green
`Red
`Blue
`Red
`Blue
`Green
`
`Small
`Small
`Small
`Medium
`Medium
`Large
`Large
`Large
`
`Circle
`Square
`Rectangle
`Circle
`Rectangle
`Circle
`Rectangle
`Square
`
`TABLE 2A is a frame table, which as described above,
`maintains items of similar type made by multiple vendors or
`multiple categories by the same vendor. In this example,
`however, only one such vendor is listed where the product
`data table is identi?ed as being Product-table-l (i.e., TABLE
`1A).
`
`WTS PARADIGM LLC EXHIBIT 1004
`10 of 12
`
`

`
`US 7,805,461 B2
`
`9
`
`TABLE 2A
`
`Fralne Table
`
`Unique ID
`
`Product-Categoryl
`
`Table Name
`
`1
`
`Widgetsl
`
`Product-table-l
`
`TABLE 3A depicts a question repository table as contain
`ing all of the questions that are generally asked in a particular
`industry to describe a certain product. In this example, three
`such questions are asked, one addressing a different attribute
`of the product (i.e., Color, Size and Shape).
`
`TABLE 3A
`
`Question Repository Table
`
`Unique
`ID
`
`Question
`ID
`
`Question
`Title
`
`Question
`Description
`
`Question
`Prompt
`
`1
`
`2
`
`3
`
`COLOR Color
`
`Contains C