Efficient query processing on unstructured tetrahedral meshes

ABSTRACT

Modern scientific applications such as fluid dynamics and earthquake modeling heavily depend on massive volumes of data produced by computer simulations. Such applications require new data management capabilities in order to scale to terabyte-scale data volumes. The most common way to discretize the application domain is to decompose it into pyramids, forming an unstructured tetrahedral mesh. Modern simulations generate meshes of high resolution and precision, to be queried by a visualization or analysis tool. Tetrahedral meshes are extremely flexible and therefore vital to accurately model complex geometries, but also are difficult to index. To reduce query execution time, applications either use only subsets of the data or rely on different (less flexible) structures, thereby trading accuracy for speed.This paper presents efficient indexing techniques for common spatial (point and range) on tetrahedral meshes. Because the prevailing multidimensional indexing techniques attempt to approximate the tetrahedra using simpler shapes (primarily rectangles) the query performance deteriorates significantly as a function of the mesh's geometric complexity. We develop Directed Local Search (DLS), an efficient indexing algorithm based on mesh topology information that is practically insensitive to the geometric properties of meshes. We show how DLS can be easily and efficiently implemented within modern DBMS without requiring new exotic index structures and complex preprocessing. Finally, we present a new data layout approach for tetrahedral mesh datasets that provides better performance for scientific applications.compared to the traditional space filling curves. In our PostgreSQL implementation DLS reduces the number of disk page accesses by 26% to 4x, and improves the overall query execution time by 25% to 4.

REFERENCES

