System of organizing catalog data for searching and retrieval

• US 6,381,607 B1
• Filed: 01/25/2000
• Issued: 04/30/2002
• Est. Priority Date: 06/19/1999
• Status: Expired due to Fees

• Current Assignee: Kent Ridge Digital Labs
• Original Assignee: Kent Ridge Digital Labs
• Inventors: Lui, Ho Chung, Lin, Tian, Wu, Horng Jyh Paul
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): ALAM, SHAHID AL
• Application Number:
  US09/463,378
• Time in Patent Office: 826 Days
• Field of Search: 707/1, 707/3, 707/5, 707/10, 707/100, 707/500, 707/102, 707/104.1, 707/200, 704/1, 704/9, 709/315, 709/201, 709/216, 709/220, 709/223
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method, an apparatus, and a computer program product for organizing and searching catalogs based on compacting a hierarchical structure (150, 500) into related arrays (210, 310, 410, 610; and 220, 320, 420, 620) are disclosed. This involves the steps of: storing indices (1-9) according to categories and subcategories in an array of indices (310), storing the keys (S54-S48) according to the categories and subcategories in an array (320) of keys, and linking each index of the array (310) of indices with one or more corresponding keys of the array (320) of keys corresponding to the category or subcategory associated with the index. The indices of a category or subcategory are stored contiguously in the array (310). Each index has one or more pointers recording the interrelationship of the indices. The keys of a given index are also stored contiguously with keys of any indices at the same corresponding category or subcategory level.

Claims

1. A method of organizing indices and keys of a tree-like data structure for electronic catalog searching and retrieval, said method including the steps of:

storing indices according to categories and subcategories in an array of indices, wherein indices of a category or subcategory are stored contiguously in said array, each index having one or more means for linking said index with a subordinate intermediate index or a leaf index, so as to record the interrelationship of said indices in said tree-like data structure;

storing said keys according to said categories and subcategories in an array of keys, wherein keys of a given index are stored contiguously with keys of any indices at the same corresponding category or subcategory level and keys of any subordinate subcategories within a category or subcategory are stored hierarchically in said array of keys;

linking each index of said array of indices with one or more corresponding keys of said array of keys corresponding to the category or subcategory associated with said index.

2. The method according to claim 1, further including the step of naming each subcategory according to one or more indices corresponding to said category or subcategory to provide a named path.

3. The method according to claim 2, further including the step of searching a category or subcategory of keys using a named path.

4. The method according to claim 1, wherein each index of said array of indices is linked with one or more corresponding keys of said array of keys corresponding to a category or subcategory associated with said index.

5. The method according to claim 1, further including the step of adding at least one alternative view path to said tree-like data structure, including at least one additional node.

6. The method according to claim 5, including the step of generating at least one equivalent named path for an existing named path of a category or subcategory.

7. The method according to claim 6, further including the step of adding one or more additional indices to said array of indices corresponding to said alternative view path.

8. The method according to claim 7, further including the step of adding one or more additional keys to said array of indices corresponding to said alternative view path.

9. An apparatus for organizing indices and keys of a tree-like data structure for electronic catalog searching and retrieval, said apparatus including:

means for storing indices according to categories and subcategories in an array of indices, wherein indices of a category or subcategory are stored contiguously in said array, each index having one or more means for linking said index with a subordinate intermediate index or a leaf index, so as to record the interrelationship of said indices in said tree-like data structure;

means for storing said keys according to said categories and subcategories in an array of keys, wherein keys of a given index are stored contiguously with keys of any indices at the same corresponding category or subcategory level and keys of any subordinate subcategories within a category or subcategory are stored hierarchically in said array of keys; and

means for linking each index of said array of indices with one or more corresponding keys of said array of keys corresponding to the category or subcategory associated with said index.

10. The apparatus according to claim 9, further including means for naming each subcategory according to one or more indices corresponding to said category or subcategory to provide a named path.

11. The apparatus according to claim 10, further including means for searching a category or subcategory of keys using a named path.

12. The apparatus according to claim 9, wherein each index of said array of indices is linked with one or more corresponding keys of said array of keys corresponding to a category or subcategory associated with said index.

13. The apparatus according to claim 9, further including means for adding at least one alternative view path to said tree-like data structure, including at least one additional node.

14. The apparatus according to claim 13, including means for generating at least one equivalent named path for an existing named path of a category or subcategory.

15. The apparatus according to claim 14, further including means for adding one or more additional indices to said array of indices corresponding to said alternative view path.

16. The apparatus according to claim 15, further including means for adding one or more additional keys to said array of indices corresponding to said alternative view path.

17. A computer program product having a computer readable medium having a computer program recorded therein for organizing indices and keys of a tree-like data structure for electronic catalog searching and retrieval, said computer program product including:

means for storing indices according to categories and subcategories in an array of indices, wherein indices of a category or subcategory are stored contiguously in said array, each index having one or more means for linking said index with a subordinate intermediate index or a leaf index, so as to record the interrelationship of said indices in said tree-like data structure;

means for storing said keys according to said categories and subcategories in an array of keys, wherein keys of a given index are stored contiguously with keys of any indices at the same corresponding category or subcategory level and keys of any subordinate subcategories within a category or subcategory are stored hierarchically in said array of keys; and

means for linking each index of said array of indices with one or more corresponding keys of said array of keys corresponding to the category or subcategory associated with said index.

