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.

Fast, Reliable Head Tracking under Varying Illumination

An improved technique for 3D head tracking under varying illumination conditions is proposed. The head is modeled as a texture mapped cylinder. Tracking is formulated as an image registration problem in the cylinder's texture map image. To solve the registration problem in the presence of lighting variation and head motion, the residual error of registration is modeled as a linear combination of texture warping templates and orthogonal illumination templates. Fast and stable on-line tracking is then achieved via regularized, weighted least squares minimization of the registration error. The regularization term tends to limit potential ambiguities that arise in the warping and illumination templates. It enables stable tracking over extended sequences. Tracking does not require a precise initial fit of the model; the system is initialized automatically using a simple 2-D face detector. The only assumption is that the target is facing the camera in the first frame of the sequence. The warping templates are computed at the first frame of the sequence. Illumination templates are precomputed off-line over a training set of face images collected under varying lighting conditions. Experiments in tracking are reported.

Fast, Reliable Head Tracking under Varying Illumination: An Approach Based on Registration of Texture-Mapped 3D Model

An improved technique for 3D head tracking under varying illumination conditions is proposed. The head is modeled as a texture mapped cylinder. Tracking is formulated as an image registration problem in the cylinder's texture map image. The resulting dynamic texture map provides a stabilized view of the face that can be used as input to many existing 2D techniques for face recognition, facial expressions analysis, lip reading, and eye tracking. To solve the registration problem in the presence of lighting variation and head motion, the residual error of registration is modeled as a linear combination of texture warping templates and orthogonal illumination templates. Fast and stable on-line tracking is achieved via regularized, weighted least squares minimization of the registration error. The regularization term tends to limit potential ambiguities that arise in the warping and illumination templates. It enables stable tracking over extended sequences. Tracking does not require a precise initial fit of the model; the system is initialized automatically using a simple 2D face detector. The only assumption is that the target is facing the camera in the first frame of the sequence. The formulation is tailored to take advantage of texture mapping hardware available in many workstations, PC's, and game consoles. The non-optimized implementation runs at about 15 frames per second on a SGI O2 graphic workstation. Extensive experiments evaluating the effectiveness of the formulation are reported. The sensitivity of the technique to illumination, regularization parameters, errors in the initial positioning and internal camera parameters are analyzed. Examples and applications of tracking are reported.

Fast Head Tilt Detection for Human-Computer Interaction

Accurate head tilt detection has a large potential to aid people with disabilities in the use of human-computer interfaces and provide universal access to communication software. We show how it can be utilized to tab through links on a web page or control a video game with head motions. It may also be useful as a correction method for currently available video-based assistive technology that requires upright facial poses. Few of the existing computer vision methods that detect head rotations in and out of the image plane with reasonable accuracy can operate within the context of a real-time communication interface because the computational expense that they incur is too great. Our method uses a variety of metrics to obtain a robust head tilt estimate without incurring the computational cost of previous methods. Our system runs in real time on a computer with a 2.53 GHz processor, 256 MB of RAM and an inexpensive webcam, using only 55% of the processor cycles.

Fast Synchronization of Perpetual Grouping in Laminar Visual Cortical Circuits

Perceptual grouping is well-known to be a fundamental process during visual perception, notably grouping across scenic regions that do not receive contrastive visual inputs. Illusory contours are a classical example of such groupings. Recent psychophysical and neurophysiological evidence have shown that the grouping process can facilitate rapid synchronization of the cells that are bound together by a grouping, even when the grouping must be completed across regions that receive no contrastive inputs. Synchronous grouping can hereby bind together different object parts that may have become desynchronized due to a variety of factors, and can enhance the efficiency of cortical transmission. Neural models of perceptual grouping have clarified how such fast synchronization may occur by using bipole grouping cells, whose predicted properties have been supported by psychophysical, anatomical, and neurophysiological experiments. These models have not, however, incorporated some of the realistic constraints on which groupings in the brain are conditioned, notably the measured spatial extent of long-range interactions in layer 2/3 of a grouping network, and realistic synaptic and axonal signaling delays within and across cells in different cortical layers. This work addresses the question: Can long-range interactions that obey the bipole constraint achieve fast synchronization under realistic anatomical and neurophysiological constraints that initially desynchronize grouping signals? Can the cells that synchronize retain their analog sensitivity to changing input amplitudes? Can the grouping process complete and synchronize illusory contours across gaps in bottom-up inputs? Our simulations show that the answer to these questions is Yes.

Grid Cell Hexagonal Patterns Formed by Fast Self-Organized Learning within Entorhinal Cortex

