-
Chapter and Conference Paper
Support Optimality and Adaptive Cuckoo Filters
Filters (such as Bloom Filters) are a fundamental data structure that speed up network routing and measurement operations by storing a compressed representation of a set. Filters are very space efficient, but ...
-
Article
Mind the Gap!
We examine the complexity of the online Dictionary Matching with One Gap Problem (DMOG) which is the following. Preprocess a dictionary D of d patterns, where each pattern contains a special gap symbol that can m...
-
Article
Streaming Pattern Matching with d Wildcards
In the pattern matching with d wildcards problem one is given a text T of length n and a pattern P of length m that contains d wildcard characters, each denoted by a special symbol ‘?’. A wildcard character match...
-
Chapter and Conference Paper
Dynamic Dictionary Matching in the Online Model
In the classic dictionary matching problem, the input is a dictiona...
-
Chapter and Conference Paper
Conditional Lower Bounds for Space/Time Tradeoffs
In recent years much effort has been concentrated towards achieving polynomial time lower bounds on algorithms for solving various well-known problems. A useful technique for showing such lower bounds is to pr...
-
Article
Suffix Trays and Suffix Trists: Structures for Faster Text Indexing
Suffix trees and suffix arrays are two of the most widely used data structures for text indexing. Each uses linear space and can be constructed in linear time for polynomially sized alphabets. However, when it...
-
Chapter and Conference Paper
Dynamic Set Intersection
Consider the problem of maintaining a family F of dynamic sets subject to insertions, deletions, and set-intersection reporting queries: given ...
-
Chapter and Conference Paper
Orienting Fully Dynamic Graphs with Worst-Case Time Bounds
In edge orientations, the goal is usually to orient (direct) the edges of an undirected network (modeled by a graph) such that all out-degrees are bounded. When the network is fully dynamic, i.e., admits edge ...
-
Chapter and Conference Paper
Sparse Suffix Tree Construction in Small Space
We consider the problem of constructing a sparse suffix tree (or suffix array) for b suffixes of a given text T of length n, using only O(b) words of space during construction. Attempts at breaking the naive boun...
-
Chapter and Conference Paper
Selection in the Presence of Memory Faults, with Applications to In-place Resilient Sorting
The selection problem, where one wishes to locate the k th smallest element in an unsorted array of size n, is one of the basic problems studied in comp...
-
Chapter and Conference Paper
Forbidden Patterns
We consider the problem of indexing a collection of documents (a.k.a. strings) of total length n such that the following kind of queries are supported: given two patterns P + and P
-
Chapter and Conference Paper
Persistency in Suffix Trees with Applications to String Interval Problems
The suffix tree has proven to be an invaluable indexing data structure, which is widely used as a building block in many applications. We study the problem of making a suffix tree persistent. Specifically, con...
-
Chapter and Conference Paper
The Property Suffix Tree with Dynamic Properties
Recently there has been much interest in the Property Indexing Problem ([1],[7],[8]), where one is interested to preprocess a text T of size n over alphabet Σ (which we assume is of constant size), and a set of i...
-
Chapter and Conference Paper
Generalized Substring Compression
In substring compression one is given a text to preprocess so that, upon request, a compressed substring is returned. Generalized substring compression is the same with the following twist. The queries contain an...
-
Article
Improved Algorithms for Polynomial-Time Decay and Time-Decay with Additive Error
We consider the problem of maintaining polynomial and exponential decay aggregates of a data stream, where the weight of values seen from the stream diminishes as time elapses. These types of aggregation were...
-
Chapter and Conference Paper
On the Longest Common Parameterized Subsequence
The well-known problem of the longest common subsequence (LCS), of two strings of lengths n and m respectively, is O(nm)-time solvable and is a classical distance measure for strings. Another well-studied string ...
-
Chapter and Conference Paper
Range Non-overlap** Indexing and Successive List Indexing
We present two natural variants of the indexing problem:
-
Chapter and Conference Paper
Suffix Trays and Suffix Trists: Structures for Faster Text Indexing
Suffix trees and suffix arrays are two of the most widely used data structures for text indexing. Each uses linear space and can be constructed in linear time [3,5,6,7]. However, when it comes to answering que...
-
Chapter and Conference Paper
Property Matching and Weighted Matching
Pattern Matching with Properties (Property Matching, for short), involves a string matching between the pattern and the text, and the requirement that the text part satisfies some property.
-
Chapter and Conference Paper
Towards Real-Time Suffix Tree Construction
The quest for a real-time suffix tree construction algorithm is over three decades old. To date there is no convincing understandable solution to this problem. This paper makes a step in this direction by cons...
