IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v33y2021i4p1339-1353.html
   My bibliography  Save this article

Near-Linear Time Local Polynomial Nonparametric Estimation with Box Kernels

Author

Listed:
  • Yining Wang

    (Warrington College of Business, University of Florida, Gainesville, Florida 32611)

  • Yi Wu

    (Institute of Interdisciplinary Information Sciences, Tsinghua University, Beijing, 100084, China; Shanghai Qi Zhi Institute, Xuhui District, Shanghai, 200232, China)

  • Simon S. Du

    (Paul G. Allen School of Computer Science and Engineering, University of Washington, Seattle, Washington 98195)

Abstract

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.

Suggested Citation

  • Yining Wang & Yi Wu & Simon S. Du, 2021. "Near-Linear Time Local Polynomial Nonparametric Estimation with Box Kernels," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1339-1353, October.
    • Handle: RePEc:inm:orijoc:v:33:y:2021:i:4:p:1339-1353
    DOI: 10.1287/ijoc.2020.1021
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2020.1021
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ijoc.2020.1021?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Matias D. Cattaneo & Michael Jansson & Xinwei Ma, 2020. "Simple Local Polynomial Density Estimators," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 115(531), pages 1449-1455, July.
    2. Benjamin T. Hazen & Joseph B. Skipper & Christopher A. Boone & Raymond R. Hill, 2018. "Back in business: operations research in support of big data analytics for operations and supply chain management," Annals of Operations Research, Springer, vol. 270(1), pages 201-211, November.
    3. Tsan‐Ming Choi & Stein W. Wallace & Yulan Wang, 2018. "Big Data Analytics in Operations Management," Production and Operations Management, Production and Operations Management Society, vol. 27(10), pages 1868-1883, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Raeesi, Ramin & Sahebjamnia, Navid & Mansouri, S. Afshin, 2023. "The synergistic effect of operational research and big data analytics in greening container terminal operations: A review and future directions," European Journal of Operational Research, Elsevier, vol. 310(3), pages 943-973.
    2. Vaibhav S. Narwane & Rakesh D. Raut & Sachin Kumar Mangla & Manoj Dora & Balkrishna E. Narkhede, 2023. "Risks to Big Data Analytics and Blockchain Technology Adoption in Supply Chains," Annals of Operations Research, Springer, vol. 327(1), pages 339-374, August.
    3. Erkip, Nesim Kohen, 2023. "Can accessing much data reshape the theory? Inventory theory under the challenge of data-driven systems," European Journal of Operational Research, Elsevier, vol. 308(3), pages 949-959.
    4. Francesco Decarolis & Raymond Fisman & Paolo Pinotti & Silvia Vannutelli, 2019. "Rules, Discretion, and Corruption in Procurement: Evidence from Italian Government Contracting," Boston University - Department of Economics - The Institute for Economic Development Working Papers Series dp-344, Boston University - Department of Economics.
    5. Albanese, Andrea & Picchio, Matteo & Ghirelli, Corinna, 2020. "Timed to Say Goodbye: Does Unemployment Benefit Eligibility Affect Worker Layoffs?," Labour Economics, Elsevier, vol. 65(C).
    6. Zhang, Abraham & Wang, Jason X. & Farooque, Muhammad & Wang, Yulan & Choi, Tsan-Ming, 2021. "Multi-dimensional circular supply chain management: A comparative review of the state-of-the-art practices and research," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 155(C).
    7. Suyuan Luo & Tsan‐Ming Choi, 2022. "E‐commerce supply chains with considerations of cyber‐security: Should governments play a role?," Production and Operations Management, Production and Operations Management Society, vol. 31(5), pages 2107-2126, May.
    8. Srinivas, Sharan & Ramachandiran, Surya & Rajendran, Suchithra, 2022. "Autonomous robot-driven deliveries: A review of recent developments and future directions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).
    9. Guida Ayza Estopa, 2024. "Return-to-work policies for disability insurance recipients: The role of financial incentives," French Stata Users' Group Meetings 2024 17, Stata Users Group.
    10. Gonzalez-Eiras, Martín & Sanz, Carlos, 2021. "Women’s representation in politics: The effect of electoral systems," Journal of Public Economics, Elsevier, vol. 198(C).
    11. repec:irs:cepswp:2024-01 is not listed on IDEAS
    12. Gurgand, Marc & Lorenceau, Adrien & Mélonio, Thomas, 2023. "Student loans: Credit constraints and higher education in South Africa," Journal of Development Economics, Elsevier, vol. 161(C).
    13. Harkaran Kava & Konstantina Spanaki & Thanos Papadopoulos & Stella Despoudi & Oscar Rodriguez-Espindola & Masoud Fakhimi, 2021. "Data Analytics Diffusion in the UK Renewable Energy Sector: An Innovation Perspective," Post-Print hal-03781046, HAL.
    14. Guangmei Cao & Yuesen Wang & Honghu Gao & Hao Liu & Haibin Liu & Zhigang Song & Yuqing Fan, 2023. "Coordination Decision-Making for Intelligent Transformation of Logistics Services under Capital Constraint," Sustainability, MDPI, vol. 15(6), pages 1-25, March.
    15. Graham Elliott & Nikolay Kudrin & Kaspar Wüthrich, 2022. "Detecting p‐Hacking," Econometrica, Econometric Society, vol. 90(2), pages 887-906, March.
    16. Jason R. W. Merrick & Claire A. Dorsey & Bo Wang & Martha Grabowski & John R. Harrald, 2022. "Measuring Prediction Accuracy in a Maritime Accident Warning System," Production and Operations Management, Production and Operations Management Society, vol. 31(2), pages 819-827, February.
    17. Havinga, Maik J.A. & de Jonge, Bram, 2020. "Condition-based maintenance in the cyclic patrolling repairman problem," International Journal of Production Economics, Elsevier, vol. 222(C).
    18. De Benedetto, Marco Alberto & De Paola, Maria & Scoppa, Vincenzo & Smirnova, Janna, 2023. "Erasmus Program and Labor Market Outcomes: Evidence from a Fuzzy Regression Discontinuity Design," IZA Discussion Papers 16181, Institute of Labor Economics (IZA).
    19. Isabelle Chort & Maëlys de la Rupelle, 2022. "Managing the impact of climate on migration: evidence from Mexico," Journal of Population Economics, Springer;European Society for Population Economics, vol. 35(4), pages 1777-1819, October.
    20. Albanese, Andrea & Cockx, Bart & Dejemeppe, Muriel, 2024. "Long-term effects of hiring subsidies for low-educated unemployed youths," Journal of Public Economics, Elsevier, vol. 235(C).
    21. Brasington, David M. & Parent, Olivier, 2024. "Fire protection services and house prices: A regression discontinuity investigation," Regional Science and Urban Economics, Elsevier, vol. 105(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:33:y:2021:i:4:p:1339-1353. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.