This project extends arithmetic using planar binary trees over adaptive multi-dimensional metric data structures called statistical regular pavings (SRPs). SRPs have been used to represent and process all civil air-traffic data of flight co-trajectories over Atlanta, Georgia, USA - one of the busiest airports in the world. SRPs, as adaptive multi-dimensional histograms, have been used for scalable Bayesian computations in non-parametric density estimation. SRPs and their generalization into mapped regular pavings allow computational statisticians to use powerful tools and rigorous techniques from interval analysis, including automatic differentiation, constraint propagation, contractor programming and set inversion. A comprehensive C++ library for statistical set processing is developed.