Fast Shortest Path Distance Estimation in Large Networks

We study the problem of preprocessing a large graph so that point-to-point shortest-path queries can be answered very fast. Computing shortest paths is a well studied problem, but exact algorithms do not scale to huge graphs encountered on the web, social networks, and other applications. In this paper we focus on approximate methods for distance estimation, in particular using landmark-based distance indexing. This approach involves selecting a subset of nodes as landmarks and computing (offline) the distances from each node in the graph to those landmarks. At runtime, when the distance between a pair of nodes is needed, we can estimate it quickly by combining the precomputed distances of the two nodes to the landmarks. We prove that selecting the optimal set of landmarks is an NP-hard problem, and thus heuristic solutions need to be employed. Given a budget of memory for the index, which translates directly into a budget of landmarks, different landmark selection strategies can yield dramatically different results in terms of accuracy. A number of simple methods that scale well to large graphs are therefore developed and experimentally compared. The simplest methods choose central nodes of the graph, while the more elaborate ones select central nodes that are also far away from one another. The efficiency of the suggested techniques is tested experimentally using five different real world graphs with millions of edges; for a given accuracy, they require as much as 250 times less space than the current approach in the literature which considers selecting landmarks at random. Finally, we study applications of our method in two problems arising naturally in large-scale networks, namely, social search and community detection.

Traveled Distance Estimation Algorithm for Indoor Localization

This paper presents an ankle mounted Inertial Navigation System (INS) used to estimate the distance traveled by a pedestrian. This distance is estimated by the number of steps given by the user. The proposed method is based on force sensors to enhance the results obtained from an INS. Experimental results have shown that, depending on the step frequency, the traveled distance error varies between 2.7% and 5.6%.

Pattern-based phylogenetic distance estimation and tree reconstruction

