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

arXiv: https://arxiv.org/abs/2003.08031 · HTML: https://mlsanity.com/paper/2003.08031/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Mar 2020.

## Built on by (most cited first, 1 of 1)

- [A Survey of Learned Indexes for the Multi-dimensional Space](https://mlsanity.com/paper/2403.06456/) (2024)

## Abstract (arXiv)

Range aggregate queries find frequent application in data analytics. In some 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 data set 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. Experiment results show that PolyFit is faster and more accurate and compact than existing learned index structures.