Global static indexing for real-time exploration of very large regular grids

ABSTRACT

In this paper we introduce a new indexing scheme for progressive traversal and visualization of large regular grids. We demonstrate the potential of our approach by providing a tool that displays at interactive rates planar slices of scalar field data with very modest computing resources. We obtain unprecedented results both in terms of absolute performance and, more importantly, in terms of scalability. On a laptop computer we provide real time interaction with a 2048³ grid (8 Giga-nodes) using only 20MB of memory. On an SGI Onyx we slice interactively an 8192³ grid (½ tera-nodes) using only 60MB of memory. The scheme relies simply on the determination of an appropriate reordering of the rectilinear grid data and a progressive construction of the output slice. The reordering minimizes the amount of I/O performed during the out-of-core computation. The progressive and asynchronous computation of the output provides flexible quality/speed tradeoffs and a time-critical and interruptible user interface.

REFERENCES

• 1: James M. Abello , Jeffrey Scott Vitter, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 2: Lars Arge , Peter Bro Miltersen, On showing lower bounds for external-memory computational geometry problems, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 3: Tetsuo Asano , Desh Ranjan , Thomas Roos , Emo Welzl , Peter Widmayer, Space Filling Curves and Their Use in the Design of Geometric Data Structures, Proceedings of the Second Latin American Symposium on Theoretical Informatics, p.36-48, April 03-07, 1995
• 4: C. L. Bajaj , V. Pascucci , D. Thompson , X. Y. Zhang, Parallel accelerated isocontouring for out-of-core visualization, Proceedings of the 1999 IEEE symposium on Parallel visualization and graphics, p.97-104, October 25-26, 1999, San Francisco, California, United States [doi>10.1145/328712.319342]
• 5: Balmelli, L., Kovačević, J., and Vetterli, M., Quadtree for embedded surface visualization: Constraints and efficient data structures. In IEEE International Conference on Image Processing (ICIP), Kobe Japan, October 1999.
• 6: Balmelli, L., Kovačević, J., and Vetterli, M., Solving the coplanarity problem of regular embedded triangulations. In Proceedings of the Workshop on Vision, Modeling and Visualization, November 1999.
• 7: Bandou, Y., and Kamata, S.I., An address generator for a 3-dimensional pseudo-hilbert scan in a cuboid region. In International Conference on Image Processing, ICIP99, volume I, 1999.
• 8: Bandou, Y., and Kamata, S.I., An address generator for an n-dimensional pseudo-hilbert scan in a hyper-rectangular parallelepiped region. In International Conference on Image Processing, ICIP 2000, 2000. to appear.
• 9: Siddhartha Chatterjee , Alvin R. Lebeck , Praveen K. Patnala , Mithuna Thottethodi, Recursive array layouts and fast parallel matrix multiplication, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.222-231, June 27-30, 1999, Saint Malo, France [doi>10.1145/305619.305645]
• 10: Yi-Jen Chiang , Cláudio T. Silva, I/O optimal isosurface extraction (extended abstract), Proceedings of the 8th conference on Visualization '97, p.293-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 11: Mark Duchaineau , Murray Wolinsky , David E. Sigeti , Mark C. Miller , Charles Aldrich , Mark B. Mineev-Weinstein, ROAMing terrain: real-time optimally adapting meshes, Proceedings of the 8th conference on Visualization '97, p.81-88, October 18-24, 1997, Phoenix, Arizona, United States
• 12: Jeremy D. Frens , David S. Wise, Auto-blocking matrix-multiplication or tracking BLAS3 performance from source code, ACM SIGPLAN Notices, v.32 n.7, p.206-216, July 1997
• 13: Goodrich, M.T., Tsay, J.J., Vengroff, D.E., and Vitter, J.S., External-memory computational geometry. In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS '93), Palo Alto, CA, November 1993.
• 14: Michael Griebel , Gerhard Zumbusch, Parallel multigrid in an adaptive PDE solver based on hashing and space-filling curves, Parallel Computing, v.25 n.7, p.827-843, July 1999 [doi>10.1016/S0167-8191(99)00020-4]
• 15: Hilbert, D., Über die stetige abbildung einer linie auf ein flachenstück. Mathematische Annalen, 38:459-460, 1891.
• 16: S. Kamata , Y. Bandoh, An address generator of a pseudo-Hilbert scan in a rectangle region, Proceedings of the 1997 International Conference on Image Processing (ICIP '97) 3-Volume Set-Volume 1, p.707, October 26-29, 1997
• 17: Lawder, J.K., The Application of Space-filling Curves to the Storage and Retrieval of Multi-Dimensional Data. PhD thesis, School of Computer Science and Information Systems, Birkbeck College, University of London, 2000.
• 18: Jonathan K. Lawder , Peter J. H. King, Using Space-Filling Curves for Multi-dimensional Indexing, Proceedings of the 17th British National Conferenc on Databases: Advances in Databases, p.20-35, July 03-05, 2000
• 19: Peter Lindstrom , David Koller , William Ribarsky , Larry F. Hodges , Nick Faust , Gregory A. Turner, Real-time, continuous level of detail rendering of height fields, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.109-118, August 1996 [doi>10.1145/237170.237217]
• 20: Yossi Matias , Eran Segal , Jeffrey Scott Vitter, Efficient bundle sorting, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.839-848, January 09-11, 2000, San Francisco, California, United States
• 21: Mirin, A., Performance of large-scale scientific applications on the IBM ASCI blue-pacific system. In Ninth SIAM Conf. of Parallel Processing for Scientific Computing, Philadelphia, Mar 1999. SIAM. CD-ROM.
• 22: Niedermeier, R., Reinhardt, K., and Sanders, P., Towards optimal locality in meshindexings, 1997.
• 23: Niedermeier, R., and Sanders, P., On the manhattandistance between points on space-filling mesh-indexings. Technical Report iratr-1996-18, Universität Karlsruhe, Informatik für Ingenieure und Naturwissenschaftler, 1996.
• 24: Manish Parashar , James C. Browne , Carter Edwards , Kenneth Klimkowski, A common data management infrastructure for adaptive algorithms for PDE solutions, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-22, November 15-21, 1997, San Jose, CA [doi>10.1145/509593.509649]
• 25: Pascucci, V., and Frank, R.J., Hierarchical indexing for out-of-core access to multi-resolution data. Technical Report UCRL-JC-140581, Lawrence Livermore National Laboratory, 2001. A preliminary version was presented at the Lake Tahoe Workshop NSF/DOE Lake Tahoe Workshop on Hierarchical Approximation and Geometrical Methods for Scientific Visualization.
• 26: Rivara, M.C., Algorithms for refining triangular grids suitable for adaptive and multigrid techniques. International Journal for Numerical Methods in Engineering, 20:745-756, 1984.
• 27: Sagan, H., Space-Filling Curves. Springer-Verlag, New York, NY, 1994.
• 28: Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 29: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
• 30: David S. Wise, Ahnentafel Indexing into Morton-Ordered Arrays, or Matrix Locality for Free, Proceedings from the 6th International Euro-Par Conference on Parallel Processing, p.774-783, August 29-September 01, 2000

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

General Terms:
Design, Experimentation, Performance