18. The computer program product according to claim 17, further including means for naming each subcategory according to one or more indices corresponding to said category or subcategory to provide a named path.

19. The computer program product according to claim 18, further including means for searching a category or subcategory of keys using a named path.

20. The computer program product according to claim 17, wherein each index of said array of indices is linked with one or more corresponding keys of said array of keys corresponding to a category or subcategory associated with said index.

21. The computer program product according to claim 17, further including means for adding at least one alternative view path to said tree-like data structure, including at least one additional node.

22. The computer program product according to claim 21, including means for generating at least one equivalent named path for an existing named path of a category or subcategory.

23. The computer program product according to claim 22, further including means for adding one or more additional indices to said array of indices corresponding to said alternative view path.

24. The computer program product according to claim 21, further including means for adding one or more additional keys to said array of indices corresponding to said alternative view path.

25. A method of organizing indices and keys of a tree-like data structure for electronic catalog searching and retrieval, said method including the steps of:

storing indices according to sibling categories and subcategories in an array of indices, wherein indices of a sibling category or subcategory are stored contiguously in said array, each index having one or more means for linking said index with a subordinate intermediate index or a leaf index, so as to record the interrelationship of said indices in said tree-like data structure;

storing said keys according to said sibling categories and subcategories in an array of keys, wherein keys of a given index are stored contiguously with keys of any indices at the same corresponding sibling category or subcategory level;

linking each index of said array of indices with one or more corresponding keys of said array of keys corresponding to the sibling category or subcategory associated with said index.

26. The method according to claim 25, further including the step of naming each subcategory according to one or more indices corresponding to said sibling category or subcategory to provide a named path.

27. The method according to claim 26, further including the step of searching a sibling category or subcategory of keys using a named path.

28. The method according to claim 25, wherein each index of said array of indices is linked with one or more corresponding keys of said array of keys corresponding to a sibling category or subcategory associated with said index.

29. The method according to claim 25, further including the step of adding at least one alternative view path to said tree-like data structure, including at least one additional node.

30. The method according to claim 29, including the step of generating at least one equivalent named path for an existing named path of a sibling category or subcategory.

31. The method according to claim 30, further including the step of adding one or more additional indices to said array of indices corresponding to said alternative view path.

32. The method according to claim 31, further including the step of adding one or more additional keys to said array of indices corresponding to said alternative view path.

33. An apparatus for organizing indices and keys of a tree-like data structure for electronic catalog searching and retrieval, said apparatus including:

means for storing indices according to sibling categories and subcategories in an array of indices, wherein indices of a sibling category or subcategory are stored contiguously in said array, each index having one or more means for linking said index with a subordinate intermediate index or a leaf index, so as to record the interrelationship of said indices in said tree-like data structure;

means for storing said keys according to said sibling categories and subcategories in an array of keys, wherein keys of a given index are stored contiguously with keys of any indices at the same corresponding sibling category or subcategory level;

means for linking each index of said array of indices with one or more corresponding keys of said array of keys corresponding to the sibling category or subcategory associated with said index.

34. The apparatus according to claim 33, further including means for naming each subcategory according to one or more indices corresponding to said sibling category or subcategory to provide a named path.

35. The apparatus according to claim 34, further including means for searching a sibling category or subcategory of keys using a named path.

36. The apparatus according to claim 33, wherein each index of said array of indices is linked with one or more corresponding keys of said array of keys corresponding to a sibling category or subcategory associated with said index.

37. The apparatus according to claim 33, further including means for adding at least one alternative view path to said tree-like data structure, including at least one additional node.

38. The apparatus according to claim 37, including means for generating at least one equivalent named path for an existing named path of a sibling category or subcategory.

39. The apparatus according to claim 38, further including means for adding one or more additional indices to said array of indices corresponding to said alternative view path.

40. The apparatus according to claim 39, further including means for adding one or more additional keys to said array of indices corresponding to said alternative view path.

41. A computer program product having a computer readable medium having a computer program recorded therein for organizing indices and keys of a tree-like data structure for electronic catalog searching and retrieval, said computer program product including:

means for storing indices according to sibling categories and subcategories in an array of indices, wherein indices of a sibling category or subcategory are stored contiguously in said array, each index having one or more means for linking said index with a subordinate intermediate index or a leaf index, so as to record the interrelationship of said indices in said tree-like data structure;

means for storing said keys according to said sibling categories and subcategories in an array of keys, wherein keys of a given index are stored contiguously with keys of any indices at the same corresponding sibling category or subcategory level;

means for linking each index of said array of indices with one or more corresponding keys of said array of keys corresponding to the sibling category or subcategory associated with said index.

42. The computer program product according to claim 41, further including means for naming each subcategory according to one or more indices corresponding to said sibling category or subcategory to provide a named path.

43. The computer program product according to claim 42, further including means for searching a sibling category or subcategory of keys using a named path.

44. The computer program product according to claim 41, wherein each index of said array of indices is linked with one or more corresponding keys of said array of keys corresponding to a sibling category or subcategory associated with said index.

45. The computer program product according to claim 41, further including means for adding at least one alternative view path to said tree-like data structure, including at least one additional node.

46. The computer program product according to claim 45, including means for generating at least one equivalent named path for an existing named path of a sibling category or subcategory.

47. The computer program product according to claim 46, further including means for adding one or more additional indices to said array of indices corresponding to said alternative view path.

48. The apparatus according to claim 47, further including means for adding one or more additional keys to said array of indices corresponding to said alternative view path.