OpenRaiser/Intern-Atlas huggingface dataset:
Dimension Reduction of Health Data Clustering
Venue: arXiv cs.DB 2011
Year: 2011

The current data tends to be more complex than conventional data and need dimension reduction. Dimension reduction is important in cluster analysis and creates a smaller data in volume and has the same analytical results as the original representation. A clustering process needs data reduction to obtain an efficient processing time while clustering and mitigate curse of dimensionality. This paper proposes a model for extracting multidimensional data clustering of health database. We implemented four dimension reduction techniques such as Singular Value Decomposition (SVD), Principal Component Analysis (PCA), Self Organizing Map (SOM) and FastICA. The results show that dimension reductions significantly reduce dimension and shorten processing time and also increased performance of cluster in several health datasets.
Optimal Final Carry Propagate Adder Design for Parallel Multipliers
Venue: arXiv cs.AR 2011
Year: 2011

Based on the ASIC layout level simulation of 7 types of adder structures each of four different sizes, i.e. a total of 28 adders, we propose expressions for the width of each of the three regions of the final Carry Propagate Adder (CPA) to be used in parallel multipliers. We also propose the types of adders to be used in each region that would lead to the optimal performance of the hybrid final adders in parallel multipliers. This work evaluates the complete performance of the analyzed designs in terms of delay, area, power through custom design and layout in 0.18 um CMOS process technology.
Evaluating the SharedCanvas Manuscript Data Model in CATCHPlus
Venue: arXiv cs.DL 2011
Year: 2011

In this paper, we present the SharedCanvas model for describing the layout of culturally important, hand-written objects such as medieval manuscripts, which is intended to be used as a common input format to presentation interfaces. The model is evaluated using two collections from CATCHPlus not consulted during the design phase, each with their own complex requirements, in order to determine if further development is required or if the model is ready for general usage. The model is applied to the new collections, revealing several new areas of concern for user interface production and discovery of the constituent resources. However, the fundamental information modelling aspects of SharedCanvas and the underlying Open Annotation Collaboration ontology are demonstrated to be sufficient to cover the challenging new requirements. The distributed, Linked Open Data approach is validated as an important methodology to seamlessly allow simultaneous interaction with multiple repositories, and at the same time to facilitate both scholarly commentary and crowd-sourcing of the production of transcriptions.
A critical evaluation of network and pathway based classifiers for outcome prediction in breast cancer
Venue: arXiv cs.LG 2011
Year: 2011

Recently, several classifiers that combine primary tumor data, like gene expression data, and secondary data sources, such as protein-protein interaction networks, have been proposed for predicting outcome in breast cancer. In these approaches, new composite features are typically constructed by aggregating the expression levels of several genes. The secondary data sources are employed to guide this aggregation. Although many studies claim that these approaches improve classification performance over single gene classifiers, the gain in performance is difficult to assess. This stems mainly from the fact that different breast cancer data sets and validation procedures are employed to assess the performance. Here we address these issues by employing a large cohort of six breast cancer data sets as benchmark set and by performing an unbiased evaluation of the classification accuracies of the different approaches. Contrary to previous claims, we find that composite feature classifiers do not outperform simple single gene classifiers. We investigate the effect of (1) the number of selected features; (2) the specific gene set from which features are selected; (3) the size of the training set and (4) the heterogeneity of the data set on the performance of composite feature and single gene classifiers. Strikingly, we find that randomization of secondary data sources, which destroys all biological information in these sources, does not result in a deterioration in performance of composite feature classifiers. Finally, we show that when a proper correction for gene set size is performed, the stability of single gene sets is similar to the stability of composite feature sets. Based on these results there is currently no reason to prefer prognostic classifiers based on composite features over single gene classifiers for predicting outcome in breast cancer.
Types for X10 Clocks
Venue: arXiv cs.PL 2011
Year: 2011

X10 is a modern language built from the ground up to handle future parallel systems, from multicore machines to cluster configurations. We take a closer look at a pair of synchronisation mechanisms: finish and clocks. The former waits for the termination of parallel computations, the latter allow multiple concurrent activities to wait for each other at certain points in time. In order to better understand these concepts we study a type system for a stripped down version of X10. The main result assures that well typed programs do not run into the errors identified in the X10 language reference, namely the ClockUseException. The study will open, we hope, doors to a more flexible utilisation of clocks in the X10 language.
Clipping Noise Cancellation for OFDM and OFDMA Systems Using Compressed Sensing
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we propose clipping noise cancellation scheme using compressed sensing (CS) for orthogonal frequency division multiplexing (OFDM) systems. In the proposed scheme, only the data tones with high reliability are exploited in reconstructing the clipping noise instead of the whole data tones. For reconstructing the clipping noise using a fraction of the data tones at the receiver, the CS technique is applied. The proposed scheme is also applicable to interleaved orthogonal frequency division multiple access (OFDMA) systems due to the decomposition of fast Fourier transform (FFT) structure. Numerical analysis shows that the proposed scheme performs well for clipping noise cancellation of both OFDM and OFDMA systems.
An Improved Analytical Expression for Write Amplification in NAND Flash
Venue: arXiv cs.PF 2011
Year: 2011

