Accurate calculations of travel times and raypaths of reflection waves are important for reflection travel time tomography.The multistage shortest path method(MSPM)and multistage fast marching method(MFMM)have been wi...Accurate calculations of travel times and raypaths of reflection waves are important for reflection travel time tomography.The multistage shortest path method(MSPM)and multistage fast marching method(MFMM)have been widely used in reflection wave raytracing,and both of them are characterized by high efficiency and ac-curacy.However,the MSPM does not strictly follow Snell's law at the interface because it treats the interface point as a sub-source,resulting in a decrease in accuracy.The MFMM achieves high accuracy by solving the Eikonal equation in local triangular mesh.However,the implementation process is complex.Here we propose a new method which uses linear interpolation to compute the incident travel time of interface points and then using Snell's law to compute the reflection travel time of grid points just above the interface.Our new method is much simpler than the MFMM;furthermore,numerical simulations show that the accuracy of the MFMM and our new method are basically the same,thus the reflection tomography algorithms which use our new method are easier to implement without decreasing accuracy.Besides,our new method can be extended easily to other grid-based raytracing methods.展开更多
The present paper predicted the function of unknow genes by analyzing the co-expression data of Arabidopsis thaliana from biological pathway based on the shortest-path algorithm. This paper proposed that transitive co...The present paper predicted the function of unknow genes by analyzing the co-expression data of Arabidopsis thaliana from biological pathway based on the shortest-path algorithm. This paper proposed that transitive co-expression among genes can be used as an important attribute to link genes of the same biological pathway. The genes from the same biological pathway with similar functions are strongly correlated in expression. Moreover,the function of unknown genes can be predicted by the known genes where they are strongly correlated in expression lying on the same shortest-path from the biological pathway. Analyzing the Arabidopsis thaliana from the biological pathway,this study showed that this method can reliably reveal function of the unknown Arabidopsis thaliana genes and the approach of predicting gene function by transitiving co-expression in shortest-path is feasible and effective.展开更多
Fast identifying the amount of information that can be gained by measuring a network via shortest-paths is one of the fundamental problem for networks exploration and monitoring.However,the existing methods are time-c...Fast identifying the amount of information that can be gained by measuring a network via shortest-paths is one of the fundamental problem for networks exploration and monitoring.However,the existing methods are time-consuming for even moderate-scale networks.In this paper,we present a method for fast shortest-path cover identification in both exact and approximate scenarios based on the relationship between the identification and the shortest distance queries.The effectiveness of the proposed method is validated through synthetic and real-world networks.The experimental results show that our method is 105 times faster than the existing methods and can solve the shortest-path cover identification in a few seconds for large-scale networks with millions of nodes and edges.展开更多
Effective link analysis techniques are needed to help law enforcement and intelligence agencies fight money laundering. This paper presents a link analysis technique that uses a modified shortest-path algorithms to id...Effective link analysis techniques are needed to help law enforcement and intelligence agencies fight money laundering. This paper presents a link analysis technique that uses a modified shortest-path algorithms to identify the strongest association paths between entities in a money laundering network. Based on two-tree Dijkstra and Priority＇First-Search （PFS） algorithm, a modified algorithm is presented. To apply the algorithm, a network representation transformation is made first.展开更多
This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linea...This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given.展开更多
在3DS MAX 中,物体材质的效果对于一个动画的好坏起着很大的作用,而在3DS MAX的材质编辑器中材质又扮演着重要的角色。现在制作一个新产品广告,为了突出产品的名称或者强调其它的功能,就可以用放大镜功能。要制作放大效果有许多技巧,由...在3DS MAX 中,物体材质的效果对于一个动画的好坏起着很大的作用,而在3DS MAX的材质编辑器中材质又扮演着重要的角色。现在制作一个新产品广告,为了突出产品的名称或者强调其它的功能,就可以用放大镜功能。要制作放大效果有许多技巧,由于材质的不同,影响材质的真实度。下面我给大家介绍一种方便快捷的方法,就是运用M A X 的独特的光影追踪(RAYTRACE)材质,制作放大镜的放大效果。本例是模拟一个放大镜镜片球体。展开更多
Data center networks may comprise tens or hundreds of thousands of nodes,and,naturally,suffer from frequent software and hardware failures as well as link congestions.Packets are routed along the shortest paths with s...Data center networks may comprise tens or hundreds of thousands of nodes,and,naturally,suffer from frequent software and hardware failures as well as link congestions.Packets are routed along the shortest paths with sufficient resources to facilitate efficient network utilization and minimize delays.In such dynamic networks,links frequently fail or get congested,making the recalculation of the shortest paths a computationally intensive problem.Various routing protocols were proposed to overcome this problem by focusing on network utilization rather than speed.Surprisingly,the design of fast shortest-path algorithms for data centers was largely neglected,though they are universal components of routing protocols.Moreover,parallelization techniques were mostly deployed for random network topologies,and not for regular topologies that are often found in data centers.The aim of this paper is to improve scalability and reduce the time required for the shortest-path calculation in data center networks by parallelization on general-purpose hardware.We propose a novel algorithm that parallelizes edge relaxations as a faster and more scalable solution for popular data center topologies.展开更多
基金This research is jointly sponsored by National Natural Science Foundation of China(Grant No.U1901602)Shenzhen Key Laboratory of Deep Offshore Oil and Gas Exploration Technology(Grant No.ZDSYS20190902093007855)+1 种基金Shenzhen Science and Technology Program(KQTD20170810111725321)This study is also sponsored by the China Earthquake Science Experiment Project of China Earthquake Administration(Grant No.2018CSES0101).
文摘Accurate calculations of travel times and raypaths of reflection waves are important for reflection travel time tomography.The multistage shortest path method(MSPM)and multistage fast marching method(MFMM)have been widely used in reflection wave raytracing,and both of them are characterized by high efficiency and ac-curacy.However,the MSPM does not strictly follow Snell's law at the interface because it treats the interface point as a sub-source,resulting in a decrease in accuracy.The MFMM achieves high accuracy by solving the Eikonal equation in local triangular mesh.However,the implementation process is complex.Here we propose a new method which uses linear interpolation to compute the incident travel time of interface points and then using Snell's law to compute the reflection travel time of grid points just above the interface.Our new method is much simpler than the MFMM;furthermore,numerical simulations show that the accuracy of the MFMM and our new method are basically the same,thus the reflection tomography algorithms which use our new method are easier to implement without decreasing accuracy.Besides,our new method can be extended easily to other grid-based raytracing methods.
基金Supported by Shanghai Municipal Education Committee Educationand Scientific Research (Grant No. 07ZZ60)~~
文摘The present paper predicted the function of unknow genes by analyzing the co-expression data of Arabidopsis thaliana from biological pathway based on the shortest-path algorithm. This paper proposed that transitive co-expression among genes can be used as an important attribute to link genes of the same biological pathway. The genes from the same biological pathway with similar functions are strongly correlated in expression. Moreover,the function of unknown genes can be predicted by the known genes where they are strongly correlated in expression lying on the same shortest-path from the biological pathway. Analyzing the Arabidopsis thaliana from the biological pathway,this study showed that this method can reliably reveal function of the unknown Arabidopsis thaliana genes and the approach of predicting gene function by transitiving co-expression in shortest-path is feasible and effective.
基金This work was supported in part by the National Natural Science Foundation of China(61471101)the National Natural Science Foundation of China(U1736205).
文摘Fast identifying the amount of information that can be gained by measuring a network via shortest-paths is one of the fundamental problem for networks exploration and monitoring.However,the existing methods are time-consuming for even moderate-scale networks.In this paper,we present a method for fast shortest-path cover identification in both exact and approximate scenarios based on the relationship between the identification and the shortest distance queries.The effectiveness of the proposed method is validated through synthetic and real-world networks.The experimental results show that our method is 105 times faster than the existing methods and can solve the shortest-path cover identification in a few seconds for large-scale networks with millions of nodes and edges.
基金Supported bythe National Tenth Five-Year PlanforScientific and Technological Development of China (2001BA102A06-11)
文摘Effective link analysis techniques are needed to help law enforcement and intelligence agencies fight money laundering. This paper presents a link analysis technique that uses a modified shortest-path algorithms to identify the strongest association paths between entities in a money laundering network. Based on two-tree Dijkstra and Priority＇First-Search （PFS） algorithm, a modified algorithm is presented. To apply the algorithm, a network representation transformation is made first.
文摘This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given.
文摘在3DS MAX 中,物体材质的效果对于一个动画的好坏起着很大的作用,而在3DS MAX的材质编辑器中材质又扮演着重要的角色。现在制作一个新产品广告,为了突出产品的名称或者强调其它的功能,就可以用放大镜功能。要制作放大效果有许多技巧,由于材质的不同,影响材质的真实度。下面我给大家介绍一种方便快捷的方法,就是运用M A X 的独特的光影追踪(RAYTRACE)材质,制作放大镜的放大效果。本例是模拟一个放大镜镜片球体。
基金This work was supported by the Serbian Ministry of Science and Education(project TR-32022)by companies Telekom Srbija and Informatika.
文摘Data center networks may comprise tens or hundreds of thousands of nodes,and,naturally,suffer from frequent software and hardware failures as well as link congestions.Packets are routed along the shortest paths with sufficient resources to facilitate efficient network utilization and minimize delays.In such dynamic networks,links frequently fail or get congested,making the recalculation of the shortest paths a computationally intensive problem.Various routing protocols were proposed to overcome this problem by focusing on network utilization rather than speed.Surprisingly,the design of fast shortest-path algorithms for data centers was largely neglected,though they are universal components of routing protocols.Moreover,parallelization techniques were mostly deployed for random network topologies,and not for regular topologies that are often found in data centers.The aim of this paper is to improve scalability and reduce the time required for the shortest-path calculation in data center networks by parallelization on general-purpose hardware.We propose a novel algorithm that parallelizes edge relaxations as a faster and more scalable solution for popular data center topologies.
