GRAIL: a scalable index for reachability queries in very large graphs

Given a large directed graph, rapidly answering reachability queries between source and target nodes is an important problem. Existing methods for reachability tradeoff indexing time and space versus query time performance. However, the biggest limitation of existing methods is that they do not scale to very large real-world graphs. We present a simple yet scalable reachability index, called GRAIL, that is based on the idea of randomized interval labeling and that can effectively handle very large graphs. Based on an extensive set of experiments, we show that while more sophisticated methods work better on small graphs, GRAIL is the only index that can scale to millions of nodes and edges. GRAIL has linear indexing time and space, and the query time ranges from constant time to being linear in the graph order and size. Our reference C++ implementations are open source and available for download at http://www.code.google.com/p/grail/.     

P2P网络信任管理研究综述

建立信任管理机制对于确保P2P网络中用户的利益,确定资源或者服务的有效性具有重要意义.阐明了P2P网络信任管理中的基本概念,剖析了P2P网络信任管理系统的基本组成及各个部分中的关键问题,在此基础上介绍了P2P环境下的典型信任管理系统,讨论了和其他学科的融合发展.最后,对进一步研究方向如统一描述框架和分析评价标准作了展望.     

P2P网络中双向信任机制的研究

P2P网络(Peer toPeer,对等网)已经以飞快的速度发展成为internet中最重要的应用系统之一。P2P网络开放、匿名的特性使得任何人在任何时候都也可加入网络为其他人提供内容和服务,同时也可以从网络中查找并获得所需要的资源。然而,也正是因为这种特点,节点之间缺乏信任、恶意节点随意终止服务,造成了网络的利用率低下,信任管理就显得十分必要。然而传统的单向信任管理机制难以有效地对自私节点和恶意节点进行控制。鉴于此,本文在研究P2P网络的信任管理机制的基础上,引入了双向信任机制,实现节点之间的双向评估。     

Cadabra: a field-theory motivated symbolic computer algebra system

Field theory is an area in physics with a deceptively compact notation. Although general purpose computer algebra systems, built around generic list-based data structures, can be used to represent and manipulate field-theory expressions, this often leads to cumbersome input formats, unexpected side-effects, or the need for a lot of special-purpose code. This makes a direct translation of problems from paper to computer and back needlessly time-consuming and error-prone. A prototype computer algebra system is presented which features -like input, graph data structures, lists with Young-tableaux symmetries and a multiple-inheritance property system. The usefulness of this approach is illustrated with a number of explicit field-theory problems.     

一种对等网中基于相互信任的两层信任模型

在P2P 系统中,声誉模型是建立节点间信任关系的重要方法之一,但现有的P2P 声誉模型几乎都是纯分散式的,具有信任收敛慢、信任管理复杂和网络开销大等缺点.在TLT(two-level trust)中,节点自发组织为信任簇,信任评价以簇为单位.每个簇由簇首和成员节点组成,簇首和成员节点之间是一种相互信任的关系:簇首为了提高自身的簇间服务信任,利用簇内服务信任观察成员节点的服务性能,过滤恶意的成员节点;成员节点为了提高服务声誉和接受更好的服务,利用代理信任考察簇首的管理能力.分析和仿真结果表明:在TLT 中,节点的信任值收敛快,恶意行为能够被快速识别;TLT 可扩展性好,如信任管理简单和网络开销小.     

P2P网络环境中节点信息交换的信任机制研究

P2P网络的匿名性和动态性带来了许多安全问题,传统的信任管理模型并不能很好地适应P2P网络环境,动态信任模型是新的研究热点。本文在对现有P2P环境中的信任机制进行分析的基础上,通过研究消费节点对服务节点的信任,针对节点间的信息交换活动提出了一种改进的信用评估模型,评估服务提供者在信息交换过程中的信用度变化过程;并引入风险机制,分析了P2P网络中节点间进行信息交换的风险。实验证明,该模型能有效地抗信用炒作和抗周期性欺骗。     

Nonmonotonic Trust Management for P2P Applications

Community decisions about access control in virtual communities are non-monotonic in nature. This means that they cannot be expressed in current, monotonic trust management languages such as the family of Role Based Trust Management languages (RT). To solve this problem we propose RT, which adds a restricted form of negation to the standard RT language, thus admitting a controlled form of non-monotonicity. The semantics of RT is discussed and presented in terms of the well-founded semantics for Logic Programs. Finally we discuss how chain discovery can be accomplished for RT.     

