A novel framework for parallel subgraph isomorphism on GPUs is proposed, named GPUSI, which consists of GPU region exploration and GPU subgraph matching. The GPUSI iteratively enumerates subgraph instances and solves ...A novel framework for parallel subgraph isomorphism on GPUs is proposed, named GPUSI, which consists of GPU region exploration and GPU subgraph matching. The GPUSI iteratively enumerates subgraph instances and solves the subgraph isomorphism in a divide-and-conquer fashion. The framework completely relies on the graph traversal, and avoids the explicit join operation. Moreover, in order to improve its performance, a task-queue based method and the virtual-CSR graph structure are used to balance the workload among warps, and warp-centric programming model is used to balance the workload among threads in a warp. The prototype of GPUSI is implemented, and comprehensive experiments of various graph isomorphism operations are carried on diverse large graphs. The experiments clearly demonstrate that GPUSI has good scalability and can achieve speed-up of 1.4–2.6 compared to the state-of-the-art solutions.展开更多
Bicycle-sharing system is considered as a green option to provide a better connection between scenic spots and nearby metro/bus stations. Allocating and optimizing the layout of bicycle-sharing system inside the sceni...Bicycle-sharing system is considered as a green option to provide a better connection between scenic spots and nearby metro/bus stations. Allocating and optimizing the layout of bicycle-sharing system inside the scenic spot and around its influencing area are focused on. It is found that the terrain, land use, nearby transport network and scenery point distribution have significant impact on the allocation of bicycle-sharing system. While the candidate bicycle-sharing stations installed at the inner scenic points, entrances/exits and metro stations are fixed, the ones installed at bus-stations and other passenger concentration buildings are adjustable. Aiming at minimizing the total cycling distance and overlapping rate, an optimization model is proposed and solved based on the idea of cluster concept and greedy heuristic. A revealed preference/stated preference （RP/SP） combined survey was conducted at Xuanwu Lake in Nanjing, China, to get an insight into the touring trip characteristics and bicycle-sharing tendency. The results reveal that 39.81% visitors accept a cycling distance of 1-3 km and 62.50% respondents think that the bicycle-sharing system should charge an appropriate fee. The sttrvey indicates that there is high possibility to carry out a bicycle-sharing system at Xuanwu Lake. Optimizing the allocation problem cluster by cluster rather than using an exhaustive search method significantly reduces the computing amount from O（2^43） to O（43 2）. The 500 m-radius-coverage rate for the alternative optimized by 500 m-radius-cluster and 800 m-radius-cluster is 89.2% and 68.5%, respectively. The final layout scheme will provide decision makers engineering guidelines and theoretical support.展开更多
Astronomical cross-matching is a basic method for aggregating the observational data of different wavelengths. By data aggregation, the properties of astronomical objects can be understood comprehensively. Aiming at d...Astronomical cross-matching is a basic method for aggregating the observational data of different wavelengths. By data aggregation, the properties of astronomical objects can be understood comprehensively. Aiming at decreasing the time consumed on I/O operations, several improved methods are introduced, including a processing flow based on the boundary growing model, which can reduce the database query operations; a concept of the biggest growing block and its determination which can improve the performance of task partition and resolve data-sparse problem; and a fast bitwise algorithm to compute the index numbers of the neighboring blocks, which is a significant efficiency guarantee. Experiments show that the methods can effectively speed up cross-matching on both sparse datasets and high-density datasets.展开更多
As the basic problems in seismology, fluid, heat and energy distribution near earthquake sources during earthquake generation have been the leading subjects of concern to seismologists. Currently, more and more resear...As the basic problems in seismology, fluid, heat and energy distribution near earthquake sources during earthquake generation have been the leading subjects of concern to seismologists. Currently, more and more research shows fluid around earthquake source areas, which plays an important role in the process of earthquake preparation and generation. However, there is considerable controversy over the source of fluid in the deep crust. As for the problem of heat around earthquake source areas, different models have been proposed to explain the stress heat flow paradox. Among them, the dynamic weakening model has been thought to be the key to solving the heat flow paradox issue. After large earthquakes, energy distribution is directly related to friction heat. It is of timely and important practical significance to immediately implement deep drilling in-site surveying to gain understanding of fluid, friction heat and energy distribution during earthquake generation. The latest international progress in fluid, heat and energy distribution research has been reviewed in this paper which will bring important inspiration for the understanding of earthquake preparation and occurrence.展开更多
Let G be a weighted hypergraph with edges of size i for i = 1, 2. Let wi denote the total weight of edges of size i and α be the maximum weight of an edge of size 1. We study the following partitioning problem of Bol...Let G be a weighted hypergraph with edges of size i for i = 1, 2. Let wi denote the total weight of edges of size i and α be the maximum weight of an edge of size 1. We study the following partitioning problem of Bollob′as and Scott： Does there exist a bipartition such that each class meets edges of total weight at least （w_1-α）/2＋（2w_2）/3？ We provide an optimal bound for balanced bipartition of weighted hypergraphs, partially establishing this conjecture. For dense graphs, we also give a result for partitions into more than two classes.In particular, it is shown that any graph G with m edges has a partition V_1,..., V_k such that each vertex set meets at least（1-（1-1/k）~2）m ＋ o（m） edges, which answers a related question of Bollobás and Scott.展开更多
基金Projects(61272142,61103082,61003075,61170261,61103193)supported by the National Natural Science Foundation of ChinaProject supported by Funds for New Century Excellent Talents in University of ChinaProjects(2012AA01A301,2012AA010901)supported by the National High Technology Research and Development Program of China
文摘A novel framework for parallel subgraph isomorphism on GPUs is proposed, named GPUSI, which consists of GPU region exploration and GPU subgraph matching. The GPUSI iteratively enumerates subgraph instances and solves the subgraph isomorphism in a divide-and-conquer fashion. The framework completely relies on the graph traversal, and avoids the explicit join operation. Moreover, in order to improve its performance, a task-queue based method and the virtual-CSR graph structure are used to balance the workload among warps, and warp-centric programming model is used to balance the workload among threads in a warp. The prototype of GPUSI is implemented, and comprehensive experiments of various graph isomorphism operations are carried on diverse large graphs. The experiments clearly demonstrate that GPUSI has good scalability and can achieve speed-up of 1.4–2.6 compared to the state-of-the-art solutions.
基金Project(51208261)supported by the National Natural Science Foundation of ChinaProject(12YJCZH062)supported by the Ministry of Education of Humanities and Social Science of ChinaProject(30920140132033)supported by the Fundamental Research Funds for the Central Universities,China
文摘Bicycle-sharing system is considered as a green option to provide a better connection between scenic spots and nearby metro/bus stations. Allocating and optimizing the layout of bicycle-sharing system inside the scenic spot and around its influencing area are focused on. It is found that the terrain, land use, nearby transport network and scenery point distribution have significant impact on the allocation of bicycle-sharing system. While the candidate bicycle-sharing stations installed at the inner scenic points, entrances/exits and metro stations are fixed, the ones installed at bus-stations and other passenger concentration buildings are adjustable. Aiming at minimizing the total cycling distance and overlapping rate, an optimization model is proposed and solved based on the idea of cluster concept and greedy heuristic. A revealed preference/stated preference （RP/SP） combined survey was conducted at Xuanwu Lake in Nanjing, China, to get an insight into the touring trip characteristics and bicycle-sharing tendency. The results reveal that 39.81% visitors accept a cycling distance of 1-3 km and 62.50% respondents think that the bicycle-sharing system should charge an appropriate fee. The sttrvey indicates that there is high possibility to carry out a bicycle-sharing system at Xuanwu Lake. Optimizing the allocation problem cluster by cluster rather than using an exhaustive search method significantly reduces the computing amount from O（2^43） to O（43 2）. The 500 m-radius-coverage rate for the alternative optimized by 500 m-radius-cluster and 800 m-radius-cluster is 89.2% and 68.5%, respectively. The final layout scheme will provide decision makers engineering guidelines and theoretical support.
基金Supported by National Natural Science Foundation of China (No.10978016)Natural Science Foundation of Tianjin (No. 08JCZDJC19700)Key Technologies Research and Development Program of Tianjin (No.09ZCKFGX00400)
文摘Astronomical cross-matching is a basic method for aggregating the observational data of different wavelengths. By data aggregation, the properties of astronomical objects can be understood comprehensively. Aiming at decreasing the time consumed on I/O operations, several improved methods are introduced, including a processing flow based on the boundary growing model, which can reduce the database query operations; a concept of the biggest growing block and its determination which can improve the performance of task partition and resolve data-sparse problem; and a fast bitwise algorithm to compute the index numbers of the neighboring blocks, which is a significant efficiency guarantee. Experiments show that the methods can effectively speed up cross-matching on both sparse datasets and high-density datasets.
基金sponsored by the Special Fund of the"Study on the Science and Technology R&D Program for Earthquake Prediction"of China Earthquake Administration
文摘As the basic problems in seismology, fluid, heat and energy distribution near earthquake sources during earthquake generation have been the leading subjects of concern to seismologists. Currently, more and more research shows fluid around earthquake source areas, which plays an important role in the process of earthquake preparation and generation. However, there is considerable controversy over the source of fluid in the deep crust. As for the problem of heat around earthquake source areas, different models have been proposed to explain the stress heat flow paradox. Among them, the dynamic weakening model has been thought to be the key to solving the heat flow paradox issue. After large earthquakes, energy distribution is directly related to friction heat. It is of timely and important practical significance to immediately implement deep drilling in-site surveying to gain understanding of fluid, friction heat and energy distribution during earthquake generation. The latest international progress in fluid, heat and energy distribution research has been reviewed in this paper which will bring important inspiration for the understanding of earthquake preparation and occurrence.
基金National Natural Science Foundation of China (Grant Nos. 11371355 and 11471193)
文摘Let G be a weighted hypergraph with edges of size i for i = 1, 2. Let wi denote the total weight of edges of size i and α be the maximum weight of an edge of size 1. We study the following partitioning problem of Bollob′as and Scott： Does there exist a bipartition such that each class meets edges of total weight at least （w_1-α）/2＋（2w_2）/3？ We provide an optimal bound for balanced bipartition of weighted hypergraphs, partially establishing this conjecture. For dense graphs, we also give a result for partitions into more than two classes.In particular, it is shown that any graph G with m edges has a partition V_1,..., V_k such that each vertex set meets at least（1-（1-1/k）~2）m ＋ o（m） edges, which answers a related question of Bollobás and Scott.
