Approximate minimum weight matching on points ink-dimensional space

We study the problem of finding a minimum weight complete matching in the complete graph on a set V ofn points ink-dimensional space. The points are the vertices of the graph and the weight of an edge between any two points is the distance between the points under someL _q,-metric. We give anO((2c _q )^{1.5k –1.5k} ((n, n))^0.5 n ^1.5(logn)^2.5) algorithm for finding an almost minimum weight complete matching in such a graph, wherec _q =6k ^1/q for theL _q -metric, is the inverse Ackermann function, and 1. The weight of the complete matching obtained by our algorithm is guaranteed to be at most (1 + ) times the weight of a minimum weight complete matching.This research was supported by a fellowship from the Shell Foundation.     

基于双索引的近似子图匹配

越来越多的大型复杂网络使得图结构的研究变得日益重要,其中近似子图查询备受关注。为了提高查询效率,利用顶点的邻接关系特征为每个顶点建立索引,减少了匹配顶点的数量;并基于结构和标签对大型数据图进行划分,缩小了匹配时的搜索空间。利用离线时建立的双索引,查询时首先利用顶点间的近邻关系判定公式过滤掉大量不满足匹配关系的候选顶点,然后在一定的划分空间中进行边的匹配。真实数据集中的实验表明,与单纯的划分方法或近邻关系索引相比较,双索引机制对于查询的效率和准确率方面均有明显改善。     

Approximate matching of polygonal shapes

For two given simple polygonsP, Q, the problem is to determine a rigid motionI ofQ giving the best possible match betweenP andQ, i.e. minimizing the Hausdorff distance betweenP andI(Q). Faster algorithms as the one for the general problem are obtained for special cases, namely thatI is restricted to translations or even to translations only in one specified direction. It turns out that determining pseudo-optimal solutions, i.e. ones that differ from the optimum by just a constant factor, can be done much more efficiently than determining optimal solutions. In the most general case, the algorithm for the pseudo-optimal solution is based on the surprising fact that for the optimal possible match betweenP and an imageI(Q) ofQ, the distance between the centroids of the edges of the convex hulls ofP andI(Q) is a constant multiple of the Hausdorff distance betweenP andI(Q). It is also shown that the Hausdorff distance between two polygons can be determined in timeO(n logn), wheren is the total number of vertices.This research was supported by the Deutsche Forschungsgemeinschaft under Grant Al 253/1–2, Schwerpunktprogramm Datenstrukturen und effiziente Algorithmen, and by the ESPRIT Basic Research Action No. 7141 (ALCOM II).     

Approximate maximum weight branchings

We consider a special subgraph of a weighted directed graph: one comprising only the k heaviest edges incoming to each vertex. We show that the maximum weight branching in this subgraph closely approximates the maximum weight branching in the original graph. Specifically, it is within a factor of k/(k+1). Our interest in finding branchings in this subgraph is motivated by a data compression application in which calculating edge weights is expensive but estimating which are the heaviest k incoming edges is easy. An additional benefit is that since algorithms for finding branchings run in time linear in the number of edges our results imply faster algorithms although we sacrifice optimality by a small factor. We also extend our results to the case of edge-disjoint branchings of maximum weight and to maximum weight spanning forests.     

Approximate string matching using withinword parallelism

Given a text string, a pattern string, and an integer k, the problem of approximate string matching with k differences is to find all substrings of the text string whose edit distance from the pattern string is less than k. The edit distance between two strings is defined as the minimum number of differences, where a difference can be a substitution, insertion, or deletion of a single character. An implementation of the dynamic programming algorithm for this problem is given that packs several characters and mod-4 integers into a computer word. Thus, it is a parallelization of the conventional implementation that runs on ordinary processors. Since a small alphabet means that characters have short binary codes, the degree of parallelism is greatest for small alphabets and for processors with long words. For an alphabet of size 8 or smaller and a 64 bit processor, a 21-fold parallelism over the conventional algorithm can be obtained. Empirical comparisons to the basic dynamic programming algorithm, to a version of Ukkonen's algorithm, to the algorithm of Galil and Park, and to a limited implementation of the Wu-Manber algorithm are given.     

Approximate topological matching of quad meshes

In this paper, we study the problem of approximate topological matching for quadrilateral meshes, that is, the problem of finding as large a set as possible of matching portions of two quadrilateral meshes. This study is motivated by applications in graphics that involve the modeling of different shapes that have results needing to be merged in order to produce a final unified representation of an object. We show that the problem of producing a maximum approximate topological match of two quad meshes is NP-hard and that its decision version is NP-complete. Given these results, which make an exact solution extremely unlikely, we show that the natural greedy algorithm derived from polynomial-time graph isomorphism can produce poor results, even when it is possible to find matches with only a few nonmatching quads. Nevertheless, we provide a “lazy-greedy” algorithm that is guaranteed to find good matches when mismatching portions of mesh are localized. Finally, we provide empirical evidence that this approach produces good matches between similar quad meshes.

Approximate string matching with suffix automata

Theapproximate string matching problem is, given a text string, a pattern string, and an integerk, to find in the text all approximate occurrences of the pattern. An approximate occurrence means a substring of the text with edit distance at mostk from the pattern. We give a newO(kn) algorithm for this problem, wheren is the length of the text. The algorithm is based on the suffix automaton with failure transitions and on the diagonalwise monotonicity of the edit distance table. Some experiments showing that the algorithm has a small overhead are reported.     

