一种基于悬挂顶点关联索引的最短路径查询算法

最短路径查询是图数据查询中的热点问题。针对现有的"索引+查询"方法存在的查询效率低下且扩展性差等问题,本文提出了悬挂顶点关联索引策略,即先对度为1的顶点构建顶点关联索引,再对其他顶点构建2-hop标签索引,并依此提出了相应的最短路径查询算法。本文提出的索引策略降低了索引规模,减少了构建索引时间,使得最短路径查询算法的效率和扩展性得到了改善。最后,通过对11个真实的数据集进行实验,从索引构建时间、索引规模大小、查询时间等方面验证了本文方法的高效性。     

基于素数序列标记法的XML查询处理算法

XML索引为查询处理提供了高效的帮助,其中F＆B索引是已知的处理分枝查询的最小的索引,但快速创建F＆B索引和利用F＆B索引完成查询处理的算法却很少有人研究．本文提出了一种素数序列标记法,这种标记法不仅有助于快速的建立F＆B索引,更可以高效的完成F＆B索引上的查询处理．此外,我们还给出了基于素数序列标记法的查询处理算法,即素数整除匹配算法,该算法可以高效的判定某节点是否有某分枝子结构．实验表明基于素数序列标记法的F＆B索引创建方法比SAM算法快,在多个数据集F＆B索引上素数整除匹配算法优于关联路径连接算法和TwigStack算法．     

面向用户偏好的动态网页数据交互式查询算法

为提高网页数据查询速度、精度及工作效率,提出一种面向用户偏好的动态网页数据交互式查询算法.首先,构建用户偏好模型,增加偏好组合的演化个体适应性,综合计算适配值;其次,为防止数据冗余和重复,基于兴趣相似性,分离相似度高的查询数据和重复数据,识别出网络数据的性质;最后,利用粒子群优化算法寻找最优的动态网页数据交互式查询方案.实验结果表明：在数据集基数影响下,该算法的查询结果集质量在0.95以上;在查询最大维数影响下,该算法的查询结果集质量在0.96以上,表明其查询使用时间短、结果集精度高、自适应能力强.     

一种分布式数据库查询优化算法

在分析分布式数据库查询目标和策略的基础上,提出了一种新的查询优化算法：基于二级索引的查询算法。该算法利用全局和局部二级索引对查询语句进行分析,进而确定最优查询路径。该算法可以有效地减少分布式数据库系统查询过程对带宽的消耗。     

基于标记的图数据关键词查询方法研究

图数据关键词查询技术在结构化数据、半结构化数据和非结构化数据等领域具有良好的应用前景。随着需要解决问题规模的不断扩大,寻找top-k结果所花费时间将会增多。针对该问题,提出了一种基于标记查询优化的方法。该方法首先引入路径索引,通过输入一组关键词遍历路径索引,找到与关键词相关的结构子图;然后基于结构子图,找出当前最优结果,对当前最优结果,选择需要处理的路径进行标记;并设置该路径为无穷大,实现对当前最优结果的屏蔽,再在此基础上查找次优结果,直到top-k结果查询完毕;最后,基于测试数据集,验证该方法的有效性。     

基于聚类的逆向Skyline查询算法

逆向Skyline查询能够应用到诸如决策支持、用户偏好支持以及市场行为分析等方面。由于参考对象q的存在,在执行逆向Skyline查询的过程中数据空间被划分成许多分区。然而,存在的算法都没有考虑这个问题的影响,直接使用原始数据集建立索引结构。本文提出了一种新的逆向Skyline查询方法CRSQ,它考虑了这个问题。CRSQ首先根据查询对象q对数据进行聚类,然后建立R-tree索引,最后利用高效修剪策略修剪索引搜索空间。实验结果表明CRSQ算法是有效的,它相对于没有聚类技术的算法获得了50%以上的性能提高。     

无索引空间数据库的基于最优点的集合最近邻查找算法

针对度量空间中的无索引空间数据库,提出一种基于最优点的集合最近邻查找算法及其改进算法.采用真实数据集与人工生成的数据集对算法进行测试,评估所提出算法的效率.实验结果表明,所提算法的效率优于组最近邻居查询算法,并且对于高维数据空间,所提出的算法有较高的稳定性.由于查询区域中数据点的数量比较少,改进的基于最优点的集合最近邻...     

基于地理信息的最少倒乘次数公交线路搜索算法

