Compression of particle data from hierarchical approximate methods Academic Article uri icon


  • This article presents an analytical and computational framework for the compression of particle data resulting from hierarchical approximate treecodes such as the Barnes--Hut and Fast Multipole Methods . Due to approximations introduced by hierarchical methods, various parameters (such as position, velocity, acceleration, potential) associated with a particle can be bounded by distortion radii. Using this distortion radii, we develop storage schemes that guarantee error bounds while maximizing compression. Our schemes make extensive use of spatial and temporal coherence of particle behavior and yield compression ratios higher than 12:1 over raw data, and 6:1 over gzipped (LZ) raw data for selected simulation instances. We demonstrate that for uniform distributions with 2M particles, storage requirements can be reduced from 24 MB to about 1.8 MB (about 7 bits per particle per timestep) for storing particle positions. This is significant because it enables faster storage/retrieval, better temporal resolution, and improved analysis. Our results are shown to scale from small systems (2K particles) to much larger systems (over 2M particles). The associated algorithm is asymptotically optimal in computation time ( O ( n )) with a small constant. Our implementations are demonstrated to run extremely fast---much faster than the time it takes to compute a single time-step advance. In addition, our compression framework relies on a natural hierarchical representation upon which other analysis tasks such as segmented and window retrieval can be built.

published proceedings


altmetric score

  • 3

author list (cited authors)

  • Yang, D. Y., Grama, A., Sarin, V., & Ramakrishnan, K.

citation count

  • 1

complete list of authors

  • Yang, DY||Grama, A||Sarin, V||Ramakrishnan, K

publication date

  • January 2001