PolyFit: Polynomial-based indexing approach for fast approximate range aggregate queries

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

doi:10.5441/002/edbt.2021.22

PolyFit: Polynomial-based indexing approach for fast approximate range aggregate queries

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

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

14 Downloads (Pure)

Abstract

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 language	English
Title of host publication	Advances in Database Technology - EDBT 2021 : 24th International Conference on Extending Database Technology, Proceedings
Editors	Yannis Velegrakis, Yannis Velegrakis, Demetris Zeinalipour, Panos K. Chrysanthis, Panos K. Chrysanthis, Francesco Guerra
Number of pages	12
Publisher	OpenProceedings.org
Publication date	2021
Pages	241-252
ISBN (Electronic)	978-3-89318-084-4
DOIs	https://doi.org/10.5441/002/edbt.2021.22
Publication status	Published - 2021
Event	Advances in Database Technology - 24th International Conference on Extending Database Technology, EDBT 2021 - Virtual, Nicosia, Cyprus Duration: 23 Mar 2021 → 26 Mar 2021

Conference

Conference	Advances in Database Technology - 24th International Conference on Extending Database Technology, EDBT 2021
Country/Territory	Cyprus
City	Virtual, Nicosia
Period	23/03/2021 → 26/03/2021
Sponsor	Oracle, Snowflake, ZOOM, Zoom Video Communications, Inc.

Series	Advances in Database Technology
ISSN	2367-2005

Bibliographical note

Publisher Copyright:
© 2021 Copyright held by the owner/author(s).

Access to Document

10.5441/002/edbt.2021.22Licence: CC BY-NC-ND 4.0

Open Access articleFinal published version, 2.08 MBLicence: CC BY-NC-ND 4.0

AUB Link

Search for the material in Aalborg University Library's search engine

Cite this

Li, Z., Chan, T. N., Yiu, M. L., & Jensen, C. S. (2021). PolyFit: Polynomial-based indexing approach for fast approximate range aggregate queries. In Y. Velegrakis, Y. Velegrakis, D. Zeinalipour, P. K. Chrysanthis, P. K. Chrysanthis, & F. Guerra (Eds.), Advances in Database Technology - EDBT 2021: 24th International Conference on Extending Database Technology, Proceedings (pp. 241-252). OpenProceedings.org. https://doi.org/10.5441/002/edbt.2021.22

Li, Zhe ; Chan, Tsz Nam ; Yiu, Man Lung et al. / PolyFit : Polynomial-based indexing approach for fast approximate range aggregate queries. Advances in Database Technology - EDBT 2021: 24th International Conference on Extending Database Technology, Proceedings. editor / Yannis Velegrakis ; Yannis Velegrakis ; Demetris Zeinalipour ; Panos K. Chrysanthis ; Panos K. Chrysanthis ; Francesco Guerra. OpenProceedings.org, 2021. pp. 241-252 (Advances in Database Technology).

@inproceedings{09f27f2ac8ee46f08e4093cbdfe03ba2,

title = "PolyFit: Polynomial-based indexing approach for fast approximate range aggregate queries",

abstract = "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.",

author = "Zhe Li and Chan, {Tsz Nam} and Yiu, {Man Lung} and Jensen, {Christian S.}",

note = "Publisher Copyright: {\textcopyright} 2021 Copyright held by the owner/author(s).; Advances in Database Technology - 24th International Conference on Extending Database Technology, EDBT 2021 ; Conference date: 23-03-2021 Through 26-03-2021",

year = "2021",

doi = "10.5441/002/edbt.2021.22",

language = "English",

series = "Advances in Database Technology",

pages = "241--252",

editor = "Yannis Velegrakis and Yannis Velegrakis and Demetris Zeinalipour and Chrysanthis, {Panos K.} and Chrysanthis, {Panos K.} and Francesco Guerra",

booktitle = "Advances in Database Technology - EDBT 2021",

publisher = "OpenProceedings.org",

}

Li, Z, Chan, TN, Yiu, ML & Jensen, CS 2021, PolyFit: Polynomial-based indexing approach for fast approximate range aggregate queries. in Y Velegrakis, Y Velegrakis, D Zeinalipour, PK Chrysanthis, PK Chrysanthis & F Guerra (eds), Advances in Database Technology - EDBT 2021: 24th International Conference on Extending Database Technology, Proceedings. OpenProceedings.org, Advances in Database Technology, pp. 241-252, Advances in Database Technology - 24th International Conference on Extending Database Technology, EDBT 2021, Virtual, Nicosia, Cyprus, 23/03/2021. https://doi.org/10.5441/002/edbt.2021.22

PolyFit: Polynomial-based indexing approach for fast approximate range aggregate queries. / Li, Zhe; Chan, Tsz Nam; Yiu, Man Lung et al.
Advances in Database Technology - EDBT 2021: 24th International Conference on Extending Database Technology, Proceedings. ed. / Yannis Velegrakis; Yannis Velegrakis; Demetris Zeinalipour; Panos K. Chrysanthis; Panos K. Chrysanthis; Francesco Guerra. OpenProceedings.org, 2021. p. 241-252 (Advances in Database Technology).

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

TY - GEN

T1 - PolyFit

T2 - Advances in Database Technology - 24th International Conference on Extending Database Technology, EDBT 2021

AU - Li, Zhe

AU - Chan, Tsz Nam

AU - Yiu, Man Lung

AU - Jensen, Christian S.

PY - 2021

Y1 - 2021

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 - Article in proceeding

AN - SCOPUS:85113717020

T3 - Advances in Database Technology

SP - 241

EP - 252

BT - Advances in Database Technology - EDBT 2021

A2 - Velegrakis, Yannis

A2 - Zeinalipour, Demetris

A2 - Chrysanthis, Panos K.

A2 - Guerra, Francesco

PB - OpenProceedings.org

Y2 - 23 March 2021 through 26 March 2021

ER -

Li Z, Chan TN, Yiu ML, Jensen CS. PolyFit: Polynomial-based indexing approach for fast approximate range aggregate queries. In Velegrakis Y, Velegrakis Y, Zeinalipour D, Chrysanthis PK, Chrysanthis PK, Guerra F, editors, Advances in Database Technology - EDBT 2021: 24th International Conference on Extending Database Technology, Proceedings. OpenProceedings.org. 2021. p. 241-252. (Advances in Database Technology). doi: 10.5441/002/edbt.2021.22

PolyFit: Polynomial-based indexing approach for fast approximate range aggregate queries

Abstract

Conference

Bibliographical note

Access to Document

AUB Link

Other files and links

Fingerprint

Cite this