%ANakandala, Supun%AKumar, Arun%APapakonstantinou, Yannis%Anull Ed.%BJournal Name: ACM SIGMOD Record; Journal Volume: 49; Journal Issue: 1 %D2020%I %JJournal Name: ACM SIGMOD Record; Journal Volume: 49; Journal Issue: 1 %K %MOSTI ID: 10279996 %PMedium: X %TQuery Optimization for Faster Deep CNN Explanations %XDeep Convolutional Neural Networks (CNNs) now match human accuracy in many image prediction tasks, resulting in a growing adoption in e-commerce, radiology, and other domains. Naturally, "explaining" CNN predictions is a key concern for many users. Since the internal workings of CNNs are unintuitive for most users, occlusion-based explanations (OBE) are popular for understanding which parts of an image matter most for a prediction. One occludes a region of the image using a patch and moves it around to produce a heatmap of changes to the prediction probability. This approach is computationally expensive due to the large number of re-inference requests produced, which wastes time and raises resource costs. We tackle this issue by casting the OBE task as a new instance of the classical incremental view maintenance problem. We create a novel and comprehensive algebraic framework for incremental CNN inference combining materialized views with multi-query optimization to reduce computational costs. We then present two novel approximate inference optimizations that exploit the semantics of CNNs and the OBE task to further reduce runtimes. We prototype our ideas in a tool we call Krypton. Experiments with real data and CNNs show that Krypton reduces runtimes by up to 5x (resp. 35x) to produce exact (resp. high-quality approximate) results without raising resource requirements. %0Journal Article