本文通过分析以往算法的在公交线路最少倒换次数路径查询方面的盲目性，提出了一种基于地理信息的最少倒乘次数公交线路搜索算法，该算法将以站点为线索的搜索算法改进为以线路为线索的搜索方法。基于出发和到达站点，建立了出发线路集和到达线路集，并结合地理方位信息定义了一个线路趋势函数，进一步地通过该函数来缩减上述两个集合的规模，进而改变了算法的运行效率。     

车辆导航中一种改进的路径优化算法

针对车辆定位与导航系统中的最优路径规划中存在的问题,研究了最短路径搜索算法的快速实现技术,提出了一种启发式快速最优路径规划算法.在分析经典迪杰斯特拉最短路径搜索算法和A*启发式搜索算法的基础上,利用双向A*算法和地图分层搜索技术减小搜索空间,采用二叉堆结构来实现路径计算过程中优先级队列的一系列操作,从而提高了算法的执行效率.仿真试验的结果证明了该算法的优异性能.     

求解带时间窗车辆路径问题的混合智能算法

基于布谷鸟搜索算法和单亲遗传算法,设计了一种求解带时间窗车辆路径问题的混合智能算法.该算法首先对客户位置进行聚类分析,然后再进行各区域的路径优化.混合智能算法不仅改进了布谷鸟搜索算法中当鸟卵被鸟窝主人发现后需要随机改变整个鸟窝位置的操作,同时引入的单亲遗传算法加快了最优配送路线的搜索速度.分析和比较了混合智能算法与布谷鸟搜索算法的计算复杂度.最后采用国际通用标准测试集Benchmark Problems进行测试.结果显示,混合智能算法是求解带时间窗车辆路径问题的一种有效算法.     

基于关键词的RDF数据查询方法

在建立关键词倒排索引和路径索引的基础上,提出一个利用量化均衡规则和等距规则的启发式查询算法,并按照查询结果的大小排序返回最相关的前k个结果.通过建模RDF数据为RDF句子图,将文本信息封装到句子节点,同时将查询结果建模为包括所有查询关键词并且叶节点是关键词节点的无根树,将关键词查询问题转化为斯坦纳树问题.假设RDF句子图包括n个节点,最坏情况下索引占用的空间是3n2.假设关键词节点数为k,查询算法的时间复杂度为O(kn).该方法不需要依赖RDF数据的模式信息,支持对数据中的属性和关系名进行关键词查询.实验证明该方法能够快速而有效地实现RDF数据的关键词查询.     

地理社交网中基于范围的星型组查询

针对星型组查询只考虑了用户的位置信息和朋友关系,而没有考虑用户的偏好信息,使得推荐质量不高的问题,本文提出一种基于范围的星型组查询算法(m SG),同时考虑用户的社交关系、文本信息和当前位置信息,在给定范围为用户返回k个得分最高的星型组。为了迅速查找中心点用户,提出带倒排表的网格索引结构。为中心点用户更快速地查找朋友,提出了社交关系和文本信息混合索引结构。最后,通过实验表明,利用所提索引结构减少了查询算法的运行时间。     

具有结果多样性的近似子图查询算法

针对大型图中的各种top-k近似子图查询算法存在的顶点重叠度高、无法满足多样性匹配结果输出等问题,提出具有最大顶点覆盖集的多样性近似子图查询算法.该算法建立基于近邻关系和基于区域划分的双重索引,并为相互关系紧密的同标号顶点建立簇索引.在图查询过程中,利用近邻特征为查询图中的每个顶点快速筛选出满足局部匹配要求的候选顶点集,并从不同区域找到多个满足要求的近似匹配子图,避免了查询结果间的高重复率.同时,基于区域和同标号近邻簇的划分,优先查找属于不同划分或不同簇顶点的匹配,减少了不同区域划分间的交互,提高了查询的效率.在大量数据集上的实验结果验证了该算法在查询效率和结果多样性等方面的有效性.     

面向组近邻的Top-k空间偏好查询

空间偏好查询是当前空间查询研究中的一类热点问题,而现有的空间偏好查询不能有效支持面向组用户的位置服务应用.为此,提出一类新型空间偏好查询——面向组近邻的Top-k空间偏好查询(Topk spatial preference query for group nearest neighbor).该查询通过查找特征对象的λ子集组近邻最终为用户返回评分值最高的前k个λ子集.为了高效执行这一查询,给出了两种查询算法:TSPQ-G及TSPQ-G*.其中TSPQ-G*在TSPQ-G的基础上,通过空间剪枝及高效的特征对象索引树遍历策略大幅减少I/O代价,进而有效提高了该查询的执行效率.实验采用多个数据集验证了所提算法在不同参数设置下的有效性.     

