Method, article and apparatus for organizing information

• US 6,563,521 B1
• Filed: 06/14/2000
• Issued: 05/13/2003
• Est. Priority Date: 06/14/2000
• Status: Expired due to Fees

• Current Assignee: Cary D. Perttunen
• Original Assignee: Cary D. Perttunen
• Inventors: Perttunen, Cary D.
• Primary Examiner(s): Cabeca, John
• Assistant Examiner(s): Thai, Cuong T.
• Application Number:
  US09/594,058
• Time in Patent Office: 1,063 Days
• Field of Search: 345/764, 345/853, 345/854, 345/855, 345/711, 345/712, 345/713, 345/802, 345/803, 345/804, 707/3, 707/5, 707/203
• US Class Current: 715/854
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99954 Version management

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.

Claims

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.