P2 P网络中基于改进DyTrust的信任模型

为了动态提升P2P网络的适应性、可靠性和可信度,在DyTrust信任模型的基础上,考虑到风险因素和时间因素对P2 P网络节点信任的影响,引入一个基于服务质量的风险函数和时间衰减因子棕,提出一种适合P2 P复杂环境的信任模型。实验结果表明,相比现有信任模型,文中研究的P2 P网络信任模型具有更好的动态自适应能力、更强的恶意节点检测能力,以及更优越的反馈信息聚合能力,对P2 P网络的安全提供有力保障。     

基于时间序列的P2P网络综合信任模型研究

P2P网络具有动态性,自组织和匿名性等特点,从而导致网络中某些节点存在恶意行为,为了保证节点能提供可靠资源和良好服务,提出一种基于时间序列的P2P综合信任模型,使对等节点之间建立信任关系。该模型在计算直接信任度和间接信任度时引入时间衰减函数,近期的信任值衰减小,对整体信任度的影响大。通过反馈控制机制动态更新簇内节点和簇头节点的信任度,使整体信任值具有时效性,对节点信任度的评价更精确和更可靠。实验证明,该信任模型较DyTrust模型降低了节点之间的交互时延,稳定性和动态自适应性更好,检测恶意节点的能力更强,提高P2P网络的可信度,对P2P网络的安全提供有力保障。     

Knot Insertion Algorithms for ECT B-spline Curves

Knot insertion algorithm is one of the most important technologies of B-spline method. By inserting a knot the local prop- erties of B-spline curve and the control flexibility of its shape can be fiu＇ther improved, also the segmentation of the curve can be rea- lized. ECT spline curve is drew by the multi-knots spline curve with associated matrix in ECT spline space; Muehlbach G and Tang Y and many others have deduced the existence and uniqueness of the ECT spline function and developed many of its important properties .This paper mainly focuses on the knot insertion algorithm of ECT B-spline curve.It is the widest popularization of B-spline Behm algorithm and theory. Inspired by the Behm algorithm, in the ECT spline space, structure of generalized P61ya poly- nomials and generalized de Boor Fix dual functional, expressing new control points which are inserted after the knot by linear com- bination of original control vertex the single knot, and there are two cases, one is the single knot, the other is the double knot. Then finally comes the insertion algorithm of ECT spline curve knot. By application of the knot insertion algorithm, this paper also gives out the knot insertion algorithm of four order geometric continuous piecewise polynomial B-spline and algebraic trigonometric spline B-spline, which is consistent with previous results.     

一种面向服务的P2P存储系统模型

P2P存储系统以功能对等的方式组成存储网络,面向服务的体系结构为存储资源的有效管理以及按需服务的实现提供了一种思路。提出的P2P存储系统模型采用分层思想,建立在结构化覆盖网络之上,将异构节点存储资源封装成服务块,以用户需求为出发点,通过服务的动态选取和组合,形成可定制的个人存储视图,并给出一种对等节点的功能部署结构。模型达到分散控制,具有良好的可扩展性。     

Efficient sparse voxel octrees

In this paper, we examine the possibilities of using voxel representations as a generic way for expressing complex and feature-rich geometry on current and future GPUs. We present in detail a compact data structure for storing voxels and an efficient algorithm for performing ray casts using this structure. We augment the voxel data with novel contour information that increases geometric resolution, allows more compact encoding of smooth surfaces, and accelerates ray casts. We also employ a novel normal compression format for storing high-precision object-space normals. Finally, we present a variable-radius postprocess filtering technique for smoothing out blockiness caused by discrete sampling of shading attributes. Based on benchmark results, we show that our voxel representation is competitive with triangle-based representations in terms of ray casting performance, while allowing tremendously greater geometric detail and unique shading information for every voxel. Our voxel codebase is open sourced and available at http://code.google.com/p/efficient-sparse-voxel-octrees/.     

Pentagons: A weakly relational abstract domain for the efficient validation of array accesses

We introduce Pentagons (), a weakly relational numerical abstract domain useful for the validation of array accesses in byte-code and intermediate languages (IL). This abstract domain captures properties of the form of . It is more precise than the well known Interval domain, but it is less precise than the Octagon domain.The goal of is to be a lightweight numerical domain useful for adaptive static analysis, where is used to quickly prove the safety of most array accesses, restricting the use of more precise (but also more expensive) domains to only a small fraction of the code.We implemented the abstract domain in , a generic abstract interpreter for.NET assemblies. Using it, we were able to validate 83% of array accesses in the core runtime library in a little bit more than 3 minutes.     

