Case 1:19-cv-00859-RTH Document 82-2 Filed 04/29/22 Page 1 of 11
`Case 1:19-cv-00859-RTH Document 82-2 Filed 04/29/22 Page 1 of 11
`
`EXHIBIT B
`EXHIBIT B
`
`

`

`Case 1:19-cv-00859-RTH Document 82-2 Filed 04/29/22 Page 2 of 11
`I 1111111111111111 11111 111111111111111 11111 1111111111 lllll 111111111111111111
`US005940822A
`[11] Patent Number:
`[45] Date of Patent:
`
`United States Patent [19J
`Haderle et al.
`
`5,940,822
`Aug. 17, 1999
`
`[54] ENCODING METHOD OF MEMBERS
`RELATED BY MULTIPLE CONCEPT OR
`GROUP HIERARCHIES AND
`IDENTIFICATION OF MEMBERS IN A
`CORPUS OR A DATABASE THAT ARE
`DESCENDANTS OF ONE OR MORE
`SELECTED CONCEPTS OR GROUPS FROM
`THE ENCODING
`
`[75]
`
`Inventors: Donald J. Haderle, Los Gatos;
`Balakrishna Raghavendra Iyer, San
`Jose, both of Calif.
`
`[73] Assignee: International Business Machines
`Corporation, Armonk, N.Y.
`
`[21] Appl. No.: 08/921,197
`
`[22] Filed:
`
`Aug. 29, 1997
`
`Int. Cl.6
`...................................................... G06F 17/30
`[51]
`[52] U.S. Cl. ....................... 707/3; 707/2; 707/4; 707/101
`[58] Field of Search ................................. 707/2, 3, 4, 101
`
`[56]
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,289,567
`5,495,605
`5,619,615
`5,659,725
`5,694,591
`5,701,454
`5,706,495
`5,761,654
`
`2/1994 Roth ...................................... 3295/133
`2/1996 Cadot .......................................... 707/3
`4/1997 Pitchaikani et al. . ... ... .... ... ... ... .. 395 /11
`8/1997 Levy et al. .................................. 707/2
`12/1997 Du et al. ..................................... 707/2
`12/1997 Bhargava et al.
`... ... ... .... ... ... ... ... . 707 /2
`1/1998 Chadha et al. . ... ... ... ... .... ... ... ... ... . 707 /2
`6/1998 Tow ............................................ 707/2
`
`OIBER PUBLICATIONS
`
`IBM Technical Disclosure Bulletin, "Evaluation of Column
`Functions on Grouped Data Ordering", vol. 32, No. lOB,
`Mar. 1990, pp. 385-386.
`
`Merchandise 15
`
`Iyer, Balakrishna R., et al., "Data Compression Support in
`Databases", Technology Institute, International Business
`Machines Corporation, Software Solutions Division, Santa
`Teresa Laboratory, Apr. 1994, pp. 1-26.
`Kerin, Roger A., et al., "Product Hierarchy and Brand
`Strategy Influences on the Order of Entry Effect for Con(cid:173)
`sumer Packaged Goods", J. Prod. Innov. Manag., vol. 13,
`1996, Elsevier Science Inc., pp. 21-34.
`Klug, Anthony, "Access Paths in the 'Abe' Statistical Query
`Facility", Proceedings of the International Conference on
`Management of Data, Jun. 2-4, 1982, Orlando, Florida,
`ACM SIGMOD Association for Computing Machinery, pp.
`161-173.
`http://fas.sfu.ca/cs/conf/dmkd97.html,
`article,
`Internet
`"Workshop on Research Issues on Data Mining and Knowl(cid:173)
`edge Discovery (DMKD'97) in cooperation with ACM(cid:173)
`-SIGMOD'97, Tuscon,Arizona, May 11, 1997", DMKD'97
`Pre-Conf. Data Mining Workshop: Call For Participation
`and Registration (entire document).
`
`Primary Examiner-Paul V. Kulik
`Assistant Examiner-Jean R. Homere
`Attorney, Agent, or Firm-Merchant, Gould, Smith, Edell,
`Welter, & Schmidt
`
`[57]
`
`ABSTRACT
`
`A method, apparatus, and article of manufacture for an
`encoder for encoding members in a concept hierarchy. A
`query is executed in a computer. The query is performed by
`the computer to retrieve data from a database stored on a
`data storage device connected to the computer. Members in
`the database that are related by one or more concept hier(cid:173)
`archies are encoded. Then, members in one of the concept
`hierarchies that are descendants of one or more selected
`concepts are identified based on the encoding.
`
`18 Claims, 4 Drawing Sheets
`
`300
`
`<PRODUCTS>
`
`i
`
`Men 0
`
`John 2
`
`I_
`
`Kids 5
`
`Women 14
`
`Misses 6
`
`Ladies 12
`
`Petites 13
`
`@) 13
`
`@),15
`
`Hosiery 11
`
`1@16
`
`Cathy 17
`
`Harry10 +
`
`~ I - - -~ -
`
`I
`
`Marys
`
`Jane 14
`
`Jacob6
`
`Phil 18
`
`Deb 19
`
`302
`
`/
`
`<BUYERS>
`
`

