Array based HV/VH tree: an effective data structure for layout representation

Jie REN; Wei-wei PAN; Yong-jun ZHENG; Zheng SHI; Xiao-lang YAN

doi:10.1631/jzus.C1100193

Your Location：

Home >

Browse articles >

Array based HV/VH tree: an effective data structure for layout representation

Electronic Engineering | Updated：2022-05-19

- Array based HV/VH tree: an effective data structure for layout representation
- Array based HV/VH tree: an effective data structure for layout representation
- Frontiers of Information Technology & Electronic Engineering Vol. 13, Issue 3, Pages: 232-237(2012)
- Affiliations：
  
  Institute of VLSI Design, Zhejiang University, Hangzhou 310027, China
- Author bio：
  
  [ "Jie REN, E-mail: renjie@vlsi.zju.edu.cn" ]
  Zheng SHI, E-mail: shiz@vlsi.zju.edu.cn
- Funds：
- DOI：10.1631/jzus.C1100193
  CLC： TN47
- Received：04 July 2018，
  
  Revised：2012-;2-;8，
  
  Published：2012-03
- Accepted：
Scan QR Code
Jie REN, Wei-wei PAN, Yong-jun ZHENG, et al. Array based HV/VH tree: an effective data structure for layout representation[J]. Frontiers of Information Technology & Electronic Engineering, 2012, 13(3): 232-237.
DOI：

Jie REN, Wei-wei PAN, Yong-jun ZHENG, et al. Array based HV/VH tree: an effective data structure for layout representation[J]. Frontiers of Information Technology & Electronic Engineering, 2012, 13(3): 232-237. DOI： 10.1631/jzus.C1100193.

摘要

Abstract

We present a new data structure for the representation of an integrated circuit layout. It is a modified HV/VH tree using arrays as the primary container in bisector lists and leaf nodes. By grouping and sorting objects within these arrays together with a customized binary search algorithm

our new data structure provides excellent performance in both memory usage and region query speed. Experimental results show that in comparison with the original HV/VH tree

which has been regarded as the best layout data structure to date

the new data structure uses much less memory and can become 30% faster on region query.

关键词

Keywords

references

M.D. Berg , , , O. Cheong , , , M.V. Kreveld , , , M. Overmars . . Computational Geometry: Algorithms and Applications . . Springer, the Netherlands , , 2008 . . p.219 - - 238 . . . .

R.L. Brown . . Multiple storage quad trees: a simpler faster alternative to bisector list quad trees . . IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. , , 1986 . . 5 ( ( 3 ): ): 413 - - 419 . . DOI: 10.1109/TCAD.1986.1270210 http://doi.org/10.1109/TCAD.1986.1270210 . .

G. Kedem . . The Quad-CIF Tree: a Data Structure for Hierarchical On-line Algorithms . . Proc. 19th Design Automation Conf. , , 1982 . . p.352 - - 357 . . . .

G.G. Lai , , , D. Fussell , , , D.F. Wong . . HV/VH Trees: a New Spatial Data Structure for Fast Region Queries . . Proc. 30th Int. Design Automation Conf. , , 1993 . . p.43 - - 47 . . DOI: 10.1145/157485.164562 http://doi.org/10.1145/157485.164562 . .

G.G. Lai , , , D.S. Fussell , , , D.F. Wong . . Hinted quad trees for VLSI geometry DRC based on efficient searching for neighbors . . IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. , , 1996 . . 15 ( ( 3 ): ): 317 - - 324 . . DOI: 10.1109/43.489102 http://doi.org/10.1109/43.489102 . .

D.P. Mehta . . Handbook of Data Structures and Applications . . Chapter 52: Layout Data Structures. Chapman & Hall/CRC, USA , , 2005 . . p.1046 - - 1063 . . . .

D.P. Mehta , , , H. Zhou . . Handbook of Algorithms for Physical Design Automation . . Chapter 4: Basic Data Structures. Auerbach Publications, FL, USA , , 2008 . . p.55 - - 69 . . . .

J.K. Ousterhout . . Corner stitching: a data structure technique for VLSI layout tools . . IEEE Trans. Comput.- Aided Des. Integr. Circ. Syst. , , 1982 . . 3 ( ( 1 ): ): 87 - - 100 . . DOI: 10.1109/TCAD.1984.1270061 http://doi.org/10.1109/TCAD.1984.1270061 . .

A. Pitaksanonkul , , , S. Thanawastien , , , C. Lursinsap . . Comparisons of quad trees and 4-D trees: new results . . IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. , , 1989 . . 8 ( ( 11 ): ): 1157 - - 1164 . . DOI: 10.1109/43.41501 http://doi.org/10.1109/43.41501 . .

J.B. Rosenberg . . Geographical data structures compared: a study of data structures supporting region queries . . IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. , , 1985 . . 4 ( ( 1 ): ): 53 - - 67 . . DOI: 10.1109/TCAD.1985.1270098 http://doi.org/10.1109/TCAD.1985.1270098 . .

H. Samet . . Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS . . Addison-Wesley, MA , , 1990a . . .

H. Samet . . The Design and Analysis of Spatial Data Structures , , : : MA Addison-Wesley , , 1990b . . .

H. Samet . . Foundations of Multidimensional and Metric Data Structures . . Morgan Kaufmann, CA, USA , , 2006 . . p.474 - - 483 . . . .

L. Weyten , , , W. de Pauw . . Quad list quad trees: a geometrical data structure with improved performance for large region queries . . IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. , , 1989 . . 8 ( ( 3 ): ): 229 - - 233 . . DOI: 10.1109/43.21842 http://doi.org/10.1109/43.21842 . .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