Method and apparatus for representing multidimensional data

• US 6,959,304 B1
• Filed: 11/05/2002
• Issued: 10/25/2005
• Est. Priority Date: 03/15/2000
• Status: Expired due to Term

• Current Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Original Assignee: Cadence Design Systems Incorporated (Cadence Group)
• Inventors: Teig, Steven, Siegel, Andrew F., Kronmiller, Tom
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US10/288,009
• Time in Patent Office: 1,085 Days
• Field of Search: 707 2- 10, 707100-1041, 345/645
• US Class Current: 707/713
• CPC Class Codes: G06F 30/398 Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] optical proximity correction [OPC] design processes G03F1/36
• CPC Class Codes: Y10S 707/921 Spatial
• CPC Class Codes: Y10S 707/957 Multidimensional
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

The invention is directed towards method and apparatus for representing multidimensional data. Some embodiments of the invention provide a two-layered data structure to store multidimensional data tuples that are defined in a multidimensional data space. These embodiments initially divide the multidimensional data space into a number of data regions, and create a data structure to represent this division. For each data region, these embodiments then create a hierarchical data structure to store the data tuples within each region. In some of these embodiments, the multidimensional data tuples are spatial data tuples that represent spatial or geometric objects, such as points, lines, polygons, regions, surfaces, volumes, etc. For instance, some embodiments use the two-layered data structure of the invention to store data relating to geometric objects (such as rectangles) that represent interconnect lines of an IC in an IC design layout.

Claims

1. A computer-implemented method of representing multidimensional data tuples, the method comprising:

a) defining a plurality of data regions in a multidimensional data space;

b) creating a plurality of hierarchical data structures for a plurality of said data regions, wherein each hierarchical data structure corresponds to a particular data region and stores the multidimensional data tuples within said particular data region, wherein each multidimensional data tuple includes a plurality of values, said values specified along a plurality of dimensions wherein the multidimensional data tuples are spatial data that represent spatial data objects; and

c) storing the created hierarchical data structures in a first memory of a computer system.

2. The method of claim 1 further comprising:

a) retrieving a hierarchical data structure of a data region from the first memory;

b) storing the retrieved hierarchical data structure in a second memory of the computer system; and

c) performing a query on the hierarchical data structure stored in the second memory.

3. The method of claim 2, wherein the first memory is a permanent storage device and the second memory is a system memory of the computer system.

4. The method of claim 1, wherein a hierarchical data structure is created for each data region.

5. The method of claim 1, wherein hierarchical data structures are created only for some data regions.

6. The method of claim 5, wherein hierarchical data structures are created for all data regions that contain multidimensional data tuples.

7. The method of claim 1 further comprising creating a non-hierarchical data structure to represent the division of the data space into a plurality of data regions.

8. The method of claim 7, wherein creating the non-hierarchical data structure includes creating an array of data objects, wherein each particular data object represents one particular data region.

9. The method of claim 1 further comprising adaptively determining the number or size of the data regions in the multidimensional data space based on the number of multidimensional data tuples in the multidimensional space.

10. The method of claim 1, wherein the hierarchical data structures are k-d trees.

11. The method of claim 1, wherein the hierarchical data structures are quadtrees.

12. The method of claim 1, wherein said multidimensional data tuples are stored on a computer readable medium, the method further comprising:

a) retrieving the multidimensional data tuples from the computer readable medium; and

b) inserting each retrieved multidimensional data tuple into a hierarchical data structure of a region that the multidimensional data tuple intersects.

13. The method of claim 1, wherein the spatial data objects represent interconnect lines in a design layout of an integrated circuit.

14. For a computer system that represents spatial objects by using spatial data tuples, a method of storing spatial data tuples defined in a multidimensional coordinate system, the method comprising:

a) defining a plurality of regions in the multidimensional coordinate system; and

b) creating a plurality of hierarchical data structures for a plurality of said regions, wherein each hierarchical data structure corresponds to a particular region and stores the spatial data tuples of the spatial objects within said particular region, wherein each spatial data tuple includes a plurality of spatial attributes that are defined in the multidimensional coordinate system wherein the spatial objects are geometric objects.

15. The method of claim 14, further comprising:

for each particular region that has a hierarchical data structure,

a) identifying the spatial objects that are outside of the particular region that are needed for the analysis of the spatial objects within the particular region; and

b) inserting the spatial data tuples of the identified spatial objects into the hierarchical data structure for the particular region.

16. The method of claim 14, wherein a particular spatial object crosses a boundary between a first region and a second region, wherein a first portion of the spatial object is in the first region, the method further comprising:

a) defining a first spatial data tuple to represent the first portion; and

b) inserting the first spatial data tuple into the hierarchical data structure of the first region.

17. The method of claim 14, further comprising creating a non-hierarchical data structure to represent the plurality of regions, wherein the non-hierarchical data structure includes a plurality of entries and each particular entry represents a particular region.

18. The method of claim 17, wherein creating the non-hierarchical data structure includes creating an array of data objects, wherein each particular data object represents one particular region.