`

`Case 1:19-cv-00859-RTH Document 82-2 Filed 04/29/22 Page 3 of 11
`
`U.S. Patent
`
`Aug. 17, 1999
`
`Sheet 1 of 4
`
`5,940,822
`
`FIG. 1
`
`100
`
`~
`
`Data Communications Device 108
`
`Data Storage Device 106
`
`Processor 102
`
`I Operating System 116 I Memory 104
`
`Computer Programs 118
`
`RDBMS 120
`
`Encoder122
`
`Monitor 110
`
`Keyboard 114
`
`

`

`Case 1:19-cv-00859-RTH Document 82-2 Filed 04/29/22 Page 4 of 11
`
`FIG. 2
`
`200
`
`/
`
`Super Department Store 28
`
`d •
`r:JJ.
`•
`~
`~ ......
`~ = ......
`
`~----
`
`Apparel 14
`
`Leisure 23
`
`----------------
`Supermarket 27
`
`~~
`~
`
`Auto 15 Sports 16 Luggage 17 Electronics 18 Music 19 Garden 22
`
`Meat 24
`
`Produce 25 Vegetables 26
`
`Men 0
`
`Shoes 1
`
`Kids 6
`~
`Infants 2 Toddlers 3 Boys 4 Girls 5
`
`Women 13
`
`Indoor 20
`
`Outdoor 21
`
`Petites 7
`
`Ladies 8
`
`Misses 9
`
`Jewelry 1 O Accessories 11
`
`Hosiery 12
`
`~
`~
`'"""'
`~-..J
`'"""'
`\0
`\0
`\0
`
`rF.J. =(cid:173)~
`~ ....
`N
`0 ....,
`
`,i;;..
`
`Ul
`....
`\0
`
`"'-' =
`
`....
`00
`N
`N
`
`

`

`Case 1:19-cv-00859-RTH Document 82-2 Filed 04/29/22 Page 5 of 11
`
`FIG. 3
`
`Merchandise 15
`
`Men 0
`
`Kids 5
`
`0 0 1·1
`I ~ ~:) I 7 ~ 3V I 8 (
`
`Toddlers 1
`
`Infants 2
`
`Boys 3 Girls 4
`
`) I 1 8 I 9
`
`19
`
`300
`
`/
`<PRODUCTS>
`
`Petites 13
`
`§113
`
`I
`Hosiery 11
`
`Women 14
`
`Ladies 12
`
`Misses 6
`
`§13
`
`Accessories 7
`
`Jewelry 8 Apparel 9
`
`I 8111 @14 @112
`
`I
`Fashion 10
`Q
`v
`
`115 @16
`I
`Cathy 17
`
`Harry 10
`I __________ _J_ __ ~
`
`Jane 14
`
`John 2
`
`Mary 5
`
`Jacob 6
`
`Phil 18
`
`Deb 19
`
`302
`
`/
`
`<BUYERS>
`
`d •
`r:JJ.
`•
`~
`~ ......
`~ = ......
`
`~
`~
`'"""'
`~-..J
`'"""'
`\0
`\0
`\0
`
`'JJ. =(cid:173)~
`~ ....
`0 ....,
`
`~
`
`,i;;..
`
`Ul
`....
`\0
`
`"'-' =
`
`....
`00
`N
`N
`
`

