Data storage and retrieval system with optimized categorization of information items based on category selection

• US 7,555,486 B2
• Filed: 08/17/2005
• Issued: 06/30/2009
• Est. Priority Date: 01/20/2005
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Pi Corp. (Dell Technologies Inc.)
• Inventors: Venguerov, Mark
• Primary Examiner(s): Pham; Khanh B
• Assistant Examiner(s): Yen; Syling
• Application Number:
  US11/205,630
• Publication Number:
  US 20060161570A1
• Time in Patent Office: 1,413 Days
• Field of Search: 707/3, 707/100, 707/10, 707/102, 707/103.R, 707/104.1
• US Class Current: 1/1
• CPC Class Codes: G06Q 10/00 Administration; Management
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A data storage and retrieval system with optimized categorization of information items using intelligent category selection, based on the information items that are to be checked for category membership. The set of categories for which an information item may be a candidate member is determined, and only that set of categories is checked for membership of the information item during the categorization process. The determination of which categories an information item can be a candidate member of is based on the properties defined for that information item, which are compared to the properties checked for category membership of specific categories. A category index tree may be built and maintained to support efficient determination of which categories a given information item may be a candidate member of. The efficiency of categorization provided by the disclosed techniques enables the disclosed system to maintain category definitions indefinitely with minimal performance impact.

Claims

1. A method of categorizing information items in a computer implemented data storage and retrieval system, wherein each of said information items is associated with at least one property, comprising:

applying a global property ordering to each list of properties required for membership in each corresponding one of a currently defined set of categories;

generating, a tree structure providing an index, wherein said tree structure indexes said currently defined set of categories based on said properties required for membership in corresponding ones of said categories, wherein said tree structure includes a plurality of nodes, each node being associated with an individual property and a list of categories, wherein said nodes are ordered within said tree structure based on said global property ordering, and wherein each category in said category list for each node is a category that requires the property associated with the node as well as the properties associated with all ancestor nodes of the node in the up direction for membership in that category;

receiving an input one of said information items;

selecting a subset of said defined set of categories to be checked by ordering all properties associated with said input information item into an ordered property list based on said global property ordering and traversing said tree structure according to said ordered property list, wherein said traversing is limited to subtrees of said tree structure having nodes associated with properties in said ordered property list, wherein subtrees of said tree structure having nodes not associated with properties in said ordered property list are not traversed; and

categorizing said information item based on said selected subset of categories by checking the properties in said ordered list of properties to determine whether conditions for membership in each of said selected subset of categories are met, wherein conditions for membership in those categories not within said selected subset of categories are not checked.

2. The method of claim 1, wherein said selecting is performed responsive to receipt of said information item.

3. The method of claim 1, wherein said selecting is performed responsive to deletion of said information item.

4. The method of claim 1, wherein said selecting is performed responsive to modification of said information item.

5. A computer system for categorizing information items in a data storage and retrieval system, wherein each of said information items is associated with at least one property, said system including a computer readable memory having program code stored thereon, said program code comprising:

program code for applying a global property ordering to each list of properties required for membership in each corresponding one of a currently defined set of categories;

program code for generating a tree structure providing an index, wherein said tree structure indexes said currently defined set of categories based on said properties required for membership in corresponding ones of said categories, wherein said tree structure includes generating a plurality of nodes, each node being associated with an individual property and a list of categories, wherein said nodes are ordered within said tree structure based on said global property ordering, and wherein each category in said category list for each node is a category that requires the property associated with the node as well as the properties associated with all ancestor nodes of the node in the up direction for membership in that category;

program code for receiving an input one of said information items;

program code for selecting a subset of said defined set of categories to be checked by ordering all properties associated with said input information item into an ordered property list based on said global property ordering, and traversing said tree structure according to said ordered property list, wherein said traversing is limited to subtrees of said tree structure having nodes associated with properties in said ordered property list, wherein subtrees of said tree structure having nodes not associated with properties in said ordered property list are not traversed; and

program code for categorizing said information item based on said selected subset of categories by checking the properties in said ordered list of properties to determine whether conditions for membership in each of said selected subset of categories are met, wherein conditions for membership in those categories not within said selected subset of categories are not checked.

6. The system of claim 5, wherein said program code for selecting is responsive to receipt of said information item.

7. The system of claim 5, wherein said program code for selecting is responsive to deletion of said information item.

8. The system of claim 5, wherein said program code for selecting is responsive to modification of said information item.

9. A computer program product including a computer readable memory, said computer readable memory having a computer program for categorizing information items in a data storage and retrieval system stored thereon, wherein each of said information items is associated at least one property, said computer program comprising:

program code for applying a global property ordering to each list of properties required for membership in each corresponding one of a currently defined set of categories;

program code for generating a tree structure providing an index, wherein said tree structure indexes said currently defined set of categories based on said properties required for membership in corresponding ones of said categories, wherein said tree structure includes generating a plurality of nodes, each node being associated with an individual property and a list of categories, and wherein said nodes are ordered within said tree structure based on said global property ordering, and wherein each category in said category list for each node is a category that requires the property associated with the node as well as the properties associated with all ancestor nodes of the node in the up direction for membership in that category;

program code for receiving an input one of said information items;

program code for selecting a subset of said defined set of categories to be checked by ordering all properties associated with said input information item into an ordered property list based on said global property ordering, and traversing said tree structure according to said ordered property list, wherein said traversing is limited to subtrees of said tree structure having nodes associated with properties in said ordered property list, wherein subtrees of said tree structure having nodes not associated with properties in said ordered property list are not traversed; and

program code for categorizing said information item based on said selected subset of categories by checking the properties in said ordered list of properties to determine whether conditions for membership in each of said selected subset of categories are met, wherein conditions for membership in those categories not within said selected subset of categories are not checked.

10. A computer system including at least one processor and a computer readable storage medium, wherein said computer readable medium has stored thereon program code for categorizing information items in a data storage and retrieval system stored on said computer readable medium, wherein each of said information items is associated at least one property, wherein said program code for categorizing information items comprises:

means for applying a global property ordering to each list of properties required for membership in each corresponding one of a currently defined set of categories;

means for generating a tree structure providing an index, wherein said tree structure indexes said currently defined set of categories based on said properties required for membership in corresponding ones of said categories, wherein said tree structure includes generating a plurality of nodes, each node being associated with an individual property and a list of categories, wherein said nodes are ordered within said tree structure based on said global property ordering, and wherein each category in said category list for each node is a category that requires the property associated with the node as well as the properties associated with all ancestor nodes of the node in the up direction for membership in that category;

means for receiving an input one of said information items;

means for selecting a subset of said defined set of categories to be checked by ordering all properties associated with said input information item into an ordered property list based on said global property ordering, and traversing said tree structure according to said ordered property list, wherein said traversing is limited to subtrees of said tree structure having nodes associated with properties in said ordered property list, wherein subtrees of said tree structure having nodes not associated with properties in said ordered property list are not traversed; and

means for categorizing said information item based on said selected subset of categories by checking the properties in said ordered list of properties to determine whether conditions for membership in each of said selected subset of categories are met, wherein conditions for membership in those categories not within said selected subset of categories are not checked.