Running Median Algorithm and Implementation for Integer Streaming Applications

Oswaldo Cadenas; Graham M. Megson

doi:10.1109/LES.2018.2868409

Running Median Algorithm and Implementation for Integer Streaming Applications

Oswaldo Cadenas, Graham M. Megson

University of Westminster

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Article number	8453865
Pages (from-to)	58-61
Number of pages	4
Journal	IEEE Embedded Systems Letters
Volume	11
Issue number	2
DOIs	https://doi.org/10.1109/LES.2018.2868409 https://doi.org/10.1109/LES.2018.2868409
Publication status	Published - 3 Sept 2018

Bibliographical note

Publisher Copyright:
© 2018 IEEE.

Keywords

Embedded processors
median
median filter
running median
streaming algorithms

Access to Document

Cite this

@article{4e7cc1656dcb42bba3c34552138405e2,

title = "Running Median Algorithm and Implementation for Integer Streaming Applications",

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.",

keywords = "Embedded processors, median, median filter, running median, streaming algorithms",

author = "Oswaldo Cadenas and Megson, {Graham M.}",

note = "Publisher Copyright: {\textcopyright} 2018 IEEE.",

year = "2018",

month = sep,

day = "3",

doi = "10.1109/LES.2018.2868409",

language = "English",

volume = "11",

pages = "58--61",

number = "2",

}

TY - JOUR

T1 - Running Median Algorithm and Implementation for Integer Streaming Applications

AU - Cadenas, Oswaldo

AU - Megson, Graham M.

PY - 2018/9/3

Y1 - 2018/9/3

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

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

KW - Embedded processors

KW - median

KW - median filter

KW - running median

KW - streaming algorithms

UR - http://www.scopus.com/inward/record.url?scp=85052816037&partnerID=8YFLogxK

U2 - 10.1109/LES.2018.2868409

DO - 10.1109/LES.2018.2868409

M3 - Article

SN - 1943-0663

VL - 11

SP - 58

EP - 61

JO - IEEE Embedded Systems Letters

JF - IEEE Embedded Systems Letters

IS - 2

M1 - 8453865

ER -

Running Median Algorithm and Implementation for Integer Streaming Applications

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this