Agarwal et al. gave an closed-form expression for write amplification in NAND flash memory by finding the probability of a page being valid over the whole flash memory. This paper gives an improved analytic expression for write amplification in NAND flash memory by finding the probability of a page being invalid over the block selected for garbage collection. The improved expression uses Lambert W function. Through asymptotic analysis, write amplification is shown to depend on overprovisioning factor only, consistent with the previous work. Comparison with numerical simulations shows that the improved expression achieves a more accurate prediction of write amplification. For example, when the overprovisioning factor is 0.3, the expression proposed by this paper gives a write amplification of 2.36 whereas that of the previous work gives 2.17, when the actual value is 2.35.
Generalized Optimization Framework for Graph-based Semi-supervised Learning
Venue: arXiv cs.NI 2011
Year: 2011

We develop a generalized optimization framework for graph-based semi-supervised learning. The framework gives as particular cases the Standard Laplacian, Normalized Laplacian and PageRank based methods. We have also provided new probabilistic interpretation based on random walks and characterized the limiting behaviour of the methods. The random walk based interpretation allows us to explain di erences between the performances of methods with di erent smoothing kernels. It appears that the PageRank based method is robust with respect to the choice of the regularization parameter and the labelled data. We illustrate our theoretical results with two realistic datasets, characterizing di erent challenges: Les Miserables characters social network and Wikipedia hyper-link graph. The graph-based semi-supervised learning classi- es the Wikipedia articles with very good precision and perfect recall employing only the information about the hyper-text links.
Organizational adaptation to Complexity: A study of the South African Insurance Market as a Complex Adaptive System through Statistical Risk Analysis
Venue: arXiv cs.CY 2011
Year: 2011

South Africa assumes a significant position in the insurance landscape of Africa. The present research based upon qualitative and quantitative analysis, shows that it shows the characteristics of a Complex Adaptive System. In addition, a statistical analysis of risk measures through Value at risk and Conditional tail expectation is carried out to show how an individual insurance company copes under external complexities. The authors believe that an explanation of the coping strategies, and the subsequent managerial implications would enrich our understanding of complexity in business.
Learning Hierarchical and Topographic Dictionaries with Structured Sparsity
Venue: arXiv cs.LG 2011
Year: 2011

Recent work in signal processing and statistics have focused on defining new regularization functions, which not only induce sparsity of the solution, but also take into account the structure of the problem. We present in this paper a class of convex penalties introduced in the machine learning community, which take the form of a sum of l_2 and l_infinity-norms over groups of variables. They extend the classical group-sparsity regularization in the sense that the groups possibly overlap, allowing more flexibility in the group design. We review efficient optimization methods to deal with the corresponding inverse problems, and their application to the problem of learning dictionaries of natural image patches: On the one hand, dictionary learning has indeed proven effective for various signal processing tasks. On the other hand, structured sparsity provides a natural framework for modeling dependencies between dictionary elements. We thus consider a structured sparse regularization to learn dictionaries embedded in a particular structure, for instance a tree or a two-dimensional grid. In the latter case, the results we obtain are similar to the dictionaries produced by topographic independent component analysis.
Semantic conflict resolution for integration of business components
Venue: arXiv cs.SE 2011
Year: 2011

Reusing and integrating Business Components in a new Information System requires detection and resolution of semantic conflicts. Moreover, most of integration and semantic conflict resolution systems rely on ontology alignment methods based on domain ontology. This work is positioned at the intersection of two research areas: Integration of reusable B C and alignment of ontologies for semantic conflict resolution. Our contribution concerns both the proposal of a BC integration solution based on ontologies alignment and a method for enriching the domain ontology used as a support for alignment
Kernel Topic Models
Venue: arXiv cs.LG 2011
Year: 2011

Latent Dirichlet Allocation models discrete data as a mixture of discrete distributions, using Dirichlet beliefs over the mixture weights. We study a variation of this concept, in which the documents' mixture weight beliefs are replaced with squashed Gaussian distributions. This allows documents to be associated with elements of a Hilbert space, admitting kernel topic models (KTM), modelling temporal, spatial, hierarchical, social and other structure between documents. The main challenge is efficient approximate inference on the latent Gaussian. We present an approximate algorithm cast around a Laplace approximation in a transformed basis. The KTM can also be interpreted as a type of Gaussian process latent variable model, or as a topic model conditional on document features, uncovering links between earlier work in these areas.
Spectral descriptors for deformable shapes
Venue: arXiv cs.CV 2011
Year: 2011

