AQUASUN: adaptive window query processing in CAD applications for physical design and verification

ABSTRACT

CAD applications for physical design and verification very often require enumerating all layout objects whose bounding box intersects an axis-aligned rectangular area. A number of multidimensional access methods exist to process such window queries. The performance of some important design and verification algorithms heavily depends on the processing speed of the used access method. For complex layouts, these methods require huge amounts of resident memory to attain this speed.In this paper, we present a new access method called AQUASUN, which brings a significant query processing performance improvement over other adaptive methods---methods which can cope with a continuously changing layout. These methods generally descend from the database world and are designed to perform the equivalent query in n-dimensional space. Our method is specifically tailored to two dimensions, exploiting 2D optimisations that significantly accelerate window queries within oblong objects like PCB tracks. Furthermore, AQUASUN makes use of an efficient compression technique which greatly cuts down on memory usage.

REFERENCES

• 1: H.K.Ahn,N.Mamoulis,and H.M.Wong.A survey on multidimensional access methods.Lecture COMP630c,"Spatial,Image and Multimedia Databases ",University o Science and Technology, Clearwater Bay,Hong Kong,Oct.1997.
• 2: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 3: W.De Pauw.(in Dutch) Datastructuren voor grafische informatie bij CAD (Data structures for graphical information in CAD).PhD thesis,Ghent University, Belgium,ELIS D9144,1991 -1992.
• 4: M.De Wilde.The internals of the adaptive box indexing method AQUASUN (in progress).Technical Report PARIS 02-01,Ghent University/ELIS,2002.
• 5: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 6: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 7: Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer, Generalized Search Trees for Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.562-573, September 11-15, 1995
• 8: Yun-Wu Huang , Ning Jing , Elke A. Rundensteiner, Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations, Proceedings of the 23rd International Conference on Very Large Data Bases, p.396-405, August 25-29, 1997
• 9: George Kollios , Vassilis J. Tsotras , Dimitrios Gunopulos , Alex Delis , Marios Hadjieleftheriou, Indexing Animated Objects Using Spatiotemporal Access Methods, IEEE Transactions on Knowledge and Data Engineering, v.13 n.5, p.758-777, September 2001 [doi>10.1109/69.956099]
• 10: Curtis P. Kolovson , Michael Stonebraker, Segment indexes: dynamic indexing techniques for multi-dimensional interval data, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.138-147, May 29-31, 1991, Denver, Colorado, United States
• 11: Beng Chin Ooi , Ron Sacks-Davis , Ken J. McDonell, Spatial indexing in binary decomposition and spatial bounding, Information Systems, v.16 n.2, p.211-237, 1991 [doi>10.1016/0306-4379(91)90016-3]
• 12: Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984 [doi>10.1145/356924.356930]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Graphics

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Trees

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

General Terms:
Algorithms, Performance

Keywords:
multidimensional access methods, rectangle indexes