`

`Case 1:19-cv-00859-RTH Document 82-2 Filed 04/29/22 Page 6 of 11
`
`U.S. Patent
`
`Aug. 17, 1999
`
`Sheet 4 of 4
`
`5,940,822
`
`FIG.4
`
`400
`
`402
`
`Select Next Hierarchy,
`Starting With First
`
`Traverse the Selected
`Hierarchy in Postorder,
`Assigning Non-negative
`Integers to Each Member
`
`404
`
`No
`
`_,.,.,,,.--(cid:173)
`AreAII
`Hierarchies
`Selected?
`
`Yes
`
`406
`
`Assign a Combined Code
`to Each Member
`
`Using the Combined Code,
`Identify the Descendants
`of Each Member
`
`408
`
`

`

`Case 1:19-cv-00859-RTH Document 82-2 Filed 04/29/22 Page 7 of 11
`
`5,940,822
`
`15
`
`2
`The following example is from the Business Intelligence
`domain. One skilled in the art would recognize that there are
`equivalent examples in the domain of Internet text mining.
`Example concepts or groups are (sales by) STATE(s), (sales
`5 by) CITY(s), etc. Concepts and groups have members, and,
`typically, members are related by a hierarchy. For example,
`for the group STATE(s), one natural hierarchy is based on
`geography (e.g., East Coast states, Southwest states, Mid(cid:173)
`west states, Western states, etc.).
`10 Members can be related by more than one hierarchy. For
`example, in a department store, individual products are
`related hierarchically by product categories (e.g.,
`housewares, hardware, etc.), as described in R. A. Kevin, D.
`Kalyanaraman, and D. J. Howard, Product Hierarchy and
`Brand Strategy Influence on the Order of Entry Effect for
`Consumer Packaged Goods, Journal of Product Innovation
`Management, Vol. 13, No. 1. Jan. 1996, which is incorpo(cid:173)
`rated by reference herein. In addition, they are also related
`by employees of the department store, commonly referred to
`as buyers, who are responsible for buying the products, and
`related by the management structure of these employees.
`If members of the hierarchy were represented just by their
`names, e.g., "12 oz. Tide" in a table (e.g., a DETAIL table)
`of transaction records, conventional systems employ one of
`two methods to compute the aggregations.
`In the first method, a sequence of joins are performed
`between the DETAIL table and other tables that carry a map
`of the hierarchy. The number of joins is determined by the
`maximum depth of the hierarchy. After the sequence of
`joins, this method performs aggregations. This method is
`described in more detail in M. Wang and B. Iyer, Efficient
`Roll-Up and Drill-Down Analysis in Relational Databases,
`SIGMOD Data Mining Workshop, 1997, which is incorpo(cid:173)
`rated by reference herein. The first method does not clearly
`address the issue of input/output ("1/0") efficiency and is
`also subject to the known "quirkiness" of commercial
`RDBMS optimizers that sometimes cause the RDBMS to
`execute a query sub-optimally.
`The second technique stores the names of ancestors of
`members along with the members in the DETAIL table. This
`40 second technique requires a large amount of memory for
`storing the names of the ancestors. Therefore, the second
`method is wasteful of space.
`There is a need in the art for an improved method of
`computing aggregations.
`
`1
`ENCODING METHOD OF MEMBERS
`RELATED BY MULTIPLE CONCEPT OR
`GROUP HIERARCHIES AND
`IDENTIFICATION OF MEMBERS IN A
`CORPUS OR A DATABASE THAT ARE
`DESCENDANTS OF ONE OR MORE
`SELECTED CONCEPTS OR GROUPS FROM
`THE ENCODING
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`This invention relates in general to a computer(cid:173)
`implemented encoding system, and more particularly, to an
`encoding system for concept or group hierarchies.
`2. Description of Related Art
`Databases are computerized information storage and
`retrieval systems. A Relational Database Management Sys(cid:173)
`tem (RDBMS) is a database management system (DBMS)
`which uses relational techniques for storing and retrieving
`data. Relational databases are organized into tables which
`consist of rows and columns of data. The rows are formally
`called tuples. A database will typically have many tables and
`each table will typically have multiple tuples and multiple
`columns. The tables are typically stored on random access
`storage devices (RASD) such as magnetic or optical disk 25
`drives for semi-permanent storage.
`RDBMS software using a Structured Query Language
`(SQL) interface is well known in the art. The SQL interface
`has evolved into a standard language for RDBMS software
`and has been adopted as such by both the American National 30
`Standards Institute (ANSI) and the International Standards
`Organization (ISO). The SQL interface allows users to
`formulate relational operations on the tables either
`interactively, in batch files, or embedded in host languages,
`such as C and COBOL. SQL allows the user to manipulate 35
`the data.
`The definitions for SQL provide that a RDBMS should
`respond to a particular query with a particular set of data
`given a specified database content, but the method that the
`RDBMS uses to actually find the required information in the
`tables on the disk drives is left up to the RDBMS. Typically,
`there will be more than one method that can be used by the
`RDBMS to access the required data. The RDBMS will
`optimize the method used to find the data requested in a
`query in order to minimize the computer time used and, 45
`therefore, the cost of doing the query.
`It is common in Internet text mining and Business Intel(cid:173)
`ligence applications for atomic data in a relational database
`to be related by one or more hierarchies of concepts or
`groups. A "concept" or "group" is a generalization of one or
`more keywords or parts of parsed text. A text search query
`against a large corpus (i.e., collection of data) may be
`modeled as a search for various concepts or groups.
`For both Internet text mining and Business Intelligence
`applications, the computation of aggregate functions for 55
`each individual concept or group is a basic, often repeated,
`operation. The aggregate grouping operator is used to rank
`one collection versus another. A. Klug, Access Path in the
`"Abe" Statistical Query Facility, Proc. ACM SIGMOD,
`1982, pp. 161-172, which is incorporated by reference 60
`herein, teaches that special treatment should be given to
`aggregation of groups. Efficiency for the aggregate grouping
`operator was addressed in D. J. Haderle, and E. J. Lynch,
`Evaluation of Column Function on Grouped Data During
`Data Ordering, IBM Technical Disclosure Bulletin, Mar. 10, 65
`1990, pp. 385-386, which is incorporated by reference
`herein.
`
`20
`
`SUMMARY OF IBE INVENTION
`To overcome the limitations in the prior art described
`above, and to overcome other limitations that will become
`apparent upon reading and understanding the present
`50 specification, the present invention discloses a method,
`apparatus, and article of manufacture for a computer imple(cid:173)
`mented encoder for encoding members in a concept hierar(cid:173)
`chy.
`In accordance with the present invention, a query is
`executed in a computer. The query is performed by the
`computer to retrieve data from a database stored on a data
`storage device connected to the computer. Members in the
`database that are related by one or more concept hierarchies
`are encoded. Then, members in one of the concept hierar-
`chies that are descendants of one or more selected concepts
`are identified based on the encoding.
`An object of the invention is to provide an improved
`system for encoding members of hierarchies. Another object
`of the present invention is to encode members of multiple,
`related concept hierarchies. Yet another object of the present
`invention is to identify descendants of a member based on
`the encoding.
`
`

`

`Case 1:19-cv-00859-RTH Document 82-2 Filed 04/29/22 Page 8 of 11
`
`5,940,822
`
`3
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Referring now to the drawings in which like reference
`numbers represent corresponding parts throughout:
`FIG. 1 is an exemplary hardware environment used to
`implement the preferred embodiment of the invention;
`FIG. 2 illustrates a tree structure stored on a data storage
`device that represents a hierarchy of products sold at a Super
`Department Store;
`FIG. 3 illustrates a tree structure stored on a data storage
`device that represents two hierarchies by which items at a
`Super Department Store may be related; and
`FIG. 4 is a flow diagram illustrating the steps performed
`by the encoder.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`In the following description of the preferred embodiment,
`reference is made to the accompanying drawings which
`form a part hereof, and which is shown by way of illustration
`a specific embodiment in which the invention may be
`practiced. It is to be understood that other embodiments may
`be utilized as structural changes may be made without
`departing from the scope of the present invention.
`Hardware Environment
`FIG. 1 is an exemplary hardware environment used to
`implement the preferred embodiment of the invention. The
`present invention is typically implemented using a computer
`100, which generally includes, inter alia, a processor 102,
`random access memory (RAM) 104, data storage devices 30
`106 (e.g., hard, floppy, and/or CD-ROM disk drives, etc.),
`data communications devices 108 (e.g., modems, network
`interfaces, etc.), monitor 110 (e.g., CRT, LCD display, etc.),
`mouse pointing device 112, and keyboard 114. It is envi(cid:173)
`sioned that attached to the computer 100 may be other 35
`devices such as read only memory (ROM), a video card, bus
`interface, printers, etc. Those skilled in the art will recognize
`that any combination of the above components, or any
`number of different components, peripherals, and other
`devices, may be used with the computer 100.
`The computer 100 operates under the control of an
`operating system (OS) 116, such as MYS™, AIX™,
`OS/2™, WINDOWS NT™, WINDOWS™, UNIX™, etc.
`The operating system 116 is booted into the memory 102 of
`the computer 100 for execution when the computer 100 is 45
`powered-on or reset. In turn, the operating system 116 then
`controls the execution of one or more computer programs
`118 by the computer 100. The present invention is generally
`implemented in these computer programs 118, which
`execute under the control of the operating system 116 and 50
`cause the computer 100 to perform the desired functions as
`described herein. Alternatively, the present invention may be
`implemented in the operating system 116 itself. In particular,
`the present invention is typically implemented using rela(cid:173)
`tional database management system (RDBMS) software 55
`120, such as the DB2 product sold by IBM Corporation,
`although it may be implemented with any database man(cid:173)
`agement system (DBMS) software.
`The RDBMS software 120 receives commands from users
`for performing various search and retrieval functions,
`termed queries, against one or more databases stored in the
`data storage devices 106. In the preferred embodiment, these
`queries conform to the Structured Query Language (SQL)
`standard, although other types of queries could also be used
`without departing from the scope of the invention. The 65
`queries invoke functions performed by the RDBMS soft(cid:173)
`ware 120, such as definition, access control, interpretation,
`
`10
`
`4
`compilation, database retrieval, and update of user and
`system data. The RDBMS software 120 invokes the encoder
`122 to perform encoding.
`The operating system 116 and computer programs 118 are
`5 comprised of instructions which, when read and executed by
`the computer 100, causes the computer 100 to perform the
`steps necessary to implement and/or use the present inven(cid:173)
`tion. Generally, the operating system 116 and/or computer
`programs 118 are tangibly embodied in and/or readable from
`a device, carrier, or media, such as memory 102, data storage
`devices 106, and/or data communications devices 108.
`Under control of the operating system 116, the computer
`programs 118 may be loaded from the memory 102, data
`storage devices 106, and/or data communications devices
`108 into the memory 102 of the computer 100 for use during
`15 actual operations.
`Thus, the present invention may be implemented as a
`method, apparatus, or article of manufacture using standard
`programming and/or engineering techniques to produce
`software, firmware, hardware, or any combination thereof.
`20 The term "article of manufacture" (or alternatively, "com(cid:173)
`puter program product") as used herein is intended to
`encompass a computer program accessible from any
`computer-readable device, carrier, or media. Of course,
`those skilled in the art will recognize many modifications
`25 may be made to this configuration without departing from
`the scope of the present invention.
`Those skilled in the art will recognize that the exemplary
`environment illustrated in FIG. 1 is not intended to limit the
`present invention. Indeed, those skilled in the art will
`recognize that other alternative hardware environments may
`be used without departing from the scope of the present
`invention.
`The Encoder
`The present invention provides an encoder 122 that pro(cid:173)
`vides encoding of members related by multiple concept or
`group hierarchies. After encoding, the encoder 122 can
`identify members in a corpus or a database that are descen(cid:173)
`dants of one or more selected concepts or groups in one or
`more hierarchies based on the encoding. The concepts or
`40 groups are known as ancestors. In one pass through the
`corpus or database, the number of occurrences of selected
`concepts or groups are identified, regardless of the number
`of concepts or groups in a hierarchy and regardless of the
`number of hierarchies.
`The encoder 122 provides a simple but elegant system to
`encode members belonging simultaneously to multiple hier(cid:173)
`archies and solves the problems of the two conventional
`systems mentioned earlier that compute aggregations. In one
`embodiment, it is recommended that the present invention
`be combined with a method to compress codes using a
`compression system which exhibits decoding efficiency both
`in central processing unit ("CPU") cycles and memory
`usage. One skilled in the art, however, would recognize that
`the present invention may be used without a compression
`system.
`In AV. Aho, J.E. Hopcroft, and J. D. Ullman, The Design
`and Analysis of Algorithms, Addisson-Wesley, 1974, an
`observation was made that, if a binary tree is labeled by
`increasing natural numbers, during a postorder traversal of
`60 the tree, whether one node is a child of another can be
`determined in an amount of time that does not depend on the
`number of nodes in the tree. The encoder 122 uses this
`concept to take a partial order induced by a hierarchy and
`convert it into a total order, so that all children of an ancestor
`fall into one range (i.e., of values) of this labeling. The
`encoder 122 extends this idea to encode multiple hierarchies
`by yet another elegant form of code construction.
`
`

`

`Case 1:19-cv-00859-RTH Document 82-2 Filed 04/29/22 Page 9 of 11
`
`5,940,822
`
`10
`
`5
`Data captured by point-of-sale ("POS") systems, is the
`primary driver of the market for Business Intelligence
`applications providing data analysis. Consumer Packaged
`Goods ("CPG") manufacturers, retailers, and supermarkets
`are traditional users of these applications. More recently 5
`pharmaceutical drug manufacturers and pharmacies have
`also begun using these applications.
`The following example will focus on a Super Department
`Store. Each item in the store is labeled with a stackable unit
`number ("SKU"). The SKU is based on a natural hierarchy
`and is used to located that item in the store.
`FIG. 2 illustrates a tree structure stored on a data storage
`device 106 that represents a hierarchy of products sold at a
`Super Department Store 200. A tree structure has a root node
`from which all other nodes in the tree depend. A node from
`which other nodes depend is called a parent node. Nodes that 15
`depend from another node are called child nodes. A child
`node is said to be a descendent of a parent node, and a parent
`node is said to be an ancestor of a child node. For example,
`the root node "Super Department Store 28" is an ancestor
`node of each other node in the tree, but it does not have an 20
`ancestor itself. The node "Apparel 14" has an ancestor node
`"Super Department Store 28" and child nodes "Men 0",
`"Shoes l", "Kids 6", and "Women 13". Nodes that have
`ancestor nodes and no child nodes are termed leaf nodes. For
`instance, node "Petites 7" is a leaf node that has an ancestor 25
`node "Women 13" and no child nodes.
`The nodes in FIG. 2 represent members of a domain. Each
`of the members has an associated label (e.g., number) for
`identifying the node in the tree. One skilled in the art would
`recognize that the illustration provided in FIG. 2 is an
`example only and that other hierarchies could be used with
`the present invention.
`The plunging cost of disk and processors are responsible
`for lO0's of millions, perhaps even billions, of transactions
`being recorded on magnetic media reachable by a database
`manager. Roll-up, i.e., accumulating total sales for all
`descendent SKUs of selected members of the hierarchy, is a
`generic operation for Business Intelligence analysis. For
`example, with reference to the Super Department Store
`hierarchy 200, an analyst at the Super Department Store
`headquarters, may wish to roll-up sales on "Apparel 14" for
`"Women 13" and "Supermarket 27" for analyzing relative
`performance of the store in the two categories.
`On-line analytical processing ("OLAP") tools such as
`Arbor's ESSBASE, Informix's METACUSE, etc., store 45
`frequently computed aggregations in essentially the main
`memory database on a client personal computer ("PC"). If a
`pre-computed aggregate is not available in the main memory
`database of the client PC, an SQL query is issued against the
`database manager hosting the Detail table data.
`One efficient execution method for the query is a single
`pass over the data in the Detail table. The encoder 122
`demonstrates that if members of the hierarchy are labeled by
`a postorder traversal of the tree representing one hierarchy,
`all children of an ancestor are bounded by the labels of the 55
`ancestor and the lowest numbered child. Next, if the mem(cid:173)
`bers appearing in the database were encoded by such labels,
`multiple aggregates of members and all their descendants
`are computable in one pass of the data, as described further
`in M. Wang and B. Iyer, Efficient Roll-Up and Drill-Down 60
`Analysis in Relational Databases, SIGMOD Data Mining
`Workshop, 1997, which is incorporated by reference herein.
`For example, in the Super Department Store hierarchy 200
`of FIG. 2, labels for all SKU's in the "Apparel 14" for
`"Women 13" member are in the range of (7, 14) and labels 65
`for SKU's in the "Supermarket" member are in the range
`(24, 27).
`
`6
`FIG. 3 illustrates a tree structure stored on a data storage
`device 106 that represents two hierarchies by which items at
`a Super Department Store may be related. One of the
`hierarchies is a products hierarchy 300, which includes some
`of the members of the Super Department Store hierarchy
`200, and the other hierarchy is a buyers hierarchy 302
`representing buyers who purchase products for the Super
`Department Store. FIG. 3 illustrates that members are
`related by more than one hierarchy, i.e., products 300 and
`buyers 302. For example, John 2 is the buyer for "Men 0",
`"Toddlers l", "Infants 2", "Boys 3", and "Girls 4" products.
`For a single hierarchy, the encoder 122 demonstrates that
`predicates that capture a range of consecutive values identify
`a member of the hierarchy and all its descendants. For the
`example hierarchies illustrated in FIG. 3, users may want a
`report of the aggregate sales of all "Kids l" products
`purchased by buyers managed by "Phil 18". The encoder
`122 encodes members with labels from which the encoder
`122 can determine whether the member is a descendant of a
`specified ancestor in any hierarchy. In the worst case, the
`time taken to perform encoding is proportional to the
`number of hierarchies. The label is used for multiple hier(cid:173)
`archies in a similar manner as the label for a single hierarchy.
`Consider the hierarchy on members illustrated in FIG. 3.
`The encoder 122 first traverses the products hierarchy 300 in
`postorder fashion and assigns non-negative integers to each
`member, in natural order. For example, the encoder 122
`assigns the label 1 to the member "Toddler" for the products
`hierarchy 300. As there are 16 members of the products
`30 hierarchy 300, the encoder 122 uses 16 integers (0 through
`15 inclusive) for labeling.
`Next, the encoder 122 traverses the buyers hierarchy 302
`in postorder fashion and assigns non-negative integers to
`each member, in natural order. For example, the encoder 122
`35 assigns the label 7 to the member "Toddler" for the buyers
`hierarchy 302.
`The encoder 122 encodes each member of the products
`hierarchy 300 with a combined code derived from multi(cid:173)
`plying the label assigned to the member for the buyers
`40 hierarchy 302 with the maximum number of labels assigned
`(e.g., 16) in the products hierarchy 300 and adding the label
`assigned to the member for the products hierarchy 300. For
`example, the encoder 122 computes a combined code for the
`member "Toddler" as 7x16+1=113.
`When the encoder 122 finds this combined code with the
`member, the encoder 122 can determine the labels for the
`member from each hierarchy of which it is a member ( e.g.,
`the products and buyers hierarchies 300, 302). The encoder
`122 determines the label for the member "Toddler" in the
`50 products hierarchy 300 by computing the combined code
`mod the maximum number of labels assigned and subtract(cid:173)
`ing the label assigned to the member for the products
`hierarchy 300 (e.g., ((113 mod 16)-1)=1). The encoder 122
`determines the label for the member "Toddler" in the buyers
`hierarchy 302 by subtracting the label assigned to the
`member for the products hierarchy 300 from the combined
`code and dividing this result by the maximum number of
`labels ( e.g., ((113-1)/16)= 7)).
`Referring back to the products and buyers hierarchies 300
`and 302 illustrated in FIG. 3, once the combined code 113,
`is unraveled into code 1 for the products hierarchy 300, the
`encoder 122 can determine that the member is a descendant
`of concept "Kids", which has a range (1, 5), in the products
`hierarchy 300. Once the combined code 113, is unraveled
`into code 7 for the buyers hierarchy 302, the encoder 122 can
`determine that the member is a descendant of "Phil", which
`has a range (7, 18) in the buyers hierarchy 302.
`
`

`

`Case 1:19-cv-00859-RTH Document 82-2 Filed 04/29/22 Page 10 of 11
`
`5,940,822
`
`7
`The following discussion provides a more formal descrip(cid:173)
`tion of the present invention. First, let h<i> denote the
`number of nodes in the tree representing hierarchy <i> ( e.g.,
`for hierarchy 1, the number of nodes is represented by hl).
`Then, assume that there are four hierarchies, and each
`member defined in a Detail table belongs to every hierarchy.
`For the hierarchies, hl is not larger (in terms of number of
`members, i.e., nodes in the tree) than h2 which, in turn, is not
`larger than h3, and that, in turn, is not larger than h4.
`Independent traversals of the four hierarchies produce four
`labels (i.e., codes cl, c2, c3, c4) for each leaf, for hierarchies
`1, 2, 3 and 4, respectively.
`The encoder 122 computes the combined code for a leaf
`appearing in these four hierarchies with the following for(cid:173)
`mula:
`
`combined code-cl +c2xhlxh2+c4xhlxh2xh3
`
`Upon obtaining the combined code of a member, the
`encoder 122 computes the labels for the member in its
`various hierarchies with the following formulas:
`
`(since hl <- h2)
`cl - combined code % hl
`(since h2 <- h3)
`c2 - ((combined code - c1)/h1)%h2
`(since h3 <- h4)
`c3 - ((combined code - cl - c2 x hl)/(hl x h2))%h3
`c4 - ((combined code - cl - c2 x hl - c3 x hl x h2)/(h1 x h2 x h3))
`
`15
`
`8
`native embodiments for accomplishing the present inven(cid:173)
`tion. For example, any type of computer, such as a
`mainframe, minicomputer, or personal computer, or com(cid:173)
`puter configuration, such as a timesharing mainframe, local
`5 area network, or standalone personal computer, could be
`used with the present invention.
`In summary, the present invention discloses a method,
`apparatus, and article of manufacture for an encoder for
`encoding members in a concept hierarchy. The present
`10 invention provides an improved system for encoding mem(cid:173)
`bers of hierarchies. The present invention also encodes
`members of multiple, related concept hierarchies.
`Additionally, the present invention identifies descendants of
`a member based on the encoding.
`The foregoing description of the preferred embodiment of
`the invention has been presented for the purposes of illus(cid:173)
`tration and description. It is not intended to be exhaustive or
`to limit the invention to the precise form disclosed. Many
`modifications and variations arc possible in light of the
`20 above teaching. It is intended that the scope of the invention
`be limited not by this detailed description, but rather by the
`claims appended hereto.
`What is claimed is:
`1. A method of executing a query in a computer, the query
`25 being performed by the computer to retrieve data from a
`database stored on a data storage device connected to the
`computer, the method comprising the steps of:
`encoding members in the database related by one or more
`concept hierarchies, wherein the encoding represents
`one or more concepts; and
`identifying members in one of the concept hierarchies that
`are descendants of one or more selected concepts based
`on the encoding by traversing each of the members
`related by the concept hierarchies only once.
`2. The method of claim 1 above, wherein the step of
`encoding further comprises the steps of:
`traversing each of the members in each of the concept
`hierarchies in postorder; and
`assigning a label to each of the traversed members.
`3. A method of executing a query in a computer, the query
`being performed by the computer to retrieve data from a
`database stored on a data storage device connected to the
`computer, the method comprising the steps of:
`encoding members in the database related by one or more
`concept hierarchies by traversing each of the members
`in each of the concept hierarchies in postorder and
`assigning a label comprised of a non-negative integer to
`each of the traversed members; and
`identifying members in one of the concept hierarchies that
`are descendants of one or more selected concepts based
`on the encoding.
`4. A method of executing a query in a computer, the query
`being performed by the computer to retrieve data from a
`55 database stored on a data storage device connected to the
`computer, the method comprising the s