Informative and discriminative feature descriptors play a fundamental role in deformable shape analysis. For example, they have been successfully employed in correspondence, registration, and retrieval tasks. In the recent years, significant attention has been devoted to descriptors obtained from the spectral decomposition of the Laplace-Beltrami operator associated with the shape. Notable examples in this family are the heat kernel signature (HKS) and the wave kernel signature (WKS). Laplacian-based descriptors achieve state-of-the-art performance in numerous shape analysis tasks; they are computationally efficient, isometry-invariant by construction, and can gracefully cope with a variety of transformations. In this paper, we formulate a generic family of parametric spectral descriptors. We argue that in order to be optimal for a specific task, the descriptor should take into account the statistics of the corpus of shapes to which it is applied (the "signal") and those of the class of transformations to which it is made insensitive (the "noise"). While such statistics are hard to model axiomatically, they can be learned from examples. Following the spirit of the Wiener filter in signal processing, we show a learning scheme for the construction of optimal spectral descriptors and relate it to Mahalanobis metric learning. The superiority of the proposed approach is demonstrated on the SHREC'10 benchmark.
Experimental Assessment of BitTorrent Completion Time in Heterogeneous TCP/uTP swarms
Venue: arXiv cs.NI 2011
Year: 2011

BitTorrent, one of the most widespread used P2P application for file-sharing, recently got rid of TCP by introducing an application-level congestion control protocol named uTP. The aim of this new protocol is to efficiently use the available link capacity, while minimizing its interference with the rest of user traffic (e.g., Web, VoIP and gaming) sharing the same access bottleneck. In this paper we perform an experimental study of the impact of uTP on the torrent completion time, the metric that better captures the user experience. We run BitTorrent applications in a flash crowd scenario over a dedicated cluster platform, under both homogeneous and heterogeneous swarm population. Experiments show that an all-uTP swarms have shorter torrent download time with respect to all-TCP swarms. Interestingly, at the same time, we observe that even shorter completion times can be achieved under careful mixtures of TCP and uTP traffic.
Paraglide: Interactive Parameter Space Partitioning for Computer Simulations
Venue: arXiv cs.SY 2011
Year: 2011

In this paper we introduce paraglide, a visualization system designed for interactive exploration of parameter spaces of multi-variate simulation models. To get the right parameter configuration, model developers frequently have to go back and forth between setting parameters and qualitatively judging the outcomes of their model. During this process, they build up a grounded understanding of the parameter effects in order to pick the right setting. Current state-of-the-art tools and practices, however, fail to provide a systematic way of exploring these parameter spaces, making informed decisions about parameter settings a tedious and workload-intensive task. Paraglide endeavors to overcome this shortcoming by assisting the sampling of the parameter space and the discovery of qualitatively different model outcomes. This results in a decomposition of the model parameter space into regions of distinct behaviour. We developed paraglide in close collaboration with experts from three different domains, who all were involved in developing new models for their domain. We first analyzed current practices of six domain experts and derived a set of design requirements, then engaged in a longitudinal user-centered design process, and finally conducted three in-depth case studies underlining the usefulness of our approach.
Diffusion of Information in Robot Swarms
Venue: arXiv cs.RO 2011
Year: 2011

This work is devoted to communication approaches, which spread information in robot swarms. These mechanisms are useful for large-scale systems and also for such cases when a limited communication equipment does not allow routing of information packages. We focus on two approaches such as virtual fields and epidemic algorithms, discuss several aspects of hardware implementation and demonstrate experiments performed with microrobots "Jasmine".
Face Recognition Based on SVM and 2DPCA
Venue: arXiv cs.CV 2011
Year: 2011

The paper will present a novel approach for solving face recognition problem. Our method combines 2D Principal Component Analysis (2DPCA), one of the prominent methods for extracting feature vectors, and Support Vector Machine (SVM), the most powerful discriminative method for classification. Experiments based on proposed method have been conducted on two public data sets FERET and AT&T; the results show that the proposed method could improve the classification rates.
Graph Searching, Parity Games and Imperfect Information
Venue: arXiv cs.GT 2011
Year: 2011

We investigate the interrelation between graph searching games and games with imperfect information. As key consequence we obtain that parity games with bounded imperfect information can be solved in PTIME on graphs of bounded DAG-width which generalizes several results for parity games on graphs of bounded complexity. We use a new concept of graph searching where several cops try to catch multiple robbers instead of just a single robber. The main technical result is that the number of cops needed to catch r robbers monotonously is at most r times the DAG-width of the graph. We also explore aspects of this new concept as a refinement of directed path-width which accentuates its connection to the concept of imperfect information.
Secondary Spectrum Auctions for Symmetric and Submodular Bidders
Venue: arXiv cs.DS 2011
Year: 2011

