Optimization of RDF link traversal based query execution

Aiming at the problem that only some types of SPARQL （ simple protocal and resource description framework query language） queries can be answered by using the current resource description framework link traversal based query execution （RDF-LTE） approach, this paper discusses how the execution order of the triple pattern affects the query results and cost based on concrete SPARQL queries, and analyzes two properties of the web of linked data, missing backward links and missing contingency solution. Then three heuristic principles for logic query plan optimization, namely, the filtered basic graph pattern （FBGP） principle, the triple pattern chain principle and the seed URIs principle, are proposed. The three principles contribute to decrease the intermediate solutions and increase the types of queries that can be answered. The effectiveness and feasibility of the proposed approach is evaluated. The experimental results show that more query results can be returned with less cost, thus enabling users to develop the full potential of the web of linked data.

An image encryption algorithm based on spatiotemporal chaos and middle order traversal of a binary tree

This paper proposes an image encryption algorithm based on spatiotemporal chaos and middle order traversal of a binary tree.Firstly,other programming software is used to perform the middle order traversal,and the plaintext image is sorted according to the middle order traversal sequence on the permutation.Secondly,the chaotic sequence is generated using the coupled map lattice to set the chaotic interference value.Finally,the XOR operation between the adjacent pixel values of the replacement image is completed to generate the ciphertext matrix.The simulation and experimental results show that the proposed algorithm can resist typical attacks and has good robustness.

Network address translation traversal based on Bernoulli laws of large number in P2P streaming system

P2P streaming application must realize network address translation （NAT） traversal. To handle low success ratio of the existing NAT traversal algorithm, UPnP-STUN （UPUN） and port-mapping sample estimation （PMSE） algorithm are recommended in this paper. UPUN is the combination of UPnP and STUN, and PMSE utilizes port mapping samples added by symmetric NAT for different sessions to estimate regularity of port mapping of symmetric NAT, which takes advantage of the Bernoulli law of large numbers. Besides, for the situation that both peers are behind NAT, and to handle heavy relay server load when many inner peers want to communicate with each other, a peer auxiliary-relay （PAR） algorithm is presented. PAR lets outer peers with sufficient bandwidth act as relay servers to alleviate pressure of real server, which could avoid NAT traversal failure caused by single point failure of relay server. Finally, experiments show that the proposed algorithms could improve the success ratio significantly for NAT traversal in P2P streaming application as well as improve P2P streaming application applicability.

Recursive and Nonrecursive Traversal Algorithms for Dynamically Created Binary Trees

The modeling of dynamical systems from a time series implemented by our DSA program introduces binary trees of height D with all leaves on the same level, and the related subtrees of height L 〈 D. These are called e-trees and e-subtrees. The recursive and nonrecursive versions of the traversal algorithms for the trees with dynamically created nodes are discussed. The original nonrecursive algorithms that return the pointer to the next node in preorder, inorder and postorder traversals are presented. The space-time complexity analysis shows and the execution time measurements confirm that for these O（2D） algorithms, the recursive versions have approximately 10-25% better time constants. Still, the use of nonrecursive algorithms may be more appropriate in several occasions.

An Improved Approach for Generating Test Cases during Model-Based Testing Using Tree Traversal Algorithm

During the model-based software testing process, test cases are generated from modeled requirements to conduct acceptance testing. However, existing approaches generate erroneous test cases, lack full coverage criteria and prototype tools. Therefore, the aim of this research is to develop an approach capable of reducing erroneous test case generation based on full coverage criteria and a prototype tool. The method employed was to develop a parser to extract information from the XMI file of a modeling diagram where a tree is constructed and a traversal operation executed on the nodes and edges to generate test cases. The results obtained from the proposed approach showed that 97.35% of the generated test cases were precise and comprehensive enough to conduct testing because 99.01% of all the nodes and edges were fully covered during the traversal operations.

Binary Tree’s Recursion Traversal Algorithm and Its Improvement

Binary tree is a very important data structure in computer science. Some major properties are discussed. Both recursive and non-recursive traversal methods of binary tree are discussed in detail. Some improvements in programming are proposed.

DYNAMIC TRAVERSAL CRITERION FOR GEOMETRIC FRACTALS

This paper presents a new generating criterion for self-similar geometric fractalsDynamic Traversal Criterion (DTC) and the principle to practice it. According to the principle,symbol shifting technique is put forward which can control the traversal symbols dynamically in recursive procession. The Dynamic Traversal Criterion inherits the mechanism for generating self-similar fractals from traditional way and creates more fractal images from one initiator and generator than Static traversal strategy.

Deformation characteristics and instability mechanism of transportation hub under downward traversal conditions of the double-track super-large diameter shield tunnel

