【摘 要】
：
研究了不确定图上的最短距离问题，提出了期望最短距离的概念，证明了该问题不存在多项式时间的算法。为了解决该问题，使用了随机采样技术获得不确定图的一些可能世界，在每个可能世界上计算有穷的最短距离，最后计算出平均值作为期望最短距离的估计值。为提高计算效率，使用了过滤条件来减少采样过程中采样的边数从而加快随机采样。在此基础上，提出了一种基于对称变量的、无偏的随机采样近似算法，并证明了与直接随机采样方法相比
【机 构】
：
School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001
论文部分内容阅读
研究了不确定图上的最短距离问题，提出了期望最短距离的概念，证明了该问题不存在多项式时间的算法。为了解决该问题，使用了随机采样技术获得不确定图的一些可能世界，在每个可能世界上计算有穷的最短距离，最后计算出平均值作为期望最短距离的估计值。为提高计算效率，使用了过滤条件来减少采样过程中采样的边数从而加快随机采样。在此基础上，提出了一种基于对称变量的、无偏的随机采样近似算法，并证明了与直接随机采样方法相比，该方法在不增加时间开销的同时能减小采样方差。通过真实数据上的实验表明，提出的算法在时间开销和采样方差上均明显好于直接随机采样方法。
其他文献
借助于群体移动规律挖掘技术，可以为商业及社会领域提供有效的决策支持，产生巨大的商业价值并具有非常重要的社会意义。但是由于移动通讯领域的发展和移动数据本身的特点，传统技术已经很难满足对海量数据的处理需求。本文设计了一种基于云计算平台的群体移动规律挖掘系统，借助于云计算平台的稳定高效且易于扩展等特性，根据实际应用需要构建可配置的移动轨迹，并通过个体惯常轨迹挖掘和协同聚类来实现群体移动规律挖掘。最后通过
如何处理缺失值一直是数据库领域中一个值得关注的问题，缺失值问题的研究对于提高运算效率和保证系统健壮性具有重要意义。云环境中海量数据的稀疏性使缺失值问题变的更加突出，现有的处理方法要么语义表达能力有限，要么未考虑到云环境对其的影响。针对这些问题，提出了一种面向海量稀疏数据存储的缺失值处理方法：首先结合现实的云环境应用，把缺失值归纳为未知值和不存在值两类；其次基于该语义定义了算术运算及比较运算；然后利
随着语义网技术的发展,RDF数据应用的领域越来越广泛,因此产生了海量的RDF数据,对存储和查询提出了更高的要求。在RDF数据上建立多索引结构能有效地提高查询效率,设计了一个包括一个词典表和3个不同顺序的数据表的RDF数据存储模式,通过对数据表的排序和建立次要索引实现了多索引功能,并设计了能够使SQL优化执行的SPARQL转化策略和算法,有效地提高了查询效率。
由多核CPU和GPU构成的异构计算平台已经成为当前高性能计算的重要发展方向，为充分发掘异构计算平台的潜力，有效提升列数据库查询的性能，首先提出了一套列数据库查询的原语集合，并根据多核CPU和GPU体系结构的特点，优化原语实现机制，充分开发了原语内的并行性.同时，将SQL查询语句编译为原语构成的依赖图，并提出了一套调度机制，使得多个原语可以在多核CPU、GPU以及磁盘等部件之间并行执行.通过对TPC
高效且准确地找出存在于深网中的与用户查询意图最相关的Top-N元组，是深网数据集成中的关键问题。针对数据源内容概括未见成果的现状，本文提出了一种能够有效概括非数字、非离散属性特征的非合作结构化深网数据源摘要构建方法。利用主题词抽样，依据主题语义选择与主题词相关的特征词，通过主题词及特征词构建数据源语义摘要。实验结果表明与传统的基于词频的方法相比较，该方法在召回率及准确度方面均有较大幅度的提升。
社区挖掘算法能够在复杂社会网络中发现社区,却无法精确区分社区边界点,也没有考虑挖掘结果可视化。力导引布局算法是社会网络信息可视化领域的主流布局算法,但是无法反映网络中社区的聚簇特性。因此,提出了社区挖掘分析布局(community detection analysis layout,CDAL)算法来解决这一问题。该算法通过引入度中心度和结构紧凑度对力导引算法进行改进,并采用分层布局的方式实现社会网
在传统的关系数据库上进行关键字查询已经成为近来数据库领域的研究热点。面向关系数据库的关键字查询允许用户在不知道数据库模式、不使用复杂的查询语句的情况下查找出相关信息。然而这种方法可能会产生大量的查询结果，且这些结果与用户的查询意图不是紧密相关的。针对已有问题，提出一种面向关系数据库的语义关键字查询策略。在进行语义分析时，不仅仅利用数据库的模式信息，同时也要利用用户给出的关键字之间的相互联系，既支持
为了提升用户体验度，社交网络都提供了用户推荐。新浪微博的用户推荐方式基于社交网络的结构，并没考虑微博内容信息。而微博作为一个用户创建与分享信息的社交网络应用，具有很强的互动性，用户的兴趣、用户间的关系紧密度等信息都体现在用户发布的消息中。本文综合了新浪微博的结构和内容信息，分别提取了两种结构因素(共同关注与共同好友)和内容因素(转发与@关系)，给出了一种综合定义用户间信任关系的度量方式，基于该信任
近些年，由于数据采集的不精确和数据本身的不确定性，使不确定性在位置数据中普通存在。在障碍空间中，聚类不确定数据面临新的挑战。提出了障碍空间中聚类不确定数据的OBS-UK-means算法，并提出了分别基于R树和Voronoi图的两种剪枝策略和最近距离区域的概念，大大减少了计算量。通过实验验证了OBS-UK-means算法的高效性和准确性，同时证明了剪枝策略在不损害聚类有效性的情况下，能够有效地提高聚
数据前端加密是保护云环境下外包数据隐私的一种有效手段，但却给数据查询等操作带来挑战.针对云环境下多数据拥有者数据外包及选择性访问授权特征，为支持大规模加密云数据上高效且隐私保护的用户个性化密文查询，文中提出了一种隐私保护的高效密文排序查询方法RQED.通过设计无证书认证的PKES(支持关键词检索的公钥加密)，并构建RQED框架来实现强隐私保护的密文查询.基于该框架，设计了更合理的多属性多关键词密文