Grid cells in the dorsal segment of the medial entorhinal cortex (dMEC) show remarkable hexagonal activity patterns, at multiple spatial scales, during spatial navigation. How these hexagonal patterns arise has excited intense interest. It has previously been shown how a selforganizing map can convert firing patterns across entorhinal grid cells into hippocampal place cells that are capable of representing much larger spatial scales. Can grid cell firing fields also arise during navigation through learning within a self-organizing map? A neural model is proposed that converts path integration signals into hexagonal grid cell patterns of multiple scales. This GRID model creates only grid cell patterns with the observed hexagonal structure, predicts how these hexagonal patterns can be learned from experience, and can process biologically plausible neural input and output signals during navigation. These results support a unified computational framework for explaining how entorhinal-hippocampal interactions support spatial navigation.

Statistical Properties of Single and Competing Non-Linear Fast-Slow Oscillators in Noise

Statistical properties offast-slow Ellias-Grossberg oscillators are studied in response to deterministic and noisy inputs. Oscillatory responses remain stable in noise due to the slow inhibitory variable, which establishes an adaptation level that centers the oscillatory responses of the fast excitatory variable to deterministic and noisy inputs. Competitive interactions between oscillators improve the stability in noise. Although individual oscillation amplitudes decrease with input amplitude, the average to'tal activity increases with input amplitude, thereby suggesting that oscillator output is evaluated by a slow process at downstream network sites.

A Fast BCS/FCS Algorithm for Image Segmentation

A fast and efficient segmentation algorithm based on the Boundary Contour System/Feature Contour System (BCS/FCS) of Grossberg and Mingolla [3] is presented. This implementation is based on the FFT algorithm and the parallelism of the system.

Fast Learning VIEWNET Architectures for Recognizing 3-D Objects from Multiple 2-D Views

The recognition of 3-D objects from sequences of their 2-D views is modeled by a family of self-organizing neural architectures, called VIEWNET, that use View Information Encoded With NETworks. VIEWNET incorporates a preprocessor that generates a compressed but 2-D invariant representation of an image, a supervised incremental learning system that classifies the preprocessed representations into 2-D view categories whose outputs arc combined into 3-D invariant object categories, and a working memory that makes a 3-D object prediction by accumulating evidence from 3-D object category nodes as multiple 2-D views are experienced. The simplest VIEWNET achieves high recognition scores without the need to explicitly code the temporal order of 2-D views in working memory. Working memories are also discussed that save memory resources by implicitly coding temporal order in terms of the relative activity of 2-D view category nodes, rather than as explicit 2-D view transitions. Variants of the VIEWNET architecture may also be used for scene understanding by using a preprocessor and classifier that can determine both What objects are in a scene and Where they are located. The present VIEWNET preprocessor includes the CORT-X 2 filter, which discounts the illuminant, regularizes and completes figural boundaries, and suppresses image noise. This boundary segmentation is rendered invariant under 2-D translation, rotation, and dilation by use of a log-polar transform. The invariant spectra undergo Gaussian coarse coding to further reduce noise and 3-D foreshortening effects, and to increase generalization. These compressed codes are input into the classifier, a supervised learning system based on the fuzzy ARTMAP algorithm. Fuzzy ARTMAP learns 2-D view categories that are invariant under 2-D image translation, rotation, and dilation as well as 3-D image transformations that do not cause a predictive error. Evidence from sequence of 2-D view categories converges at 3-D object nodes that generate a response invariant under changes of 2-D view. These 3-D object nodes input to a working memory that accumulates evidence over time to improve object recognition. ln the simplest working memory, each occurrence (nonoccurrence) of a 2-D view category increases (decreases) the corresponding node's activity in working memory. The maximally active node is used to predict the 3-D object. Recognition is studied with noisy and clean image using slow and fast learning. Slow learning at the fuzzy ARTMAP map field is adapted to learn the conditional probability of the 3-D object given the selected 2-D view category. VIEWNET is demonstrated on an MIT Lincoln Laboratory database of l28x128 2-D views of aircraft with and without additive noise. A recognition rate of up to 90% is achieved with one 2-D view and of up to 98.5% correct with three 2-D views. The properties of 2-D view and 3-D object category nodes are compared with those of cells in monkey inferotemporal cortex.

Fuzzy ART: Fast Stable Learning and Categorization of Analog Patterns by an Adaptive Resonance System

