A string S is called a square if it can be written as the concatenation of two identical strings. Two strings P and Q of the same length are said to square match if, for every substring of P, it is a square if and only if the corresponding substring of Q is also a square. The square pattern matching problem asks for locating all substrings of a given text T of length n that square match a query pattern P of length m. This notion captures similarity in repetition structures and is motivated by applications in areas such as bioinformatics and music structure analysis. In this paper, we introduce a novel technique, called the longest prefix square (LPS) encoding, which represents the square structure of a string as an integer array of the same length. We show that two strings square match if and only if they have identical LPS encodings. Based on this result, we construct an index solving the square pattern matching problem in time O(m lg m + occ) using O(nlg²n) bits of space, where occ denotes the number of occurrences of substrings in T that square match P. If the LPS encoding of P is precomputed, the query time improves to O(m + occ).

We propose a space-efficient index, called τλ-index, for locating rare patterns among similar strings, which has potential usage in drug discovery. Experiments are conducted on real data to compare our index with the state-of-the-art r-index.

The run-length compressed Burrows-Wheeler transform (RLBWT) used in conjunction with the backward search introduced in the FM index is the centerpiece of most com-pressed indexes working on highly-repetitive data sets like biological sequences. Compared to grammar indexes, the size of the RLBWT is often much bigger, but queries like counting the occurrences of long patterns can be done much faster than on any existing grammar index so far. In this paper, we combine the virtues of a grammar with the RLBWT by building the RLBWT on top of a special grammar based on induced suffix sorting. Our experiments reveal that our hybrid approach outperforms the classic RLBWT with respect to the index sizes, and with respect to query times on biological data sets for sufficiently long patterns, which could be interesting for aligning long reads in bioinformatics.

In applications such as network monitoring and sensor measurements, massive amounts of data arrive as a high-rate stream and real-time analytic over the stream data is required. Maintaining a succinct sketch over the data stream has been a dominant approach to support analysis in those applications. Recent applications, however, demand more sophisticated types of analytics such as range-counting. Unfortunately, state-of-the-art sketches perform poorly when facing range-counting as none of them was designed to support range-counting at the outset. In this paper, we aim to fill the gap and present RC-Sketch, a sketch that supports range-counting over rapid data stream. Empirical results show that RC-Sketch outperforms the state-of-the-art in range-count accuracy with comparable throughput.

Two equal-length strings X and Y over an alphabet Σ of size σ are a parameterized match iff X can be transformed to Y by renaming the character X[i] to the character Y[i] for 1 ≤ i ≤ |X| using a one-to-one function from the set of characters in X to the set of characters in Y. The parameterized text indexing problem is defined as: Index a text T of n characters over an alphabet set Σ of size σ, such that whenever a pattern P[1, p] comes as a query, we can report all occ parameterized occurrences of P in T. A position i ϵ [1, n] is a parameterized occurrence of P in T, iff P and T[i,(i+p-1)] are a parameterized match. We study an interesting generalization of this problem, where the pattern contains one wildcard character φ ∉ Σ that matches with any other character in Σ. Therefore, for a pattern P[1, p] = P1φP2, our task is to report all positions i in T, such that the string P_1 P_2 and the string obtained by concatenating T[i,(i+|P1|-1)] and T[(i+|P1|+1),(i+p-1)] are a parameterized match. We show that such queries can be answered in optimal O(p+occ) time per query using an O(n log n) space index. We then show how to compress our index into O(n log σ) space but with a higher query cost of O(p(log log n+logσ)+occ logσ).

MOTIVATION: High-throughput sequencing technology has revolutionized the study of metagenomics and cancer evolution. In a relatively simple environment, a metagenomics sequencing data is dominated by a few species. By analyzing the alignment of reads from microbial species, single nucleotide polymorphisms can be discovered and the evolutionary history of the populations can be reconstructed. The ever-increasing read length will allow more detailed analysis about the evolutionary history of microbial or tumor cell population. A simulator of shotgun sequences from such populations will be helpful in the development or evaluation of analysis algorithms. RESULTS: Here, we described an efficient algorithm, MetaSMC, which simulates reads from evolving microbial populations. Based on the coalescent theory, our simulator supports all evolutionary scenarios supported by other coalescent simulators. In addition, the simulator supports various substitution models, including Jukes-Cantor, HKY85 and generalized time-reversible models. The simulator also supports mutator phenotypes by allowing different mutation rates and substitution models in different subpopulations. Our algorithm ignores unnecessary chromosomal segments and thus is more efficient than standard coalescent when recombination is frequent. We showed that the process behind our algorithm is equivalent to Sequentially Markov Coalescent with an incomplete sample. The accuracy of our algorithm was evaluated by summary statistics and likelihood curves derived from Monte Carlo integration over large number of random genealogies. AVAILABILITY AND IMPLEMENTATION: MetaSMC is written in C. The source code is available at https://github.com/tarjxvf/metasmc. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Many emerging applications are based on finding interesting subsequences from sequence data. Finding “prominent streaks,” a set of the longest contiguous subsequences with values all above (or below) a certain threshold, from sequence data is one of that kind that receives much attention. Motivated from real applications, we observe that prominent streaks alone are not insightful enough but require the discovery of something we coined as “historic moments” as companions. In this article, we present an algorithm to efficiently compute historic moments from sequence data. The algorithm is incremental and space optimal , meaning that when facing new data arrival, it is able to efficiently refresh the results by keeping minimal information. Case studies show that historic moments can significantly improve the insights offered by prominent streaks alone. Furthermore, experiments show that our algorithm can outperform the baseline in both time and space.

