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. 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.
    3. 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.
    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. Eibich, Peter & Siedler, Thomas, 2020. "Retirement, intergenerational time transfers, and fertility," European Economic Review, Elsevier, vol. 124(C).
    6. Luis R. Martinez & Jonas Jessen & Guo Xu, 2023. "A Glimpse of Freedom: Allied Occupation and Political Resistance in East Germany," American Economic Journal: Applied Economics, American Economic Association, vol. 15(1), pages 68-106, January.
    7. Liu, Weihua & George Shanthikumar, J. & Tae-Woo Lee, Paul & Li, Xiang & Zhou, Li, 2021. "Special issue editorial: Smart supply chains and intelligent logistics services," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 147(C).
    8. S. Di Luozzo & A. Fronzetti Colladon & M. M. Schiraldi, 2024. "Decoding excellence: Mapping the demand for psychological traits of operations and supply chain professionals through text mining," Papers 2403.17546, arXiv.org.
    9. Annika Lindskog & Dick Durevall, 2021. "To educate a woman and to educate a man: Gender‐specific sexual behavior and human immunodeficiency virus responses to an education reform in Botswana," Health Economics, John Wiley & Sons, Ltd., vol. 30(3), pages 642-658, March.
    10. Albanese, Andrea & Picchio, Matteo & Ghirelli, Corinna, 2020. "Timed to Say Goodbye: Does Unemployment Benefit Eligibility Affect Worker Layoffs?," Labour Economics, Elsevier, vol. 65(C).
    11. Canaan, Serena & Mouganie, Pierre & Zhang, Peng, 2022. "The Long-Run Educational Benefits of High-Achieving Classrooms," IZA Discussion Papers 15039, Institute of Labor Economics (IZA).
    12. Dmitry Ivanov, 2022. "Viable supply chain model: integrating agility, resilience and sustainability perspectives—lessons from and thinking beyond the COVID-19 pandemic," Annals of Operations Research, Springer, vol. 319(1), pages 1411-1431, December.
    13. Johnsen, Julian V. & Willén, Alexander, 2022. "The effect of negative income shocks on pensioners," Labour Economics, Elsevier, vol. 76(C).
    14. Abel Brodeur, Nikolai M. Cook, Anthony Heyes, 2022. "We Need to Talk about Mechanical Turk: What 22,989 Hypothesis Tests Tell Us about Publication Bias and p-Hacking in Online Experiments," LCERPA Working Papers am0133, Laurier Centre for Economic Research and Policy Analysis.
    15. 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).
    16. Bagues, Manuel & Campa, Pamela, 2021. "Can gender quotas in candidate lists empower women? Evidence from a regression discontinuity design," Journal of Public Economics, Elsevier, vol. 194(C).
    17. Lei Wang & Ram Gopal & Ramesh Shankar & Joseph Pancras, 2022. "Forecasting venue popularity on location‐based services using interpretable machine learning," Production and Operations Management, Production and Operations Management Society, vol. 31(7), pages 2773-2788, July.
    18. 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.
    19. Meltem Dayioglu & Müşerref Küçükbayrak & Semih Tumen, 2022. "The impact of age-specific minimum wages on youth employment and education: a regression discontinuity analysis," International Journal of Manpower, Emerald Group Publishing Limited, vol. 43(6), pages 1352-1377, March.
    20. 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).

    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.