Title
At-the-time and Back-in-time Persistent Sketches
Abstract
ABSTRACTIn the era of big data, more and more applications require the information of historical data to support rich analytics, learning, and mining operations. In these cases, it is highly desirable to retrieve information of previous versions of data. Traditionally, multi-version databases can be used to store all historical values of the data in order to support historical queries. However, storing all the historical data can be impractical due to its large space consumption. In this paper, we propose the concept of at-the-time persistent (ATTP) and back-in-time persistent (BITP) sketches, which are sketches that approximately answer queries on previous versions of data with small space. We then provide several implementations of ATTP/BITP sketches which are shown to be more efficient compared to existing state-of-the-art solutions in our empirical studies.
Year
DOI
Venue
2021
10.1145/3448016.3452802
International Conference on Management of Data
Keywords
DocType
ISSN
data sketching, random sampling, persistent data structure, streaming algorithms
Conference
0730-8078
Citations 
PageRank 
References 
0
0.34
0
Authors
5
Name
Order
Citations
PageRank
Benwei Shi100.34
Zhuoyue Zhao2372.55
Yanqing Peng3164.98
Feifei Li42242120.05
Jeff M. Phillips553649.83