We present a parallel k-Means clustering algorithm specifically designed to address large datasets and cluster counts. Our approach, BSP (binary space partitioning) k-Means, recursively partitions the input space optimally across the first principal component of the current subset of the data. From a single space partitioning, clusterings with arbitrary ?? can be found by a greedy tree search. Combining a reduction onto the first principal component and optimal binary clustering of 1D data is highly effective at reducing clustering costs. We attribute this to the close relationship between directional variance and the within-cluster sum of squares. We analyze our approach theoretically and, under an idealized population model, prove that the runtime is in O(n . max(d, lnn) · lnn) for a broad class of input distributions with high probability. We demonstrate that our algorithm consistently outperforms k-Means++ and performs similarly or better than other sophisticated algorithms in an evaluation with nine datasets and up to six cluster sizes. Our algorithm is parallelizable using common database operations such as Scan, Reduce, and Sort. We show that with our CUDA implementation, a significant speedup can be achieved. Additionally, our algorithm generates centers and datapoint assignments alike, removing the expensive cluster assignment step after initial seeding. Furthermore, our algorithm approximates k-Means accurately so that any additional use of Lloyd’s algorithm is optional and yields only incremental improvement.

The computation of a potentially visible set (PVS) can accelerate many computer graphics algorithms, such as framerate upsampling, streaming rendering, global illumination, and multi-fragment effects. Algorithms for from-region PVS have an inherently high complexity. Previous from-region PVS algorithms propagate occlusion through the scene in a front-to-back manner and are order-dependent, which places bounds on parallelism and restricts execution speed. We introduce the disocclusion buffer, which operates on a sparse, layered representation of the scene with quantized depth. In this representation, we invert the traditional PVS problem formulation and explicitly compute disocclusion rather than occlusion. Disocclusion can be computed in parallel in an order-independent manner, overcoming the main bottleneck in traditional PVS computation. Our PVS algorithm is over six times faster than the previous state of the art at the same level of accuracy in a direct comparison. It runs in shaders on the GPU without requiring any hardware extensions. We demonstrate how our work outperforms previous PVS algorithms in the range of supported camera motion without compromising quality.

Semi-Lagrangian texture advection (SLTA) enables efficient visualization of 2D and 3D unsteady flow. The major drawback of SLTA-based visualizations is numerical diffusion caused by iterative texture interpolation. We focus on reducing numerical diffusion in techniques that use textures sparsely populated by solid blobs, such as typically in dye advection. A ReLU-based model architecture is the foundation of our ML-based approach. Multiple model configurations are trained to learn a performant interpolation model that reduces numerical diffusion. Our evaluation investigates the models’ ability to generalize concerning the flow and length of the advection process. The model with the best tradeoff between the computational effort to compute, quality of the result, and generality of application is found to be single-layer ReLU-based. This model is further analyzed and explained in-depth and improved using symmetry constraints. Additionally, a metamodel is fitted to predict single-layer ReLU model parameters for advection processes of any length. The metamodel removes the need for any prior training when applying our technique to a new scenario. Additionally, we show that our model is compatible with Back and Forth Error Compensation and Correction to improve the quality of the advection result further. We demonstrate that our model shows excellent diffusion reduction properties in typical examples of 3D steady and unsteady flow visualization. Finally, we utilize the strong diffusion reduction capabilities of our model to compute dye advection with exponential decay, a novel method that we introduce to visualize the extent and evolution of unsteadiness in both 2D and 3D unsteady flow. • ML-based ReLU model for dye advection. • A thorough evaluation of the core ML part and the overall flow visualization technique. • A decay effect with dye streaklines to visualize unsteadiness in flow data. • Pretrained metamodels for direct deployment of our approach.

Scene-graph-based Visual Question Answering (VQA) has emerged as a burgeoning field in Deep Learning research, with a growing demand for robust and interpretable VQA systems. In this paper, we present a novel visual analysis approach that addresses two critical objectives in VQA: identifying and correcting prediction issues and providing insights into model decision-making processes through visualizing internal information. Our approach builds on the GraphVQA framework, which uses graph neural networks to process scene graphs representing images and which was trained on the widely-used GQA dataset. Our analysis tool aims at users familiar with the basics of graph-based VQA. By leveraging query-based scene analysis and visualization of crucial internal states, we are able to detect and pinpoint reasons for inaccurate predictions, facilitating model refinement and dataset curation. Identifying expressive internal states is a challenge. Through rigorous computer-based evaluations and presentation of a use case, we demonstrate the effectiveness of our analysis tool and model state visualization.