TY - GEN
T1 - PolyFit: Polynomial-based Indexing Approach for Fast Approximate Range Aggregate Queries
AU - Li, Zhe
AU - Chan, Tsz Nam
AU - Yiu, Man Lung
AU - Jensen, Christian S.
N1 - Funding Information:
∗This work was supported by grant GRF 152050/19E from the Hong Kong RGC.
Publisher Copyright:
© 2021 Copyright held by the owner/author(s).
PY - 2021/3
Y1 - 2021/3
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85113717020&partnerID=8YFLogxK
U2 - 10.5441/002/edbt.2021.22
DO - 10.5441/002/edbt.2021.22
M3 - Conference article published in proceeding or book
T3 - Advances in Database Technology - EDBT
SP - 241
EP - 252
BT - Advances in Database Technology - EDBT 2021
A2 - Velegrakis, Yannis
A2 - Velegrakis, Yannis
A2 - Zeinalipour, Demetris
A2 - Chrysanthis, Panos K.
A2 - Chrysanthis, Panos K.
A2 - Guerra, Francesco
PB - OpenProceedings.org
ER -