Approximate string matching using the k-difference technique has been widely applied to many fields such as pattern recognition and computational biology. Data dependency exists in the traditional sequential algorithm...
详细信息
Approximate string matching using the k-difference technique has been widely applied to many fields such as pattern recognition and computational biology. Data dependency exists in the traditional sequential algorithm. Therefore, it is hard to design a parallel algorithm for approximate string matching with k differences. This paper presents a technique to eliminate data dependency. Based on this technique, this paper also presents a parallel algorithm which can calculate the elements in the same row of the edit distance matrix in parallel by eliminating data dependency. The algorithm has high parallelism, but requires synchronization. To validate the proposed algorithm, it is implemented on GPU and multiple-core CPUs. Moreover, the CUDA optimization techniques are also presented in the paper. Finally, experimental results show that, compared with the traditional sequential algorithm on CPU with twenty-four cores, the proposed parallel algorithm achieves speedup of 7-42 on GPU.
In order to improve the network spatial reuse and maximize the network throughput, this paper presents a physical conflict model based power allocation and link scheduling algorithm (PPLA). Firstly, PPLA picks availab...
详细信息
In order to improve the network spatial reuse and maximize the network throughput, this paper presents a physical conflict model based power allocation and link scheduling algorithm (PPLA). Firstly, PPLA picks available set of parallel links using hexagon coloring method. With physical conflict model, it further obtains the minimum power vector which corresponds to parallel links set. The experimental results indicate that the algorithm can increase network spatial reuse ratio and improve throughput significantly.
Energy saving and the tracking performance are two important issues in moving target tracking. This paper presents a Voronoi structure-based nodes selection algorithm, which constructs a network model based on the pro...
详细信息
In the procedure of three-way handshake of transmission control protocol connection establishment, it involves the management of half-connection and connection tables. However, in the famous networks simulator NS2, th...
详细信息
In the procedure of three-way handshake of transmission control protocol connection establishment, it involves the management of half-connection and connection tables. However, in the famous networks simulator NS2, there is only a formal description instead of a concrete and complete implementation for the procedure of TCP connection establishment. An improvement was beed made on the point. Table structures for half-connections and connections are added, and the way of managing half-connection table in Linux kernel is also imported into NS2. Simulation results show that it is clear to monitor the change in half-connection table in the TCP connection establishment procedure, and thus the requirement of simulating the connection establishment procedure in studies such as protection from TCP SYN flooding attack can be met.
Router alias resolution is one of hard problems and important steps for router level Internet topology measurement based on traceroute mechanism, and the topology characteristic of the generated router level topology ...
详细信息
Router alias resolution is one of hard problems and important steps for router level Internet topology measurement based on traceroute mechanism, and the topology characteristic of the generated router level topology graph has close relationship with the completeness of alias resolution. The graph with its degrees following power-law distribution was taken as the base-graph, and the shortest paths from one source to others were computed for simulating topology measurement. Experiment results show that it is very probable to see different topology characteristics between the derived graph and the base-graph due to incomplete alias resolution. Most importantly, for large-scale router level topology measurement, the completeness of alias resolution must be improved with the increasing number of probe sources, and in this way the derived topology graph could be approximate to the real topology graph.
Community search is to explore valuable target community structure from a large social network. In real community, every point has a geographic location information, and many edges are uncertain. Such a network is cal...
Community search is to explore valuable target community structure from a large social network. In real community, every point has a geographic location information, and many edges are uncertain. Such a network is called spatial uncertain network. In order to meet the existing needs, this paper studies the community search in the spatial uncertain network so that the searched communities can be relatively close in the geographical location and the relationship between each other is also very close. Based on the spatial uncertain graph, this paper proposes K-R-τ community, and proposes a linear algorithm and a two-dimensional algorithm for community search in the spatial uncertain network. A large number of experiments are carried out on several real datasets, and the results show that the algorithm proposed in this paper is effective and accurate.
暂无评论