检索结果-内蒙古大学图书馆

Dynamic reserve design with the union-find algorithm

ECOLOGICAL MODELLING 2008年第4期215卷 369-376页

作者： Harrison, Paul Spring, Daniel MacKenzie, Michael Mac Nally, Ralph Monash Univ Australian Ctr Biodivers Sch Biol Sci Clayton Vic 3800 Australia Monash Univ Victorian Bioinformat Consortium Clayton Vic 3800 Australia RMIT Univ Sch Econ Finance & Mkt Fac Business Melbourne Vic 3000 Australia

When reserve networks are established over time, there is a risk that sites will be developed in areas planned for future reservation, reducing the effectiveness of reserves. We developed a dynamic reserve design model that maximizes the expected number of species conserved, taking account of the risk of future habitat loss and fragmentation. The model makes use of the union-find algorithm, which is an efficient method for maintaining a list of connected regions in a graph as nodes and edges are inserted. A simple extension of the algorithm allows us to efficiently determine, for each species, when a sequence of site selections results in a reserve in which the species can persist. The extension also allows us to determine when a sequence of deforestation events results in the species becoming non-viable. The dynamic reserve design model is much more effective than commonly used heuristics, particularly when multiple connected sites are required for species persistence. The model also is able to solve much larger problems with greater effectiveness than the only previous dynamic reserve design model that considered site connectivity relationships. The union-find algorithm has much scope for addressing ecological management problems in which dynamic connectivity needs to be considered. (C) 2008 Elsevier B.V All rights reserved.

关键词： dynamic reserve design union-find algorithm connectivity graph theory

来源：评论

学校读者我要写书评

暂无评论

Grid-based DBSCAN: Indexing and inference

引用

PATTERN RECOGNITION 2019年 90卷 271-284页

作者： Boonchoo, Thapana Ao, Xiang Liu, Yang Zhao, Weizhong Zhuang, Fuzhen He, Qing Chinese Acad Sci Inst Comp Technol Key Lab Intelligent Informat Proc Beijing 100190 Peoples R China Univ Chinese Acad Sci Beijing 100049 Peoples R China Cent China Normal Univ Sch Comp Wuhan Hubei Peoples R China Cent China Normal Univ Hubei Key Lab Artificial Intelligence & Smart Lea Wuhan Hubei Peoples R China

DBSCAN is one of clustering algorithms which can report arbitrarily-shaped clusters and noises without requiring the number of clusters as a parameter (unlike the other clustering algorithms, k-means, for example). Because the running time of DBSCAN has quadratic order of growth, i.e. O(n(2)), research studies on improving its performance have been received a considerable amount of attention for decades. Grid-based DBSCAN is a well-developed algorithm whose complexity is improved to O(nlog n) in 2D space, while requiring Omega(n(4/3)) to solve when dimension >= 3. However, we find that Grid-based DBSCAN suffers from two problems: neighbour explosion and redundancies in merging, which make the algorithms infeasible in high dimensional space. In this paper we first propose a novel algorithm called GDCF which utilizes bitmap indexing to support efficient neighbour grid queries. Second, based on the concept of union-find algorithm we devise a forest-like structure, called cluster forest, to alleviate the redundancies in the merging. Moreover, we find that running the cluster forest in different orders can lead to a different number of merging operations needed to perform in the merging step. We propose to perform the merging step in a uniform random order to optimize the number of merging operations. However, for high-density database, a bottleneck could be occurred, we further propose a low-density-first order to alleviate this bottleneck. The experiments resulted on both real-world and synthetic datasets demonstrate that the proposed algorithm outperforms the state-of-the-art exact/approximate DBSCAN and suggests a good scalability. (C) 2019 Elsevier Ltd. All rights reserved.

关键词： Density-based clustering Grid-based DBSCAN union-find algorithm

来源：评论

学校读者我要写书评

暂无评论

A parallel algorithm for three-dimensional numerical manifold elements generation

引用

ENGINEERING ANALYSIS WITH BOUNDARY ELEMENTS 2024年 163卷 448-464页