We have developed an alignment-free method that calculates phylogenetic distances using a maximum-likelihood approach for a model of sequence change on patterns that are discovered in unaligned sequences. To evaluate the phylogenetic accuracy of our method, and to conduct a comprehensive comparison of existing alignment-free methods (freely available as Python package decaf+py at http://www.bioinformatics.org.au), we have created a data set of reference trees covering a wide range of phylogenetic distances. Amino acid sequences were evolved along the trees and input to the tested methods; from their calculated distances we infered trees whose topologies we compared to the reference trees. We find our pattern-based method statistically superior to all other tested alignment-free methods. We also demonstrate the general advantage of alignment-free methods over an approach based on automated alignments when sequences violate the assumption of collinearity. Similarly, we compare methods on empirical data from an existing alignment benchmark set that we used to derive reference distances and trees. Our pattern-based approach yields distances that show a linear relationship to reference distances over a substantially longer range than other alignment-free methods. The pattern-based approach outperforms alignment-free methods and its phylogenetic accuracy is statistically indistinguishable from alignment-based distances.

Comparaisons intersexes dans l'estimation des distances

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Sight distance studies on roads: influence of digital elevation models and roadside elements

Sight distance plays an important role in road traffic safety. Two types of Digital Elevation Models (DEMs) are utilized for the estimation of available sight distance in roads: Digital Terrain Models (DTMs) and Digital Surface Models (DSMs). DTMs, which represent the bare ground surface, are commonly used to determine available sight distance at the design stage. Additionally, the use of DSMs provides further information about elements by the roadsides such as trees, buildings, walls or even traffic signals which may reduce available sight distance. This document analyses the influence of three classes of DEMs in available sight distance estimation. For this purpose, diverse roads within the Region of Madrid (Spain) have been studied using software based on geographic information systems. The study evidences the influence of using each DEM in the outcome as well as the pros and cons of using each model.

"mind the gap": The size-distance dissociation in visual neglect is a cueing effect

There is a growing body of evidence that the processes mediating the allocation of spatial attention within objects may be separable from those governing attentional distribution between objects. In the neglect literature, a related proposal has been made regarding the perception of (within-object) sizes and (between-object) distances. This proposal follows observations that, in size-matching and bisection tasks, neglect is more strongly expressed when patients are required to attend to the sizes of discrete objects than to the (unfilled) distances between objects. These findings are consistent with a partial dissociation between size and distance processing, but a simpler alternative must also be considered. Whilst a neglect patient may fail to explore the full extent of a solid stimulus, the estimation of an unfilled distance requires that both endpoints be inspected before the task can be attempted at all. The attentional cueing implicit in distance estimation tasks might thus account for their superior performance by neglect patients. We report two bisection studies that address this issue. The first confirmed, amongst patients with left visual neglect, a reliable reduction of rightward error for unfilled gap stimuli as compared with solid lines. The second study assessed the cause of this reduction, deconfounding the effects of stimulus type (lines vs. gaps) and attentional cueing, by applying an explicit cueing manipulation to line and gap bisection tasks. Under these matched cueing conditions, all patients performed similarly on line and gap bisection tasks, suggesting that the reduction of neglect typically observed for gap stimuli may be attributable entirely to cueing effects. We found no evidence that a spatial extent, once fully attended, is judged any differently according to whether it is filled or unfilled.

Computer vision onboard UAVs for civilian tasks

Computer vision is much more than a technique to sense and recover environmental information from an UAV. It should play a main role regarding UAVs’ functionality because of the big amount of information that can be extracted, its possible uses and applications, and its natural connection to human driven tasks, taking into account that vision is our main interface to world understanding. Our current research’s focus lays on the development of techniques that allow UAVs to maneuver in spaces using visual information as their main input source. This task involves the creation of techniques that allow an UAV to maneuver towards features of interest whenever a GPS signal is not reliable or sufficient, e.g. when signal dropouts occur (which usually happens in urban areas, when flying through terrestrial urban canyons or when operating on remote planetary bodies), or when tracking or inspecting visual targets—including moving ones—without knowing their exact UMT coordinates. This paper also investigates visual serving control techniques that use velocity and position of suitable image features to compute the references for flight control. This paper aims to give a global view of the main aspects related to the research field of computer vision for UAVs, clustered in four main active research lines: visual serving and control, stereo-based visual navigation, image processing algorithms for detection and tracking, and visual SLAM. Finally, the results of applying these techniques in several applications are presented and discussed: this study will encompass power line inspection, mobile target tracking, stereo distance estimation, mapping and positioning.

Isolation and inheritance of microsatellite loci for the oily bittering (Acheilognathus koreensis): applications for analysis of genetic diversity of wild populations

The oily bittering Acheilognathus koreensis is a freshwater species that is endemic to Korea and is experiencing severe declines in natural populations as a result of habitat fragmentation and water pollution. For the conservation and restoration of this species, it is necessary to assess its genetic diversity at the population level. We developed 13 polymorphic microsatellite loci that were used to analyze the genetic diversity of two populations collected from the Kum River and the Tamjin River in Korea. All loci exhibited Mendelian inheritance patterns when examined in controlled crosses. Both populations revealed high levels of variability, with the number of alleles ranging from 3 to 20 and observed and expected heterozygosities ranging from 0.500 to 0.969 and from 0.529 to 0.938, respectively. None of the loci showed significant deviation from Hardy–Weinberg equilibrium, and one pair of loci showed significant linkage disequilibrium after Bonferroni correction. Pairwise F ST and genetic distance estimation showed significant differences between two populations. These results suggest that the microsatellites developed herein can be used to study the genetic diversity, population structure and conservation measure of A. koreensis.

Indexing Distances in Large Graphs and Applications in Search Tasks

This thesis elaborates on the problem of preprocessing a large graph so that single-pair shortest-path queries can be answered quickly at runtime. Computing shortest paths is a well studied problem, but exact algorithms do not scale well to real-world huge graphs in applications that require very short response time. The focus is on approximate methods for distance estimation, in particular in landmarks-based distance indexing. This approach involves choosing some nodes as landmarks and computing (offline), for each node in the graph its embedding, i.e., the vector of its distances from all the landmarks. At runtime, when the distance between a pair of nodes is queried, it can be quickly estimated by combining the embeddings of the two nodes. Choosing optimal landmarks is shown to be hard and thus heuristic solutions are employed. Given a budget of memory for the index, which translates directly into a budget of landmarks, different landmark selection strategies can yield dramatically different results in terms of accuracy. A number of simple methods that scale well to large graphs are therefore developed and experimentally compared. The simplest methods choose central nodes of the graph, while the more elaborate ones select central nodes that are also far away from one another. The efficiency of the techniques presented in this thesis is tested experimentally using five different real world graphs with millions of edges; for a given accuracy, they require as much as 250 times less space than the current approach which considers selecting landmarks at random. Finally, they are applied in two important problems arising naturally in large-scale graphs, namely social search and community detection.

A Planetary Nebula around Nova V458 Vulpeculae Undergoing Flash Ionization

Nova V458 Vul erupted on 2007 August 8 and reached a visual magnitude of 8.1 a few days later. Ha images obtained 6 weeks before the outburst as part of the IPHAS Galactic plane survey reveal an 18th magnitude progenitor surrounded by an extended nebula. Subsequent images and spectroscopy of the nebula reveal an inner nebular knot increasing rapidly in brightness due to flash ionization by the nova event. We derive a distance of 13 kpc based on light travel time considerations, which is supported by two other distance estimation methods. The nebula has an ionized mass of 0.2 Msolar and a low expansion velocity: this rules it out as ejecta from a previous nova eruption, and is consistent with it being a ~14,000 year old planetary nebula, probably the product of a prior common envelope (CE) phase of evolution of the binary system. The large derived distance means that the mass of the erupting WD component of the binary is high. We identify two possible evolutionary scenarios, in at least one of which the system is massive enough to produce a Type Ia supernova upon merging.

Use of negative information in positioning and tracking algorithms

To avoid additional hardware deployment, indoor localization systems have to be designed in such a way that they rely on existing infrastructure only. Besides the processing of measurements between nodes, localization procedure can include the information of all available environment information. In order to enhance the performance of Wi-Fi based localization systems, the innovative solution presented in this paper considers also the negative information. An indoor tracking method inspired by Kalman filtering is also proposed.

Orientação espacial em pessoas com deficiência visual: um estudo de triangulação por meio de monitoramento remoto

This study was conducted to investigate how visually impaired people perform distance estimation tasks by movement and navigation during deprivation of effective perceptual and proprioceptive information. For that they performed the task of walking three distances, being the first and second of 100 meters and the third of 140 meters (triangulation) from a point of origin in open field on a inverted L shaped trajectory and then returning to the origin. The first and second tasks were driven by means of a guide with GPS adapted to the study coordinates, and the third one was freeform with three sessions, the first without perceptual and proprioceptive restrictions, the second without auditory perception, and the third in a wheelchair, without proprioception. The objective of this study was to indicate the differences in distance reproduction in relation to accuracy and investigate the spatial representation of participants in a navigation task, in which there is active movement, but no effective perceptual and proprioceptive information. Results showed that the average participants underestimated distances producing average angles close to the value of 45°. And by means of the "t" students test no significant differences between subjects can be pointed out. To achieve these results we used remote monitoring by GPS and software TrackMaker.

Type Ia Supernova Cosmology : Quantitative Spectral Analysis

Type Ia supernovae have been successfully used as standardized candles to study the expansion history of the Universe. In the past few years, these studies led to the exciting result of an accelerated expansion caused by the repelling action of some sort of dark energy. This result has been confirmed by measurements of cosmic microwave background radiation, the large-scale structure, and the dynamics of galaxy clusters. The combination of all these experiments points to a “concordance model” of the Universe with flat large-scale geometry and a dominant component of dark energy. However, there are several points related to supernova measurements which need careful analysis in order to doubtlessly establish the validity of the concordance model. As the amount and quality of data increases, the need of controlling possible systematic effects which may bias the results becomes crucial. Also important is the improvement of our knowledge of the physics of supernovae events to assure and possibly refine their calibration as standardized candle. This thesis addresses some of those issues through the quantitative analysis of supernova spectra. The stress is put on a careful treatment of the data and on the definition of spectral measurement methods. The comparison of measurements for a large set of spectra from nearby supernovae is used to study the homogeneity and to search for spectral parameters which may further refine the calibration of the standardized candle. One such parameter is found to reduce the dispersion in the distance estimation of a sample of supernovae to below 6%, a precision which is comparable with the current lightcurve-based calibration, and is obtained in an independent manner. Finally, the comparison of spectral measurements from nearby and distant objects is used to test the possibility of evolution with cosmic time of the intrinsic brightness of type Ia supernovae.