Nested categorization using factorization
View Patent ↗A system for information item categorization in which each non-leaf node in a hierarchical organization of nodes represents a category, and each leaf node represents an information item. A number P is associated with each node. For non-leaf nodes, the associated number P is selected from a subset of relatively prime elements chosen from an appropriate Unique Factorization Domain (UFD), such as a set of relatively prime numbers which are a subset of the familiar set of integers. For leaf nodes, P is set to 1. A number M is also associated with each node. For each root node, M is set to the value of P for that node. For each non-root node, M is set to the product of the M's of all parent nodes of the node and the P of that node.
1. A method for categorizing information items using a hierarchical structure of nodes, wherein each information item is represented by a leaf node and each category is represented by a non-leaf node in said hierarchical structure, comprising:
associating a first number with each node, wherein for each non-leaf node said first number is uniquely selected from a subset of relatively prime elements within a unique factorization domain, wherein said subset of relatively prime elements includes at least one nonprime element, wherein elements of said subset of relatively prime elements taken pairwise are all relatively prime to each other, and wherein for each leaf node said first number is equal to one; and
associating a second number with each node, wherein for each root node said second number is equal to said first number, wherein for each non-root node said second number is equal to a product of said second numbers associated with each direct parent node of said non-root node and said first number of said non-root node, and wherein at least one non-root node has multiple direct parents, said second number for said at least one non-root node being equal to a product determined from multiplying said second numbers belonging to each of said multiple direct parents and said first number of said at least one non-root node.
2. The method of claim 1 , further comprising:
processing a query to find information items located under a given node by identifying those leaf nodes having an associated second number completely divisible by a first number associated with said given node.
3. The method of claim 1 , further comprising:
processing a query to find information items located under a given node by identifying those leaf nodes having an associated second number completely divisible by a second number associated with the given node.
4. The method of claim 1 , further comprising:
processing a query to find information items located under a plurality of nodes by identifying those leaf nodes having an associated second number completely divisible by a product of said first numbers associated with respective ones of said plurality of nodes.
5. The method of claim 1 , further comprising:
processing a query to find information items located under a plurality of nodes by identifying those leaf nodes having an associated second number completely divisible by a product of said second numbers associated with respective ones of said plurality of nodes.
6. The method of claim 1 , further comprising:
processing a query to find information items that are direct children of a plurality of nodes by identifying those leaf nodes having an associated second number equal to a product of said second numbers associated with respective ones of said plurality of nodes.
7. The method of claim 1 , wherein said unique factorization domain comprises the set of non-negative integers and said first numbers are chosen from the set of probable prime numbers determined as numbers satisfying a predetermined primality test.
8. The method of claim 7 , wherein said predetermined primality test comprises Fermat's little theorem.
9. The method of claim 1 , wherein said hierarchical structure of nodes represents a categorization of electronic mail messages within a mailbox structure of an electronic mail application program, and wherein at least one of said electronic mail messages is in more than one category.
10. The method of claim 1 , wherein said hierarchical structure of nodes represents a nested set of user groups, and wherein at least one user belongs to more than one of said user groups.
11. The method of claim 1 , wherein said unique factorization domain comprises the set of Gaussian integers.
12. The method of claim 1 , wherein said at least one non-prime element is not a power of two.
13. A system including at least one processor and a non-signal computer readable medium having program code stored thereon for, when executed by said processor, categorizing information items using a hierarchical structure of nodes, wherein each information item is represented by a leaf node and each category is represented by a non-leaf node in said hierarchical structure, said program code comprising:
program code for associating a first number with each node, wherein for each non-leaf node said first number is uniquely selected from a subset of relatively prime elements within a unique factorization domain, wherein said subset of relatively prime elements includes at least one non-prime element, wherein elements of said subset of relatively prime elements taken pairwise are all relatively prime to each other, and wherein for each leaf node said first number is equal to one; and
program code for associating a second number with each node, wherein for each root node said second number is equal to said first number, wherein for each non-root node said second number is equal to a product of said second numbers associated with each direct parent node of said non-root node and said first number of said non-root node, and wherein at least one non-root node has multiple direct parents, said second number for said at least one non-root node being equal to a product determined from multiplying said second numbers belonging to each of said multiple direct parents and said first number of said at least one non-root node.
14. A computer program product, comprising:
a non-transitory computer readable medium having program code stored thereon for categorizing information items using a hierarchical structure of nodes, wherein each information item is represented by a leaf node and each category is represented by a non-leaf node in said hierarchical structure, said program code comprising:
program code for associating a first number with each node, wherein for each non-leaf node said first number is uniquely selected from a subset of relatively prime elements within a unique factorization domain, wherein said subset of relatively prime elements includes at least one non-prime element, wherein elements of said subset of relatively prime elements taken pairwise are all relatively prime to each other, and wherein for each leaf node said first number is equal to one; and
program code for associating a second number with each node, wherein for each root node said second number is equal to said first number, wherein for each non-root node said second number is equal to a product of said second numbers associated with each direct parent node of said non-root node and said first number of said non-root node, and wherein at least one non-root node has multiple direct parents, said second number for said at least one non-root node being equal to a product determined from multiplying said second numbers belonging to each of said multiple direct parents and said first, number of said at least one non-root node.