This study considers the soft capacitated vertex cover problem in a dynamic setting. This problem generalizes the dynamic model of the vertex cover problem, which has been intensively studied in recent years. Given a dynamically changing vertex-weighted graph G=(V,E), which allows edge insertions and edge deletions, the goal is to design a data structure that maintains an approximate minimum vertex cover while satisfying the capacity constraint of each vertex. That is, when picking a copy of a vertex v in the cover, the number of v's incident edges covered by the copy is up to a given capacity of v. We extend Bhattacharya et al.'s work [SODA'15 and ICALP'15] to obtain a deterministic primal-dual algorithm for maintaining a constant-factor approximate minimum capacitated vertex cover with O(log n / epsilon) amortized update time, where n is the number of vertices in the graph. The algorithm can be extended to (1) a more general model in which each edge is associated with a non-uniform and unsplittable demand, and (2) the more general capacitated set cover problem.

Galled treesare a class of tree-like phylogenetic networks in which the loops are not overlapping with each other. They are popularly used among biologists to represent the evolutionary history between a set of species. In this paper, we propose a compact encoding for the structure of a galled tree, and show that with our encoding, the treecontainment problemon a galled tree can be solved in optimal time.

Given n horizontal segments, each associated with a color from [σ], the Categorical Segment Stabbing problem is to find the distinct K colors stabbed by a vertical line. When the end-points of the segments are distinct and lie in [1, 2n], we present an (2 + ε)n log σ + O(n)-bit index with O(K/ε) query time, where ε∈ (0, 1].When the end-points are arbitrary real numbers, a standard reduction to the above scenario improves the existing bounds of Janardan and Lopez. We also present results for few other variations: • reporting the top-k colors that are stabbed, where each color has a fixed priority. • handling these scenarios when the given segments form a tree range.

Finding the density of a set of n points, especially where points are in IR 2 or IR 3 , has direct applications in thermal analysis of VLSI chips. In this paper, we consider identifying the maximum-density axes-parallel region for a set of weighted points in IR d for d ≥ 2, and show that it can be done in O( dn 2 ) time. We also consider finding the minimum-density axes-parallel region, and show that for IR 2 the problem can be solved in O( n 2 ) time.

Let S and S' be two strings of the same length.We consider the following two variants of string matching. * Parameterized Matching: The characters of S and S' are partitioned into static characters and parameterized characters. The strings are parameterized match iff the static characters match exactly and there exists a one-to-one function which renames the parameterized characters in S to those in S'. * Order-Preserving Matching: The strings are order-preserving match iff for any two integers i,j in [1,|S|], S[i] <= S[j] iff S'[i] <= S'[j]. Let P be a collection of d patterns {P_1, P_2, ..., P_d} of total length n characters, which are chosen from an alphabet Sigma. Given a text T, also over Sigma, we consider the dictionary indexing problem under the above definitions of string matching. Specifically, the task is to index P, such that we can report all positions j where at least one of the patterns P_i in P is a parameterized-match (resp. order-preserving match) with the same-length substring of $T$ starting at j. Previous best-known indexes occupy O(n * log(n)) bits and can report all occ positions in O(|T| * log(|Sigma|) + occ) time. We present space-efficient indexes that occupy O(n * log(|Sigma|+d) * log(n)) bits and reports all occ positions in O(|T| * (log(|Sigma|) + log_{|Sigma|}(n)) + occ) time for parameterized matching and in O(|T| * log(n) + occ) time for order-preserving matching.

In this paper, we propose a new framework to index versioned documents, and extend the keyword queries into the more general phrase queries. Our index answers a one-sided time-constrained phrase query for any phrase P in O((|P|+k)log n) time, where n is the dataset size and k is the output size. We discuss how to tune our framework with realistic assumptions, our experiments shows that under similar space budgets, our index supports queries 5 times faster than the baseline inverted lists when |P| is at least four.

Given a string X[1, n] and a position k in [1, n], the Shortest Unique Substring of X covering k, denoted by S_k, is a substring X[i, j] of X which satisfies the following conditions: (i) i leq k leq j, (ii) i is the only position where there is an occurrence of X[i, j], and (iii) j - i is minimized. The best-known algorithm [Hon et al., ISAAC 2015] can find S k for all k in [1, n] in time O(n) using the string X and additional 2n words of working space. Let tau be a given parameter. We present the following new results. For any given k in [1, n], we can compute S_k via a deterministic algorithm in O(n tau^2 log n tau) time using X and additional O(n/tau) words of working space. For every k in [1, n], we can compute S_k via a deterministic algorithm in O(n tau^2 log n/tau) time using X and additional O(n/tau) words and 4n + o(n) bits of working space. For both problems above, we present an O(n tau log^{c+1} n)-time randomized algorithm that uses n/ log c n words in addition to that mentioned above, where c geq 0 is an arbitrary constant. In this case, the reported string is unique and covers k, but with probability at most n^{-O(1)} , may not be the shortest. As a consequence of our techniques, we also obtain similar space-and-time tradeoffs for a related problem of finding Maximal Unique Matches of two strings [Delcher et al., Nucleic Acids Res. 1999].

