Data Mining, Information Retrieval and Pattern Matching - Application-driven Algorithmic Research

模式匹配正在成熟。在过去的六年里，模式匹配算法领域取得了很大的进展。特别是，研究人员已经研究了这个问题的一般版本。该领域已经从一个重要的理论基础领域发展到在许多不同应用（从多媒体到计算分子生物学）中具有实际可用性的边缘。该项目正在寻求一个积极主动的角色，将这些新结果引入相关的应用领域，以及对模式匹配理论中重要缺失部分的反馈和指导。这包括加入一些大型应用项目作为一个算法组。这里描述的研究问题是由这些项目的需求所激发和启发的。这些问题需要获得对模式匹配本质的新见解，以及以下性质的结果：在动态数据库中生成关联的有效算法。有效地生成广义关联（例如带有否定的关联）。超文本中近似匹配的高效算法。近似字典匹配的高效算法。新的多维自适应压缩方案，允许有效的压缩搜索和空间和时间有效的局部解压缩。模式匹配的泛化。

Pattern Matching is coming of age. The last six years have seen great progress in the area of Pattern Matching Algorithms. In particular, researchers have looked into generalized versions of the problem. The field has evolved from being an important theoretical foundational area to being well-poised on the verge of practical usability in many diverse applications, from multi-media to computational molecular biology. The project is seeking a pro-active role in bringing these new results into the relevant applicant domains, as well as feedback and direction about the important missing parts in the theory of pattern matching. This involves joining some large applied projects as an algorithmic group. The research problems described here are motivated and inspired by the needs of these projects. These problems require achieving new insights into the nature of pattern matching, as well as results of the following nature: Efficient algorithms for association generation in dynamic data bases. Efficient generation of generalized associations (e.g.\ with negations). Efficient algorithms for approximate matching in hyper-text. Efficient algorithms for approximate dictionary matching. New multidimensional adaptive compression schemes that allow efficient compressed searches and space and time efficient local decompression. Generalization of Pattern Matching.