北大考研-计算机科学技术研究所研究生导师简介-刘家瑛_副教授

第４４卷　第１期２０２１年１月计 算 机 学 报ＣＨＩＮＥＳＥＪＯＵＲＮＡＬＯＦＣＯＭＰＵＴＥＲＳＶｏｌ．４４Ｎｏ．１Ｊａｎ．２０２１收稿日期：２０１９ ０３ ２２；在线发布日期：２０１９ １０ ３１．本课题得到国家重点研发计划项目（２０１８ＹＦＢ１００３４０４）、国家自然科学基金（Ｕ１８１１２６１，６１６７２１４２）、辽宁省科学技术基金（２０１８０５５０３２１）资助．于　戈，博士，教授，中国计算机学会（ＣＣＦ）会员，主要研究领域为分布式数据库、分布与并行计算、区块链．Ｅ ｍａｉｌ：ｙｕｇｅ＠ｍａｉｌ．ｎｅｕ．ｅｄｕ．ｃｎ．聂铁铮（通信作者），博士，副教授，中国计算机学会（ＣＣＦ）会员，主要研究方向为数据库、数据集成、区块链．Ｅ ｍａｉｌ：ｎｉｅｔｉｅｚｈｅｎｇ＠ｍａｉｌ．ｎｅｕ．ｅｄｕ．ｃｎ．李晓华，博士，讲师，中国计算机学会（ＣＣＦ）会员，主要研究方向为信息安全、区块链．张岩峰，博士，教授，中国计算机学会（ＣＣＦ）高级会员，主要研究领域为分布式数据处理、云计算．申德荣，博士，教授，中国计算机学会（ＣＣＦ）高级会员，主要研究领域为分布式数据库、数据集成．鲍玉斌，博士，教授，中国计算机学会（ＣＣＦ）高级会员，主要研究领域为数据仓库、ＯＬＡＰ．区块链系统中的分布式数据管理技术———挑战与展望于　戈　聂铁铮　李晓华　张岩峰　申德荣　鲍玉斌（东北大学计算机科学与工程学院　沈阳　１１０１６９）摘　要　区块链是在数字加密货币的应用基础之上发展起来的一种分布式数据库技术．区块链系统具有去中心化、不可篡改、分布共识、可溯源和最终一致性等特点，这使其可以用于解决不可信环境下数据管理问题．区块链独特的数据管理功能已经成为各领域应用中发挥区块链价值的关键．本文基于对比特币、以太坊、超级账本等代表性区块链系统的研究分析，阐述区块链系统中分布式数据管理技术．首先，深入讨论区块链系统与传统分布式数据库系统之间的异同点，从分布式部署模式、节点角色、链拓扑结构等多个方面给出区块链的分类．然后，详细分析各类区块链系统所使用的数据存储结构、分布式查询处理与优化技术及其优缺点．最后，总结区块链系统的分布式数据管理技术在各专门领域应用中所面临的挑战和发展趋势．关键词　区块链；分布式数据管理；数据存储；查询处理中图法分类号ＴＰ３１１ 犇犗犐号１０．１１８９７／ＳＰ．Ｊ．１０１６．２０２１．０００２８犜犺犲犆犺犪犾犾犲狀犵犲犪狀犱犘狉狅狊狆犲犮狋狅犳犇犻狊狋狉犻犫狌狋犲犱犇犪狋犪犕犪狀犪犵犲犿犲狀狋犜犲犮犺狀犻狇狌犲狊犻狀犅犾狅犮犽犮犺犪犻狀犛狔狊狋犲犿狊ＹＵＧｅ　ＮＩＥＴｉｅ Ｚｈｅｎｇ　ＬＩＸｉａｏ Ｈｕａ　ＺＨＡＮＧＹａｎ Ｆｅｎｇ　ＳＨＥＮＤｅ Ｒｏｎｇ　ＢＡＯＹｕ Ｂｉｎ（犛犮犺狅狅犾狅犳犆狅犿狆狌狋犲狉犛犮犻犲狀犮犲犪狀犱犈狀犵犻狀犲犲狉犻狀犵，犖狅狉狋犺犲犪狊狋犲狉狀犝狀犻狏犲狉狊犻狋狔，犛犺犲狀狔犪狀犵　１１０１６９）犃犫狊狋狉犪犮狋　Ｂｌｏｃｋｃｈａｉｎｉｓａｔｅｃｈｎｉｑｕｅｏｆｄｉｓｔｒｉｂｕｔｅｄｄａｔａｂａｓｅｗｈｉｃｈｉｓｄｅｖｅｌｏｐｅｄｗｉｔｈｔｈｅａｐｐｌｉｃａｔｉｏｎｓｏｆｄｉｇｉｔａｌｅｎｃｒｙｐｔｅｄｃｕｒｒｅｎｃｙ．Ａｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍｈａｓｔｈｅｃｈａｒａｃｔｅｒｉｓｔｉｃｓｏｆｄｅｃｅｎｔｒａｌｉｚａｔｉｏｎ，ｎｏｎ ｔａｍｐｅｒｉｎｇ，ｄｉｓｔｒｉｂｕｔｅｄｃｏｎｓｅｎｓｕｓ，ｐｒｏｖｅｎａｎｃｅａｎｄｅｖｅｎｔｕａｌｃｏｎｓｉｓｔｅｎｃｙ，ｗｈｉｃｈｍａｋｅｓｉｔｂｅａｐｐｌｉｅｄｔｏｓｏｌｖｅｄａｔａｍａｎａｇｅｍｅｎｔｐｒｏｂｌｅｍｓｏｆｔｈｅｕｎｔｒｕｓｔｅｄｅｎｖｉｒｏｎｍｅｎｔｓ．Ｔｈｅｄａｔａｍａｎａｇｅｍｅｎｔｆｕｎｃｔｉｏｎｏｆａｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍｈａｓａｌｒｅａｄｙｂｅｃｏｍｅｔｈｅｉｍｐｏｒｔａｎｔｆｅａｔｕｒｅｆｏｒｐｌａｙｉｎｇｉｔｓｖａｌｕｅｉｎｔｈｅａｐｐｌｉｃａｔｉｏｎｓｏｆｄｉｆｆｅｒｅｎｔｄｏｍａｉｎｓ．Ｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍｓｍａｋｅｅｖｅｒｙｎｏｄｅｃｏｎｔａｉｎａｃｏｍｐｌｅｔｅｃｏｐｙｏｆｌｅｄｇｅｒｄａｔａ，ａｎｄｕｓｅｄｉｓｔｒｉｂｕｔｅｄｃｏｎｓｅｎｓｕｓａｌｇｏｒｉｔｈｍｓｔｏｅｎｓｕｒｅｔｈｅｃｏｎｓｉｓｔｅｎｃｙｏｆｄａｔａ．Ｔｈｅｒｅｆｏｒｅ，ａｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍｉｓａｎｅｗｋｉｎｄｏｆｄｉｓｔｒｉｂｕｔｅｄｄａｔａｍａｎａｇｅｍｅｎｔｓｙｓｔｅｍｓｃｏｍｐａｒｅｄｗｉｔｈｔｒａｄｉｔｉｏｎａｌｄｉｓｔｒｉｂｕｔｅｄｄａｔａｂａｓｅｓｙｓｔｅｍｓ．ＷｉｔｈａｎａｌｙｚｉｎｇｔｈｅｒｅｐｒｅｓｅｎｔａｔｉｖｅｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍｓｉｎｃｌｕｄｉｎｇＢｉｔｃｏｉｎ，ＥｔｈｅｒｅｕｍａｎｄＨｙｐｅｒｌｅｄｇｅｒＦａｂｒｉｃ，ｔｈｉｓｐａｐｅｒｆｏｃｕｓｅｓｏｎｔｈｅｄｉｓｔｒｉｂｕｔｅｄｄａｔａｍａｎａｇｅｍｅｎｔｔｅｃｈｎｉｑｕｅｓｉｎｅｘｉｓｔｉｎｇｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍｓ，ｗｈｉｃｈｃｏｖｅｒｓｑｕｅｒｙｐｒｏｃｅｓｓｉｎｇ，ｓｍａｒｔｃｏｎｔｒａｃｔ，ｎｅｔｗｏｒｋｃｏｍｍｕｎｉｃａｔｉｏｎ，ａｎｄｄａｔａｓｔｏｒａｇｅｌａｙｅｒｓｉｎｔｈｅａｒｃｈｉｔｅｃｔｕｒｅｏｆｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍｓ．Ｔｈｉｓｐａｐｅｒｆｉｒｓｔｄｉｓｃｕｓｓｅｓｔｈｅｍａｉｎｄｉｆｆｅｒｅｎｃｅｓａｎｄｓｉｍｉｌａｒｉｔｉｅｓｂｅｔｗｅｅｎａｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍａｎｄａｔｒａｄｉｔｉｏｎａｌｄｉｓｔｒｉｂｕｔｅｄｄａｔａｂａｓｅｓｙｓｔｅｍ．Ｊｕｓｔｌｉｋｅａｄｉｓｔｒｉｂｕｔｅｄｄａｔａｂａｓｅｓｙｓｔｅｍ，ａｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍｈａｓｆｅａｔｕｒｅｓｏｆｄｉｓｔｒｉｂｕｔｉｏｎ，ｔｒａｎｓｐａｒｅｎｃｙ，ａｕｔｏｎｏｍｙａｎｄｓｃａｌａｂｉｌｉｔｙｏｎｍａｎａｇｉｎｇｄａｔａ，ｂｕｔｉｔｉｓａｌｓｏｄｉｆｆｅｒｅｎｔｆｒｏｍｍｏｓｔｏｆｄｉｓｔｒｉｂｕｔｅｄｄａｔａｂａｓｅｓｙｓｔｅｍｓｏｎｔｏｐｏｌｏｇｉｃ，ｄａｔａｄｉｓｔｒｉｂｕｔｉｏｎ，ｑｕｅｒｙｐｒｏｃｅｓｓｉｎｇ，ｃｏｎｓｉｓｔｅｎｃｙａｎｄｓｅｃｕｒｉｔｙｍｅｃｈａｎｉｓｍ．Ｔｈｅｎ，ｔｈｉｓｐａｐｅｒｐｒｅｓｅｎｔｓｔｈｅｃｌａｓｓｉｆｉｃａｔｉｏｎｏｆｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍｓｏｎｄｉｆｆｅｒｅｎｔａｓｐｅｃｔｓｏｆｄｉｓｔｒｉｂｕｔｅｄｄｅｐｌｏｙｍｅｎｔｓｔｙｌｅｓ，ｎｏｄｅｒｏｌｅｓａｎｄｔｏｐｏｌｏｇｉｃａｌｓｔｒｕｃｔｕｒｅｓ．Ｗｉｔｈｔｈｅｄｅｖｅｌｏｐｍｅｎｔｏｆｂｌｏｃｋｃｈａｉｎｔｅｃｈｎｏｌｏｇｙ，ｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍｓａｒｅｄｅｓｉｇｎｅｄｔｏａｄａｐｔｂｌｏｃｋｃｈａｉｎａｐｐｌｉｃａｔｉｏｎｅｎｖｉｒｏｎｍｅｎｔｓ．Ｔｈｅｍｏｄｅｌｓｏｆｐｕｂｌｉｃｂｌｏｃｋｃｈａｉｎ，ｃｏｎｓｏｒｔｉｕｍｂｌｏｃｋｃｈａｉｎａｎｄｐｒｉｖａｔｅｂｌｏｃｋｃｈａｉｎａｒｅｐｒｏｐｏｓｅｄ，ａｎｄｆｕｎｃｔｉｏｎｓｏｆｂｌｏｃｋｃｈａｉｎａｒｅｒｅｇｒｏｕｐｅｄａｎｄｄｅｐｌｏｙｅｄｔｏｍａｋｅｎｏｄｅｓｐｌａｙｄｉｆｆｅｒｅｎｔｒｏｌｅｓｉｎａｓｙｓｔｅｍ．Ｍｏｒｅｏｖｅｒ，ｔｈｅｍｕｌｔｉｐｌｅｔｏｐｏｌｏｇｉｃｓｔｒｕｃｔｕｒｅｓｏｆｂｌｏｃｋｃｈａｉｎａｒｅｐｒｏｐｏｓｅｄ．Ｂｅｓｉｄｅｓｔｈｅｃｈａｉｎｓｔｒｕｃｔｕｒｅｏｆｔｒａｄｉｔｉｏｎａｌｂｌｏｃｋｃｈａｉｎ，ｔｈｅＤＡＧｓｔｒｕｃｔｕｒｅｓ，ｓｕｃｈａｓＴａｎｇｌｅａｎｄＬａｔｔｉｃｅ，ａｒｅａｐｐｌｉｅｄｔｏｉｍｐｒｏｖｅｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍｓ．Ｔｈｉｒｄｌｙ，ｔｈｉｓｐａｐｅｒａｎａｌｙｚｅｓｔｈｅｔｅｃｈｎｉｑｕｅｓｏｆｄｉｓｔｒｉｂｕｔｅｄｄａｔａｓｔｏｒａｇｅｍａｎａｇｅｍｅｎｔ，ｄｉｓｔｒｉｂｕｔｅｄｑｕｅｒｙｐｒｏｃｅｓｓｉｎｇａｎｄｏｐｔｉｍｉｚａｔｉｏｎｕｓｅｄｉｎｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍｓａｎｄｄｉｓｃｕｓｓｅｓｔｈｅｉｒａｄｖａｎｔａｇｅｓａｎｄｄｉｓａｄｖａｎｔａｇｅｓ．Ｓｐｅｃｉｆｉｃａｌｌｙ，ｔｈｅｄａｔａｓｔｏｒａｇｅｔｅｃｈｎｉｑｕｅｓｏｆｅｘｉｓｔｉｎｇｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍｓａｒｅｄｅｅｐｌｙａｎａｌｙｚｅｄ，ｉｎｃｌｕｄｉｎｇｔｈｅｄａｔａｓｔｒｕｃｔｕｒｅｓｏｆｓｔｏｒａｇｅ，ａｓｗｅｌｌａｓｔｈｅｏｒｇａｎｉｚａｔｉｏｎｏｆｄａｔａｆｉｌｅｓａｎｄｏｐｔｉｍｉｚａｔｉｏｎｔｅｃｈｎｉｑｕｅｓ．Ｋｅｙ ＶａｌｕｅｄａｔａｂａｓｅｓｓｕｃｈａｓＬｅｖｅｌＤＢａｒｅｕｓｕａｌｌｙｕｓｅｄｉｎｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍｓｔｏｉｍｐｒｏｖｅｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆａｃｃｅｓｓｉｎｇｌｅｄｇｅｒｄａｔａａｎｄｓｔａｔｅｄａｔａ．Ｃｕｒｒｅｎｔｌｙ，ｍｏｒｅｒｅｓｅａｒｃｈｗｏｒｋｓｆｏｃｕｓｏｎｕｓｉｎｇｄｉｆｆｅｒｅｎｔｍｅｔｈｏｄｓ，ｉｎｃｌｕｄｉｎｇｄａｔａｂａｓｅ，ｉｎｄｅｘａｎｄｄｉｓｔｒｉｂｕｔｅｄｓｔｏｒａｇｅ，ｔｏｏｐｔｉｍｉｚｅｔｈｅｓｔｏｒａｇｅｏｆｂｌｏｃｋｃｈａｉｎ．Ｔｈｉｓｐａｐｅｒａｌｓｏａｎａｌｙｚｅｓｖａｒｉｏｕｓｑｕｅｒｉｅｓｉｎｔｈｅｅｘｉｓｔｉｎｇｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍｓａｎｄｃｌａｓｓｉｆｉｅｓｔｈｅｍｉｎｔｏｔｈｒｅｅｔｙｐｅｓ：ａｃｃｏｕｎｔｑｕｅｒｙ，ｔｒａｎｓａｃｔｉｏｎｑｕｅｒｙａｎｄｃｏｎｔｒａｃｔｑｕｅｒｙ．Ｔｈｅｄｉｓｔｒｉｂｕｔｅｄｑｕｅｒｙｐｒｏｃｅｓｓｉｎｇｔｅｃｈｎｉｑｕｅｓｕｓｅｄｉｎｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍｓａｒｅｄｉｓｃｕｓｓｅｄ．Ｆｏｕｒｔｈｌｙ，ｔｈｉｓｐａｐｅｒｐｏｉｎｔｓｏｕｔｔｈｅｃｈａｌｌｅｎｇｅｓａｎｄｄｅｖｅｌｏｐｍｅｎｔｔｒｅｎｄｓｏｆｄｉｓｔｒｉｂｕｔｅｄｄａｔａｍａｎａｇｅｍｅｎｔｔｅｃｈｎｉｑｕｅｓｆｏｒｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍｓ，ｉｎｃｌｕｄｉｎｇｄｉｓｔｒｉｂｕｔｅｄｓｔｏｒａｇｅｆｏｒｂｌｏｃｋｃｈａｉｎｄａｔａ，ｅｆｆｉｃｉｅｎｔａｎｄｓｅｃｕｒｅｃｏｎｓｅｎｓｕｓｍｅｃｈａｎｉｓｍｆｏｒｂｌｏｃｋｃｈａｉｎｔｒａｎｓａｃｔｉｏｎｓ，ｈｉｇｈａｖａｉｌａｂｌｅｑｕｅｒｙｐｒｏｃｅｓｓｉｎｇ，ｄｉｓｔｒｉｂｕｔｅｄｍａｎａｇｅｍｅｎｔｏｆｓｍａｒｔｃｏｎｔｒａｃｔｓ，ｐｒｉｖａｃｙｐｒｏｔｅｃｔｉｏｎｆｏｒｂｌｏｃｋｃｈａｉｎｄａｔａ，ｄａｔａａｕｄｉｔａｎｄｍｏｎｉｔｏｒｉｎｇｉｎｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍ．Ｆｉｎａｌｌｙ，ｔｈｉｓｐａｐｅｒｓｈｏｗｓｔｈｅｄｉｓｔｒｉｂｕｔｅｄｄａｔａｍａｎａｇｅｍｅｎｔｏｆｂｌｏｃｋｃｈａｉｎｓｙｓｔｅｍｓｉｎｖａｒｉｏｕｓｄｏｍａｉｎ ｓｐｅｃｉｆｉｃａｐｐｌｉｃａｔｉｏｎｓ，ｓｕｃｈａｓｆｉｎａｎｃｅ，ｍａｎｕｆａｃｔｕｒｅ，ｎｅｔｗｏｒｋｓｔｏｒａｇｅ，ｃｒｅｄｉｔａｎｄｏｔｈｅｒｆｉｅｌｄｓ．犓犲狔狑狅狉犱狊　ｂｌｏｃｋｃｈａｉｎ；ｄｉｓｔｒｉｂｕｔｅｄｄａｔａｍａｎａｇｅｍｅｎｔ；ｄａｔａｓｔｏｒａｇｅ；ｑｕｅｒｙｐｒｏｃｅｓｓｉｎｇ１　引　言在“互联网＋”应用日益普及的大环境下，大量应用需要将发生的事件、行为、状态持久地记录在分布式环境中以用于日后的查询，即进行分布式记账．分布式记账已经逐渐成为互联网应用中的一项重要功能．以电子商务交易系统为例，客户需要执行提交订单、通过电子银行向商家支付货款、从物流公司收货等操作，商家需要执行接受订单、通过物流公司发货、通过电子银行收款等操作，电子银行方需要执行从客户收款、向商家付款等操作，物流公司需要执行从商家收货、收取物流款、向客户发货等操作．客户、商家、物流公司、电子银行共四方处于一个分布式环境中，在每一个环节都需要记录相关的操作和信息．由于各方之间并不存在完全信任关系，最终以哪一方记录的账目为确认信息是一个重要的问题．传统的方法采用由电子商务交易服务平台作为公正的第三方进行统一记账，所有的交易信息的查询操作全部在这个平台上进行处理，物流公司和银行的部分数据也以接入的方式添加至交易服务平台．在这种传统集中式记账方式里，主要的交易信息存储在单一的记账方，这是一种“逻辑”上的集中式存储模式，即交易数据存储在唯一的某业务参与方并由其负责管理．集中式记账方式存在的问题包括：（１）记账方为了保证可靠性需要存储数据的多个副本，从而造成了数据存储的性能瓶颈；（２）交易数据可能被记账方篡改且无法验证，因此各参与方需要完全信任记账方；（３）记账方受到攻击后数据难以恢复．因此，传统集中式记账方式存在着存储效率低、可信性差、易受攻击等弊端．为了解决以上难题，采用分布式记账方式的比９２１期于　戈等：区块链系统中的分布式数据管理技术———挑战与展望特币系统（Ｂｉｔｃｏｉｎ）［１］在２００８年被首次提出，并受到广泛关注．随后，区块链技术作为比特币系统所采用的底层技术逐渐引起工业界与学术界的重视，比特币系统所具有的分布共享性、共识性、不可篡改性、可溯源性和最终一致性等特点均来源于区块链技术．在基于区块链技术的分布式记账方式中，所有参与方都可以保存一份相同的完全账本，新加入的参与方可以下载完全账本并验证账本的正确性．这种方式降低了传统集中式记账方式中记账方的多副本数据维护成本，同时参与方也可以通过访问本地数据提高访问效率．此外，在区块链系统中，交易的账目采用数字签名和加密算法处理，从而提高了系统中数据的安全性，而区块之间通过哈希值串联的数据关联方式和基于共识算法确认区块的数据写入机制也使得区块链上的数据极难被篡改．起初，区块链技术所支撑的比特币系统仅是一个专用的交易系统，并不支持虚拟货币交易以外的其他功能，这严重限制了区块链技术在分布式数据管理上的应用．随着区块链技术的发展，产生了大量新型区块链系统．２０１４年由Ｂｕｔｅｒｉｎ基于区块链技术推出了以太坊（Ｅｔｈｅｒｕｍ）平台［２］．以太坊提供了基于智能合约的编程功能，支持区块链应用的二次开发，这标志着区块链２．０时代的诞生．超级账本（ＨｙｐｅｒｌｅｄｇｅｒＦａｂｒｉｃ）［３］则是基于ＩＢＭ早期贡献出的ＯｐｅｎＢｌｏｃｋｃｈａｉｎ为主体搭建而成的Ｌｉｎｕｘ基金会的区块链项目，其主要目的是发展跨行业的商用区块链平台技术．在超级账本框架中，包括了ＨｙｐｅｒｌｅｄｇｅｒＦａｂｒｉｃ①、ＨｙｐｅｒｌｅｄｇｅｒＢｕｒｒｏｗ②、ＨｙｐｅｒｌｅｄｇｅｒＳａｗｔｏｏｔｈ③和ＨｙｐｅｒｌｅｄｇｅｒＩｒｏｈａ等多个项目，构成了完整的生态环境．区块链３．０时代［４］则是将区块链技术的应用范围扩展到各类应用之中，服务领域除金融、经济之外，还包括政府、健康、科学、文化等领域．区块链技术将支持各类资产交易与登记的去中心化可信处理，并与物联网等技术融合．未来，区块链技术将会与其他新兴技术相结合用于各类应用之中，诸如区块链＋科学、区块链＋医疗、区块链＋教育、区块链＋能源等应用将会迅速发展．目前，区块链技术已应用于多个领域之中．在数字货币服务领域，支持支付、兑换、汇款、交易功能；在金融服务领域，支持清算、结算、安全监管、反洗钱等功能；在Ｂ２Ｃ服务领域，支持无人管理的商亭等新业务；在Ｐ２Ｐ租赁管理领域，支持无需中介的货物交换、租赁等共享经济新业务；在供应链管理领域，支持物理资产签名、物流跟踪和交付等功能；在知识产权保护领域，用于建立不可篡改的权利和拥有权；在征信管理领域，支持身份认证、日志审计和监管等；在溯源管理领域，支持数据鉴别与存证、防伪溯源等功能．区块链技术是一种建立在多种技术之上的分布式共享账本技术，而区块链本质上是一种多方参与共同维护的分布式数据库．相对于集中式数据库管理系统，区块链系统采用去中心化或者弱中心化的数据管理模式，没有中心节点，所有参与节点均可以存储数据，而事务的持久性则依靠参与节点共同维护的不断增长的数据链和非集中式的共识机制予以实现，保证了数据在基于验证基础上的可信性．此外，相比于传统的分布式数据库和分布式数据存储系统，区块链系统的参与节点可以获得完整的数据副本，而非部分数据的副本．区块链系统的特殊数据存储机制和一致性共识机制是其不同于传统分布式数据库系统的主要原因．区块链的数据存储结构和数据组织方式不同于其他数据存储系统．区块链将数据记录组织成区块（Ｂｌｏｃｋ），并在每个区块的区块头中通过记录前一区块的哈希值将区块组织成链式结构．这种结构使区块链的数据存储具有不易篡改性、可溯源性和可验证性．然而，区块链的存储结构和基于密码学算法的共识机制也为数据管理带来了交易确认效率低和查询不便等诸多弊端．例如在记录交易的吞吐量方面，使用区块链技术的比特币系统仅支持每秒处理７笔交易数，并且还需要经过１小时以上时间才可以确认写到区块（相关研究表明４３％的比特币交易未能在一小时内得到处理④）．此外，区块链的数据记录按时间顺序存储在区块中，这为交易数据的查询处理带来了挑战，当前很多数字货币系统的查询处理都要依赖于某种键值数据库系统．其次，区块链的共识机制也不同于分布式数据库系统．区块链系统为了在Ｐ２Ｐ网络环境下保证交易操作符合事务特性，需要维护数据一致性，并避免“双重支付”（ＤｏｕｂｌｅＳｐｅｎｄｓ）的发生，这是区块链共０３计 算 机 学 报２０２１年①②③④ＨｙｐｅｒｌｅｄｇｅｒＦａｂｒｉｃ．ｈｔｔｐｓ：／／ｗｗｗ．ｈｙｐｅｒｌｅｄｇｅｒ．ｏｒｇ／ｐｒｏｊｅｃｔｓ／ｆａｂｒｉｃＨｙｐｅｒｌｅｄｇｅｒＢｕｒｒｏｗ．ｈｔｔｐｓ：／／ｗｗｗ．ｈｙｐｅｒｌｅｄｇｅｒ．ｏｒｇ／ｐｒｏｊｅｃｔｓ／ｈｙｐｅｒｌｅｄｇｅｒ ｂｕｒｒｏｗＨｙｐｅｒｌｅｄｇｅｒＳａｗｔｏｏｔｈ．ｈｔｔｐｓ：／／ｗｗｗ．ｈｙｐｅｒｌｅｄｇｅｒ．ｏｒｇ／ｐｒｏｊｅｃｔｓ／ｓａｗｔｏｏｔｈＳｔｕｄｙ：４３％ｏｆＢｉｔｃｏｉｎＴｒａｎｓａｃｔｉｏｎｓＡｒｅｎ’ｔＰｒｏｃｅｓｓｅｄａｆｔｅｒＦｉｒｓｔＨｏｕｒ．２０１７．ｈｔｔｐｓ：／／ｗｗｗ．ｃｃｎ．ｃｏｍ／４３ ｂｉｔｃｏｉｎ ｔｒａｎｓａｃｔｉｏｎｓ ｎｏｔ ｐｒｏｃｅｓｓｅｄ ｏｎｅ ｈｏｕｒ ｓｔｕｄｙ ｓａｙｓ识机制的主要考虑的问题．同时，由于区块链网络本身是一个去中心化的网络，参与节点完全自治，并没有统一的节点负责管理和维护，为此区块链节点之间需要使用Ｐ２Ｐ技术实现数据广播以更新节点的状态信息和账本信息．区块链系统公认的基础架构模型［５］主要分为６层，本文在其基础上增加了查询层，以便对区块链系统的查询处理机制进行分析．这样，区块链系统架构扩展为７层，如图１所示，主要包括：（１）应用层．基于区块链的各类应用，如数字货币、区块链金融、区块链征信等；（２）查询层．实现对交易账本数据的访问和验证，以及对账号状态的查询；（３）合约层．由脚本、算法机制和智能合约所构成的可编程基础框架；（４）激励层．负责为奖励记帐工作而进行货币发行、交易费用分配任务；（５）共识层．封装网络节点的ＰｏＷ、ＰｏＳ、ＤＰｏＳ和ＰＢＦＴ等各类共识算法，实现分布式共识机制；（６）网络层．封装Ｐ２Ｐ组网机制，数据传播机制和数据验证机制；（７）数据层．封装底层数据区块的数据结构和加密机制．当前的区块链系统大多基于该系统架构进行实现，其中数据层、网络层、共识层和查询层是区块链系统的必要元素．现有相关工作针对区块链系统不同层次的技术和区块链在各领域上的应用进行了大量研究与综述．对于区块链系统所包含的关键技术和研究现状，以及未来的发展趋势，袁勇等人［５］在区块链的基础架构模型方面对比特币的原理和技术进行了系统的阐述，何蒲等人［６］结合比特币系统介绍了区块链的概念和技术，并对前景进行了展望，邵奇峰等人［７］对比特币、以太坊和超级账本等多个区块链平台进行分析，总结了区块链的优势、劣势和发展趋势．在应用层方面，文献［８］对区块链在数字货币上的应用进行了全面的综述，刘敖迪等人［９］介绍了区块链技术在信息安全领域的研究现状和进展．由于区块链具有健壮的数据存储能力，因此相关研究工作在数据存储系统上进行区块链技术的应用［１０ １１］．对于合约层，贺海武等人［１２］结合多个领域应用场景对智能合约技术的概念、关键技术和面临的问题进行了阐述．此外，对于共识层、网络层和数据层，已有研究分别对区块链系统的共识机制［１３ １４］、安全机制［１５ １６］、网络协议［１７］、可信数据管理［１８］和查询处理［１９］进行了整理和综述．区块链在设计之初就是以进行防篡改的数据存储和管理为目的，分布式数据管理是区块链系统的主要功能之一．区块链技术中涉及分布式数据管理的部分主要集中在区块链架构的查询层、合约层、网络层和数据层，其中查询层和合约层在区块链系统中负责实现对数据的处理操作，如图１所示．本文主要以分布式数据管理为视角，基于对当前主流的区块链系统分析，对比不同区块链系统在数据管理上的差异，对其中分布式数据管理所涉及的数据存储技术、查询处理机制和算法进行阐述和分析，并对区块链研究中涉及分布式数据管理的挑战进行探讨，对各领域的应用进行展望．本文第２节对区块链系统的分布式数据管理机制进行分析，对比区块链系统和传统分布式数据管１３１期于　戈等：区块链系统中的分布式数据管理技术———挑战与展望理系统的异同；第３节介绍区块链系统的分类；第４节介绍区块链系统中的数据存储技术，包括物理存储结构，对比不同区块链系统在物理存储机制上的差异，以及区块链系统所采用的数据存储优化技术；第５节介绍区块链系统的数据查询处理技术；第６节探讨区块链系统在分布式数据管理方面所面临的研究挑战和发展方向；第７节展望区块链所支持领域应用的场景和待解决的问题；第８节总结全文．２　区块链系统的分布式数据管理区块链系统作为一种分布式数据库管理系统，主要以解决数字货币的货币转移、兑换和支付功能而被提出．区块链的特征主要体现在数据的公开透明、不可篡改和网络结构的去中心化等几个方面．由于区块链主要面向的是不可信数据存储环境下的记账应用，因此在数据存储上采用了去中心化、全副本的分布式方式，即所有参与方均通过Ｐ２Ｐ网络结构连接，并可以存储完整的共享账本．由此可见，区块链系统在管理交易记账上虽然使用了分布式数据管理方式，但与传统的集中式数据管理和分布式数据库系统管理数据的方式均有所差别．本节主要将区块链系统与传统数据管理方式进行对比和分析，并阐述彼此间的共同点和差异性．图２　记账业务流程对比２ １　区块链与传统分布式数据库的共同点区块链技术主要是针对现有金融机构的集中式记账系统的信任问题而被提出的，其本身是由分布式存储、Ｐ２Ｐ网络、加密算法、共识机制等多种技术所构成的．中本聪基于区块链技术设计并发行了数字货币“比特币”，用以解决美国次贷危机中所展现的金融机构信任问题．相比于金融机构的集中式记账系统，基于区块链技术的交易记账系统具有公开透明、去中心化、可溯源查询和不可篡改等诸多的优势，从而避免了集中式记账方式中账本的真实性高度依赖于对记账方信任的弊端．这里以电子商务的交易记账应用为例，对传统基于清算中心的集中式记账方式和基于区块链的分布式记账方式的记账业务流程进行对比．传统集中式记账方式如图２（ａ）所示，交易相关的账目数据集中存储在清算中心的数据库中，交易的参与各方如果需要调用完整的交易信息需要访问清算中心，其弊端主要体现在完全依赖于对清算中心记账方的信任，一旦记账方失信或遭受攻击，其保存的数据也随之失去可信性．区块链的分布式记账方式如图２（ｂ）所示，其中账本数据是整体共享的，以区块为单位通过密码学算法链接在一起，且网络中任何一个参与方均可以存储完整的共享账本副本，而数据的安全性则也是基于密码学算法予以保证．由于所有参与方均保存有共识后的共享账本，因此任何一个参与方进行双重支付或篡改账本数据的难度变得极大，从而保证账本数据在不可信环境中的可信性．区块链系统的分布式记账方式使其在数据存储管理的方式上与分布式数据库相同，即存储结构化的数据集合，这些数据逻辑上属于同一系统，物理上分布在计算机网络的各个不同场地上［１７］．区块链系统同样具有分布式数据库所具有的诸多特性：（１）分布性区块链系统与分布式数据库系统在数据的存储方面都是物理上分散、逻辑上统一的系统．区块链系统中具有全局统一的数据模式，数据以副本形式存储在参与节点中，每个参与节点存储的是数据模式相同且数据一致的共享账本．（２）透明性区块链系统在数据访问上具有透明性，用户看到的共享账本是全局数据模型的描述，就如同使用集中式数据库一样，在记录交易数据时也不需要考虑共享账本的存储场地和操作的执行场地．在数据复制方面，区块链系统的共享账本存储在各个参与节点上，并通过共识机制自动维护数据的一致性．２３计 算 机 学 报２０２１年（３）自治性区块链系统的参与节点具有高度的自治性．在通信方面，参与节点可以独立地决定如何与其他参与者进行通信；在查询方面，参与节点本地就保存了完整的共享账本，可以在本地执行对账本数据的访问．（４）可伸缩性区块链系统支持参与节点规模的任意扩展．区块链系统允许参与节点在任意时刻加入和退出系统．而且，由于区块链的参与节点保存的是完整共享账本，因此对于参与节点重新加入区块链系统后，仅需要从其他节点更新缺失的区块数据即可完成数据的重新分布，不会影响整体的系统性能．２ ２　区块链与传统分布式数据库的差异区块链系统原始的设计目的之一是解决非信任环境下数据的可信性问题．所谓的非信任环境是指负责数据存储的节点可能随意篡改数据而其他参与节点又无法识别，这将造成参与节点之间的互不信任问题．对于传统分布式数据库管理系统而言，系统建立在信任环境，其中参与节点采用统一管理的方式，节点之间具备完全相互信任的关系．因此区块链与传统的分布式数据库在数据管理方式上又具有显著的差异，如图３所示，具体体现在以下几个方面：（１）去中心化拓扑结构在参与节点的网络拓扑结构方面，区块链系统的去中心化结构采用了基于Ｐ２Ｐ的分布式模式，这种结构与基于Ｐ２Ｐ网络结构［２０］的数据库系统（Ｐ２ＰＤＢＳ）［２１ ２２］相似．如图３（ｂ）所示，区块链节点通过通信控制器（ＣＭ）仅基于邻居地址进行通信，其加入和退出都是随意和动态的．传统分布式数据库虽然数据分布在不同的场地，但是通常采用中心化的主从结构，由全局的网络管理层存储各个局部数据库节点的地址和局部数据的模式信息，以用于查询处理时进行全局优化和调度，如图３（ａ）所示．（２）数据分布方式分布式数据管理的数据存储方式，通常分为两类［２３］：①分割式．数据被划分成若干个不相交的分片，分别保存在不同的节点上，数据的划分方法分为水平分片和垂直分片；②复制式．同一个数据分片保存在一个以上的节点上，复制方式分为部分复制和全复制．分割式能够节省数据的存储空间，查询时需要在节点间传输数据，虽然使用半连接等算法可进行优化，但效率依然较低．复制式通过多节点的数据冗余存储可提高查询效率，但耗费存储空间且需要维护数据一致性．区块链系统的数据分布采用的是全复制式，即每个参与节点都在本地复制了具有全局模式的全部数据．因此，数据在区块链系统中是全局共享的，如图３（ｂ）所示．相比于区块链系统，传统分布式数据库的分布方式主要基于在全局模式创建局部模式，再对数据进行垂直分片和水平分片，如图３（ａ）所示，每个节点存储的是全局数据分片的副本，再通过数据分片的元信息管理实现全局数据的访问和查询处理．当前很多基于分布式数据库技术的大数据存储系统，如ＨＢａｓｅ①等，均采用集中式的元信息管理节点管理数据副本的分布信息．图３　区块链系统与传统分布式数据库系统对比（３）数据查询处理区块链系统中对账本信息的查询处理通常在存３３１期于　戈等：区块链系统中的分布式数据管理技术———挑战与展望①ＡｐａｃｈｅＨＢａｓｅＲｅｆｅｒｅｎｃｅＧｕｉｄｅ．ｈｔｔｐ：／／ｈｂａｓｅ．ａｐａｃｈｅ．ｏｒｇ／ｂｏｏｋ．ｈｔｍｌ储了完整共享数据的参与节点本地执行．由于区块数据采用基于文件的存储方式且本身缺少索引结构，因此在区块链上直接执行对账本查询只能使用顺序扫描的方式访问所有区块数据．目前区块链系统常用的查询优化方式是将账本记录存储在Ｋｅｙ Ｖａｌｕｅ数据库中，以提高数据的访问效率．当前，比特币和以太坊等系统都使用了ＬｅｖｅｌＤＢ①存储和检索数据．需要说明的是，在以太坊这类支持智能合约的第二代区块链系统中，智能合约代码的执行处理是嵌入在区块链记账功能中的．因此，对智能合约代码的调用是在所有参与进行共识验证的节点上执行．传统分布式数据库的查询处理主要基于数据副本的大小和分布场地进行优化［２４］，而在面向大数据的分布式数据库上则采用基于并行计算思想的查询优化方法［２５］．（４）数据一致性维护数据一致性是保证数据正确性和可信性的关键，区块链系统采用共识机制来保证各节点上数据的一致性．在数字货币的应用中通常采用工作量证明机制（ＰｏＷ）通过算力竞争保证分布式的一致性［２６］，如解决基于ＳＨＡ２５６、Ｅｔｈａｓｈ②等算法的数学难题，而从节约能耗的角度，则会采用权益证明机制（Ｐｒｏｏｆ ｏｆ Ｓｔａｋｅ，ＰｏＳ）和授权权益证明机制（ＤｅｌｅｇａｔｅｄＰｒｏｏｆ ｏｆ Ｓｔａｋｅ，ＤＰｏＳ）等③方法．其中，使用工作量证明机制进行一致性维护的最大问题在于共识的效率过低，一个区块的一致性需要在其后生成一定长度的后续区块之后才能够被确认．分布式数据库系统通常采用包括实用拜占庭容错ＰＢＦＴ［２７］、Ｐａｘｏｓ［２８］、Ｇｏｓｓｉｐ［２９］、ＲＡＦＴ［３０］等高效的算法维护数据的一致性，而这些算法也被一些面向联盟链应用的区块链系统所采用．（５）数据安全性机制区块链系统在安全性方面主要为用户提供了数据篡改验证、数据溯源和加密安全机制．数据的篡改可以通过校验前后区块的哈希值进行验证，因此要篡改数据并被所有参与者认可就需要在算力上付出高昂代价以重新生成区块，其难度相比传统的集中式和分布式数据库都要大很多．但是在数据的可访问性上，由于区块链的共享性，所有用户均可访问完整数据，而传统数据库管理系统则基于用户身份验证方式控制数据的访问．为了解决共享数据上的隐私安全性问题，区块链采用了基于非对称加密的交易方式实现匿名交易，其优点是很好地保护了用户隐私，缺点是一旦密钥丢失，用户的账号信息将无法恢复．综上所述，区块链系统相比传统分布式数据库系统，在记账方式上提供了更好的分布性、透明性和可信性，在功能上提供了防篡改验证机制和智能合约机制，因此更加适合在非可信环境下的匿名使用．另一方面，相比传统的分布式数据库系统，区块链系统在网络结构、数据存储和访问方式上也具有显著的差异．３　区块链系统的分类３ １　区块链系统部署方式的分类区块链系统根据其分布式部署方式和开放对象被划分为三种：“公有链”（ＰｕｂｌｉｃＢｌｏｃｋｃｈａｉｎ）、“联盟链”（ＣｏｎｓｏｒｔｉｕｍＢｌｏｃｋｃｈａｉｎ）和“私有链”（ＰｒｉｖａｔｅＢｌｏｃｋｃｈａｉｎ）．三类区块链系统的对比如表１所示．表１　各区块链系统类型对比公有链联盟链私有链网络结构完全去中心化部分去中心化（多）可信中心节点规模无控制可控有限加入机制随时可以参加特定群体或有限第三方机构内部节点记账方任意参与节点预选节点机构内部节点数据读取任意读取受限读取受限读取共识机制容错性高、交易效率低（ＰｏＷ或ＰｏＳ等）容错性和交易效率适中（ＰＢＦＴ，ＲＡＦＴ）容错性低、交易效率高（Ｐａｘｏｓ，ＲＡＦＴ）激励机制有代币激励无代币激励无代币激励代码开放完全开源部分开源或定向开源不开源（１）公有链公有链是对所有人开放的，任何互联网用户都能够随时加入并任意读取数据，能够发送交易和参与区块的共识过程．比特币和以太坊等虚拟货币系统就是典型的公有链系统．公有链是完全去中心化的结构，其共识机制主要采用ＰｏＷ、ＰｏＳ或ＤＰｏＳ等方式，将经济奖励和加密算法验证相结合，以保证经济奖励和共识过程贡献成正比．此外，公有链中程序开发者对系统的代码是完全开源的，而且开发者无权干涉用户．在分布式数据管理方面，公有链系统的优势和缺陷主要包括以下几个方面：４３计 算 机 学 报２０２１年①②③ＬｅｖｅｌＤＢ．ｈｔｔｐ：／／ｌｅｖｅｌｄｂ．ｏｒｇ／ＲａｙＪ．Ｅｔｈａｓｈ．ｈｔｔｐｓ：／／ｇｉｔｈｕｂ．ｃｏｍ／ｅｔｈｅｒｅｕｍ／ｗｉｋｉ／ｗｉｋｉ／ＥｔｈａｓｈＢｉｔｓｈａｒｅｓ．ＤｅｌｅｇａｔｅｄＰｒｏｏｆｏｆＳｔａｋｅ．ｈｔｔｐ：／／ｄｏｃｓ．ｂｉｔｓ ｈａｒｅｓ．ｏｒｇ／ｂｉｔｓｈａｒｅｓ／ｄｐｏｓ．ｈｔｍｌ。

