台湾论文下载
國立中央大學博碩士論文
http://thesis.lib.ncu.edu.tw/ETD-db/ETD-search-c/search
元智大学电子学位论文
http://etds.yzu.edu.tw/etdservice/bs?from=DEPT&deptid=C0009002
成功大学学位论文
http://etdncku.lib.ncku.edu.tw/ETD-db/ETD-search/search
国立台湾科技大学学位论文
http://pc01.lib.ntust.edu.tw:1793/ETD-db/ETD-search/search
朝阳科技大学学位论文
http://ethesys.lib.cyut.edu.tw/ETD-db/ETD-search/search
2009年4月8日星期三
相关教程
后缀树 Fast String Searching With Suffix Trees
http://maya.cs.depaul.edu/~classes/ds575/Suffix_Trees/index.html
台湾 朝阳科技大学硕博论文库
http://ethesys.lib.cyut.edu.tw/ETD-db/ETD-search-c/search
http://maya.cs.depaul.edu/~classes/ds575/Suffix_Trees/index.html
台湾 朝阳科技大学硕博论文库
http://ethesys.lib.cyut.edu.tw/ETD-db/ETD-search-c/search
2009年3月22日星期日
项目基金网站
国家自然科学基金网站http://www.nsfc.gov.cn/nsfc2008/index.htm
查询基金网站ISIS http://isis.nsfc.gov.cn/portal/index.asp
查询基金网站ISIS http://isis.nsfc.gov.cn/portal/index.asp
2009年3月15日星期日
A Survey on Ontology Mapping
A Survey on Ontology Mapping
[2006][SIGMOD][Namyoun Choi]
摘要： Ontology日益被看作使得异构系统和SW应用之间交互的关键因素。 本文介绍了本体映射的分类，描述了每种分类的特点。比较了这些特点和测量工具、系统和每类映射的相关工作。
一、Introduction：
1、本体的独立开发这一特性导致对相同领域或者重叠领域的本体的定义有所不同，而这些独立的 本体开发团体之间缺乏充分沟通，所以：
——需要使用本体映射来促进他们之间的互操作。
2、本文将本体映射分为三大类[相关论文]：
1）综合的、全局本体 <----> 局部本体 ——描述全局本体与局部本体之间的关系
[3]Learning to Match the Schemas of Data Sources: A Multistrategy Approach（2003） [4]Synthesizing an Integrated Ontology（2003） [1]Ontologies for Enterprise Knowledge Management（2003） [7]A Framework for Ontology Integration（2001）
2）局部本体 <----> 局部本体 ——使得在高度动态和分布的环境中的互操作成为可能
[6]C-OWL: Contextualizing Ontologies（2003） [1]Ontologies for Enterprise Knowledge Management（2003） [8]Semantic Coordination: A New Approach and an Application（2003） [9]Learning to Map between Ontologies on the Semantic Web（2003） [12]MAFRA – An Ontology Mapping FRAmework for the Semantic Web（2003） [13]Resolving Terminological Heterogeneity in Ontologies（2002） [14]Representing and reasoning about mappings between domain models（AAAI 2002）
3）mapping for 本体合并与联合 ——被作为本体重用处理的一种途径
[15]PROMPT: Algorithm and Tool for Automated Ontology Merging and Alignment(AAAI2000) [16]Ontomorph: A Translation System for Symbolic Knowledge（2000） [17]FCA-Merge:Bottom-Up Merging of Ontologies（2001） [18]Smart:Automated Support for Oontology Merging and Alignment（1999） [19]Rule Induction for Concept Hierarchy Alignment（(IJCAI 2001） [20]Anchor-PROMPT: Using Non-Local Context for Semantic Matching（(IJCAI 2001）
3、本文的内容：
基于详细的评价标准对这三类本体映射的工具和系统进行比较。这些标准是：
a、input requirements —— 需要的输入 b、level of user interaction —— 使用者交互的层次 c、type of output —— 输出的类型 d、content of output —— 输出的内容 e、the following five dimensions structural, lexical, domain, instance-based knowledge, and type of result ——结构的、词汇的、领域的、基于场合的知识、结果类型
4、全文分为四大部分：
Section2：meanings of ontology mapping, ontology integration,merging, and alignment
Section3： ·characteristics and application domains of three different categories of ontology mapping are discussed. ·The tools, systems, frameworks, and related work of ontology mapping are surveyed based on the three different ontology mapping categories. ·Then the overall comparison of tools or systems about ontology mapping is presented
Section4：conclusion and presentation of future work
二、术语：本体映射，本体综合，合并，联合
1、本体映射在很多领域中被用到：ontology integration, merging, and alignment ——这三个领域中所用的的工具都被归为本体映射使用的工具。
还有一个与之相关的领域：schema matching，是数据库中的主要研究内容,本文何种不涉及
[3]Learning to Match the Schemas of Data Sources: A Multistrategy Approach（2003） [36]A comparative analysis of methodologies for database schema integration(1986） [37]Semantic Integration Research in the Database Community: A Brief Survey(2005) [38]Corpus based schema matching(2005)
2、ontology integration, merging, and alignment——都可以被看成本体重用的一种方式
·ontology merging： ——从现存、不同的、并和同一主题相关的两个或者多个本体中生成单个、一致的本体的过程； ——其中被合并的那些本体是有相似性或者部分重叠的
·ontology integration： ——在两个或者多个现存的、不同的、并且描述不同主题的本体基础上生成单独的、在一个领域 中的本体 ——原来的多个本体应该是相关的，在他们在被合并后的结果中，原有的本体中的内容会有变化
·ontology alignment： ——建立两个原始本体之间的链接 ——本体联合的源本体是互相一致的、分离的；当需要充足的领域支持时才这么做。
3、ontology mapping（三种情况分别定义） 1）综合的、全局本体 <----> 局部本体
把存在于某一个本体中的一个概念映射到一个视图或者一个在其他本体之上的查询
2）局部本体 <----> 局部本体
在语义关系的基础上，把一个本体中的实体翻译为目标本体中的对应实体的过程。其中的源实体 和目标实体在语义概念上相关。
3）mapping for 本体合并与联合
在这种情况下，本体映射在源本体之间建立通信，并决定他们之间重叠的概念、同义词或者对其 他源本体来说独特的概念的集合。这种映射鉴别多个源本体之间的相似和不同之处，用于进行合 并或者联合。
三、本体映射的种类：
1、综合的、全局本体 <----> 局部本体
1.1 实力和缺点
优点：容易定义映射和找到映射的规则（因为有一个全局本体，全局本体提供共享的词汇） 缺点：缺乏可维护性和可测量性，因为局部本体的修改很容易影响到对全局本体的映射
该映射不能在包含不一致信息的相同或相似领域的不同本体之间进行，因为全局本体无法被创建
1.2 应用领域
SW、企业知识管理、信息/数据整合
1.3 工具、系统和相关工作 ·LSD（learning source description）:使用多策略学习方法的半自动创建语义映射。
包含多个Learner：分为两类 base learner 和 meta learner ——base learner：The Name Learner、Content Learner、Na?ve Bayes Learner、XML Learner ——meta learner：meta learner
映射过程分为两个阶段： ——training：a small set of data sources has been manually mapped to the mediated schema and is utilized to train the base learners and the meta learner ——matching：the trained learners predict mappings for new sources and match the schema of the new input source to the mediated schema
·MOMIS (Mediator Environment for Multiple Information Sources): MOMIS creates a global virtual view (GVV) of information sources, independent oftheir location or their data’s heterogeneity.
分为五个阶段：略
·A Framework for OIS(Ontology integration system):
——用描述逻辑来表达本体之间的映射query和本体 ——使用两种方法：从全局本体的每一个概念 --->局部本体的概念(global-centric approach) 从局部本体的每一个概念 --->Global本体的概念(localcentric approach)
2、局部本体 <----> 局部本体 （是一个重点）
更适合Web上的高度动态的，开放的，分布式环境下的互操作。
2.1 实力和缺点
优点：适用与各局部本体因为包含不一致的信息而不能被综合或合并时,提供他们之间的互操作。 缺点：局部本体之间缺少共同的词汇.
2.2 应用领域
Web,Semantic web
2.3 工具、系统和相关工作
·Context OWL：Contextualizing Ontologies
·CTXMATCH：CTXMATCH is an algorithm for discovering semantic mappings across hierarchical classifications (HCs) using logical deduction.
·GLUE：semi-automatically creates ontology mapping using machine learning techniques
·MAFRA：Ontology MAapping FRAmework for distributed ontologies in the Semantic Web provides a distributed mapping process that consists of five horizontal and four vertical modules.
·LOM：Lexicon-based Ontology Mapping
·QOM：Quick Ontology Mapping，a efficient method for identifying mappings between two ontologies because it has lower run-time complexity.
·ONION：ONtology compositION system
·OKMS：Ontology-based knowledge management system。mapping is used for combining distributed and heterogeneous ontologies
·OMEN：Ontology Mapping Enhancer，OMEN is a probabilistic ontology mapping tool which enhances the quality of existing ontology mappings using a Bayesian Net
·P2P ontology mapping：This work proposes the framework which allows agents to interact with other agents efficiently based on the dynamic mapping of only the portion of ontologies relevant to the interaction.
3、mapping for 本体合并与联合
可以通过合并处理创建一个一致的本体。It also creates links between local ontologies while they remain separate during the ontology alignment process.
映射不存在于合并后得到的的本体 与 被合并的若干局部本体之间， 但存在于被合并的若干局部本体之间。
第一步：找出待合并或者待联合的多个局部本体之间的相似和冲突。
3.1 实力和缺点
3.2 应用领域
Many applications such as standard search, e-commerce, government intelligence, medicine, etc., have large-scale ontologies and require the reuse of ontology merging processes。
3.3 工具、系统和相关工作
·SMAR：SMART is a semi-automatic ontology merging and alignment tool.
·PROMPT：PROMPT is a semi-automatic ontology merging and alignment tool.
·OntoMorph: OntoMorph provides a powerful rule language for specifying mappings, and facilitates ontology merging and the rapid generation of knowledge-base translators.
·HICAL (Hierarchical Concept Alignment system): provides concept hierarchy management for ontology merging/alignment (one concept hierarchy is aligned with another concept in another concept hierarchy), uses a machine-learning method for aligning multiple concept hierarchies, and exploits the data instances in the overlap between the two taxonomies to infer mappings.
·Anchor-PROMPT：takes a set of anchors (pairs of related terms) from the source ontologies and traverses the paths between the anchors in the source ontologies.
·CMS (CROSI Mapping System): CMS is an ontology alignment system.
·FCA-Merge：a method for ontology merging based on Ganter and Wille’s formal concept analysis, lattice exploration, and instances of ontologies to be merged.
·CHIMAERA: CHIMAERA is an interactive ontology merging tool based on the Ontolingual ontology editor.
4、本体映射工具和系统的比较
四、结论
[文中的一个图]
下面要重点看的五篇论文：
A、[2002][www][ AH Doan][Learning to Map Between ontologies on the semantic web]B、[2002][EKAW][Alexander Maedche][MAFRA— A MApping FRAmework for Distributed Ontologies] C、[2003][IEEE Internet Computing][D Beneventano][Synthesizing an integrated ontology](未打)D、[2004][ISWC][John Li][QOM - Quick Ontology Mapping](未打)E、[2003][IEEE Intelligent Systems][A Maedche][Ontologies for enterprise knowledge management](未打)
[2006][SIGMOD][Namyoun Choi]
摘要： Ontology日益被看作使得异构系统和SW应用之间交互的关键因素。 本文介绍了本体映射的分类，描述了每种分类的特点。比较了这些特点和测量工具、系统和每类映射的相关工作。
一、Introduction：
1、本体的独立开发这一特性导致对相同领域或者重叠领域的本体的定义有所不同，而这些独立的 本体开发团体之间缺乏充分沟通，所以：
——需要使用本体映射来促进他们之间的互操作。
2、本文将本体映射分为三大类[相关论文]：
1）综合的、全局本体 <----> 局部本体 ——描述全局本体与局部本体之间的关系
[3]Learning to Match the Schemas of Data Sources: A Multistrategy Approach（2003） [4]Synthesizing an Integrated Ontology（2003） [1]Ontologies for Enterprise Knowledge Management（2003） [7]A Framework for Ontology Integration（2001）
2）局部本体 <----> 局部本体 ——使得在高度动态和分布的环境中的互操作成为可能
[6]C-OWL: Contextualizing Ontologies（2003） [1]Ontologies for Enterprise Knowledge Management（2003） [8]Semantic Coordination: A New Approach and an Application（2003） [9]Learning to Map between Ontologies on the Semantic Web（2003） [12]MAFRA – An Ontology Mapping FRAmework for the Semantic Web（2003） [13]Resolving Terminological Heterogeneity in Ontologies（2002） [14]Representing and reasoning about mappings between domain models（AAAI 2002）
3）mapping for 本体合并与联合 ——被作为本体重用处理的一种途径
[15]PROMPT: Algorithm and Tool for Automated Ontology Merging and Alignment(AAAI2000) [16]Ontomorph: A Translation System for Symbolic Knowledge（2000） [17]FCA-Merge:Bottom-Up Merging of Ontologies（2001） [18]Smart:Automated Support for Oontology Merging and Alignment（1999） [19]Rule Induction for Concept Hierarchy Alignment（(IJCAI 2001） [20]Anchor-PROMPT: Using Non-Local Context for Semantic Matching（(IJCAI 2001）
3、本文的内容：
基于详细的评价标准对这三类本体映射的工具和系统进行比较。这些标准是：
a、input requirements —— 需要的输入 b、level of user interaction —— 使用者交互的层次 c、type of output —— 输出的类型 d、content of output —— 输出的内容 e、the following five dimensions structural, lexical, domain, instance-based knowledge, and type of result ——结构的、词汇的、领域的、基于场合的知识、结果类型
4、全文分为四大部分：
Section2：meanings of ontology mapping, ontology integration,merging, and alignment
Section3： ·characteristics and application domains of three different categories of ontology mapping are discussed. ·The tools, systems, frameworks, and related work of ontology mapping are surveyed based on the three different ontology mapping categories. ·Then the overall comparison of tools or systems about ontology mapping is presented
Section4：conclusion and presentation of future work
二、术语：本体映射，本体综合，合并，联合
1、本体映射在很多领域中被用到：ontology integration, merging, and alignment ——这三个领域中所用的的工具都被归为本体映射使用的工具。
还有一个与之相关的领域：schema matching，是数据库中的主要研究内容,本文何种不涉及
[3]Learning to Match the Schemas of Data Sources: A Multistrategy Approach（2003） [36]A comparative analysis of methodologies for database schema integration(1986） [37]Semantic Integration Research in the Database Community: A Brief Survey(2005) [38]Corpus based schema matching(2005)
2、ontology integration, merging, and alignment——都可以被看成本体重用的一种方式
·ontology merging： ——从现存、不同的、并和同一主题相关的两个或者多个本体中生成单个、一致的本体的过程； ——其中被合并的那些本体是有相似性或者部分重叠的
·ontology integration： ——在两个或者多个现存的、不同的、并且描述不同主题的本体基础上生成单独的、在一个领域 中的本体 ——原来的多个本体应该是相关的，在他们在被合并后的结果中，原有的本体中的内容会有变化
·ontology alignment： ——建立两个原始本体之间的链接 ——本体联合的源本体是互相一致的、分离的；当需要充足的领域支持时才这么做。
3、ontology mapping（三种情况分别定义） 1）综合的、全局本体 <----> 局部本体
把存在于某一个本体中的一个概念映射到一个视图或者一个在其他本体之上的查询
2）局部本体 <----> 局部本体
在语义关系的基础上，把一个本体中的实体翻译为目标本体中的对应实体的过程。其中的源实体 和目标实体在语义概念上相关。
3）mapping for 本体合并与联合
在这种情况下，本体映射在源本体之间建立通信，并决定他们之间重叠的概念、同义词或者对其 他源本体来说独特的概念的集合。这种映射鉴别多个源本体之间的相似和不同之处，用于进行合 并或者联合。
三、本体映射的种类：
1、综合的、全局本体 <----> 局部本体
1.1 实力和缺点
优点：容易定义映射和找到映射的规则（因为有一个全局本体，全局本体提供共享的词汇） 缺点：缺乏可维护性和可测量性，因为局部本体的修改很容易影响到对全局本体的映射
该映射不能在包含不一致信息的相同或相似领域的不同本体之间进行，因为全局本体无法被创建
1.2 应用领域
SW、企业知识管理、信息/数据整合
1.3 工具、系统和相关工作 ·LSD（learning source description）:使用多策略学习方法的半自动创建语义映射。
包含多个Learner：分为两类 base learner 和 meta learner ——base learner：The Name Learner、Content Learner、Na?ve Bayes Learner、XML Learner ——meta learner：meta learner
映射过程分为两个阶段： ——training：a small set of data sources has been manually mapped to the mediated schema and is utilized to train the base learners and the meta learner ——matching：the trained learners predict mappings for new sources and match the schema of the new input source to the mediated schema
·MOMIS (Mediator Environment for Multiple Information Sources): MOMIS creates a global virtual view (GVV) of information sources, independent oftheir location or their data’s heterogeneity.
分为五个阶段：略
·A Framework for OIS(Ontology integration system):
——用描述逻辑来表达本体之间的映射query和本体 ——使用两种方法：从全局本体的每一个概念 --->局部本体的概念(global-centric approach) 从局部本体的每一个概念 --->Global本体的概念(localcentric approach)
2、局部本体 <----> 局部本体 （是一个重点）
更适合Web上的高度动态的，开放的，分布式环境下的互操作。
2.1 实力和缺点
优点：适用与各局部本体因为包含不一致的信息而不能被综合或合并时,提供他们之间的互操作。 缺点：局部本体之间缺少共同的词汇.
2.2 应用领域
Web,Semantic web
2.3 工具、系统和相关工作
·Context OWL：Contextualizing Ontologies
·CTXMATCH：CTXMATCH is an algorithm for discovering semantic mappings across hierarchical classifications (HCs) using logical deduction.
·GLUE：semi-automatically creates ontology mapping using machine learning techniques
·MAFRA：Ontology MAapping FRAmework for distributed ontologies in the Semantic Web provides a distributed mapping process that consists of five horizontal and four vertical modules.
·LOM：Lexicon-based Ontology Mapping
·QOM：Quick Ontology Mapping，a efficient method for identifying mappings between two ontologies because it has lower run-time complexity.
·ONION：ONtology compositION system
·OKMS：Ontology-based knowledge management system。mapping is used for combining distributed and heterogeneous ontologies
·OMEN：Ontology Mapping Enhancer，OMEN is a probabilistic ontology mapping tool which enhances the quality of existing ontology mappings using a Bayesian Net
·P2P ontology mapping：This work proposes the framework which allows agents to interact with other agents efficiently based on the dynamic mapping of only the portion of ontologies relevant to the interaction.
3、mapping for 本体合并与联合
可以通过合并处理创建一个一致的本体。It also creates links between local ontologies while they remain separate during the ontology alignment process.
映射不存在于合并后得到的的本体 与 被合并的若干局部本体之间， 但存在于被合并的若干局部本体之间。
第一步：找出待合并或者待联合的多个局部本体之间的相似和冲突。
3.1 实力和缺点
3.2 应用领域
Many applications such as standard search, e-commerce, government intelligence, medicine, etc., have large-scale ontologies and require the reuse of ontology merging processes。
3.3 工具、系统和相关工作
·SMAR：SMART is a semi-automatic ontology merging and alignment tool.
·PROMPT：PROMPT is a semi-automatic ontology merging and alignment tool.
·OntoMorph: OntoMorph provides a powerful rule language for specifying mappings, and facilitates ontology merging and the rapid generation of knowledge-base translators.
·HICAL (Hierarchical Concept Alignment system): provides concept hierarchy management for ontology merging/alignment (one concept hierarchy is aligned with another concept in another concept hierarchy), uses a machine-learning method for aligning multiple concept hierarchies, and exploits the data instances in the overlap between the two taxonomies to infer mappings.
·Anchor-PROMPT：takes a set of anchors (pairs of related terms) from the source ontologies and traverses the paths between the anchors in the source ontologies.
·CMS (CROSI Mapping System): CMS is an ontology alignment system.
·FCA-Merge：a method for ontology merging based on Ganter and Wille’s formal concept analysis, lattice exploration, and instances of ontologies to be merged.
·CHIMAERA: CHIMAERA is an interactive ontology merging tool based on the Ontolingual ontology editor.
4、本体映射工具和系统的比较
四、结论
[文中的一个图]
下面要重点看的五篇论文：
A、[2002][www][ AH Doan][Learning to Map Between ontologies on the semantic web]B、[2002][EKAW][Alexander Maedche][MAFRA— A MApping FRAmework for Distributed Ontologies] C、[2003][IEEE Internet Computing][D Beneventano][Synthesizing an integrated ontology](未打)D、[2004][ISWC][John Li][QOM - Quick Ontology Mapping](未打)E、[2003][IEEE Intelligent Systems][A Maedche][Ontologies for enterprise knowledge management](未打)
Similarity Flooding
Similarity Flooding
http://www.blogjava.net/weidagang2046/articles/81825.html
算法大致思路： 把要匹配的模型转换为带标记的有向图（directed labeled graphs。由节点和弧组成的图，允许对象用自身的属性及其和其他对象的关系来定义，类似于ER图）。这些图要用来做迭代的不动点计算，计算结果将告诉我们一张图里的哪些节点和第二张图的节点相似。 为了计算相似度，我们利用了这样一个直觉：两个不同的节点是相似的，当它们邻接元素是相似的。换句话说，两个元素相似性的一部分传播给了它们各自的邻居，这种传播方式类似于IP广播，这也是SF这个名字的由来。我们把算法的结果叫做一个 mapping，然后根据匹配目标，选择特定的过滤器来过滤出一个原始结果的子集。我们希望能够人工对结果进行修正，需要修正的成员数目就反映了算法的准确性。概述： 假设有2个schema，S1和S2。我们要为S1里每一个元素在S2中找到匹配的元素。 过程如下： 1. G1 = SQL2Graph(S1); G2 = SQL2Graph(S2); 把schema变成图，图采用了Open Information Model (OIM)规格，图中node采用矩形和卵形，矩形是文字描述，卵形是标识符 2. initialMap = StringMatch(G1, G2); 用字符串匹配做为初始匹配，主要是比较通常的前缀和后缀，这样的结果通常是不准确的 3. product = SFJoin(G1, G2, initialMap); 用SF算法生成结果。假设两个不同的节点是相似的，则它们邻接元素的相似度增加。经过一系列的迭代，这种相似度会传遍整个图 4. result = SelectThreshold(product); 结果筛选SF算法 图中的每条边，用一个三元组表示（s，p，o），分别是 源点，边名，目的点。 相似度传播图：首先定义pairwise connectivity graph(PCG) ： ((x; y); p; (x'; y')) 属于 PCG(A;B)<==>(x; p; x') € A and (y; p; y') € B。 关键是p要相同，也就是边的名字一样。式子从右向左推导，就可以A、B从两个模型建立起它们的PCG。图中的每个节点，都是A和B中的元素构成的2元组，叫做map pairs。 induced propagation graph。从PCG推导而来，加上了反向的边，边上注明了[传播系数]，值为 1/n，n为相应的边的数目。 不动点计算： 设ó(x; y) > 0 代表了节点x € A 和 y € B 的相似度，是在整个 A X B的范围上定义的。我们把 ó 叫做 mapping。相似度的计算就是基于ó-values的迭代计算。设 ói 代表了第 i 次迭代后的结果，ó0 是初始相似度（可以用字符串相似度的办法的得出，在我们的例子里，没有 ó0 ，即让 ó0 =1）。 每次迭代中，ó-values 都会根据其邻居paris的 ó-values 乘以[传播系数] 来增加。例如，在第一次迭代 ó1(a1; b1) = ó0(a1; b1) + ó0(a; b) * 0.5 = 1.5。类似的，ó1(a, b) = ó0(a, b) + ó0(a1; b1) * 1.0 + ó0(a2, b1) *1.0 = 3.0。接下来，所有 ó 值进行正规化，比如除以当前迭代的 ó的最大值，保证所有 ó 都不大于1。所以在正规化以后，ó1(a; b) = 1.0, ó1(a1, b1) = 1.5/3.0 = 0.5。一般情况下，迭代如下进行：
上面的计算进行迭代，直到 ón 和 ón-1之间的差别小于一个阈值，如果计算没有聚合，我们就在迭代超过一定次数后停止。上图3的第三副图，就是5次迭代后的结果。表3时一些计算方法，后面的实验表明，C比较好。A叫做 sparce，B叫做 excepted，C叫做verbose过滤 迭代出的结果是一种[多匹配]，可能包含有用的匹配子集。 三个步骤： 1。用程序定义的[限制条件]进行过滤。 2。用双向图中的匹配上下文技术进行过滤 3。比较各种技术的有效性（满足用户需求的能力） 限制：主要有两种，一个是[类型]限制，比如只考虑[列]的匹配（匹配双方都是列）。第二个是 cardinality 限制，即模式S1中的所有元素都要在S2中有一个映射。stable marriage问题：n女和n男配对，不存在这样的两对 (x; y)和(x0; y0)，其中x喜欢 y0 胜过 y，而且 y0 喜欢 x 胜过 x0。具有stable marriage的匹配结果的total satisfaction可能会比不具有stable marriage的匹配结果还低！匹配质量的评估 基本的评估思想，就是 用户对匹配结果做的修改越少，匹配质量就越高（修改结果包括去掉错误的pair，加上正确的pair） n是找到的匹配数，m是理想的匹配数，c是用户作出修正的数目。
http://www.blogjava.net/weidagang2046/articles/81825.html
算法大致思路： 把要匹配的模型转换为带标记的有向图（directed labeled graphs。由节点和弧组成的图，允许对象用自身的属性及其和其他对象的关系来定义，类似于ER图）。这些图要用来做迭代的不动点计算，计算结果将告诉我们一张图里的哪些节点和第二张图的节点相似。 为了计算相似度，我们利用了这样一个直觉：两个不同的节点是相似的，当它们邻接元素是相似的。换句话说，两个元素相似性的一部分传播给了它们各自的邻居，这种传播方式类似于IP广播，这也是SF这个名字的由来。我们把算法的结果叫做一个 mapping，然后根据匹配目标，选择特定的过滤器来过滤出一个原始结果的子集。我们希望能够人工对结果进行修正，需要修正的成员数目就反映了算法的准确性。概述： 假设有2个schema，S1和S2。我们要为S1里每一个元素在S2中找到匹配的元素。 过程如下： 1. G1 = SQL2Graph(S1); G2 = SQL2Graph(S2); 把schema变成图，图采用了Open Information Model (OIM)规格，图中node采用矩形和卵形，矩形是文字描述，卵形是标识符 2. initialMap = StringMatch(G1, G2); 用字符串匹配做为初始匹配，主要是比较通常的前缀和后缀，这样的结果通常是不准确的 3. product = SFJoin(G1, G2, initialMap); 用SF算法生成结果。假设两个不同的节点是相似的，则它们邻接元素的相似度增加。经过一系列的迭代，这种相似度会传遍整个图 4. result = SelectThreshold(product); 结果筛选SF算法 图中的每条边，用一个三元组表示（s，p，o），分别是 源点，边名，目的点。 相似度传播图：首先定义pairwise connectivity graph(PCG) ： ((x; y); p; (x'; y')) 属于 PCG(A;B)<==>(x; p; x') € A and (y; p; y') € B。 关键是p要相同，也就是边的名字一样。式子从右向左推导，就可以A、B从两个模型建立起它们的PCG。图中的每个节点，都是A和B中的元素构成的2元组，叫做map pairs。 induced propagation graph。从PCG推导而来，加上了反向的边，边上注明了[传播系数]，值为 1/n，n为相应的边的数目。 不动点计算： 设ó(x; y) > 0 代表了节点x € A 和 y € B 的相似度，是在整个 A X B的范围上定义的。我们把 ó 叫做 mapping。相似度的计算就是基于ó-values的迭代计算。设 ói 代表了第 i 次迭代后的结果，ó0 是初始相似度（可以用字符串相似度的办法的得出，在我们的例子里，没有 ó0 ，即让 ó0 =1）。 每次迭代中，ó-values 都会根据其邻居paris的 ó-values 乘以[传播系数] 来增加。例如，在第一次迭代 ó1(a1; b1) = ó0(a1; b1) + ó0(a; b) * 0.5 = 1.5。类似的，ó1(a, b) = ó0(a, b) + ó0(a1; b1) * 1.0 + ó0(a2, b1) *1.0 = 3.0。接下来，所有 ó 值进行正规化，比如除以当前迭代的 ó的最大值，保证所有 ó 都不大于1。所以在正规化以后，ó1(a; b) = 1.0, ó1(a1, b1) = 1.5/3.0 = 0.5。一般情况下，迭代如下进行：
上面的计算进行迭代，直到 ón 和 ón-1之间的差别小于一个阈值，如果计算没有聚合，我们就在迭代超过一定次数后停止。上图3的第三副图，就是5次迭代后的结果。表3时一些计算方法，后面的实验表明，C比较好。A叫做 sparce，B叫做 excepted，C叫做verbose过滤 迭代出的结果是一种[多匹配]，可能包含有用的匹配子集。 三个步骤： 1。用程序定义的[限制条件]进行过滤。 2。用双向图中的匹配上下文技术进行过滤 3。比较各种技术的有效性（满足用户需求的能力） 限制：主要有两种，一个是[类型]限制，比如只考虑[列]的匹配（匹配双方都是列）。第二个是 cardinality 限制，即模式S1中的所有元素都要在S2中有一个映射。stable marriage问题：n女和n男配对，不存在这样的两对 (x; y)和(x0; y0)，其中x喜欢 y0 胜过 y，而且 y0 喜欢 x 胜过 x0。具有stable marriage的匹配结果的total satisfaction可能会比不具有stable marriage的匹配结果还低！匹配质量的评估 基本的评估思想，就是 用户对匹配结果做的修改越少，匹配质量就越高（修改结果包括去掉错误的pair，加上正确的pair） n是找到的匹配数，m是理想的匹配数，c是用户作出修正的数目。
Similarity Flooding全
Similarity Flooding全 摘要： 在两个data schemas 或者data instances中做元素的匹配在数据仓库、电子商务等领域都很重要。本文中我们提出了一个匹配算法，基于不动点计算，适用于不同场景。算法以两个图作为输入，输出图中对应结点的映射。根据匹配目标，用过滤器选出一个映射的子集。算法运行后，我们期望用人来检查，看是否需要修正结果。事实上，我们根据需要进行修正的数目来评估算法的准确性。我们引入一个例子，使用accuracy metric 来评估用户利用我们的算法来得到一个初始匹配能节省多少时间。最终，我们讨论了如何把算法部署为高级别的运算符，在一个用于管理信息模型和映射的已实现了testbed中。Keywords: Matching, Model Management, Heterogeneous Databases, Semistructured Data1。引言2。方法概述3。SF算法 相似度传播图Similarity propagation graph 不动点计算 4。过滤器 限制 选择的度量指标 Selection metrics5。算法特性的例子 半结构化数据 XML模式 两种不同的基于图的表示：OEM/Lore、XML/DOM standard。在OEM表示法中，元素tags被当作边标注，DOM表示法把元素间的关系表示为特定的边标注“child”。 首先，算法对于不同的表示法产生了相似的结果。其次，例子显示了 使用wider spectrum的边标注，会有一个更快的迭代计算。两种表示法虽然图形大小差不多，但是OEM的相似度传播图笔DOM小一半，而且不动点计算的每次迭代都比较快。 用实例数据来匹配XML模式 查找相关的东西6。匹配质量的评估 匹配准确性 Intended match result7。算法和过滤器的评估8。体系结构和实现9。算法的局限 Open Issues and Limitations 1。算法只对于有向labeled图有效。当边名唯一或者无向时候，或者当结点之间的区别模糊的时候会退化。 2。只能匹配同类型的模型 3。一个重要假设就是邻接性对相似度传播的贡献。所以如果无法保存邻接性的信息，则算法无法正常工作。 4。算法会给superstructures.更高的相似度 5。算法未考虑顺序和聚合。如果考虑了，对匹配XML很有帮助 6。算法的独立版本不如为一个特定领域开发的matchers有效10。相关工作11。结论参考文献附录A：内部数据模型设 U为 Unicode alphabet，U*为在U上定义的字符串集合。 entity集合E，statement集合V用如下的递归定义：1. U* × U* 属于 E (任何由2个string组合的二元组都是一个实体，第一个string是entity的type或者namespace，第二个string是entity的名字)2. E×E ×E 属于 V (every tuple of three entities constitutes a statement)3. V 属于 E (every statement is an entity)4. V 和 E 是具有以上属性的最小集合. V的一个子集称为model。以上的定义和终结符基于RDF标准。根据递归定义中的V和E表明，statements可以是嵌套的（一个statement 可以当作另一个statement 中的元素）。在我们的内部数据结构中，嵌套的statement 被用作表示次序关系和聚合。目前，我们文中提到的匹配算法没有用到这些方面。所以，我们不进行嵌套statement 的进一步讨论。我们可以做一个简单的假设：E = U* × U*，V=E3 。所以，一个 model是E3 的子集。在图中，entity就是结点，statement就是边。任何statement (s; p; o)，（中间的元素p叫做predicate）用边上的标注来描述。有共同谓词的声明定义了一个实体间的二元关系)OIM图中，矩形结点被叫做[literals]，属于实体 L = {"literal"}× U*。literals和其他实体没有本质区别，我们在图形上区分，主要为了更好的可读性。模型M1 和 M2 之间的映射可以被从概念上看作一个元组的集合(n1; n2; o)，因此belongsTo(n1;M1); belongsTo(n2;M2) 和o都是实际的数字，代表了相似度。当M1 M2 没有共享元素，映射可以被定义为代权的无向双向图。为了把映射当作模型，模型被表示为一个声明的集合。对于每一个元组t = (n1; n2; o)，我们建立四个声明：1. (node(t); type; MapEntry)2. (node(t); src; n1)3. (node(t); dest; n2)4. (node(t); similarity;o)附录B：算法的通用版本 Generalized version附录C：传播系数 Propagation coefficients附录D：算法的收敛性和复杂度 Convergence and complexity of the algorithm SF的不动点计算可以表达为如下的特征向量计算。T 是一个方形矩阵，和从模型A、B得到的相似度传播图G对应。如果有一条边连接 j = (x; y) 和 i = (x'; y')，传播系数 c, 让矩阵条目 tij = c.其他条目都置0 。注意G中传播系数符合跃迁可能性，如果T是一个跃迁矩阵。 当T是一个aperiodic, irreducible matrix (Ergodic theorem)时，不动点计算是收敛的。矩阵 T是 irreducible的，当且仅当 associated graph G 是强连通的(每个结点都可以从任意其他结点达到). 为了保证这些特性，我们可以在G中引入self-loops，通过在不动点方程中包含被加数 o0。例如，让oi+1 = normalize(o0 + p(oi))。这个方法在文学中被称为dampening（使沮丧？）。如果o0 赋了一个非零值给A×B中的每一个map pair, 则加上o0 就相当于把G修改为G'，其中所有结点都通过特定的传播系数互相连接。让 T'成为和 G'联系的矩阵。 可以如下表示特征向量计算。 设 S 为一个 map pair vector，在每一个位置包含了一个来自o的相似度的值，形成一个map pairs的固定顺序。我们不动点的迭代计算，对应矩阵乘法 T’×S。反复相乘，产生了矩阵T’的占优势的特征向量S*，例如 T’×S* = LS*，其中L是T’的占优势的特征值。在不动点方程中，通过把 T’×S*除以L来进行标准化。 不动点计算符合计算T的马尔科夫链。这个事实提供了一个有趣的对算法的深入透视。因为T符合G上的跃迁矩阵，获得的相似度度量标准可以被视为从pair到pair的随机走动导致的map pairs的固定的概率分布。这个随机的走动符合一个人设计师对A和B的手工匹配过程。从一个给定的map pair 开始，设计师基于A和B的结构性特性来推断和另一个map pair的相似度。假设A和B是关系模式的模型。 如果设计师得出结论 A中的表t1和B中的表t2匹配，则有一个确定的可能性，他/她下一步就是匹配t1和t2中的列。 不动点计算的conversion rate依赖于T的dominant和the second eigenvalue的比率，由G’的结构化特性所决定。较高的dampening values代表了矩阵更快的conversion rate。 复杂度：每次迭代中操作的次数 正比于传播图G中的边数，和模型A、B边数的乘积成正比。
订阅：
评论 (Atom)