基于数据广播的空间关键字查询处理

为了解决无线广播环境下空间关键字查询的问题,研究广播环境下空间关键字k近邻查询处理(BkSKQ),设计了一种结合kd树、倒排位图和(1,m)索引机制的空间关键字索引(ISKW)结构,以有效地组织对象的关键字信息、位置信息以及索引信息.该索引结构为客户的查询处理提供有效的指导,使得他们尽可能只下载查询处理所必须的数据信息.在ISKW索引结构的基础上,提出了BkSKQ查询处理算法.最后,通过模拟实验验证了提出的索引结构和算法的性能,实验结果表明所提出方法在访问时间和调谐时间上明显优于基于IR树的方法(BIRM).     

基于出行偏好和路径长度的路径规划方法

针对基于最短路径的路径规划方法只关注路径长度, 而基于轨迹的路径规划方法过度依赖用户偏好的问题, 提出一种同时考虑用户出行偏好和路径长度的路径规划方法. 首先, 利用长短期记忆模型从历史出行轨迹中提取用户的出行偏好; 其次, 采用Markov链Monte Carlo采样技术将用户的出行偏好引入启发式搜索算法A*中, 在道路网络中搜索得到符合用户出行偏好且较短的路径; 最后, 以北京市路网和出租车轨迹数据作为测试数据, 将该方法与基于最短路径的规划方法和基于轨迹的路径规划方法进行实验对比. 实验结果表明, 该路径规划方法更稳定, 并且其规划的路径具有较高的准确度、 较短的行驶距离和行程时间.     

空间网络数据库关键字查询的高效空中索引

研究无线广播环境下空间网络数据库关键字查询问题,提出一种包含路网加权四叉树、各关键字四叉树和路网距离矩阵的空中索引结构(KSSN).讨论了kNN查询处理问题,提出了高效的查询处理算法.所提出的算法能综合利用路网距离信息和关键字信息高效地消减不存在查询结果对象的路网空间,提高查询处理的效率.KSSN索引结构可推广至其他类型的查询,比如范围查询、Rank查询.在一个真实路网上进行了仿真实验,验证了基于KSSN索引结构的查询处理算法的性能.实验结果表明:所提出算法的访问时间和调谐时间分别为参照的IRRDA算法的25.13%和12.31%.     

在线数据流的连续限制查询算法

提出并实现一个基于持续限制查询的在线系统,使其能在网络日志数据流中,当满足一定条件的事件时自动发出警告;而条件是根据用户需要而设定的,用来侦测可能严重破坏网站正常运作的行为.分析并评测时间索引算法、无时间索引算法、紧过期时间算法、紧过期时间无索引算法、多查询并行算法5种算法的性能,结果表明,单个查询时,无时间索引算法是最好的选择;而在多个查询时,多查询并行算法是最佳的算法.     

多约束最优路径算法比较研究

针对多弧权网络路径寻优及其效率问题,提出了4种多约束最优路径算法,并对其进行了比较研究.基于经典Dijkstra算法,提出了多约束最优路径问题的D_MCOP算法;引入启发式搜索思想,设计了A*_MCOP算法和迭代加深搜索的IDA*_MCOP算法;为克服IDA* _MCOP算法每次迭代都要回到起始节点重新搜索的缺陷,提出了一种多约束边沿搜索算法——Fringe_MCOP算法.实例研究表明:三种启发式搜索算法扩展的节点数、边数以及算法的执行时间都远小于D_MCOP算法,而且Fringe_MCOP算法在三种启发式算法中性能最优;当给定的约束条件与最优路径的权值向量越接近时,算法的执行效率越高,当网络规模较大时,这一趋势更加明显;当约束条件过于严格而得不到满足约束条件的路径时,A*_MCOP和Fringe_MCOP的算法速度比IDA*_MCOP的算法速度更快,D_MCOP的算法速度最慢.     

基于树模型的XML查询匹配算法的设计与应用

在分析基于区间编码的结构连接算法Stack-Tree算法的基础上,研究基于树型模型的XML结构编码、XML查询处理过程中路径匹配等关键技术问题,并利用dom4j解析技术,基于Berkeley DB实现基于Stack-Tree算法的XML查询原型系统.实验结果表明本文设计的基于Stack-Tree算法的查询系统在查询时间,查询准确性以及全面性上能够满足对查询系统的功能和性能要求.