IDEAS home Printed from https://ideas.repec.org/a/spr/compst/v39y2024i7d10.1007_s00180-023-01381-1.html
   My bibliography  Save this article

Order statistics in large arrays (OSILA): a simple randomised algorithm for a fast and efficient attainment of the order statistics in very large arrays

Author

Listed:
  • Andrea Cerasa

    (European Commission, Joint Research Centre)

Abstract

When dealing with large-scale applications, the availability of simple and efficient algorithms is essential. We focus on the algorithm for calculating the order statistics, i.e. for selecting the kth smallest element of an array X. Many statistical procedures rely on this basic operation, that is usually solved by sorting all the elements and selecting the one in position k. If the dimension of the array to sort is quite large, this simple operation can become excessively time consuming. For this purpose, we propose an original randomised algorithm that reduces the dimension of the selection problem by focusing only on a small subset of elements that contains the solution. Despite its random nature, it always returns the target value. Empirical results shows that, for arrays of dimensions running from $$10^5$$ 10 5 to $$10^8$$ 10 8 , our procedure resulted to be remarkably (up to almost 10 times) faster than the naïve procedure, independently of the programming environment and of the sorting algorithm, and with a relative advantage that tends to growth with the dimension of the array.

Suggested Citation

  • Andrea Cerasa, 2024. "Order statistics in large arrays (OSILA): a simple randomised algorithm for a fast and efficient attainment of the order statistics in very large arrays," Computational Statistics, Springer, vol. 39(7), pages 3599-3624, December.
    • Handle: RePEc:spr:compst:v:39:y:2024:i:7:d:10.1007_s00180-023-01381-1
    DOI: 10.1007/s00180-023-01381-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00180-023-01381-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00180-023-01381-1?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Fried, Roland & Einbeck, Jochen & Gather, Ursula, 2007. "Weighted Repeated Median Smoothing and Filtering," Journal of the American Statistical Association, American Statistical Association, vol. 102, pages 1300-1308, December.
    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. Jean‐Christophe Delfim & Martin Hoesli, 2021. "Robust desmoothed real estate returns," Real Estate Economics, American Real Estate and Urban Economics Association, vol. 49(1), pages 75-105, March.
    2. Croux, C. & Fried, R. & Gijbels, I. & Mahieu, K., 2010. "Robust Forecasting of Non-Stationary Time Series," Discussion Paper 2010-105, Tilburg University, Center for Economic Research.
    3. Croux, C. & Fried, R. & Gijbels, I. & Mahieu, K., 2010. "Robust Forecasting of Non-Stationary Time Series," Other publications TiSEM 94542b5e-4319-4f5a-bc35-2, Tilburg University, School of Economics and Management.
    4. Dehling, Herold & Fried, Roland, 2012. "Asymptotic distribution of two-sample empirical U-quantiles with applications to robust tests for shifts in location," Journal of Multivariate Analysis, Elsevier, vol. 105(1), pages 124-140.
    5. Walter Krämer, 2015. "Interview mit Ursula Gather," AStA Wirtschafts- und Sozialstatistisches Archiv, Springer;Deutsche Statistische Gesellschaft - German Statistical Society, vol. 9(2), pages 159-166, November.
    6. Najla M. Qarmalah & Jochen Einbeck & Frank P. A. Coolen, 2018. "k-Boxplots for mixture data," Statistical Papers, Springer, vol. 59(2), pages 513-528, June.

    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:spr:compst:v:39:y:2024:i:7:d:10.1007_s00180-023-01381-1. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.