Secure and privacy-preserving storage of digital data typically requires encrypting it, where the retrieval will man-date its decryption. The overhead of these encryption/decryption requirements introduce some latency, which might be limiting user experience on massive volumes for real-time applications. Reducing this computational load have been studied previously by using lightweight algorithms or selective/partial encryption schemes. In this work, we propose using a recently introduced privacy-preserving coding method [1] (COCOON’2023) to reduce this load and observe that the number of encryption/decryption operations can be reduced by more than 75%, which can be a decent relief especially for real-world applications. We particularly consider privacy requirements of some applications on multimedia data, most typically images and videos.

Rank and select queries are the fundamental building blocks of the compressed data structures. On a given bit string of length$n$, counting the number of set bits up to a certain position is named as the rank, and finding the position of the$k$th set bit is the select query. We present a new data structure and the procedures on it to support rank/select operations. The proposed scheme introduces ($\frac{\log 2m}{d}+\frac{\log n}{s\cdot d}$) overhead bits per each bit over the$n$-bits long input bit string, where$d$is the inner-block size in bits,$s$is the number of inner-blocks in a super-block, and$m$is a properly chosen constant modulus value. When compared to the previous two-level hierarchical data structures that generate$(\frac{\log(s\cdot d)}{d}+\frac{\log n}{s\cdot d})$overhead bits per bit, the new approach reduces the space consumption significantly with proper selection of the parameters. With the new data structure, the rank queries are usually (≈ 90% of the time) executed in$O(t_{d})$time, where$O(t_{d})$is the time required to compute a rank in an inner-block of length$d$-bits, which is assumed to be constant via the wide-register instructions in modern processors. Seldom, it may require to investigate more than one block, where on average this is observed to be around two blocks, empirically. We provide probabilistic analyses on how to choose the appropriate parameters and present several trade-offs to guarantee constant-time rank. We also investigate using the same data structure to support the select queries as well. Experimental evaluation of the introduced scheme revealed that the proposed data structure consumes nearly 30%-50% less space than its alternatives by introducing less than 5% overhead, while the speed is either better or very competitive when compared with the current state-of the art implementations both in terms of rank and select.

On a given vector X = (x1, x2,..., xn) of integers, the range selection (i, j, k) query is finding the k-th smallest integer in (xi, xi+1,..., xj) for any (i, j, k) such that 1 ≤ i ≤ j ≤ n, and 1 ≤ k ≤ j - i + 1. Previous studies on the problem kept X intact and proposed data structures that occupied additional O(n · log n) bits of space over the X itself that answer the queries in logarithmic time. In this study, we replace X and encode all integers in it via a single wavelet tree by using S = n · log u + Σ∀ilog xi+ o(n · log u + Σ∀ilog xi) bits, where u is the number of distinct ⌊log xi⌋ values observed in X. Notice that u is at most 32 (64) for 32-bit (64-bit) integers and when xi> u, the space used for xiin the proposed data structure is less then the Elias-δ coding of xi. Besides data-aware coding of X, the range selection is performed in O(log u + log x') time where x' is the k-th smallest integer in the queried range. This somewhat adaptive result interestingly achieves the range selection regardless of the size of X, and totally depends on the actual answer of the query. In summary, to the best of our knowledge, we present the first algorithm using data-aware space and time for the general range selection problem.

We investigate the usage of the wavelet tree and the rank/select-dictionary data structures on hybrid-structured variable-length codes, which represent an integer in the form of a unary code section followed by a binary section. We propose to handle unary and binary partitions as separate streams and create wavelet trees or R/S dictionaries over the unary streams, which grants us the opportunity to directly access any codeword. Particularly concentrating on Elias and Rice schemes, we introduce several solutions that (i) improve the compression significantly, and (ii) provide random access in constant or logarithmic time. Experiments are conducted to compare the performances of the proposed codes against Elias/Rice schemes and more recent state-of-the-art codings such as Simple9, PForDelta,DACs, and improved-AC techniques. We observed that the newly introduced methods outperform the original Elias/Rice codecs by approximately 30% and the others by approximately 10% in terms of compression ratios. The methods described in this study are generic and may further be extended to some other hybrid structure (unary/binary) variable-length codes as well.

In text compression, statistical context modeling aims to construct a model to calculate the probability distribution of a character based upon its context. The order-k context of a symbol is defined as the string formed by its preceding k symbols. This study introduces compressed context modeling, which defines the order-k context of a character as the sequence of k-bits composed of the entropy compressed representations of its preceding characters. While computing the compressed context of a symbol at some position in a given text, enough number of characters are involved in the compressed context so as to produce k-bits of information. Thus, instead of certain number of characters, certain amount of information is considered as the context of a character, and this property enables the prediction of each character to be performed with nearly uniform amount of information. Experiments are conducted to compare the proposed modeling against the classical fixed-length context definitions. The files in the large Calgary corpus are modeled with the newly introduced compressed context modeling and with the classical fixed-length context modeling. It is observed that on the average the statistical model with the proposed method uses 13.76 percent less space measured according to the number of distinct contexts, while providing 5.88 percent gain in empirical entropy measured by the information content as bits per character.