Commenced in January 2007
Frequency: Monthly
Edition: International
Paper Count: 2

Search results for: Qiuyi Lyu

2 Speedup Breadth-First Search by Graph Ordering

Authors: Qiuyi Lyu, Bin Gong


Breadth-First Search(BFS) is a core graph algorithm that is widely used for graph analysis. As it is frequently used in many graph applications, improve the BFS performance is essential. In this paper, we present a graph ordering method that could reorder the graph nodes to achieve better data locality, thus, improving the BFS performance. Our method is based on an observation that the sibling relationships will dominate the cache access pattern during the BFS traversal. Therefore, we propose a frequency-based model to construct the graph order. First, we optimize the graph order according to the nodes’ visit frequency. Nodes with high visit frequency will be processed in priority. Second, we try to maximize the child nodes overlap layer by layer. As it is proved to be NP-hard, we propose a heuristic method that could greatly reduce the preprocessing overheads. We conduct extensive experiments on 16 real-world datasets. The result shows that our method could achieve comparable performance with the state-of-the-art methods while the graph ordering overheads are only about 1/15.

Keywords: breadth-first search, BFS, graph ordering, graph algorithm

Procedia PDF Downloads 58
1 Investigation of Elastic Properties of 3D Full Five Directional (f5d) Braided Composite Materials

Authors: Apeng Dong, Shu Li, Wenguo Zhu, Ming Qi, Qiuyi Xu


The primary objective of this paper is to focus on the elasticity properties of three-dimensional full five directional (3Df5d) braided composite. A large body of research has been focused on the 3D four directional (4d) and 3D five directional (5d) structure but not much research on the 3Df5d material. Generally, the influence of the yarn shape on mechanical properties of braided materials tends to be ignored, which makes results too ideal. Besides, with the improvement of the computational ability, people are accustomed to using computers to predict the material parameters, which fails to give an explicit and concise result facilitating production and application. Based on the traditional mechanics, this paper firstly deduced the functional relation between elasticity properties and braiding parameters. In addition, considering the actual shape of yarns after consolidation, the longitudinal modulus is modified and defined practically. Firstly, the analytic model is established based on the certain assumptions for the sake of clarity, this paper assumes that: A: the cross section of axial yarns is square; B: The cross section of braiding yarns is hexagonal; C: the characters of braiding yarns and axial yarns are the same; D: The angle between the structure boundary and the projection of braiding yarns in transverse plane is 45°; E: The filling factor ε of composite yarns is π/4; F: The deformation of unit cell is under constant strain condition. Then, the functional relation between material constants and braiding parameters is systematically deduced aimed at the yarn deformation mode. Finally, considering the actual shape of axial yarns after consolidation, the concept of technology factor is proposed and the longitudinal modulus of the material is modified based on the energy theory. In this paper, the analytic solution of material parameters is given for the first time, which provides a good reference for further research and application for 3Df5d materials. Although the analysis model is established based on certain assumptions, the analysis method is also applicable for other braided structures. Meanwhile, it is crucial that the cross section shape and straightness of axial yarns play dominant roles in the longitudinal elastic property. So in the braiding and solidifying process, the stability of the axial yarns should be guaranteed to increase the technology factor to reduce the dispersion of material parameters. Overall, the elastic properties of this materials are closely related to the braiding parameters and can be strongly designable, and although the longitudinal modulus of the material is greatly influenced by the technology factors, it can be defined to certain extent.

Keywords: analytic solution, braided composites, elasticity properties, technology factor

Procedia PDF Downloads 173