Algorithms for Grey-Weighted Distance Computations
With the increasing size of datasets and demand for real time response for interactive applications, improving runtime for algorithms with excessive computational requirements has become increasingly important. Many different algorithms combining efficient priority queues with various helper structures have been proposed for computing grey-weighted distance transforms. Here we compare the performance of popular competitive algorithms in different scenarios to form practical guidelines easy to adopt. The label-setting category of algorithms is shown to be the best choice for all scenarios. The hierarchical heap with a pointer array to keep track of nodes on the heap is shown to be the best choice as priority queue. However, if memory is a critical issue, then the best choice is the Dial priority queue for integer valued costs and the Untidy priority queue for real valued costs.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Missing Data Imputation for Classification Problems
Imputation of missing data is a common application in various classification problems where the feature training matrix has missingness. A widely used solution to this imputation problem is based on the lazy learning tec…
ClassificationGeneral ClassificationImputationAverage Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees
The average distance from a node to all other nodes in a graph, or from a query point in a metric space to a set of points, is a fundamental quantity in data analysis. The inverse of the average distance, known as the (c…
Efficient Gradient Computation for Structured Output Learning with Rational and Tropical Losses
Many structured prediction problems admit a natural loss function for evaluation such as the edit-distance or $n$-gram loss. However, existing learning algorithms are typically designed to optimize alternative objectives…
Structured PredictionEstimation of intrinsic volumes from digital grey-scale images
Local algorithms are common tools for estimating intrinsic volumes from black-and-white digital images. However, these algorithms are typically biased in the design based setting, even when the resolution tends to infini…
Adaptive Estimation for Approximate k-Nearest-Neighbor Computations
Algorithms often carry out equally many computations for "easy" and "hard" problem instances. In particular, algorithms for finding nearest neighbors typically have the same running time regardless of the particular prob…