In 3-D integrated circuits, through silicon via (TSV) is a critical enabling technique to provide vertical connections. However, it may suffer from many reliability issues such as undercut, misalignment, or random open defects. Various fault-tolerance mechanisms have been proposed in literature to improve yield, at the cost of significant area overhead. In this paper, we focus on the structure that uses one spare TSV for a group of original TSVs, and study the optimal assignment of spare TSVs under yield and timing constraints to minimize the total area overhead. We show that such problem can be modeled as a constrained graph decomposition problem. Two efficient heuristics are further developed to address this problem. Experimental results show that under the same yield and timing constraints, our heuristic can reduce the area overhead induced by the fault-tolerance mechanisms by up to 61%, compared with a seemingly more intuitive nearest-neighbor-based heuristic.

Through Silicon Via (TSV) is a critical enabling technique in three-dimensional integrated circuits (3D ICs). However, it may suffer from many reliability issues. Various fault-tolerance mechanisms have been proposed in literature to improve yield, at the cost of significant area overhead. In this paper, we focus on the structure that uses one spare TSV for a group of original TSVs, and study the optimal assignment of spare TSVs under yield and timing constraints to minimize the total area overhead. We show that such problem can be modeled through constrained graph decomposition. An efficient heuristic is further developed to address this problem. Experimental results show that under the same yield and timing constraints, our heuristic can reduce the area overhead induced by the fault-tolerance mechanisms by up to 38%, compared with a seemingly more intuitive nearest-neighbor based heuristic.

Cognitive radio (CR) is intended to meet the exponentially growing demand for spectrum by allowing for opportunistic utilization of idle legacy channels. Rendezvous, where two radios complete handshaking in an idle channel, is a key step for “stranger” (unknown to each other) CRs to start communication. However, none of existing algorithms guarantee rendezvous for heterogeneous or stranger CRs with different spectrum-sensing capabilities, in spite of the fact that (i) a wide variety of mobile devices are equipped with heterogeneous radios and (ii) there are numerous applications requiring efficient rendezvous for heterogeneous radios/CRs. In this paper, we propose a new channel hopping algorithm, called Heterogeneous Hopping (HH), that guarantees rendezvous without assuming existence of a universal channel set that can be sensed by all radios. HH is realized with a two-layer design that harmonizes the fixed-short-cycle and parity-alignment techniques we propose here, in order to guide CRs to rendezvous in two complementary situations resulting from the different capabilities of mobile wireless devices. To best of our knowledge, HH is the first channel-hopping scheme that guarantees rendezvous between heterogeneous radios. Our in-depth evaluation has shown HH to be significantly faster than simple extensions of existing schemes. Moreover, the latter cannot guarantee successful rendezvous, either.

The inverted index is the backbone of modern web search engines. For each word in a collection of web documents, the index records the list of documents where this word occurs. Given a set of query words, the job of a search engine is to output a ranked list of the most relevant documents containing the query. However, if the query consists of an arbitrary string—which can be a partial word, multiword phrase, or more generally any sequence of characters—then word boundaries are no longer relevant and we need a different approach. In string retrieval settings, we are given a set D ={ d 1 , d 2 , d 3 , …, d D } of D strings with n characters in total taken from an alphabet set Σ = [σ], and the task of the search engine, for a given query pattern P of length p , is to report the “most relevant” strings in D containing P . The query may also consist of two or more patterns. The notion of relevance can be captured by a function score ( P , d r ), which indicates how relevant document d r is to the pattern P . Some example score functions are the frequency of pattern occurrences, proximity between pattern occurrences, or pattern-independent PageRank of the document. The first formal framework to study such kinds of retrieval problems was given by Muthukrishnan [SODA 2002]. He considered two metrics for relevance: frequency and proximity. He took a threshold-based approach on these metrics and gave data structures that use O ( n log n ) words of space. We study this problem in a somewhat more natural top- k framework. Here, k is a part of the query, and the top k most relevant (highest-scoring) documents are to be reported in sorted order of score. We present the first linear-space framework (i.e., using O ( n ) words of space) that is capable of handling arbitrary score functions with near-optimal O ( p + k log k ) query time. The query time can be made optimal O ( p + k ) if sorted order is not necessary. Further, we derive compact space and succinct space indexes (for some specific score functions). This space compression comes at the cost of higher query time. At last, we extend our framework to handle the case of multiple patterns. Apart from providing a robust framework, our results also improve many earlier results in index space or query time or both.

Hon et al. (2011) recently proposed a variant of suffix tree, called circular suffix tree, and showed that it can be compressed into succinct space and can be used to solve the circular dictionary matching problem efficiently. Although there are several efficient construction algorithms for the suffix tree in the literature, none of them can be applied directly to construct circular suffix tree due to the different nature of the patterns being indexed. Here, we give the first construction algorithm for the circular suffix tree, which takes O(n log n) time and requires O(n log σ + d log n)$ bits of working space, where n denotes the total length of the patterns in the dictionary, d denotes the number of patterns, and s denotes the alphabet size.

