Skip to main content

Durable top-k queries on temporal data

Publication ,  Conference
Gao, J; Agarwal, PK; Yang, J
Published in: Proceedings of the VLDB Endowment
January 1, 2018

Many datasets have a temporal dimension and contain a wealth of historical information. When using such data to make decisions, we often want to examine not only the current snapshot of the data but also its history. For example, given a result object of a snapshot query, we can ask for its "durability," or intuitively, how long (or how often) it was valid in the past. This paper considers durable top-k queries, which look for objects whose values were among the top k for at least some fraction of the times during a given interval-e.g., stocks that were among the top 20 most heavily traded for at least 80% of the trading days during the last quarter of 2017. We present a comprehensive suite of techniques for solving this problem, ranging from exact algorithms where k is fixed in advance, to approximate methods that work for any k and are able to exploit workload and data characteristics to improve accuracy while capping index cost. We show that our methods vastly outperform baseline and previous methods using both real and synthetic datasets.

Duke Scholars

Published In

Proceedings of the VLDB Endowment

DOI

EISSN

2150-8097

Publication Date

January 1, 2018

Volume

11

Issue

13

Start / End Page

2223 / 2235

Related Subject Headings

  • 4605 Data management and data science
  • 0807 Library and Information Studies
  • 0806 Information Systems
  • 0802 Computation Theory and Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Gao, J., Agarwal, P. K., & Yang, J. (2018). Durable top-k queries on temporal data. In Proceedings of the VLDB Endowment (Vol. 11, pp. 2223–2235). https://doi.org/10.14778/3275366.3275371
Gao, J., P. K. Agarwal, and J. Yang. “Durable top-k queries on temporal data.” In Proceedings of the VLDB Endowment, 11:2223–35, 2018. https://doi.org/10.14778/3275366.3275371.
Gao J, Agarwal PK, Yang J. Durable top-k queries on temporal data. In: Proceedings of the VLDB Endowment. 2018. p. 2223–35.
Gao, J., et al. “Durable top-k queries on temporal data.” Proceedings of the VLDB Endowment, vol. 11, no. 13, 2018, pp. 2223–35. Scopus, doi:10.14778/3275366.3275371.
Gao J, Agarwal PK, Yang J. Durable top-k queries on temporal data. Proceedings of the VLDB Endowment. 2018. p. 2223–2235.

Published In

Proceedings of the VLDB Endowment

DOI

EISSN

2150-8097

Publication Date

January 1, 2018

Volume

11

Issue

13

Start / End Page

2223 / 2235

Related Subject Headings

  • 4605 Data management and data science
  • 0807 Library and Information Studies
  • 0806 Information Systems
  • 0802 Computation Theory and Mathematics