학술논문
Running Median Algorithm and Implementation for Integer Streaming Applications
Document Type
Periodical
Author
Source
IEEE Embedded Systems Letters IEEE Embedded Syst. Lett. Embedded Systems Letters, IEEE. 11(2):58-61 Jun, 2019
Subject
Language
ISSN
1943-0663
1943-0671
1943-0671
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.