Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPreprocessing power weighted shortest path data using a s-Well Separated Pair Decomposition
55
0
0.0
(
0
)
Added by
Steven Damelin Dr
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
For $s$ $>$ 0, we consider an algorithm that computes all $s$-well separated pairs in certain point sets in $mathbb{R}^{n}$, $n$ $>1$. For an integer $K$ $>1$, we also consider an algorithm that is a permutation of Dijkstras algorithm, that computes $K$-nearest neighbors using a certain power weighted shortest path metric in $mathbb{R}^{n}$, $n$ $>$ $1$. We describe each algorithm and their respective dependencies on the input data. We introduce a way to combine both algorithms into a fused algorithm. Several open problems are given for future research.
rate research
Read More
We describe and provide code and examples for a polygonal edge matching method.
Computing shortest path distances between nodes lies at the heart of many graph algorithms and applications. Traditional exact methods such as breadth-first-search (BFS) do not scale up to contemporary, rapidly evolving todays massive networks. Therefore, it is required to find approximation methods to enable scalable graph processing with a significant speedup. In this paper, we utilize vector embeddings learnt by deep learning techniques to approximate the shortest paths distances in large graphs. We show that a feedforward neural network fed with embeddings can approximate distances with relatively low distortion error. The suggested method is evaluated on the Facebook, BlogCatalog, Youtube and Flickr social networks.
The textit{Multi-Constraint Shortest Path (MCSP)} problem aims to find the shortest path between two nodes in a network subject to a given constraint set. It is typically processed as a textit{skyline path} problem. However, the number of intermediate skyline paths becomes larger as the network size increases and the constraint number grows, which brings about the dramatical growth of computational cost and further makes the existing index-based methods hardly capable of obtaining the complete exact results. In this paper, we propose a novel high-dimensional skyline path concatenation method to avoid the expensive skyline path search, which then supports the efficient construction of hop labeling index for textit{MCSP} queries. Specifically, a set of insightful observations and techniques are proposed to improve the efficiency of concatenating two skyline path set, a textit{n-Cube} technique is designed to prune the concatenation space among multiple hops, and a textit{constraint pruning} method is used to avoid the unnecessary computation. Furthermore, to scale up to larger networks, we propose a novel textit{forest hop labeling} which enables the parallel label construction from different network partitions. Our approach is the first method that can achieve both accuracy and efficiency for textit{MCSP} query answering. Extensive experiments on real-life road networks demonstrate the superiority of our method over the state-of-the-art solutions.
We present a framework to simulate SIR processes on networks using weighted shortest paths. Our framework maps the SIR dynamics to weights assigned to the edges of the network, which can be done for Markovian and non-Markovian processes alike. The weights represent the propagation time between the adjacent nodes for a particular realization. We simulate the dynamics by constructing an ensemble of such realizations, which can be done by using a Markov Chain Monte Carlo method or by direct sampling. The former provides a runtime advantage when realizations from all possible sources are computed as the weighted shortest paths can be re-calculated more efficiently. We apply our framework to three empirical networks and analyze the expected propagation time between all pairs of nodes. Furthermore, we have employed our framework to perform efficient source detection and to improve strategies for time-critical vaccination.
The effectiveness of fingerprint-based authentication systems on good quality fingerprints is established long back. However, the performance of standard fingerprint matching systems on noisy and poor quality fingerprints is far from satisfactory. Towards this, we propose a data uncertainty-based framework which enables the state-of-the-art fingerprint preprocessing models to quantify noise present in the input image and identify fingerprint regions with background noise and poor ridge clarity. Quantification of noise helps the model two folds: firstly, it makes the objective function adaptive to the noise in a particular input fingerprint and consequently, helps to achieve robust performance on noisy and distorted fingerprint regions. Secondly, it provides a noise variance map which indicates noisy pixels in the input fingerprint image. The predicted noise variance map enables the end-users to understand erroneous predictions due to noise present in the input image. Extensive experimental evaluation on 13 publicly available fingerprint databases, across different architectural choices and two fingerprint processing tasks demonstrate effectiveness of the proposed framework.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
