The adaptable buffer algorithm for high quantile estimation in non-stationary data streams
The need to estimate a particular quantile of a distribution is an important problem which frequently arises in many computer vision and signal processing applications. For example, our work was motivated by the requirements of many semi-automatic surveillance analytics systems which detect abnormal...
| Main Authors: | , , |
|---|---|
| Format: | Conference Paper |
| Published: |
2015
|
| Online Access: | http://hdl.handle.net/20.500.11937/15134 |
| _version_ | 1848748811752570880 |
|---|---|
| author | Arandjelovic, O. Pham, DucSon Venkatesh, S. |
| author_facet | Arandjelovic, O. Pham, DucSon Venkatesh, S. |
| author_sort | Arandjelovic, O. |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | The need to estimate a particular quantile of a distribution is an important problem which frequently arises in many computer vision and signal processing applications. For example, our work was motivated by the requirements of many semi-automatic surveillance analytics systems which detect abnormalities in close-circuit television (CCTV) footage using statistical models of low-level motion features. In this paper we specifically address the problem of estimating the running quantile of a data stream with non-stationary stochasticity when the memory for storing observations is limited. We make several major contributions: (i) we derive an important theoretical result which shows that the change in the quantile of a stream is constrained regardless of the stochastic properties of data, (ii) we describe a set of high-level design goals for an effective estimation algorithm that emerge as a consequence of our theoretical findings, (iii) we introduce a novel algorithm which implements the aforementioned design goals by retaining a sample of data values in a manner adaptive to changes in the distribution of data and progressively narrowing down its focus in the periods of quasi-stationary stochasticity, and (iv) we present a comprehensive evaluation of the proposed algorithm and compare it with the existing methods in the literature on both synthetic data sets and three large 'real-world' streams acquired in the course of operation of an existing commercial surveillance system. Our findings convincingly demonstrate that the proposed method is highly successful and vastly outperforms the existing alternatives, especially when the target quantile is high valued and the available buffer capacity severely limited. |
| first_indexed | 2025-11-14T07:10:59Z |
| format | Conference Paper |
| id | curtin-20.500.11937-15134 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T07:10:59Z |
| publishDate | 2015 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-151342018-03-29T09:07:21Z The adaptable buffer algorithm for high quantile estimation in non-stationary data streams Arandjelovic, O. Pham, DucSon Venkatesh, S. The need to estimate a particular quantile of a distribution is an important problem which frequently arises in many computer vision and signal processing applications. For example, our work was motivated by the requirements of many semi-automatic surveillance analytics systems which detect abnormalities in close-circuit television (CCTV) footage using statistical models of low-level motion features. In this paper we specifically address the problem of estimating the running quantile of a data stream with non-stationary stochasticity when the memory for storing observations is limited. We make several major contributions: (i) we derive an important theoretical result which shows that the change in the quantile of a stream is constrained regardless of the stochastic properties of data, (ii) we describe a set of high-level design goals for an effective estimation algorithm that emerge as a consequence of our theoretical findings, (iii) we introduce a novel algorithm which implements the aforementioned design goals by retaining a sample of data values in a manner adaptive to changes in the distribution of data and progressively narrowing down its focus in the periods of quasi-stationary stochasticity, and (iv) we present a comprehensive evaluation of the proposed algorithm and compare it with the existing methods in the literature on both synthetic data sets and three large 'real-world' streams acquired in the course of operation of an existing commercial surveillance system. Our findings convincingly demonstrate that the proposed method is highly successful and vastly outperforms the existing alternatives, especially when the target quantile is high valued and the available buffer capacity severely limited. 2015 Conference Paper http://hdl.handle.net/20.500.11937/15134 10.1109/IJCNN.2015.7280314 restricted |
| spellingShingle | Arandjelovic, O. Pham, DucSon Venkatesh, S. The adaptable buffer algorithm for high quantile estimation in non-stationary data streams |
| title | The adaptable buffer algorithm for high quantile estimation in non-stationary data streams |
| title_full | The adaptable buffer algorithm for high quantile estimation in non-stationary data streams |
| title_fullStr | The adaptable buffer algorithm for high quantile estimation in non-stationary data streams |
| title_full_unstemmed | The adaptable buffer algorithm for high quantile estimation in non-stationary data streams |
| title_short | The adaptable buffer algorithm for high quantile estimation in non-stationary data streams |
| title_sort | adaptable buffer algorithm for high quantile estimation in non-stationary data streams |
| url | http://hdl.handle.net/20.500.11937/15134 |