graph edge partitionmodels have recently become an appealing alternative to graph vertex partitionmodels for parallel and distributed computing due to their flexibility in balancing loads and their performance in re...
详细信息
ISBN:
(纸本)9781450365239
graph edge partitionmodels have recently become an appealing alternative to graph vertex partitionmodels for parallel and distributed computing due to their flexibility in balancing loads and their performance in reducing communication cost [1, 3]. In this paper, we introduce a simple yet effective graph edge partitioning model for GPU computing. In practice, our model yields high partition quality (better than or the same as the state-of-the-art edge partition approaches, at least for power-law graphs) with low partition overhead. In theory, previous work [1] showed that an approximation factor of O(d(max) root logn log k) apply to the graphs with m = O(k(2)) edges (k is the number of partitions). Our model extends this result to all graphs. We demonstrate how graph edge partitionmodel can be applied to GPU computing. We draw our examples from GPU program for locality enhancement both over time and (processor) space. For the first time, we demonstrate the effectiveness of edge partition for modeling data reuse in a many-core processors, both in theory and in practice.
For better reuse of motion capture data, long motion sequences need to be segmented into multiple motion clips of simple motion types. In this paper, we propose a method for motion capture data segmentation based on g...
详细信息
ISBN:
(纸本)9781479927630
For better reuse of motion capture data, long motion sequences need to be segmented into multiple motion clips of simple motion types. In this paper, we propose a method for motion capture data segmentation based on graphpartition. Each frame of motion sequence is viewed as a node in an undirected weighted graph, and the weight of an edge is the similarity between two frames corresponding to the two nodes connected by the edge. The optimal segmentation is obtained through graphpartition algorithm, which makes the similarities of nodes in each subgraph being high, and the similarities between different subgraphs being low. After the segment scores at each frame are calculated, double thresholds decision method is conducted on the score curve to detect segment points. Experimental results show that our method obtains good segmentation results.
For better reuse of motion capture data, long motion sequences need to be segmented into multiple motion clips of simple motion types. In this paper, we propose a method for motion capture data segmentation based on g...
详细信息
ISBN:
(纸本)9781479927654
For better reuse of motion capture data, long motion sequences need to be segmented into multiple motion clips of simple motion types. In this paper, we propose a method for motion capture data segmentation based on graphpartition. Each frame of motion sequence is viewed as a node in an undirected weighted graph, and the weight of an edge is the similarity between two frames corresponding to the two nodes connected by the edge. The optimal segmentation is obtained through graphpartition algorithm, which makes the similarities of nodes in each subgraph being high, and the similarities between different subgraphs being low. After the segment scores at each frame are calculated, double thresholds decision method is conducted on the score curve to detect segment points. Experimental results show that our method obtains good segmentation results.
This paper conducts a formal study of the shot boundary detection problem. First, a general formal framework of shot boundary detection techniques is proposed. Three critical techniques, i.e., the representation of vi...
详细信息
This paper conducts a formal study of the shot boundary detection problem. First, a general formal framework of shot boundary detection techniques is proposed. Three critical techniques, i.e., the representation of visual content, the construction of continuity signal and the classification of continuity values, are identified and formulated in the perspective of pattern recognition. Meanwhile, the major challenges to the framework are identified. Second, a comprehensive review of the existing approaches is conducted. The representative approaches are categorized and compared according to their roles in the formal framework. Based on the comparison of the existing approaches, optimal criteria for each module of the framework are discussed, which will provide practical guide for developing novel methods. Third, with all the above issues considered, we present a unified shot boundary detection system based on graph partition model. Extensive experiments are carried out on the platform of TRECVID. The experiments not only verify the optimal criteria discussed above, but also show that the proposed approach is among the best in the evaluation of TRECVID 2005. Finally, we conclude the paper and present some further discussions on what shot boundary detection can learn from other related fields.
暂无评论