Exploring Bit-Difference for Approximate KNN Search in High-dimensional Databases

In this paper, we develop a novel index structure to support efficient approximate k-nearest neighbor (KNN) query in high-dimensional databases. In high-dimensional spaces, the computational cost of the distance (e.g., Euclidean distance) between two points contributes a dominant portion of the overall query response time for memory processing. To reduce the distance computation, we first propose a structure (BID) using BIt-Difference to answer approximate KNN query. The BID employs one bit to represent each feature vector of point and the number of bit-difference is used to prune the further points. To facilitate real dataset which is typically skewed, we enhance the BID mechanism with clustering, cluster adapted bitcoder and dimensional weight, named the BID⁺. Extensive experiments are conducted to show that our proposed method yields significant performance advantages over the existing index structures on both real life and synthetic high-dimensional datasets.

Scene Classification Using a Hybrid Generative/Discriminative Approach

We investigate whether dimensionality reduction using a latent generative model is beneficial for the task of weakly supervised scene classification. In detail, we are given a set of labeled images of scenes (for example, coast, forest, city, river, etc.), and our objective is to classify a new image into one of these categories. Our approach consists of first discovering latent ";topics"; using probabilistic Latent Semantic Analysis (pLSA), a generative model from the statistical text literature here applied to a bag of visual words representation for each image, and subsequently, training a multiway classifier on the topic distribution vector for each image. We compare this approach to that of representing each image by a bag of visual words vector directly and training a multiway classifier on these vectors. To this end, we introduce a novel vocabulary using dense color SIFT descriptors and then investigate the classification performance under changes in the size of the visual vocabulary, the number of latent topics learned, and the type of discriminative classifier used (k-nearest neighbor or SVM). We achieve superior classification performance to recent publications that have used a bag of visual word representation, in all cases, using the authors' own data sets and testing protocols. We also investigate the gain in adding spatial information. We show applications to image retrieval with relevance feedback and to scene classification in videos

Optimización del sistema de transporte en el colegio The English School

La optimización de sistemas y modelos se ha convertido en uno de los factores más importantes a la hora de buscar la mayor eficiencia de un proceso. Este concepto no es ajeno al transporte escolar, ambiente que cambia constantemente al ritmo de las necesidades de sus clientes, y que responde ante una fuerte responsabilidad frente a sus usuarios, los niños que hacen uso del servicio, en cuanto al cumplimiento de tiempos y seguridad, mientras busca constantemente la reducción de costos. Este proyecto expone las problemáticas presentadas en The English School en esta área y propone un modelo de optimización simple que permitirá notables mejoras en términos de tiempos y costos, de tal forma que genere beneficios para la institución en términos financieros y de satisfacción al cliente. Por medio de la implementación de este modelo será posible identificar errores comunes del proceso, se identificarán soluciones prácticas de fácil aplicación en el manejo del transporte y se presentarán los resultados obtenidos en la muestra utilizada para desarrollar el proyecto.

Evolutionary history of vegetative reproduction in Porpidia s. l. (lichen-forming ascomycota)

The evolutionary history of gains and losses of vegetative reproductive propagules (soredia) in Porpidia s.l., a group of lichen-forming ascomycetes, was clarified using Bayesian Markov chain Monte Carlo (MCMC) approaches to monophyly tests and a combined MCMC and maximum likelihood approach to ancestral character state reconstructions. The MCMC framework provided confidence estimates for the reconstructions of relationships and ancestral character states, which formed the basis for tests of evolutionary hypotheses. Monophyly tests rejected all hypotheses that predicted any clustering of reproductive modes in extant taxa. In addition, a nearest-neighbor statistic could not reject the hypothesis that the vegetative reproductive mode is randomly distributed throughout the group. These results show that transitions between presence and absence of the vegetative reproductive mode within Porpidia s.l. occurred several times and independently of each other. Likelihood reconstructions of ancestral character states at selected nodes suggest that - contrary to previous thought - the ancestor to Porpidia s.l. already possessed the vegetative reproductive mode. Furthermore, transition rates are reconstructed asymmetrically with the vegetative reproductive mode being gained at a much lower rate than it is lost. A cautious note has to be added, because a simulation study showed that the ancestral character state reconstructions were highly dependent on taxon sampling. However, our central conclusions, particularly the higher rate of change from vegetative reproductive mode present to absent than vice versa within Porpidia s.l., were found to be broadly independent of taxon sampling. [Ancestral character state reconstructions; Ascomycota, Bayesian inference; hypothesis testing; likelihood; MCMC; Porpidia; reproductive systems]

