PolyFit: Polynomial-based Indexing Approach for Fast Approximate Range Aggregate Queries

Zhe Li, Tsz Nam Chan, Man Lung Yiu, Christian S. Jensen

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review


Range aggregate queries find frequent application in data ana- lytics. In many use cases, approximate results are preferred over accurate results if they can be computed rapidly and satisfy ap- proximation guarantees. Inspired by a recent indexing approach, we provide means of representing a discrete point dataset by continuous functions that can then serve as compact index struc- tures. More specifically, we develop a polynomial-based indexing approach, called PolyFit, for processing approximate range ag- gregate queries. PolyFit is capable of supporting multiple types of range aggregate queries, including COUNT, SUM, MIN and MAX aggregates, with guaranteed absolute and relative error bounds. Experimental results show that PolyFit is faster and more accurate and compact than existing learned index structures.
Original languageEnglish
Title of host publicationAdvances in Database Technology - EDBT 2021 - 24th International Conference on Extending Database Technology, Proceedings
EditorsYannis Velegrakis, Demetris Zeinalipour, Panos K. Chrysanthis, Francesco Guerra
Place of PublicationKonstanz
Number of pages12
ISBN (Print)9783893180844
Publication statusPublished - 23 Mar 2021

Publication series

NameProceedings of the International Conference on Extending Database Technology
ISSN (Print)2367-2005


Dive into the research topics of 'PolyFit: Polynomial-based Indexing Approach for Fast Approximate Range Aggregate Queries'. Together they form a unique fingerprint.

Cite this