Let D = {d1, d2,...dD} be a given collection of D string documents of total length n, our task is to index D, such that whenever a pattern P (of length p) and an integer k come as a query, those k documents in which P appears the most number of times can be listed efficiently. In this paper, we propose a compressed index taking 2|CSA| + D logn/D + O(D) + o(n) bits of space, which answers a query with O(tsalog k logϵn) per document report time. This improves the O(tsalog k log1+ϵn) per document report time of the previously best-known index with (asymptotically) the same space requirements [Belazzougui and Navarro, SPIRE 2011]. Here, |CSA| represents the size (in bits) of the compressed suffix array (CSA) of the text obtained by concatenating all documents in V, and tsais the time for decoding a suffix array value using the CSA.

Memory architectures have been widely adopted in network intrusion detection system for inspecting malicious packets due to their flexibility and scalability. Memory architectures match input streams against thousands of attack patterns by traversing the corresponding state transition table stored in commodity memories. With the increasing number of attack patterns, reducing memory requirement has become critical for memory architectures. In this paper, we propose a novel memory architecture using perfect hashing to condense state transition tables without hash collisions. The proposed memory architecture achieves up to 99.5% improvement in memory reduction compared to the traditional two-dimensional memory architecture. We have implemented our memory architectures on graphic processing units and tested using attack patterns from Snort V2.8 and input packets form DEFCON. The experimental results show that the proposed memory architectures outperform state-of-the-art memory architectures both on performance and memory efficiency.

Structural alignment has been shown to be an effective computational method to identify structural noncoding RNA(ncRNA) candidates as ncRNAs are known to be conserved in secondary structures. However, the complexity of the structural alignment algorithms becomes higher when the structure has pseudoknots. Even for the simplest type of pseudoknots (simple pseudoknots), the fastest algorithm runs in O(mn3) time, where m, n are the length of the query ncRNA (with known structure) and the length of the target sequence (with unknown structure), respectively. In practice, we are usually given a long DNA sequence and we try to locate regions in the sequence for possible candidates of a particular ncRNA. Thus, we need to run the structural alignment algorithm on every possible region in the long sequence. For example, finding candidates for a known ncRNA of length 100 on a sequence of length 50,000, it takes more than one day. In this paper, we provide an efficient algorithm to solve the problem for simple pseudoknots and it is shown to be 10 times faster. The speedup stems from an effective pruning strategy consisting of the computation of a lower bound score for the optimal alignment and an estimation of the maximum score that a candidate can achieve to decide whether to prune the current candidate or not.

Given a set D of d patterns of total length n, the dictionary matching problem is to index D such that for any query text T, we can locate the occurrences of any pattern within T efficiently. This problem can be solved in optimal O(|T|+occ) time by the classical AC automaton (Aho and Corasick, 1975) where occ denotes the number of occurrences. The space requirement is O(n) words. In the {approximate} dictionary matching problem with one error, we consider a substring of T[i..j] an occurrence of P whenever the edit distance between T[i..j] and P is at most one. For this problem, the best known indexes are by Cole et al. (2004), which requires O(n+ d\log{d}) words of space and reports all occurrences in O(|T|\log{d}\log{\log{d}}+occ) time, and by Ferragina et al. (1999), which requires O(n^{1+\epsilon}) words of space and reports all occurrences in O(|T|\log\log n + occ) time. Recently, there have been successes in compressing the dictionary matching index while keeping the query time optimal (Belazzougui, 2010, Hon et al., 2010). However, a compressed index for approximate dictionary matching problem is still open. In this paper, we propose the first such index which requires an optimal nH_k+O(n)+o(n\log\sigma)-bit index space, where H_k denotes the kth-order empirical entropy of \D, and \sigma is the size of alphabet set from which all the characters in \D and T are drawn. The query time of our index is O(σ|T|log3n log \ log n + occ).

Property matching is a biologically motivated problem where the task is to find those occurrences of an online pattern P in a string text T (of size n), such that the matched part in T satisfies some conceptual property. The property of a string is a set π of (possibly overlapping) intervals {(s1, f1), (s2, f2),⋯} corresponding to the part of T, and an occurrence of a pattern P at T[i..(i + |P| - 1)] is a valid output under the property π only if T[i..(i + |P| - 1)] is completely contained in some interval (sj, fj) ∈ π. Algorithmically this problem can be solved in time linear to the size of text. Amir et al. (2008) introduced the indexing version of this problem, where they preprocess the text in O(n log σ + n log log n) time and maintain an O(n log n) bits index, named Property Suffix Tree (PST), where σ denotes the alphabet size. PST can perform property matching in optimal O(|P| log σ + occπ) time, where occπis the number of occurrences of P in T which satisfies the property. Later, Iliopoulos and Rahman (2008) proposed an alternative index which can be constructed in linear time. Recently Kopelowitz (2010) considered the dynamic version of this problem where intervals can be added or deleted. However, all these indexes requires space of O(n log n) bits, which can be much more than the size of the text (n log σ bits). In this paper, we propose the first index for property matching which takes space close to the entropy compressed space requirement of the text. Our compressed index takes |CSA| + n(2 + ∈ + o(1)) bits space and can perform query answering in O(t(|P|) + 1/∈ occπtSA) time, where |CSA| is the size of compressed suffix array (CSA), t(|P|) and tSAare the time for searching a pattern of length |P| and the time for computing the suffix array value using CSA, respectively, and e is a constant. We also introduce a dynamic index, taking |CSA| + n(2 + ∈ + o(1)) + O(|π|log n) bits of space, which can perform query answering in O(t(|P|) + 1/∈ occπ(log n/log log n + tSA) log n) time and can update (insert or delete) an interval (s, f) in O((f - s + 1)(log n + log |π| + tSA)) time.