Rejoinder to 'Performance of different synchronisation measures in real data: A case study on electroencephalograhic signals

We agree with Duckrow and Albano [Phys. Rev. E 67, 063901 (2003)] and Quian Quiroga et al. [Phys. Rev. E 67, 063902 (2003)] that mutual information (MI) is a useful measure of dependence for electroencephalogram (EEG) data, but we show that the improvement seen in the performance of MI on extracting dependence trends from EEG is more dependent on the type of MI estimator rather than any embedding technique used. In an independent study we conducted in search for an optimal MI estimator, and in particular for EEG applications, we examined the performance of a number of MI estimators on the data set used by Quian Quiroga et al. in their original study, where the performance of different dependence measures on real data was investigated [Phys. Rev. E 65, 041903 (2002)]. We show that for EEG applications the best performance among the investigated estimators is achieved by k-nearest neighbors, which supports the conjecture by Quian Quiroga et al. in Phys. Rev. E 67, 063902 (2003) that the nearest neighbor estimator is the most precise method for estimating MI.

Comment on "Performance of different synchronization measures in real data: A case study on electroencephalographic signals"

We agree with Duckrow and Albano [Phys. Rev. E 67, 063901 (2003)] and Quian Quiroga [Phys. Rev. E 67, 063902 (2003)] that mutual information (MI) is a useful measure of dependence for electroencephalogram (EEG) data, but we show that the improvement seen in the performance of MI on extracting dependence trends from EEG is more dependent on the type of MI estimator rather than any embedding technique used. In an independent study we conducted in search for an optimal MI estimator, and in particular for EEG applications, we examined the performance of a number of MI estimators on the data set used by Quian Quiroga in their original study, where the performance of different dependence measures on real data was investigated [Phys. Rev. E 65, 041903 (2002)]. We show that for EEG applications the best performance among the investigated estimators is achieved by k-nearest neighbors, which supports the conjecture by Quian Quiroga in Phys. Rev. E 67, 063902 (2003) that the nearest neighbor estimator is the most precise method for estimating MI.

Assessment of the RE(OH)3 Ising magnetic materials as possible candidates for the study of transverse-field-induced quantum phase transitions

The LiHoxY1−xF4 Ising magnetic material subject to a magnetic field perpendicular to the Ho3+ Ising direction has shown over the past 20 years to be a host of very interesting thermodynamic and magnetic phenomena. Unfortunately, the availability of other magnetic materials other than LiHoxY1−xF4 that may be described by a transverse-field Ising model remains very much limited. It is in this context that we use here a mean-field theory to investigate the suitability of the Ho(OH)3, Dy(OH)3, and Tb(OH)3 insulating hexagonal dipolar Ising-type ferromagnets for the study of the quantum phase transition induced by a magnetic field, Bx, applied perpendicular to the Ising spin direction. Experimentally, the zero-field critical (Curie) temperatures are known to be Tc≈2.54, 3.48, and 3.72 K, for Ho(OH)3, Dy(OH)3, and Tb(OH)3, respectively. From our calculations we estimate the critical transverse field, Bxc, to destroy ferromagnetic order at zero temperature to be Bxc=4.35, 5.03, and 54.81 T for Ho(OH)3, Dy(OH)3, and Tb(OH)3, respectively. We find that Ho(OH)3, similarly to LiHoF4, can be quantitatively described by an effective S=1/2 transverse-field Ising model. This is not the case for Dy(OH)3 due to the strong admixing between the ground doublet and first excited doublet induced by the dipolar interactions. Furthermore, we find that the paramagnetic (PM) to ferromagnetic (FM) transition in Dy(OH)3 becomes first order for strong Bx and low temperatures. Hence, the PM to FM zero-temperature transition in Dy(OH)3 may be first order and not quantum critical. We investigate the effect of competing antiferromagnetic nearest-neighbor exchange and applied magnetic field, Bz, along the Ising spin direction ẑ on the first-order transition in Dy(OH)3. We conclude from these preliminary calculations that Ho(OH)3 and Dy(OH)3 and their Y3+ diamagnetically diluted variants, HoxY1−x(OH)3 and DyxY1−x(OH)3, are potentially interesting systems to study transverse-field-induced quantum fluctuations effects in hard axis (Ising-type) magnetic materials.

