Abstract This paper introduces Geometric- k -means (or $${\mathsf{G}}k$$ -means for short), a novel approach that significantly enhances the efficiency and energy economy of the widely utilized k -means algorithm, which, despite its inception over five decades ago, remains a cornerstone in machine learning applications. The essence of $${\mathsf{G}}k$$ -means lies in its active utilization of geometric principles, specifically scalar projection, to significantly accelerate the algorithm without sacrificing solution quality. This geometric strategy enables a more discerning focus on data points that are most likely to influence cluster updates, which we call as high expressive data (HE). In contrast, low expressive data (LE), does not impact clustering outcome, is effectively bypassed, leading to considerable reductions in computational overhead. Experiments spanning synthetic, real-world and high-dimensional datasets, demonstrate $${\mathsf{G}}k$$ -means is significantly better than traditional and state of the art (SOTA) $$k$$ -means variants in runtime and distance computations (DC). Moreover, $${\mathsf{G}}k$$ -means exhibits better resource efficiency, as evidenced by its reduced energy footprint, placing it as more sustainable alternative. The software code and data for our algorithm is available at https://github.com/parichit/Geometric-k-means .

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.

FM-index is traditionally constructed over the forward strand complemented with the reverse strand to support searching both strands by executing a single procedure. Although it expedite the process of indexing, it consumes large amount of memory. In this paper we propose a novel algorithm that is capable of compute the FM-index of a given reference sequence without appending its reverse complement to it. In fact, we deduce the rank of the suffixes on the reverse complemented DNA sequences from the suffix ranks on the forward strand. It reduces the memory consumption significantly. Given a reference genome F of length n, FR is the concatenated forward and reverse strand, where R is the reverse complement string of F such that each base is replaced with its corresponding complement in the reverse order. The algorithm makes it possible to compute the FM-index over 2n–symbols long FR by using the FM-index over the n–symbols long FM-index, which nearly halves the memory consumption. The embarrassingly parallel process can speed up significantly with the availability of more cores/threads.

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.

Given a text T[1,n] over an alphabet Σ of size σ, the suffix array of T stores the lexicographic order of the suffixes of T. The suffix array needs Θ(nlog n) bits of space compared to the n log σ bits needed to store T itself. A major breakthrough [FM - Index, FOCS'00] in the last two decades has been encoding the suffix array in near-optimal number of bits (≈ log σ bits per character). One can decode a suffix array value using the FM-Index in log^{O(1)} n time. We study an extension of the problem in which we have to also decode the suffix array values of the reverse text. This problem has numerous applications such as in approximate pattern matching [Lam et al., BIBM' 09]. Known approaches maintain the FM - Index of both the forward and the reverse text which drives up the space occupancy to 2nlog σ bits (plus lower order terms). This brings in the natural question of whether we can decode the suffix array values of both the forward and the reverse text, but by using nlog σ bits (plus lower order terms). We answer this question positively, and show that given the FM - Index of the forward text, we can decode the suffix array value of the reverse text in near logarithmic average time. Additionally, our experimental results are competitive when compared to the standard approach of maintaining the FM - Index for both the forward and the reverse text. We believe that applications that require both the forward and reverse text will benefit from our approach.

The non-overlapping indexing problem is defined as follows: pre-process a given text T[1,n] of length n into a data structure such that whenever a pattern P[1,p] comes as an input, we can efficiently report the largest set of non-overlapping occurrences of P in T. The best known solution is by Cohen and Porat [ISAAC, 2009]. Their index size is O(n) words and query time is optimal O(p+nocc), where nocc is the output size. We study this problem in the cache-oblivious model and present a new data structure of size O(n log n) words. It can answer queries in optimal O(p/(B)+log_B n+nocc/B) I/Os, where B is the block size.