作者： Yi, Xiongwei Tan, Fei Tong, Defu Jiao, Yuyong China Univ Geosci Badong Natl Observat & Res Stn Geohazards Wuhan 430074 Peoples R China China Univ Geosci Fac Engn Wuhan 430074 Peoples R China

Numerical Manifold Method (NMM) has gained widespread application in engineering practice due to its capacity to effectively address both continuous and discontinuous problems in a unified framework. With the advancement of 3D-NMM, there remains a deficiency in ready-made preprocessing tools. Hence, the generation of 3D manifold elements (MEs) is the primary prerequisite for 3D-NMM. In this study, a parallel algorithm to generate the MEs is proposed. Firstly, a novel 3D block identification algorithm is developed to improve the modeling efficiency. Then, 3D joint networks are simulated using the geological statistical results. Thirdly, the mathematical cover system is constructed using uniformly regular hexahedral meshes. Subsequently, the physical domain is cut using the Boolean algorithm to generate the related manifold blocks (MBs) and the union -find algorithm is used to determine the relationship of MBs with mathematical patches (MPs) and physical patches (PPs). The proposed program incorporates the OpenMP parallel library for CPU parallelization to enhance its efficiency and the OpenGL library is used to build a real-time visualization program. Finally, the proposed program is validated using several representative examples, and the obtained results demonstrate its efficient capability in generating MEs.

关键词： 3D numerical manifold method Block identification Parallel algorithm Manifold elements union-find algorithm

来源：评论

学校读者我要写书评

暂无评论

Optimal union-find in Constraint Handling Rules

引用

THEORY AND PRACTICE OF LOGIC PROGRAMMING 2006年第1-2期6卷 213-224页

作者： Schrijvers, T Frühwirth, T Katholieke Univ Leuven Dept Comp Sci Louvain Belgium Univ Ulm Fac Comp Sci D-89069 Ulm Germany

Constraint Handling Rules (CHR) is a committed-choice rule-based language that was originally intended for writing constraint solvers. In this paper we show that it is also possible to write the classic union-find algorithm and variants in CHR. The programs neither compromise in declarativeness nor efficiency. We study the time complexity of our programs: they match the almost-linear complexity of the best known imperative implementations. This fact is illustrated with experimental results.

关键词： declarative algorithms time complexity analysis disjoint-set problem union-find algorithm constraint handling rules

来源：评论

学校读者我要写书评

暂无评论

Optimizing two-pass connected-component labeling algorithms

引用

PATTERN ANALYSIS AND APPLICATIONS 2009年第2期12卷 117-135页

作者： Wu, Kesheng Otoo, Ekow Suzuki, Kenji Univ Calif Berkeley Lawrence Berkeley Natl Lab Berkeley CA 94720 USA Univ Chicago Dept Radiol Chicago IL 60637 USA

We present two optimization strategies to improve connected-component labeling algorithms. Taking together, they form an efficient two-pass labeling algorithm that is fast and theoretically optimal. The first optimization strategy reduces the number of neighboring pixels accessed through the use of a decision tree, and the second one streamlines the union-find algorithms used to track equivalent labels. We show that the first strategy reduces the average number of neighbors accessed by a factor of about 2. We prove our streamlined union-find algorithms have the same theoretical optimality as the more sophisticated ones in literature. This result generalizes an earlier one on using union-find in labeling algorithms by Fiorio and Gustedt (Theor Comput Sci 154(2):165-181, 1996). In tests, the new union-find algorithms improve a labeling algorithm by a factor of 4 or more. Through analyses and experiments, we demonstrate that our new two-pass labeling algorithm scales linearly with the number of pixels in the image, which is optimal in computational complexity theory. Furthermore, the new labeling algorithm outperforms the published labeling algorithms irrespective of test platforms. In comparing with the fastest known labeling algorithm for two-dimensional (2D) binary images called contour tracing algorithm, our new labeling algorithm is up to ten times faster than the contour tracing program distributed by the original authors.

关键词： Connected-component labeling Optimization union-find algorithm Decision tree Equivalence relation

来源：评论

学校读者我要写书评

暂无评论

Building a Regionally Connected Reserve Network in a Changing and Uncertain World

引用

CONSERVATION BIOLOGY 2010年第3期24卷 691-700页

