Full Text:
<5072>
CLC number: TN47
On-line Access: 2024-08-27
Received: 2023-10-17
Revision Accepted: 2024-05-08
Crosschecked: 2012-02-08
Cited: 0
Clicked: 7767
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. Array based HV/VH tree: an effective data structure for layout representation[J]. Journal of Zhejiang University Science C, 2012, 13(3): 232-237.
@article{title="Array based HV/VH tree: an effective data structure for layout representation",
author="Jie Ren, Wei-wei Pan, Yong-jun Zheng, Zheng Shi, Xiao-lang Yan",
journal="Journal of Zhejiang University Science C",
volume="13",
number="3",
pages="232-237",
year="2012",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.C1100193"
}
%0 Journal Article
%T Array based HV/VH tree: an effective data structure for layout representation
%A Jie Ren
%A Wei-wei Pan
%A Yong-jun Zheng
%A Zheng Shi
%A Xiao-lang Yan
%J Journal of Zhejiang University SCIENCE C
%V 13
%N 3
%P 232-237
%@ 1869-1951
%D 2012
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.C1100193
TY - JOUR
T1 - Array based HV/VH tree: an effective data structure for layout representation
A1 - Jie Ren
A1 - Wei-wei Pan
A1 - Yong-jun Zheng
A1 - Zheng Shi
A1 - Xiao-lang Yan
J0 - Journal of Zhejiang University Science C
VL - 13
IS - 3
SP - 232
EP - 237
%@ 1869-1951
Y1 - 2012
PB - Zhejiang University Press & Springer
ER -
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.
[1]Berg, M.D., Cheong, O., Kreveld, M.V., Overmars, M., 2008. Computational Geometry: Algorithms and Applications. Springer, the Netherlands, p.219-238.
[2]Brown, R.L., 1986. Multiple storage quad trees: a simpler faster alternative to bisector list quad trees. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst., 5(3):413-419.
[3]Kedem, G., 1982. The Quad-CIF Tree: a Data Structure for Hierarchical On-line Algorithms. Proc. 19th Design Automation Conf., p.352-357.
[4]Lai, G.G., Fussell, D., Wong, D.F., 1993. HV/VH Trees: a New Spatial Data Structure for Fast Region Queries. Proc. 30th Int. Design Automation Conf., p.43-47.
[5]Lai, G.G., Fussell, D.S., Wong, D.F., 1996. Hinted quad trees for VLSI geometry DRC based on efficient searching for neighbors. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst., 15(3):317-324.
[6]Mehta, D.P., 2005. Handbook of Data Structures and Applications. Chapter 52: Layout Data Structures. Chapman & Hall/CRC, USA, p.1046-1063.
[7]Mehta, D.P., Zhou, H., 2008. Handbook of Algorithms for Physical Design Automation. Chapter 4: Basic Data Structures. Auerbach Publications, FL, USA, p.55-69.
[8]Ousterhout, J.K., 1982. Corner stitching: a data structure technique for VLSI layout tools. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst., 3(1):87-100.
[9]Pitaksanonkul, A., Thanawastien, S., Lursinsap, C., 1989. Comparisons of quad trees and 4-D trees: new results. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst., 8(11):1157-1164.
[10]Rosenberg, J.B., 1985. Geographical data structures compared: a study of data structures supporting region queries. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst., 4(1):53-67.
[11]Samet, H., 1990a. Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS. Addison-Wesley, MA.
[12]Samet, H., 1990b. The Design and Analysis of Spatial Data Structures. Addison-Wesley, MA.
[13]Samet, H., 2006. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann, CA, USA, p.474-483.
[14]Weyten, L., de Pauw, W., 1989. Quad list quad trees: a geometrical data structure with improved performance for large region queries. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst., 8(3):229-233.
Open peer comments: Debate/Discuss/Question/Opinion
<1>