This study concentrates on the security of high-entropy volumes, where entropy-encoded multimedia files or compressed text sequences are the most typical sources. We consider a system in which the cost of encryption is hefty in terms of some metric (e.g., time, memory, energy, or bandwidth), and thus, creates a bottleneck. With the aim of reducing the encryption cost on such a system, we propose a data coding scheme to achieve the data security by encrypting significantly less data than the original size without sacrifice in secrecy. The main idea of the proposed technique is to represent the input sequence by not uniquely-decodable codewords. The proposed coding scheme splits a given input into two partitions as the payload, which consists of the ambiguous codeword sequence, and the disambiguation information, which is the necessary knowledge to properly decode the payload. Under the assumed condition that the input data is the output of an entropy-encoder, and thus, on ideal case independently and identically distributed, the payload occupies ~~ (d-2)/d, and the disambiguation information takes ~~ 2/d of the encoded stream, where d>2 denotes a chosen parameter typically between 6 to 20. We propose to encrypt the payload and keep the disambiguation information in plain to reduce the amount of data to be encrypted, where recursive representation of the payload with the proposed coding can decrease the to-be-encrypted volume further. When 2 * 2^d <= n <= tau * d * 2^d, for tau = (d-1.44)/2, we show that the contraction of the possible message space 2^n due to the public disambiguation information is accommodated by keeping the codeword set secret. We discuss possible applications of the proposed scheme in practice.

Summary The order‐preserving pattern matching problem has gained attention in recent years. It consists in finding all substrings in the text, which have the same length and relative order as the input pattern. Typically, the text and the pattern consist of numbers. Since recent times, there has been a tendency to utilize the ability of the word RAM model to increase the efficiency of string matching algorithms. This model works on computer words, reading and processing blocks of characters at once, so that usual arithmetic and logic operations on words can be performed in one unit of time. In this paper, we present a fast order‐preserving pattern matching algorithm, which uses specialized word‐size packed string matching instructions, grounded on the single instruction multiple data instruction set architecture. We show with experimental results that the new proposed algorithm is more efficient than the previous solutions. ©2016 The Authors. Software: Practice and Experience Published by John Wiley & Sons Ltd.

GENCROBAT is a computational system for efficient transmission of genetic data produced by high-throughput DNA sequencing equipment to cloud computing service providers, where the data is processed and turned into information. The transmission not only helps huge sequencing data to be transferred efficiently over the Internet, but also generates highly useful information to be used in the further steps of analysis on the cloud side. A simple analogy to describe what GENCROBAT does is, it acts as an acrobat carrying the DNA sequencing data from where it is produced to where it will be processed through a tiny rope, the communication channel. The volume it needs to transport from one point to another is so huge that it needs to travel over that rope many times. The capacity of the transmission channel is yet another dimension that needs to be handled carefully. GENCROBAT aims to carry as much as the rope lets at each pass. To achieve this, before beginning to carry the raw data, it puts them into special vacuum bags where the goods are squeezed to carry more at each iteration by respecting the capacity of the channel.

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.

Searching for all occurrences of a pattern in a text is a fundamental problem in computer science with applications in many other fields, like natural language processing, information retrieval and computational biology. In the last two decades a general trend has appeared trying to exploit the power of the word RAM model to speed-up the performances of classical string matching algorithms. In this model an algorithm operates on words of length w, grouping blocks of characters, and arithmetic and logic operations on the words take one unit of time. In this paper we use specialized word-size packed string matching instructions, based on the Intel streaming SIMD extensions (SSE) technology, to design very fast string matching algorithms in the case of short patterns. From our experimental results it turns out that, despite their quadratic worst case time complexity, the new presented algorithms become the clear winners on the average for short patterns, when compared against the most effective algorithms known in literature.

Unique decodability is the essential feature of any coding scheme, which is naturally provided by prefix-free codes satisfying the Kraft-McMillan inequality. Non-prefix-free codes have received much less attention due to the lack of an efficient method to support this property. In this study we introduce a novel technique that uses wavelet trees to bring unique decodability to non-prefix-free codes. Proposed method also provides direct access to the ith codeword, which can be extended to any variable-length coding scheme. The space overhead required for unique decoding is upper bounded by n·log q bits, where n is the number of symbols, and q is the number of distinct codeword lengths, which is normally expected to be a small number in non-prefix-free codes. Direct access is supported by using an additional o(n · log q) bits. We show that the overhead space requirement is much less than sampling methods using state-of-the-art compact integer representations.

