Nearest neighbor mechanism

Details Nearest neighbor mechanism Nearest neighbor mechanism

2005-12-27

2005-12-27

Siek, Vuthe (Department: 2825)

Computer-aided design and analysis of circuits and semiconductor

Nanotechnology related integrated circuit design

C716S030000, C716S030000

Reexamination Certificate

active

06981235

ABSTRACT:
A method of analyzing a design of an electronic circuit may include selecting a query object in a collection of sets of intervals for the design, where each set of intervals along a first common axis, the collection of sets along a second common axis. Candidate objects within the collection that are candidates to be closest to the query object may be identified. A nearest neighbor object is selected from the candidate objects, the nearest neighbor object having shortest distance to the query object.

REFERENCES:
patent: 5157618 (1992-10-01), Ravindra et al.
patent: 5911061 (1999-06-01), Tochio et al.
patent: 6253363 (2001-06-01), Gasanov et al.
patent: 6324675 (2001-11-01), Dutta et al.
patent: 6349403 (2002-02-01), Dutta et al.
patent: 6625611 (2003-09-01), Teig et al.
patent: 6701306 (2004-03-01), Kronmiller et al.
patent: 6785874 (2004-08-01), Tsukuda
patent: 2002/0059194 (2002-05-01), Choi et al.
patent: 2004/0044980 (2004-03-01), Juengling
Tzionas et al.,“A New,Cellular Automation-Based, Nearest Neighbor Pattern Classifier and Its VLSI Implementation”, Sep. 1994, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 2, iss. 3, pp. 343-353.
Christian et al.,“A VLSI Interval Router for High-Speed Networks”, May 1996, IEEE Candidan Conference on Electrical and Computer Engineering, vol. 1, pp. 154-157.
Benetis et al., “Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects”, Jul. 2002, IEEE Proceedings, International Database Engineering and Applications Symposium.
Ahuja, R.K. et al.,eds.,Networks Flows. Theory. Algorithms, and Applications(1993) pp. 510-542, Prentice Hall, Upper Saddle River, NJ.
Al-Yamani, A. et al. “HPTS: Heterogeneous Parallel Tabu Search for VLSI Placement”Proceedings of the 2002 Congress on Evolutionary Computation(May 12-17, 2002) 1:351-355.
Anderson, R. et al. “An O(n log n) Algorithm for 1-D Tile Compaction”ICCAD-89-International Conference on Computer-Aided Design(Nov. 5-9, 1989) pp. 144-147.
Balasa, F. et al. “Efficient Solution Space Exploration Based on Segment Trees in Analog Placement with Symmetry Constraints” InIEEE/ACM International Conference on Computer Aided Design(Nov. 10-14, 2002) pp. 497-502.
Barzaghi, M. et al. “Hierarchical Management of VLSI Cells at Different Description Levels”Proceedings of the 6thMediterranean Electrotechnical Conference(May 22-24, 1991) 1:327-330.
Bern, J. et al. “Some Heuristics for Generating Tree-like FBDD Types”IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems(Jan. 1996) 15(1):127-130.
Bhattacharya, S. and W.-T. Tsai “Area Efficient Binary Tree Layout”1stGreat Lakes Symposium on VLSI(Mar. 1-2, 1991) pp. 18-24.
Blust, G. and D.P. Mehta “Corner Stitching for L-shaped Tiles”Proceedings of the 3rdGreat Lakes Symposium on VLSI, Design Automation of High Performance VLSI Systems(Mar. 5-6, 1993) pp. 67-68.
Borah, M. et al. “An Edge-Based Heuristic for Steiner Routing”IEEE Transactions on Computer-Aided Design of Integrated Cricuits and Systems(Dec. 1994) 13(12):1563-1568.
Brück, R. and H. Wronn “ —geoADDICTION—Flexible Handling of Geometries in IC-Layout Tools”ISCAS '88—IEEE International Symposium on Circuits and Systems(Jun. 7-9, 1988) 1:723-726.
Cadence Design Systems, Inc.IC Shaped-Based Technology Chip Assembly User GuideProduct Version 11.0 (Nov. 2001).
Carlson, E.C. and R.A. Rutenbar “A Scanline Data Structure Processor for VLSI Geometry Checking”IEEE Transactions on Computer-Aided Design(Sep. 1987) 6(5):780-794.
Cheung, P. and J. Hesketh “Design Automation Tools for Tile-Based Analogue Cells”IEE Colloquium on New Directions in VLSI Design(Nov. 27, 1989) pp. 3/1-3/5.
Chiang, C. and C.-S. Chiang “Octilinear Steiner Tree Construction”MWSCAS-2002-The 2002 45thMidwest Symposium on Circuits and Systems(Aug. 4-7, 2002) 1:603-606.
Cong, J. et al. “Multilevel Approach to Full-Chip Gridless Routing”ICCAD 2001—IEEE/ACM International Conference on Computer-Aided Design(Nov. 4-8, 2001) pp. 396-403.
Curatelli, F. et al. “Efficient Management of Complex Elements in Physical IC Design”Proceedings of the IEEE International Symposium on Circuits and Systems(May 1-3, 1990) 1:456-459.
Das, S. and B.B. Bhattacharya “Channel Routing in Manhattan-Diagonal Model”Proceedings of the 9thInternational Conference on VLSI Design(Jan. 3-6, 1996) pp. 43-48.
Dasgupta, P. et al. “Multiobjective Search in VLSI Design”Proceedings of the 7thInternational Conference on VLSI Design(Jan. 1994) pp. 395-400.
Dasgupta, P. et al. “Searching Networks With Unrestricted Edge Costs”IEEE Transactions on Systems, Man and Cybernetics-Part A: Systems and Humans(Nov. 2001) 31(6):497-507.
Dijkstra, E.W. “A Note on Two Problems in Connexion with Graphs”Numerische Mathematik(1959) 1:269-271.
de Dood, P. et al. “A Two-Dimensional Topological Compactor With Octagonal Geometry”28thACM/IEEE Automation Conference(1991) pp. 727-731.
Doong, K. Y.-Y. et al. “Infrastructure Development and Integration of Electrical-Based Dimensional Process Window Checking”IEEE Transactions on Semiconductor Manufacturing(May 2004) 17(2):123-141.
Dutt, S. “New Faster Kernighan-Lin-Type Graph-Partitioning Algorithms”ICCAD-93—1993 IEEE/ACM International Conference on Computer-Aided Design(Nov. 7-11, 1993) pp. 370-377.
Façanha, H.S. et al. “Layout Tool for High Speed Electronic and Optical Circuits”IEE Colloquium on Analogue IC Design: Obstacles and Opportunities(Jun. 18, 1990) pp. 3/1-3/5.
Façanha, H.S. et al. “Data structures for physical representation of VLSI”Software Engineering Journal(Nov. 1990) 5(6):339-349.
Fang, J.P. and S.J. Chen “Tile-Graph-Based Power Planning”ISCAS'03—Proceedings of the 2003 International Symposium on Circuits and Systems(May 25-28, 2003) 5:V-501-V-504.
Faroe, O. et al. “Local Search for Final Placement in VLSI Design”ICCAD 2001—IEEE/ACM International Conference on Computer-Aided Design(Nov. 4-8, 2001) pp. 565-572.
Gannett, J.W. “Shortfinder: A Graphical CAD Tool for Locating Net-to-Net Shorts in VLSI Chip Layouts”IEEE Transactions on Computer-Aided Design(Jun. 1990) 9(6):669-674.
Grgek, M. et al. “Performance Comparison of Several Data Structures for Storing VLSI Geometry”The IEEE Region 8 EUROCON 2003, Computer as a Tool(Sep. 22-24, 2003) 1:156-159.
Guibas, L.J. and J. Stolfi “On Computing All North-East Nearest Neighbors in the L1Metric”Information Processing Letters(Nov. 8, 1983) 17:219-223.
Hettiaratchi, S. and P.Y.K. Cheung “A novel implementation of tile-based address mapping” Date'04—Proceedings of the Design, Automation and Test in Europe Conference and Exhibition(Feb. 16-20, 2004) 1:306-310.
Hsiao, P.-Y. and W.-S. Feng “Using a Multiple Storage Quad Tree on a Hierarchical VLSI Compaction Scheme”IEEE Transactions on Computer-Aided Design(May 1990) 9(5):522-536.
Hsiao, P.-Y. et al. “Optimal tile partition for space region of integrated circuits geometry”IEEE Proceedings-E(May, 1993) 140(3):145-153.
Hur, S.-W. and J. Lillas “Relaxation and Clustering In a Local Search Framework: Application to Linear Placement”Proceedings of the 36h Design Automation Conference(Jun. 21-25, 1999) pp. 360-366.
Hwang, F.K. “An O(n log n) Algorithm for Rectilinear Minimal Spanning Trees”J ACM(Apr. 1979) 26(2):177-182.
Iwasaki, H. et al. “An Effective Data Structure for VLSI Layout Systems”Proceedings of the IEEE International Symposium on Circuits and Systems(Jun. 11-14, 1991) 5:3134-3137.
Johann, M. and R. Reis “Net by Net Routing with a New Path Search Algorithm”Proceedings of the 13thSymposium on Integrated Circuits

Affiliated with

Also associated with

Rating

Nearest neighbor mechanism does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Nearest neighbor mechanism, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nearest neighbor mechanism will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3519103