.png){kind=icon}
.png){kind=icon}
Return
Computation over APT compressed data
.png){kind=icon}
PRE
AI
DOI：10.1016/j.is.2024.102504.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The Arithmetic Progressions Tree (APT) is a data structure storing an encoding of a monotonic sequence G in [1 .. ] . Previous work on APTs focused on its theoretical and experimental compression guarantees. This paper is the first to consider computations over APT compressed data. In particular: 1. We show how to perform a search for any sub-sequence/a set of the monotone sequence G in time proportional to the query sub-sequence length/set size multiplied by the size of the APT compressed representation of G. 2. We show how, given the APT compressed representation of the monotone sequence G , we can find a minimum run-length of G inconstant time, a maximum run-length of G in (log ) time, and all runs of G in constant time plus the output size. 3. We show how, given the APT compressed representation of the monotone sequence G , we can answer whether a consecutive periodic pattern is represented by an APT-node in (log ) time and report occurrences of in G within the processing time of the output size. 4. In addition, we improve the APT construction algorithm time and space complexity.
Keywords:
Monotonic sequences
Arithmetic progression
Compact data structure
Periodic pattern
Inverted index