Inverted indexes are the most fundamental and widely used data structures in information retrieval. For each unique word occurring in a document collection, the inverted index stores a list of the documents in which this word occurs. Compression techniques are often applied to further reduce the space requirement of these lists. However, the index has a shortcoming, in that only predefined pattern queries can be supported efficiently. In terms of string documents where word boundaries are undefined, if we have to index all the substrings of a given document, then the storage quickly becomes quadratic in the data size. Also, if we want to apply the same type of indexes for querying phrases or sequence of words, then the inverted index will end up storing redundant information. In this paper, we show the first set of inverted indexes which work naturally for strings as well as phrase searching. The central idea is to exclude document d in the inverted list of a string P if every occurrence of P in d is subsumed by another string of which P is a prefix. With this we show that our space utilization is close to the optimal. Techniques from succinct data structures are deployed to achieve compression while allowing fast access in terms of frequency and document id based retrieval. Compression and speed trade-offs are evaluated for different variants of the proposed index. For phrase searching, we show that our indexes compare favorably against a typical inverted index deploying position-wise intersections. We also show efficient top-k based retrieval under relevance metrics like frequency and tf-idf.

MOTIVATION: Structural alignment of RNA is found to be a useful computational technique for idenitfying non-coding RNAs (ncRNAs). However, existing tools do not handle structures with pseudoknots. Although algorithms exist that can handle structural alignment for different types of pseudoknots, no software tools are available and users have to determine the type of pseudoknots to select the appropriate algoirthm to use which limits the usage of structural alignment in identifying novel ncRNAs. RESULTS: We implemented the first web server, RNASAlign, which can automatically identify the pseudoknot type of a secondary structure and perform structural alignment of a folded RNA with every region of a target DNA/RNA sequence. Regions with high similarity scores and low e-values, together with the detailed alignments will be reported to the user. Experiments on more than 350 ncRNA families show that RNASAlign is effective. AVAILABILITY: http://www.bio8.cs.hku.hk/RNASAlign.

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.

Pattern matching on text data has been a fundamental field of Computer Science for nearly 40 years. Databases supporting full-text indexing functionality on text data are now widely used by biologists. In the theoretical literature, the most popular internal-memory index structures are the suffix trees and the suffix arrays, and the most popular external-memory index structure is the string B-tree. However, the practical applicability of these indexes has been limited mainly because of their space consumption and I/O issues. These structures use a lot more space (almost 20 to 50 times more) than the original text data and are often disk-resident. Ferragina and Manzini (2005) and Grossi and Vitter (2005) gave the first compressed text indexes with efficient query times in the internal-memory model. Recently, Chien et al (2008) presented a compact text index in the external memory based on the concept of Geometric Burrows-Wheeler Transform. They also presented lower bounds which suggested that it may be hard to obtain a good index structure in the external memory. In this paper, we investigate this issue from a practical point of view. On the positive side we show an external-memory text indexing structure (based on R-trees and KD-trees) that saves space by about an order of magnitude as compared to the standard String B-tree. While saving space, these structures also maintain a comparable I/O efficiency to that of String B-tree. We also show various space vs I/O efficiency trade-offs for our structures.

This paper investigates the approximate library management problem, which is to construct an index for a dynamic text collection $L$ such that for any query pattern $P$ and any integer $k$, we can report all $k$-error matches of $P$ in $L$ efficiently. Existing work either focussed on the static version of the problem or assumed k=0. We observe that by combining several recent techniques, we can achieve the first compressed indexes that support efficient pattern queries and updating simultaneously.

We consider service enhancement in a wireless environment in which clients try to obtain service from a set of servers. Each client desires a minimum overall service success probability, which is achieved by establishing multiple independent connections with multiple servers. Given the service success probability of each potential client-server connection, our problem is to assign the connections such that the number of satisfied clients (whose overall service success probability is met) is maximized subject to server capacity constraints. In this paper, we make minor adaptations to the well-known notion of probabilistic network from the machine learning community and use it as our communication model. We then formally define the above optimization problem as the link assignment for successful service problem (LASS). While LASS can be reduced to the maximum matching problem in the deterministic case (where the success probabilities of each edge is 1), we show that in the probabilistic case it is NP-hard (and MaxSNP-hard). An equivalent integer programming formulation for LASS is obtained so that for small input size, the problem may be efficiently solved by the standard IP solver in practice. To tackle large input size, various heuristics are designed. Furthermore, in the special case where the underlying network graph is a tree (which is common in many real-life settings), we show that LASS can be solved in linear time based on a simple greedy algorithm. Experimental evaluations are performed and the results demonstrate the practicality of the algorithms and the heuristics.

To evaluate the performance of database applications and DBMSs, we usually execute workloads of queries on generated databases of different sizes and measure the response time. This paper introduces MyBenchmark, an offline data generation tool that takes a set of queries as input and generates database instances for which the users can control the characteristics of the resulting workload. Applications of MyBenchmark include database testing, database application testing, and application-driven benchmarking. We present the architecture and the implementation algorithms of MyBenchmark. We also present the evaluation results of MyBenchmark using TPC workloads.

