US 6,563,521 B1Grant
Method, article and apparatus for organizing information
Issue Date:2003-05-13
•39 Claims
•5 Drawing Sheets
Abstract
Items related by a tree are further organized by determining a depth-first search of the tree having an optimum value associated therewith. The associated value of a depth-first search is based upon an order of considering items in the tree, and similarity values between pairs of items in the tree.
Metadata
Inventor
- Cary D. Perttunen
Application Information
Application Number:US 09/594,058
Filing Date:2000-06-14
Priority Date:2000-06-14
Art Unit:7
Classifications
IPC:
G09G 500
Field of Search:
345764345853345854345855345711345712345713345802345803345804707 3707 5707203
Patent Drawings (5 sheets)
Description
Related Applications
[0002] The present application is related to the application entitled “METHODS, ARTICLES AND APPARATUS FOR VISIBLY REPRESENTING INFORMATION AND FOR PROVIDING AN INPUT INTERFACE”, having Ser. No. 09/243,595, filed Feb. 3, 1999, whose disclosure is hereby incorporated by reference into the disclosure of the present application, and the application entitled “BROWSING METHODS, ARTICLES AND APPARATUS”, having Ser. No. 09/533,545, filed Mar. 23, 2000, whose disclosure is hereby incorporated by reference into the disclosure of the present application.
Technical Field
[0003] The present invention relates to methods, articles and apparatus for organizing information.
Background of the Invention
[0004] Many Internet portals provide a search engine with which a user may initiate an Internet search. The search engine returns a list of Web pages based upon a search expression received from the user.
[0005] Some search engines display a similarity value for each Web page in the list. Each similarity value numerically indicates a degree of correlation or relevance between its corresponding Web page and the search expression.
[0006] Oftentimes, the Web pages in the list are sorted based on the similarity values. By sorting the Web pages in this manner, the list presents highly-relevant Web pages before lesser-relevant Web pages.
[0007] Some Internet portals provide directories of Web pages. These directories provide a tree-like structure of categories and subcategories within which Web pages are classified.
Brief Description of the Drawings
[0008] The present invention is pointed out with particularity in the appended claims. However, other features are described in the following detailed description in conjunction with the accompanying drawings in which:
[0009] FIGS. 1, 2(A-B) and 3 provide a flow chart of an embodiment of a method of organizing item information;
[0010] FIG. 4 schematically shows a tree which relates items in an example;
[0011] FIG. 5 shows one example of a planar depiction of an optimum ordering of the items in the tree; and
[0012] FIG. 6 shows another example of a depiction of the optimum ordering of the items in the tree.
Detailed Description of Preferred Embodiments
[0013] Improved methods, articles and apparatus for organizing information are disclosed herein. Items related by a tree are further organized by determining a depth-first search of the tree having an optimum value associated therewith. The associated value of a depth-first search is based upon an order of considering items in the tree, and similarity values between pairs of items in the tree.
[0014] FIGS. 1, 2 and 3 provide a flow chart of an embodiment of a method of organizing item information. As indicated by block 20, the method comprises providing a tree which relates a plurality of items. Various computer-readable data structures can be used to represent the tree in a computer-readable form using a computer-readable medium.
[0015] Examples of an item include, but are not limited to a computer address, a computer site, a Web page, audio content, an image, computer software, an information category, an information subcategory, an information source, a logical disk for a computer, a computer directory, a computer-readable file, computer-readable data, a computer-readable message, a computer-readable description and/or image of a physical object, a computer-readable description and/or image of a purchasable item, a general category, and a general subcategory. Of particular interest are computer-readable items in a markup language such as HTML (hypertext markup language), HDML (handheld device markup language), or WML (wireless markup language). Also of interest are computer-readable messages such as those from either USENET or a Web page which provides an on-line discussion forum.
[0016] Before proceeding, a review of trees and graph-related terminology is provided. A graph is definable by a set of nodes and a set of edges joining or associating different pairs of distinct nodes. The edges in the graph may be either directed or undirected.
[0017] Alternative terminology may be used to describe the graph. Examples of synonyms of “node” include, but are not limited to, “vertex” and “state”. Examples of synonyms of “edge” include, but are not limited to, “arc” and “link”. Therefore, the herein-disclosed methods, articles, apparatus, and examples should not be limited by the selected terminology used to describe the graph.
[0018] A first node is said to be adjacent to a second node if there is an edge from the first node to the second node. A path is definable by a sequence of nodes wherein each consecutive pair of nodes in the sequence is adjacent.
[0019] A tree is a graph having a unique path from a designated node, called a root node, to each of its other nodes. If the tree is undirected, then any of its nodes can be designated to be the root node. An undirected tree can be made into a directed tree by directing all edges away from the designated root node.
[0020] Each node in a directed tree, except for the root node, is a child node of a unique parent node from which an edge is directed thereto. Nodes having the same parent node are called siblings. Nodes of a directed tree with no children are called leaf nodes. Nodes having at least one child are called internal nodes. The level number of a node is defined as the number of edges in the path between the node and the root node. The height of the tree is the largest level number of any node.
[0021] If each internal node of a rooted tree has m children, the tree is called an m-ary tree. If m=1, the tree is unary. If m=2, the tree is binary. If m=3, the tree is ternary.
[0022] Referring back to block 20, each of the items is represented by a corresponding node of the tree. Relationships between items are represented by edges in the tree. Examples of edge-represented relationships between items include, but are not limited to, a degree of similarity, a hyperlink, an associative link, a state of being an element of, a state of being contained in, a state of being associated with, a state of reporting to, a state of being in a category, a state of depending from, and a state of being a reply to.
[0023] It is preferred that the tree is non-unary. By being non-unary, the tree has at least one internal node with two or more child nodes. It is also preferred that the tree has a height of at least two. It is further preferred that the tree has more leaf nodes than a number of child nodes emanating from its root node.
[0024] Optionally, the tree is provided based upon a search. It should be appreciated, however, that embodiments of the method may be performed absent the search.
[0025] A search expression may be user-entered using an input device such as a keyboard, a touch screen, a touch pad or a voice input device. The search expression may contain one or more words in the form of either a Boolean search expression or a natural language search expression, for example. The search expression may include information from a plurality of user-enterable fields to limit the scope of the search. The search expression may include an image or encoded audio.
[0026] A search is performed based on the search expression. The search yields search results comprising a plurality of items, the plurality of items being a subset of a larger set of items.
[0027] A first plurality of similarity values between the search expression and the plurality of items are determined. Each of the first plurality of similarity values indicates a degree of similarity, relevance or correlation between the search expression and a corresponding one of the items of the subset.
[0028] A second plurality of similarity values between a corresponding plurality of pairs of the items are determined. Each of the second plurality of similarity values indicates a degree of similarity, relevance or correlation between a corresponding pair of items of the subset.
[0029] The tree may be provided by determining an optimum path tree based upon the first plurality of similarity values and the second plurality of similarity values. The optimum path tree indicates a respective optimum path between the search expression and each of the plurality of items.
[0030] The optimum path between the search expression and an item has an optimum function value of similarity values between the search expression and the item. Examples of the function whose optimum value dictates the optimum path include, but are not limited to, a sum of similarity values between the search expression and the item, and a product of similarity values between the search expression and the item. To determine an optimum product of similarity values, an additive optimum path algorithm may be performed on a logarithm of the similarity values. For example, if the similarity values are numerical values between 0% and 100%, then an additive minimum path algorithm may be performed on a negative logarithm of the non-zero similarity values, e.g. −log(similarity value), to determine a maximum product of similarity values.
[0031] As is known in the art of network algorithms, examples of algorithms to compute the shortest paths include, but are not limited to, Dijkstra's algorithm and Floyd's algorithm. Those having ordinary skill can review shortest path algorithms on pp. 123-127 of A. Tucker, Applied Combinatorics, Second Edition, John Wiley & Sons, 1984, which is hereby incorporated by reference into this disclosure.
[0032] Alternatively, the tree may be provided by determining a spanning tree based upon the first plurality of similarity values and the second plurality of similarity values. Examples of the spanning tree include, but are not limited to, an optimum spanning tree such as a minimum spanning tree, and a search tree.
[0033] The optimum spanning tree has an optimum function value of similarity values. Examples of the function whose optimum value dictates the optimum spanning tree include, but are not limited to, a sum of similarity values, and a product of similarity values. To determine an optimum product of similarity values, an additive optimum spanning tree algorithm may be performed on a logarithm of the similarity values.
[0034] As is known in the art of network algorithms, examples of algorithms to compute a minimum spanning tree include, but are not limited to, Kruskal's algorithm and Prim's algorithm. Those having ordinary skill can review minimum spanning trees on pp. 127-131 of A. Tucker, Applied Combinatorics, Second Edition, John Wiley & Sons, 1984, which is hereby incorporated by reference into this disclosure.
[0035] Examples of the search tree include, but are not limited to, a depth-first search spanning tree, a breadth-first search spanning tree, or a best-first search spanning tree. Those having ordinary skill can review search trees on pp. 80-122 of A. Tucker, Applied Combinatorics,Second Edition, John Wiley & Sons, 1984, which is hereby incorporated by reference into this disclosure.
[0036] For computer-readable messages, an edge in the tree may indicate that one message is a reply to another message. Thus, a reply message is a child of its parent message, and two reply messages to the same parent message are siblings.
[0037] Each base message, i.e. each message that begins a new thread, may have an associated edge to a root node in the tree. If a search is performed, the root node may represent the search expression. Regardless of whether a search is performed, the root node may represent a discussion group of which the messages are elements.
[0038] As indicated by block 22, the method comprises providing a depth-first search sequence for considering items in the tree. An initial depth-first search sequence may be provided by initializing, for each of the internal items having at least two child items in the tree, a respective sequence for considering its respective child items.
[0039] As indicated by block 24, the method comprises providing a memory which is to indicate, for each level number from one to a height of the tree, a last-considered item associated with the level number in the depth-first search sequence. The memory may be initialized to indicate that no items have been considered at each level number from one to the height of the tree.
[0040] As indicated by block 26, the method comprises considering a first non-root item in the depth-first search sequence as a current item. As indicated by block 30, the method comprises determining if the current item is an internal item of the tree. If the current item is an internal item of the tree, an act of determining if at least one of the leaf items had been previously considered in the depth-first search sequence is performed (block 32).
[0041] If at least one of the leaf items had been previously considered in the depth-first search sequence, a similarity value between the current item and the last-considered item associated with the level number of the current item is used to determine a value associated with the depth-first search sequence (block 34). As indicated by block 36, the current item is indicated as the last-considered item associated with the level number of the current item.
[0042] Referring back to block 30, if the current item is not an internal item of the tree, and thus is a leaf item of the tree, a subprocess is performed for each level number L from the level number of the current item to the height of the tree (block 40). The subprocess comprises determining if at least one of the leaf items had been previously considered in the depth-first search sequence (block 42) and determining if the last-considered item associated with level number L is the same as the last-considered item associated with level number L-1 (block 44). Since the root item is always the last-considered item associated with level number 0, the last-considered item associated with level number 1 always differs from the last-considered item associated with level number 0. Thus, block 44 may be skipped for L=1.
[0043] If at least one of the leaf items has been previously considered in the depth-first search sequence and the last-considered item associated with level number L differs from the last-considered item associated with level number L-1, a similarity value between the current item and the last-considered item associated with the level number L is used to determine a value associated with the depth-first search sequence (block 50). As indicated by block 52, the subprocess is performed one or more times for each level number indicated in block 40.
[0044] Each of the similarity values described with reference to blocks 34 and 50 indicates a degree of similarity, relevance or correlation between a corresponding pair of items. The similarity values described with reference to blocks 34 and 50 may be the same as the second plurality of similarity values used to determine the tree. Alternatively, the similarity values described with reference to blocks 34 and 50 may differ from the second plurality of similarity values used to determine the tree.
[0045] As indicated by block 56, a subprocess is performed for each level number L from the level number of the current item to the height of the tree. As indicated by block 60, the current item is indicated as the last-considered item associated with the level number L. As indicated by block 62, the subprocess is performed one or more times for each level number indicated in block 56.
[0046] As indicated by block 64, a subsequent item in the depth-first search sequence is considered as the current item. Flow of the method may be directed back to block 26 until no subsequent items exist in the depth-first search sequence. Optionally, block 26 may be modified to further iterate, after the final item, from the first non-root item to the first leaf item. In this case, items from the first non-root item to the first leaf item are considered twice.
[0047] The value associated with the depth-first search sequence is a function of the similarity values identified in blocks 34 and 50. For example, the function may be based on a sum of the aforementioned similarity values, a product of the aforementioned similarity values, an average of the aforementioned similarity values such as either an arithmetic mean or a geometric mean of the aforementioned similarity values, a maximum of the aforementioned similarity values, or a minimum of the aforementioned similarity values.
[0048] The function may be partially evaluated each time a similarity value is identified in blocks 34 and 50. Alternatively, the function may be evaluated after all of the similarity values have been identified in blocks 34 and 50 for all iterations of block 26. In general, the similarity values identified in blocks 34 and 50 may be used at any time to evaluate the function and thus determine the value associated with the depth-first search sequence.
[0049] As indicated by block 66, the depth-first search sequence is modified. The depth-first search sequence may be modified by modifying the sequence for considering child items for each of at least one of the internal items having at least two child items in the tree. Flow of the method is directed back to block 24 to initiate the process of determining a value associated with the modified depth-first search sequence. The memory provided for indicating last-considered items in the initial depth-first search sequence may be either different or the same as the memory provided for indicating last-considered items for the modified depth-first search sequence.
[0050] In this way, values associated with a plurality of depth-first search sequences of the tree are determined. Optionally, values associated with all possible depth-first search sequences of the tree may be determined. The number of possible depth-first search sequences of the tree is equal to the product of the factorial of each internal node's number of children nodes.
[0051] Using an embodiment of the herein-disclosed method for some functions, two depth-first search sequences have the same value associated therewith if one has an order of considering leaf items which is the reverse of the other. Thus, in these and other cases, values associated with at most half of all possible depth-first search sequences of the tree may be determined. The depth-first search sequences which are considered may be limited by prohibiting reverse-equivalent sequences for considering child items of the root item. A branch-and-bound approach, for example, may be used to limit consideration to less than half of all possible depth-first search sequences.
[0052] Using another embodiment of the herein-disclosed method for some functions, two depth-first search sequences have the same value associated therewith if one has an order of considering leaf items which is either a cyclic-equivalent or a reverse cyclic-equivalent of the other. For example, a sequence A-B-C-D has three cyclic-equivalent sequences B-C-D-A, C-D-A-B and D-A-B-C, and four reverse cyclic-equivalent sequences D-C-B-A, A-D-C-B, B-A-D-C and C-B-A-D. Thus, in these and other cases, values associated with at most M/(2*N) sequences may be determined, where M is the number of all possible depth-first search sequences of the tree, and N is the number of child items of the root item. The depth-first search sequences which are considered may be limited by prohibiting cyclic-equivalent and reverse cyclic-equivalent sequences for considering child items of the root item. A branch-and-bound approach, for example, may be used to limit consideration to less than M/(2*N) sequences.
[0053] As indicated by block 70, the method comprises determining which depth-first search sequence has an optimum value associated therewith. Depending on the function used to determine values associated with depth-first search sequence, this act may comprise either determining which depth-first search sequence has a maximum associated value, or determining which depth-first search sequence has a minimum associated value.
[0054] As indicated by block 72, a signal is outputted to display a planar depiction of the tree in which the items are ordered according to the depth-first search sequence having the optimum value. The planar depiction may comprise a plurality of regions to visibly represent the items, wherein adjacent items in the tree are represented by radially-adjacent regions, and wherein pairs of items identified in blocks 34 and 50 for the depth-first search sequence having the optimum value are represented by angularly-adjacent regions. The planar depiction may be determined in accordance with the teachings in the patent application having Ser. No. 09/243,595, which is incorporated by reference into the present disclosure.
[0055] The root item may be represented by a region having a shape at least partially defined by an outer arc. Each of the non-root, internal items may be represented by a corresponding region having a corresponding shape at least partially defined by a corresponding outer arc, a corresponding inner arc approximately equivalent to the corresponding outer arc of its parent in the tree, and a corresponding angular width approximately equal to a sum of each corresponding angular width of its at least one child in the tree. Each of the leaf items may be represented by a corresponding region having a corresponding shape at least partially defined by a corresponding outer arc, a corresponding inner arc approximately equivalent to the corresponding outer arc of its parent item in the tree, and a corresponding angular width approximately equal to the corresponding angular width of its parent item in the tree. If the depiction is to span an overall angular width of about 360 degrees, it is preferred that block 26 be modified to further iterate, after the final item, from the first non-root item to the first leaf item.
[0056] In these cases and other cases, the herein-disclosed method acts to determine an arrangement of a plurality of shapes which represent the non-root, internal items and the leaf items, which optimizes a function of similarity values between pairs of items represented by angularly-adjacent pairs of the shapes and has radially-adjacent pairs of the shapes representing adjacent pairs of the items in the tree.
[0057] Alternatively, the planar depiction may comprise a plurality of regions to visibly represent the items, wherein adjacent items in the tree are represented by a visible edge between their corresponding regions, and wherein child items are ordered (either left-to-right, right-to-left, top-to-bottom, bottom-to-top, clockwise or counterclockwise, for example) according to the sequence associated with the depth-first search sequence having the optimum value.
[0058] Examples of the signal include, but are not limited to, a display signal and a computer data signal. The display signal may be communicated either through a video cable or wirelessly to a display device. The display device displays the planar depiction based on the display signal. Examples of the display device include, but are not limited to, a computer monitor, a television, a liquid crystal display, a cathode ray tube, and a gas plasma display.
[0059] The computer data signal may be communicated via a computer network. Examples of the network include, but are not limited to, an internet, an intranet and an extranet. The computer data signal may include computer program code to assist in displaying the planar depiction. Of particular interest is the signal being representative of code in a markup language such as HTML, HDML or WML.
[0060] The computer data signal is received by a computer in communication with the computer network. The computer generates a display signal to display the planar depiction on the display device.
[0061] Each of the regions of the planar depiction may be user-selectable. In this case and other cases, the above-described method may be augmented to perform an act based on a selection of an item from the tree. The act may be performed in response to receiving a user action via an input device. The act may include, but is not limited to, any of the following examples. If the plurality of items are associated with purchasable items, the act may include: providing information for the particular purchasable item, and/or performing a transaction for the particular purchasable item. If the plurality of items include a plurality of computer addresses, the act may include linking to the particular computer address. If the plurality of items include a plurality of computer-readable files, the act may include opening the computer-readable file. If the plurality of items include a plurality of records from a database, the act may include any combination of retrieving, processing, displaying, modifying, or deleting the record from the database.
[0062] Examples of the input device include, but are not limited to, a pointing device, a keyboard, and a voice input device. Examples of pointing devices include, but are not limited to, a mouse, a touchpad, a trackball, a joystick, a pointing stick and a touchscreen. A selection of an item is detected in response to a user-initiated event for the item's associated region. Examples of the user-initiated event include, but are not limited to, an on-click event, a double-click event, a mouse-move event, a mouse-over event, a mouse-out event, a mouse-up event, and a key depression event.
[0063] Optionally, the method may further comprise outputting a signal to display a user-viewable advertisement. The signal to display the user-viewable advertisement may encode an image and/or graphics in the advertisement, or may provide a link to an image and/or graphics in the advertisement. The user-viewable advertisement may be viewable by the user while a visible depiction of the optimum ordering of the tree is being displayed. Here, for example, the user-viewable advertisement and the visible depiction may be contained within a single Web page.
[0064] An example is given to illustrate one embodiment of a method of organizing information. As should be appreciated, the scope of the present disclosure is not to be limited by this example. Other practical applications are contemplated based on the examples given in the patent applications having Ser. Nos. 09/243,595 and 09/533,545.
[0065] For purposes of illustration and example, consider a search engine generating fourteen items based on a search expression. FIG. 4 schematically shows a tree which relates the items. Each item is represented by a circle. The search expression is represented by a square. The search expression is the root node of the tree. Adjacent items in the tree are represented by a visible line segment between their corresponding regions.
[0066] For each of the items, TABLE I shows an initial sequence for considering its child items in a depth-first search of the tree. The initial sequence is used to provide an initial depth-first search sequence for considering items in the tree.
[0067] TABLE II illustrates one embodiment of determining a value associated with the initial depth-first search sequence. Each row in TABLE II represents an iteration associated with one of the items. From left to right, the columns in TABLE II indicate: (a) if at least one leaf item had been previously considered, (b) the current item being considered in the depth-first search sequence of the tree, (c) whether the current item is an internal item or a leaf item of the tree, (d) the level number of the current item, (e) a last-considered item associated with level number 1, (f) a last-considered item associated with level number 2, (g) a last-considered item associated with level number 3, (h) a last-considered item associated with level number 4, and (i) which similarity values are used to determine the value.
| TABLE I | ||
|---|---|---|
| Sequence for | ||
| considering | ||
| Item | child items | |
| S | A G N | |
| A | B F | |
| B | C D | |
| C | — | |
| D | E | |
| E | — | |
| F | — | |
| G | H I M | |
| H | — | |
| I | J K L | |
| J | — | |
| K | — | |
| L | — | |
| M | — | |
| N | — | |
[0068] As illustrated in TABLE II, fifteen similarity values are used to determine the value associated with the initial depth-first search sequence. The fifteen similarity values consist of a similarity value between items C and D, a similarity value between items C and E, a similarity value between items B and F, a similarity value between items D and F, a similarity value between items E and F, a similarity value between items A and G, a similarity value between items F and H, a similarity value between items H and I, a similarity value between items H and J, a similarity value between items J and K, a similarity value between items K and L, a similarity value between items I and M, a similarity value between items L and M, a similarity value between items G and N, and a similarity value between items M and N. In this example, the function used to determine the value associated with the initial depth-first search sequence is a sum of the fifteen similarity values.
| TABLE II | ||||||||
|---|---|---|---|---|---|---|---|---|
| At least one | Similarity | |||||||
| leaf item | values used in | |||||||
| previously | Internal | function | ||||||
| considered? | Item | or leaf? | Level | 1 | 2 | 3 | 4 | evaluation |
| No | A | Internal | 1 | A | — | — | — | — |
| No | B | Internal | 2 | A | B | — | — | — |
| No | C | Leaf | 3 | A | B | C | C | — |
| Yes | D | Internal | 3 | A | B | D | C | (C, D) |
| Yes | E | Leaf | 4 | A | B | D | E | (C, E) |
| Yes | F | Leaf | 2 | A | F | F | F | (B, F) (D, F) |
| (E, F) | ||||||||
| Yes | G | Internal | 1 | G | F | F | F | (A, G) |
| Yes | H | Leaf | 2 | G | H | H | H | (F, H) |
| Yes | I | Internal | 2 | G | I | H | H | (H, I) |
| Yes | J | Leaf | 3 | G | I | J | J | (H, J) |
| Yes | K | Leaf | 3 | G | I | K | K | (J, K) |
| Yes | L | Leaf | 3 | G | I | L | L | (K, L) |
| Yes | M | Leaf | 2 | G | M | M | M | (I, M) (L, M) |
| Yes | N | Leaf | 1 | N | N | N | N | (G, N) (M, N) |
[0069] TABLE III shows a modified sequence for considering child items of the search expression in a depth-first search of the tree. The modified sequence is used to provide a second depth-first search for considering items in the tree.
| TABLE III | ||
|---|---|---|
| Sequence for | ||
| considering | ||
| Item | child items | |
| S | G A N | |
| A | B F | |
| B | C D | |
| C | — | |
| D | E | |
| E | — | |
| F | — | |
| G | H I M | |
| H | — | |
| I | J K L | |
| J | — | |
| K | — | |
| L | — | |
| M | — | |
| N | — | |
[0070] TABLE IV illustrates one embodiment of determining a value associated with the second depth-first search sequence. As illustrated, sixteen similarity values are used to determine the value associated with the second depth-first search sequence. The sixteen similarity values consist of a similarity value between items H and I, a similarity value between items H and J, a similarity value between items J and K, a similarity value between items K and L, a similarity value between items I and M, a similarity value between items L and M, a similarity value between items A and G, a similarity value between items B and M, a similarity value between items C and M, a similarity value between items C and D, a similarity value between items C and E, a similarity value between items B and F, a similarity value between items D and F, a similarity value between items E and F, a similarity value between items A and N, and a similarity value between items F and N. In this example, the function used to determine the value associated with the second depth-first search sequence is a sum of the sixteen similarity values.
| TABLE IV | ||||||||
|---|---|---|---|---|---|---|---|---|
| At least one | Similarity | |||||||
| leaf item | values used in | |||||||
| previously | Internal | function | ||||||
| considered? | Item | or leaf? | Level | 1 | 2 | 3 | 4 | evaluation |
| No | G | Internal | 1 | G | — | — | — | — |
| No | H | Leaf | 2 | G | H | H | H | — |
| Yes | I | Internal | 2 | G | I | H | H | (H, I) |
| Yes | J | Leaf | 3 | G | I | J | J | (H, J) |
| Yes | K | Leaf | 3 | G | I | K | K | (J, K) |
| Yes | L | Leaf | 3 | G | I | L | L | (K, L) |
| Yes | M | Leaf | 2 | G | M | M | M | (I, M) (L, M) |
| Yes | A | Internal | 1 | A | M | M | M | (A, G) |
| Yes | B | Internal | 2 | A | B | M | M | (B, M) |
| Yes | C | Leaf | 3 | A | B | C | C | (C, M) |
| Yes | D | Internal | 3 | A | B | D | C | (C, D) |
| Yes | E | Leaf | 4 | A | B | D | E | (C, E) |
| Yes | F | Leaf | 2 | A | F | F | F | (B, F) (D, F) |
| (E, F) | ||||||||
| Yes | N | Leaf | 1 | N | N | N | N | (A, N) (F, N) |
[0071] The above process is repeated for additional depth-first search sequences by modifying a sequence for considering child items for at least one item. Potential sequences for considering child items of item S are A-G-N, A-N-G, G-A-N, G-N-A, N-A-G and N-G-A. Potential sequences for considering child items of item A are B-F and F-B. Potential sequences for considering child items of item B are C-D and D-C. Item D has one potential sequence for considering its child, namely item E. Potential sequences for considering child items of item G are H-I-M, H-M-I, I-H-M, I-M-H, M-H-I and M-I-H. Potential sequences for considering child items of item I are J-K-L, J-L-K, K-J-L, K-L-J, L-J-K and L-K-J.
[0072] Values associated with all possible depth-first search sequences of the tree may be determined. The number of possible depth-first search sequences of the tree is equal to the product of 3!, 2!, 2!, 1!, 3! and 3!, which equals 864.
[0073] Preferably, values associated with at most half of all possible depth-first search sequences of the tree (432 in this example) are determined. In this case, the depth-first search sequences which are considered are limited by prohibiting reverse-equivalent sequences for considering child items of the root item, namely the item S. In this example, the sequences for considering child items of the item S may be limited to A-G-N, A-N-G and G-A-N (whose reverse-equivalent sequences are N-G-A, G-N-A and N-A-G, respectively).
[0074] Based on the values, the depth-first search sequence having a maximum value associated therewith is determined. For purposes of illustration and example, consider that the value associated with the second depth-first search sequence is greater than or equal to values associated with the other depth-first search sequences.
[0075] A signal may be outputted to display a planar depiction of the tree in which the items are ordered according to the second depth-first search sequence. FIG. 5 shows one example of a planar depiction of the tree having the aforementioned ordering of the items. The planar depiction comprises a plurality of regions to visibly represent the items, wherein adjacent items in the tree are represented by a visible line segment between their corresponding regions. Child items are ordered from left-to-right according to the sequence associated with the second depth-first search sequence.
[0076] FIG. 6 shows an alternative depiction of the tree having the aforementioned ordering of the items. In this depiction, the items are visibly represented by a plurality of regions. Adjacent items in the tree are represented by radially-adjacent regions. Pairs of items indicated in the rightmost column of TABLE IV are represented by angularly-adjacent regions.
[0077] A browsing sequence may be provided in accordance with the second depth-first search sequence. In this case, the sequence for browsing the items is G-H-I-J-K-L-M-A-B-C-D-E-F-N (see the second column of TABLE IV). The browsing sequence and the tree may be used in accordance with the teachings in the patent application having Ser. No. 09/533,545, which is incorporated by reference into the present disclosure.
[0078] In the above example, cyclic-equivalent and reverse cyclic-equivalent sequences may be prohibited by prohibiting cyclic-equivalent and reverse cyclic-equivalent sequences for considering child items of the root item, namely the item S. Thus, the sequence for considering child items of the item S may be limited to A-G-N, since G-N-A and N-A-G are cyclic-equivalent sequences, and N-G-A, A-N-G and G-A-N are reverse cyclic-equivalent sequences. In this case, the items from the first non-root item to the first leaf item may be considered twice to determine a value associated with a depth-first search sequence of the tree. In the above example, the value associated with initial depth-first search sequence would be further based upon a similarity value between items A and N, a similarity value between items B and N, and a similarity value between items C and N. The value associated with the second depth-first search sequence would be further based upon a similarity value between items G and N, and a similarity value between items H and N. However, as explained above, the second depth-first search sequence would not have been considered.
[0079] An apparatus for performing embodiments of the herein-disclosed method may comprise one or more programmed computers. Each programmed computer may provide a particular functionality implemented using hardware and/or software and/or firmware.
[0080] Preferably, a programmed computer includes a computer memory encoded with executable instructions representing a computer program. A processor is responsive to the computer memory to perform a series of specifically identified operations dictated by the computer program. In this way, the computer program can cause the computer to act in a particular fashion.
[0081] Examples of the processor include, but are not limited to, a general purpose microprocessor, an application-specific integrated circuit (which may be either standard or custom), one or more discrete logic elements, a digital signal processor, one or more circuits, or any combination thereof. It is noted that the processor may be embodied by either a single processing unit or a plurality of processing units. For example, the processor may be embodied by either a single, central processing unit or a plurality of distributed processing units.
[0082] Examples of the computer memory include, but are not limited to, an electronic memory, a magnetic memory, an optical memory, and a magneto-optical memory. Examples of an electronic memory include, but are not limited to, a programmable electronic memory and a read-only, hard-wired electronic memory. Examples of a magnetic memory include, but are not limited to, a magnetic disk and a magnetic tape. The magnetic disk may be embodied by a magnetic floppy diskette or a magnetic hard drive, for example. Examples of an optical memory include, but are not limited to, an optical disk. The optical disk may be embodied by a compact disk or a DVD, for example. Regardless of its form, the computer memory may be either read-only, once-writable, or rewritable.
[0083] In general, the processor may be responsive to any data structures, computer programs, and signals encoded on a computer-readable medium to perform an embodiment of any of the herein-disclosed methods and examples. Examples of the computer-readable medium include, but are not limited to, computer-readable storage media and computer-readable communication media. Examples of computer-readable storage media are described with reference to the computer memory. Examples of computer-readable communication media include, but are not limited to, an optical medium, an electronic medium, and an electromagnetic medium.
[0084] The computer is coupled to a display to display a planar depiction described herein, computer-readable items represented by the planar depiction, and other visible information to an end user. Examples of the display include any of the herein-disclosed display devices.
[0085] The computer receives user-initiated selections and other user input from one or more user input devices. Examples of the one or more user input devices include any of the herein-disclosed input devices. The computer processes the user input and/or communicates at least one signal based upon the user input. The display and the one or more user input devices facilitate user interaction with the computer.
[0086] The computer includes a transceiver to communicate with a computer network. Examples of the transceiver include, but are not limited to, a modem, a network interface, and a wireless transceiver.
[0087] Embodiments of the herein-disclosed methods and examples can be performed using either a single computer or a plurality of computers. A plurality of computers may cooperate in a client-server fashion, for example.
[0088] It is noted that the present disclosure contemplates methods, articles, apparatus, and examples which include an act of providing a link to a computer site which performs an embodiment of any of the herein-disclosed methods and examples. The present disclosure also contemplates methods, articles, apparatus, and examples which include an act of providing a user-viewable advertisement for a computer site which assists in performing an embodiment of any of the herein-disclosed methods and examples. The user-viewable advertisement may be communicated to the end user from either an advertisement provider or the computer site. The present disclosure further contemplates methods, articles, apparatus, and examples which include an act of receiving a hit from an end user who has hyperlinked from a computer site which performs an embodiment of any of the herein-disclosed methods and examples. Each of the aforementioned computer sites may include an internet site, a Web site, or another site accessible via a computer network.
[0089] It will be apparent to those skilled in the art that the disclosed inventions may be modified in numerous ways and may assume many embodiments other than the preferred forms specifically set out and described herein. For example, the acts described with reference to FIGS. 1 to 3 may be executed in an order other than that indicated by FIGS. 1 to 3. Further, some of the acts may be performed in parallel.
[0090] Accordingly, it is intended by the appended claims to cover all modifications which fall within the true spirit and scope of the present invention.
Claims
What is claimed is:
1. A method comprising:
(a) providing a tree which relates a plurality of items, the items consisting of a plurality of internal items and a plurality of leaf items;
(b) providing a depth-first search sequence for considering items in the tree;
(c) providing a memory which is to indicate, for each level number from one to a height of the tree, a last-considered item associated with the level number;
(d) considering a current item in the depth-first search sequence of the tree;
(e) using a similarity value between the current item and the last-considered item associated with a level number of the current item to determine a value associated with the depth-first search sequence if at least one of the leaf items had been previously considered in the depth-first search sequence and the current item is one of the internal items;
(f) using each similarity value between the current item and each unique last-considered item associated with level numbers from the level number of the current item to the height of tree to determine the value associated with the depth-first search sequence if at least one of the leaf items had been previously considered in the depth-first search sequence and the current item is one of the leaf items;
(g) indicating the current item as the last considered item associated with the level number of the current item if the current item is one of the internal items;
(h) indicating the current item as the last considered item associated with each level number from the level number of the current item to the height of tree if the current item is one of the leaf items;
(i) repeating (d) to (h) for at least one subsequent item in the depth-first search sequence;
(j) modifying the depth-first search sequence for considering the items in the tree and repeating (d) to (i); and
(k) determining which depth-first search sequence has an optimum value associated therewith.
2. The method of claim 1 wherein (b) comprises, for each of the internal items having at least two child items in the tree, initializing a respective sequence for considering its respective child items in the depth-first search sequence of the tree, and wherein (j) comprises, for at least one of the internal items having at least two child items in the tree, modifying the respective sequence for considering its respective child items to modify the depth-first search sequence.
3. The method of claim 1 wherein (i) comprises repeating (d) to (f) for each subsequent item in the depth-first search sequence.
4. The method of claim 1 further comprising repeating (j) to determine a plurality of values associated with at least half of all possible depth-first search sequences of the tree.
5. The method of claim 1 wherein the value associated with the depth-first search sequence is based on a sum of a plurality of similarity values identified in (e) and (f) for the depth-first search sequence.
6. The method of claim 1 wherein the value associated with the depth-first search sequence is based on an average of a plurality of similarity values identified in (e) and (f) for the depth-first search sequence.
7. The method of claim 1 wherein the value associated with the depth-first search sequence is based on a product of a plurality of similarity values identified in (e) and (f) for the depth-first search sequence.
8. The method of claim 1 further comprising:
(l) outputting a signal to display a planar depiction of the tree in which the items are ordered according to the depth-first search sequence having the optimum value.
9. The method of claim 1 further comprising:
(l) outputting a signal to display a plurality of regions to visibly represent the items, wherein adjacent items in the tree are represented by radially-adjacent regions, and wherein pairs of items identified in (e) and (f) for the depth-first search sequence having the optimum value are represented by angularly-adjacent regions.
10. The method of claim 1 further comprising:
(l) outputting a signal to provide a plurality of user-selectable regions associated with the items, wherein adjacent items in the tree are represented by radially-adjacent user-selectable regions, and wherein pairs of items identified in (e) and (f) for the depth-first search sequence having the optimum value are represented by angularly-adjacent user-selectable regions.
11. The method of claim 1 wherein the items comprise a search expression and results of a search based on the search expression.
12. The method of claim 1 wherein the items comprise a plurality of computer-readable items.
13. The method of claim 1 further comprising:
(l) providing a browsing sequence for the items based on the depth-first search sequence having the optimum value associated therewith.
14. A computer-readable medium whose contents cause a computer system to:
(a) provide a tree which relates a plurality of items, the items consisting of a plurality of internal items and a plurality of leaf items;
(b) provide a depth-first search sequence for considering items in the tree;
(c) provide a plurality of variables in a memory which is to indicate, for each level number from one to a height of the tree, a last-considered item associated with the level number;
(d) consider a current item in the depth-first search sequence of the tree;
(e) use a similarity value between the current item and the last-considered item associated with a level number of the current item to determine a value associated with the depth-first search sequence if at least one of the leaf items had been previously considered in the depth-first search sequence and the current item is one of the internal items;
(f) use each similarity value between the current item and each unique last-considered item associated with level numbers from the level number of the current item to the height of tree to determine the value associated with the depth-first search sequence if at least one of the leaf items had been previously considered in the depth-first search sequence and the current item is one of the leaf items;
(g) indicate the current item as the last considered item associated with the level number of the current item if the current item is one of the internal items;
(h) indicate the current item as the last considered item associated with each level number from the level number of the current item to the height of tree if the current item is one of the leaf items;
(i) repeat (d) to (h) for at least one subsequent item in the depth-first search sequence;
(j) modify the depth-first search sequence for considering the items in the tree and repeat (d) to (i); and
(k) determine which depth-first search sequence has an optimum value associated therewith.
15. The computer-readable medium of claim 14 wherein (b) comprises, for each of the internal items having at least two child items in the tree, initializing a respective sequence for considering its respective child items in the depth-first search sequence of the tree, and wherein (j) comprises, for at least one of the internal items having at least two child items in the tree, modifying the respective sequence for considering its respective child items to modify the depth-first search sequence.
16. The computer-readable medium of claim 14 wherein (i) comprises repeating (d) to (f) for each subsequent item in the depth-first search sequence.
17. The computer-readable medium of claim 14 wherein the contents further cause the computer system to repeat (j) to determine a plurality of values associated with at least half of all possible depth-first search sequences of the tree.
18. The computer-readable medium of claim 14 wherein the value associated with the depth-first search sequence is based on a sum of a plurality of similarity values identified in (e) and (f) for the depth-first search sequence.
19. The computer-readable medium of claim 14 wherein the value associated with the depth-first search sequence is based on an average of a plurality of similarity values identified in (e) and (f) for the depth-first search sequence.
20. The computer-readable medium of claim 14 wherein the value associated with the depth-first search sequence is based on a product of a plurality of similarity values identified in (e) and (f) for the depth-first search sequence.
21. The computer-readable medium of claim 14 wherein the contents further cause the computer system to:
(l) output a signal to display a planar depiction of the tree in which the items are ordered according to the depth-first search sequence having the optimum value.
22. The computer-readable medium of claim 14 wherein the contents further cause the computer system to:
(l) output a signal to display a plurality of regions to visibly represent the items, wherein adjacent items in the tree are represented by radially-adjacent regions, and wherein pairs of items identified in (e) and (f) for the depth-first search sequence having the optimum value are represented by angularly-adjacent regions.
23. The computer-readable medium of claim 14 wherein the contents further cause the computer system to:
(l) output a signal to provide a plurality of user-selectable regions associated with the items, wherein adjacent items in the tree are represented by radially-adjacent user-selectable regions, and wherein pairs of items identified in (e) and (f) for the depth-first search sequence having the optimum value are represented by angularly-adjacent user-selectable regions.
24. The computer-readable medium of claim 14 wherein the items comprise a search expression and results of a search based on the search expression.
25. The computer-readable medium of claim 14 wherein the items comprise a plurality of computer-readable items.
26. The computer-readable medium of claim 14 wherein the contents further cause the computer system to:
(l) provide a browsing sequence for the items based on the depth-first search sequence having the optimum value associated therewith.
27. An apparatus comprising:
a computer system programmed to:
(a) provide a tree which relates a plurality of items, the items consisting of a plurality of internal items and a plurality of leaf items;
(b) provide a depth-first search sequence for considering items in the tree;
(c) provide a memory which is to indicate, for each level number from one to a height of the tree, a last-considered item associated with the level number;
(d) consider a current item in the depth-first search sequence of the tree;
(e) use a similarity value between the current item and the last-considered item associated with a level number of the current item to determine a value associated with the depth-first search sequence if at least one of the leaf items had been previously considered in the depth-first search sequence and the current item is one of the internal items;
(f) use each similarity value between the current item and each unique last-considered item associated with level numbers from the level number of the current item to the height of tree to determine the value associated with the depth-first search sequence if at least one of the leaf items had been previously considered in the depth-first search sequence and the current item is one of the leaf items;
(g) indicate the current item as the last considered item associated with the level number of the current item if the current item is one of the internal items;
(h) indicate the current item as the last considered item associated with each level number from the level number of the current item to the height of tree if the current item is one of the leaf items;
(i) repeat (d) to (h) for at least one subsequent item in the depth-first search sequence;
(j) modify the depth-first search sequence for considering the items in the tree and repeat (d) to (i); and
(k) determine which depth-first search sequence has an optimum value associated therewith.
28. The apparatus of claim 27 wherein (b) comprises, for each of the internal items having at least two child items in the tree, initializing a respective sequence for considering its respective child items in the depth-first search sequence of the tree, and wherein (j) comprises, for at least one of the internal items having at least two child items in the tree, modifying the respective sequence for considering its respective child items to modify the depth-first search sequence.
29. The apparatus of claim 27 wherein (i) comprises repeating (d) to (f) for each subsequent item in the depth-first search sequence.
30. The apparatus of claim 27 wherein the computer system is further programmed to repeat (j) to determine a plurality of values associated with at least half of all possible depth-first search sequences of the tree.
31. The apparatus of claim 27 wherein the value associated with the depth-first search sequence is based on a sum of a plurality of similarity values identified in (e) and (f) for the depth-first search sequence.
32. The apparatus of claim 27 wherein the value associated with the depth-first search sequence is based on an average of a plurality of similarity values identified in (e) and (f) for the depth-first search sequence.
33. The apparatus of claim 27 wherein the value associated with the depth-first search sequence is based on a product of a plurality of similarity values identified in (e) and (f) for the depth-first search sequence.
34. The apparatus of claim 27 wherein the computer system is further programmed to:
(l) output a signal to display a planar depiction of the tree in which the items are ordered according to the depth-first search sequence having the optimum value.
35. The apparatus of claim 27 wherein the computer system is further programmed to:
(l) output a signal to display a plurality of regions to visibly represent the items, wherein adjacent items in the tree are represented by radially-adjacent regions, and wherein pairs of items identified in (e) and (f) for the depth-first search sequence having the optimum value are represented by angularly-adjacent regions.
36. The apparatus of claim 27 wherein the computer system is further programmed to:
(l) output a signal to provide a plurality of user-selectable regions associated with the items, wherein adjacent items in the tree are represented by radially-adjacent user-selectable regions, and wherein pairs of items identified in (e) and (f) for the depth-first search sequence having the optimum value are represented by angularly-adjacent user-selectable regions.
37. The apparatus of claim 27 wherein the items comprise a search expression and results of a search based on the search expression.
38. The apparatus of claim 27 wherein the items comprise a plurality of computer-readable items.
39. The apparatus of claim 27 wherein the computer system is further programmed to:
(l) provide a browsing sequence for the items based on the depth-first search sequence having the optimum value associated therewith.
Patent Citations (25)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US5515488(A) | 1996-05-01 | Hoppe et al. | Examiner |
| US5596699(A) | 1997-01-01 | Driskell | Applicant |
| US5675733(A) | 1997-10-01 | Williams | Applicant |
| US5768423(A) | 1998-06-01 | Aref et al. | Examiner |
| US5798760(A) | 1998-08-01 | Vayda et al. | Applicant |
| US5805167(A) | 1998-09-01 | van Cruyningen | Applicant |
| US5926180(A) | 1999-07-01 | Shimamura | Applicant |
| US5943039(A) | 1999-08-01 | Anderson et al. | Applicant |
| US5987469(A) | 1999-11-01 | Lewis et al. | Applicant |
| US6014678(A) | 2000-01-01 | Inoue et al. | Examiner |
| US6104400(A) | 2000-08-01 | Halachmi et al. | Applicant |
| US6144962(A) | 2000-11-01 | Weinberg et al. | Applicant |
| US6145000(A) | 2000-11-01 | Stuckman et al. | Applicant |
| US6285367(B1) | 2001-09-01 | Abrams et al. | Applicant |
| US6286002(B1) | 2001-09-01 | Axaopoulos et al. | Examiner |
| US6297824(B1) | 2001-10-01 | Hearst et al. | Examiner |
| US6314434(B1) | 2001-11-01 | Shigemi et al. | Examiner |
| US6359635(B1) | 2002-03-01 | Perttunen | Applicant |
| US6369819(B1) | 2002-04-01 | Pitkow et al. | Applicant |
| US6377287(B1) | 2002-04-01 | Hao et al. | Applicant |
| US6385602(B1) | 2002-05-01 | Tso et al. | Examiner |
| US6426761(B1) | 2002-07-01 | Kanevsky et al. | Applicant |
| US6442544(B1) | 2002-08-01 | Kohli | Examiner |
| US6448987(B1) | 2002-09-01 | Easty et al. | Applicant |
| US2002/0122072(A1) | 2002-09-01 | Selker | Applicant |
Non-Patent Literature (14)
- Johnson et al., Applied Multivariate Statistical Analysis, 1982, pp. 532-573, Prentice-Hall, Englewood Cliffs.Applicant
- Tucker, Applied Combinatorics, Second Edition, 1984, pp. 28-31 and 80-131, John Wiley & Sons, New York.Applicant
- Luger et al., Artificial Intelligence and the Design of Expert Systems, 1989, pp. 88-99, Benjamin/Cummings Publishing, Redwood City.Applicant
- CRC Standard Mathematical Tables and Formulae, 29th Edition, 1991, pp. 106-107, CRC Press, Boca Raton.Applicant
- American Heritage Dictionary of the English Language, Third Edition, 1992, inside back cover, Houghton Mifflin, Boston.Applicant
- “The best chart type for my data,” help screen from Microsoft Excel for Windows 95, 1995.Applicant
- Using Visio Products, 1997, pp. 119-122, 185-202 and 207-232, Visio Corporation, Seattle.Applicant
- Hyman, Dynamic HTML for Dummies, 1997, pp. 63-79, IDG Books, Foster City.Applicant
- Lehto et al., Official Microsoft FrontPage 98 Book, 1997, pp. 32-52, Microsoft Press, Redmond.Applicant
- Tittel et al., HTML 4 for Dummies, 1998, pp. 12-13 and 283-293, IDG Books, Foster City.Applicant
- “Aurigin Announces General Availability of Version 6.0 of its Intellectual Property Asset Management System,” Web page from Aurigin Systems, Oct. 1998.Applicant
- “The Brain,” Web page from PC Magazine Online, Apr. 1998.Applicant
- “Roland Introduces HPD-15 HandSonic Hand Percussion Pad”, Feb. 3, 2000, Roland Corporation U.S., Los Angeles.Applicant
- “HPD-15 HandSonic”, printed from the Internet on Jan. 3, 2001, http://209.144.99.11/PRODUCTS/hardware/hpd15.htm.Applicant