一种基于语义P2P的Web服务发现模型

提出了一种基于语义P2P的Web服务发现和选择模型，引入一种新的本体编码方式，根据分类服务注册节点的本体编码对其在P2P网络内进行组织，实现了P2P层内的语义支持发现。本文创新性的在P2P发现方面加入了本体信息，使得Web服务在P2P层内支持语义发现，提出的模型结合了集中式Web服务发现方式和分布式Web服务方式发现的优点，提高了服务发现的准确性和即时性。     

A distributed approach to node clustering in decentralized peer-to-peer networks

Connectivity-based node clustering has wide-ranging applications in decentralized peer-to-peer (P2P) networks such as P2P file sharing systems, mobile ad-hoc networks, P2P sensor networks, and so forth. This paper describes a connectivity-based distributed node clustering scheme (CDC). This scheme presents a scalable and efficient solution for discovering connectivity-based clusters in peer networks. In contrast to centralized graph clustering algorithms, the CDC scheme is completely decentralized and it only assumes the knowledge of neighbor nodes instead of requiring a global knowledge of the network (graph) to be available. An important feature of the CDC scheme is its ability to cluster the entire network automatically or to discover clusters around a given set of nodes. To cope with the typical dynamics of P2P networks, we provide mechanisms to allow new nodes to be incorporated into appropriate existing clusters and to gracefully handle the departure of nodes in the clusters. These mechanisms enable the CDC scheme to be extensible and adaptable in the sense that the clustering structure of the network adjusts automatically as nodes join or leave the system. We provide detailed experimental evaluations of the CDC scheme, addressing its effectiveness in discovering good quality clusters and handling the node dynamics. We further study the types of topologies that can benefit best from the connectivity-based distributed clustering algorithms like CDC. Our experiments show that utilizing message-based connectivity structure can considerably reduce the messaging cost and provide better utilization of resources, which in turn improves the quality of service of the applications executing over decentralized peer-to-peer networks.     

一种用于P2P网络的访问控制模型

由于P2P网络中的节点具有高度的自治性和随意性,使得P2P网络的内部安全隐患突出,如何区分恶意节点,为良节点提供更好的服务成为研究的重点。文章提出一种基于椭圆曲线数字签名和门限密钥分享的分布式认证服务模型,可以在一定程度上区分出潜在的恶意节点,此外,利用证书更新和证书撤销策略能够更进一步地孤立恶意节点,把恶意节点的危害降低到最小。最后文章通过实验验证了该模型的有效性。     

P2P技术在网格文件管理中的应用

目前把网格分为两类:计算网格和数据网格。计算网格目标在于通过大量计算节点的协作来减少应用程序的执行时间。数据网格提供解决大量数据管理的问题的方法。目前网格文件传输软件例如Grid FTP使用Client/Server结构,在性能和结构上存在问题。将网格和P2P结合起来,提出一种新的非集中式的、高效的数据网格文件管理协议。     

VectorTrust: trust vector aggregation scheme for trust management in peer-to-peer networks

With emerging Internet-scale open content and resource sharing, social networks, and complex cyber-physical systems, trust issues become prominent. Conventional trust mechanisms are inadequate at addressing trust issues in decentralized open environments. In this paper, we propose a trust vector based trust management scheme called VectorTrust for aggregation of distributed trust scores. Leveraging a Bellman–Ford based algorithm for fast and lightweight trust score aggregation, VectorTrust features localized and distributed concurrent communication. Built on a trust overlay network in a peer-to-peer network, a VectorTrust-enabled system is decentralized by nature and does not rely on any centralized server or centralized trust aggregation. We design, implement, and analyze trust rating, trust aggregation, and trust management strategies. To evaluate the performance, we design and implement a VectorTrust simulator (VTSim) in an unstructured P2P network. The analysis and simulation results demonstrate the efficiency, accuracy, scalability, and robustness of VectorTrust scheme. On average, VectorTrust converges faster and involves less complexity than most existing trust schemes. VectorTrust remains robust and tolerant to malicious peers and malicious behaviors. With dynamic growth of P2P network scales and topology complexities, VectorTrust scales well with reasonable overheads (about O(lg?N) communication overheads) and fast convergence speed (about O(log? _D N) iterations).