Prof. Lewenstein's Lab
Prof. Moshe Lewenstein, former Chair of the Department of Computer Science, is an expert on the analysis of algorithms used in pattern matching and data structure design.
Lewenstein and his team create data structures such as fast indexing, indexing with errors, and online indexing. Another focus of the group is approximation algorithms problems, in particular TSP problems such as directed metric TSP, shortest superstring, and special variants of matchings.
The Pattern Matching field is in great demand in leading industries such as multimedia, digital libraries and computational biology. One of the fundamental questions driving much of the pattern matching research in the last twenty years is what type of approximations are inherently computationally hard, and what types are faster to compute.
Lewenstein has researched approximate pattern matching for various notions of approximation. Specifically, he introduced the fastest approximate algorithm with a bounded Hamming distance. He also has several works on scaled pattern matching, where the goal is to find a pattern within a larger text under (size) scaling.
Another interest of Lewenstein's is parameterized matching - pattern matching with alphabet mappings that appear in applications such as program code duplications and image search. He has published a number of papers on approximate parameterized matching, two-dimensional parameterized matching, the longest common parameterized subsequence, and function matching. Lewenstein was one of the first in his field to use code theory techniques in pattern matching.
Advanced Data Structures
Indexing, the online variant of pattern matching, has become ubiquitous in many of the internet systems, where queries are expected to be answered on-the-fly. Classical indexing solutions have been around for a long time now. However, they were tailored to the needs of classical problems.
New challenges arise from the evolving internet-environment on a daily basis. One such problem is to allow indexing in the presence of errors. Lewenstein presented a novel data structure that was efficient in doing so in the presence of more than one error. This has been followed up in the work of scores of papers and is still being actively researched. Along this line, Lewenstein is interested in the special case of indexing with "don't cares" and their extension indexing with gaps and the more elusive indexing with edit distance.
Dynamizing Static Data Structures
Another line of research that has been actively researched by the group is dynamizing static data structures. While indexing data structures take online queries, they tend to treat the text as static information. Lewenstein's team has shown that one can maintain this data online with a low worst-case running time per every character appended to the text. In addition, they dynamized weighted ancestors, where one desires to find a predecessor on a root-to-node path, using novel methods of tree partitions, amortization and deamortization arguments. More recently, they also proposed near-tight algorithms for distance queries in dynamic graphs.
Lewenstein has also addressed the TSP (Travelling Salesperson) problem, demonstrating a strong connection between cycle covers and TSPs, and offering a solution for achieving better approximations for the directed TSP problem. This represented the first improvement to the directed TSP problem in about 20 years. The strong algorithmic connection between cycle covers and matchings in graphs led Lewenstein to explore several NP-hard matching problems, such as minimal maximal matchings, stable matchings with ties and incomplete lists, as well as matchings in multiple interval graphs and dotted interval graphs.
His team has also explored NP-complete pattern matching problems, focusing on supersequences and subsequences, with works on Constrained LCS (Longest Common Subsequence), Restricted LCS, Permuted Common Subsequence, Shortest Common Supersequence, Longest Common Parameterized Subsequence, Longest Common Rigid Subsequence and Shortest Common Superstring.