Hierarchical data processing

• US 7,155,440 B1
• Filed: 05/21/2003
• Issued: 12/26/2006
• Est. Priority Date: 04/29/2003
• Status: Expired due to Fees

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Kronmiller, Tom
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US10/443,556
• Time in Patent Office: 1,315 Days
• Field of Search: 707/102, 707/100, 707/101, 707/103.R, 707/104.1
• US Class Current: 707/797
• CPC Class Codes: G06F 30/39 Circuit design at the physical level physical level design for reconfigurable circuits G06F30/347
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• 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

Some embodiments of the invention provide a method for processing a hierarchical data structure that includes a parent data set and first and second child data sets of the parent data set. The parent and first and second child data sets includes several data tuples. From the second child data set, the method identifies a first data tuple that is not in the first child data set and that is relevant for the processing of the data tuples within the first child data set. The method then assigns the first data tuple to the first child data set and then processes the first child data set based on the data tuples included in the first child data set and assigned to the first child data set. In some embodiments, the method also identifies, from the parent data set, a second data tuple that is not in the first child data set and that is relevant for the processing of the data tuples within the first child data set. The method assigns the identified second data tuple to the first child data set, and processes the first child data set based on this data tuple.

Claims

1. A method of processing a hierarchical data structure that includes a parent data set and first and second child data sets of the parent data set, wherein each of the parent and first and second child data sets includes a plurality of data subsets that include data that relate to a design layout, the method comprising:

a) identifying a first data subset in the second child data set that is not in the first child data set and that is relevant for the processing of the data subsets within the first child data set;

b) assigning the first data subset to the first child data set;

c) processing the first child data set based on the data subsets included in the first child data set and assigned to the first child data set;

d) removing the first data subset from the second child data set; and

e) processing the second child data set by examining the remaining data subsets in the second child data set.

3. The method of claim 1, wherein the first data subset is not part of any other data subset in the second child data set.

4. The method of claim 1, wherein the first data subset is a portion of a second data subset that is in the second child data set, wherein identifying the first data subset comprises identifying the portion of the second data subset that is relevant for the processing of the first child data set.

9. The method of claim 1, wherein each child set is at least one data subset within the parent data set.

2. A method of processing a hierarchical data structure that includes a parent data set and first and second child data sets of the parent data set, wherein each of the parent and first and second child data sets includes a plurality of data subsets that include data that relate to a design layout, the method comprising:

a) identifying a first data subset in the second child data set that is not in the first child data set and that is relevant for the processing of the data subsets within the first child data set;

b) assessing the complexity of the first data set and the complexity of the second data set based on a set of indicia;

c) determining whether the first data set is less complex than the second data set;

d) if the first data set is less complex than the second data set assigning the first data subset to the first child data set;

e) processing the first child data set based on the data subsets included in the first child data set and assigned to the first child data set.

17. The method of claim 2, wherein said indicia comprise size of a given data set.

18. The method of claim 2, wherein said indicia comprise geometrical complexity of a given data set.

5. A method of analyzing a design layout by processing a hierarchical data structure that includes a parent data set and first and second child data sets of the parent data set, wherein each of the parent and first and second child data sets includes a plurality of data subsets that include data that relate to a design layout, and wherein the first child data set is a parent data set of a third child data set, the method comprising:

a) identifying a first data subset in the second child data set that is not in the first child data set and that is relevant for the processing of the data subsets within the first child data set;

b) assigning the first data subset to the first child data set;

c) processing the first child data set based on the data subsets included in the first child data set and assigned to the first child data set;

d) identifying a second data subset in the first child data set that is not in the third child data set and that is relevant for the processing of the data subsets within the third child data set;

e) assigning the identified second data subset to the third child data set.

6. The method of claim 5, wherein the second data subset is identified and assigned before processing the first child data set.

7. The method of claim 6, wherein the second data subset is at least a portion of the first data subset.

8. The method of claim 7, wherein the second data subset is the portion of the first data subset that is relevant for the processing of the data subsets within the third child data set.

10. A method of analyzing a design layout by processing a hierarchical data structure that includes a parent data set and first and second child data sets of the parent data set, wherein each of the parent and first and second child data sets includes a plurality of data subsets that include data that relate to a design layout, the method comprising:

a) identifying a first data subset in the parent data set that is not in the first child data set and that is relevant for the processing of the data subsets within the first child data set;

b) assigning the identified first data subset to the first child data set;

c) identifying a second data subset in the second child data set that is not in the first child data set and that is relevant for the processing of the data subsets within the first child data set;

d) assigning the second data subset to the first child data set;

e) processing the first child data set based on the data subsets included in the first child data set and assigned to the first child data set.

15. The method of claim 10 further comprising:

a) removing the first data subset from the parent data set; and

b) processing the parent data set by examining the remaining data subsets in the parent data set.

16. The method of claim 10 further comprising:

a) removing the second data subset from the second child set; and

b) processing the second child set by examining the remaining data subsets in the parent data set.

11. A computer readable medium that stores a computer program for processing a hierarchical data structure that includes a parent data set and first and second child data sets of the parent data set, wherein each of the parent and first and second child data sets includes a plurality of data subsets, the computer program comprising a set of instructions for:

a) identifying a first data subset in the second child data set that is not in the first child data set and that is relevant for the processing of the data subsets within the first child data set;

b) assigning the first data subset to the first child data set;

c) processing the first child data set based on the data subsets included in the first child data set and assigned to the first child data set;

d) removing the first data subset from the second child data set; and

e) processing the second child data set by examining the remaining data subsets in the second child data set.

12. The computer readable medium of claim 11, wherein the computer program further comprises sets of instructions for:

a) from the parent data set, identifying a second data subset that is not in the first child data set and that is relevant for the processing of the data subsets within the first child data set;

b) assigning the identified second data subset to the first child data set.

13. The computer readable medium of claim 12, wherein the computer program further comprises sets of instructions for:

a) removing the second data subset from the parent data set;

b) processing the parent data set by examining the remaining data subsets in the parent data set.

14. The computer readable medium of claim 13, wherein the computer program further comprises sets of instructions for:

a) from the parent data set, identifying a third data subset that is not in the first child data set and that is relevant for the processing of the data subsets within the first child data set;

b) assigning the identified third data subset to the first child data set;

c) wherein the set of instructions for examining the remaining data subsets in the parent data set comprises a set of instructions for examining the third data subset.