1,721,254 research outputs found
Network analytics via pattern discovery
No full textSocial, biological and communication networks of data with a strong linked nature can often be modeled and analyzed as labeled graphs. We describe some new algorithms for pattern discovery in graphs that can be useful for network analytics, focusing on clique enumeration and its applications
Text Indexing, Suffix Sorting, and Data Compression: Common Problems and Techniques (invited talk)
No full textWavelet Trees
No full textThe wavelet tree is a data structure that represents a recursive partition of a sequence S of length n according to its symbols
On finding common subtrees
No full textAbstractLet T and R be two arbitrary ordered trees, |T| ⩾ |R|, whose nodes are labelled over an alphabet A. We devise a simple solution for detecting all the common subtrees in O(|T|) time and space if the size of A is finite, and O(|T| log min (|A|, |T|)) time otherwise. We solve the problem of finding in T and R all occurrences (if any) of any given tree B in either O(|T|⧸|B|) or O(|B|+|T|⧸|B|) time. This requires to set up a simple data structure in O(|T|) time that allows to find all maximal subtrees of B in O (|B|) time and to solve other related problems
A Quick Tour on Suffix Arrays and Compressed Suffix Arrays
No full textAbstractSuffix arrays are a key data structure for solving a run of problems on texts and sequences, from data compression and information retrieval to biological sequence analysis and pattern discovery. In their simplest version, they can just be seen as a permutation of the elements in {1,2,…,n}, encoding the sorted sequence of suffixes from a given text of length n, under the lexicographic order. Yet, they are on a par with ubiquitous and sophisticated suffix trees. Over the years, many interesting combinatorial properties have been devised for this special class of permutations: for instance, they can implicitly encode extra information, and they are a well characterized subset of the n! permutations. This paper gives a short tutorial on suffix arrays and their compressed version to explore and review some of their algorithmic features, discussing the space issues related to their usage in text indexing, combinatorial pattern matching, and data compression
- …