·
YuxinPeng,CuihuaFang,XiaoouChen:UsingEarthMover'sDistanceforAudioClipRetrieval.PCM200
6
· 余 军 、 陈 晓 鸥 命 名 实 体 识 别 :One-at-a-timeorAll-at-once?Word-basedorCharacter-based ，
ICCC2007(ISTP)2007
·余军、杨建武、陈晓鸥，一种与 TDT 结合的增量多文档摘要方法，NCIRCS2007
·路斌、万小军、杨建武、陈晓鸥，《基于搜索引擎摘要的词汇语义褒贬计算》，计算机科学
爱考机构 中国高端考研第一品牌（保过 保录 限额）
爱考机构-北大考研-计算机科学技术研究所研究生导师 简介-陈晓鸥_ 研究员
陈晓鸥研究员
陈晓鸥，陈晓鸥，1960 年出生，研究员。1982 年毕业于国防科技大学计算机系计算机软件 专业。研究方向涉及数字音视频处理、数字图像处理、中文信息处理、数据挖掘、数字广播、 内容管理、数字电路辅助设计等领域。曾获国家广电总局科技创新奖一等奖、国防科技大学 科技进步二等奖、国家档案局优秀科技成果三等奖、中国科协期刊优秀学术论文奖、柯达奖 教金、CCID 中国信息技术创新人物奖等奖励。曾任文字信息处理国家重点实验室副主任、 北京大学计算机研究所副所长等职。现任中国中文信息学会常务理事。
研究方向： ·音乐概念识别与检索 ·安全监控视音频检索 ·数aoouChen,YuQianWu
，
DeshunYang,MUSICEMOTIONCLASSIFICATIONUSINGTF*IDFANDRHYMEBASEDONLY
RICS,InproceedingsofISMIR2011

