Patent Abstract:
Articles of manufacture and methods are described. Specifically, the methods include constructing category structures within a database, classifying a data item within a database, and facilitating location of a data item within a database are described. A first method includes defining, in a database, a first structure of categories and an alternative second structure of categories to provide an alternative classification of a data item. A second method includes classifying a data item in a first hierarchy of categories and a second alternative hierarchy of categories. A third method includes locating a data item responsive to identifying of a link between a first hierarchy of categories and a second alternative hierarchy of categories.

Full Description:
[0001]    The present application is a continuation of application Ser. No. 09/733,767, filed on Dec. 8, 2000, which claims priority from U.S. provisional patent application No. 60/199,731 entitled “Method and System for Categorizing Items in Both Actual and Virtual Categories” filed Apr. 24, 2000. 
     
    
     TECHNICAL FIELD 
       [0002]    The present invention relates generally to the field of database architecture and, more specifically, to the categorizing of database items in both an actual category and a virtual category. 
       BACKGROUND 
       [0003]    Web sites, or other network-based data aggregators or presenters, commonly use category schemas to provide context and structure for data items. For example, within an on-line web site directory, such as that presented by Yahoo! Incorporated of Santa Clara, Calif., web sites are commonly classified under an extensive category schema. 
         [0004]    Within commercial web sites, product or service offerings are also commonly classified under a category schema so as to enable convenient user navigation of offerings to locate offerings of interest. For example, eBay, Incorporated of San Jose, Calif., implements an extensive categorization schema for an on-line auction service. Specifically, a seller wishing to post an item for auction on the on-line auction facility is required to specify a category for the relevant product offering. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0005]    The present invention is illustrated by way of example and not limitation in the figures of the accompanying drawings, in which like references indicate similar elements and in which: 
           [0006]      FIG. 1  is a block diagram illustrating an exemplary network-based transaction facility in the form of an internet-based auction facility  10 . 
           [0007]      FIG. 2  is a database diagram illustrating an exemplary database, maintained and accessed via a database engine server, which at least partially implements and supports the auction facility. 
           [0008]      FIG. 3  is a representation of an item table, according to an exemplary embodiment of the present invention, that may include a category identifier corresponding to an identifier of one or more real categories defined within a category table of the database. 
           [0009]      FIG. 4  is a diagrammatic representation of an exemplary category table, and of an exemplary category class, that may be instantiated as objects that reference a category table. 
           [0010]      FIG. 5  is a diagrammatic representation of an exemplary populated category table, which is populated with exemplary records from both an actual category as well as two virtual categories. 
           [0011]      FIG. 6  is a conceptual diagram illustrating a view of selected actual categories and virtual categories within an exemplary database, as defined within one or more exemplary category tables. 
           [0012]      FIG. 7  is a flow chart illustrating a method, according to an exemplary embodiment of the present invention, of constructing a category structure within a database. 
           [0013]      FIG. 8  is a flow chart detailing a method, according to an exemplary embodiment of the present invention, of facilitating the location of a data item by navigation of a hierarchy of virtual categories. 
           [0014]      FIG. 9A  provides an example of a markup language document that lists a number of top-level virtual categories. 
           [0015]      FIG. 9B  illustrates an example of a markup language document that may present an exemplary list of mixed-level categories. 
           [0016]      FIG. 9C  is an example of a markup language document that may be utilized to present both next level, or leaf, categories and data items identified to a user. 
           [0017]      FIG. 10A  shows an exemplary user interface, in the form of a markup language document, that facilitates classification by a user of a data item according to actual categories. 
           [0018]      FIGS. 10B-10E  illustrate a further interface via which a user may specify actual category information. 
           [0019]      FIG. 11  is a diagrammatic representation of a machine, in the exemplary form of a computer system, within which a set of instructions for causing the machine to perform any of the methodologies discussed above may be executed. 
       
    
    
     DETAILED DESCRIPTION 
       [0020]    A method and system for categorizing items in both actual and virtual categories are described. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It will be evident, however, to one skilled in the art that the present invention may be practiced without these specific details. 
       Terminology 
       [0021]    For the purposes of the present specification, the term “transaction” shall be taken to include any communications between two or more entities and shall be construed to include, but not be limited to, commercial transactions including sale and purchase transactions, auctions and the like. 
         [0022]    The term “virtual category” shall be understood to be a category that, for a particular data item, is not directly recorded as being associated with the data item. Nonetheless, a “virtual category” may, for a further data item, be directly recorded as an appropriate category, and for such a further data item will comprise an “actual category” (or a “real category”). 
       Transaction Facility 
       [0023]      FIG. 1  is block diagram illustrating an exemplary network-based transaction facility in the form of an Internet-based auction facility  10 . While an exemplary embodiment of the present invention is described within the context of an auction facility, it will be appreciated by those skilled in the art that the invention will find application in many different types of computer-based, and network-based, commerce facilities. 
         [0024]    The auction facility  10  includes one or more of a number of types of front-end servers, namely page servers  12  that deliver web pages (e.g., markup language documents), picture servers  14  that dynamically deliver images to be displayed within Web pages, listing servers  16 , CGI servers  18  that provide an intelligent interface to the back-end of facility  10 , and search servers  20  that handle search requests to the facility  10 . E-mail servers  21  provide, inter alia, automated e-mail communications to users of the facility  10 . 
         [0025]    The back-end servers include a database engine server  22 , a search index server  24  and a credit card database server  26 , each of which maintains and facilitates access to a respective database. 
         [0026]    The Internet-based auction facility  10  may be accessed by a client program  30 , such as a browser (e.g., the Internet Explorer distributed by Microsoft Corp. of Redmond, Wash.) that executes on a client machine  32  and accesses the facility  10  via a network such as, for example, the Internet  34 . Other examples of networks that a client may utilize to access the auction facility  10  include a wide area network (WAN), a local area network (LAN), a wireless network (e.g., a cellular network), or the Plain Old Telephone Service (POTS) network. 
       Database Structure 
       [0027]      FIG. 2  is a database diagram illustrating an exemplary database  23 , maintain by and accessed via the database engine server  22 , which at least partially implements and supports the auction facility  10 . The database  23  may, in one embodiment, be implemented as a relational database, and includes a number of tables having entries, or records, that are linked by indices and keys. In an alternative embodiment, the database  23  may be implemented as collection of objects in an object-oriented database. 
         [0028]    Central to the database  23  is a user table  40 , which contains a record for each user of the auction facility  10 . A user may operate as a seller, buyer, or both, within the auction facility  10 . The database  23  also includes item tables  42  that may be linked to the user table  40 . Specifically, the tables  42  include a seller items table  44  and a bidder items table  46 . A user record in the user table  40  may be linked to multiple items that are being, or have been, auctioned via the facility  10 . A link indicates whether the user is a seller or a bidder (or buyer) with respect to items for which records exist within the item tables  42 . 
         [0029]    The database  23  also includes one or more category tables  47 . Each record within the category table  47  describes a respective category. In one embodiment, a specific category table  47  may describe multiple, hierarchical category structures, and include multiple category records, each of which may describe the context of a particular category within the one of the multiple hierarchical category structures. For example, the category table  47  may describe a number of real, or actual, categories to which item records, within the item tables  42 , may be linked. For example, as shown in  FIG. 3 , an item table  42  may include a category identifier  62  corresponding to an identifier of one or more real categories defined within the category table  47 . 
         [0030]    The category table  47  may also define a number of “virtual” hierarchical category structures that support alternative navigation paths that may be presented to a user to locate a particular item. In one embodiment, categories of a “virtual” hierarchical category structure are not directly referenced within item records within the item tables  42 , but are instead linked to “real” categories. Accordingly, in one embodiment, no category identifiers  62  within the item tables  42  point directly to a “virtual” category. As will be described in further detail below, multiple virtual categories may be linked to a single real category. 
         [0031]    The database  23  also includes a note table  48  populated with note records that may be linked to one or more item records within the item tables  42  and/or to one or more user records within the user table  40 . Each note record within the table  48  may include, inter alia, a comment, description, history or other information pertaining to an item being auction via the auction facility  10 , or to a user of the auction facility  10 . 
         [0032]    A number of other tables are also shown to be linked to the user table  40 , namely a user past aliases table  50 , a feedback table  52 , a feedback details table  53 , a bids table  54 , an accounts table  56 , an account balances table  58  and a transaction record table  60 . 
       Category Table and Hierarchical Category Structures 
       [0033]      FIG. 4  is a diagrammatic representation of an exemplary category table  47 , and of an exemplary category class  70  that may be instantiated as objects that reference the category table  47 . 
         [0034]    The category table  47  is shown to include a number of fields, each of which may be populated with relevant information for a category record within the category table  47 . For each category record, a marketplace field  68  indicates a particular marketplace (e.g., automobiles, computers, collectibles, etc.) within the context of the network-based auction facility  10  to which the category pertains. An identifier field  72  contains a unique category identifier for each category record. A name field  74  similarly includes a name (which need not be unique) for the relevant category. 
         [0035]    An IS_LEAF field  76 , for each category record, is populated with a character that indicates whether the relevant category is a leaf category of a particular hierarchical category structure (e.g., an actual or virtual category structure). The level1-level4 fields  78 - 84  record the category identifiers of categories from which a particular category depends within the context of hierarchical category structure. For example, the level1 field  78  will record the category identifier for an immediate parent category, while the level2 field  80  will record the category identifier for a grandparent category. 
         [0036]    An actual_category field  86  is, in one embodiment, only populated for a virtual category, and stores the category identifier of an actual (or real) category to which the relevant virtual category is linked. 
         [0037]      FIG. 5  is a diagrammatic representation of an exemplary populated category table  47 , that is populated with exemplary records for both an actual category  90 , as well as two virtual categories  92  and  94 . 
         [0038]    Turning first to the hierarchy of actual categories  90 , a parent (passenger vehicle) category includes a “Ford” child category, the “Ford” category being indicated as a child of the “passenger car” category by inclusion of the category identifier (e.g.,  50 ) within the level1 field  78  of the record for the “Ford” category. The “Ford” category in turn is shown to include a “Taurus” sub-category and a “Model T” sub-category. It will be noted the “Taurus” and the “Model T” categories are indicated in the IS-LEAF field  76  as being leaf categories of the hierarchy of actual categories  90 . It will furthermore be noted that, for each category within the hierarchy of actual categories  90 , the actual_category field  86  contains a null value, as these categories are not linked to, and do not point to, further categories. 
         [0039]    Turning now to the hierarchy of virtual categories  92 , a parent “cars” category is defined to have a “Ford” child category, that in turn is defined to have a “Taurus” child category. It will be noted that the level1 field  78  of the “Ford” category includes an identifier pointing back to the parent “cars” category. 
         [0040]    The “Taurus” category of the virtual categories  92  is also shown, within the actual_category field  86 , to include the identifier of the “Taurus” category of the actual categories  90 . In this way, the virtual “Taurus” category, identified by the category identifier “8001” is linked to, or points to, the actual “Taurus” category identified by the category identifier “8000”. In this way, user navigation of the hierarchy of virtual categories  92 , when resulting in the selection of the virtual “Taurus” category, can be utilized to identify the category identifier for an actual “Taurus” category, that can in turn be utilized to identify records within an item table  42 . 
         [0041]    Similarly, the hierarchy of virtual categories  94  is headed by a “vintage cars” category that includes a child “Ford” category and a grandchild “Model T” category. The “Model T” category is again linked, by an appropriate category identifier within the actual_category field  86 , to the actual “Model T” category of the actual categories  90 . 
         [0042]    It will furthermore be noted that, in one embodiment, only real categories are indicated in the IS_LEAF field  76  as being leaf categories. 
         [0043]    In one embodiment of the present invention, as mentioned above, data items may only be categorized under a hierarchy of actual categories  90 , and not under a hierarchy of virtual categories. It is for this reason that only actual categories may be indicated as leaf categories. 
         [0044]    While the hierarchies of virtual categories  92  and  94  are indicated as being distinct hierarchies, these hierarchies may in fact be sub-hierarchies of a larger hierarchy of virtual categories. Nonetheless, the present application contemplates that the category table  47  may define multiple hierarchies of virtual categories, and that multiple virtual categories may be linked to, or pointed to, a single actual category. 
         [0045]      FIG. 6  is a conceptual diagram illustrating a view of selected actual categories  100  and virtual categories  102  within an exemplary database, and as defined within one or more exemplary category tables  47 . As illustrated, both the actual categories  100  and the virtual categories  102  are shown to include parent, child and grandchild categories. The grandchild categories, in the illustrated example, are “leaf” categories for both the actual and virtual categories  100  and  102 . Leaf categories of the virtual categories are shown to be linked to appropriate “leaf” categories of the actual categories  100 . 
       Methodologies 
       [0046]      FIG. 7  is a flow chart illustrating a method  110 , according to an exemplary embodiment of the present invention, of constructing category structures within a database. The database may, in one exemplary embodiment, support a web site that classifies data items for presentation to a user via a browser. Such data items may describe, for example, web sites, products, services or any other items that may be categorized so as to facilitate convenient location by a user. In one embodiment, the data items may describe goods and services that are offered for sale via an auction process by the network-based auction facility  10 . However, it will readily be appreciated that the present invention is not limited to use in such an exemplary facility. 
         [0047]    The method  110  commences at block  112  with the definition, for example by a database designer, of a hierarchy of “actual” categories  100  being described by a respective category records that each specify a category identifier. 
         [0048]    At block  114 , the database designer then defines at least one hierarchy and multiple hierarchies, of “virtual” categories  102  within the category table  47 . In one embodiment, the virtual categories are not intended to be presented to a user for selection to categorize a data item, but are linked, in the manner described above, to actual categories. 
         [0049]    At block  116 , in an actual_category field  86  for each “leaf” virtual category, the database designer includes a pointer (or link) in the form of a category identifier to a “actual” leaf category. 
         [0050]      FIG. 8  is a flow chart detailing a method  120 , according to an exemplary embodiment of the present invention, of facilitating the location of a data item by navigation of a hierarchy of virtual categories. 
         [0051]    The method  120  commences at block  122 , with the presentation to a user of a list of top-level virtual categories. For example, the top-level categories may be the parent categories of the virtual categories  102  illustrated in  FIG. 6 . The top-level categories may furthermore be presented in the form of a markup language document (e.g., a HTML document) that is generated by a page server  12  utilizing category information retrieved by the database engine server  22  from the database  23 .  FIG. 9A  provides an example of such a markup language document  138 , which lists a number of top-level virtual categories  140 . 
         [0052]    At block  124 , user selection of a virtual category is detected. For example, by performing a “point-and-click” operation utilizing a cursor control device, a user may select the “cars” category of the virtual categories  140  shown in  FIG. 9A , the selection being communicated to a CGI server  18  that in turn communicates the selection to an appropriate CGI script. 
         [0053]    At block  126 , a list of next-level virtual category is presented, based on the virtual category selected at block  124 .  FIG. 9B  illustrates an example of a markup language document that may be utilized to present an exemplary list  144  of such mixed-level categories. For example, a CGI script executing within a CGI server  18  and responsive to identification of a user-selected top-level category, may, via the database engine server  22 , query the category table  47  to identify virtual categories that are child categories of the “cars” category. The results of this query are then communicated to a page server  12  that populates a template to generate the markup language document illustrated in  FIG. 9B . The list  144  of virtual categories shown in  FIG. 9B  accordingly represents child categories of the “cars” virtual category. 
         [0054]    At block  128 , a user selection of a next-level virtual category is detected, in the same manner described above. For example, assuming user selection of a hypertext link  146  for the “Ford” category of the list  144  of categories shown in  FIG. 9B , this user selection may be communicated to a CGI server  18 . 
         [0055]    At block  130 , a leaf category, or leaf categories, of the virtual category selected at block  128  may, in one embodiment, be identified so as to facilitate presentation of all data items associated with that leaf category or categories. For example, all leaf categories that depend from the virtual “Ford” category selected at block  128  may be identified. Such leaf categories may include the virtual “Taurus” category or the virtual “Model T” category discussed above with reference to  FIG. 5 . 
         [0056]    Where the category selected at block  128  itself comprises a leaf category, it will be appreciated that such a category itself be identified as the leaf category at block  130 . 
         [0057]    At block  132 , a mapping, or linking, operation is performed so as to map the relevant virtual leaf categories identified at block  130  to actual leaf categories. Specifically, as described above, this mapping operation may be performed utilizing a category identifier included within the actual_category field  86  of each relevant virtual category. 
         [0058]    Having then identified one or more actual leaf categories corresponding to the virtual leaf categories, at block  134 , data items categorized as being attributed to the identified real leaf categories are identified and presented in a user interface. 
         [0059]      FIG. 9C  is an exemplary embodiment of a user interface, in the form of a markup language document, that may be utilized to present both the next level, or leaf, categories identified at block  130  and the data items identified at block  134  to a user. Specifically, the next level virtual categories are shown to be presented at  150 , and the identified data items are shown to be presented at  152 . It will be noted that the data items presented at  152  include data items within all of the virtual leaf categories listed at  150 . Accordingly, the list of data items  152  may be extensive. For this reason, a user may wish to further navigate the hierarchy of virtual categories to further limit the list of data items  152  to a more manageable size. 
         [0060]    Returning to  FIG. 8 , at decision block  136 , a determination is made as to whether a user selected a virtual leaf category at block  128 . If the selected virtual category is not a leaf category, the method  120  loops back through blocks  126 - 134 . For example, a user may select a hypertext link  154  for the virtual “Taurus” category, responsive to which the user will be presented, at block  134 , with a list of data items identified as being within the actual “Taurus” category by performing a link between the virtual “Taurus” category and the actual “Taurus” category. 
         [0061]      FIG. 9D  is an exemplary user interface, in the form of a markup language document, that illustrates the presenting of such a narrowed list of data items at  156 . It will furthermore be noted that the user interface shown in  FIG. 9D  does not provide a list of any child categories, as were shown at  150  in  FIG. 9C , as the virtual “Taurus” category is a leaf category. 
       User-Classification of a Data Item 
     User Interfaces 
       [0062]    As described above, in one embodiment, a user (e.g., a seller) utilizing the network-based auction facility  10  or an administrator classifying data items for presentation via a web site, may be presented with the option of only classifying data items within the context of a hierarchy of actual (and not virtual) categories. 
         [0063]      FIG. 10A  shows an exemplary user interface, in the form of a markup language document, that facilitates classification by a user of a data item according to actual categories  100 , such as those shown in  FIG. 6 . The top-level (or parent) actual categories comprise vehicle types (e.g., a passenger vehicles, commercial trucks, boats, aircraft, etc.). Selection of a passenger vehicle type utilizing a drop-down menu  162  indicates both an actual parent category and an actual child category. Alternatively, the user (i.e., seller) may be offering a further vehicle type for auction. User selection of the drop-down menu  164  allows the seller to specify such a further vehicle type. 
         [0064]      FIGS. 10B-10E  illustrates a further user interface  170  via which a user (i.e., a seller) may specify actual category information. In an exemplary embodiment, the information inputted by the user at block  172 , as shown in  FIG. 10B , specifies an actual category. Specifically, for passenger vehicles, a leaf category is defined by a passenger vehicle make and model. 
         [0065]    It should thus be noted that, in the exemplary embodiment, data items are classified according to a selected leaf category. Such leaf categories may be viewed as a category path selected within the context of a hierarchy of categories. For example, the full categorization of a data item may be viewed as the “passenger vehicle/Ford/Taurus” categorization. 
       Software 
       [0066]    The methodologies described above may, it will be appreciated, be performed by software modules residing and executing on a wide variety of machines. In one embodiment, the mapping of the virtual leaf categories to actual leaf categories may be performed by a “listings produce” module or object that issues a series of SQL statements against the database  23 . The “listings produce” object may reside, for example, on a CGI server  18  or be part of the database engine server  22 . 
         [0067]      FIG. 11  shows a diagrammatic representation of a machine in the exemplary form of a computer system  300  within which a set of instructions, for causing the machine to perform any one of the methodologies discussed above, may be executed. In alternative embodiments, the machine may comprise a network router, a network switch, a network bridge, Personal Digital Assistant (PDA), a cellular telephone, a web appliance or any machine capable of executing a sequence of instructions that specify actions to be taken by that machine. 
         [0068]    The computer system  300  includes a processor  302 , a main memory  304  and a static memory  306 , which communicate with each other via a bus  308 . The computer system  300  may further include a video display unit  310  (e.g., a liquid crystal display (LCD) or a cathode ray tube (CRT)). The computer system  300  also includes an alpha-numeric input device  312  (e.g. a keyboard), a cursor control device  314  (e.g. a mouse), a disk drive unit  316 , a signal generation device  320  (e.g. a speaker) and a network interface device  322   
         [0069]    The disk drive unit  316  includes a machine-readable medium  324  on which is stored a set of instructions (i.e., software)  326  embodying any one, or all, of the methodologies described above. The software  326  is also shown to reside, completely or at least partially, within the main memory  304  and/or within the processor  302 . The software  326  may further be transmitted or received via the network interface device  322 . For the purposes of this specification, the term “machine-readable medium” shall be taken to include any medium that is capable of storing or encoding a sequence of instructions for execution by the machine and that cause the machine to perform any one of the methodologies of the present invention. The term “machine-readable medium” shall accordingly be taken to included, but not be limited to, solid-state memories, optical and magnetic disks, and carrier wave signals. 
         [0070]    Thus, a method and system for categorizing items in both actual and virtual categories have been described. Although the present invention has been described with reference to specific exemplary embodiments, it will be evident that various modifications and changes may be made to these embodiments without departing from the broader spirit and scope of the invention. Accordingly, the specification and drawings are to be regarded in an illustrative rather than a restrictive sense.

Technology Classification (CPC): 6