Running Median Algorithm and Implementation for Integer Streaming Applications

Journal article

Cadenas, O and Megson, GM (2018). Running Median Algorithm and Implementation for Integer Streaming Applications. IEEE Embedded Systems Letters. 11 (2), pp. 58-61. https://doi.org/10.1109/LES.2018.2868409
AuthorsCadenas, O and Megson, GM
Abstract

A novel algorithm is proposed to compute the median of a running window of m integers in O(lg lg m) time. For a new window, the new median value is computed as a simple decision based on the previous median and the values removed and inserted into the window. This facilitates implementations based on data structures that support fast ordinal predecessor/successor operations. The results show accelerations of up to factors of six for integer data streaming in typical embedded processors.

Year2018
JournalIEEE Embedded Systems Letters
Journal citation11 (2), pp. 58-61
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
ISSN1943-0663
Digital Object Identifier (DOI)https://doi.org/10.1109/LES.2018.2868409
Web address (URL)https://ieeexplore.ieee.org/document/8453865
Publication dates
Print03 Sep 2018
Publication process dates
Deposited30 Aug 2018
Accepted24 Aug 2018
Accepted author manuscript
License
File Access Level
Open
Additional information

© 2018 IEEE Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

Page range1-4
Permalink -

https://openresearch.lsbu.ac.uk/item/869qw

Download files

Accepted author manuscript
StreamingMedian-Acceptedversion.pdf
License: CC BY 4.0
File access level: Open

  • 107
    total views
  • 843
    total downloads
  • 0
    views this month
  • 10
    downloads this month

Export as

Related outputs

Preprocessing 2D data for fast convex hull computations
Cadenas, O and Megson, GM (2019). Preprocessing 2D data for fast convex hull computations. PLoS ONE. 14 (2), p. e0212189. https://doi.org/10.1371/journal.pone.0212189
KurSL: Model of anharmonic coupled oscillations based on Kuramoto coupling and Sturm-Liouville problem
Cadenas, O, Laszuk, D and Slawomir, N (2018). KurSL: Model of anharmonic coupled oscillations based on Kuramoto coupling and Sturm-Liouville problem. Advances in Data Science and Adaptive Analysis. 10 (02). https://doi.org/10.1142/S2424922X18400028
Rapid preconditioning of data for accelerating convex hull algorithms
Cadenas, O and Megson, G (2014). Rapid preconditioning of data for accelerating convex hull algorithms. Electronics Letters. 50 (4), pp. 270-272. https://doi.org/10.1049/el.2013.3507
Virtualization for cost-effective teaching of assembly language
Cadenas, O, Sherratt, S, Howlett, D, Guy, C and Lundqvist, K (2015). Virtualization for cost-effective teaching of assembly language. IEEE Transactions on Education. 58 (4), pp. 282-288. https://doi.org/10.1109/TE.2015.2405895
Median architecture by accumulative parallel counters
Cadenas, O, Megson, G and Sherratt, S (2015). Median architecture by accumulative parallel counters. IEEE Transactions on Circuits and Systems II: Express Briefs. 62 (7), pp. 661-665. https://doi.org/10.1109/TCSII.2015.2415655
Pipelined median architecture
Cadenas, O (2015). Pipelined median architecture. Electronics Letters. 51 (24), pp. 1999-2001. https://doi.org/10.1049/el.2015.1898
Preconditioning 2D integer data for fast convex hull computations
Cadenas, O, Megson, G.M. and Luengo Hendriks, C.L. (2016). Preconditioning 2D integer data for fast convex hull computations. PLoS ONE. 11 (3). https://doi.org/10.1371/journal.pone.0149860
EMD performance comparison: single vs double floating points
Laszuk, D, Cadenas, O. and Nasuto, J (2016). EMD performance comparison: single vs double floating points. International journal of signal processing systems. 4 (4), pp. 349-353. https://doi.org/10.18178/ijsps.4.4.349-353
On the Phase Coupling of Two Components Mixing in Empirical Mode Decomposition
Laszuk, D, Cadenas, O. and Nasuto, Slawomir J. (2016). On the Phase Coupling of Two Components Mixing in Empirical Mode Decomposition. Advances in Data Science and Adaptive Analysis. 8 (1). https://doi.org/10.1142/S2424922X16500042