An empirical study of Hoelfding Racing for model selction in K-nearest neighbor classification

Racing algorithms have recently been proposed as a general-purpose method for performing model selection in machine teaming algorithms. In this paper, we present an empirical study of the Hoeffding racing algorithm for selecting the k parameter in a simple k-nearest neighbor classifier. Fifteen widely-used classification datasets from UCI are used and experiments conducted across different confidence levels for racing. The results reveal a significant amount of sensitivity of the k-nn classifier to its model parameter value. The Hoeffding racing algorithm also varies widely in its performance, in terms of the computational savings gained over an exhaustive evaluation. While in some cases the savings gained are quite small, the racing algorithm proved to be highly robust to the possibility of erroneously eliminating the optimal models. All results were strongly dependent on the datasets used.

Quantum-error correction on linear-nearest-neighbor qubit arrays

A quantum circuit implementing 5-qubit quantum-error correction on a linear-nearest-neighbor architecture is described. The canonical decomposition is used to construct fast and simple gates that incorporate the necessary swap operations allowing the circuit to achieve the same depth as the current least depth circuit. Simulations of the circuit's performance when subjected to discrete and continuous errors are presented. The relationship between the error rate of a physical qubit and that of a logical qubit is investigated with emphasis on determining the concatenated error correction threshold.

Hierarchical indexing structure for efficient similarity search in video retrieval

With the rapid increase in both centralized video archives and distributed WWW video resources, content-based video retrieval is gaining its importance. To support such applications efficiently, content-based video indexing must be addressed. Typically, each video is represented by a sequence of frames. Due to the high dimensionality of frame representation and the large number of frames, video indexing introduces an additional degree of complexity. In this paper, we address the problem of content-based video indexing and propose an efficient solution, called the Ordered VA-File (OVA-File) based on the VA-file. OVA-File is a hierarchical structure and has two novel features: 1) partitioning the whole file into slices such that only a small number of slices are accessed and checked during k Nearest Neighbor (kNN) search and 2) efficient handling of insertions of new vectors into the OVA-File, such that the average distance between the new vectors and those approximations near that position is minimized. To facilitate a search, we present an efficient approximate kNN algorithm named Ordered VA-LOW (OVA-LOW) based on the proposed OVA-File. OVA-LOW first chooses possible OVA-Slices by ranking the distances between their corresponding centers and the query vector, and then visits all approximations in the selected OVA-Slices to work out approximate kNN. The number of possible OVA-Slices is controlled by a user-defined parameter delta. By adjusting delta, OVA-LOW provides a trade-off between the query cost and the result quality. Query by video clip consisting of multiple frames is also discussed. Extensive experimental studies using real video data sets were conducted and the results showed that our methods can yield a significant speed-up over an existing VA-file-based method and iDistance with high query result quality. Furthermore, by incorporating temporal correlation of video content, our methods achieved much more efficient performance.

Surface k-NN query processing

A k-NN query finds the k nearest-neighbors of a given point from a point database. When it is sufficient to measure object distance using the Euclidian distance, the key to efficient k-NN query processing is to fetch and check the distances of a minimum number of points from the database. For many applications, such as vehicle movement along road networks or rover and animal movement along terrain surfaces, the distance is only meaningful when it is along a valid movement path. For this type of k-NN queries, the focus of efficient query processing is to minimize the cost of computing distances using the environment data (such as the road network data and the terrain data), which can be several orders of magnitude larger than that of the point data. Efficient processing of k-NN queries based on the Euclidian distance or the road network distance has been investigated extensively in the past. In this paper, we investigate the problem of surface k-NN query processing, where the distance is calculated from the shortest path along a terrain surface. This problem is very challenging, as the terrain data can be very large and the computational cost of finding shortest paths is very high. We propose an efficient solution based on multiresolution terrain models. Our approach eliminates the need of costly process of finding shortest paths by ranking objects using estimated lower and upper bounds of distance on multiresolution terrain models.

Dynamical properties of a strongly correlated model for quarter-filled layered organic molecular crystals

