Back to Search
Start Over
Near-Linear Time Local Polynomial Nonparametric Estimation with Box Kernels.
- Source :
- INFORMS Journal on Computing; 2021, Vol. 33 Issue 4, p1339-1353, 15p
- Publication Year :
- 2021
-
Abstract
- 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. Local polynomial regression is an important class of methods for nonparametric density estimation and regression problems. However, straightforward implementation of local polynomial regression has quadratic time complexity which hinders its applicability in large-scale data analysis. In this paper, we significantly accelerate the computation of local polynomial estimates by novel applications of multidimensional binary indexed trees. Both time and space complexity of our proposed algorithm is nearly linear in the number of input data points. Simulation results confirm the efficiency and effectiveness of our proposed approach. 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 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- NONPARAMETRIC estimation
POLYNOMIAL time algorithms
ALGORITHMS
LAZINESS
Subjects
Details
- Language :
- English
- ISSN :
- 10919856
- Volume :
- 33
- Issue :
- 4
- Database :
- Complementary Index
- Journal :
- INFORMS Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 153606665
- Full Text :
- https://doi.org/10.1287/ijoc.2020.1021