所在院系
职称
数学与计算机学院 数学系 数学所 数学与计算科学学院 应用数学所 数学学院 数学系 数学科学学院 数学与统计学院
数学学院 数学科学学院 数学与信息科学学院 数学与计算机科学学院 数学系 应用数学所 数学所
理学院 数学系 数学系
理学院 数学系 数学科学学院 数学系 数学系 数学与计算机科学系 数学科学学院
数学学院 数学系 数学科学学院 数学系 数学科学学院 数学与统计学院 数学科学学院 数学系 数理信息学院数学系 理学院数学系 数学系 数学系 数学系
数学学院
数学科学学院 数学学院
讲师 研究生 教授 研究生 讲师 研究生 研究生 副教授 副教授 副教授 副教授 副教授 研究生 讲师 研究生 研究生 副教授 讲师
教授
117 杨迎球 男 安顺学院
数学与计算机科学系 讲师
56 姚光同 男 山姚海楼 男 北京工业大学
教授
83 姚廷富 男 贵州师范大学
数计学院
研究生
43 姚云飞 男 阜阳师范学院
数学与计算科学学院 教授
95 叶家琛 男 同济大学
数学系
教授
27 叶郁
男 中国科学技术大学
数学系
139 林增强 男
115 令狐荣涛 男
31 刘东
男
110 刘家春 男
152 刘建波 男
20 刘文德 男
55 陆珊年 男
53 罗翠玲 女
12 罗栗
男
112 罗勇贵 男
120 孟道骥 男
128 穆强
男
81 倪军娜 女
10 倪霖
女
40 宁群
男
89 裴玉峰 男
8 钱玲
女
84 任斌

