【摘 要】
：
提出了一种在图数据库中建立相似匹配查找的索引方法。因为图的近似匹配是一个NP难问题,为了避免在数据库上的顺序查找,利用k-邻接子图索引一个大规模的图数据库,首先给出k-邻接子图索引的过滤机制以及生成k-邻接子图集的广度优先搜索算法,然后通过建立k-邻接子图字典的方法压缩存储空间并优化索引,最后讨论索引的维护方法。对于一个基于编辑距离范围的近似查询,通过在k-邻接子图索引上的过滤,最终可以得到一个远
【机 构】
：
东北大学信息科学与工程学院 沈阳 110004
【出 处】
：
第二十五届中国数据库学术会议(NDBC2008)
论文部分内容阅读
提出了一种在图数据库中建立相似匹配查找的索引方法。因为图的近似匹配是一个NP难问题,为了避免在数据库上的顺序查找,利用k-邻接子图索引一个大规模的图数据库,首先给出k-邻接子图索引的过滤机制以及生成k-邻接子图集的广度优先搜索算法,然后通过建立k-邻接子图字典的方法压缩存储空间并优化索引,最后讨论索引的维护方法。对于一个基于编辑距离范围的近似查询,通过在k-邻接子图索引上的过滤,最终可以得到一个远小于数据库数量的图集合作为精确匹配的候选集,大大减小了匹配所需的时间和空间.
其他文献
针对XML数据中大量的数据冗余,已有很多XML数据压缩方法的研究,但结合具体应用对XML数据压缩进行的研究还很少.以生物XML数据为研究对象,提出基于Schema提取可压缩子结构的XML压缩算法SCSC.根据生物XML数据层次嵌套简单、子结构重复高频出现的特点,提出可压缩子结构的概念.利用XML Schema提供的丰富结构信息建立XML扩充结构树,提取可压缩子结构,并设计可压缩子结构编码方案,对X
作为互联网上数据的表示和交换事实上的标准,XML已经广泛应用于许多领域.提出一种基于相关性(related)语义来扩充XPath的表达能力,使得用户在不了解文档模式的情况下可以轻松表达自身的查询请求.提出基于related语义的XML Twig查询处理方法rTwigStack,可以高效处理包含related语义的查询.在此基础上,提出基于DTD模式的优化算法rTwigStack+来提高查询效率。通
目前一些比较成熟的数据流管理系统,大都使用多元存储模型在内存中存储数据.研究表明,多元存储模型的缓存利用率不高,在处理大量、快速、时变的数据流时,影响查询的响应速度.为了更好地管理和存储来自无线传感器网络的实时数据流,提高查询性能,提出一种带时间偏移的页面存储模型(model using time offset,MUTO).它基于属性划分策略按页存储实时数据流,并在页头存储本页数据流采样起始时间戳
无线传感器网络资源有限,在传感器节点处对数据进行压缩,可以减少数据流的传输量,节约通信带宽.目前已有的数据流压缩算法没有同时考虑数据流内部的多态性,而实际应用中,传感器网络采集的数据既有事件发生前的常态数据,又包含事件发生期间的非常态数据.针对多态数据流提出了一种线性预测综合压缩算法,对常态数据流和非常态数据流采用不同的压缩算法,并通过动态调整移动系数和预测模型以获得比较高的压缩性能.实验表明,在
数据库分区技术采用"分而治之"的策略来降低管理海量数据复杂性,提升系统性能,其中以区间分区最为常用。实时数据仓库通常要求迅速地对数据仓库数据进行分区以满足实时性要求.常规的区间分区算法的时间复杂度随着分区个数增加而线性增长,不适合海量数据实时分区的要求.为提高海量数据的分区速度,研究了现有数据库分区算法,提出了一种有效的针对海量数据的非等数据量的区间分区算法NEP,该算法通过允许各分区的数据量在小
转录调控是后基因组时代研究的热点之一,转录因子结合位点(或顺式调控元件)是一类非常重要的功能元素.构建转录因子结合位点数据库是转录调控中的重要工作,从日益增长的相关文献中挖掘转录因子结合位点是构建转录因子结合位点数据库的重要途径.在借鉴QA(question answering)问答系统的基础上,提出以"问题网"Qnet(question net)为核心概念的转录因子结合位点文本挖掘算法Qnet-
由于数据本身固有的不确定性、采集的随机性及不精确性导致现实应用中产生了大量的不确定数据集.基于概率Skyline的思想,提出了不确定数据集上的k-Skyline查询,用于查询Skyline概率最大的k个对象,并设计了一个高效算法:GIKS(grid indexed k-skyline).GIKS是一个自底向上的网格索引方法,将数据空间分割为多个易于处理的小区域,利用网格的优势分而治之;同时借助索引
针对Web页面中包含大量噪声信息的问题,提出了一种基于页面布局及XPath技术的自动清洗算法。算法首先对样本页面划分形成的内容块进行有效性判定,将相似内容块在页面集中的位置信息归纳为公共XPath,再基于公共XPath识别并消除更多相似页面中的噪声内容.实验结果证明了该清洗方法的有效性及准确性。
给定关键字集合,关系数据库上的关键字查询返回一个元组连接树集合.现有的关键字查询处理方法要求元组连接树的每个叶节点至少包含一个查询关键字.但是,这些方法都忽略了与查询关键字语义相关的元组。因此,提出一种基于语义的关键字查询处理算法。首先定义了查询关键字与元组连接树的语义相关性评价函数,然后在查询处理过程中利用该评价函数,以产生相关性最高的top-k结果.最后,实验结果表明该查询处理算法的准确性和高
个性化Web搜索能够根据用户兴趣偏好为不同用户返回更符合其信息需求的个性化查询结果,是解决查询歧义性问题、提高搜索精度和用户满意度的有效途径.但用户查询复杂多样,基于用户所有历史查询而建立的静态用户模型往往不准确,降低了个性化搜索的性能.针对这一问题,提出了一种基于动态用户模型的个性化算法。在建立该用户模型时,将与当前查询相似性较高的历史查询赋予较高的权重,去除不相关查询,提高用户模型的可靠性和准