To investigate the deformation characteristics and instability mechanism of the transportation hub underdownward traversal conditions of the double-track super-large diameter shield tunnel, take the example of BeijingEast Sixth Ring Road into the ground reconstruction project. Using the field experimental monitoring method andnumerical simulation method, after verifying the accuracy of the model, this manuscript begins to unfold theanalysis. The results show that, without any deformation prevention and control measures, The basement raft ofthe underground structure of the transportation hub will produce a deformation difference of 18 mm, and thetensile stress is more than 1.43 MPa, the inhomogeneous deformation and structural cracking will lead tostructural instability and groundwater surges, which seriously affects the safe operation of the transportation hubstation. When control measures are taken, the deformation and stress of the base raft slab of the undergroundstructure of the transportation hub are within the prescribed limits, which can ensure the safe operation of thestation. The displacement of the base slab of the underground structure in the horizontal direction of the crosssection is all pointing to the east, and the overall trend is to shift from the first tunnel to the backward tunnel. Thehorizontal displacement of the base slab in the direction of the tunnel axis all points to the beginning of thecrossing, and the displacement of the slab in the vertical direction is distributed as "rising in the middle andsinking in the surroundings". For a two-lane super-large diameter shield tunnel penetrating an undergroundstructure, there are two mechanical effects: unloading rebound and perimeter rock pressure. The above deformation characteristics are the superposition effect produced by the two, and this fine assessment of the deformation of the raft foundation provides a scientific basis for formulating the deformation control countermeasuresof the crossing project. At the same time, it makes up for the blank of the double-track super-large diameter shieldtunnel down through the transportation hub project.

Fast Single-phase Fault Location Method Based on Community Graph Depth-first Traversal for Distribution Network

With the increasing complexity of distribution network structures originating from the high penetration of renewable energy and responsive loads,fast and accurate fault location technology for distribution networks is a prerequisite for rapid isolation of faults and restoration of the power supply.In this paper,a fault location method based on community graph depth-first traversal is proposed for fast location of single-phase ground faults in distribution networks.First,this paper defines the fault graph weight of the vertices in the distribution network graph model,which can be used to reflect the topology of the vertices and fault points as well as the fluctuation of the vertices’currents.Then,the vertices on the graph model are clustered by using an improved parallel louvain method(IPLM).Finally,the community formed by IPLM is used as the smallest unit for depth-first traversal to achieve fast and accurate location of the fault section.The paper develops a distribution network graph model of IEEE 33-bus system on the graph database for testing.And three other methods are selected for comparison with IPLMDF.The test results show that IPLMDF can achieve fast and accurate fault location when half of the nodes in the distribution network are equipped with D-PMUs.When some of the D-PMUs lose time synchronization,it is still possible to locate the fault section,and at the same time,the locating results can be avoided by falling into local optimal solutions.

On the graph traversal method for evaluating linear binary-chain programs

Grahne et al. have presented a graph algorithm for evaluating a subset of recursive queries. This method consists of two phases. In the first phase, the method transforms a linear binary-chain program into a set of equations over expressions containing predicate symbols. In the second phase, a graph is constructed from the equations and the answers are produced by traversing the relevant paths. A new algorithm is described which requires less time than Grahne’ s. The key idea of the improvement is to reduce the search space that will be traversed when a query is invoked. Further, the evaluation of cyclic data is speeded up by generating most answers directly in terms of the answers already found and the associated 'path information' instead of traversing the corresponding paths as usual. In this way, this algorithm achieves a linear time complexity for both acyclic and most of cyclic data.

Graph Traversal and Top-Down Evaluation of Logic Queries

In this paper, an optimal method to handle cyclic and acyclic data relations in the linear recursive queries is proposed. High efficiency is achieved by integrating graph traversal mechanisms into a top-down evaluation. In such a way the subsumption checks and the identification of cyclic data can be done very efficielltly First, based on the subsumption checks, the search space can be reduced drastically by avoiding any redundant expansion operation. In fact, in the case of non-cyclic data, the proposed algorithm requires only linear time for evaluating a linear recursive query. On the other hand, in the case of cyclic data, by using the technique for isolating strongly connected components a lot of answers can be generated directly in terms of the intermediate results and the relevant path information instead of evaluating them by performing algebraic operations. Since the cost of generating an answer is much less than that of evaluating an answer by algebraic operations, the time consumption for cyclic data can be reduced by an order of magnitude or more.

Z^2 traversal order: An interleaving approach for VR stereo rendering on tile-based GPUs

With increasing demands of virtual reality(VR) applications, efficient VR rendering techniques are becoming essential. Because VR stereo rendering has increased computational costs to separately render views for the left and right eyes, to reduce the rendering cost in VR applications, we present a novel traversal order for tile-based mobile GPU architectures: Z^2 traversal order. In tile-based mobile GPU architectures,a tile traversal order that maximizes spatial locality can increase GPU cache efficiency. For VR applications, our approach improves upon the traditional Z order curve.We render corresponding screen tiles in left and right views in turn, or simultaneously, and as a result, we can exploit spatial adjacency of the two tiles. To evaluate our approach, we conducted a trace-driven hardware simulation using Mesa and a hardware simulator. Our experimental results show that Z^2 traversal order can reduce external memory bandwidth requirements and increase rendering performance.

Macroscopic Traversable Wormholes: Minimum Requirements

