Abstract: Pattern match search oriented to planar graphs is widely used in biological networks, social networks, fingerprint identification and image segmentation. Meanwhile, data extracted from those applications is inherently uncertain due to noise, incompleteness and inaccuracy, and query processing techniques of certain planar graphs cannot be applied to uncertain graph data. Therefore, in this paper, the pattern match query oriented to uncertain planar graphs was studied under the probabilistic semantics. Specifically, Uncertain Pattern Match (UPM) queries using the possible world semantics were investigated. Firstly, to avoid enumerating all possible worlds, a basic deterministic algorithm that can exactly compute UPM query was proposed. To further speed up the basic algorithm, an improved deterministic approach was developed based on tighten bounds. Secondly, a sampling algorithm that can quickly and accurately estimate matching probability was designed. The effectiveness of the proposed solutions for UPM queries was verified through extensive experiments on real uncertain planar graph datasets. Finally, UPM queries were applied to the segmentation on pulmonary CT images. The results show that the proposed approaches are superior to classical techniques of image segmentation.

Key words: Uncertain Pattern Match (UPM), possible world, matching graph, deterministic algorithm, sampling algorithm

摘要： 平面图的模式匹配查询可广泛应用于生物网络、社会网络、指纹识别和图像分割等。由于对数据操作时引入的噪声和错误使这些图数据具有不确定性，而确定平面图的查询处理技术不能有效地处理不确定性，因此利用概率语义描述的平面图的模式进行匹配查询。具体地，使用可能世界概率模型定义不确定平面图，基于该模型，研究了不确定模式匹配(UPM)查询。首先给出一个确定算法可避免枚举所有的可能世界，同时给出改进的确定算法可更快速地求解查询。其次设计出采样算法，可快速地估算出匹配概率，并具有较高的精确度。基于真实不确定平面图数据的大量实验验证了该设计。最后将该查询应用于肺部CT图像的分割，结果表明此方法优于经典的图像分割算法。

关键词: 不确定模式匹配, 可能世界, 匹配图, 确定算法, 采样算法