算法导论大作业。
**名称：ontology-based subgraph querying
**出处：yinghui wu ，shengqi yang ，xifeng yan
university of california santa barbara
yinghui, sqyang, xyan}
学校：哈尔滨工业大学。
学院：软件学院。
背景。随着internet的迅猛发展，互联网上的信息正在随着指数的速度在迅速增长，出现了信息**的问题。在如此浩瀚的信息海洋中，检索到有价值的信息成为当前计算机检索系统必须解决的问题。
然而，图是计算机科学中的重要数据结构。随着信息技术地不断发展，出现了越来越多的以图作为逻辑表达的数据，例如化学分子结构式，生物网络，社会网络以及图像中的实体关系等等。另一方面，这些图数据本身的数据量也在不断增大。
如何有效地管理和挖掘海量的图数据是图数据库研究的核心问题。子图查询是图数据管理中的基本操作。具体地说，给定一个查询图q，在图数据库中找到所有包含查询图q的数据图。
子图查询广泛应用于各种新兴的应用当中。传统的基于子图同构的子图查询要求相同标签的匹配，这往往是过于严格把握在语义上贴近查询图的匹配。本文扩展了子图查询通过利用本体信息来识别语义相关的匹配：
（1）我们介绍的基于本体的子图查询，其中在一个给定的本体图中通过把查询映射到语义相关的子图上来修改子图同构。我们介绍一个衡量来度量匹配的相似度。基于该标准，我们引入一个找到在前k的最佳匹配的优化问题。
（2）我们为基于本体的子图查询提供一个过滤和验证框架，来确定（top-k）匹配的。该框架有效地从本体索引中提取一个数据图的一个小的子图，并进一步通过只访问提取的子图来计算匹配。（3）此外，我们显示，本体索引可以根据变化的数据图被有效地更新，从而使框架能够应对动态数据图表。
（4）与传统的字符查询方法比较，我们通过对合成图和现实世界的图进行实验验证了我们框架的有效性和效率性。
把发现的大量数据信息建模成图的形式是越来越常见，其中每个标记节点代表具有属性的现实生活中的实体，每条边表示两个实体之间的关系。然而高效的子图查询的需求也随之而来。在给定一个基于图q和数据图g的查询时，子图查询就是发现数据图g中是否存在与和图q同构相匹配的子图。
传统的子图查询采用相同标签的匹配，其要求q中的查询节点只能被映射到一个在g中具有相同的标签的节点。这就造成了，对于想要识别出某个领域的查询结果的相似翻译的匹配来说，是一个过度的伤害。在这种匹配中，一个查询节点会对应图g中的语义相关的数据节点，而不是一个具有相同标签的数据节点。
这种需求在社会网络、生物网络以及语义web和其他领域中的查询操作中都是显而易见的。
例如，在一个图fig.1所示是一个社交旅行网络的一小部分，没一个节点代表一个类型实体，如旅行团（(holiday tours (ht), culture tours (ct))，名胜景区(disneyland, royal
gallery (rg)),休闲中心(holiday plaza (hp), royal palace (rp)),或者是餐馆 (holiday cafe (hc), riverside)。每一条代表两个实体之间的关系。如做向导（guide），建议（recommend）。
当给定这么一个图q，要我们要寻找一些带有建议和向导的，并且附近有和“moonlight：相似参观的博物馆旅行时，传统的子图同构查询不能够在图g中识别出所有的相同标签。因为在g中没有与图q中相同或者大致相似的标签。
然而，在g中却有着和查询节点语义相近的数据节点，这是一个潜在的匹配算法。例如，节点royal gallery在g中直观地表现为一种博物馆。然而，单独凭借q和g也是无法决定相近关系的。
上面的例子说明了确定节点需要匹配那些和查询节点相类似的节点，而不是那些具有相同或相似的标签的节点。假设在查询节点和数据节点中输入相似信息为了解决这种问题，一些子图同构的扩展方法已经被提出，用来确定与相似节点的匹配。然而由观察可知，用户可能不具备充分的知识来提供这些信息体的概念。
为此，我们需要了解查询节点和数据节点之间的语义关系，也就是说，给定的查询节点的标签，根据对实体的标准描述，该节点的标签在语义上是接近的。这也就给出了新兴发展的图形本体论。一个本体图通常包括（1）一系列概念或实体，和（2）的一系列节点之间的语义关系。
本体图通过提供有关实体之间的关系和相似性的附加信息使得子图查询评估获得受益。
本体信息已被用于如关键词检索，语义查询和社交网络之中。然而，很少有人知道如何利用本体图进行有效的子图查询。此外，制定有效的查询评估技术是很重要的，尤其是当一个查询可能有多个“解释”，并且要根据本体的相似性进行匹配。
1、我们提出了基于本体的子图查询。
与子图同构和它的扩展相反，基于本体的子图查询通过利用本体图来测量节点的相似性。
基于查询的节点和其根据本体图的匹配的标签的总体相似性度，我们引入一个标准来排列q的匹配。该标准则引出了top-k问题。
2、基于所述标准，我们提出了一种过滤-验证框架，用于计算top-k的匹配问题。
3、此外，我们提供的技术来尽可能的维护本体索引。
4、我们通过用实际数据和模拟数据实验验证了我们的查询算法的有效性和效率。
对于以上的研究则需要我们做以下的相关工作，包括子图查询评估、基于本体的子图查询、图的抽象化。
ontology的概念起源于哲学领域，来自于形而上学的哲学分支，即“对世界上客观存在的事物进行分解，发现基本组成部分，今儿找出其抽象本质的研究方法”。近年来，人们将本体的概念引入人工智能和数据处理等领域。2024年studer等人提出：
“ontology是共享概念模型的明确的形式化规范说明。”本体可以被看作是一座桥，桥的一端是具体的语法形式，另一端是这种表达形式的概念模型，而桥的下面则是难以逾越的语义大河。本体是对领域实体存在。
本质的抽象，它强调实体间的联系，它主要包括包括以下方面。
1)概念模型：指通过抽象出客观世界中的一些现象的相关概念而得到概念模型，即概。
念系统所蕴涵的语义结构，是对某一事实结构的一组非正式的约束规则，可以理解和表达为。
一组概念(包括类、属性和过程)、定义和关系。
2) 明确：指所使用的概念的类型以及对这些概念使用上的约束都有了明确的定义。
3) 形式化：指本体论是计算机可读的(即能被计算机处理)，而不是完全用自然语言表。
达本体是计算机可读的。
4) 共享：指本体论的目标是捕获相关领域的知识，提供对该领域知识的共同理解，确。
定该领域内共同认可的词汇，并从不同层次的形式化模式上给出这些词汇和词汇间相互关系。
的明确定义。
数据图是一个有向图g=（v，e，l），其中v是一个有限集的数据节点，e是边集，其中(u, u‘) e表示数据从边缘节点u到u’，l为标签函数，其主要是给一个节点v∈v（或者边e∈e）分配一个标签l（v）（或l（e））。而在实际的l函数中，节点标签表示对实体的描述，边标签标示实体之间的关系。
查询图定义为一个有向图q = vq,eq, lq)，其中vq 和 eq分别是一组查询节点和查询边；lq是一个标签函数标记于每个顶点v ∈ vq (或 e ∈ eq), lq(u)(或 lq(e))是一个节点（或相应边）的标签。
在现实生活中应用的本体和它们之间的关系通常可以表示为标准化的本体图。
本体图o =(vr,er)是一个无向图，其中vr是一个节点集合，集合中的每个节点 vr ∈ vr 是一个实体的标签；而 er是标签中边的集合。其中每一条边er ∈ er 代表一条语义关系，比如，两个节点之间 “refer to”, is a”,“specialization”。
此外，我们定义了一个相似度函数sim(vr1, vr2 )，用来计算本体图o中节点vr1 和vr的相似度的，其真值在[0, 1]之间。基于本体查询，sim(vr1, vr2 ) 表示vr1和vr2间的距离，是单调递函数。并且sim(vr1, vr2 ) sim(vr2, vr1 )。
直观的说vr1与vr2的距离越短，他们的相似度越高。
给出一个查询图q = vq,eq, lq)，一个本体图o和一个数据图g = v, e,l),以及相似度函数sim()和相似度临界值θ,基于本体的子图查询就是要找出g中的子图g‘ =v’,e‘, l’) 满足从vq到v’的映射函数h。其中sim(l(h(u)),lq(u)) u，u‘）是一个查询变，当且仅当（h（u），h（u’））是一条数据边，并且他们拥有相同的边标签。由此我们可以通过映射函数h在q中进行对g的匹配，把所有匹配g’结果设为集合q（g）。
除此之外，当sim(u, v) ≥时，查询节点u的候选集可以作为节点v的集合。当我们假设g中所有节点的标签均来自于本体图o。
top-k 子图查询。
c(h) =sim(lq(u), l(h(u)))u ∈ vq
这个衡量标准支持语义上相近查询的匹配：相似分值c(h)越大，映射的越好。另一方面，如果子图g’根据相同节点标签来匹配，例如同构子图在h映射中，c(h)有最大的值。
当相似度临界值θ=1时，传统的同构子图是基于本体子图查询的一个特例。与此同时，这个衡量标准很自然地引出了最优化问题。在给定的q,g,o和常量k中，top-k问题则确定了q在g中前k个最大相似度的匹配结果。
由于很难降低同构测试的复杂性，所以我们采用本体图开发了一个过滤-验证框架来减少基于本体查询的输入。当接收到一个查询时，这个框架会按照以下步骤进行评估：
（1）索引结构：这个框架开始的结构是一个数据图g的本体索引，它作为概念图的集合。每个概念图示都是通过对本体图中具有相似标签的节点的整合，进而对g抽象化。
这个索引是预计算的，并随着g的改变而动态维护的。
2）过滤阶段：这个框架使用本体索引结构，要么来提取一个包含所有匹配的数据图中的一部分子图，要么来确定匹配的不存在。
3）验证阶段：这个框架从（1）所得到的的一部分子图中提取出最佳匹配，也就是top-k问题，而不用通过搜索实体的数据图。
ontoldx算法是用来给一个给定的数据图构建本体索引的。首先给定一个数据图g(v, e,l), 在o(|e| log |v |)时间内即可构建出本体索引。具体实现如下图：
对于给定的本体索引i，查询图q，数据图g，如果子图**为空，那么q(g)为空，否则q(g)=q(**)；同时**能够在o(|q||i|)时间内被计算出来（|i|或|q|表示在i或q中节点和边的总数量）。
算法大作业
零钱问题。02105111张旭。02105113陈松懋。1 问题描述。现有1元，2元，5元，10元，50元的零钱若干张，需要找钱，用最少的张数实现。分别用贪心发，分治法，动态规划法实现。2 define infinity 32767无穷大。define max 100 include int gre...
作业调度算法 先来先服务算法,短作业算法
操作系统 实验报告。题目 作业调度算法。班级 网络工程。姓名 朱锦涛。学号 e31314037 一 实验目的。用 实现页面调度算法，即先来先服务 fcfs 调度算法。短作业优先算法 高响应比优先调度算法。通过 的具体实现，加深对算法的核心的理解。二 实验原理。1.先来先服务 fcfs 调度算法。fc...
作业调度算法 先来先服务算法,短作业算法
操作系统 实验报告。题目 作业调度算法。班级 网络工程。姓名 朱锦涛。学号 e31314037 一 实验目的。用 实现页面调度算法，即先来先服务 fcfs 调度算法。短作业优先算法 高响应比优先调度算法。通过 的具体实现，加深对算法的核心的理解。二 实验原理。1.先来先服务 fcfs 调度算法。fc...