SYSTEM, METHOD AND COMPUTER PROGRAM PRODUCT FOR EFFICIENT CACHING OF HIERARCHICAL ITEMS

• US 20140207825A1
• Filed: 03/24/2014
• Published: 07/24/2014
• Est. Priority Date: 03/30/2011
• Status: Active Grant

• Current Assignee: Ip Ot Sub Ulc
• Original Assignee: Open TEXT SA (Open Text Corporation)
• Inventors: Wongkar, Adison Hana, Gupta, Shaival
• Granted Patent: US 9,183,241 B2
• Time in Patent Office: Days
• US Class Current: 707/797
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: H04L 63/0281 Proxies
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 7/0008 Synchronisation information channels, e.g. clock distribution lines

Abstract

Embodiments disclosed herein provide a “lazy” approach in caching a hierarchical navigation tree with one or more associated permission trees. In one embodiment, only a portion of a cached permission tree is updated. One embodiment of a method may comprise determining whether a dirty node exists by comparing tree timestamps of the permission tree and the master tree. If the tree timestamp of the master tree is temporally more recent than the tree timestamp of the permission tree, the permission tree has a dirty node and the method may operate to check node timestamps of the master and permission trees. This process may be repeated until the dirty node is found, at which time a portion of the permission tree associated with the dirty node may be reconstructed, rather than the entire permission tree itself, thereby eliminating or significantly reducing access time to the cached permission tree.

Claims

1. A method of caching hierarchical items in a network environment, the method comprising:

in a hierarchical navigation tree having nodes representing hierarchical items of a web site, each node in the hierarchical navigation tree having a tree timestamp and a node timestamp, a server computer where the hierarchical navigation tree is cached performing;

in response to a change to the hierarchical navigation tree, identifying dirty nodes in the hierarchical navigation tree that are affected by the change, wherein the tree timestamp and the node timestamp are used in the identifying; and

rebuilding a portion of the hierarchical navigation tree containing the dirty nodes without alternating all the nodes in the hierarchical navigation tree.

2. The method according to claim 1, further comprising:

associating the hierarchical navigation tree with one or more permission trees, each permission tree of the one or more permission trees having a set of nodes representing access restriction of a group of users to the web site.

3. The method according to claim 2, further comprising:

caching the hierarchical navigation tree and the one or more permission trees in a hierarchical cache on the server computer.

4. The method according to claim 1, further comprising:

tracking a temporal point in time when each node in the hierarchical navigation tree was last updated using the node timestamp.

5. The method according to claim 1, wherein the change represents adding a node, deleting a node, reordering a node, re-permissioning a node, de-permissioning a node, re-parenting a node, or editing a node.

6. The method according to claim 1, further comprising:

in response to a request from a user, updating a portion of a permission tree associated with the user, the portion of the permission tree containing dirty nodes in comparison to corresponding nodes in the hierarchical navigation tree.

7. The method according to claim 6, wherein the dirty nodes in the portion of the permission tree are determined by:

comparing a root tree timestamp of the hierarchical navigation tree with a root tree timestamp of the permission tree;

if the root tree time stamp of the hierarchical navigation tree is more recent than the root tree timestamp of the permission tree, comparing node time stamps of each node in the permission tree with node time stamps of corresponding nodes in the hierarchical navigation tree; and

if a node time stamp for a node in the hierarchical navigation tree is not more recent than a node time stamp for a corresponding node in the permission tree, comparing a tree timestamp for the node in the hierarchical navigation tree with a tree timestamp for the corresponding node in the permission tree.

8. A computer program product comprising at least one non-transitory computer readable medium storing instructions translatable by a server computer where a hierarchical navigation tree is cached, the hierarchical navigation tree having nodes representing hierarchical items of a web site, each node in the hierarchical navigation tree having a tree timestamp and a node timestamp, the instructions when translated by the server computer cause the server computer to perform:

in response to a change to the hierarchical navigation tree, identifying dirty nodes in the hierarchical navigation tree that are affected by the change, wherein the tree timestamp and the node timestamp are used in the identifying; and

rebuilding a portion of the hierarchical navigation tree containing the dirty nodes without alternating all the nodes in the hierarchical navigation tree.

9. The computer program product of claim 8, wherein the instructions when translated by the server computer further cause the server computer to perform:

associating the hierarchical navigation tree with one or more permission trees, each permission tree of the one or more permission trees having a set of nodes representing access restriction of a group of users to the web site.

10. The computer program product of claim 8, wherein the instructions when translated by the server computer further cause the server computer to perform:

tracking a temporal point in time when each node in the hierarchical navigation tree was last updated using the node timestamp.

11. The computer program product of claim 8, wherein the change represents adding a node, deleting a node, reordering a node, re-permissioning a node, de-permissioning a node, re-parenting a node, or editing a node.

12. The computer program product of claim 8, wherein the instructions when translated by the server computer further cause the server computer to perform:

in response to a request from a user, updating a portion of a permission tree associated with the user, the portion of the permission tree containing dirty nodes in comparison to corresponding nodes in the hierarchical navigation tree.

13. The computer program product of claim 12, wherein the dirty nodes in the portion of the permission tree are determined by:

comparing a root tree timestamp of the hierarchical navigation tree with a root tree timestamp of the permission tree;

if the root tree time stamp of the hierarchical navigation tree is more recent than the root tree timestamp of the permission tree, comparing node time stamps of each node in the permission tree with node time stamps of corresponding nodes in the hierarchical navigation tree; and

if a node time stamp for a node in the hierarchical navigation tree is not more recent than a node time stamp for a corresponding node in the permission tree, comparing a tree timestamp for the node in the hierarchical navigation tree with a tree timestamp for the corresponding node in the permission tree.

14. A system, comprising:

a server computer storing a hierarchical navigation tree, the hierarchical navigation tree having nodes representing hierarchical items of a web site, each node in the hierarchical navigation tree having a tree timestamp and a node timestamp, the server computer configured to perform;

in response to a change to the hierarchical navigation tree, identifying dirty nodes in the hierarchical navigation tree that are affected by the change, wherein the tree timestamp and the node timestamp are used in the identifying; and

rebuilding a portion of the hierarchical navigation tree containing the dirty nodes without alternating all the nodes in the hierarchical navigation tree.

15. The system of claim 14, wherein the server computer is further configured to perform:

associating the hierarchical navigation tree with one or more permission trees, each permission tree of the one or more permission trees having a set of nodes representing access restriction of a group of users to the web site.

16. The system of claim 15, wherein the hierarchical navigation tree and the one or more permission trees are cached in a hierarchical cache on the server computer.

17. The system of claim 14, wherein the server computer is further configured to perform:

tracking a temporal point in time when each node in the hierarchical navigation tree was last updated using the node timestamp.

18. The system of claim 14, wherein the change represents adding a node, deleting a node, reordering a node, re-permissioning a node, de-permissioning a node, re-parenting a node, or editing a node.

19. The system of claim 14, wherein the server computer is further configured to perform:

in response to a request from a user, updating a portion of a permission tree associated with the user, the portion of the permission tree containing dirty nodes in comparison to corresponding nodes in the hierarchical navigation tree.

20. The system of claim 19, wherein the dirty nodes in the portion of the permission tree are determined by the server computer by:

comparing a root tree timestamp of the hierarchical navigation tree with a root tree timestamp of the permission tree;

if the root tree time stamp of the hierarchical navigation tree is more recent than the root tree timestamp of the permission tree, comparing node time stamps of each node in the permission tree with node time stamps of corresponding nodes in the hierarchical navigation tree; and

if a node time stamp for a node in the hierarchical navigation tree is not more recent than a node time stamp for a corresponding node in the permission tree, comparing a tree timestamp for the node in the hierarchical navigation tree with a tree timestamp for the corresponding node in the permission tree.