System and method for processing a hierarchical data tree

• US 7,272,607 B2
• Filed: 10/31/2003
• Issued: 09/18/2007
• Est. Priority Date: 11/27/2002
• Status: Expired due to Fees

• Current Assignee: Zyvex Labs, Llc
• Original Assignee: Zyvex Labs, Llc
• Inventors: Parker, Eric, Udeshi, Tushar
• Primary Examiner(s): Vo; Tim
• Assistant Examiner(s): OMOSEWO, OLUBUSOLA
• Application Number:
  US10/698,178
• Publication Number:
  US 20040111406A1
• Time in Patent Office: 1,418 Days
• Field of Search: 707200-205, 705/26, 702/182
• US Class Current: 707/769
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/959 Network
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method for performing an operation on a hierarchical data tree comprising retrieving data from an anchor node in the tree and a plurality of neighboring nodes each potentially affected by the operation. A cache is queried for a key representing the anchor node and the plurality of neighboring nodes based on the retrieved data. If the query finds a match, the retrieved data is replaced with cached data. If the query does not find a match, the operation is performed on the retrieved data to generate post-operation data, the retrieved data is replaced with the post-operation data and the post-operation data is stored in the cache based on the key.

Claims

1. A method for performing an operation on a hierarchical data tree, comprising:

visiting an anchor node in the tree;

retrieving data from the anchor node and a plurality of neighboring nodes each potentially affected by the operation;

querying a cache for a key representing the anchor node and the plurality of neighboring nodes in a pre-operation condition based on the retrieved data, wherein the cache stores pre-operation/post-operation data pairs;

if the query finds a match, replacing the pre-operation retrieved data with cached post-operation data; and

if the query does not find a match, performing the operation on the pre-operation retrieved data to generate post-operation data, replacing the pre-operation retrieved data with the post-operation data and storing the post-operation data in the cache with the associated pre-operation retrieved data.

2. The method of claim 1 wherein the retrieving data from the anchor node and a plurality of neighboring nodes each potentially affected by the operation further comprises retrieving data from at least one neighboring node affecting the operation.

3. The method of claim 1 wherein the pre-operation retrieved data is replaced with cached post-operation data for a subset of the nodes for which pre-operation data was retrieved.

4. The method of claim 3 wherein the operation assigns the anchor node to one of a plurality of equivalence classes and maintains a count of the number of nodes in each of the plurality of equivalence classes.

5. The method of claim 1 wherein the hierarchical data tree represents a physical structure and the operation comprises modifying the retrieved data to reflect the addition of material to the physical structure.

6. The method of claim 1 wherein the hierarchical data tree represents a physical structure and the operation comprises modifying the retrieved data to reflect the removal of material from the physical structure.

7. The method of claim 1 wherein the operation modifies a parameter of at least one of the anchor node and the plurality of neighboring nodes.

8. The method of claim 7 wherein the parameter is a temperature of the at least one of the anchor node and the plurality of neighboring nodes.

9. The method of claim 7 wherein the parameter is a pressure of the at least one of the anchor node and the plurality of neighboring nodes.

10. The method of claim 7 wherein the parameter is a stress of the at least one of the anchor node and the plurality of neighboring nodes.

11. The method of claim 7 wherein the parameter is an equivalence class.

12. The method of claim 7 wherein the parameter is a composition of the at least one of the anchor node and the plurality of neighboring nodes.

13. The method of claim 12 wherein the composition comprises a percentage of occupation of the at least one of the anchor node and the plurality of neighboring nodes by a predetermined material.

14. The method of claim 12 wherein the composition comprises a percentage of occupation of the at least one of the anchor node and the plurality of neighboring nodes by each of a plurality of predetermined materials.

15. The method of claim 1 wherein the tree is an X-dimensional tree and the plurality of neighboring nodes includes at least X neighboring nodes.

16. The method of claim 1 wherein the tree is an X-dimensional tree and the plurality of neighboring nodes consists of X neighboring nodes.

17. The method of claim 1 wherein the tree has a directed acyclic graph structure.

18. The method of claim 1 wherein the tree is an octree.

19. The method of claim 1 wherein the tree is a quadtree.

20. The method of claim 1 wherein the tree is a shared tree.

21. The method of claim 1 further comprising expunging non-matched data from the cache when the cache attains a predetermined occupancy.

22. The method of claim 1 wherein replacing the retrieved data with cached data comprises replacing the retrieved data with pointers to previously examined nodes represented by the cached data.

23. The method of claim 1 wherein the data retrieval, cache querying and data replacement based on results of the cache querying is repeated with each unique node in the tree treated as the anchor node.

24. The method of claim 1 wherein the tree represents a microelectronic device.

25. The method of claim 24 wherein the microelectronic device is a MEMS device.