The dynamical properties of an extended Hubbard model, which is relevant to quarter-filled layered organic molecular crystals, are analyzed. We have computed the dynamical charge correlation function, spectral density, and optical conductivity using Lanczos diagonalization and large-N techniques. As the ratio of the nearest-neighbor Coulomb repulsion, V, to the hopping integral, t, increases there is a transition from a metallic phase to a charge-ordered phase. Dynamical properties close to the ordering transition are found to differ from the ones expected in a conventional metal. Large-N calculations display an enhancement of spectral weight at low frequencies as the system is driven closer to the charge-ordering transition in agreement with Lanczos calculations. As V is increased the charge correlation function displays a collective mode which, for wave vectors close to (pi,pi), increases in amplitude and softens as the charge-ordering transition is approached. We propose that inelastic x-ray scattering be used to detect this mode. Large-N calculations predict superconductivity with d(xy) symmetry close to the ordering transition. We find that this is consistent with Lanczos diagonalization calculations, on lattices of 20 sites, which find that the binding energy of two holes becomes negative close to the charge-ordering transition.

Amorphous structures induced in monocrystalline silicon by mechanical loading

Different amorphous structures have been induced in monocrystalline silicon by high pressure in indentation and polishing. Through the use of high-resolution transmission electron microscopy and nanodiffraction, it was found that the structures of amorphous silicon formed at slow and fast loading/unloading rates are dissimilar and inherit the nearest-neighbor distance of the crystal in which they are formed. The results are in good agreement with recent theoretical predictions. (C) 2004 American Institute of Physics.

Multiquantum eigenstates of a linear chain of coupled qubits

We present a technique to identify exact analytic expressions for the multiquantum eigenstates of a linear chain of coupled qubits. A choice of Hilbert subspaces is described that allows an exact solution of the stationary Schrodinger equation without imposing periodic boundary conditions and without neglecting end effects, fully including the dipole-dipole nearest-neighbor interaction between the atoms. The treatment is valid for an arbitrary coherent excitation in the atomic system, any number of atoms, any size of the chain relative to the resonant wavelength and arbitrary initial conditions of the atomic system. The procedure we develop is general enough to be adopted for the study of excitation in an arbitrary array of atoms including spin chains and one-dimensional Bose-Einstein condensates.

