Running Median Algorithm and Implementation for Integer Streaming Applications
Cadenas, O and Megson, GM (2018). Running Median Algorithm and Implementation for Integer Streaming Applications. IEEE Embedded Systems Letters.
|Authors||Cadenas, O and Megson, GM|
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.
|Journal||IEEE Embedded Systems Letters|
|Publisher||Institute of Electrical and Electronics Engineers|
|Digital Object Identifier (DOI)||doi:10.1109/LES.2018.2868409|
|Publication process dates|
|Deposited||30 Aug 2018|
|Accepted||24 Aug 2018|
|Accepted author manuscript|
CC BY 4.0
0views this month
3downloads this month