惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

J
Java Code Geeks
GbyAI
GbyAI
Google DeepMind News
Google DeepMind News
Jina AI
Jina AI
B
Blog
aimingoo的专栏
aimingoo的专栏
酷 壳 – CoolShell
酷 壳 – CoolShell
T
The Blog of Author Tim Ferriss
Last Week in AI
Last Week in AI
月光博客
月光博客
H
Help Net Security
V
Visual Studio Blog
量子位
A
About on SuperTechFans
博客园 - Franky
人人都是产品经理
人人都是产品经理
N
Netflix TechBlog - Medium
云风的 BLOG
云风的 BLOG
雷峰网
雷峰网
Martin Fowler
Martin Fowler
Microsoft Security Blog
Microsoft Security Blog
博客园 - 叶小钗
P
Proofpoint News Feed
MongoDB | Blog
MongoDB | Blog

cs.DS updates on arXiv.org

PAC Learning with Bandit Feedback: Sharp Sample Complexity in the Realizable Setting Algorithms with Polynomially-Improved Approximation Factors for the $2 \rightarrow q$ Norm, and Applications A computational phase transition for learning-to-sample from Ising models Covering vertices by sequential stars Fermi-Dirac machines as quantizations of neurons A Comprehensive Evaluation of Vertex Elimination Algorithms for Algorithmic Differentiation A Tight Bound on Localization of Electrical Flows Optimal Dimension-Free Sampling for Regularized Classification Reducing the Randomness in Partition Oracles for Bounded Degree Minor-Free Graphs Beyond the Half-Approximation: Fair and Efficient Online Class Matching Efficient Uniform Sampling of Surjections via their Profiles Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth Fairness in Aggregation: Optimal Top-$k$ and Improved Full Ranking Learning-Augmented Online Scheduling with Parsimonious Preemption Entropy Equivalence Testing Lumberjack: Better Differentially Private Random Forests through Heavy Hitter Detection in Trees The Secretary Problem with a Stochastic Precursor Polynomial-Time Robust Multiclass Linear Classification under Gaussian Marginals Efficient Banzhaf-Based Data Valuation for $k$-Nearest Neighbors Classification Block-Sphere Vector Quantization An Approximation Algorithm for Graph Label Selection Iterative Chow Filtering for Learning with Distribution Shift Complexity of Non-Log-Concave Sampling in Fisher Information Stochastic Matching via Local Sparsification Finite Sample Bounds for Learning with Score Matching What is Learnable in Valiant's Theory of the Learnable? Provable Quantization with Randomized Hadamard Transform Min-Max Optimization Requires Exponentially Many Queries Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm A proximal gradient algorithm for composite log-concave sampling
A Watershed Delineation Algorithm for 2D Flow Direction G...
Scott Haag, Ali Shokoufandeh · 2017-08-01 · via cs.DS updates on arXiv.org

In this paper we propose an algorithm and associated data model for creating a watershed boundary using a 2D Flow Direction Grid. Flow Direction Grids (FDGs) are common abstractions for hydrodynamic models and are utilized for delineating physical systems (e.g. watersheds, fluvial, and non-fluvial flow paths). The proposed algorithm and associated data model provides geometric speed increases in watershed boundary retrieval while keeping storage constraints linear in comparison to existing techniques. The algorithm called Haag Shokoufandehs' March (HSM) relies on an existing data structure, the modified nested set model, originally described by Celko and applied to hydrodynamic models by Haag and Shokoufandeh in 2017. The proposed algorithm creates watershed boundaries by marching around the edges of its' corresponding region, never entering the internal area. In contrast to existing algorithms that scales in proportional to the area of the underlying region, the complexity of the HSM algorithm is proportional to the boundary length. Results for a group of tested watersheds (n = 14,718) in the approximately 36,000 km^2 Delaware River Watershed show a reduction of between 0 and 99% in computational complexity using a 30 m DEM vs. existing techniques. Larger watersheds have a consistent reduction in the number of (read) operation complexity, with the largest watershed resulting in approximately 35 million reads using traditional techniques compared to approximately 45 thousand using the HSM algorithm, respectively. Modelled estimates of the complexity for the approximately 6.1 million km^2 Amazon River basin show a reduction from 6.7 billion to 1.4 million reads.