Approximate model matching with multivariable PI-controllers

A technique is proposed for the design of multivariable PI-controllers by approximately matching a prespecified model. The controller parameters are transparently tuned via a scalar model speed parameter. For slow models closed-loop stability can be guaranteed under mild conditions.     

Approximate string matching for music analysis

Approximate pattern matching algorithms have become an important tool in computer assisted music analysis and information retrieval. The number of different problem formulations has greatly expanded in recent years, not least because of the subjective nature of measuring musical similarity. From an algorithmic perspective, the complexity of each problem depends crucially on the exact definition of the difference between two strings. We present an overview of advances in approximate string matching in this field focusing on new measures of approximation.     

图像识别中的兴趣点匹配方法研究

针对图像检索识别的需求,提出了一种基于兴趣点的匹配算法,利用小波变换对图像进行降维和去噪,提取其SIFT点特征,同时进行PCA降维,最后采用基于K-d树的最近邻法进行快速匹配。通过对各种图像大量的实验,结果表明,该方法具有很强的匹配性和鲁棒性,是一种较好的图像匹配算法,可以广泛应用于图像的检索和识别中。     

基于特征点匹配的步态识别

基于图像特征点匹配的算法思想,结合步态能量图(GEI),提出了一种适用于2幅GEI匹配的步态识别方法.在GEI中采用改进的FAST算法提取特征点,并采用具有良好特征描述性能的BRIEF算法描述特征点.考虑到GEI匹配不要求特征点具有旋转不变性,提出了一种质心角约束条件加速特征点的匹配.在CASIA数据库B库上的实验结果表明:方法在识别率和特征计算时间上均具有良好的表现.     

基于压缩后缀数组的近似字符串匹配算法

近似字符串匹配是模式匹配研究领域中的一个重要研究方向。压缩后缀数组是字符串匹配、数据压缩等领域广泛使用的索引结构,具有检索速度快和适用广泛的优点。利用压缩后缀数组,提出了适合近似字符串匹配搜索算法的数据结构,并在此基础上提出了一种匹配搜索算法。实验结果表明,相对于现有的算法,提出的算法在小字母表的情况下具有计算优势。     

图像空间与手术空间点配准算法

手术导航系统中手术空间与图像空间点配准方法,普遍使用无约束最小二乘法求出三维刚体变换矩阵,由于测量误差,求出的矩阵存在着缩放、错切和反射等形变,不是严格的三维刚体变换矩阵。提出有约束最小二乘法,约束条件为正交矩阵,使用迭代法使变换矩阵正交化,从而逼近最优变换矩阵,从理论上解决了点配准算法的工程实现。     

Approximate geometric pattern matching under rigid motions

We present techniques for matching point-sets in two and three dimensions under rigid-body transformations. We prove bounds on the worst-case performance of these algorithms to be within a small constant factor of optimal and conduct experiments to show that the average performance of these matching algorithms is often better than that predicted by the worst-case bounds     

Approximate data instance matching: a survey

Approximate data matching is a central problem in several data management processes, such as data integration, data cleaning, approximate queries, similarity search and so on. An approximate matching process aims at defining whether two data represent the same real-world object. For atomic values (strings, dates, etc), similarity functions have been defined for several value domains (person names, addresses, and so on). For matching aggregated values, such as relational tuples and XML trees, approaches alternate from the definition of simple functions that combine values of similarity of record attributes to sophisticated techniques based on machine learning, for example. For complex data comparison, including structured and semistructured documents, existing approaches use both structure and data for the comparison, by either considering or not considering data semantics. This survey presents terminology and concepts that base approximated data matching, as well as discusses related work on the use of similarity functions in such a subject.     

Approximate string matching with address bit errors

A string S∈Σ^m$S\in {\Sigma }^m$ can be viewed as a set of pairs S={(_σi,i):i∈{0,…,m−1}}$S=\{({\sigma }_i,i):i\in \{0,\dots ,m-1\}\}$. We consider approximate pattern matching problems arising from the setting where errors are introduced to the location component (i$i$), rather than the more traditional setting, where errors are introduced into the content itself (_σi${\sigma }_i$). In this paper, we consider the case where bits of i$i$ may be erroneously flipped, either in a consistent or transient manner. We formally define the corresponding approximate pattern matching problems, and provide efficient algorithms for their resolution, while introducing some novel techniques.     

Approximate regional sequence matching for genomic databases

Recent advances in computational biology have raised sequence matching requirements that result in new types of sequence database problems. In this work, we introduce an important class of such problems, the approximate regional sequence matching (ARSM) problem. Given a data and a pattern sequence, an ARSM result is an approximate occurrence of a region of the pattern in the data sequence under two conditions. First, the region must contain a predetermined area of the pattern sequence, termed core. Second, the allowable deviation between the region of the pattern and its occurrence in the data sequence depends on the length of the region. We propose the PS-ARSM method that processes holistically the regions of a pattern, taking advantage of their overlaps to efficiently identify the ARSM results. Its performance is evaluated with respect to existing techniques adapted to the ARSM problem.     

Approximate model matching for non-linear control systems

Approximate model matching refers to the problem of controlling a non-linear system so as to achieve a response resembling that of a desirable model. The paper presents a family of recursive output feedback controllers that can achieve approximate model matching in all cases where it is possible. The design of these controllers depends on the solution of a set of algebraic inequalities.