作者： Spring, Daniel Baum, Jiri Mac Nally, Ralph MacKenzie, Michael Sanchez-Azofeifa, A. Thomson, James R. Monash Univ Sch Biol Sci Australian Ctr Biodivers Clayton Vic 3800 Australia RMIT Univ Fac Business Sch Econ Finance & Mkt Melbourne Vic 3000 Australia Univ Alberta Earth Observat Syst Lab Dept Earth & Atmospher Sci Edmonton AB T6G 2E3 Canada

Habitat connectivity is required at large spatial scales to facilitate movement of biota in response to climatic changes and to maintain viable populations of wide-ranging species. Nevertheless, it may require decades to acquire habitat linkages at such scales, and areas that could provide linkages are often developed before they can be reserved. Reserve scheduling methods usually consider only current threats, but threats change over time as development spreads and reaches presently secure areas. We investigated the importance of considering future threats when implementing projects to maintain habitat connectivity at a regional scale. To do so, we compared forward-looking scheduling strategies with strategies that consider only current threats. The strategies were applied to a Costa Rican case study, where many reserves face imminent isolation and other reserves will probably become isolated in the more distant future. We evaluated strategies in terms of two landscape-scale connectivity metrics, a pure connectivity metric and a metric of connected habitat diversity. Those strategies that considered only current threats were unreliable because they often failed to complete planned habitat linkage projects. The most reliable and effective strategies considered the future spread of development and its impact on the likelihood of completing planned habitat linkage projects. Our analyses highlight the critical need to consider future threats when building connected reserve networks over time.

关键词： connectivity dynamic reserve design graph theory union-find algorithm

来源：评论

学校读者我要写书评

暂无评论

Novel Fast and Scalable Parallel union-find ASIC Implementation For Real-Time Digital Image Segmentation 41

Novel Fast and Scalable Parallel Union-Find ASIC Implementat...

引用

41st Annual Conference of the IEEE-Industrial-Electronics-Society (IECON)

作者： Salahat, Ehab Saleh, Hani Sluzek, Andrzej Al-Qutayri, Mahmoud Mohammad, Baker Ismail, Mohammad Khalifa Univ Dept Elect & Comp Engn Abu Dhabi U Arab Emirates

ISBN: (纸本)9781479917624

This paper presents a new fast and scalable Parallel union-find algorithm for image segmentation and its System-on-Chip (SoC) implementation using 65nm CMOS technology following the Application-Specific Integrated Circuit (ASIC) design flow. The algorithm is capable of labeling all foreground and background pixels, using the least possible pixels scanning. This contrasts the classical labeling algorithms that label only foreground (or background) pixels in a single run. The new algorithm utilizes only two memory blocks. In one memory block, it labels image segments using their seeds as the label and, simultaneously, the segments sizes are used as the other label in second memory block. By this parallel labeling, monitoring the image segments is very fast and efficient. With 350 MHz operating frequency, the processing rate estimated to be 2100 frames/sec, the total chip area of 15950.5 mu m(2) (off-chip memory) and very low-power of 0.3 mW, the SoC tends to be an excellent candidate for mobile devices and real-time applications.

关键词： Parallel Labeling union-find algorithm ASIC SoC Segmentation Low-power Real-time

来源：评论

学校读者我要写书评

暂无评论

PARDICLE: Parallel Approximate Density-based Clustering 14

PARDICLE: Parallel Approximate Density-based Clustering

引用

International Conference on High Performance Computing, Networking, Storage and Analysis

作者： Patwary, Md. Mostofa Ali Satish, Nadathur Sundaram, Narayanan Manne, Fredrik Habib, Salman Dubey, Pradeep Intel Parallel Comp Lab Santa Clara CA 95052 USA Univ Bergen N-5020 Bergen Norway Argonne Natl Lab Argonne IL 60439 USA

ISBN: (纸本)9781479955008