A Fuzzy ART model capable of rapid stable learning of recognition categories in response to arbitrary sequences of analog or binary input patterns is described. Fuzzy ART incorporates computations from fuzzy set theory into the ART 1 neural network, which learns to categorize only binary input patterns. The generalization to learning both analog and binary input patterns is achieved by replacing appearances of the intersection operator (n) in AHT 1 by the MIN operator (Λ) of fuzzy set theory. The MIN operator reduces to the intersection operator in the binary case. Category proliferation is prevented by normalizing input vectors at a preprocessing stage. A normalization procedure called complement coding leads to a symmetric theory in which the MIN operator (Λ) and the MAX operator (v) of fuzzy set theory play complementary roles. Complement coding uses on-cells and off-cells to represent the input pattern, and preserves individual feature amplitudes while normalizing the total on-cell/off-cell vector. Learning is stable because all adaptive weights can only decrease in time. Decreasing weights correspond to increasing sizes of category "boxes". Smaller vigilance values lead to larger category boxes. Learning stops when the input space is covered by boxes. With fast learning and a finite input set of arbitrary size and composition, learning stabilizes after just one presentation of each input pattern. A fast-commit slow-recode option combines fast learning with a forgetting rule that buffers system memory against noise. Using this option, rare events can be rapidly learned, yet previously learned memories are not rapidly erased in response to statistically unreliable input fluctuations.

Adaptive Resonance Associative Map: A Hierarchical ART System for Fast Stable Associative Learning

This paper introduces a new class of predictive ART architectures, called Adaptive Resonance Associative Map (ARAM) which performs rapid, yet stable heteroassociative learning in real time environment. ARAM can be visualized as two ART modules sharing a single recognition code layer. The unit for recruiting a recognition code is a pattern pair. Code stabilization is ensured by restricting coding to states where resonances are reached in both modules. Simulation results have shown that ARAM is capable of self-stabilizing association of arbitrary pattern pairs of arbitrary complexity appearing in arbitrary sequence by fast learning in real time environment. Due to the symmetrical network structure, associative recall can be performed in both directions.

Rapid separation of biologically important low molecular weight compounds by microchip electrophoresis and ultra-fast performance liquid chromatography

The research work in this thesis reports rapid separation of biologically important low molecular weight compounds by microchip electrophoresis and ultrahigh liquid chromatography. Chapter 1 introduces the theory and principles behind capillary electrophoresis separation. An overview of the history, different modes and detection techniques coupled to CE is provided. The advantages of microchip electrophoresis are highlighted. Some aspects of metal complex analysis by capillary electrophoresis are described. Finally, the theory and different modes of the liquid chromatography technology are presented. Chapter 2 outlines the development of a method for the capillary electrophoresis of (R, S) Naproxen. Variable parameters of the separation were optimized (i.e. buffer concentration and pH, concentration of chiral selector additives, applied voltage and injection condition).The method was validated in terms of linearity, precision, and LOD. The optimized method was then transferred to a microchip electrophoresis system. Two different types of injection i.e. gated and pinched, were investigated. This microchip method represents the fastest reported chiral separation of Naproxen to date. Chapter 3 reports ultra-fast separation of aromatic amino acid by capillary electrophoresis using the short-end technique. Variable parameters of the separation were optimized and validated. The optimized method was then transferred to a microchip electrophoresis system where the separation time was further reduced. Chapter 4 outlines the use of microchip electrophoresis as an efficient tool for analysis of aluminium complexes. A 2.5 cm channel with linear imaging UV detection was used to separate and detect aluminium-dopamine complex and free dopamine. For the first time, a baseline, separation of aluminium dopamine was achieved on a 15 seconds timescale. Chapter 5 investigates a rapid, ultra-sensitive and highly efficient method for quantification of histamine in human psoriatic plaques using microdialysis and ultrahigh performance liquid chromatography with fluorescence detection. The method utilized a sub-two-micron packed C18 stationary phase. A fluorescent reagent, 4-(1-pyrene) butyric acid N-hydroxysuccinimide ester was conjugated to the primary and secondary amino moieties of histamine. The dipyrene-labeled histamine in human urine was also investigated by ultrahigh pressure liquid chromatography using a C18 column with 1.8 μm particle diameter. These methods represent one of the fastest reported separations to date of histamine using fluorescence detection.

Synthesis, functionalisation and characterisation of germanium nanocrystals & their applications