Helium ion microscopy visualizes lipid nanodomains in mammalian cells

Cell membranes are composed of two-dimensional bilayers of amphipathic lipids, which allow a lateral movement of the respective membrane components. These components are arranged in an inhomogeneous manner as transient micro- and nanodomains, which are believed to be crucially involved in the regulation of signal transduction pathways in mammalian cells. Because of their small size (diameter 10-200 nm), membrane nanodomains cannot be directly imaged using conventional light microscopy. Here, we present direct visualization of cell membrane nanodomains by helium ion microscopy (HIM). We show that HIM is capable to image biological specimens without any conductive coating, and that HIM images clearly allow the identification of nanodomains in the ultrastructure of membranes with 1.5 nm resolution. The shape of these nanodomains is preserved by fixation of the surrounding unsaturated fatty acids while saturated fatty acids inside the nanodomains are selectively removed. Atomic force microscopy, fluorescence microscopy, 3D structured illumination microscopy and direct stochastic optical reconstruction microscopy provide additional evidence that the structures in the HIM images of cell membranes originate from membrane nanodomains. The nanodomains observed by HIM have an average diameter of 20 nm and are densely arranged with a minimal nearest neighbor distance of ~15 nm.

Paged similarity queries

An important feature of a database management systems (DBMS) is its client/server architecture, where managing shared memory among the clients and the server is always an tough issue. However, similarity queries are specially sensitive to this kind of architecture, since the answer sizes vary widely. Usually, the answers of similarity query are fully processed to be sent in full to the user, who often is interested in just parts of the answer, e.g. just few elements closer or farther to the query reference. Compelling the DBMS to retrieve the full answer, further ignoring its majority is at least a waste of server processing power. Paging the answer is a technique that splits the answer onto several pages, following client requests. Despite the success of paging on traditional queries, little work has been done to support it in similarity queries. In this work, we present a technique that not only provides paging in similarity range or k-nearest neighbor queries, but also supports them in two variations: the forward similarity query and the backward similarity query. They return elements either increasingly farther of increasingly closer to the query reference. The reported experiments show that, depending on the proportion of the interesting part over the full answer, both techniques allow answering queries much faster than it is obtained in the non-paged way. (C) 2010 Elsevier Inc. All rights reserved.

Clustering and diffusion in a symplectic map lattice with non-local coupling

We study a symplectic chain with a non-local form of coupling by means of a standard map lattice where the interaction strength decreases with the lattice distance as a power-law, in Such a way that one can pass continuously from a local (nearest-neighbor) to a global (mean-field) type of coupling. We investigate the formation of map clusters, or spatially coherent structures generated by the system dynamics. Such clusters are found to be related to stickiness of chaotic phase-space trajectories near periodic island remnants, and also to the behavior of the diffusion coefficient. An approximate two-dimensional map is derived to explain some of the features of this connection. (C) 2008 Elsevier Ltd. All rights reserved.

Lipid bilayer pre-transition as the beginning of the melting process

We investigate the bilayer pre-transition exhibited by some lipids at temperatures below their main phase transition, and which is generally associated to the formation of periodic ripples in the membrane. Experimentally we focus on the anionic lipid dipalmytoylphosphatidylglycerol (DPPG) at different ionic strengths, and on the neutral lipid dipalmytoylphosphatidylcholine (DPPC). From the analysis of differential scanning calorimetry traces of the two lipids we find that both pre- and main transitions are part of the same melting process. Electron spin resonance of spin labels and excitation generalized polarization of Laurdan reveal the coexistence of gel and fluid domains at temperatures between the pre- and main transitions of both lipids, reinforcing the first finding. Also, the melting process of DPPG at low ionic strength is found to be less cooperative than that of DPPC. From the theoretical side, we introduce a statistical model in which a next-nearest-neighbor competing interaction is added to the usual two-state model. For the first time, modulated phases (ordered and disordered lipids periodically aligned) emerge between the gel and fluid phases as a natural consequence of the competition between lipid-lipid interactions. (C) 2009 Elsevier B.V. All rights reserved.

