基于随机游走的大规模图中节点对采样算法

社会网络中的节点对采样可用于大规模社会网络的好友预测和用户兴趣识别.当整个网络的拓扑结构不完全或者随机选择用户的代价很高时,传统的均匀顶点采样方法的性能迅速下降.为此,提出了一种基于随机游走的大规模图中节点对采样算法.首先对社会网络的节点对采样进行了系统分析,对不同跳数下的节点对进行了定义;然后将社会网络转换成等价的网络图.新图中的顶点是原图中的边,新图中边的两个顶点是原图中含有相同顶点的两条边.最后,在新图上应用随机游走模型对节点对进行采样.实验结果表明,提出的方法统计误差小、执行效率高,性能明显优于均匀节点采样的相关算法.     

室内概率阈值反向最近邻查询

室内空间变得越发的庞大和复杂,随之产生了越来越多的室内空间查询需求.目前已有文献提出了针对室内空间环境的范围查询和最近邻查询,而作为常见的空间查询类型的反向最近邻查询,尚未有相关的研究.为此,提出了室内概率阈值反向最近邻查询和基于定位设备的设备可达图模型.在图模型基础上,提出了室内概率阈值反向最近邻查询处理算法,该算法由基于图模型的批量剪枝、基于室内距离的剪枝、基于概率的剪枝和概率计算4部分构成,通过剪枝策略修剪掉不可能出现在结果集中的对象,从而缩小了查询空间,提高了效率.     

卫星图像的村落民居Lebesgue测度η值研究

以古民居的分布与发展演变为变量参数所形成的古村落拓扑图,通过对Lebesgue测度计算形成几何拟合数值曲线,在引入优美图优美标号的基础上,形成对村落优美度η的勒贝格测度值,在古村落发育（时间增长）过程中,η值是单调变化的。以徽州地区存在1000年古村落google卫星图像为基础,结合历史文献获得不同年代民居拓扑图,依据上述方法对村落拓扑中优美图进行统计量化,定义出村落优美度值η。结论认为η介于8000左右时,村落民居年代人文分布丰富;而低于6000时村落民居数量发展上升,但人文资料零乱;在700年左右的村落中,η值稳定在9600附近,呈现出古村落的明显拓扑特征。通过村落优美度按年代变化的η值曲线,对村落的（年代）演变做了分析。     

地铁环境下时变公交网络的最优路算法

通过建立图论模型实现了地铁环境下时变公交网络的出行优化问题.首先,建立了公交地铁网络图及基于此网络图的二分图、映射网络图,并对地铁线路上站点间的权值进行合理倍数的缩小以达到优选地铁的目的.同时,考虑到地铁与公交的时变性,即是否在它们的运营时间段内直接关系到查询到的最优路径.然后给出以换乘次数少为目标的最优路径选择算法.最后用实例来验证了该算法的有效性.     

针对有向图的局部扩展的重叠社区发现算法

当前社区发现算法主要是针对无向图研究社区结构,但在实际复杂网络中,链接关系时常表现出非对称性或方向性,比如Twitter的用户关注关系,文献网络的引 用关系,网页之间的超链接关系等应用网络。因此,本文依据信息在复杂网络中的传播规律和流动方向性,提出了k-Path共社区邻近相似性概念及计算方法,用于衡量结点在同一社区的相似性程度,并给出了把有向图转换为带方向权值的无向图的方法。基于带权无向图提出了一种从局部扩展来探测社区的重叠社区发现算法(Local and wave-like extension algorithm of detecting overlapping community, LWS-OCD)。在真实数据集上的实验表明,共社区邻近相似性概念实现了有向到无向的合理转换,而且提高了社区结点的聚集效果,LWS-OCD算法能够有效地发现带权无向图中的重叠社区。     

GPU-OSDDA: a bit-vector GPU-based deadlock detection algorithm for single-unit resource systems

This article presents a GPU-based single-unit deadlock detection methodology and its algorithm, GPU-OSDDA. Our GPU-based design utilizes parallel hardware of GPU to perform computations and thus is able to overcome the major limitation of prior hardware-based approaches by having the capability of handling thousands of processes and resources, whilst achieving real-world run-times. By utilizing a bit-vector technique for storing algorithm matrices and designing novel, efficient algorithmic methods, we not only reduce memory usage dramatically but also achieve two orders of magnitude speedup over CPU equivalents. Additionally, GPU-OSDDA acts as an interactive service to the CPU, because all of the aforementioned computations and matrix management techniques take place on the GPU, requiring minimal interaction with the CPU. GPU-OSDDA is implemented on three GPU cards: Tesla C2050, Tesla K20c, and Titan X. Our design shows overall speedups of 6-595X over CPU equivalents.     

Error quantification of the normalised right graph symbol for an errors-in-variables system

This paper proposes a novel method to quantify the error of a nominal normalized right graph symbol (NRGS) for an errors-in-variables (EIV) system corrupted with bounded noise. Following an identification framework for estimation of a perturbation model set, a worst-case v-gap error bound for the estimated nominal NRGS can be first determined from \textit{a priori} and \textit{a posteriori} information on the underlying EIV system. Then, an NRGS perturbation model set can be derived from a close relation between the v-gap metric of two models and ${\rm H}_\infty$-norm of their NRGSs' difference. The obtained NRGS perturbation model set paves the way for robust controller design using an ${\rm H}_\infty$ loop-shaping method because it is a standard form of the well-known NCF (normalized coprime factor) perturbation model set. Finally, a numerical simulation is used to demonstrate the effectiveness of the proposed identification method.     

藏文文字特征提取方法的研究

特征提取是文字识别中很重要的环节。藏文字识别中特征提取的方法有很多,但由于藏文字的字型有很多种特点,可以探索出适合藏文识别的最优特征提取方法。该文简述了藏文字型的特征及印刷体藏文字识别原理,主要讨论了符合藏文字的一种特征提取方法--网络点阵图形投影法。     

QMDS: a file system metadata management service supporting a graph data model-based query language

File system metadata management has become a bottleneck for many data-intensive applications that rely on high-performance file systems. Part of the bottleneck is due to the limitations of an almost 50-year-old interface standard with metadata abstractions that were designed at a time when high-end file systems managed less than 100 MB. Today's high-performance file systems store 7–9 orders of magnitude more data, resulting in a number of data items for which these metadata abstractions are inadequate, such as directory hierarchies unable to handle complex relationships among data. Users of file systems have attempted to work around these inadequacies by moving application-specific metadata management to relational databases to make metadata searchable. Splitting file system metadata management into two separate systems introduces inefficiencies and systems management problems. To address this problem, we propose QMDS: a file system metadata management service that integrates all file system metadata and uses a graph data model with attributes on nodes and edges. Our service uses a query language interface for file identification and attribute retrieval. We present our metadata management service design and architecture and study its performance using a text analysis benchmark application. Results from our QMDS prototype show the effectiveness of this approach. Compared to the use of a file system and relational database, the QMDS prototype shows superior performance for both ingest and query workloads.