计算机系2022-2022(2)研究生课程表学期2022春2022春2022春2022春2022春2022春2022春2022春2022春2022春2022春2022春2022春2022春2022春课程代码某033518/C033716CS28002某033533C033728某033537CS28001C033713某033530F033574某033514某033533某033525某033526F033569F033581课程名称程序语言理论计算复杂性高级论题学分/学时起止周3/483/482-17周3-10周1-16周1-16周1-11周1-16周1-16周1-16周1-8周1-12周1-16周1-16周1-16周6-13周10-17周上课时间任课教师上课地点陈瑞球楼309电院3-318陈瑞球楼312陈瑞球楼207陈瑞球楼309陈瑞球楼309电院3-414陈瑞球楼207陈瑞球楼312陈瑞球楼313陈瑞球楼219陈瑞球楼216陈瑞球楼207陈瑞球楼309陈瑞球楼311备注全英文课程星期四11-13节邓玉欣星期一11-13节傅育熙星期四11-13节星期四6-8节星期四3-5节高晓沨郁昱算法分析与理论(英语班)3/48可证明安全理论并行计算与并行算法现代移动通信与计算现代密码算法密码算法与协议神经网络理论与应用计算机图形学算法分析与理论机器学习生物信息学自然语言理解网络安全基础3/482/323/483/483/483/483/483/483/483/483/483/48全英文课程星期三11-13节过敏意星期五11-13节贾维嘉星期二11-13节刘胜利星期一6-8节星期一6-9节星期四6-9节星期三6-8节星期五6-8节星期四6-8节星期三6-9节星期三6-9节龙宇吕宝粮马利庄任庆生杨旸苑波赵海朱浩瑾/阮娜全英文课程全英文课程全英文课程全英文课程全英文课程上课时段上课时间(节次)1、2节08:00-09:403、4节10:00-11:405、6节12:00-13:407、8节14:00-15:409、10节16:00-17:4011、12节18:00-19:4011、12、13节18:00-20:20。

北京大学硕士研究生培养方案（报表）一级学科名称哲学专业名称科学技术哲学专业代码010108北京大学研究生院制表填表日期：1999年6月24日修订日期：2002年5月16日一学科(专业)主要研究方向二培养目标与学制及应修学分三课程设置(包括专题研讨课等)注：1. 序号第8-11的4门课程中至少必须选修3门。

2. 序号第12-13的2门课程中至少必须选修1门。

3. 补修课为推荐免试者开设，不计学分。

4. 研究生还可在导师指导下选修校内其他院、系、所、中心开设的有关课程。

P r o g r a m m e o f M a s t e r S t u d e n t C o u r s e sD i s c i p l i n e (一级学科)：P h i l o s o p h y S p e c i a l t y (二级学科)：P h i l o s o p h y o f S c i e n c e a n d T e c h n o l o g y*. N —n e e s s a r y ; C -c h o s e n ; M --m a k e -u p . **.S --S p r i n g s e m e s t e r ; A --A u t u m n s e m e s t e r四科研能力与水平及学位论文的基本要求五对新生能力、水平的基本要求及入学考试科目设置一北京大学博士研究生培养方案（报表）一级学科名称哲学专业名称科学技术哲学专业代码010108北京大学研究生院制表填表日期：1999年6月24日修订日期：2002年5月16日一学科（专业）主要研究方向二培养目标与学制及应修学分三 课程设置（包括讨论班等）P r o g r a m m e o f P h . D S t u d e n t C o u r s e sD i s c i p l i n e (一级学科)：P h i l o s o p h y S p e c i a l t y (二级学科)：P h i l o s o p h y o f S c i e n c e a n d T e c h n o l o g y*. N --n e c e s s a r y ; C -c h o s e n . **.S --S p r i n g s e m e s t e r ; A --A u t u m n s e m e s t e r课程内容提要四前沿讲座课（含讨论班）的基本要求五需阅读的主要经典著作和专业学术期刊目录六学习安排和综合考试的基本要求七科研能力与水平的基本要求八学位论文的基本要求1九对新生能力、水平的基本要求及入学考试科目设置北京大学直攻博、硕-博连读研究生培养方案（报表）一级学科名称哲学专业名称科学技术哲学专业代码010108北京大学研究生院制表填表日期：1999年6月24日修订日期：2002年5月16日说明：本报表中的学科（专业）主要研究方向、前沿讲座课（含讨论班）的基本要求、需阅读的主要经典著作与专业学术期刊目录、学位论文的基本要求等部分内容同博士研究生培养方案（报表）一培养目标与学制二课程设置（包括讨论班和属于硕士生层次的课程）注：1. 序号第8-11的4门课程中至少必须选修3门。

电子科技大学计算机学院导师及其科研能力介绍为方便大家报考我们学校,了解各位导师的学术和科研能力,科大考研网www.**将提供给大家详细的信息。

陈雷霆,1966年7月出生,男,现任电子科技大学计算机学院副教授、副院长,主管学院的科研、产业和外事工作,在职博士研究生;现为中国软件行业协会理事,四川省计算机学会理事。

主要研究方向:(1)信息安全;(2)网络多媒体与虚拟现实。

主要科研项目:国家“863-317-403”项目—综合业务多媒体通讯终端与系统;“八五”军事预研项目激光成像雷达系统;多媒体安全监控系统;“九五”军事预研项目激光防撞雷达系统;总装备部项目军用移动图象采集压缩传输系统;航空科技信息集成处理系统;模拟实战射击训练系统;国家“十五”863信息安全项目等。