• 1: Vokan Akcelik , Jacobo Bielak , George Biros , Ioannis Epanomeritakis , Antonio Fernandez , Omar Ghattas , Eui Joong Kim , Julio Lopez , David O'Hallaron , Tiankai Tu , John Urbanic, High Resolution Forward And Inverse Earthquake Modeling on Terascale Computers, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.52, November 15-21, 2003
• 2: Lars Arge , Mark de Berg , Herman J. Haverkort , Ke Yi, The Priority R-tree: a practically efficient and worst-case optimal R-tree, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007608]
• 3: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, ACM SIGMOD Record, v.19 n.2, p.322-331, Jun. 1990
• 4: Daniel K. Blandford , Guy E. Blelloch , Ian A. Kash, Compact representations of separable graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 5: Jochen Van den Bercken , Bernhard Seeger , Peter Widmayer, A Generic Approach to Bulk Loading Multidimensional Index Structures, Proceedings of the 23rd International Conference on Very Large Data Bases, p.406-415, August 25-29, 1997
• 6: Olivier Devillers , Sylvain Pion , Monique Teillaud, Walking in a triangulation, Proceedings of the seventeenth annual symposium on Computational geometry, p.106-114, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378643]
• 7: Luc Devroye , Christophe Lemaire , Jean-Michel Moreau, Expected time analysis for Delaunay point location, Computational Geometry: Theory and Applications, v.29 n.2, p.61-89, October 2004 [doi>10.1016/j.comgeo.2004.02.002]
• 8: 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]
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1990
• 10: [10] J. Gray, D. T. Liu, M. Nieto-Santisteban, A. S. Szalay, D. DeWitt, and G. Heber. Data managemenet in the coming decade. Technical Report MSR-TR-2005-10, Microsoft Research, 2004.
• 11: Oliver Günther, The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases, Proceedings of the Fifth International Conference on Data Engineering, p.598-605, February 06-10, 1989
• 12: 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
• 13: [13] M. Hadjieleftheriou. www.cs.ucr.edu/marioh/spatialindex.
• 14: [14] G. Heber and J. Gray. Supporting finite element analysis with a relational database backend part i: There is life beyond files. Technical Report MSR-TR-2005-49, Microsoft Research, 2005.
• 15: [15] G. Heber and J. Gray. Supporting finite element analysis with a relational database backend part ii: Database design and access. Technical Report MSR-TR-2006-21, Microsoft Research, 2006.
• 16: H. V. Jagadish, Spatial Search with Polyhedra, Proceedings of the Sixth International Conference on Data Engineering, p.311-319, February 05-09, 1990
• 17: [17] J. Gray, D. Slutz, A. Szalay, A. Thakar, J. vandenBerg, P. Kunszt, and C. Stoughton. Data mining the SDSS skyserver database. Technical Report MSR-TR-2002-01, Microsoft Research, 2002.
• 18: Ibrahim Kamel , Christos Faloutsos, On packing R-trees, Proceedings of the second international conference on Information and knowledge management, p.490-499, November 01-05, 1993, Washington, D.C., United States [doi>10.1145/170088.170403]
• 19: George Karypis , Vipin Kumar, Multilevel k-way partitioning scheme for irregular graphs, Journal of Parallel and Distributed Computing, v.48 n.1, p.96-129, Jan. 1998 [doi>10.1006/jpdc.1997.1404]
• 20: Dimitri Komatitsch , Seiji Tsuboi , Chen Ji , Jeroen Tromp, A 14.6 billion degrees of freedom, 5 teraflops, 2.5 terabyte earthquake simulation on the Earth Simulator, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.4, November 15-21, 2003
• 21: Scott T. Leutenegger , J. M. Edgington , Mario A. Lopez, STR: A Simple and Efficient Algorithm for R-Tree Packing, Proceedings of the Thirteenth International Conference on Data Engineering, p.497-506, April 07-11, 1997
• 22: Swanwa Liao , Mario A. Lopez , Scott T. Leutenegger, High Dimensional Similarity Search With Space Filling Curves, Proceedings of the 17th International Conference on Data Engineering, p.615-622, April 02-06, 2001
• 23: Julio C. Lopez , David R. O'Hallaron , Tiankai Tu, Big Wins with Small Application-Aware Caches, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.20, November 06-12, 2004 [doi>10.1109/SC.2004.14]
• 24: Kwan-Liu Ma, Parallel volume ray-casting for unstructured-grid data on distributed-memory architectures, Proceedings of the IEEE symposium on Parallel rendering, p.23-30, October 30-31, 1995, Atlanta, Georgia, United States [doi>10.1145/218327.218333]
• 25: Bongki Moon , H. v. Jagadish , Christos Faloutsos , Joel H. Saltz, Analysis of the Clustering Properties of the Hilbert Space-Filling Curve, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.124-141, January 2001 [doi>10.1109/69.908985]
• 26: J. A. Orenstein, Redundancy in spatial databases, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.295-305, June 1989, Portland, Oregon, United States
• 27: J. A. Orenstein , T. H. Merrett, A class of data structures for associative searching, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588037]
• 28: Nick Roussopoulos , Daniel Leifker, Direct spatial search on pictorial databases using packed R-trees, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.17-31, May 1985, Austin, Texas, United States
• 29: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 30: Jonathan Richard Shewchuk, Tetrahedral mesh generation by Delaunay refinement, Proceedings of the fourteenth annual symposium on Computational geometry, p.86-95, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276894]
• 31: [31] C. Silva, Y. Chiang, J. El-Sana, and P. Lindstrom. Out-of-core algorithms for scientific visualization and computer graphics. In Visualization'02, 2002.
• 32: [32] Office of Science Data Management Workshops. The office of science data-management challenge. Technical report, Department of Energy, 2005.
• 33: Tiankai Tu , David R. O'Hallaron, A Computational Database System for Generatinn Unstructured Hexahedral Meshes with Billions of Elements, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.25, November 06-12, 2004 [doi>10.1109/SC.2004.2]
• 34: Shyh-Kuang Ueng , Christopher Sikorski , Kwan-Liu Ma, Out-of-Core Streamline Visualization on Large Unstructured Meshes, IEEE Transactions on Visualization and Computer Graphics, v.3 n.4, p.370-380, October 1997 [doi>10.1109/2945.646239]
• 35: Hongfeng Yu , Kwan-Liu Ma , Joel Welling, A Parallel Visualization Pipeline for Terascale Earthquake Simulations, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.49, November 06-12, 2004 [doi>10.1109/SC.2004.6]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
          Subjects: File organization

General Terms:
Experimentation, Measurement, Performance

Keywords:
spatial indexing, tetrahedral mesh indexing