We study truthful auctions for secondary spectrum usage in wireless networks. In this scenario, n communication requests need to be allocated to k available channels that are subject to interference and noise. We present the first truthful mechanisms for secondary spectrum auctions with symmetric or submodular valuations. Our approach to model interference uses an edge-weighted conflict graph, and our algorithms provide asymptotically almost optimal approximation bounds for conflict graphs with a small inductive independence number rho << n. This approach covers a large variety of interference models such as, e.g., the protocol model or the recently popular physical model of interference. For unweighted conflict graphs and symmetric valuations we use LP-rounding to obtain $O(ρ)$-approximate mechanisms; for weighted conflict graphs we get a factor of O(rho (log n + log k)). For submodular users we combine the convex rounding framework of Dughmi et al [STOC 2011] with randomized meta-rounding to obtain O(rho)-approximate mechanisms for matroid-rank-sum valuations; for weighted conflict graphs we can fully drop the dependence on k to get O(rho log n). We conclude with promising initialresults for deterministically truthful mechanisms that allow approximation factors based on rho.
The Axiomatic Foundation of Space in GFO
Venue: arXiv cs.OH 2011
Year: 2011

Space and time are basic categories of any top-level ontology. They are fundamental assumptions for the mode of existence of those individuals which are said to be in space and time. In the present paper the ontology of space in the General Formal Ontology (GFO) is expounded. This ontology is represented as a theory BT (Brentano Theory), which is specified by a set of axioms formalized in first-order logic. This theory uses four primitive relations: SReg(x) (x is space region), spart(x, y) (x is spatial part of y), sb(x, y) (x is spatial boundary of y), and scoinc(x, y) (x and y spatially coincide). This ontology is inspired by ideas of Franz Brentano. The investigation and exploration of Franz Brentano's ideas on space and time began about twenty years ago by work of R.M. Chisholm, B. Smith and A. Varzi. The present paper takes up this line of research and makes a further step in establishing an ontology of space which is based on rigorous logical methods and on principles of the new philosophical approach of integrative realism.
A Wikipedia Literature Review
Venue: arXiv cs.DL 2011
Year: 2011

This paper was originally designed as a literature review for a doctoral dissertation focusing on Wikipedia. This exposition gives the structure of Wikipedia and the latest trends in Wikipedia research.
A Continuation Method for Nash Equilibria in Structured Games
Venue: arXiv cs.GT 2011
Year: 2011

Structured game representations have recently attracted interest as models for multi-agent artificial intelligence scenarios, with rational behavior most commonly characterized by Nash equilibria. This paper presents efficient, exact algorithms for computing Nash equilibria in structured game representations, including both graphical games and multi-agent influence diagrams (MAIDs). The algorithms are derived from a continuation method for normal-form and extensive-form games due to Govindan and Wilson; they follow a trajectory through a space of perturbed games and their equilibria, exploiting game structure through fast computation of the Jacobian of the payoff function. They are theoretically guaranteed to find at least one equilibrium of the game, and may find more. Our approach provides the first efficient algorithm for computing exact equilibria in graphical games with arbitrary topology, and the first algorithm to exploit fine-grained structural properties of MAIDs. Experimental results are presented demonstrating the effectiveness of the algorithms and comparing them to predecessors. The running time of the graphical game algorithm is similar to, and often better than, the running time of previous approximate algorithms. The algorithm for MAIDs can effectively solve games that are much larger than those solvable by previous methods.
Reliable Provisioning of Spot Instances for Compute-intensive Applications
Venue: arXiv cs.DC 2011
Year: 2011

Cloud computing providers are now offering their unused resources for leasing in the spot market, which has been considered the first step towards a full-fledged market economy for computational resources. Spot instances are virtual machines (VMs) available at lower prices than their standard on-demand counterparts. These VMs will run for as long as the current price is lower than the maximum bid price users are willing to pay per hour. Spot instances have been increasingly used for executing compute-intensive applications. In spite of an apparent economical advantage, due to an intermittent nature of biddable resources, application execution times may be prolonged or they may not finish at all. This paper proposes a resource allocation strategy that addresses the problem of running compute-intensive jobs on a pool of intermittent virtual machines, while also aiming to run applications in a fast and economical way. To mitigate potential unavailability periods, a multifaceted fault-aware resource provisioning policy is proposed. Our solution employs price and runtime estimation mechanisms, as well as three fault tolerance techniques, namely checkpointing, task duplication and migration. We evaluate our strategies using trace-driven simulations, which take as input real price variation traces, as well as an application trace from the Parallel Workload Archive. Our results demonstrate the effectiveness of executing applications on spot instances, respecting QoS constraints, despite occasional failures.