开设研究生课程:多媒体技术及应用、计算机图形学、软件认证;本科生课程:多媒体技术、数字逻辑。

--------------------------------------------------------------------------------李毅超,男,1969年6月,硕士,副教授。

1997年4月毕业于电子科技大学,获计算机应用硕士学位。

现任网络安全基础实验室主任,计算机网络与通信研究室主任,计算机网络与安全技术研究所副所长,兼成都市软件行业协会副秘书长。

研究方向为计算机网络与通信、网络信息安全、嵌入式应用。

参加或主持"恩威网络MIS系统“、“420驻厂军代室光纤网络MIS系统”、“路由器开发”、信产部基金项目“IP电话网关”,成都华易“美视数字录像监控系统”、西部网信“软交换关守和IP电话多功能终端研发”等近10个科研项目,获得四川省科技三等奖1项,省部级科技成果鉴定5项,国家版权局软件著作权2项。

出版《计算机网络》教材1本在国内外重要刊物和国际会议上发表论文十余篇。

为本科和硕士生开设了若干课程。

获得Microsoft、Novell、SCO、Cisco、Compaq等各大公司认证证书和授权讲师资格。

爱考机构-北大考研-计算机科学技术研究所研究生导师简介-贾文华_副研究员贾文华副研究员贾文华，男，1968年生于四川省渠县，1987年进入北京大学学习,1994年毕业于北京大学计算机科学技术系计算机软件专业，获得理学硕士学位。

现任北京大学计算机科学技术研究所副研究员，长期从事电子出版、印刷系统技术的研究、开发管理及其产品在国际市场的推广。

1994年到1998年的主要研究领域是文字、图形和图象信息的计算机处理，1999年开始从事基于网络、数据库的数字化流程技术方面的研究工作,2000年起同时开始研究并实施如何将自主技术的软件产品有效出口欧美市场。

曾获得北京市科技进步一等奖和北京大学优秀教学奖(柯达奖教金)。

研究方向研究室主页>>·基于网络与数据库的数字化流程·文字与图形图象信息处理主要科研成果·1993年与阳振坤博士和其它同事一起实现了国际上第一个中文PostScriptLevel2的激光照排控制器（也称光栅化图象处理器）—PSP，同年秋天产品化并在香港明报正式投入使用。

·1997年完成了基于WindowsNT的全32位多线程的PostScript激光照排控制器—PSPNT，PSPNT包含近20个子系统30多万行源代码，我个人担任PostScript解释器总体设计师职责。

·1998年起全面负责方正激光照排控制器的研制工作，组织研制了支持PostScriptLevel3和出版印刷行业新标准PDF1.3的新版激光照排控制器，并对欧美客户行业要求进行深入调研并对产品进行大幅度提升和改进，于2000年成功推出方正EagleRIP2.1激光照排控制器，并成功推向欧美纯西文市场。

·1999年发起并组织研究方正畅流全数字化工作流程系统，其基于出版印刷行业国际标准—PDF，有效应用数据库和互联网技术，并完全采用国际组织CIP4的最新国际标准—JDF 作为方正畅流系统内部与印前其它工艺、印刷、印后加工、互联网管理以及第三方管理信息系统通讯的标准语言，形成全数字化的高度自动化的印前工艺流程管理系统，极大地提高了出版印刷行业的生产效率和管理水平。

优先出版 计 算 机 应 用 研 究 第32卷--------------------------------基金项目：北京市教委科技面上项目(SQKM201211232011)；网络文化与数字传播北京重点实验室开放课题资助；北京市属高等学校创新团队建设与教师职业发展计划项目(IDHT20130519)作者简介：凌峰(1990-)，男，北京人，硕士研究生，主要研究方向为文档信息处理(tomoko000@)；刘旭红(1972-)，女，博士，副教授，主要研究方向为XML 与文档信息处理；田英爱(1975-)，女，博士，高级实验师，主要研究方向为文档数据处理与集成、软件工程；李宁(1964-)，男，博士，教授，主要研究方向为文档信息处理、XML 、信息技术标准化．ODQ 文档模型和语法的扁平化处理 *凌 峰，刘旭红，田英爱，李 宁(北京信息科技大学 计算机学院，北京 100192)摘 要：ODQ 是一种面向流式办公文档的查询语言。

为了提高ODQ 的查询效率并降低使用难度，提出了一种将ODQ 文档模型和语法进行扁平化处理的方法。

首先将ODQ 文档模型由传统树形结构转换成多线性结构，减少文档模型的层次。

其次，在语法中设置特定关键字，将文档模型中的各层次连接起来，形成一条可以直接访问目标数据的路径。

实验结果表明扁平化处理可以使查询效率得到提高，并简化查询操作。

关键词：文档查询语言；文档格式；扁平化；文档模型；语法 中图分类号：TP302.1 文献标志码：AFlattening dispose of ODQ document model and grammarLING Feng, LIU Xu-hong, TIAN Ying-ai, LI Ning(Dept. of Computer, Beijing Information Science & Technology University, Beijing 100192, China)Abstract: ODQ is a query language for streaming office documents. In order to increase the query efficiency and lower the use difficulty, this paper proposed a method to flatten the ODQ document model and grammar. First, it translated the ODQ document model from the original tree structure into multi-linear structure, and reduced the level of document model. Second, it designed a specific keyword in grammar, which is able to link all levels of document model and create a path that lead to the target data. The experimental results show that the flatten procedure can increase the query efficiency and simplify the query operations. Key Words: document query language; document format; flattening dispose; document model; grammar0 引言目前流式文档在办公领域占据了很大的份额。

• 两极分化比较严重 • 程序课程讨论气氛比较弱
16
我们的翻转课堂尝试
考试分数
• MOOC班平均分：87分 • 普通班平均分：78分 • 实验班平均分：88分
MOOC班 (22人选课)
• 最终成绩>85分的共17人, 占考试人数的77.3%
普通班 (71人选课)
• 最终成绩>85分的共33人, 占考试人数的45.8% • 最终成绩<60分的共2人, 占考试人数的2.8%
3
程序设计实习— 在线平台基础
课程配套在线评测平台
• POJ: http://openjudge/ • 在线提交作业 • 组织期末考试
4
MOOC课程的首尝试
2019年春季学期
Coursera平台
https:///pkupop-001
• 1 门课程 • 2 位授课教师 • 3 +1位助教 • 14 +1周教学内容 • 78段视频 1400+分钟
10 10 12 14 12 9 10 10 12
视频 总数
51 44 82 101 78 57 70 76 101
视频平均 平均每周 平均每周
时长
视频个数 视频时长
0:18:51
4.94
1:28:46
0:14:35
4.37
1:03:25
0:13:23
6.83
1:31:25
0:11:55
7.21
1:25:55
操作方式
• 老师对教学内容进行切分 • 课前MOOC课程介绍大部分课程内容 (侧重基础) • 课上对重点难点的教学内容进行深入介绍, 保证互动, 彻底消化
最简单的翻转模式 比较安全的翻转, 本质变革不大

主要研究成果
• 1997年以来在国内《外语界》、《外语与外语教学》、 《中国外语》、《外语电化教学》、《中国大学教学》 、《大学英语》以及国外《教学与学习》等外语类核心 及统计源刊物发表外语教学方面的学术研究论文20余篇 。 • 他在1998-2001年间合作主持出版了多媒体教材《大学 英语精读》，2001年该套光盘获国家优秀教学成果二等 奖，广东省优秀教学成果一等奖。 • 2002—2004年期间主持完成了国家“十五”规划教材《 大学体验英语》及其网络课程系统（高等教育出版社） 。于2001年获国家教学成果二等奖（排名第二），广东 省教学成果一等奖。 • 贾国栋目前担任教育部大学外语教学指导委员会副主任 委员、教育部全国大学英语四、六级考试委员会副主任 委员、北京市大学英语研究会副理事长等职。他也是国 际英语教师协会会员、亚洲英语教师协会会员。
黎家厚
• 1986年，华南师大电化教育专 业硕士研究生；1989年获教育 学硕士学位。1990.西北师大 教科所，教学论专业博士研究 生；1993年获教育学博士学位 。已有35年从事教学的经历， 从小学生教到研究生，将自己 的全部精力投入到教育技术的 研究和教学中。
主要研究方向
• • • • 教育技术学原理 信息技术教育 教学设计 教师教育信息化
文秋芳教授主要著作
• • • • • • • 《英语语言学导论》 《英语学习策略论》 《外语口语测试与教学》 《应用语言学研究方法与论文写作》 《英语学习的成功之路》 《学习者可控因素与英语成绩的关系》 《英语学习策略实证研究》
文秋芳教授主要研究项目
• “学习者可控因素与大学生英语成绩之间 的关系” • “英语学习者动机、观念和策略的变化规 律与特点” • “中国大学生英语写作能力发展的规律与 特点” • “全国英语专业八级口语与口译考试可行 性研究” • “中国大学生英语口语能力发展的规律与 特点”

北京大学计算机科学技术研究所计算机应用技术学科（专业代码：081203）研究生培养方案2010年8月目录计算机科学技术研究所简介一、硕士研究生培养方案二、博士研究生培养方案三、硕博连读研究生培养方案四、直读博士研究生培养方案五、硕士研究生课程北大计算机科学技术研究所简介北京大学计算机科学技术研究所成立于1983年，源于王选教授开创的汉字激光照排技术研究，是北京大学的二级科研教学机构、计算机应用技术国家重点学科之一，研究方向包括:图形图像处理技术与电子出版应用、网络与数据库技术及应用、视音频技术及应用、网络与信息安全技术及应用，拥有硕士、博士培养点及博士后流动站，以及“电子出版新技术国家工程研究中心”、“中国文字字体设计与研究中心”、“网络与信息安全中关村开放实验室”等科研基地。

计算机所坚持自主创新、产学研相结合的发展道路，以一流的科研成果创造一流的产业应用为目标，围绕计算机技术在印刷、新闻出版、广电、信息安全等相关领域的应用，开拓进取，取得了多项重大科研成果，获国家最高科学技术奖1次、国家科技进步一等奖2次、国家科技进步二等奖3次，2次入选中国十大科技成就、2次入选信息产业重大技术发明、2次入选中国高等学校十大科技进展，多次推动相关行业实现了技术变革，产生了重大的社会与经济效益。

一、硕士研究生培养方案培养目标与学制及应修学分（表一）科研能力与水平及学位论文的基本要求（表二）硕士研究生的课程学习要求（表三）二、博士研究生（普博）培养方案培养目标与学制（表四）学习安排和综合考试的基本要求（表五）科研能力与水平的基本要求（表六）学位论文的基本要求（表七）三、硕博连读研究生培养方案培养目标与学制（表八）学习安排和综合考试的基本要求（表九）新生能力、水平的基本要求及选拔办法（表十）四、直读博士研究生培养方案培养目标与学制（表十一）学习安排和综合考试的基本要求（表十二）新生能力、水平的基本要求及选拔办法（表十三）五、硕士研究生课程计算机科学与技术专业硕士研究生课程（表十四）。

北京大学信息科学技术学院【字体：大中小】考研书店一．基本情况北京大学信息科学技术学院成立于2002 年9 月。

学院由12 个研究所和中心组成：基础实验教学研究所、电子工程研究所、量子电子学研究所、光子和通信技术研究所、物理电子学研究所、软件研究所、网络和信息系统研究所、计算语言学研究所、计算机系统结构研究所、数字媒体研究所、微电子学研究院、信息科学中心。

学院覆盖了4 个一级学科：（计算机科学和技术、电子科学和技术、信息和通信工程、物理学），11 个二级学科（计算机软件和理论、计算机系统结构、计算机使用技术；微电子学和固体电子学、物理电子学、电磁场和微波技术、电路和系统；通信和信息系统、信号和信息处理；无线电物理、声学）。

其中5 个二级学科在2002 年被评为国家重点学科（计算机软件和理论、计算机使用技术、微电子学和固体电子学、物理电子学、通信和信息系统）。

学院教学研究实力雄厚，拥有一支高水平的师资队伍，其中中国科学院院士3 人( 含双聘 1 人) 、中国工程院院士1 人，教授70 余人，博士生导师50 余名。

学院拥有3 个国家级重点实验室——视觉和听觉信息处理国家重点实验室、微米/ 纳米加工技术国家级重点实验室和区域光纤通信和新型光通信系统国家重点实验室（北京大学）， 5 个部委和市级重点实验室，以及和国际著名公司、科研机构组建的若干联合实验室。

近年来，学院承担了大量的国家级科研项目（年平均科研经费约一亿元），每年在国内外核心刊物和高水平会议上发表学术论文500 多篇。

北京大学的信息科学技术学科具有悠久的历史，最早可以追溯到上个世纪50 年代数学系的计算数学专业、物理系的无线电物理、电子物理和半导体物理专业。

几十年来，北京大学在信息科学技术学科取得了一系列具有全国领先水平的重大研究成果：20 世纪70 年代我国第一台百万次数字计算机150 的研制，80 年代卫星通信和光纤通信系统的研制和使用，90 年代纳米电子学、量子电子学研究的重要成果和微电子技术以及拥有自主知识产权的核心技术领先的指纹识别系统等等，都对国家的经济发展、国防建设以及人民生活水平提高乃至生活和工作方式的改变产生了重大影响。

