Narrow Results

Kim and Park [A dynamic edit distance table, J. Disc. Algo., 2:302–312, 2004] proposed a method (KP) based on a “dynamic edit distance table” that allows one to efficiently maintain unit cost edit distance information between two strings $A$ of length $m$ and $B$ of length $n$ when the strings can be modified by single-character edits to their left or right ends. This type of computation is useful e.g. in cyclic string comparison. KP uses linear time, $O(m+n)$, to update the distance representation after each single edit. Recently Hyyrö et al. [Incremental string comparison, J. Disc. Algo., 34:2-17, 2015] presented an efficient method for maintaining the dynamic edit distance table under general weighted edit distance, running in $O(c(m+n))$ time per single edit, where $c$ is the maximum weight of the cost function. The work noted that the $\mathrm{\Theta }(mn)$ space requirement, and not the running time, may be the main bottleneck in using the dynamic edit distance table. In this paper we take the first steps towards reducing the space usage of the dynamic edit distance table by RLE compressing $A$ and $B$. Let $M$ and $N$ be the lengths of RLE compressed versions of $A$ and $B$, respectively. We propose how to store the dynamic edit distance table using $\mathrm{\Theta }(mN+Mn)$ space while maintaining the same time complexity as the previous methods for uncompressed strings.

In this paper, we study the problem of sequence similarity search. We incorporate vector transformations and apply DFT (Discrete Fourier Transformation) and DWT (Discrete Wavelet Transformation, Haar) dimensionality reduction techniques to reduce the search space/time of sequence similarity range queries. Our empirical results on a number of Prokaryote and Eukaryote DNA contig databases demonstrate up to 50-fold filtration ratio reduction of the search space and up to 13 times faster filtration. The proposed transformation techniques may easily be integrated as a pre-processing phase on top of current similarity search heuristics/techniques such as BLAST, PatternHunter, FastA and QUASAR to efficiently prune non-relevant sequences. We study the precision of applying dimensionality reduction techniques for faster and more efficient range query searches and discuss the imposed trade-offs.

Currently, information search on websites is an indispensable part of daily life. It is an important platform to obtain resources, such as regular notifications or current affairs about relevant companies, schools or other organizations. However, websites are prone to tampering by malicious attacks and thus tamper detection for websites is an important countermeasure to maintain the credibility and integrity of information found on websites. In this paper, we propose a highly feasible batch website tamper detection method based on text comparison. Different algorithms for text comparison have been proposed to analyze various websites with with varying degrees tamper detection using three factors: time efficiency, accuracy of detection and memory consumption. The experiments demonstrated that different algorithms have varying performances in terms of website tamper detection but nevertheless the string comparison method has more advantages under normal circumstances.