In synchronous circuit designs, clock skew is difficult to minimize because a single physical layout of a clock tree must satisfy multiple constraints in a complicated power mode environment where certain modules may operate with different voltages. In this paper, we use adjustable delay buffers (ADB) whose delays can be tuned or adjusted to minimize clock skew under different power modes. Assuming that the positions of$k$ADBs are already determined, we first propose a linear-time optimal algorithm which assigns the values of ADBs so that the skew is optimal among all possible ADB assignments with a possibility of latency penalty. Then, we propose a modified optimal algorithm without latency penalty. We also propose an efficient heuristic to determine good positions for ADBs. Our results show significant improvement when compared to cases without ADBs.

Given a set D={d1, d2,..., dD} of D strings of total length n, our task is to report the "most relevant"strings for a given query pattern P. This involves somewhat more advanced query functionality than the usual pattern matching, as some notion of "most relevant" is involved. In information retrieval literature, this task is best achieved by using inverted indexes. However, inverted indexes work only for some predefined set of patterns. In the pattern matching community, the most popular pattern-matching data structures are suffix trees and suffix arrays. However, a typical suffix tree search involves going through all the occurrences of the pattern over the entire string collection, which might be a lot more than the required relevant documents. The first formal framework to study such kind of retrieval problems was given by Muthukrishnan. He considered two metrics for relevance: frequency and proximity. He took a threshold-based approach on these metrics and gave data structures taking O(n log n) words of space. We study this problem in a slightly different framework of reporting the top k most relevant documents (in sorted order) under similar and more general relevance metrics. Our framework gives linear space data structure with optimal query times for arbitrary score functions. As a corollary, it improves the space utilization for the problems in while maintaining optimal query performance. We also develop compressed variants of these data structures for several specific relevance metrics.

In synchronous circuit designs, clock skew is difficult to minimize because a single physical layout of a clock tree must satisfy multiple constraints in a complicated power mode environment where certain modules may operate with different voltages. In this paper, we use Adjustable Delay Buffers (ADB) whose delays can be tuned or adjusted to minimize clock skew under different power modes. Assuming that the positions of k ADBs are already determined, we propose a linear-time optimal algorithm which assigns the values of ADBs so that the skew is optimal among all possible ADB assignments. We also propose an efficient heuristic to determine good positions for ADBs. Our results show significant improvement when compared to cases without ADBs. Categories and Subject Descriptors B.6.3 [Logic Design]: Design Aids — Optimization General Terms: Algorithms, Reliability

Suffix trees and suffix arrays are the most prominent full-text indices, and their construction algorithms are well studied. In the literature, the fastest algorithm runs in $O(n)$ time, while it requires $O(n\log n)$-bit working space, where n denotes the length of the text. On the other hand, the most space-efficient algorithm requires $O(n)$-bit working space while it runs in $O(n\log n)$ time. It was open whether these indices can be constructed in both $o(n\log n)$ time and $o(n\log n)$-bit working space. This paper breaks the above time-and-space barrier under the unit-cost word RAM. We give an algorithm for constructing the suffix array, which takes $O(n)$ time and $O(n)$-bit working space, for texts with constant-size alphabets. Note that both the time and the space bounds are optimal. For constructing the suffix tree, our algorithm requires $O(n\log^{\epsilon}n)$ time and $O(n)$-bit working space for any $0<\epsilon<1$. Apart from that, our algorithm can also be adopted to build other existing full-text indices, such as compressed suffix tree, compressed suffix arrays, and FM-index. We also study the general case where the size of the alphabet $\Sigma$ is not constant. Our algorithm can construct a suffix array and a suffix tree using optimal $O(n\log|\Sigma|)$-bit working space while running in $O(n\log\log|\Sigma|)$ time and $O(n(\log^{\epsilon}n+\log|\Sigma|))$ time, respectively. These are the first algorithms that achieve $o(n\log n)$ time with optimal working space. Moreover, for the special case where $\log|\Sigma|=O((\log\log n)^{1-\epsilon})$, we can speed up our suffix array construction algorithm to the optimal $O(n)$.

The transmission energy required for a wireless communication increases superlinearly with the communication distance. In a mobile wireless network, nodal movement can be exploited to greatly reduce the energy required by postponing communication until the sender moves close to a target receiver, subject to application deadline constraints. In this paper, we characterize the fundamental performance limit, namely the lower bound expected communication distance, achievable by any postponement algorithm within given deadline constraints. Our analytical results concern mainly the random waypoint (RWP) model. Specifically, we develop a tight analytical lower bound of the achievable expected communication distance under the model. In addition, we define a more general map-based movement model, and characterize its lower bound distance by simulations. We also address the practical attainment of distance reduction through movement-predicted communication. Specifically, whereas prior work has experimentally demonstrated the effectiveness a least distance (LD) algorithm, we provide an absolute performance measure of how closely LD can match the theoretical optimum. We show that LD achieves an average reduction in the expected communication distance within 62% to 94% of the optimal, over a realistic range of nodal speeds, for both the RWP and map-based models.

We introduce a new variant of the popular Burrows-Wheeler transform (BWT) called geometric Burrows-Wheeler transform (GBWT). Unlike BWT, which merely permutes the text, GBWT converts the text into a set of points in 2-dimensional geometry. Using this transform, we can answer to many open questions in compressed text indexing: (1) can compressed data structures be designed in external memory with similar performance as the uncompressed counterparts? (2) Can compressed data structures be designed for position restricted pattern matching [16]? We also introduce a reverse transform, called Points2Text; which converts a set of points into text. This transform allows us to derive the first known lower bounds in compressed text indexing. We show strong equivalence between data structural problems in geometric range searching and text pattern matching. This provides a way to derive new results in compressed text indexing by translating the results from range searching.