爱考机构-北大考研-计算机科学技术研究所研究生导师简介-刘志红_副教授刘志红,1967年11月出生，副教授，毕业于北京大学。

研究方向·嵌入式系统研究·电子设计自动化(EDA)及VHDL/Verilog语言·大规模ASIC/FPGA/CPLD芯片设计研究工作·嵌入式系统：包括嵌入式硬件平台设计，FPGA/CPLD设计，嵌入式操作系统研究，嵌入式软件设计。

·电子出版新技术：包括数码印刷系统研究开发，高端彩色打印服务器研究开发。

主要工作业绩·1990年进入北京大学计算机研究所,1990年参加方正91电子出版系统中照排控制器的调试工作,解决了其中关键技术难点,确保了方正91电子出版系统的成功上市,1991年至1992年,作为主要设计者之一,参加方正PostScriptLevel2RIP的核心硬件超大规模专用芯片OP的设计,1993年至1994年,作为主要设计者之一，参加超大规模专用芯片PSP的设计，OP和PSP芯片作为北大方正电子出版系统的核心硬件，在出版市场上产生了很大的影响,创造了很高的经济效益,也多次获得各种奖励.在当时国内实验条件相对滞后的条件下,OP和PSP芯片都做到了一次投片成功。

·1992年至1993年，参加方正电子出版系统发排软件的开发，完成照排控制器中微程序的软件移植工作。

·1994年,主持设计了超大规模专用挂网芯片SA,使当时调频网的挂网速度比PC机高出50倍以上,使当时RIP的挂网速度处于世界领先地位。

·1995年,进行PCI总线技术研究,并且设计完成了方正第一个基于PCI总线的照排控制器的控制卡,这一产品也是国内最早的自主开发的基于PCI总线的产品。

·1996年至2002年,负责方正文杰激光打印机的开发,是方正文杰激光打印机控制器的主要设计者和开发者,主持完成了文杰打印机多款机型的设计和开发,同时负责了方正网星网络打印服务器的开发,方正文杰打印机和网星网络打印服务器均已经成功上市,获得用户好评,文杰打印机已经累计销售数万台,创造了良好的经济效益。

本人2004.1~2008.12科研情况
获国家奖项，省部级奖6项。
发表论文共10篇，出版专著部。
目前承担国家级项目项，省部级项目1项。
在研科研经费共96万元。
最
有
代
表
性
的
成
果
序
号
成果（获奖项目、论文、专著）名称
获奖名称、等级或鉴定单位，
发表刊物，出版单位，时间
本人
排序
1
开放式计算机实验室综合管理系统
河北省教育厅
1
2006~2008
2.5
Ⅴ-2-3-3本学科主要学术带头人基本情况
姓名
王书海
性别
男
出生年月
1969.06
专业技术职务
教授
定职时间
2005.09
是否博导（硕导）
硕导
最高学位或最后学历
（包括毕业时间、学校、系科）
硕士，2002年毕业于西南交通大学计算机与通信工程学院
主要研究方向
计算机信息系统
（计算机软件与理论）
封筠
1971.10
2005.06
副教授
硕导
1
5
张翠肖
1969.11
教授
硕导
2
8
王学军
1968.06
教授
硕导
2
6
刘晨晨
1977.02
2007.03
副教授
硕导
Ⅴ-2-3-1本学科主要学术带头人基本情况
姓名
赵正旭
性别
男
出生年月
1960.02
专业技术职务
长江学者特聘教授
定职时间
2001.7
计算机科学与技术081221基本数据项目统计时间学术队伍200812在编杰青长江学者燕赵学者副教授16具有博士学位教师20041200812scieiistp收录论文7420041200812获奖类别特等奖一等奖二等奖三等奖国家奖20061200812三年内拥有科研经费合计6655万元平均每年2218万元高级专业技术职务人员三年平均科研经费716万元年人200812国家级重点项目863973国家杰出青年基金自然科学基金重大重点项目或国家攻关项目国家自然科学基金项目国家社会科学基金项目国家及国务院各部门项目省级项目10国防科研项目目前承担的科研项目的经费合计5805万元教学与人200812是否硕士学位授权一级学科在读硕士共8720041200812获国家级优秀教学成果奖共实验条件200812配有省部重点实验室工程中心专业实验室面积合计426010万元以上仪器设备合计11仪器设备值合计1871万元备注22本一级学科代表性研究方向及其学术带头人主要学术骨干研究方向及所属二级学科出生年月获博士学位年月专业技术职务培养硕士学士生毕业人数在学人数虚拟现实技术及其应用计算机应用技术196002199207教授博导24195403教授196408教授196912200809副教授计算机检测与控制技术计算机应用技术197008教授195705教授197103200801教授綦朝晖197601200603副教授计算机信息系统计算机应用技术王书海196906教授196512200706教授196711200801副教授197102200812副教授模式识别与图像处理计算机软件与理论197110200506副教授196911教授王学军196806教授197702200703副教授231本学科主要学术带头人基本情况出生年月196002专业技术职务长江学者特聘教授20017是否博导硕导博导最高学位或最后学历包括毕业时间学校系科博士1992年毕业于英国staffordshire大学计算机系计算机科学专业博士后199312英国newcastle大学计算机工程系应用计算机专业2001年被东南大学聘为博士生导师主要研究方向虚拟现实技术及其应用本人20041200812科研情况获国家奖项省部级奖发表论文共29篇出版专著在研科研经费共260万元

ｏｆ ｌｅａｒｎｉｎｇ ｔｈｅ ｉｎｖｅｒｓｅ ｍａｐｐｉｎｇ ｆ ｒｏｍ ｔｈｅ ＬＲ ｐａｔｃｈ ｔｏ ｔｈｅ ｍｅａｎ ｏｆ ｔｈｅｓｅ ＨＲ ｐａｔｃｈｅｓ，ｒｅｓｕｌｔｉｎｇ ｉｎ ｖｉｓｕａｌｌｙ ｂｌｕｒｒｅｄ ｒｅｓｕｌｔ Ｉｎ ｏｒｄｅｒ ｔＯ ．
ａｌｌｅｖｉａｔｅ ｔｈｅ ｈｉ 【ｇｈ ｆ ｒｅｑｕｅｎｃｙ ｌｏｓｓ ｃａｕｓｅｄ ｂｙ ａｍｂｉｇｕｉｔｙ，ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｓ ａ ｄｅｅｐ ｎｅｔｗｏｒｋ ｆｏｒ ｉｍａｇｅ ｓｕｐｅｒ—ｒｅｓｏｌｕｔｉｏｎ ｕｔｉｌｉｚｉｎｇ ｔｈｅ ｏｎｌｉｎｅ ｒｅｔｒｉｅｖｅｄ ｄａｔａ ｔｏ ｃｏｍｐｅｎｓａｔｅ ｈｉｇｈ—ｆ ｒｅｑｕｅｎｃｙ ｄｅｔａｉｌｓ．Ｔｈｉｓ ｍｅｔｈｏｄ ｃｏｎｓｔｒｕｃｔｓ ａ ｄｅｅｐ ｎｅｔｗｏｒｋ ｔｏ ｐｒｅｄｉｃｔ ｔｈｅ ＨＲ ｒｅｃｏｎｓｔｒｕ ｃｔｉｏｎ ｔｈｒｏｕｇｈ ｔｈｒｅｅ ｐａｔｈｓ：Ａ ｂｙｐａｓｓ ｃｏｎｎｅｃｔｉｏｎ ｄｉｒｅｃｔｌｙ ｉｎｐｕｔｔｉｎｇ ｔｈｅ ＬＲ ｉｍ ａｇｅ ｔｏ ｔｈｅ ｌａｓｔ ｌａｙｅｒ ｏｆ ｔｈｅ ｎｅｔｗｏｒｋ；ａｎ ｉｎｔｅｒｎ ａｌ ｈｉｇｈ—ｆｒｅｑｕｅｎｃｙ ｉｎｆｏｒｍａｔｉｏｎ ｉｎｆｅｒｅｎｃｅ ｐａｔｈ ｒｅｇｒｅｓｓｉｎｇ ｔｈｅ ＨＲ ｉｍａｇｅｓ ｂａｓｅｄ ｏｎ ｔｈｅ ｉｎｐｕｔ ＬＲ ｉｍａｇｅ，ｔｏ ｒｅｃｏｎｓｔｒｕ ｃｔ ｔｈｅ ｍａｉｎ ｓｔｒｕｃｔｕｒｅ ｏｆ ｔｈｅ ＨＲ ｉｍａｇｅｓ；ａｎｄ ａｎｏｔｈｅｒ
Ｄａｔａ—Ｄｒｉｖｅｎ Ｅｘｔｅｒｎａｌ Ｃｏｍ ｐｅｎｓａｔｉｏｎ Ｇｕｉｄｅｄ Ｄｅｅｐ Ｎｅｔｗｏｒｋｓ ｆｏｒ Ｉｍ ａｇｅ Ｓｕｐｅｒ－Ｒｅｓｏｌｕｔｉｏｎ
ＹＡＮＧ Ｗ ｅｎ—Ｈａｎ， ＬＩＵ Ｊｉａ—Ｙｉｎｇ， ＸＩＡ Ｓｉ－Ｆｅｎｇ， ＧＵＯ Ｚｏｎｇ—Ｍ ｉｎｇ