In the last two decades, semiconductor nanocrystals have been the focus of intense research due to their size dependant optical and electrical properties. Much is now known about how to control their size, shape, composition and surface chemistry, allowing fine control of their photophysical and electronic properties. However, genuine concerns have been raised regarding the heavy metal content of these materials, which is toxic even at relatively low concentrations and may limit their wide scale use. These concerns have driven the development of heavy metal free alternatives. In recent years, germanium nanocrystals (Ge NCs) have emerged as environmentally friendlier alternatives to II-VI and IV-VI semiconductor materials as they are nontoxic, biocompatible and electrochemically stable. This thesis reports the synthesis and characterisation of Ge NCs and their application as fluorescence probes for the detection of metal ions. A room-temperature method for the synthesis of size monodisperse Ge NCs within inverse micelles is reported, with well-defined core diameters that may be tuned from 3.5 to 4.5 nm. The Ge NCs are chemically passivated with amine ligands, minimising surface oxidation while rendering the NCs dispersible in a range of polar solvents. Regulation of the Ge NCs size is achieved by variation of the ammonium salts used to form the micelles. A maximum quantum yield of 20% is shown for the nanocrystals, and a transition from primarily blue to green emission is observed as the NC diameter increases from 3.5 to 4.5 nm. A polydisperse sample with a mixed emission profile is prepared and separated by centrifugation into individual sized NCs which each showed blue and green emission only, with total suppression of other emission colours. A new, efficient one step synthesis of Ge NCs with in situ passivation and straightforward purification steps is also reported. Ge NCs are formed by co-reduction of a mixture of GeCl4 and n-butyltrichlorogermane; the latter is used both as a capping ligand and a germanium source. The surface-bound layer of butyl chains both chemically passivates and stabilises the Ge NCs. Optical spectroscopy confirmed that these NCs are in the strong quantum confinement regime, with significant involvement of surface species in exciton recombination processes. The PL QY is determined to be 37 %, one of the highest values reported for organically terminated Ge NCs. A synthetic method is developed to produce size monodisperse Ge NCs with modified surface chemistries bearing carboxylic acid, acetate, amine and epoxy functional groups. The effect of these different surface terminations on the optical properties of the NCs is also studied. Comparison of the emission properties of these Ge NCs showed that the wavelength position of the PL maxima could be moved from the UV to the blue/green by choice of the appropriate surface group. We also report the application of water-soluble Ge NCs as a fluorescent sensing platform for the fast, highly selective and sensitive detection of Fe3+ ions. The luminescence quenching mechanism is confirmed by lifetime and absorbance spectroscopies, while the applicability of this assay for detection of Fe3+ in real water samples is investigated and found to satisfy the US Environmental Protection Agency requirements for Fe3+ levels in drinkable water supplies.

Ferrochelatase is a conserved downstream target of the blue light-sensing White collar complex in fungi.

Light is a universal signal perceived by organisms, including fungi, in which light regulates common and unique biological processes depending on the species. Previous research has established that conserved proteins, originally called White collar 1 and 2 from the ascomycete Neurospora crassa, regulate UV/blue light sensing. Homologous proteins function in distant relatives of N. crassa, including the basidiomycetes and zygomycetes, which diverged as long as a billion years ago. Here we conducted microarray experiments on the basidiomycete fungus Cryptococcus neoformans to identify light-regulated genes. Surprisingly, only a single gene was induced by light above the commonly used twofold threshold. This gene, HEM15, is predicted to encode a ferrochelatase that catalyses the final step in haem biosynthesis from highly photoreactive porphyrins. The C. neoformans gene complements a Saccharomyces cerevisiae hem15Delta strain and is essential for viability, and the Hem15 protein localizes to mitochondria, three lines of evidence that the gene encodes ferrochelatase. Regulation of HEM15 by light suggests a mechanism by which bwc1/bwc2 mutants are photosensitive and exhibit reduced virulence. We show that ferrochelatase is also light-regulated in a white collar-dependent fashion in N. crassa and the zygomycete Phycomyces blakesleeanus, indicating that ferrochelatase is an ancient target of photoregulation in the fungal kingdom.

High-fidelity, broadband stimulated-Brillouin-scattering-based slow light using fast noise modulation.

We demonstrate a 5-GHz-broadband tunable slow-light device based on stimulated Brillouin scattering in a standard highly-nonlinear optical fiber pumped by a noise-current-modulated laser beam. The noisemodulation waveform uses an optimized pseudo-random distribution of the laser drive voltage to obtain an optimal flat-topped gain profile, which minimizes the pulse distortion and maximizes pulse delay for a given pump power. In comparison with a previous slow-modulation method, eye-diagram and signal-to-noise ratio (SNR) analysis show that this broadband slow-light technique significantly increases the fidelity of a delayed data sequence, while maintaining the delay performance. A fractional delay of 0.81 with a SNR of 5.2 is achieved at the pump power of 350 mW using a 2-km-long highly nonlinear fiber with the fast noise-modulation method, demonstrating a 50% increase in eye-opening and a 36% increase in SNR in the comparison.