社会媒体多模态、多层次资源推荐技术研究

社会媒体中多模态和多层次的信息资源和基于各种关系构建的用户社群为推荐系统提供了更广阔的分析和选择空间,同时也带来了更多的问题与挑战。分析了当前社会媒体中用户与资源的关系以及社会媒体资源推荐的特点,分别从社会媒体资源推荐策略和相关支撑技术两方面综述了相关工作,将其概括为"社会媒体中用户角色的变化构成了更加复杂的用户关系"、"社会媒体资源表示形式呈现多模态特点"以及"社会媒体资源推荐应该满足多层次的用户需求",并从多模态、多层次资源推荐方面提出进一步的研究方向。     

Asyn-SimRank：一种可异步执行的大规模 SimRank 算法

SimRank 算法利用网络结构来评估网络中任意2点的相似性,它被广泛应用于社交网络和链接预测等诸多领域中．近年来,随着大数据技术的发展,SimRank 算法处理的数据不断增大,人们利用MapReduce 等分布式计算模型设计实现分布式的大规模 SimRank 算法来适应大数据处理的需求．但是,由于 SimRank 算法包含开销较大的迭代过程,每次迭代之后都需要一个全局同步,且每次迭代的计算复杂度高、通信量大,SimRank 算法不能在分布式环境下高效地实现．1）提出 Asyn‐SimRank 算法,该算法采用迭代‐累积的方式完成迭代计算,异步执行 SimRank 的核心迭代过程,避免了大规模分布式计算中的大量同步开销,同时有效降低计算量并减少通信开销;2）提出关键点优先调度计算,提升了 Asyn‐SimRank 算法的全局收敛速度;3）证明了 Asyn‐SimRank 算法的正确性和收敛性以及关键点优先调度计算的有效性;4）支持异步迭代的分布式框架 Maiter 上实现了 Asyn‐SimRank 算法．实验结果显示,相比较于 Hadoop ,Spark 上实现的 SimRank 算法和 Delta‐SimRank 算法,Asyn‐SimRank 算法大大提升了算法的计算效率,加速了算法收敛．     

MapReduce连接查询的I/O代价研究

数据的指数级增长给数据管理和分析带来了严峻的挑战.连接查询是数据分析中一种常用运算,而MapReduce是一种用于大规模数据集并行处理的编程模型,研究基于MapReduce的连接查询代价评估和查询优化,有着学术意义和应用价值.MapReduce连接查询算法的性能主要取决于I/O代价(包括本地和网络I/O),而I/O代价与数据集以及连接运算的特征参数相关,通过对二元连接的I/O代价评估可以优化多元连接执行计划.基于此,首先提出了二元连接查询的I/O代价模型;随后,对现有二元连接算法进行形式化定义和简单扩展,归纳出6种基于MapReduce连接查询算法,并通过算法白盒分析定义它们的I/O代价函数;最后,提出一种多元连接最优执行计划的选择算法.通过实验表明I/O代价模型的正确性且能够准确地反映算法的性能优劣.     

一种能效优化的MapReduce资源比模型

随着云计算的快速发展,IT资源规模的不断扩大导致能耗问题日益凸显.为降低MapReduce编程模型带来的高能耗,文中研究Map/Reduce任务的资源消费特征及该特征与能效的关系,旨在寻找一种能够指导资源分配和任务调度的资源模型,进而实现能效优化.文中提出任务的能效与任务被分配的资源量无关,而与其被分配的各种资源的资源量比例相关,且存在一个“最佳资源比”使得能效达到最高.基于此,文中首先提出了普适的资源和能效模型,从模型层面证明最佳资源比和能效之间的关系,量化空闲资源量和空闲能耗;随后分析MapReduce编程模型,将普适资源比模型变换到MapReduce下.通过抽象的数据的“生产者-消费者”模式,求解Map/Reduce任务的最佳资源比;最后,通过实验从任务能效和空闲能耗两个角度证明了最佳资源比的存在,并根据实验结果,对MapReduce执行过程进行划分,给出了部分Map/Reduce任务的最佳资源比.最佳资源比的提出和求解将有利于基于该最佳资源比的任务调度和资源分配算法的研究,进而实现Map/Reduce任务能效的提高.     

实时数据仓库中支持QoS的更新和查询任务调度

实时数据仓库中,数据更新不再是定期批量执行,而是持续不间断地进行.因此更新与查询的执行调度成为了重要问题.提出一种支持服务质量(QoS)的更新和查询调度算法,定义了查询相关的QoS参数,包括期望的查询响应时间和可接受的实时数据延迟;根据查询任务的具体QoS要求,进行更新和查询的实时调度.实验证明该算法能够根据查询的具体QoS需求,合理地调整任务的执行顺序,为用户提供更快速的查询响应和更高的数据实时性.     

一种面向不确定对象的可见k近邻查询算法

真实世界中,常存在很多障碍物,影响空间对象到查询点的可见性及距离,可见k近邻查询查找距查询点最近的k个可见对象,是时空查询领域的一类重要算法.由于度量设备误差以及通信开销的限制等因素,空间对象位置不确定因素广泛存在.文中拟对不确定对象执行可见k近邻查询,提出了概率可见k近邻(PVkNN)查询,即查找前k个成为查询点最近邻居概率最大的节点.为了高效地执行这一查询,文中提出了k-界限剪枝方法,基于可见质心的紧缩过滤以及对不可见对象的剪枝策略,从空间角度过滤掉不符合条件的对象.为避免对候选集合中每个对象的概率都进行精确计算,从概率角度提出了根据概率上下限来对候选集合进行进一步的求精方法,采用近似采样技术来获取可见区域的比例,实现了对PVkNN的高效计算.采用真实和模拟数据集设计实验,充分验证了算法的效率和精度.     

采用形态学边界特征的医学图像检索

特征提取是基于内容的图像检索(CBIR)中的关键步骤,如何有效提取反映高层语义的图像特征对于医学图像的检索至关重要.提出一种基于边界形状特征的医学图像检索方法.该方法首先通过多尺度形态学方法检测图像边界点,然后对边界图像进行形状特征提取,构建边界的形状密度直方图,最后通过相似性匹配实现医学图像检索.实验结果证明了所提取的边界形状特征在医学图像检索中的有效性,通过对比实验给出了结果分析和进一步的研究思路.     

WSN SnSim:一种无线传感网络仿真平台的研究与实现

随着无线传感网络技术的研究逐渐深入,对于无线传感网络仿真平台的需求也受到越来越多的重视.为了更加方便有效地进行无线传感网络上的算法研究,设计实现了一种无线传感网络仿真平台SnSim (Sensor Network Simulator).针对目前无线传感网络的发展情况,结合无线传感网络的特点,采用目前流行的Eclipse RCP面向对象框架,设计了无线传感网络仿真平台的数学模型、体系结构、功能模块、平台语言.实现了无线传感网络仿真平台,并对其性能及有效性进行了科学评估.     

Query Intent Disambiguation of Keyword-Based Semantic Entity Search in Dataspaces

Keyword query has attracted much research attention due to its simplicity and wide applications. The inherent ambiguity of keyword query is prone to unsatisfied query results. Moreover some existing techniques on Web query, keyword query in relational databases and XML databases cannot be completely applied to keyword query in dataspaces. So we propose KeymanticES, a novel keyword-based semantic entity search mechanism in dataspaces which combines both keyword query and semantic query features. And we focus on query intent disambiguation problem and propose a novel three-step approach to resolve it. Extensive experimental results show the effectiveness and correctness of our proposed approach.     

A Framework for Supporting Tree-Like Indexes on the Chord Overlay

With the explosive growth of data, to support efficient data management including queries and updates, the database system is expected to provide tree-like indexes, such as R-tree, M-tree, B＋-tree, according to different types of data. In the distributed environment, the indexes have to be scattered across the compute nodes to improve reliability and scalability. Indexes can speed up queries, but they incur maintenance cost when updates occur. In the distributed environment, each compute node maintains a subset of an index tree, so keeping the communication cost small is more crucial, or else it occupies lots of network bandwidth and the scalability and availability of the database system are affected. Further, to achieve the reliability and scalability for queries, several replicas of the index are needed, but keeping the replicas consistent is not straightforward. In this paper, we propose a framework supporting tree-like indexes, based on Chord overlay, which is a popular P2P structure. The framework dynamically tunes the number of replicas of index to balance the query cost and the update cost. Several techniques are designed to improve the efficiency of updates without the cost of performance of the queries. We implement M-tree and R-tree in our framework, and extensive experiments on real- life and synthetic datasets verify the efficiency and scalability of our framework.