[2N6-GS-1] Fundamental AI, theory: Constraint satisfaction and optimization

[2N6-GS-1-05] Acceleration of ε-Approximate Quantile Summary Construction by Using Item Counters

〇Kosuke Maeda¹, Koji Iwanuma² (1. Conputer Science and Engineering Course, Integrated Graduate School of Medicine, Engineering and Agricultural Sciences, University of Yamanashi, 2. Interdisciplinary Graduate School, University of Yamanashi)

Keywords:ε-approximate quantile, counter, stream

In recent years, research on sensor networks has shown rapid progress as a means of collecting information from the real world. Along with that, the technology that integrates and compresses information from multiple sensors is also increasing its importance. The quantile is one of the typical compression methods.

In this study, we focus on Greenwald and Khanna's algorithm for constructing the ε-approximate quantile summary, and propose a new method to further increase the speed using a counter for the purpose of realizing high-speed online calculation of quantiles on stream data.