Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-03-15
2003-09-23
Mizrahi, Diane D. (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C716S030000
Reexamination Certificate
active
06625611
ABSTRACT:
BACKGROUND OF THE INVENTION
Many applications today analyze multidimensional data records. A multidimensional data record contains a number of data values, which are defined along a number of dimensions (also called attributes or keys) in a multidimensional space. Such records are typically stored in data files or databases.
A spatial data record is one type of multidimensional data record. Spatial data records typically describe the attributes (e.g., the position, size, shape, etc.) of geometric objects, such as points, lines, polygons, regions, surfaces, volumes, etc. Spatial records are used in many fields, including computer-aided design, computer graphics, data management systems, robotics, image processing, geographic information systems, pattern recognition, and computational geometry.
Effective data structures are needed to organize multidimensional and spatial data records efficiently, in order to optimize the time for querying these records. For instance, a sequential list of the multidimensional data records provides the simplest way of storing the records. However, the time needed for performing a query on such a list is intolerably high in most cases since each record in the list needs to be examined for each query.
Numerous multidimensional data structures have been proposed for organizing multidimensional and spatial data records. Hanan Samet,
The Design and Analysis of Spatial Data Structures
, Addison-Wesley Publishing, 1990, includes a review of many of these data structures.
Multidimensional data structures include hierarchical data structures. Hierarchical structures are based on the principle of recursive decomposition of the data space (i.e., the object space or the image space). In other words, these data structures are created by recursively dividing the data space, and storing the data records according to their location in the divided space.
Quadtrees and k-d trees are two types of hierarchical data structures.
FIGS. 3-5
illustrate one example of a quadtree, while
FIG. 6
illustrates one example of a k-d tree. These examples are described by reference to a use of spatial data records to represent interconnect lines on integrated-circuit layouts. Before describing the examples illustrated in
FIGS. 3-6
, interconnect lines are first described below.
A. Interconnect Lines
Electronic design automation (“EDA”) applications assist engineers in designing integrated circuits (“IC's”). Specifically, these applications provide sets of computer-based tools for creating, editing, and analyzing IC design layouts. These layouts are formed by geometric shapes that represent layers of different materials and devices on IC's. Spatial data records define the spatial attributes of many of these geometric shapes. For instance, spatial data records are used to define geometric shapes that represent conductive interconnect lines. Interconnect lines route signals on the IC's. These lines are sometimes referred to as wire segments or segs.
EDA applications typically characterize interconnect lines as rectangles.
FIG. 1
illustrates one such characterization. As shown in this figure, the rectangular line
105
can be represented by different sets of spatial attributes. For instance, the rectangle
105
can be represented by (1) the x- and y-coordinates of any of its opposing corners (such as the corners defined by the minimum and maximum x- and y-coordinates), or (2) the coordinates of one of its comers along with its width and height.
FIG. 2
illustrates a spatial data record
205
that represents the rectangle
105
by its minimum x-coordinate (X
MIN
), the minimum y-coordinate (Y
MIN
), width along the x-coordinate (&Dgr;X), and height along the y-coordinate (&Dgr;Y). The data record
205
also identifies the layer that the interconnect line
105
traverses. This data record further designates the line as a white or gray line. A line is specified as a white line when that line is deemed critical for a particular operation. Alternatively, a line is specified as a gray line when it is not critical for a particular operation. However, a gray line might need to be taken into account for the analysis of a white line.
The six fields of the data record
205
can be viewed as six dimensions. These dimensions define a six-dimensional data space. The data record for each interconnect line can thus be viewed as a data point in the six-dimensional data space.
An interconnect line capacitively couples to other interconnect lines that are within a certain distance of it. This distance is typically the maximum distance of influence between two conductive interconnect lines. This distance is referred to as the halo distance. Capacitive coupling can exist between interconnect lines in the same plane (i.e., intra-layer coupling) or in different planes (i.e., inter-layer coupling).
Calculating such interconnect capacitances has become a critical step in the design of IC's. The decreasing size of processing geometries have increased the concentration and proximity of the interconnect lines, which, in turn, has increased the parasitic effect of interconnect capacitances. Such parasitic capacitances increase signal delay and cause crosstalk, which prevent the IC's from functioning properly.
Hence, in designing an IC, an engineer uses an EDA application to extract and analyze the interconnect capacitances that certain critical interconnect lines experience. An EDA application typically performs two steps to extract the capacitances experienced by a critical interconnect line. First, it identifies all interconnect lines within a certain distance of the critical interconnect line. Second, it calculates the capacitance between the critical interconnect line and each retrieved interconnect line.
To identify quickly the interconnect lines that are near a critical interconnect line, an EDA application needs to use data structures that efficiently organize the data relating to the interconnect line. Two commonly used data structures are quadtrees and k-d trees.
B. Ouadtrees.
Quadtrees are hierarchical tree data structures with the common property that they recursively decompose the data space into quadrants. One type of quadtree is a region quadtree, which successively subdivides the image space into equal-sized quadrants.
FIGS. 3-5
illustrate one manner for constructing a region quadtree.
FIG. 3
present IC layout
305
that contains forty interconnect lines.
FIG. 4
presents one manner of partitioning the IC layout
305
into equal-sized quadrants along the x- and y-axes.
FIG. 5
illustrates the quadtree resulting from this subdivision.
In this example, each interconnect line is characterized as a rectangle that is defined by its minimum x- and y-coordinates and its width and height. The layer information for each rectangle is ignored as the IC layout is divided only along the x- and y-axes. Table 1 lists the four dimension values for each rectangular interconnect line.
TABLE 1
Object
X
MIN
&Dgr;X
Y
MIN
&Dgr;Y
1
140
15
135
12.5
2
145
17.5
120
10
3
120
5
130
20
4
157.5
22.5
125
17.5
5
165
10
147.5
7.5
6
135
40
160
10
7
160
10
160
30
8
190
5
135
15
9
170
27.5
105
20
10
110
50
107.5
7.5
11
70
60
187.5
22.5
12
205
10
130
17.5
13
215
20
170
22.5
14
250
25
170
12.5
15
250
50
112.5
22.5
16
235
5
135
30
17
245
10
220
35
18
230
25
245
10
19
70
160
275
12.5
20
160
35
225
35
21
15
10
250
30
22
20
20
150
30
23
50
25
157.5
12.5
24
40
15
125
20
25
15
45
100
12.5
26
80
10
122.5
17.5
27
30
27.5
60
20
28
80
17.5
82.5
7.5
29
45
15
20
20
30
10
50
20
10
31
110
10
40
10
32
130
60
70
15
33
140
50
42.5
7.5
34
180
10
30
20
35
270
5
35
20
36
217.5
37.5
75
15
37
217.5
7.5
65
25
38
255
10
50
10
39
210
35
5
15
40
75
32.5
142.5
12.5
As shown in this
FIG. 4
, the IC layout
305
is initially partitioned along the x- and y-axes into four equal-sized quadrants. The resulting quadrants are further subdivided into smaller quadrants. The subdivision process continues for all quadrants that would wholly contain at least two interconnect lines and would have at least one non-empty child node. It shou
Kronmiller Tom
Siegel Andrew F.
Teig Steven
Cadence Design Systems Inc.
Mizrahi Diane D.
Stattler Johansen & Adeli LLP
LandOfFree
Method and apparatus for representing multidimensional data does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for representing multidimensional data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for representing multidimensional data will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3105922