The past few years have witnessed several exciting results on compressed representation of a string T that supports efficient pattern matching, and the space complexity has been reduced to |T| Hk(T) + o (|T| log sigma) bits, where Hk(T) denotes the kth-order empirical entropy of T, and sigma is the size of the alphabet. In this paper we study compressed representation for another classical problem of string indexing, which is called dictionary matching in the literature. Precisely, a collection D of strings (called patterns) of total length n is to be indexed so that given a text T, the occurrences of the patterns in T can be found efficiently. In this paper we show how to exploit a sampling technique to compress the existingO(n)-word index to an (n Hk(D) + o(n log sigma))-bit index with only a small sacrifice in search time.

Run-Length-Encoding (RLE) is a data compression technique that is used in various applications, e.g., time series, biological sequences, and multimedia databases. One of the main challenges is how to operate on (e.g., index, search, and retrieve) compressed data without decompressing it. In this paper, we introduce the String B-tree for Compressed sequences, termed the SBC-tree, for indexing and searching RLE-compressed sequences of arbitrary length. The SBC-tree is a two-level index structure based on the well-known String B-tree and a 3-sided range query structure [7]. The SBC-tree supports pattern matching queries such as substring matching, prefix matching, and range search operations over RLE-compressed sequences. The SBC-tree has an optimal external-memory space complexity of O(N/B) pages, where N is the total length of the compressed sequences, and B is the disk page size. Substring matching, prefix matching, and range search execute in an optimal O(logB N + |p|+T/B) I/O operations, where |p| is the length of the compressed query pattern and T is the query output size. The SBC-tree is also dynamic and supports insert and delete operations efficiently. The insertion and deletion of all suffixes of a compressed sequence of length m take O(m logB(N + m)) amortized I/O operations. The SBC-tree index is realized inside PostgreSQL. Performance results illustrate that using the SBC-tree to index RLE-compressed sequences achieves up to an order of magnitude reduction in storage, while retains the optimal search performance achieved by the String B-tree over the uncompressed sequences.

We consider the natural extension of the well-known single disk caching problem to the parallel disk I/O model (PDM) [17]. The main challenge is to achieve as much parallelism as possible and avoid I/O bottlenecks. We are given a fast memory (cache) of size M memory blocks along with a request sequence Σ =(b1,b2,...,bn) where each block bi resides on one of D disks. In each parallel I/O step, at most one block from each disk can be fetched. The task is to serve Σ in the minimum number of parallel I/Os. Thus, each I/O is analogous to a page fault. The difference here is that during each page fault, up to D blocks can be brought into memory, as long as all of the new blocks entering the memory reside on different disks. The problem has a long history [18, 12, 13, 26]. Note that this problem is non-trivial even if all requests in Σ are unique. This restricted version is called read-once. Despite the progress in the offline version [13, 15] and read-once version [12], the general online problem still remained open. Here, we provide comprehensive results with a full general solution for the problem with asymptotically tight competitive ratios.

In this paper, we develop concepts of network coverage by a set of mobile wireless sensors for given AOIs, possibly under given deadline constraints. We present analytical results to characterize various basic statistical properties of AOI coverage, when sensors move according to the random waypoint model -either by design or when carried by mobile hosts engaging in random movement -within a closed network area with boundaries.

The transmission energy required for a wireless communication increases superlinearly with the communication distance. In a mobile wireless network, nodal movement can be exploited to greatly reduce the energy required by postponing communication until the sender moves close to a target receiver, subject to application deadline constraints. In this paper, we characterize the fundamental performance limit, namely the lower bound expected communication distance, achievable by any postponement algorithm within given deadline constraints. We consider a realistic map based stochastic movement model, of which the well known random waypoint model is a special case. For the random waypoint model, we develop a tight analytical lower bound of the achievable expected communication distance. For the general map-based model, we characterize the lower bound distance experimentally. We also address the practical attainment of distance reduction (and hence, energy savings) through movement predicted communication. Specifically, whereas prior work has presented a least distance (LD) postponement algorithm and established its effectiveness experimentally, we provide an absolute performance measure of how closely LD can match the theoretical optimum. We show that LD achieves an average reduction in the expected communication distance within 62% to 94% of the optimal, over a realistic range of nodal speeds, for both the map based and random waypoint models. Moreover, the algorithm's absolute performance increases as the nodal speed or the allowable postponement delay increases.

We study the problem of a mobile target (the mouse) trying to evade detection by one or more mobile sensors (we call such a sensor a cat) in a closed network area. We view our problem as a game between two players: the mouse, and the collection of cats forming a single (meta-)player. The game ends when the mouse falls within the sensing range of one or more cats. A cat tries to determine its optimal strategy to minimize the worst case expected detection time of the mouse. The mouse tries to determine an optimal counter movement strategy to maximize the expected detection time. We divide the problem into two cases based on the relative sensing capabilities of the cats and the mouse. When the mouse has a larger sensing range than the cats, we show how the mouse can determine its optimal movement strategy based on local observations of the cats' movements. When the mouse has a sensing range smaller than or equal to the cats', we develop a dynamic programming solution for the mouse's optimal strategy, assuming high level information about the cats' movement model. We discuss how the cats' chosen movement model will affect its presence matrix in the network, and hence its payoff in the game. Extensive experimental results verify and illustrate the analytical results, and evaluate the game's payoffs as a function of several important system parameters.