19. The method of claim 14, further comprising adaptively determining the number of regions.

20. The method of claim 19, wherein adaptively determining the number of regions includes increasing the number of the regions as the number of spatial objects increases.

21. The method of claim 20, wherein the number of the regions increases linearly with the number of spatial objects.

22. The method of claim 14 further comprising adaptively determining the size of the regions.

23. The method of claim 22, wherein adaptively determining the region sizes includes decreasing the size of the data regions as the number of spatial objects increases.

24. The method of claim 22, wherein adaptively determining the region sizes includes:

a) specifying a variety of region sizes;

b) for each region size, computing the total time for performing queries for all spatial data tuples in all the hierarchical data structures; and

c) selecting the region size that results in the smallest computed total query time.

25. The method of claim 24, wherein computing the total time comprises:

a) predicting the average number of spatial objects per each region;

b) computing the average time for querying a hierarchical data structure that includes the spatial data tuples for the average number of spatial data objects; and

c) computing the total time by multiplying the average time by the number of regions resulting from the region size.

26. The method of claim 14, wherein the hierarchical data structures are k-d trees.

27. The method of claim 14, wherein the hierarchical data structures are quadtrees.

28. The method of claim 15, wherein the geometric objects represent interconnect lines in an integrated circuit design layout.

29. A computer readable medium having a set of instructions stored therein for enabling a computer to store spatial data tuples defined in a multidimensional coordinate system, wherein the spatial data tuples are the computer decipherable representation of spatial objects, said set of instructions including:

a) a first set of instructions, which when executed by the computer cause the computer to define a plurality of regions in the multidimensional coordinate system; and

b) a second set of instructions, which when executed by the computer cause the computer to create a plurality of hierarchical data structures for a plurality of said regions, wherein each hierarchical data structure corresponds to a particular region and stores the spatial data tuples of the spatial objects within said particular region, wherein each spatial data tuple includes a plurality of spatial attributes that are defined in the multidimensional coordinate system wherein the spatial objects are geometric objects.

30. The computer readable medium of claim 29 further comprising:

a third set of instructions, which when executed by the computer, for each particular region that has a hierarchical data structure, cause the computer to (i) identify the spatial objects that are outside of the particular region that are needed for the analysis of the spatial objects within the particular region, and (ii) insert the spatial data tuples of the identified spatial objects into the hierarchical data structure for the particular region.

31. The computer readable medium of claim 29, wherein a particular spatial object crosses a boundary between a first region and a second region, wherein a first portion of the spatial object is in the first region, the computer readable medium further comprising:

a) a third set of instructions, which when executed by the computer cause the computer to define a first spatial data tuple to represent the first portion; and

b) a fourth set of instructions, which when executed by the computer cause the computer to insert the first spatial data tuple into the hierarchical data structure of the first region.

32. The computer readable medium of claim 29 further comprising a third set of instructions, which when executed by the computer cause the computer to create a non-hierarchical data structure to represent the plurality of regions, wherein the non-hierarchical data structure includes a plurality of entries and each particular entry represents a particular region.

33. The computer readable medium of claim 29 further comprising a third set of instructions, which when executed by the computer cause the computer to adaptively determine the number of regions.

34. A computer readable medium having a set of instructions stored therein for enabling a computer to store multidimensional data tuples defined in a multidimensional data space, said set of instructions including:

a) a first set of instructions, which when executed by the computer cause the computer to define a plurality of data regions in the multidimensional data space; and

b) a second set of instructions, which when executed by the computer cause the computer to create a plurality of hierarchical data structures for a plurality of said data regions, wherein each hierarchical data structure corresponds to a particular data region and stores the multidimensional data tuples that are within said particular data region, wherein each multidimensional data tuple includes a plurality of values, said values specified along a plurality of dimensions wherein the multidimensional data tuples are spatial data that represent spatial data objects.

35. An apparatus for storing multidimensional data tuples defined in a multidimensional data space, said apparatus comprising:

a) a means for defining a plurality of data regions in the multidimensional data space; and

b) a means for creating a plurality of hierarchical data structures for a plurality of said data regions, wherein each hierarchical data structure corresponds to a particular data region and stores the multidimensional data tuples that are within said particular data region, wherein each multidimensional data tuple includes a plurality of values, said values specified along a plurality of dimensions wherein the multidimensional data tuples are spatial data that represent spatial data objects.

36. An apparatus for storing spatial data tuples defined in a multidimensional coordinate system, wherein the spatial data tuples are the computer decipherable representation of spatial objects, said apparatus comprising:

a) a means for defining a plurality of regions in the multidimensional coordinate system; and

b) a means for creating a plurality of hierarchical data structures for a plurality of said regions, wherein each hierarchical data structure corresponds to a particular region and stores the spatial data tuples of the spatial objects within said particular region, wherein each spatial data tuple includes a plurality of spatial attributes that are defined in the multidimensional coordinate system wherein the spatial objects are geometric objects.