第29卷 第2期 计算机辅助设计与图形学学报Vol. 29 No. 2 2017年2月Journal of Computer-Aided Design & Computer GraphicsFeb. 2017收稿日期: 2016-03-19; 修回日期: 2016-07-11. 基金项目: 国家自然科学基金(61175004); 中国博士后科学基金资助项目(2015M580952); 高等学校博士学科点专项科研基金(20121103110029); 北京市博士后工作经费资助项目(2016ZZ-24). 曾少锋(1988—), 男, 博士研究生, 主要研究方向为模式识别、机器学习; 李玉鑑(1968—), 男, 博士, 教授, 博士生导师, CCF 会员, 论文通讯作者, 主要研究方向为人工智能、模式识别、机器学习、计算机视觉、自然语言处理等; 刘兆英(1986—), 女, 博士, 讲师, 主要研究方向为模式识别、图像处理等.基于边特征的学习完全图匹配模型曾少锋, 李玉鑑*, 刘兆英(北京工业大学计算机学院 北京 100124) (liyujian@)摘 要: 传统的线性学习图匹配模型具有易于训练和能够求解最优匹配的优点, 但是没有考虑图的结构信息, 从而限制了其匹配精度. 为克服这一缺点, 提出一种新的线性学习图匹配模型——基于边特征的学习完全图匹配模型(ELC-GM), 其中, 边特征由边上采样点的特征描述, 而采样点的特征是通过一种包含旋转不变因子的形状上下文特征描述的. ELC-GM 先对模型进行有监督的训练, 再用Kuhn-Munkres 算法求解边匹配, 进而用Hungarian 解码算法将边匹配转换为点匹配. 实验结果表明, ELC-GM 的训练效果稳定, 匹配精度即使在形变和噪声条件下也能得到一定提升.关键词：图匹配; 边特征; 监督; 旋转; Hungarian 解码 中图法分类号：TP391.4Edge Feature Based Learning Complete Graph Matching ModelZeng Shaofeng, Li Yujian *, and Liu Zhaoying(College of Computer Science, Beijing University of Technology , Beijing 100124)Abstract: Traditional linear learning graph matching model is easy to be trained and can achieve a global optimal solution. However, this model doesn’t consider the information of graph structure, thus limiting its matching accuracy. To overcome this disadvantage, we propose a novel linear learning graph matching model—edge feature based learning complete graph matching model (ELC-GM). An edge feature is con-structed from its sampling point features, which are described by an extension of shape context with rotation invariant factors. After supervised training of ELC-GM, Kuhn-Munkres is used to solve the edge match and then Hungarian decoder is applied to determine the final point match. Experimental results show that ELC-GM can achieve good performances with improvement of accuracy, even in cases of deformation and noise.Key words: graph matching; edge feature; supervised; rotation; Hungarian decoder 图匹配是图理论中的一个基本问题, 它在计算机视觉的诸多研究方向, 如字符识别[1]、2D 或3D 物体形状匹配[2]、目标分类[3-4]、行为识别[5]等方面都有应用. 对于分别包含n 和n '个顶点的两图G 和G ', 图匹配问题尝试寻找G 与G '中顶点之间的最佳对应关系, 不同的对应关系会在图匹配问题上施加不同的约束. 本文考虑一对一的情况, 且n n '=, 此时可以用一个置换矩阵n n '⨯∈ X 来第2期曾少锋, 等: 基于边特征的学习完全图匹配模型 237表示这种对应关系.图匹配问题是一个求解二值解的二次规划问题, 模型一般包含线性部分和二次部分, 其中, 线性部分用于考虑两图中顶点之间的对应关系, 二次部分用于考虑图中结构之间的对应关系. 二次图匹配模型是一个NP难问题, 目前只能寻求其近似解. 常用的求解方法可以分为2类. 1) 基于谱分析的方法[6-8], 此类方法通过对邻接矩阵或相似度矩阵进行特征分解, 以在特征空间中求解原问题. 谱分析方法求解思路简单, 但有着理论上的局限性, 例如, 非同构图可能会得到相同的特征分解, 这会导致谱分析方法在遇到非同构图匹配问题时得到的结果可能较差[9]. 2) 与谱分析方法相对应的一类方法是直接在原空间对模型进行求解[10-13]. 这类方法一般也要先求得一个连续解, 然后采用某种离散策略得到二值解. 但是, 这种从连续到离散的转换是存在误差的[13-14], 为此文献[13]提出了一种路径跟随算法以减少这种转换误差.本文将上述模型统称为非学习图匹配模型. 非学习图匹配模型在实际应用中的效果不理想, 其中一个原因是形变、噪声的存在使获取的特征失效. 为了解决这一问题, 近年来机器学习的思想被引入到图匹配模型中, 即产生了学习图匹配模型. 通常, 在非学习图匹配模型的基础上引入学习参数就可以得到相应的学习图匹配模型. 和非学习图匹配模型相比, 学习图匹配模型在匹配精度上会有大幅度的提升. 目前, 对于学习图匹配模型的研究较少, Leordeanu等[15]提出一种无监督的学习图匹配模型, 但这种模型的求解是建立在矩阵的谱分析基础上的, 因此不可避免地存在着谱分析方法的缺点. Caetano等[16]提出一种有监督的学习图匹配模型, 并分别在线性和二次图匹配模型上实现. 相比于文献[15], 文献[16]中的方法有着更完善的理论支撑. 通常, 线性非学习图匹配模型的匹配效果不如二次非学习图匹配模型, 但是线性学习图匹配模型却在一些数据集上表现出了较二次学习图匹配模型更好的效果[16]. 另外, 因为线性图匹配模型可以求得全局最优解, 训练结果不会随初始条件的不同而产生较大的变化, 所以模型更易训练, 效果也较稳定; 但是这种模型不能利用图的结构信息进行匹配.本文在文献[16-17]的基础上, 提出一种基于边特征的学习完全图匹配模型(edge feature based learning complete graph matching model, ELC-GM), 该模型所对应的非学习图匹配模型称为基于边特征的完全图匹配模型(edge feature based complete graph matching model, EC-GM). 边特征是通过边上采样点的点特征得到的, 并通过一种包含旋转不变因子的形状上下文(shape context with rotation invariant factors, RIFSC)特征来描述点特征. ELC- GM首先对模型进行训练, 再通过训练后的模型求解顶点间的匹配. 模型的训练使用一种有监督的方法; 顶点间匹配的求解与EC-GM的求解方法相同, 即将边当作顶点, 通过KM(Kuhn-Munkres)算法[18]求解边之间的匹配, 再通过Hungarian解码算法[17]将边之间的匹配转换为顶点之间的匹配.1 图的边特征1.1边特征的提取与描述类似点特征, 边特征是对图中边的特征描述. 由顶点可以通过多种方法获取边, 如K NN[19], De-launay三角分解[20], 全连接[15]等. K NN, Delaunay 三角分解等方法对形变、噪声敏感, 在实际问题中, 即使对于包含相同目标的2幅图像, 这2种方法对目标的分解结果也可能不同. 而ELC-GM使用有监督的训练方法, 样本标签是边之间的对应关系. 这两种分解方法不利于标签的自动生成, 而且无对应关系的边也不能参与训练. 鉴于这些原因, ELC-GM采用全连接的方式获取图中的边, 即使用完全图(如图1a所示)进行匹配.图1 完全图G及其边ce的采样点示意图边特征是通过边的采样点的点特征描述的, 本文使用的是边的顶点及三等分点的点特征(关于采样点个数的选择见附录A). 对于图1a中的第c 条边c e, 其采样点为边的顶点i p, j p和三等分点1p, 2p, 如图1b所示; 记这4个采样点的特征为ipV,1pV,2pV和jpV, 则边c e的特征ceV表示为()12;;;.c i je p p p p=V V V V V顶点p的特征pV是一个向量, 表示为238计算机辅助设计与图形学学报第29卷()T,,.p k v = V1.2 RIFSC形状上下文(shape context, SC)[21]特征是一种经典的点特征描述方法, 它将描述点与其他点的相对位置关系作为特征描述; SC 特征对大幅度的旋转较敏感. 针对学习图匹配模型, 本文在SC 的基础上提出一种RIFSC 的点特征描述方法.对于图2a 中的一个点, 其RIFSC 特征的计算过程是: 首先计算其SC 特征, 其次通过SC 特征计算旋转不变因子. 具体步骤如下:Step1. 归一化两两顶点之间的距离. Step2. 以该点为中心建立极坐标系.Step3. 在角坐标θ和半径坐标r 上划分块. 经典的划分方法是: 角坐标上每隔30︒做一次划分, 半径坐标上, r =1/8, 1/4, 1/2, 1, 2处各做一次划分, 这样一共得到60个块, 如图2a 所示.Step4. 统计所有顶点在各块中的分布, 得到顶点分布, 如图2b 中矩阵所示, 此分布即为该点的SC 特征(为便于计算, 可将矩阵向量化).Step5. 计算旋转不变因子. 如图2b 所示, 计算分布在同半径的块中的点的平均个数(即矩阵的每一行的均值), 这样共得到5维均值, 即旋转不变因子, RIFSC 将旋转不变因子也作为该点的特征描述.图2 RIFSC 计算示意图由于旋转不会造成同半径的块中点的总个数的变化, 因此旋转不变因子对旋转是不变的. 对于旋转问题, 学习图匹配模型在计算特征相似度时会给失效的SC 特征赋予较小的权值, 而给旋转不变因子赋予较大的权值, 从而可以有效应地应对旋转问题.2 EC-GM如图3a 所示, 传统的线性图匹配模型, 直接以图中顶点为对象进行建模, 忽略了图的结构信息. EC-GM 则以边为对象进行建模(如图3b 所示), 从而考虑了图的结构信息. EC-GM 本质上仍然是线性的, 为了和传统的线性图匹配模型相区分, 本文把传统的线性图匹配模型称为基于点特征的图匹配模型(point feature based graph matching model, P-GM).图3 2种线性图匹配模型的匹配示意图P-GM 和EC-GM 的表达式分别为 *arg max ii ii ii a x '''=∑XX (1)*arg max cc cc cc k y '''=∑YY (2)其中, ()ii x '=X 和()cc y '=Y 分别是两图中顶点之间和边之间的匹配矩阵; ii a '和cc k '分别表示顶点与顶点、边与边之间的相似度, (),i i ii p p a δ'''=V V (3)()()()max ,,,c c c c e cc e e e k δδ'''''=V V V V (4)其中, (,)δ'U U 是关于两向量()T,,k u = U 与'=U()T,,ku '' 的相似度计算函数; 式(4)中c e ''=V()()1221;;;,;;;c i j j i e p p p p p p p p ''''''''''''''= V V V V V V V V V , 即c e ''V 中采样点的排序与c e ''V 相反, 目的是要考虑边中顶点的2种匹配策略, i j i j p p p p ''''↔和i j j i p p p p ''''↔.另外, 式(1), (2)分别满足如下约束:{},0,1,1,1;ii ii ii ii ii x x x '''''∀∈==∑∑{},0,1,1, cc cc cc cc y y y '''''∀∈==∑∑在算法实现上, 式(2)还伴随输出一个指示矩阵()cc s 'S =, 其中{}0,1cc s '∈. 在*1cc y '=的前提下,cc s '取值分别指示了两边是以何种策略匹配的.二次图匹配模型{}*argmax s.t.,0,1,=1,=1ii ii cc ii jj ii cc ii ii ii i i a x k x x ii x x x '''''''''''⎧⎡⎤+⎪⎢⎥⎪⎣⎦⎨⎪'∀∈⎪⎩=∑∑∑∑X X(5)第2期曾少锋, 等: 基于边特征的学习完全图匹配模型 239其中, cc k '是以G 中i p 和j p 为顶点的边与G '中以i p ''和j p ''为顶点的边之间的相似度. 式(5)与式(1)(2)对比可以看出, 二次图匹配模型比线性图匹配模型多出一个二次项, 当cc '∀, 0cc k '=时, 式(5)退化为式(1). 而式(2)将式(1)这种求解顶点之间最大权匹配的问题替换为求解边之间的最大权匹配问题, 从而实现了在线性模型的基础上考虑图的结构信息的目的.3 ELC-GM 及其训练ELC-GM 是EC-GM 对应的学习图匹配模型,*arg max ()cc cc cc k y '''=∑YY w (6)是在EC-GM 的基础上引入了参数w , 并通过模型的训练得到参数取值, 构造出更适合当前问题的模型, 能够有效地提高匹配精度. 具体思路是将式(2)中的cc k '替换为一种关于边,c ce e ''和=w ()T,,k w 的函数()cc k 'w .类似地, 可以得到P-GM 所对应的学习图匹配模型, 即基于点特征的学习图匹配模型(point featurebased learning graph matching model, PL-GM)[16], 此处略.式(6)中的()cc k 'w 具体为()()()()max ,,,,,c c c c cc e e e e k φφ'''''=w V V w V V w(7)其中, ∙表示内积运算; (),φ'U U 是关于向量U ,'U 之间的函数关系, 定义为()()T2,,,k ku u φ''=-- U U (8) 由式(7)(8)可以得到式(3)(4)中(),δ'U U 的计算方法()2,k k kkw u u δ''=--∑U U (9) 式(9)中, 参数w 中各维的取值决定了边特征中相应维度对特征之间相似度计算的影响程度.在图匹配模型的训练问题中, 训练样本是N 对图对()()(){}1122,,,,,N N G G G G G G ''' , 而样本标签是图对中边之间的匹配矩阵{}12,,,N Y Y Y , 参数训练就是要最小化目标函数()*11,().Nkk k ΩNλ=∆+∑Y Y w其中, 第1项为经验损失, *k Y 为预测函数(式(6))关于第k 个样本的预测值, ()*,kk∆Y Y表示模型的预测值与样本标签之间的差异; 第2项称为正则项, 可以有效地防止过拟合问题.图匹配模型的训练较为复杂, 其不同于传统机器学习中的分类问题, 也不同于回归问题, 要求解的是表征顶点之间对应关系的结构化的数据; 再有,Y 是离散的, 而w 是连续的, 这决定了w 的取值可能不唯一. 为了解决图匹配模型的训练问题, 文献[16]将目标函数式中的经验损失项用其上界替换, 并用Bundle Method 算法求解新的目标函数. Bundle Method 算法通过求解与原目标函数最接近的一阶泰勒展开式的极值来近似求解原函数, 求解中需要不断更新目标函数的梯度和偏移量,详见文献[16].4 KM 算法与Hungarian 解码算法ELC-GM(或EC-GM)通过KM 算法和Hungarian 解码算法求解顶点之间的匹配. KM 算法能够求解线性图匹配问题的全局最优解. 线性图匹配问题等价于求解加权二部图的最大权匹配问题, 二部图中的顶点即为图G 和G '中的顶点, 二部图中边上的权值为相似度ii a '或cc k '. KM 算法首先在二部图上建立一个相等子图, 然后在相等子图上寻找完美匹配. 如果找到这样的完美匹配则算法终止, 该完美匹配即为此图的最大权匹配; 否则扩展相等子图, 再次寻找完美匹配, 直到找到这样的匹配. KM 算法的时间复杂度最优可达到()3n ο.对于PL-GM(或P-GM), KM 算法可以求解顶点之间的匹配; 而对于ELC-GM(或EC-GM), KM 算法只能得到边之间的匹配. 因此还需要一种可以将边之间的匹配转换为顶点之间匹配的方法. Hungarian 解码算法可以解决这个问题, 其伪代码如下:输入. 式(6)的输出*Y , 指示矩阵S . 输出. 匹配*X .Step1. 初始化矩阵()ii a '=A , ,0ii ii a ''∀=.Step2. cc '∀ 如果*1cc y '=且=0cc s '.Step3. 1;1.ii ii jj jj a a a a ''''=+=+ Step4. cc '∀如果*1cc y '=且=1cc s '.Step5. 1; 1.ij ij ji ji a a a a ''''=+=+ Step6. *argmax .ii ii ii a x '''=∑XXHungarian 解码算法的思想与投票选举的思想类似, 包括2步:240计算机辅助设计与图形学学报 第29卷1) 统计所有匹配边对于顶点匹配的“支持度”.Step2~Step5中, 当*1cc y '=且0cc s '=时, 表明图G 中的顶点i p 和j p 分别和图G '中的顶点i p ''和j p ''匹配;当*1cc y '=且1cc s '=时, 顶点i p , j p 分别和顶点j p '',i p ''匹配, 矩阵A 记录了统计结果.2) 构造新的P-GM, 求解顶点匹配. Step6中, 将A 矩阵看作是图G 与G '中顶点间的相似度矩阵, 就可以建立新的P-GM; 再次利用KM 算法, 就可以求解出顶点之间的匹配.ELC-GM 求解顶点之间匹配的时间复杂度为()()63n n οο+, 其中, ()6n ο为式(6)求解边匹配的时间复杂度, ()3n ο为解码过程的时间复杂度.5 实验结果与分析为了验证ELC-GM 的有效性, 与5种方法进行对比: 其中包括3种非学习图匹配模型—— GNCCP [22], IPFP [23]和E-GM [17], 2种学习图匹配模型——PL-GM 和二次学习图匹配模型(QL-GM)[16]. E-GM 与EC-GM 的区别在于E-GM 使用Delaunay 三角分解获取边, E-GM 的效果优于EC-GM, 故本文与E-GM 作对比. 实验中各数据集平均分为三部分, 分别作为训练集、验证集和测试集.将6种模型在图像序列数据集上进行测试, 以各模型在不同帧差(图像序号之间的差值)下的平均匹配错误率作为评价指标. 对于两图G 和G ', 匹配错误率'**2F1(,)1,c c ii ii cii x x ''∆=-∑X X X其中, *X 为模型求解的匹配结果, ()c cii x '=X 为正确的匹配, F ∙是Frobenius 范数.5.1 House/Hotel 数据集House 数据集①和hotel 数据集②是2个广泛用来测试图匹配效果的数据集. House 数据集是一个包含111帧连续变化的玩具房子的图像序列, 每一帧包含30个标记点. Hotel 数据集与house 数据集类似, 包含101帧连续变化的图像, 每一帧同样包含30个标记点. 这2个数据集的样例如图4所示.a. house 数据集上的标记点b. hotel 数据集上的标记点图4 house/hotel 数据集样例图5~6所示为上述6种模型在house/hotel 数据集上的实验效果. 从图5~6可以看出, 3种学习图匹配模型较3种非学习图匹配模型在匹配正确率上有较大的提升; 尽管帧差为50时, GNCCP, IPFP 以及E-GM 在2个数据集上都表现出了很好的效果, 但随着帧差的继续增大, 特征间的相似度出现越来越大的偏差, 平均匹配错误率增幅变大, 这验证了学习图匹配模型在处理形变问题上的优势; 另外, PL-GM 在house 数据集上优于QL-GM, 但在hotel 数据集上当帧差大于70时劣于QL-GM; 而相比于PL-GM, QL-GM, ELC-GM 在各帧差下均取得了最优的效果, 且匹配效果较为稳定. 这一实验结果验证了前文的分析: ELC-GM 继承了线性学习图匹模型训练结果稳定的优势, 同时也具备二次学习图匹配模型的优势, 即考虑了图的结构信息, 提升了匹配精度.图7~8所示分别为PL-GM 和ELC-GM 在house 数据集中的第6, 96帧图像的匹配结果, 其中错误匹配数分别是3和0.5.2 合成数据集为了进一步验证模型在大幅形变、噪声影响下的效果, 本文还在3组合成数据集[16]上进行了实验, 这3种合成方法分别是旋转、剪切和加噪. 每组数据中均包含200帧连续渐变的图像, 形变程度随帧数的增加而增大, 每帧图像均包含35个标记点. 旋转数据集中图像的最大旋转角度为90°; 剪切数据集中的图像高度保持不变, 宽度逐渐扩展为原图像宽度的2倍; 加噪数据集中为图像添加高斯噪声, 标准差由0逐渐增加到20像素.图9~11所示为6种模型分别在旋转、剪切以及加噪数据集上的实验效果. 在旋转数据集上, 3种非学习图匹配模型因为无法应对大幅旋转问题, 表现效果较差; 而3种学习图匹配模型都取得了较好① //idb/html/motion/house/index.html ② //idb/html/motion/hotel/index.html第2期曾少锋, 等: 基于边特征的学习完全图匹配模型 241图5 测试模型在house数据集上的实验效果图6 测试模型在hotel数据集上的实验效果图7 PL-GM在house数据集上匹配结果示例图8 ELC-GM在house数据集上的匹配结果示例图9 测试模型在旋转数据集上的实验效果图10 测试模型在剪切数据上的实验效果图11 测试模型在加噪数据集上的实验效果的效果, 尤其是ELC-GM, 在各帧差下都得到了接近0的平均匹配错误率. 在剪切和加噪数据集上,相比于IPFP, E-GM, QL-GM, GNCCP均取得了不错的效果, 说明GNCCP具有较强的抗形变能力; QL-GM的效果较不理想, 一个可能的原因是文献[16]使用Delaunay三角分解获取边, 在剪切变换和噪声的影响下, Delaunay三角分解在不同帧之间获取的边出现了较大的偏差. 在剪切数据集上ELC- GM的效果也是最优的; 而在加噪数据集上ELC- GM与PL-GM效果相当, 这是因为噪声的随机性使得学习图匹配模型无法学习到一组可以描述这种随机性的权重, 影响了训练效果.图12所示为PL-GM在旋转数据集上帧差为图12 旋转不变因子对相似度计算的影响(旋转数据集)242 计算机辅助设计与图形学学报第29卷100时训练得到的权重w, 可以看出, 在旋转变化下, RIFSC的前60维已经失效, 而最后5维旋转不变因子在相似度计算中发挥了较大作用, 保证了计算得到的相似度的准确性.6 结语本文提出一种基于边特征的学习完全图匹配模型——ELC-GM. ELC-GM本质上是一种线性学习图匹配模型, 但模型使用边进行初次匹配, 从而使得ELC-GM也能够考虑图的结构信息. 另外, 本文改进了形状上下文特征描述方法——RIFSC, 以应对旋转问题. 在house/hotel数据集与3组合成数据集(旋转、剪切和加噪数据集)上的实验结果表明, ELC-GM获得了较好的效果; 旋转变换数据集上的实验也验证了RIFSC的有效性. 但是, ELC- GM采用完全图进行匹配, 这决定了它不适用于处理大规模顶点的图匹配问题.参考文献(References):[1] Bhuvanagiri K, Daga A V, Ramachandrula S, et al. Hand-drawnsymbol spotting using semi-definite programming based sub- graph matching[C] //Proceedings of International Conference on Frontiers in Handwriting Recognition. Los Alamitos: IEEE Computer Society Press, 2010: 283-288[2] Berg A C, Berg T L, Malik J. Shape matching and object rec-ognition using low distortion correspondences[C] //Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Los Alamitos: IEEE Computer Soci-ety Press, 2005: 26-33[3] Duchenne O, Joulin A, Ponce J. A graph-matching kernel forobject categorization[C] //Proceedings of IEEE International Conference on Computer Vision. Los Alamitos: IEEE Com-puter Society Press, 2011: 1792-1799[4] Kim G, Faloutsos C, Hebert M. Unsupervised modeling of ob-ject categories using link analysis techniques[C] //Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Los Alamitos: IEEE Computer Soci-ety Press, 2008: 1-8[5] Brendel W, Todorovic S. Learning spatiotemporal graphs ofhuman activities[C] //Proceedings of International Conference on Computer Vision. Los Alamitos: IEEE Computer Society Press, 2011: 778-785[6] Umeyama S. An eigendecomposition approach to weightedgraph matching problems[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1988, 10(5): 695-703[7] Wang H F, Hancock E R. Correspondence matching using ker-nel principal components analysis and label consistency con-straints[J]. Pattern Recognition, 2006, 39(6): 1012-1025[8] Tang Jun, Gao Tian, Liang Dong, et al. Point pattern matching:spectral descriptor based approach[J]. Journal of Computer- Aided Design & Computer Graphics, 2013, 25(9): 1338-1344 (in Chinese)(唐俊, 高天, 梁栋, 等. 点模式匹配——基于谱描述子的算法[J]. 计算机辅助设计与图形学学报, 2013, 25(9): 1338-1344)[9] Liu Zhiyong. Graph matching: a new concave relaxation func-tion and algorithm[J]. Acta Automatica Sinica, 2012, 38(5): 725-731(in Chinese)(刘智勇. 图模型匹配: 一种新的凹松弛函数及算法[J]. 自动化学报, 2012, 38(5): 725-731)[10] Almohamad H A, Duffuaa S O. A linear programming appro-ach for the weighted graph matching problem[J]. IEEE Trans-actions on Pattern Analysis and Machine Intelligence, 1993, 15(5): 522-525[11] Zhou F, De la Torre F. Factorized graph matching[C] //Pro-ceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Los Alamitos: IEEE Computer Society Press, 2012: 127-134[12] Cho M, Lee J, Lee K M. Reweighted random walks for graphmatching[M] //Lecture Notes in Computer Science. Heidelberg: Springer, 2010, 6315: 492-505[13] Zaslavskiy M, Bach F, Vert J P. A path following algorithm forthe graph matching problem[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(12): 2227-2242 [14] Lyzinski V, Fishkind D E, Fiori M, et al. Graph matching: relaxat your own risk[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016, 38(1): 60-73[15] Leordeanu M, Hebert M. Unsupervised learning for graph mat-ching[C] //Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Los Alamitos: IEEE Computer Society Press, 2009: 864-871[16] Caetano T S, McAuley J J, Cheng L, et al. Learning graphmatching[J]. IEEE Transactions on Pattern Analysis and Ma-chine Intelligence, 2009, 31(6): 1048-1058[17] Li Y J, Zeng S F, Yang Y. Image matching with multi-order fea-tures[J]. IEEE Signal Processing Letters, 2015, 22(12): 2214- 2218[18] Kuhn H W. The hungarian method for the assignment problem[J].Naval Research Logistics Quarterly, 1955, 2(1/2): 83-97 [19] Altman N S. An introduction to kernel and nearest-neighbornonparametric regression[J]. The American Statistician, 1992, 46(3): 175-185[20] Guibas L, Stolfi J. Primitives for the manipulation of generalsubdivisions and the computation of V oronoi[J]. ACM Transac-tions on Graphics, 1985, 4(2): 74-123[21] Belongie S, Malik J, Puzicha J. Shape matching and objectrecognition using shape contexts[J]. IEEE Transactions on Pat-tern Analysis and Machine Intelligence, 2002, 24(4): 509-522 [22] Liu Z Y, Qiao H. GNCCP—graduated nonconvexity and con-cavity procedure[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014, 36(6): 1258-1267[23] Marius L, Martial H, Rahul S. An integer projected fixed pointmethod for graph matching and MAP inference[C] //Proc-eedings of the Conference on Advances in Neural Information Processing Systems. Cambridge: MIT Press, 2009: 1114-1122第2期曾少锋, 等: 基于边特征的学习完全图匹配模型 243附录A 采样点个数对实验效果影响的分析因为边上采样点的个数对于实验效果会产生一定的影响, 所以本文测试了采样点分别为2, 3和4个时E L C-G M在各数据集上的实验效果,如图A1 所示. 可以看出, 随着采样点个数的增多, ELC-GM的表现效果趋好, 但是在采样点达到4个时其增长空间较为有限; 而且过多的采样点也会增加模型的求解复杂度. 综合考虑, 边上采样点个数取为4.图A1 采样点个数对ELC-GM实验效果的影响。

