Presentation
STREAM: Spatiotemporal Similarity-based Efficient Approximate Median with Tunable Granularity
DescriptionThe median (MED) is a crucial statistic for measuring the central tendency. However, exact MED computation remains costly, with even state-of-the-art (SOTA) algorithms failing to meet (near) real-time processing demands. While approximate MED algorithm has arisen as a promising candidate, existing approaches ignore the potential opportunity of spatiotemporal similarity within the application and fail to provide application-specific trade-offs between execution time and accuracy. Our goal is to design an enhanced approximate MED algorithm STREAM, which is capable of exploiting the spatiotemporal similarity to achieve bucket reuse and establish a tunable-grained bucket mechanism to meet the accuracy of application-specific requirements. Experimental results show that while maintaining nearly identical accuracy, STREAM outperforms the SOTA approximate methods DDSketch (up to 10x, 4.7x on average) and KLL (up to 71.2x, 10.1x on average).
Event Type
Research Manuscript
TimeTuesday, June 244:45pm - 5:00pm PDT
Location3008, Level 3
SYS3: Embedded Software