Let T be a string with n characters over an alphabet of constant size. A recent breakthrough on compressed indexing allows us to build an index for T in optimal space (i.e., O ( n ) bits), while supporting very efficient pattern matching [Ferragina and Manzini 2000; Grossi and Vitter 2000]. Yet the compressed nature of such indexes also makes them difficult to update dynamically. This article extends the work on optimal-space indexing to a dynamic collection of texts. Our first result is a compressed solution to the library management problem, where we show an index of O ( n ) bits for a text collection L of total length n , which can be updated in O (| T | log n ) time when a text T is inserted or deleted from L ; also, the index supports searching the occurrences of any pattern P in all texts in L in O (| P | log n + occ log 2 n ) time, where occ is the number of occurrences. Our second result is a compressed solution to the dictionary matching problem, where we show an index of O ( d ) bits for a pattern collection D of total length d , which can be updated in O (| P | log 2 d ) time when a pattern P is inserted or deleted from D ; also, the index supports searching the occurrences of all patterns of D in any text T in O ((| T | + occ )log 2 d ) time. When compared with the O ( d log d )-bit suffix-tree-based solution of Amir et al. [1995], the compact solution increases the query time by roughly a factor of log d only. The solution to the dictionary matching problem is based on a new compressed representation of a suffix tree. Precisely, we give an O ( n )-bit representation of a suffix tree for a dynamic collection of texts whose total length is n , which supports insertion and deletion of a text T in O (| T | log 2 n ) time, as well as all suffix tree traversal operations, including forward and backward suffix links. This work can be regarded as a generalization of the compressed representation of static texts. In the study of the aforementioned result, we also derive the first O ( n )-bit representation for maintaining n pairs of balanced parentheses in O (log n /log log n ) time per operation, matching the time complexity of the previous O ( n log n )-bit solution.

We propose measures for compressed data structures, in which space usage is measured in a data-aware manner. In particular, we consider the fundamental dictionary problem on set data, where the task is to construct a data structure to represent a set S of n items out of a universe U = {0,..., u $1} and support various queries on S. We use a well-known data-aware measure for set data called gap to bound the space of our data structures. We describe a novel dictionary structure taking gap+O(n log(u/n)/ log n)+O(n log log(u/n)) bits. Under the RAM model, our dictionary supports membership, rank, select, and predecessor queries in nearly optimal time, matching the time bound of Andersson and Thorup's predecessor structure (2000), while simultaneously improving upon their space usage. Our dictionary structure uses exactly gap bits in the leading term (i.e., the constant factor is 1) and answers queries in near-optimal time. When seen from the worst case perspective, we present the first O(n log(u/n))-bit dictionary structure which supports these queries in near-optimal time under RAM model. We also build a dictionary which requires the same space and supports membership, select, and partial rank queries even more quickly in O(loglogn) time. To the best of our knowledge, this is the first of a kind result which achieves data-aware space usage and retains near-optimal time.

This paper investigates how to index a text which is subject to updates. The best solution in the literature (P.Ferragina, et al., 1998) is based on suffix tree using O(n log n) bits of storage, where n is the length of the text. It supports finding all occurrences of a pattern P in O(|P|+occ) time, where occ is the number of occurrences. Each text update consists of inserting or deleting a substring of length y and can be supported in O(y+/spl radic/(n)) time. In this paper, we initiate the study of compressed index using only O(n log |/spl Sigma/|) bits of space, where /spl Sigma/ denotes the alphabet. Our solution supports finding all occurrences of a pattern P in O(|P| Iog/sup 2/n(log/sup /spl epsi//n+log|/spl Sigma/|)+occlog/sup 1+/spl epsi//n) time, while insertion or deletion of a substring of length y can be done in O((y+/spl radic/(n)) Iog/sup 2+/spl epsi// n) amortized tune, where 0

Suffix trees and suffix arrays are the most prominent full-text indices, and their construction algorithms are well studied. It has been open for a long time whether these indices can be constructed in both O(n log n) time and O(n log n)-bit working space, where n denotes the length of the text. In the literature, the fastest algorithm runs in O(n) time, while it requires O(n log n)-bit working space. On the other hand, the most space-efficient algorithm requires O(n)-bit working space while it runs in O(n log n) time. This paper breaks the long-standing time-and-space barrier under the unit-cost word RAM. We give an algorithm for constructing the suffix array which takes O(n) time and O(n)-bit working space, for texts with constant-size alphabets. Note that both the time and the space bounds are optimal. For constructing the suffix tree, our algorithm requires O(n log/sup /spl epsi//n) time and O(n)-bit working space for any 0 < /spl epsi/ < 1. Apart from that, our algorithm can also be adopted to build other existing full-text indices, such as Compressed Suffix Tree, Compressed Suffix Arrays and FM-index. We also study the general case where the size of the alphabet A is not constant. Our algorithm can construct a suffix array and a suffix tree using optimal O(n log |A|)-bit working space while running in O(n log log |A|) time and O(n log/sup /spl epsi//n) time, respectively. These are the first algorithms that achieve 0(n log n) time with optimal working space, under a reasonable assumption that log |A| = o(log n).