Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2006-12-19
2006-12-19
Wassum, Luke S (Department: 2167)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
07152071
ABSTRACT:
A shape-based geometric database uses R-trees to compactly and efficiently represent design objects. Such R-trees may be populated in an efficient and balanced manner to improve the efficient use of such R-trees in various stages of circuit design, for example. For example, tiles are assigned to bins depending at least partially on orientation of the tiles and on proximity of the tiles to reference tracks having similar orientations. Bin R-trees may be defined, along with direction and layer R-trees using a level sequential process from lower levels to higher levels until a root node is defined in each case.
REFERENCES:
patent: 5520388 (1996-05-01), Osborn
patent: 5963956 (1999-10-01), Smartt
patent: 5987460 (1999-11-01), Niwa et al.
patent: 6252605 (2001-06-01), Beesley et al.
patent: 6301797 (2001-10-01), Sundaram et al.
patent: 6349309 (2002-02-01), Aggarwal et al.
patent: 6381605 (2002-04-01), Kothuri et al.
patent: 6470344 (2002-10-01), Kothuri et al.
patent: 6505205 (2003-01-01), Kothuri et al.
patent: 6741983 (2004-05-01), Birdwell et al.
patent: 6882997 (2005-04-01), Zhang et al.
patent: 2002/0151315 (2002-10-01), Hendrey
patent: 2002/0184607 (2002-12-01), Alpert et al.
Gholamhosein Sheikholeslami, Surojit Chatterjee, Aidong Zhang, “WaveCluster: a wavelet-based clustering approach for spatial data in very large databases”, The VLDB Journal, 2000, pp. 289-304.
Zhaoyun Xing, Russell Kao, “A Minimum Cost Path Search Algorithm Through Tile Obstacles”, ACM 2001, pp. 192-197.
J. Cong, et al., An Implicit Connection Graph Maze Routing Algorithm for ECO Routing, Proc. ICCAD 1999, San Jose, CA, 4 pages.
A. Guttman, R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. of ACM SIGMOD, 1984, Boston, MA, pp. 47-57.
T. Cormen, et al., Introduction to Algorithms, MIT Press, 1990, pp. 527-531.
Black Linh
Sun Microsystems Inc.
Wassum Luke S
LandOfFree
Shape-based geometric database and methods and systems for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Shape-based geometric database and methods and systems for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shape-based geometric database and methods and systems for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3666477