Patent Publication Number: US-5897639-A

Title: Electronic catalog system and method with enhanced feature-based search

Description:
FIELD OF THE INVENTION 
     The present invention relates to a system and method for enhancing feature-based searches through feature relevance reasoning based on defined and inherited attributes of database objects. 
     BACKGROUND OF THE INVENTION 
     The increasing interest in the use of electronic media for product sales has created a need for product search strategies that are intuitive and easy to use. Most electronic catalogs provide some form of search functionality. This may be as simple as a keyword search. The search statement &#34;find all products with the characters `MP004` in their part number descriptions&#34; is an example of a keyword search. More complex searches, such as parametric searches, are also common. The search statement &#34;find all products which have the parameter `color` equal to `red`&#34; is an example of a parametric search. However, problems arise with such search methods. 
     Current search methods require that parameter relevance be embedded in the description of a product. This is typical in a relational database implementation, in which the database architect is forced to parameterise all notions in a product domain. For example, assume the notion of color is relevant to all computer products in a database. A relevant notion is one that a person searching for a product will always use in order to search for the particular product desired. If the notion is not parameterised, there is no way to enforce entry of information descriptive of the notion. In the example, assume a free-form text field is provided for the description of the computer. With such a field, there is no way to ensure that each entry contains a description of the color of the computer. The notion of color must be parameterised. A separate field must be created which requires that a value be entered. 
     It is easy to detect parameterisation by considering the different values assigned to attributes. If the values are diametric, for example, yes/no, includes/doesn&#39;t include, available/not available, 5&#34;/6&#34;/no inches, then the catalog architect is using parameter values to represent relevance. By building representations of this nature, the architect is attempting to capture when a feature of a component is relevant to a product and when it is not relevant. For example, assume there are two cameras in a catalog, one with autofocus and one without. To capture the fact that this feature is relevant to only one of the cameras, the positive and negative notions of this feature must be parameterised. An attribute such as &#34;autofocus&#34; must be created and given the value &#34;yes&#34; for one camera and the value &#34;no&#34; for the other camera. 
     Encoding relevance in this manner is difficult to create and maintain. Each time a feature is represented, the catalog architect must determine values for the attribute, which represents the feature, that not only describe the actual feature, but also describe the relevance of the feature to the product. 
     SUMMARY OF THE INVENTION 
     The present invention is a catalog database system and method in which there is a plurality of catalog objects. Each catalog object contains at least one attribute and at least some of the catalog objects have at least one search path leading to at least one other child object. A first object and the attributes of other objects in the electronic catalog are displayed. Those attributes which are defined in the first object and relevant to all child objects whose values are assigned in any search path leading from the first object, are displayed as strongly relevant attributes. Those attributes which are defined in and relevant to at least one child object, which is in any search path leading from the first object, are displayed as weakly relevant attributes. Those attributes which are defined in and relevant to no child objects, which are in any search path leading from the first object, are displayed as irrelevant attributes. To access a catalog object, a selection of an attribute from among those displayed is accepted from a user. A search path from the first object to a second object, in which the selected attribute is defined, is followed and the second object is displayed. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The details of the present invention, both as to its structure and operation, can best be understood by referring to the accompanying drawings, in which like reference numbers and designations refer to like elements. 
     FIG. 1 is an exemplary hierarchical diagram of catalog objects, in accordance with the present invention, showing membership of objects in the hierarchy. 
     FIG. 2 is a flow diagram of a process 200, which performs feature relevant reasoning with the objects of FIG. 1. 
     FIGS. 3a is an exemplary screen display 300 generated by process 200 of FIG. 2, displaying attributes of computer 102 of FIG. 1. 
     FIGS. 3b is an exemplary screen display 310 generated by process 200 of FIG. 2, displaying attributes of laptop computer 104 of FIG. 1. 
     FIGS. 3c is an exemplary screen display 320 generated by process 200 of FIG. 2, displaying attributes of model 2 110 of FIG. 1. 
     FIGS. 3d is an exemplary screen display 330 generated by process 200 of FIG. 2, displaying attributes of desktop computer 106 of FIG. 1. 
     FIG. 4 is a block diagram of a portion of an exemplary catalog database, showing the relationship of database objects to form aggregate objects. 
     FIG. 5 is a block diagram of an electronic catalog system 500, which implements feature relevant reasoning, in accordance with the present invention. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The present invention uses the characteristics of object-centered data representation to reason about feature (attribute) relevance. The only descriptions required are of the features relevant to each product or category of product and the actual values of those features. This allows the creation of smaller, simpler catalog databases that are easier to maintain. 
     Three definitions of relevance are used in the present invention. Strongly relevant features are those features that are relevant to all possible search paths in the feasible search space. Weakly relevant features are those features that are relevant to at least one possible search path. Irrelevant features are those that are not relevant to any search path. 
     FIG. 1 is a hierarchical diagram of catalog objects, showing ancestry of objects in the hierarchy. In this example, the catalog objects form an object-centered hierarchy of computer products. Each catalog object is labeled with the computer product it represents and with the attributes that it contains. Computer 102 contains two attributes: &#34;price&#34; and &#34;color&#34;. Object inheritance is indicated by the plain arrows; search paths are indicated by the bold arrows. The search path is coincident with the inheritance. Laptop computer 104 and desktop computer 106 are both children of the object computer. A child inherits the attributes which are contained in the object of which it is a child. For example, laptop computer 104 is a child of the object computer and therefore inherits attributes 104-1 from computer 102. The inherited attributes are all attributes contained in computer 102, including the defined attributes 102-2 of computer 102, which are &#34;price&#34; and &#34;color&#34; and the inherited attributes 102-1 of computer 102, of which there are none. Attribute &#34;color&#34; is set equal to the value &#34;black&#34; in laptop computer 104. In addition, the defined attribute 104-2 of &#34;battery-life&#34; is defined in laptop computer 104. Likewise, desktop computer 106 has the inherited attributes &#34;price&#34; and &#34;color&#34;, sets &#34;color&#34; equal to the value &#34;white&#34; and defines the attribute &#34;height&#34;. 
     Model 1 108 is a child of the object laptop computer which represents a specific model of computer. It therefore inherits all attributes and values of laptop computer 104. In addition, Model 1 108 defines values for &#34;price&#34; and &#34;battery-life&#34;, defines the attribute 108-2 &#34;screentype&#34; and assigns the value &#34;backlit&#34; to &#34;screentype&#34;. Model 2 110 is also a child of the object laptop computer which represents a specific model of computer. It also inherits all attributes and values of laptop computer 104. In addition, Model 2 110 defines distinct values for &#34;price&#34; and &#34;battery-life&#34;, defines the attribute 108-2 &#34;CD type&#34; and assigns the value &#34;4x speed&#34; to &#34;CD type&#34;. 
     The relevance of the various attributes may be seen from an exemplary search through the hierarchy. The search begins at the top level, computer 102. The definition of attributes &#34;price&#34; and &#34;color&#34; are contained by computer 102. All children inherit these attributes. As shown by the inheritance arrows, all other objects are descendants of object computer. Therefore all other objects contain these attributes through inheritance. The search path arrows show that all other objects are in a search path from computer 102. Therefore, the attributes &#34;price&#34; and &#34;color&#34; are strongly relevant to computer 102, because they are contained by objects in all search paths leading from computer 102. All other attributes shown are weakly relevant to computer 102 because they are defined in descendant objects of computer 102 and thereby are not inherited by child objects in all inheritance paths from computer 102. 
     Now assume that the search has led to laptop computer 104. The attributes contained by laptop computer 104 are the inherited attributes &#34;price&#34; and &#34;color&#34; and the locally-defined attribute &#34;battery-life&#34;. Because all lower-level objects inherit these attributes, they are contained by objects in all search paths leading from laptop computer 104 and are therefore strongly relevant to laptop computer 104. All other attributes in the objects which are descendants of laptop computer 104 are weakly relevant because they are defined in descendant objects leading from laptop computer 104. The attribute height, defined in desktop computer 106, is not contained by objects in any search path leading from laptop computer 104. Therefore, this attribute is irrelevant to laptop computer 104. 
     Carrying the search one level further, it is seen that for model 1 108, the attributes &#34;price&#34;, &#34;color&#34;, &#34;battery-life&#34; and &#34;screentype&#34; are strongly relevant, the attributes &#34;height&#34; and &#34;CD type&#34; are irrelevant and there are no weakly relevant attributes. Likewise, for model 2, 110, the attributes &#34;price&#34;, &#34;color&#34;, &#34;battery-life&#34; and &#34;CD type&#34; are strongly relevant, the attributes &#34;height&#34; and &#34;screentype&#34; are irrelevant and there are no weakly relevant attributes. 
     FIG. 2 is a flow diagram of a process 200, which performs feature relevance reasoning with the objects of FIG. 1. It is best viewed in conjunction with FIG. 1 and FIGS. 3a-c, which are screen displays generated by process 200. The process begins with step 200, in which the top level object is displayed. FIG. 3a is a screen display of the computer 102 of FIG. 1, which is the top level object of this example. Title field 302 displays the name of the object currently being displayed. Here, the object currently being displayed is computer 102. Strongly relevant feature field 304 displays the features which are strongly relevant to the object being displayed. Here, as discussed previously, the strongly relevant features are &#34;price&#34; and &#34;color&#34;. In addition, the values of the strongly relevant features along the different search paths are displayed. Weakly relevant feature field 306 displays the features which are weakly relevant to the object being displayed. Here, the weakly relevant features are &#34;battery-life&#34;, &#34;height&#34;, &#34;screentype&#34; and &#34;CD type&#34;. Irrelevant feature field 308 displays the features that are irrelevant to the object being displayed. At the top level, there are no irrelevant features. 
     In step 204 of FIG. 2, the user selects a weakly relevant or irrelevant feature or a strongly relevant feature value from among those displayed. In step 206, it is determined what type of feature was selected. If a value was selected in step 204, a strongly relevant feature was also selected because values are only displayed for strongly relevant features. The process goes to step 208, in which the search path is followed to the object where the value was assigned. Then, in step 214, this object is displayed. For example, selection of the &#34;color&#34; &#34;black&#34; in step 204 causes the search path to be followed, in step 208, to laptop computer 104, in which the value &#34;black&#34; is assigned to the feature &#34;color&#34;. The screen display 310 of FIG. 3b is then displayed in step 214. Title field 312 displays the name of the object being displayed, &#34;laptop computer&#34;. The &#34;battery-life&#34; feature is strongly relevant to laptop computer 104, so the &#34;battery-life&#34; feature, along with its values, is displayed in strongly relevant features field 314. The &#34;screentype&#34; and &#34;CD type&#34; features are weakly relevant to laptop computer 104, so they are displayed in weakly relevant features field 316. The &#34;height&#34; feature is not in any search path leading from laptop computer 104, so it is irrelevant and is displayed in irrelevant features field 318. 
     If a weakly relevant feature was selected in step 204, the process goes to step 210, in which the search path is followed to the object where the feature is defined. Then, in step 214, this object is displayed. For example, selection of the weakly relevant feature &#34;battery-life&#34; in step 204 causes the search path to be followed, in step 210, to laptop computer 104, in which the feature &#34;battery-life&#34; is defined. The screen display 310 of FIG. 3b is then displayed. 
     The process loops from step 214 back to step 204, in which the user may again select a feature or value from the currently displayed screen. For example, selection, from screen display 310 of FIG. 3b, of the value &#34;5000&#34; for &#34;price&#34;, the value &#34;4 hrs.&#34; for &#34;battery-life&#34;, or the &#34;CD type&#34; weakly relevant feature causes screen display 320 of FIG. 3c to be displayed. Title field 322 displays the name of the object being displayed, &#34;Model 2&#34;. The &#34;CD type&#34; feature is strongly relevant to model 2 108, so it, along with its value, &#34;4x speed&#34;, is displayed in strongly relevant features field 324. The &#34;screentype&#34; feature is not in any search path leading from model 2 108, so it is now displayed in irrelevant features field 328. There are no weakly relevant features in this display. 
     When screen display 300 of FIG. 3a is displayed, no irrelevant features were available. When screen display 310 of FIG. 3b is displayed, irrelevant features are available. Selection, in step 204, of an irrelevant feature causes a search for the object in which the feature is defined. For example, irrelevant feature &#34;height&#34; is selected from screen display 310 of FIG. 3b. The search results in the desktop computer 106, where &#34;height&#34; is defined, and screen display 330 of FIG. 3d is displayed. Title field 332 displays the name of the object being displayed &#34;desktop computer&#34;. The features &#34;price&#34;, &#34;color&#34; and &#34;height&#34; are displayed in strongly relevant field 334 and the features &#34;battery-life&#34;, &#34;CD type&#34; and &#34;screentype&#34; are displayed in irrelevant features field 338. There are no weakly relevant features in this display. 
     Feature relevance reasoning can be extended to aggregate objects as well. For example, in the previous examples, &#34;CD type&#34; was an attribute in the model 2 object. But a CD drive is in fact a separate object and may be represented as a separate object in the database. FIG. 4 is a block diagram of a portion of a catalog database, showing the CD drive represented as a separate object, CD drive 402. CD drive 402 defines the attribute &#34;CD type&#34;. Model 4x 404 is a child of the class CD drive and so inherits the &#34;CD type&#34; attribute from CD drive 402. Model 4x 404 assigns the &#34;CD type&#34; attribute the value &#34;4x speed&#34;. Model 2 110 has an aggregate relationship with model 4x 404. This allows the creation of aggregate objects, which can also be exploited with feature relevance reasoning. Model 4x 404 is not a child of the class model 2 and model 2 110 is not a child of the class model 4x. Therefore, neither object inherits any attributes from the other. However, because of the aggregate relationship of model 2 110 which leads to model 4x 404, the attributes of model 4x 404 are relevant to model 2 110. In fact, because model 4x 404 lies in an aggregation path leading from model 2 110, the attributes of model 4x 404 are strongly relevant to model 2 110. Any search path which includes model 2 110 also includes model 4x 404, so the attributes of model 4x 404 are relevant (either strongly or weakly) to all objects which have search paths which lead to or from model 2 110. Therefore, the database configuration of FIG. 3 results in screen displays which are similar to those of FIGS. 3a-c. However, this configuration allows the advantages of feature relevance reasoning to be extended to aggregate objects, without increasing the complexity of the user interface. 
     FIG. 5 is a block diagram of an electronic catalog system 500, which implements feature relevance reasoning, in accordance with the present invention. System 500 includes display device 530, which displays the screen displays of FIGS. 3a-d. System 500 also includes computer system 510 which has a CPU 512, for executing program instructions and processing data, memory 520, for storing program instructions executed by and data processed by CPU 512, display adapter 511, for generating signals to drive display 530, input adapter 514, for interfacing input devices such as keyboard 515 and mouse 516 and adapter 513, for interfacing catalog database 540. Bus 517 allows signals and data to be communicated among the interconnected elements. 
     Memory 520 may include both volatile storage devices, such as, for example, random access memory (RAM) and non-volatile storage devices, such as, for example, hard disk, floppy disk, optical disk, electrically-alterable programmable read only memory, battery-backed up RAM, etc. Memory 520 is accessible to CPU 512 over bus 517 and includes operating system 523, process routines 522, which implement process 200 of FIG. 2 and display routines 521, which generate the screen displays of FIGS. 3a-d. 
     Catalog database 540 contains catalog database objects such as those shown in FIGS. 1 and 4. Catalog database is stored in a storage device of some kind. This storage device may be a separate device, as shown in FIG. 5, or it may be memory 520. If catalog database 540 is stored in a separate storage device, the storage device is interfaced to computer system 510 through adapter 513. Catalog database 540 may be stored in a local storage device, such as a CD ROM drive or tape drive or it may be stored in a networked storage device, such as a file server, on a local area network (LAN) or a wide area network (WAN), such as, for example, the Internet. 
     Although a specific embodiment of the present invention has been described, it will be understood by those of will in the art that there are other embodiments which are equivalent to the described embodiment. Accordingly, it is to be understood that the invention is not to be limited by the specific illustrated embodiment, but only by the scope of the appended claims.