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 / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review


Range aggregate queries find frequent application in data analytics. In many use cases, approximate results are preferred over accurate results if they can be computed rapidly and satisfy approximation 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 structures. More specifically, we develop a polynomial-based indexing approach, called PolyFit, for processing approximate range aggregate 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
Subtitle of host publication24th International Conference on Extending Database Technology, Proceedings
EditorsYannis Velegrakis, Yannis Velegrakis, Demetris Zeinalipour, Panos K. Chrysanthis, Panos K. Chrysanthis, Francesco Guerra
Number of pages12
ISBN (Electronic)9783893180844
Publication statusPublished - Mar 2021

Publication series

NameAdvances in Database Technology - EDBT
ISSN (Electronic)2367-2005

ASJC Scopus subject areas

  • Information Systems
  • Software
  • Computer Science Applications


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