15424385
Data driven approach to designing minimum hamming distance polychotomizer
A polychotomous classifier assigns an observation to one of the K categories with K > = 3. Multiple binary classifiers (K = 2) such as the popular Support Vector Machines can be combined to achieve multi-class classification. Commonly used approaches include the one-vs-others scheme and the one-vs-one (pairwise coupling) scheme. While literature reported better performance from pairwise coupling than one-vs-others, the number of base learners required by pairwise coupling is quadratic in K. Alternatively, error correcting output codes (ECOC) provides a more general framework for designing polychotomizers. It associates each class with a codeword, which provides the capability to unify the traditional schemes. However, the design of an effective "coding matrix" remains an open problem. We study one kind of ECOC polychotomizer that decodes using minimum hamming distance. We propose a novel data-driven way to design the codewords based on inter-cluster distance. It provides a systematic way to extend the traditional schemes and construct effective polychotomizers. Experiments are conducted on synthetic data and real world applications including UCI repository problems and CENPARMI handwritten numerals. Experiments show that the proposed scheme can achieve competitive accuracy compared with both traditional schemes, and the number of base learners is typically much less than the requirement of the pairwise scheme.
164269
Recognition of handwritten numerals by Quantum Neural Network with fuzzy features
Abstract. This paper describes a new kind of neural network – Quantum Neural Network (QNN) – and its application to the recognition of handwritten numerals. QNN combines the advantages of neural modelling and fuzzy theoretic principles. Novel experiments have been designed for in-depth studies of applying the QNN to both real data and confusing images synthesized by morphing. Tests on synthesized data examine QNN's fuzzy decision boundary with the intention to illustrate its mechanism and characteristics, while studies on real data prove its great potential as a handwritten numeral classifier and the special role it plays in multi-expert systems. An effective decision-fusion system is proposed and a high reliability of 99.10% has been achieved.
11171096
Automatic detection of premature ventricular contraction using quantum neural networks
Premature ventricular contractions (PVCs) are ectopic heart beats originating from ventricular area. It is a common form of heart arrhythmia. Electrocardiogram (ECG) recordings have been widely used to assist cardiologists to diagnose the problem. In this paper, we study the automatic detection of PVC using a fuzzy artificial neural network named Quantum Neural Network (QNN). With the quantum neurons in the network, trained QNN can model the levels of uncertainty arising from complex classification problems. This fuzzy feature is expected to enhance the reliability of the algorithm, which is critical for the applications in the biomedical domain. Experiments were conducted on ECG records in the MIT-BIH Arrhythmia Database. Results showed consistently higher or same reliability of QNN on all the available records compared to the backpropagation network. QNN, however, has a relatively higher resource requirement for training.
27166902
Toward automatic annotation of in situ mRNA expression patterns of drosophila embryos
The in situ mRNA hybridization gene expression pattern images of Drosophila melanogaster in the course of embryogenesis provide spatial-temporal information of the expression patterns of a target gene. This information is critical for understanding the roles of genes during the development of embryos. Currently, the annotation of these images is often done by manually assigning a subset of image ontology terms to the images. This approach is time consuming and depends heavily on the consistency of the experts. Alternatively, if the annotation process can be automated or semi-automated, efficiency and consistency are likely to be greatly enhanced. We formulate this task as a pattern classification problem, and present preliminary results. We consider both the template-based global matching and the multi-objective classification based on neural networks (e.g. multi-layer perceptron). We develop a method to combine them to optimize efficiency and accuracy. This method has been applied to the gene expression pattern image database generated by the Berkeley Drosophila Genome Project.
1706470
Regularized B-spline network and its application to heart arrhythmia classification
This paper presents an effective learning scheme that combines B-spline modeling and regularized neural networks. Essential issues of structural design and learning process are discussed. Regularization theory is leveraged to design the topological structure of the network. A training algorithm is derived for the learning of both synaptic weights and B-spline coefficients. The approach is then applied to the medical problem of heart arrhythmia detection, particularly the detection of premature ventricular contraction. Promising results demonstrate the potential benefits of the proposed method.
7237236
Unconstrained numeral pair recognition using enhanced error correcting output coding: a holistic approach
This paper describes a new approach to recognize touching numeral strings. Currently most methods for numeral string recognition require segmenting the string image into separate numerals. As a result, the recognition system heavily depends on the reliability of the segmentation module. This study explores the holistic strategy directly on the string images without segmentation. It builds the novel classifier by combining binary classifiers based on data-driven error correcting output coding (DECOC). The dimensions of input images are reduced using principal components analysis. Support vector machines are used as base learners. Experiments on NIST SD19 touching numeral pairs confirm that DECOC can achieve favorable performance compared with other multi-class holistic classifiers. The method provides the flexibility of controlling the computational complexity versus accuracy. We also discuss an implementation suitable for distributing computing by decomposing the ensemble into subtasks.
18692556
Transparent mid-tier database caching in SQL server
Many applications today run in a multi-tier environment with browser-based clients, mid-tier (application) servers and a backend database server. Mid-tier database caching attempts to improve system throughput and scalability by offloading part of the database workload to intermediate database servers that partially replicate data from the backend server. The fact that some queries are offloaded to an intermediate server should be completely transparent to applications one of the key distinctions between caching and replication. MTCache is a prototype mid-tier database caching solution for SQL Server that achieves this transparency. It builds on SQL Server's support for materialized views, distributed queries and replication. This paper describes MTCache and reports experimental results on the TPC-W benchmark. The experiments show that a significant part of the query workload can be offloaded to cache servers, resulting in greatly improved scale-out on the read-dominated workloads of the benchmark. Replication overhead was small with an average replication delay of less than two seconds.
17064783
Implementing database operations using SIMD instructions
Modern CPUs have instructions that allow basic operations to be performed on several data elements in parallel. These instructions are called SIMD instructions, since they apply a single instruction to multiple data elements. SIMD technology was initially built into commodity processors in order to accelerate the performance of multimedia applications. SIMD instructions provide new opportunities for database engine design and implementation. We study various kinds of operations in a database context, and show how the inner loop of the operations can be accelerated using SIMD instructions. The use of SIMD instructions has two immediate performance benefits: It allows a degree of parallelism, so that many operands can be processed at once. It also often leads to the elimination of conditional branch instructions, reducing branch mispredictions.We consider the most important database operations, including sequential scans, aggregation, index operations, and joins. We present techniques for implementing these using SIMD instructions. We show that there are significant benefits in redesigning traditional query processing algorithms so that they can make better use of SIMD technology. Our study shows that using a SIMD parallelism of four, the CPU time for the new algorithms is from 10% to more than four times less than for the traditional algorithms. Superlinear speedups are obtained as a result of the elimination of branch misprediction effects.
17981178
An improved ellipse propagation model for location estimation in facilitating ubiquitous computing
Positioning is a crucial technology for ubiquitous computing. A directional propagation model - the ellipse propagation model (EPM) is proposed by our research group for locating a mobile station (MS) within a radio cellular network with an accuracy that can enable a number of location based services to realize ubiquitous computing. By using a geometric algorithm, the location of the mobile station can be estimated. However, since one parameter in our geometric algorithm is fixed, errors may be induced as the surrounding environment changes. In view of this, we would like to propose a new algorithm - the iterative algorithm to provide the positioning based on EPM. With the technical support of two local mobile phone operators, we have conducted a series of experiments using real data and experiment results showed that the proposed iterative algorithm outperforms the geometric algorithm by a good margin of 18% in terms of average error.
31245503
On the ascending star subgraph decomposition of star forests
AbstractLetG be a graph of size
$$\left( {n_2^ + 1} \right)$$
 for some integern≥2. ThenG is said to have an ascending star subgraph decomposition ifG can be decomposed inton subgraphsG1,G2, ...,Gn such that eachGi is a star of sizei with 1≤i≤n. We shall prove in this paper that a star forest with size
$$\left( {n_2^ + 1} \right)$$
, possesses an ascending star subgraph decomposition if the size of each component is at leastn, which is stronger than the conjecture proposed by Y. Alavi, A. J. Boals, G. Chartrand, P. Erdős and O. R. Oellermann.
15468615
Security Remarks on a Group Signature Scheme with Member Deletion
A group signature scheme allows a group member of a given group to sign messages on behalf of the group in an anonymous and unlinkable fashion. In case of a dispute, however, a designated group manager can reveal the signer of a valid group signature. Based on the Camenisch-Michels group signature scheme [7,8], Kim, Lim and Lee proposed the first group signature scheme with a member deletion procedure at ICISC 2000 [15]. Their scheme is very efficient in both communication and computation aspects. Unfortunately, their scheme is insecure. In this paper, we first identify an effective way that allows any verifier to determine whether two valid group signatures are signed by the same group member. Secondly, we find that in their scheme a deleted group member can still update his signing key and then generate valid group signatures after he was deleted from the group. In other words, the Kim-Lim-Lee group signature scheme [15] is linkable and does not support secure group member deletion.