计算机应用 ›› 2011, Vol. 31 ›› Issue (04): 874-881.

• 数据库技术专题 • 上一篇    下一篇

面向不确定平面图的模式匹配查询

王国仁1,2,袁野1,2,张佳希1   

  1. 1. 东北大学 信息科学与工程学院,沈阳 110004
    2. 东北大学 医学影像计算教育部重点实验室,沈阳 110004
  • 收稿日期:2010-09-08 修回日期:2010-12-21 发布日期:2011-04-08 出版日期:2011-04-01
  • 通讯作者: 王国仁
  • 作者简介:王国仁(1966-),男,湖北崇阳人,教授,博士生导师,博士,CCF高级会员,主要研究方向:XML数据管理、查询处理与优化、概率数据库、生物信息学;
    袁野(1981-),男,辽宁沈阳人,博士研究生,CCF会员,主要研究方向:图数据库、概率数据库、P2P数据管理、数据隐私;
    张佳希(1985-),男,辽宁盘锦人,硕士研究生,主要研究方向:不确定图数据管理。
  • 基金资助:
    国家自然科学基金重点项目(60933001);国家自然科学基金资助项目(60873100);国家863计划项目(2009AA01Z150)

Pattern match queries oriented to uncertain planar graphs

Guo-ren WANG1,2,Ye YUAN1,2,Xi-jia ZHANG1   

  1. 1. College of Information Science and Engineering, Northeastern University, Shengyang Liaoning 110004, China
    2. Key Laboratory of Medical Image Computing, Ministry of Education, Northeastern University, Shenyang Liaoning 110004, China
  • Received:2010-09-08 Revised:2010-12-21 Online:2011-04-08 Published:2011-04-01
  • Contact: Guo-ren WANG

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

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

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

中图分类号: