Efficient evaluation of monitoring top-t most influential places

The continuous top-t most influential place (CTtMIP) query is defined formally and solved efficiently in this paper. A CTtMIP query continuously monitors the t places with the maximum influence from the set of places, where the influence of a place is defined as the number of its bichromatic reverse k nearest neighbors (BRkNNs). Two new metrics and their corresponding rules are introduced to shrink the search region and reduce the candidates of BRkNNs checked. Extensive experiments confirm that our proposed approach outperforms the state-of-the-art competitor significantly.     

云环境下基于MapReduce的海量服务选择研究

当处理分布式、大规模的服务选择时,传统服务选择方法存在着效率不高和全局Qo S性能低下的问题。基于Map Reduce框架,设计了一种云环境下的海量服务选择方法以解决此问题。首先,基于Map Reduce框架,利用Skyline算法,筛选海量候选服务,生成Skyline服务库;其次,基于迭代式Map Reduce框架,运用多目标模拟退火算法,从所生成的Skyline服务库中优选Skyline服务,产生一组Pareto最优的组合服务;最后,依据用户的个性化和多样性需求,执行Top-k查询,优选出满足用户偏好的k个组合服务。该方法适应于具有分布式环境、高维Qo S的海量服务选择,能快速返回组合服务,且其全局Qo S较优。     

基于位置的可拼接轨迹对搜索

移动设备的快速发展,生成了大量轨迹.基于位置的轨迹搜索,是指给定一组查询点,从数据集中检索top-k条轨迹,但是所得到的轨迹可能不能近距离通过所有查询点.利用轨迹可拼接的想法,提出基于位置的可拼接轨迹对搜索,使用户利用轨迹对得到的轨迹更加近距离地通过所有查询点.在搜索终止过程,给出可拼接的轨迹对搜索过程的有效终止条件.真实的数据集验证了所提方法的有效性.      

基于相对量词的RDF模糊查询方法

针对RDF含相对量词模糊查询问题,提出支持分组机制的相对量词RDF模糊查询方法.利用语言层次结构理论,构造语言层次结构表,通过在FILTER子句中增加模糊条件并调用GROUPBY和HAVING子句实现特定属性上的分组操作,实现对SPARQL语法的扩展.分析了两种典型情况下的RDF相对量词模糊查询问题,给出将扩展的模糊SPARQL查询转换为标准SPARQL查询的处理方法,从而可利用现有的SPARQL查询引擎完成RDF基于相对量词的模糊查询处理.实验系统及相应的实验结果验证了所提方法的可用性.     

定性地理信息检索方法及其实现

针对当前定量化的地理信息检索模型无法有效处理自然语义导致检索结果不理想的问题, 以语义匹配为原则, 以定性表达为基础, 以推理方法为手段, 提出基于定性空间推理的定性地理信息检索的方法及其形式化模型, 实现Web文档信息内容与查询请求的定性表达和信息提取, 支持基于语义的检索匹配和结果排序, 并进行原型系统的实验验证。这种定性检索方法符合人类常识性认知和表述习惯的方式, 基于定性知识表达和推理决策技术的地理信息检索问题解决方法可以提高现代地理信息检索技术的有效性。     

基于改进ADPP的多变量时间序列异常检测

针对多变量时间序列异常检测问题进行研究,提出基于改进ADPP的多变量时间序列异常检测算法IADPP.IADPP算法引入适用于多变量时间序列的张量相似性度量SSOTPCA,并以此相似性度量构造序列集的k-近邻图,在构造的k-近邻图上计算多变量时间序列的异常系数.研究结果表明,IADPP算法克服了原有ADPP算法不支持多变量时间序列和要求密度均匀的缺陷,取得了较好的检测结果.     

一种基于对象快照模型的时空查询原子模型

基于对象快照模型, 在分析时空对象最基本时空特征的基础上, 定义时间范围、空间范围、时空范围、时间关系、空间关系和属性状态6 个基本查询元素。在此基础上, 以时间为主轴, 定义原子查询类型, 并提出基于原子类型构造新类型的方法。对基本元素和原子查询的定义不涉及应用级语义, 使其具有良好的系统性和适应性; 同时具有明确的GIS 表达, 使其具备可实现性。研究成果可以作为时态GIS 中时空查询接口实现的基础和依据。     

一种基于语义的super-peer网络构建方法

针对分类层次语义空间,提出了一种基于语义的super-peer网络构建方法.该方法根据peer上数据的语义信息,动态地将peer聚簇成不同的语义簇,语义簇之间建立适当的语义路由关系.每个语义簇由一个super-peer节点和一组peer节点组成,仅负责回答其语义子空间上的查询.查询首先根据其语义被路由到适合的语义簇中,然后被转发给包含结果的peer.实验结果表明,该方法在查找性能和开销之间取得了一个良好的平衡,具有较高的查找性能和较低的查找代价,提高了网络的可扩展性.     

一种地理信息检索的定性模型

提出一种定性地理信息检索方法, 用于地理信息的定性表达、语义匹配、推理和结果排序, 可以避免目前定量地理信息检索中语义信息丢失问题。采用命题逻辑方法综合表达查询和文档中的主题信息和地理语义信息, 将文档与查询的相关性度量分为主题相似度和地理相似度。前者通过命题关键词间加权本体距离获得。后者可进一步分为概念相似度和位置相似度, 分别基于地理本体和空间语义度量。由于信息的表达形式为命题和信息单元, 采用证据理论和模糊逻辑对上述子相关性度量进行统一建模。所提方法可以基于语义检索网页中的定性地理信息, 并对相关文档进行排序。这种检索和排序方法符合人类空间认知, 因此可以有效提高地理信息检索的效率。     

An Improved Algorithm for k-Nearest-Neighbor Finding and Surface Normals Estimation

This paper is to improve the speed of k-nearest-neighbor search and put forward algorithms related to tangent plane estimation based on existing methods. Starting from the points cloud, the algorithm segments the whole data into many different small cubes in space, and the size of cube is related to the density of the points cloud. Considering the position of the point in the cube, the algorithm enlarges the area around the given point step by step until the k-nearest-neighbor is accomplished. The neighbor's least-squares tangent plane is estimated. In order to orient the planes, the k-nearest-neighbor is introduced into the problem of seeking the minimum spanning trees instead of searching the whole data. The research proved that the algorithms put forward in this paper were effective in processing data in short time and with high precision. The theory was useful for the practical application in reverse engineering and other areas related. Solution for finding k-nearest-neighbor problem, which still costs much time in present, was provided, and a propagation algorithm for orienting the planes was also discussed. The algorithm chose the orientation among the k-nearest-neighbor of the current point.     

一种基于知识的关系数据库模糊查询方法

在数据库查询中,针对传统DBMS不支持模糊查询的弱点,提出了基于知识的数据库模糊查询转换方法.以模糊集理论为基础,介绍了数据库模糊查询条件的构成形式,并提出利用隶属函数、领域知识和模糊集的α-截集运算相结合的方法实现模糊查询转换,模糊查询条件的转换和扩展考虑了查询条件的重要程度和用户偏好.该方法无需改变传统SQL语言或数据库引擎就能够实现模糊查询,提高了用户与系统之间的交互能力.     

一种新的DL-Lite不一致容忍语义

在本体工程中,处于演变过程中的本体常出现不一致性问题,这将导致基于本体的推理失效.为解决推理失效的问题,提出了一种新的处理DL-Lite本体实例断言中冲突的不一致容忍语义,讨论了新的不一致容忍语义与已有的不一致容忍语义的关系,给出了在新定义的不一致容忍语义下的修复算法并做了新语义下推理任务的复杂度分析.     

Multi-pattern matching algorithm with wildcards based on bit-parallelism

Multi-pattern matching with wildcards is a problem of finding the occurrence of all patterns in a pattern set{p~1,---,p~k}in a given text t. If the percentage of wildcards in pattern set is not high,this problem can be solved using finite automata. We introduce a multi-pattern matching algorithm with a fixed number of wildcards to overcome the high percentage of the occurrence of wildcards in patterns. In our proposed method,patterns are matched as bit patterns using a sliding window approach. The window is a bit window that slides along the given text,matching against stored bit patterns. Matching process is executed using bit wise operations. The experimental results demonstrate that the percentage of wildcard occurrence does not affect the proposed algorithm's performance and the proposed algorithm is more efficient than the algorithms based on the fast Fourier transform. The proposed algorithm is simple to implement and runs efficiently in O(n+d(n/σ)(m/w))time,where n is text length,d is symbol distribution over k patterns,m is pattern length,and σ is alphabet size.     

NetConf查询操作的形式化模型

使用形式语义学方法详细说明了查询操作需求分析,建立了查询过程演算概念,并以NetConf协议的查询操作(get)为例验证了提出的方法.     

数据流滑动窗口上的一种多聚集查询共享策略

基于如何提高多个聚集查询的查询效率,提出了一种共享链树结构的多查询聚集计算共享策略.利用每个滑动窗口逻辑地将链树划分成若干子树,它们各自根节点中的聚集值恰好就是每个查询对应的结果值.数据流上多个查询可以在同一棵链树上并发执行,避免了每个查询的重复建树.同时,利用链树本身可降低无用的重复比较的性质,使得多个查询在同一棵链树上只需进行少量更新比较就可求得每个查询的新聚集值.实验证明,多个查询共用同一链树结构,可以最大程度地共享资源,减小内存使用量,因此大大提高了数据流上的查询处理效率,加大了数据流上的任务吞吐量,改善了系统性能.     

Neighborhood topological effect on grain topology-size relationship in three-dimensional polycrystalline microstructures

A new grain topology-size relationship in three-dimensional(3D)polycrystalline microstructures has recently been established by considering the effects of non-random first nearest neighbor grains.In this contribution,a generalized form for this relationship is presented by considering the interactions of kth(k=1,2,3…)nearest neighbor grains,and large scale Monte Carlo-Potts model simulation is used to investigate the general neighborhood topological effect on the topology-size relationship.The results show that,unlike their first nearest neighbors(k=1),the topological correlations of 3D grains with their kth layers(k 2)of nearest-neighbors may have trivial effect on the topology-size relationship.     

MapReduce框架下的查询结果共享

当前的大规模数据分析通常在MapReduce框架下执行查询。由于MapReduce框架本身的冗余性以及查询之间的重叠性,复用已有查询的结果可以大幅提高查询的执行效率。复用查询的结果需要对其进行存储和匹配管理,产生高昂的系统开销,抵消复用的部分效果。本文针对目前先进的查询结果复用系统ReStore在管理查询结果和匹配中存在的效率低下的问题,提出森林结构的Job存储管理技术和与之相适应的匹配算法,提高查询的匹配效率,减少系统的开销。为了使系统能够充分复用已执行查询的结果,本文提出对多个查询进行预处理的方案,通过改变各查询进入Pig编译器进行编译的顺序,从而改变Job的执行顺序,使得加载相同数据集的Job同时执行,减少与存储库进行匹配的次数。实验表明：在构建存储结构与匹配已有结果过程中,本文提出的方法与ReStore相比,节约16.3%的时间开销,伸缩性也更好。     

基于本体的关系型数据库集成与应用

本体越来越多地被用于异构信息的集成。本体整合大体上有三个不同的方向:单本体方法、多本体方法和混合本体方法。提出一个基于混合本体的信息集成框架,此框架能够支持两种查询:基于全局本体的查询和基于局部数据源的查询,且详细地论述了两种类型查询的实现原理和过程。此外,将此框架应用于分布式的数字博物馆中,证明了方法的有效性。     

New classes of interconnection topology structures and their properties

In the first part of this paper, three generalizations of arrangement graphA _n,k of [1], namelyB _{n, k},C _{n, k} andD _{n, k}, are introduced. We prove that all the three classes of graphs are vertex symmetric, two of them are edge symmetric. They have great faulty tolerance and high connectivity. We give the diameters ofB _{n, k}andC _n,k, the Hamiltonian cycle ofC _{n, k} and Hamiltonian path ofB _n,k. We list several open problems, one of them related to the complexity of sorting algorithm on the arrangement graphs. All these graphs can be thought as generalizations of star graph but are more flexible so that they can be considered as new interconnection network topologies. In the second part of this paper, we provide other four classes of combinatorial graphes,Ch _n, Cy_n, Zh_n, andZy _n. Many good properties of them, such as high node-connectivity, node symmetry, edge symmetry, diameter, ets., are shown in this paper.     

Slice Data Based Support Generation Algorithm for Fused Deposition Modeling

This paper presents a robust algorithm to generate support for fused deposition modeling (FDM). Since many flaws appear in most stereo lithography (STL) models, this algorithm utilizes slice data as input. A top-down approach was used to calculate the support slice layer by layer. The generation algorithm was described in detail including the slice grouping, oriental bounding box (OBB) calculation, offsetting, and Boolean operations. Several cases are given to validate the efficiency and robustness of the procedure. The algorithm provides necessary support not only for hanging surface but also for hanging vertexes and edges with O(n) time complexity, where n is the number of layers. The algorithm fully utilizes the parts' self-support ability and reduces support volume to the maximum extent. This slice data based algorithm has the same efficiency as the STL based algorithm but is more stable, which significantly enhances the robustness of the support generation process.