While wormholes are just as good a prediction of Einstein’s theory as black holes, they are subject to severe restrictions from quantum field theory. To allow for the possibility of interstellar travel, a macroscopic wormhole would need to maintain sufficiently low radial tidal forces. It is proposed in this paper that the assumption of zero tidal forces, i.e., the limiting case, is sufficient for overcoming the restrictions from quantum field theory. The feasibility of this approach is subsequently discussed by 1) introducing the additional conditions needed to ensure that the radial tidal forces can indeed be sufficiently low and 2) by viewing traversable wormholes as emergent phenomena, thereby increasing the likelihood of their existence.

Noncommutative-Geometry Wormholes Based on the Casimir Effect

While wormholes are as good a prediction of Einstein’s theory as black holes, they are subject to severe restrictions from quantum field theory. In particular, holding a wormhole open requires a violation of the null energy condition, calling for the existence of exotic matter. The Casimir effect has shown that this physical requirement can be met on a small scale, thereby solving a key conceptual problem. The Casimir effect does not, however, guarantee that the small-scale violation is sufficient for supporting a macroscopic wormhole. The purpose of this paper is to connect the Casimir effect to noncommutative geometry, which also aims to accommodate small-scale effects, the difference being that these can now be viewed as intrinsic properties of spacetime. As a result, the noncommutative effects can be implemented by modifying only the energy momentum tensor in the Einstein field equations, while leaving the Einstein tensor unchanged. The wormhole can therefore be macroscopic in spite of the small Casimir effect.

Exploration of Traversable Wormholes Sustained by an Extra Spatial Dimension

The main goal of this paper is to determine the effect of an extra dimension on a traversable wormhole. Here an earlier study by the author [Phys. Rev. D 98, 064041 (2018)] is extended in several significant ways. To begin with, the extra spatial dimension is assumed to be time dependent, while the redshift and shape functions, as well as the extra dimension, are functions of both r and l, the respective radial and extra coordinates;the last of these is therefore a function of r, l, and t. The main objective is to determine the conditions that allow the throat of the wormhole to be threaded with ordinary matter (by respecting the null energy condition) and that the same conditions lead to a violation of the null energy condition in the fifth dimension, which is therefore responsible for sustaining the wormhole. The dependence of the extra dimension on l and t is subject to additional conditions that are subsequently analyzed in this paper. Finally, the extra dimension may be extremely small or even curled up.

Volumetric extraction of porous materials based on octree algorithm

Through the octree data structure analysis,a volumetric dataset of closed-cell porous materials is converted into a dataset of hierarchical octree nodes,and then the specific traversal search algorithm on the octree nodes is depicted in details,which is involved in six steps of the volume growth model and one step of the volume decomposition model.Moreover,the conditions of both the proceeding traversal and three possibilities of terminating are given,and the traversal algorithm of completeness is proved from a theoretical perspective.Finally,using a simulated volumetric dataset of columnar pores,the extracting effectiveness of the octree traversal algorithm is verified.The results show that the volume and the distribution information of pores can be successfully extracted by the proposed algorithm,which builds a solid foundation for a more effective performance analysis of porous materials.

A Study on Reflection Phase Time of Particles Passing through a Potential Well

To understand the physical meaning of phase time further more, we discuss the reflection phase time of quantum-particles passing though a potential well It is shown that the reflection phase time is equal to the transmission phase time in value and negative under certain conditions for a square potential well by analyzing While quantum-particles passing through the potential well, we think that this course can be described only with the velocity of energy of quantum mechanics whether or not they are reflected or transmitted eventually

轿车尾流移测试验研究

轿车的尾流结构与其空气阻力、升力与安全性有密切联系 ,为进一步研究轿车尾流结构及验证尾流场数值模拟结果的精确性提供依据 ,需通过试验得到较为全面地反映尾流结构的定量信息。为此 ,进行了红旗CA774轿车 1 10模型的七孔探针尾流移测试验 。

陀螺控制导线精度的正确评定

本文推证了陀螺控制导线精度评定的严密公式,并讨论了用误差椭圆来表示最弱点点位精度的方法。所有评定精度的公式均依据最小二乘矩阵平差原理得出,这些公式对正确进行误差预计很有意义。

Improving vertex-frontier based GPU breadth-first search

Breadth-first search(BFS) is an important kernel for graph traversal and has been used by many graph processing applications. Extensive studies have been devoted in boosting the performance of BFS. As the most effective solution, GPU-acceleration achieves the state-of-the-art result of 3.3×109 traversed edges per second on a NVIDIA Tesla C2050 GPU. A novel vertex frontier based GPU BFS algorithm is proposed, and its main features are three-fold. Firstly, to obtain a better workload balance for irregular graphs, a virtual-queue task decomposition and mapping strategy is introduced for vertex frontier expanding. Secondly, a global deduplicate detection scheme is proposed to remove reduplicative vertices from vertex frontier effectively. Finally, a GPU-based bottom-up BFS approach is employed to process large frontier. The experimental results demonstrate that the algorithm can achieve 10% improvement over the state-of-the-art method on diverse graphs. Especially, it exhibits 2-3 times speedup on low-diameter and scale-free graphs over the state-of-the-art on a NVIDIA Tesla K20 c GPU, reaching a peak traversal rate of 11.2×109 edges/s.