Accelerated Force Computation for Physics-Based Information Visualization

Abstract

Visualization of similarity is an emerging technique for analyzing relation-based data sets. A common way of computing the respective layouts in an information space is to employ a physics-based mass-spring system. Force computation, however, is costly and of order N2. In this paper, we propose a new acceleration method to adopt a well-known optimized force-computation algorithm which drastically reduces the computation time to the order of N log N. The basic idea is to derive a two-pass, "prediction and correction" procedure including a customized potential function. We have applied this method to two different applications: web access and sales analysis. Both demonstrate the efficiency and versatility of the presented method.