26. The method of claim 24 wherein the microelectronic device is a NEMS device.

55. The method of claim 1 wherein at least one of the plurality of retrieved neighboring nodes each potentially affected by the operation is separated from the anchor node by at least one node.

27. A processing system for performing an operation on a hierarchical data tree, comprising:

means for retrieving data from an anchor node in the tree and a plurality of neighboring nodes affected by the operation;

means for querying a cache for a key representative of the anchor node and the plurality of neighboring nodes based on the retrieved data;

means for replacing the retrieved data with cached data if the query finds a match; and

means for performing the operation on the retrieved data to generate post-operation data, replacing the retrieved data with the post-operation data and storing the post-operation data in the cache based on the key if the query does not find a match.

28. The system of claim 27 wherein the means for performing the operation on the retrieved data includes means for assigning the anchor node to one of a plurality of equivalence classes.

29. The system of claim 28 wherein the means for performing the operation further includes means for maintaining a count of the number of nodes in each of the plurality of equivalence classes.

30. The system of claim 27 wherein the means for performing the operation includes means for modifying the retrieved data to reflect the addition of material to physical structure represented by the tree.

31. The system of claim 27 wherein the means for performing the operation includes means for modifying the retrieved data to reflect the removal of material from physical structure represented by the tree.

32. The system of claim 27 wherein the means for performing the operation includes means for modifying a parameter of at least one of the anchor node and the plurality of neighboring nodes.

33. The system of claim 27 further comprising means for expunging non-matched data from the cache when the cache attains a predetermined occupancy.

34. The system of claim 27 wherein the means for replacing the retrieved data with cached data replaces the retrieved data with pointers to previously examined nodes represented by the cached data.

35. The system of claim 27 further comprising means for repeating the data retrieval, cache querying and data replacement based on results of the cache querying with each unique node in the tree treated as the anchor node.

36. The system of claim 27 wherein the tree represents a microelectronic device.

37. The system of claim 36 wherein the microelectronic device is a MEMS device.

38. The system of claim 36 wherein the microelectronic device is a NEMS device.

39. A program product, comprising:

a computer-readable storage medium;

means recorded on the medium for retrieving data from an anchor node in a hierarchical data tree and a plurality of neighboring nodes affected by an operation to be performed on the tree;

means recorded on the medium for querying a cache for a key representative of the anchor node and the plurality of neighboring nodes based on the retrieved data;

means recorded on the medium for replacing the retrieved data with cached data if the query finds a match; and

means recorded on the medium for performing the operation on the retrieved data to generate post-operation data, replacing the retrieved data with the post-operation data and storing the post-operation data in the cache based on the key if the query does not find a match.

40. The program product of claim 39 wherein the means for performing the operation on the retrieved data includes means for assigning the anchor node to one of a plurality of equivalence classes.

41. The program product of claim 40 wherein the means for performing the operation further includes means for maintaining a count of the number of nodes in each of the plurality of equivalence classes.

42. The program product of claim 39 wherein the means for performing the operation includes means for modifying the retrieved data to reflect the addition of material to physical structure represented by the tree.

43. The program product of claim 39 wherein the means for performing the operation includes means for modifying the retrieved data to reflect the removal of material from physical structure represented by the tree.

44. The program product of claim 39 wherein the means for performing the operation includes means for modifying a parameter of at least one of the anchor node and the plurality of neighboring nodes.

45. The program product of claim 39 further comprising means for expunging non-matched data from the cache when the cache attains a predetermined occupancy.

46. The program product of claim 39 wherein the means for replacing the retrieved data with cached data replaces the retrieved data with pointers to previously examined nodes represented by the cached data.

47. The program product of claim 39 further comprising means for repeating the data retrieval, cache querying and data replacement based on results of the cache querying with each unique node in the tree treated as the anchor node.

48. The program product of claim 39 wherein the tree represents a microelectronic device.

49. The program product of claim 48 wherein the microelectronic device is a MEMS device.

50. The program product of claim 48 wherein the microelectronic device is a NEMS device.

51. The program product of claim 39 wherein the storage medium is a magnetic recording medium.

52. The program product of claim 39 wherein the storage medium is an optical recording medium.

53. The program product of claim 39 wherein the storage medium is a network distribution medium.

54. A method for performing an operation on a hierarchical data tree, comprising:

retrieving data from an anchor node in the tree and a plurality of neighboring nodes each potentially affected by the operation;

querying a cache for a key representing the anchor node and the plurality of neighboring nodes based on the retrieved data;

if the query finds a match, replacing the retrieved data with cached data; and

if the query does not find a match, performing the operation on the retrieved data to generate post-operation data, replacing the retrieved data with the post-operation data and storing the post-operation data in the cache based on the key.