Stratos Papadomanolakis
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.
- {1} V. Akcelik, J. Bielak, G. Biros, I. Epanomeritakis, A. Fernandez, O. Ghattas, E. J. Kim, J. Lopez, D. O'Hallaron, T. Tu, and J. Urbanic. High resolution forward and inverse earthquake modeling on terascale computers. In Proceedings of Supercomputing 2003. Google Scholar
Digital Library
- {2} L. Arge, M. de Berg, H. J. Haverkort, and K. Yi. The priority R-Tree: a practically efficient and worst-case optimal R-Tree. In Proceedings of SIGMOD'04. Google ScholarDigital Library
- {3} N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The r*-tree: an efficient and robust access method for points and rectangles. SIGMOD Rec., 19(2):322-331, 1990. Google ScholarDigital Library
- {4} D. K. Blandford, G. E. Blelloch, and I. A. Kash. Compact representations of separable graphs. In SODA '03, pages 679-688, Philadelphia, PA, USA, 2003. Society for Industrial and Applied Mathematics. Google ScholarDigital Library
- {5} J. V. den Bercken, B. Seeger, and P. Widmayer. A generic approach to bulk loading multidimensional index structures. In Proceedings of VLDB '97, pages 406-415, San Francisco, CA, USA, 1997. Morgan Kaufmann Publishers Inc. Google ScholarDigital Library
- {6} O. Devillers, S. Pion, and M. Teillaud. Walking in a triangulation. In Proceedings of SCG '01, pages 106-114, New York, NY, USA, 2001. ACM Press. Google ScholarDigital Library
- {7} L. Devroye, C. Lemaire, and J.-M. Moreau. Expected time analysis for delaunay point location. Comput. Geom. Theory Appl., 29(2):61-89, 2004. Google ScholarDigital Library
- {8} V. Gaede and O. Guenther. Multidimensional access methods. ACM Comput. Surv., 30(2):170-231, 1998. Google ScholarDigital Library
- {9} M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, NY, USA, 1990. Google ScholarDigital Library
- {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.Google Scholar
- {11} O. Guenther. The design of the cell tree: An object-oriented index structure for geometric databases. In Proceedings of ICDE'89, pages 598-605, Washington, DC, USA, 1989. Google ScholarDigital Library
- {12} A. Guttman. R-Trees: a dynamic index structure for spatial searching. In Proceedings of the 1984 ACM SIGMOD Conference, pages 47-57. ACM Press, 1984. Google ScholarDigital Library
- {13} M. Hadjieleftheriou. www.cs.ucr.edu/marioh/spatialindex.Google Scholar
- {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.Google Scholar
- {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.Google Scholar
- {16} H. V. Jagadish. Spatial search with polyhedra. In Proceedings of ICDE'90, pages 311-319, 1990. Google ScholarDigital Library
- {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.Google Scholar
- {18} I. Kamel and C. Faloutsos. On packing R-Trees. In Proceedings of CIKM'93. Google ScholarDigital Library
- {19} G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. J. Parallel Distrib. Comput., 48(1):96-129, 1998. Google ScholarDigital Library
- {20} D. Komatitsch, S. Tsuboi, C. Li, and J. Tromp. A 14.6 billion degrees of freedom, 5 teraflops, 2.5 terabyte earthquake simulation on the earth simulator. In Proceedings of the Supercomputing Conference, 2003. Google ScholarDigital Library
- {21} S. Leutenegger, J. Edgington, and M. Lopez. STR: A simple and efficient algorithm for R-Tree packing. In Proceedings of ICDE 1997. Google ScholarDigital Library
- {22} S. Liao, M. A. Lopez, and S. T. Leutenegger. High dimensional similarity search with space filling curves. In Proceedings of ICDE 2001. Google ScholarDigital Library
- {23} J. C. Lopez, D. R. O'Hallaron, and T. Tu. Big wins with small application-aware caches. In Proceedings of Supercomputing '04, page 20, Washington, DC, USA, 2004. Google ScholarDigital Library
- {24} K.-L. Ma. Parallel volume ray-casting for unstructured-grid data on distributed-memory architectures. In Proceedings of PRS '95, pages 23-30, 1995. Google ScholarDigital Library
- {25} B. Moon, H. v. Jagadish, C. Faloutsos, and J. H. Saltz. Analysis of the clustering properties of the hilbert space-filling curve. IEEE TKDE, 13(1):124-141, 2001. Google ScholarDigital Library
- {26} J. A. Orenstein. Redundancy in spatial databases. In Proceedings of SIGMOD '89, pages 295-305, 1989. Google ScholarDigital Library
- {27} J. A. Orenstein and T. H. Merrett. A class of data structures for associative searching. In PODS '84, pages 181-190, New York, NY, USA, 1984. ACM Press. Google ScholarDigital Library
- {28} N. Roussopoulos and D. Leifker. Direct spatial search on pictorial databases using packed R-Trees. In SIGMOD '85, pages 17-31, New York, NY, USA, 1985. ACM Press. Google ScholarDigital Library
- {29} T. K. Sellis, N. Roussopoulos, and C. Faloutsos. The r+-tree: A dynamic index for multi-dimensional objects. In The VLDB Journal, pages 507-518, 1987. Google ScholarDigital Library
- {30} J. R. Shewchuk. Tetrahedral mesh generation by delaunay refinement. In Symposium on Computational Geometry, pages 86-95, 1998. Google ScholarDigital Library
- {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.Google Scholar
- {32} Office of Science Data Management Workshops. The office of science data-management challenge. Technical report, Department of Energy, 2005.Google Scholar
- {33} T. Tu and D. R. O'Hallaron. A computational database system for generatinn unstructured hexahedral meshes with billions of elements. In Proceedings of Supercomputing '04. Google ScholarDigital Library
- {34} S.-K. Ueng, C. Sikorski, and K.-L. Ma. Out-of-core streamline visualization on large unstructured meshes. IEEE Transctions VCG'96, 3(4):370-380, 1997. Google ScholarDigital Library
- {35} H. Yu, K.-L. Ma, and J. Welling. A parallel visualization pipeline for terascale earthquake simulations. In Proceedings of Supercomputing '04. Google ScholarDigital Library
Index Terms
- Efficient query processing on unstructured tetrahedral meshes
Recommendations
Simplification of unstructured tetrahedral meshes by point sampling
VG'05: Proceedings of the Fourth Eurographics / IEEE VGTC conference on Volume GraphicsTetrahedral meshes are widely used in scientific computing for representing three-dimensional scalar, vector, and tensor fields. The size and complexity of some of these meshes can limit the performance of many visualization algorithms, making it hard ...
Streaming Simplification of Tetrahedral Meshes
Unstructured tetrahedral meshes are commonly used in scientific computing to represent scalar, vector, and tensor fields in three dimensions. Visualization of these meshes can be difficult to perform interactively due to their size and complexity. By ...
Comments