SEPIA: estimating selectivities of approximate string predicates in large Databases

Many database applications have the emerging need to support approximate queries that ask for strings that are similar to a given string, such as “name similar to smith” and “telephone number similar to 412-0964”. Query optimization needs the selectivity of such an approximate predicate, i.e., the fraction of records in the database that satisfy the condition. In this paper, we study the problem of estimating selectivities of approximate string predicates. We develop a novel technique, called Sepia, to solve the problem. Given a bag of strings, our technique groups the strings into clusters, builds a histogram structure for each cluster, and constructs a global histogram. It is based on the following intuition: given a query string q, a preselected string p in a cluster, and a string s in the cluster, based on the proximity between q and p, and the proximity between p and s, we can obtain a probability distribution from a global histogram about the similarity between q and s. We give a full specification of the technique using the edit distance metric. We study challenges in adopting this technique, including how to construct the histogram structures, how to use them to do selectivity estimation, and how to alleviate the effect of non-uniform errors in the estimation. We discuss how to extend the techniques to other similarity functions. Our extensive experiments on real data sets show that this technique can accurately estimate selectivities of approximate string predicates. A short version of this article appeared as [21] in the proceedings of the 31st International Conference on Very Large Data Bases (VLDB), August 30 – September 2, 2005, Trondheim, Norway. The source code of our algorithms is available at .     

用多路中断保存命令行

通过分析系统多路中断ＩＮＴ ２ＥＨ的ＯＡＥＨ功能的调用机制,提出一种命令行的保存２方式,从而为研究命令行提供的新的手段。     

字符串匹配技术研究

简述了字符串匹配算法的研究进展，分析了Knuth—Morris-Pratt算法、Boycr—Moore算法以及Horspool、Wu＆Manber和Aho—Corasick针对Boyer—Moore算法提出的多种改进算法，并基于网络安全应用中开放源码的NIDS系统——Snort2．0，对其中几个算法进行评测，指出了实际应用中字符串匹配技术的关键点和解决办法，探讨了应用字符串匹配技术的NIDS的研发方向。     

Hardness of optimal spaced seed design

Speeding up approximate pattern matching is a line of research in stringology since the 80s. Practically fast approaches belong to the class of filtration algorithms, in which text regions dissimilar to the pattern are first excluded, and the remaining regions are then compared to the pattern by dynamic programming. Among the conditions used to test similarity between the regions and the pattern, many require a minimum number of common substrings between them. When only substitutions are taken into account for measuring dissimilarity, counting spaced subwords instead of substrings improves the filtration efficiency. However, a preprocessing step is required to design one or more patterns, called spaced seeds (or gapped seeds), for the subwords, depending on the search parameters. Two distinct lines of research appear the literature: one with probabilistic formulations of seed design problems, in which one wishes for instance to compute a seed with the highest probability to detect the desired similarities (lossy filtration), a second line with combinatorial formulations, where the goal is to find a seed that detects all or a maximum number of similarities (both lossless and lossy filtration). We concentrate on combinatorial seed design problems and consider formulations in which the set of sought similarities is either listed explicitly (RSOS), or characterised by their length and maximal number of mismatches (Non-Detection). Several articles exhibit exponential algorithms for these problems. In this work, we provide hardness and inapproximability results for several seed design problems, thereby justifying the complexity of known algorithms. Moreover, we introduce a new formulation of seed design (MWLS), in which the weight of the seed has to be maximised, and show it is as difficult to approximate as Maximum Independent Set.     

A parallel multistart algorithm for the closest string problem

In this paper we describe and implement a parallel algorithm to find approximate solutions for the Closest String Problem (CSP). The CSP, also known as Motif Finding problem, has applications in Coding Theory and Computational Biology. The CSP is NP-hard which motivates us to think about heuristics to solve large instances. Several approximation algorithms have been designed for the CSP, but all of them have a poor performance guarantee. Recently some researchers have shown empirically that integer programming techniques can be successfully used to solve moderate-size instances (10–30 strings each of which is 300–800 characters long) of the CSP. However, real-world instances are larger than those tested. In this paper we show how a simple heuristic can be used to find near-optimal solutions to that problem. We implemented a parallel version of this heuristic and report computational experiments on large-scale instances. These results show the effectiveness of our approach.     

红河油田水平井压裂管柱可下入性分析及其应用

压裂管柱的安全下入是保证压裂作业正常实施的先决条件。根据红河油田水平井压裂工艺特点,通过建立压裂管柱下入过程中的力学模型,对压裂管柱可下入性展开了分析研究:一是进行了压裂工具遇卡位置分析、管柱强度校核以及管柱可下入性的判定;二是计算了管柱下入过程中的受力情况及压裂管柱的轴向应力、径向应力、切向应力、安全系数。该研究结果在HH55P22井上进行了验证,从而为优化水平井压裂管柱设计、压裂工具选型,确保管柱下入过程中的安全性提供了理论依据。     

一种基于分段匹配的字符串匹配算法

针对已有算法对文本和模式的相关性依赖较大,提出一种基于分段的字符串匹配算法——SM。该算法利用特殊字符将文本先分段再匹配,且匹配过程对模式内容和长度不敏感。通过将SM算法与经典算法进行分析和实验对比,证明SM算法性能稳定,特别是在多模式字符串匹配情况下,SM算法具有比Wu-Manber算法更快的速度和更小的空间消耗。     

High-gam adaptive regulator for a string equation with uncertain harmonic disturbance under boundary output feedback control

This paper considers the boundary stabilization and parameter estimation of a one-dimensional wave equation in the case when one end is fixed and control and hamaomc disturbance with uncertain amplitude are input at another end. A high-gain adaptive regulator is designed in terms of measured collocated end velocity. The existence and uniqueness of the classical solution ofthe closed-loop system is proven. It is shown that the state of the system approaches the standstill as time goes to infinity and mean-while, the estimated parameter converges to the unknown parameter.     

一种高效的多目标串匹配算法

本文通过引入右对齐位置标识方式解决了Boyer-Moore算法思想用于多串匹配的串长不等的问题，提出用于多模式串的高效匹配算法MP_BM。该算法的特点主要在于能够直接处理长度不等的多模式串匹配，同时又能获得很高的匹配效率。