Spin exchange and superconductivity in a t-J(')-V model for two-dimensional quarter-filled systems

The effect of antiferromagnetic spin fluctuations on two-dimensional quarter-filled systems is studied theoretically. An effective t-J(')-V model on a square lattice which accounts for checkerboard charge fluctuations and next-nearest-neighbor antiferromagnetic spin fluctuations is considered. From calculations based on large-N theory on this model it is found that the exchange interaction J(') increases the attraction between electrons in the d(xy) channel only, so that both charge and spin fluctuations work cooperatively to produce d(xy) pairing.

Topological side-chain classification of beta-turns: Ideal motifs for peptidomimetic development

beta-turns are important topological motifs for biological recognition of proteins and peptides. Organic molecules that sample the side chain positions of beta-turns have shown broad binding capacity to multiple different receptors, for example benzodiazepines. beta-turns have traditionally been classified into various types based on the backbone dihedral angles (phi 2, psi 2, phi 3 and psi 3). Indeed, 57-68% of beta-turns are currently classified into 8 different backbone families (Type I, Type II, Type I', Type II', Type VIII, Type VIa1, Type VIa2 and Type VIb and Type IV which represents unclassified beta-turns). Although this classification of beta-turns has been useful, the resulting beta-turn types are not ideal for the design of beta-turn mimetics as they do not reflect topological features of the recognition elements, the side chains. To overcome this, we have extracted beta-turns from a data set of non-homologous and high-resolution protein crystal structures. The side chain positions, as defined by C-alpha-C-beta vectors, of these turns have been clustered using the kth nearest neighbor clustering and filtered nearest centroid sorting algorithms. Nine clusters were obtained that cluster 90% of the data, and the average intra-cluster RMSD of the four C-alpha-C-beta vectors is 0.36. The nine clusters therefore represent the topology of the side chain scaffold architecture of the vast majority of beta-turns. The mean structures of the nine clusters are useful for the development of beta-turn mimetics and as biological descriptors for focusing combinatorial chemistry towards biologically relevant topological space.

A quasi-chemical viscosity model for fully liquid slags in the Al2O3-CaO-'FeO'-SiO2 system

A structurally based viscosity model for fully liquid silicate slags has been proposed and applied to the Al2O3-CaO-'FeO'-SiO2 system at metallic iron saturation. The model links the slag viscosity to the internal structure of melts through the concentrations of various anion/cation structural units (SUs). The concentrations of structural units are equivalent to the second nearest neighbor bond concentrations calculated by the quasi-chemical thermodynamic model. This viscosity model describes experimental data over the entire temperature and composition range within the Al2O3-CaO-'FeO'-SiO2 system at metallic iron saturation and can be extended to other industrial slag systems.

Excitation spectra of the spin-1/2 triangular-lattice Heisenberg antiferromagnet

We use series expansion methods to calculate the dispersion relation of the one-magnon excitations for the spin-(1)/(2) triangular-lattice nearest-neighbor Heisenberg antiferromagnet above a three-sublattice ordered ground state. Several striking features are observed compared to the classical (large-S) spin-wave spectra. Whereas, at low energies the dispersion is only weakly renormalized by quantum fluctuations, significant anomalies are observed at high energies. In particular, we find rotonlike minima at special wave vectors and strong downward renormalization in large parts of the Brillouin zone, leading to very flat or dispersionless modes. We present detailed comparison of our calculated excitation energies in the Brillouin zone with the spin-wave dispersion to order 1/S calculated recently by Starykh, Chubukov, and Abanov [Phys. Rev. B74, 180403(R) (2006)]. We find many common features but also some quantitative and qualitative differences. We show that at temperatures as low as 0.1J the thermally excited rotons make a significant contribution to the entropy. Consequently, unlike for the square lattice model, a nonlinear sigma model description of the finite-temperature properties is only applicable at temperatures < 0.1J. Finally, we review recent NMR measurements on the organic compound kappa-(BEDT-TTF)(2)Cu-2(CN)(3). We argue that these are inconsistent with long-range order and a description of the low-energy excitations in terms of interacting magnons, and that therefore a Heisenberg model with only nearest-neighbor exchange does not offer an adequate description of this material.

Expansion-based algorithms for finding single pair shortest path on surface

Finding single pair shortest paths on surface is a fundamental problem in various domains, like Geographic Information Systems (GIS) 3D applications, robotic path planning system, and surface nearest neighbor query in spatial database, etc. Currently, to solve the problem, existing algorithms must traverse the entire polyhedral surface. With the rapid advance in areas like Global Positioning System (CPS), Computer Aided Design (CAD) systems and laser range scanner, surface models axe becoming more and more complex. It is not uncommon that a surface model contains millions of polygons. The single pair shortest path problem is getting harder and harder to solve. Based on the observation that the single pair shortest path is in the locality, we propose in this paper efficient methods by excluding part of the surface model without considering them in the search process. Three novel expansion-based algorithms are proposed, namely, Naive algorithm, Rectangle-based Algorithm and Ellipse-based Algorithm. Each algorithm uses a two-step approach to find the shortest path. (1) compute an initial local path. (2) use the value of this initial path to select a search region, in which the global shortest path exists. The search process terminates once the global optimum criteria are satisfied. By reducing the searching region, the performance is improved dramatically in most cases.

Maximum-likelihood noncoherent lattice decoding of QAM

We present a novel, maximum-likelihood (ML), lattice-decoding algorithm for noncoherent block detection of QAM signals. The computational complexity is polynomial in the block length; making it feasible for implementation compared with the exhaustive search ML detector. The algorithm works by enumerating the nearest neighbor regions for a plane defined by the received vector; in a conceptually similar manner to sphere decoding. Simulations show that the new algorithm significantly outperforms existing approaches

Off-line signature verification and forgery detection system based on fuzzy modeling

This paper presents an innovative approach for signature verification and forgery detection based on fuzzy modeling. The signature image is binarized and resized to a fixed size window and is then thinned. The thinned image is then partitioned into a fixed number of eight sub-images called boxes. This partition is done using the horizontal density approximation approach. Each sub-image is then further resized and again partitioned into twelve further sub-images using the uniform partitioning approach. The features of consideration are normalized vector angle (α) from each box. Each feature extracted from sample signatures gives rise to a fuzzy set. Since the choice of a proper fuzzification function is crucial for verification, we have devised a new fuzzification function with structural parameters, which is able to adapt to the variations in fuzzy sets. This function is employed to develop a complete forgery detection and verification system.