DBSCAN is a widely used isodensity-based clustering algorithm for particle data well-known for its ability to isolate arbitrarily-shaped clusters and to filter noise data. The algorithm is super-linear (O(nlogn)) and computationally expensive for large datasets. Given the need for speed, we propose a fast heuristic algorithm for DBSCAN using density based sampling, which performs equally well in quality compared to exact algorithms, but is more than an order of magnitude faster. Our experiments on astrophysics and synthetic massive datasets (8.5 billion numbers) shows that our approximate algorithm is up to 56x faster than exact algorithms with almost identical quality (Omega-Index >= 0.99). We develop a new parallel DBSCAN algorithm, which uses dynamic partitioning to improve load balancing and locality. We demonstrate near-linear speedup on shared memory (15x using 16 cores, single node Intel (R) Xeon (R) processor) and distributed memory (3917x using 4096 cores, multinode) computers, with 2x additional performance improvement using Intel (R) Xeon Phi (TM) coprocessors. Additionally, existing exact algorithms can achieve up to 3.4 times speedup using dynamic partitioning.

关键词： Density based clustering approximate clustering algorithm union-find algorithm Disjoint-set data structure

来源：评论

学校读者我要写书评

暂无评论

Scalable Parallel OPTICS Data Clustering Using Graph algorithmic Techniques 13

Scalable Parallel OPTICS Data Clustering Using Graph Algorit...

引用

International Conference for High Performance Computing, Networking, Storage and Analysis (SC)

作者： Patwary, Md Mostofa Ali Palsetia, Diana Agrawal, Ankit Liao, Wei-keng Manne, Fredrik Choudhary, Alok Northwestern Univ Evanston IL 60208 USA Univ Bergen N-5020 Bergen Norway

ISBN: (纸本)9781450323789

OPTICS is a hierarchical density-based data clustering algorithm that discovers arbitrary-shaped clusters and eliminates noise using adjustable reachability distance thresholds. Parallelizing OPTICS is considered challenging as the algorithm exhibits a strongly sequential data access order. We present a scalable parallel OPTICS algorithm (POPTICS) designed using graph algorithmic concepts. To break the data access sequentiality, POPTICS exploits the similarities between the OPTICS algorithm and PRIM'S Minimum Spanning Tree algorithm. Additionally, we use the disjoint-set data structure to achieve a high parallelism for distributed cluster extraction. Using high dimensional datasets containing up to a billion floating point numbers, we show scalable speedups of up to 27.5 for our OpenMP implementation on a 40-core shared-memory machine, and up to 3,008 for our MPI implementation on a 4,096-core distributed-memory machine. We also show that the quality of the results given by POPTICS is comparable to those given by the classical OPTICS algorithm.

关键词： Density-based clustering Minimum spanning tree union-find algorithm Disjoint-set data structure

来源：评论

学校读者我要写书评

暂无评论

A New Scalable Parallel DBSCAN algorithm Using the Disjoint-Set Data Structure

A New Scalable Parallel DBSCAN Algorithm Using the Disjoint-...

引用

25th ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis (SC)

作者： Patwary, Md. Mostofa Ali Palsetia, Diana Agrawal, Ankit Liao, Wei-keng Manne, Fredrik Choudhary, Alok Northwestern Univ Evanston IL 60208 USA Univ Bergen N-5020 Bergen Norway

ISBN: (纸本)9781467308052;9781467308045

DBSCAN is a well-known density based clustering algorithm capable of discovering arbitrary shaped clusters and eliminating noise data. However, parallelization of DBSCAN is challenging as it exhibits an inherent sequential data access order. Moreover, existing parallel implementations adopt a master-slave strategy which can easily cause an unbalanced workload and hence result in low parallel efficiency. We present a new parallel DBSCAN algorithm (PDSDBSCAN) using graph algorithmic concepts. More specifically, we employ the disjoint-set data structure to break the access sequentiality of DBSCAN. In addition, we use a tree-based bottom-up approach to construct the clusters. This yields a better-balanced workload distribution. We implement the algorithm both for shared and for distributed memory. Using data sets containing up to several hundred million high-dimensional points, we show that PDSDBSCAN significantly outperforms the master-slave approach, achieving speedups up to 25.97 using 40 cores on shared memory architecture, and speedups up to 5,765 using 8,192 cores on distributed memory architecture.

关键词： Density based clustering union-find algorithm Disjoint-set data structure

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：