超大型積體電路空間資料結構之設計與研究

Abstract

據我們所知, 空間資料結構對超大型積體電腦輔助設計系統 (VLSI CAD System)、壓縮器、地理資訊系統(GIS)等等表示方式及實際應用的重要基 礎。階層式的空間資料結構對於全世界在此方面工作的研究人員來說是廣 泛受到歡迎的。 而四元樹(quad tree)無疑地在VLSI CAD系統上是非常受 重視的一種資料結構。 在各種四元樹中,多儲存體四元樹(MSQT)及四元 串列四元樹 (QLQT)不僅頗負盛名且於查詢的速度上得到肯定;而兩者在記 憶體空間的使用上, 則略顯得浪費,也就是在物體參考節點上的使用。在 本篇論文中, 我們嚐試了取消這些節點的方法,再做了些實驗,看看它除了 能減少記憶體外, 是否同時能增進查詢運算的速度。我們並於本文中介紹 一些在空間資料結構中頗為有名的代表作。以上便是整篇論文的大致內容 及網要。 As we know, spatial data structures are significant fundamental of representing and physical applications, such as VLSI CAD system, compaction, and GIS, etc. Hierarchical spatial data structures are widely popular to researchers in this field all over the world. Quad tree is a valued data structure in VLSI CAD system undoubtedly. For each kind of quad trees, the query speed of multiple storage quad tree (MSQT) and quad list quad tree(QLQT) is affirmed. But the usage of their memory space is squandered more or less, that is, the use of object reference nodes (new SSQT), and we do some experiments to test it whether this change can increase the speed query operation except for decrement of memory. And we will introduce some famous representative works in spatial data structures. The above is overview and sheme of our paper.