Hydrogen adsorption on boron doped graphene: an ab initio study

(i) The electronic and structural properties of boron doped graphene sheets, and (ii) the chemisorption processes of hydrogen adatoms on the boron doped graphene sheets have been examined by ab initio total energy calculations. In (i) we find that the structural deformations are very localized around the boron substitutional sites, and in accordance with previous studies (Endo et al 2001 J. Appl. Phys. 90 5670) there is an increase of the electronic density of states near the Fermi level. Our simulated scanning tunneling microscope (STM) images, for occupied states, indicate the formation of bright (triangular) spots lying on the substitutional boron (center) and nearest-neighbor carbon (edge) sites. Those STM images are attributed to the increase of the density of states within an energy interval of 0.5 eV below the Fermi level. For a boron concentration of similar to 2.4%, we find that two boron atoms lying on the opposite sites of the same hexagonal ring (B1-B2 configuration) represents the energetically most stable configuration, which is in contrast with previous theoretical findings. Having determined the energetically most stable configuration for substitutional boron atoms on graphene sheets, we next considered the hydrogen adsorption process as a function of the boron concentration, (ii). Our calculated binding energies indicate that the C-H bonds are strengthened near boron substitutional sites. Indeed, the binding energy of hydrogen adatoms forming a dimer-like structure on the boron doped B1-B2 graphene sheet is higher than the binding energy of an isolated H(2) molecule. Since the formation of the H dimer-like structure may represent the initial stage of the hydrogen clustering process on graphene sheets, we can infer that the formation of H clusters is quite likely not only on clean graphene sheets, which is in consonance with previous studies (Hornekaer et al 2006 Phys. Rev. Lett. 97 186102), but also on B1-B2 boron doped graphene sheets. However, for a low concentration of boron atoms, the formation of H dimer structures is not expected to occur near a single substitutional boron site. That is, the formation (or not) of H clusters on graphene sheets can be tuned by the concentration of substitutional boron atoms.

Crystal growth and magnetic properties of tin selenide-doped europium Sn(1-x)Eu(x)Se

The growth and magnetic properties of Tin Selenide (SnSe) doped with Eu(2+) Sn(1-x)Eu(x)Se (x=2.5%) were investigated. Q-band (34 GHz) electron paramagnetic resonance measurements show that the site symmetry of Eu(2+) at 4.2 K is orthorhombic and the Lande factor was determined to be g=1.99 +/- 0.01. The exchange coupling between nearest-neighbor (NN) Eu(2+) ions was estimated from magnetization and magnetic-susceptibility measurements using a model that takes into account the magnetic contributions of single ions, pairs and triplets. The exchange interaction between Eu(2+) nearest neighbors was found to be antiferromagnetic with an estimated average value of J(p)/k(B) =-0.18 +/- 0.03 K. (C) 2009 Elsevier B.V. All rights reserved.

X-ray and gamma irradiation effects on dipole defects in CaF2 : La, Yb, Al

Impurity-interstitial dipoles in calcium fluoride solutions with Al3+, Yb3+ and La3+ fluorides were studied using the thermally stimulated depolarization current (TSDC) technique. The dipolar complexes are formed by substitutional trivalent ions in Ca2+ sites and interstitial fluorine in nearest neighbor sites. The relaxations observed at 150 K are assigned to dipoles nnR(S)(3+)- F-i(-) (R-S = La or Yb). The purpose of this work is to study the processes of energy storage in the fluorides following X-ray and gamma irradiation. Computer modelling techniques are used to obtain the formation energy of dipole defects. (C) 2007 Elsevier Ltd. All rights reserved.

NONHOMOGENEOUS RANDOM WALKS SYSTEMS ON Z

We consider a random walks system on Z in which each active particle performs a nearest-neighbor random walk and activates all inactive particles it encounters. The movement of an active particle stops when it reaches a certain number of jumps without activating any particle. We prove that if the process relies on efficient particles (i.e. those particles with a small probability of jumping to the left) being placed strategically on Z, then it might survive, having active particles at any time with positive probability. On the other hand, we may construct a process that dies out eventually almost surely, even if it relies on efficient particles. That is, we discuss what happens if particles are initially placed very far away from each other or if their probability of jumping to the right tends to I but not fast enough.