This study explores an alternative way of storing text files to answer exact match queries faster. We decompose the original file into two parts as filter and payload. The filter part contains the most informative k bits of each byte, and the remaining bits of the bytes are concatenated in the order of appearance to generate the payload. We refer to this structure as k-bit filtered format. When an input pattern is to be searched on the k-bit filtered structure, the same decomposition is performed on the pattern. The k bits from each byte of the pattern form the pattern filter bit sequence, and the rest is the payload. The pattern filter is first scanned on the filter part of the file. At each match position detected in the filter part, the pattern payload is verified against the corresponding location in the payload part of the text. Thus, instead of searching an m-byte pattern on an n-byte text, first k·m bits are scanned on k·n bits, followed by a verification of (8 − k)·m bits on the respective locations of the matching positions. Experiments conducted on natural language texts, plain ASCII DNA sequences and random byte sequences showed that the search performance with the proposed scheme is on average two times faster than the tested best exact pattern-matching algorithms. The highest gain is obtained on plain ASCII DNA sequences. We also developed an effective bitwise pattern-matching algorithm of possible independent interest within this study.

Finding repetitive structures in genomes and proteins is important to understand their biological functions. Many data compressors for modern genomic sequences rely heavily on finding repeats in the sequences. Small-scale and local repetitive structures are better understood than large and complex interspersed ones. The notion of maximal repeats captures all the repeats in the data in a space-efficient way. Prior work on maximal repeat finding used either a suffix tree or a suffix array along with other auxiliary data structures. Their space usage is 19-50 times the text size with the best engineering efforts, prohibiting their usability on massive data such as the whole human genome. We focus on finding all the maximal repeats from massive texts in a time- and space-efficient manner. Our technique uses the Burrows-Wheeler Transform and wavelet trees. For data sets consisting of natural language texts and protein data, the space usage of our method is no more than three times the text size. For genomic sequences stored using one byte per base, the space usage of our method is less than double the sequence size. Our space-efficient method keeps the timing performance fast. In fact, our method is orders of magnitude faster than the prior methods for processing massive texts such as the whole human genome, since the prior methods must use external memory. For the first time, our method enables a desktop computer with 8 GB internal memory (actual internal memory usage is less than 6 GB) to find all the maximal repeats in the whole human genome in less than 17 hours. We have implemented our method as general-purpose open-source software for public use.

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.

Finding repetitive structures in genomes is important to understand their biological functions. Many modern genomic sequence data compressors also highly rely on finding the repeats over the sequences. The notion of maximal repeats captures all the repeats in a space-efficient way. Prior works on maximal repeat finding used either a suffix tree or a suffix array along with other auxiliary data structures. Their space usage is 19-50 times as large as the text size with the best engineering efforts, prohibiting their usability on massive data such as the whole human genome. Our technique is based on the Burrows-Wheeler Transform and wavelet trees. For genomic sequences stored using one byte per base, the space usage of our method is less than double of the sequence size. Our space-efficient method keeps the timing performance fast. In fact, our method is orders of magnitude faster than the prior methods for processing massive texts such as the whole human genome, since the prior methods must use external memory. For the first time, our method enables a normal computer with 8GB internal memory (actual internal memory usage is less than 6GB) to find all the maximal repeats in the whole human genome in less than 17 hours.

We concentrate on indexing DNA sequences via sparse suffix arrays (SSAs) and propose a new short read aligner named PSI-RA (parallel sparse index read aligner). The motivation in using SSAs is the ability to trade memory against time. It is possible to tune the space consumption of the index based on the available memory of the machine and the minimum length of the arriving pattern queries. Although SSAs have been studied before on exact matching of short reads, an elegant way of approximate matching capability was missing. We provide this by defining the right-most mismatch criteria that prioritizes the errors towards the end of the reads since it is known that the errors are more probable at that area. PSI-RA supports any number of mismatches in aligning reads. We give comparisons with some of the well known short read aligners, and show that indexing genome with SSA is a good alternative to Burrows-Wheeler transform or seed based solutions.

This paper describes an algorithm to segment an input Turkish string without any spaces, which may be an output of a speech-to-text application, into words by using morphological analyzer. It is quite possible to use the algorithm on other languages, which has a morphological analysis component, as well. Turkish morphological analyzer is designed and implemented as the linguistic engine of the algorithm. The construction of the analyzer proposes a technique that attempts to achieve group vise morpheme recognition instead of searching suffixes one by one in a word.