Near-Linear Time Local Polynomial Nonparametric Estimation with Box Kernels
通过多维二叉索引树和哈希惰性内存分配，大幅加速局部多项式回归估计的计算，算法时间和空间复杂度接近线性，适用于大数据环境下的经济学和运筹管理问题。
Summary of Contribution: Big data analytics has become essential for modern operations research and operations management applications. Statistics methods, such as nonparametric density and function estimation, play important roles in predictive and exploratory data analysis for economics and operations management problems. In this paper, we concentrate on efficiently computing local polynomial regression estimates. We significantly accelerate the computation of such local polynomial estimates by novel applications of multidimensional binary indexed trees ( Fenwick 1994 ) and lazy memory allocation via hashing. Both time and space complexity of our proposed algorithm are nearly linear in the number of inputs. Simulation results confirm the efficiency and effectiveness of our proposed methods.