Running Median Algorithm and Implementation for Integer Streaming Applications

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 implementa...

Full description

Saved in:
Bibliographic Details
Published in:IEEE embedded systems letters 2019-06, Vol.11 (2), p.58-61
Main Authors: Cadenas, Oswaldo, Megson, Graham M.
Format: Article
Language:English
Subjects:
Acceleration
Algorithms
Arrays
Data structures
Data transmission
Embedded processors
Embedded systems
Integers
median
median filter
Microsoft Windows
Program processors
running median
Sorting
streaming algorithms
Windows
Windows (intervals)
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1943-0663
1943-0671
DOI:10.1109/LES.2018.2868409