关于研究方向、就业前景与导师大半年没来这个论坛逛逛了，今天来到，忽然想起了一年前准备考北理工时懵懂无知的样子。

作为一个原外校的学生，对北理工的一切都是那样的陌生，当时多么希望能认识一位学长，在平时多指点指点自己，少走些弯路，但希望总归是希望，最终还是自己摸爬滚打一路走来。

此处，我想说的是关于复试后选择导师的有关事宜，当时由于自己选择导师时的无知与不负责任，导致我与自己的梦想越走越远，希望此文能够帮助学弟学妹们不要重蹈我的覆辙。

好的，废话少说，言归正传，首先说下选导师的步骤。

在我们之前，每届新生在开学之后都会召开师生双选会，在双选会上来选导师，但我们这届并没有，都是自己联系的导师。

有个别学生是在复试前找的导师，我觉得意义不大，因为去年的复试是相当公正严格的，而且复试成绩占的比重相当大，看过某个帖子计算了一下，实际总成绩中复试成绩和初试成绩大约各占一半，并不是表面上看去的三七分或者四六分，因此初试成绩低的朋友可千万不要放弃，机会也相当大的哦~我身边就有很多这样的例子（包括我）。

我是在复试结束回校的两周之后才开始联系导师的，当时对老师和研究方向不甚了解，在论坛上找了个介绍导师的帖子随便选了几个导师去联系（我发的邮件），结果前两个老师都说学生已经招满了，还好，第三个老师也就是我现在的导师给我打电话来了，第一句话就是“你怎么这么晚才找导师”。

因此，我个人的建议是复试前先瞄上自己心仪的导师，待复试名单出来后趁热打铁在回校之前去找导师面对面的交流，初试成绩很高的同学可以再复试前就去找比较牛的导师，当然，也有不少同学是开学之后联系的导师。

其实何时联系导师并不重要，重要的是你要找什么类型的导师，研究方向是否符合自己的兴趣爱好，下面我就来介绍介绍。

选择一个合适的导师至关重要，可以说决定着你将来的就业方向。

拿我来说，在读研之前我就非常想进银行的软开，但由于选导师前没有查清楚，随便报了位老师，结果现在的老师根本不搞数据库（一般搞数据库的进银行的概率比我们不搞数据库的概率大的多），可以说我现在已经放弃了进银行工作的梦想了。