OpenRaiser/Intern-Atlas huggingface dataset:
On the Use of Underspecified Data-Type Semantics for Type Safety in Low-Level Code
Venue: arXiv cs.LO 2012
Year: 2012

In recent projects on operating-system verification, C and C++ data types are often formalized using a semantics that does not fully specify the precise byte encoding of objects. It is well-known that such an underspecified data-type semantics can be used to detect certain kinds of type errors. In general, however, underspecified data-type semantics are unsound: they assign well-defined meaning to programs that have undefined behavior according to the C and C++ language standards. A precise characterization of the type-correctness properties that can be enforced with underspecified data-type semantics is still missing. In this paper, we identify strengths and weaknesses of underspecified data-type semantics for ensuring type safety of low-level systems code. We prove sufficient conditions to detect certain classes of type errors and, finally, identify a trade-off between the complexity of underspecified data-type semantics and their type-checking capabilities.
Neuro-Fuzzy Computing System with the Capacity of Implementation on Memristor-Crossbar and Optimization-Free Hardware Training
Venue: arXiv cs.NE 2012
Year: 2012

In this paper, first we present a new explanation for the relation between logical circuits and artificial neural networks, logical circuits and fuzzy logic, and artificial neural networks and fuzzy inference systems. Then, based on these results, we propose a new neuro-fuzzy computing system which can effectively be implemented on the memristor-crossbar structure. One important feature of the proposed system is that its hardware can directly be trained using the Hebbian learning rule and without the need to any optimization. The system also has a very good capability to deal with huge number of input-out training data without facing problems like overtraining.
Adaptive Interference Alignment with CSI Uncertainty
Venue: arXiv cs.IT 2012
Year: 2012

Interference alignment (IA) is known to significantly increase sum-throughput at high SNR in the presence of multiple interfering nodes, however, the reliability of IA is little known, which is the subject of this paper. We study the error performance of IA and compare it with conventional orthogonal transmission schemes. Since most IA algorithms require extensive channel state information (CSI), we also investigate the impact of CSI imperfection (uncertainty) on the error performance. Our results show that under identical rates, IA attains a better error performance than the orthogonal scheme for practical signal to noise ratio (SNR) values but is more sensitive to CSI uncertainty. We design bit loading algorithms that significantly improve error performance of the existing IA schemes. Furthermore, we propose an adaptive transmission scheme that not only considerably reduces error probability, but also produces robustness to CSI uncertainty.
An Approach of Improving Students Academic Performance by using k means clustering algorithm and Decision tree
Venue: arXiv cs.LG 2012
Year: 2012

Improving students academic performance is not an easy task for the academic community of higher learning. The academic performance of engineering and science students during their first year at university is a turning point in their educational path and usually encroaches on their General Point Average,GPA in a decisive manner. The students evaluation factors like class quizzes mid and final exam assignment lab work are studied. It is recommended that all these correlated information should be conveyed to the class teacher before the conduction of final exam. This study will help the teachers to reduce the drop out ratio to a significant level and improve the performance of students. In this paper, we present a hybrid procedure based on Decision Tree of Data mining method and Data Clustering that enables academicians to predict students GPA and based on that instructor can take necessary step to improve student academic performance.
New Heuristics for Interfacing Human Motor System using Brain Waves
Venue: arXiv cs.HC 2012
Year: 2012

There are many new forms of interfacing human users to machines. We persevere here electric mechanical form of interaction between human and machine. The emergence of brain-computer interface allows mind-to-movement systems. The story of the Pied Piper inspired us to devise some new heuristics for interfacing human motor system using brain waves by combining head helmet and LumbarMotionMonitor For the simulation we use java GridGain Brain responses of classified subjects during training indicates that Probe can be the best stimulus to rely on in distinguishing between knowledgeable and not knowledgeable
Additive-State-Decomposition-Based Tracking Control for TORA Benchmark
Venue: arXiv cs.SY 2012
Year: 2012

In this paper, a new control scheme, called additive state decomposition based tracking control, is proposed to solve the tracking (rejection) problem for rotational position of the TORA (a nonlinear nonminimum phase system). By the additive state decomposition, the tracking (rejection) task for the considered nonlinear system is decomposed into two independent subtasks: a tracking (rejection) subtask for a linear time invariant (LTI) system, leaving a stabilization subtask for a derived nonlinear system. By the decomposition, the proposed tracking control scheme avoids solving regulation equations and can tackle the tracking (rejection) problem in the presence of any external signal (except for the frequencies at +1 or -1) generated by a marginally stable autonomous LTI system. To demonstrate the effectiveness, numerical simulation is given.
Automating rule generation for grammar checkers
Venue: arXiv cs.CL 2012
Year: 2012

In this paper, I describe several approaches to automatic or semi-automatic development of symbolic rules for grammar checkers from the information contained in corpora. The rules obtained this way are an important addition to manually-created rules that seem to dominate in rule-based checkers. However, the manual process of creation of rules is costly, time-consuming and error-prone. It seems therefore advisable to use machine-learning algorithms to create the rules automatically or semi-automatically. The results obtained seem to corroborate my initial hypothesis that symbolic machine learning algorithms can be useful for acquiring new rules for grammar checking. It turns out, however, that for practical uses, error corpora cannot be the sole source of information used in grammar checking. I suggest therefore that only by using different approaches, grammar-checkers, or more generally, computer-aided proofreading tools, will be able to cover most frequent and severe mistakes and avoid false alarms that seem to distract users.
On the Role of Infrastructure sharing for Mobile Network Operators in Emerging Markets
Venue: arXiv cs.NI 2012
Year: 2012

The traditional model of single ownership of all the physical network elements and network layers by mobile network operators is beginning to be challenged. This has been attributed to the rapid and complex technology migration compounded with rigorous regulatory requirements and ever increasing capital expenditures. These trends, combined together with the increasing competition, rapid commoditization of telecommunication equipments and rising separation of network and service provisioning are pushing the operators to adopt multiple strategies, with network infrastructure sharing in the core and radio access networks emerging as a more radical mechanism to substantially and sustainably improve network costs. Through infrastructure sharing, developing countries and other emerging economies can harness the technological, market and regulatory developments that have fostered affordable access to mobile and broadband services. Similarly, the network operators entering or consolidating in the emerging markets can aim for substantial savings on capital and operating expenses. The present paper aims to investigate the current technological solutions and regulatory and the technical-economical dimensions in connection with the sharing of mobile telecommunication networks in emerging countries. We analyze the estimated savings on capital and operating expenses, while assessing the technical constraints, applicability and benefits of the network sharing solutions in an emerging market context.
A recursive divide-and-conquer approach for sparse principal component analysis
Venue: arXiv cs.CV 2012
Year: 2012

In this paper, a new method is proposed for sparse PCA based on the recursive divide-and-conquer methodology. The main idea is to separate the original sparse PCA problem into a series of much simpler sub-problems, each having a closed-form solution. By recursively solving these sub-problems in an analytical way, an efficient algorithm is constructed to solve the sparse PCA problem. The algorithm only involves simple computations and is thus easy to implement. The proposed method can also be very easily extended to other sparse PCA problems with certain constraints, such as the nonnegative sparse PCA problem. Furthermore, we have shown that the proposed algorithm converges to a stationary point of the problem, and its computational complexity is approximately linear in both data size and dimensionality. The effectiveness of the proposed method is substantiated by extensive experiments implemented on a series of synthetic and real data in both reconstruction-error-minimization and data-variance-maximization viewpoints.
Repeated Root Constacyclic Codes of Length $mp^s$ over $\mathbb{F}_{p^r}+u \mathbb{F}_{p^r}+...+ u^{e-1}\mathbb{F}_{p^r}$
Venue: arXiv cs.IT 2012
Year: 2012

We give the structure of $λ$-constacyclic codes of length $p^sm$ over $R=\mathbb{F}_{p^r}+u \mathbb{F}_{p^r}+...+ u^{e-1}\mathbb{F}_{p^r}$ with $λ\in \F_{p^r}^*$. We also give the structure of $λ$-constacyclic codes of length $p^sm$ with $λ=α_1+uα_2+...+u^{e-1} α_{e-1}$, where $α_1,α_2 \neq 0$ and study the self-duality of these codes.
VUPIC: Virtual Machine Usage Based Placement in IaaS Cloud
Venue: arXiv cs.DC 2012
Year: 2012

Efficient resource allocation is one of the critical performance challenges in an Infrastructure as a Service (IaaS) cloud. Virtual machine (VM) placement and migration decision making methods are integral parts of these resource allocation mechanisms. We present a novel virtual machine placement algorithm which takes performance isolation amongst VMs and their continuous resource usage into account while taking placement decisions. Performance isolation is a form of resource contention between virtual machines interested in basic low level hardware resources (CPU, memory, storage, and networks bandwidth). Resource contention amongst multiple co-hosted neighbouring VMs form the basis of the presented novel approach. Experiments are conducted to show the various categories of applications and effect of performance isolation and resource contention amongst them. A per-VM 3-dimensional Resource Utilization Vector (RUV) has been continuously calculated and used for placement decisions while taking conflicting resource interests of VMs into account. Experiments using the novel placement algorithm: VUPIC, show effective improvements in VM performance as well as overall resource utilization of the cloud.
Fixed-parameter tractability of satisfying beyond the number of variables
Venue: arXiv cs.DS 2012
Year: 2012

We consider a CNF formula $F$ as a multiset of clauses: $F=\{c_1,..., c_m\}$. The set of variables of $F$ will be denoted by $V(F)$. Let $B_F$ denote the bipartite graph with partite sets $V(F)$ and $F$ and with an edge between $v \in V(F)$ and $c \in F$ if $v \in c$ or $\bar{v} \in c$. The matching number $ν(F)$ of $F$ is the size of a maximum matching in $B_F$. In our main result, we prove that the following parameterization of {\sc MaxSat} (denoted by $(ν(F)+k)$-\textsc{SAT}) is fixed-parameter tractable: Given a formula $F$, decide whether we can satisfy at least $ν(F)+k$ clauses in $F$, where $k$ is the parameter. A formula $F$ is called variable-matched if $ν(F)=|V(F)|.$ Let $δ(F)=|F|-|V(F)|$ and $δ^*(F)=\max_{F'\subseteq F} δ(F').$ Our main result implies fixed-parameter tractability of {\sc MaxSat} parameterized by $δ(F)$ for variable-matched formulas $F$; this complements related results of Kullmann (2000) and Szeider (2004) for {\sc MaxSat} parameterized by $δ^*(F)$. To obtain our main result, we reduce $(ν(F)+k)$-\textsc{SAT} into the following parameterization of the {\sc Hitting Set} problem (denoted by $(m-k)$-{\sc Hitting Set}): given a collection $\cal C$ of $m$ subsets of a ground set $U$ of $n$ elements, decide whether there is $X\subseteq U$ such that $C\cap X\neq \emptyset$ for each $C\in \cal C$ and $|X|\le m-k,$ where $k$ is the parameter. Gutin, Jones and Yeo (2011) proved that $(m-k)$-{\sc Hitting Set} is fixed-parameter tractable by obtaining an exponential kernel for the problem. We obtain two algorithms for $(m-k)$-{\sc Hitting Set}: a deterministic algorithm of runtime $O((2e)^{2k+O(\log^2 k)} (m+n)^{O(1)})$ and a randomized algorithm of expected runtime $O(8^{k+O(\sqrt{k})} (m+n)^{O(1)})$. Our deterministic algorithm improves an algorithm that follows from the kernelization result of Gutin, Jones and Yeo (2011).
Efficient Community Detection in Large Networks using Content and Links
Venue: arXiv cs.SI 2012
Year: 2012

In this paper we discuss a very simple approach of combining content and link information in graph structures for the purpose of community discovery, a fundamental task in network analysis. Our approach hinges on the basic intuition that many networks contain noise in the link structure and that content information can help strengthen the community signal. This enables ones to eliminate the impact of noise (false positives and false negatives), which is particularly prevalent in online social networks and Web-scale information networks. Specifically we introduce a measure of signal strength between two nodes in the network by fusing their link strength with content similarity. Link strength is estimated based on whether the link is likely (with high probability) to reside within a community. Content similarity is estimated through cosine similarity or Jaccard coefficient. We discuss a simple mechanism for fusing content and link similarity. We then present a biased edge sampling procedure which retains edges that are locally relevant for each graph node. The resulting backbone graph can be clustered using standard community discovery algorithms such as Metis and Markov clustering. Through extensive experiments on multiple real-world datasets (Flickr, Wikipedia and CiteSeer) with varying sizes and characteristics, we demonstrate the effectiveness and efficiency of our methods over state-of-the-art learning and mining approaches several of which also attempt to combine link and content analysis for the purposes of community discovery. Specifically we always find a qualitative benefit when combining content with link analysis. Additionally our biased graph sampling approach realizes a quantitative benefit in that it is typically several orders of magnitude faster than competing approaches.
An Image Based Technique for Enhancement of Underwater Images
Venue: arXiv cs.CV 2012
Year: 2012

The underwater images usually suffers from non-uniform lighting, low contrast, blur and diminished colors. In this paper, we proposed an image based preprocessing technique to enhance the quality of the underwater images. The proposed technique comprises a combination of four filters such as homomorphic filtering, wavelet denoising, bilateral filter and contrast equalization. These filters are applied sequentially on degraded underwater images. The literature survey reveals that image based preprocessing algorithms uses standard filter techniques with various combinations. For smoothing the image, the image based preprocessing algorithms uses the anisotropic filter. The main drawback of the anisotropic filter is that iterative in nature and computation time is high compared to bilateral filter. In the proposed technique, in addition to other three filters, we employ a bilateral filter for smoothing the image. The experimentation is carried out in two stages. In the first stage, we have conducted various experiments on captured images and estimated optimal parameters for bilateral filter. Similarly, optimal filter bank and optimal wavelet shrinkage function are estimated for wavelet denoising. In the second stage, we conducted the experiments using estimated optimal parameters, optimal filter bank and optimal wavelet shrinkage function for evaluating the proposed technique. We evaluated the technique using quantitative based criteria such as a gradient magnitude histogram and Peak Signal to Noise Ratio (PSNR). Further, the results are qualitatively evaluated based on edge detection results. The proposed technique enhances the quality of the underwater images and can be employed prior to apply computer vision techniques.
An Improved UP-Growth High Utility Itemset Mining
Venue: arXiv cs.DB 2012
Year: 2012

Efficient discovery of frequent itemsets in large datasets is a crucial task of data mining. In recent years, several approaches have been proposed for generating high utility patterns, they arise the problems of producing a large number of candidate itemsets for high utility itemsets and probably degrades mining performance in terms of speed and space. Recently proposed compact tree structure, viz., UP Tree, maintains the information of transactions and itemsets, facilitate the mining performance and avoid scanning original database repeatedly. In this paper, UP Tree (Utility Pattern Tree) is adopted, which scans database only twice to obtain candidate items and manage them in an efficient data structured way. Applying UP Tree to the UP Growth takes more execution time for Phase II. Hence this paper presents modified algorithm aiming to reduce the execution time by effectively identifying high utility itemsets.
A Potential Game for Power and Frequency Allocation in Large-Scale Wireless Networks
Venue: arXiv cs.NI 2012
Year: 2012

In this paper we analyze power and frequency allocation in wireless networks through potential games. Potential games are used frequently in the literature for this purpose due to their desirable properties, such as convergence and stability. However, potential games usually assume massive message passing to obtain the necessary neighbor information at each user to achieve these properties. In this paper we show an example of a game where we are able to characterize the necessary neighbor information in order to show that the game has a potential function and the properties of potential games. We consider a network consisting of local access points where the goal of each AP is to allocate power and frequency to achieve some SINR requirement. We use the physical SINR model to validate a successful allocation, and show that given a suitable payoff function the game emits a generalized ordinal potential function under the assumption of sufficient neighbor information. Through simulations we evaluate the performance of the proposed game on a large scale in relation to the amount of information at each AP.
How many vertex locations can be arbitrarily chosen when drawing planar graphs?
Venue: arXiv cs.CG 2012
Year: 2012

It is proven that every set $S$ of distinct points in the plane with cardinality $\lceil \frac{\sqrt{\log_2 n}-1}{4} \rceil$ can be a subset of the vertices of a crossing-free straight-line drawing of any planar graph with $n$ vertices. It is also proven that if $S$ is restricted to be a one-sided convex point set, its cardinality increases to $\lceil \sqrt[3]{n} \rceil$. The proofs are constructive and give rise to O(n)-time drawing algorithms. As a part of our proofs, we show that every maximal planar graph contains a large induced biconnected outerplanar graphs and a large induced outerpath (an outerplanar graph whose weak dual is a path).
A Topological Code for Plane Images
Venue: arXiv cs.CV 2012
Year: 2012

It is proposed a new code for contours of plane images. This code was applied for optical character recognition of printed and handwritten characters. One can apply it to recognition of any visual images.
An Improved Lower Bound for Stack Sorting
Venue: arXiv cs.DM 2012
Year: 2012

We consider the problem of sorting elements on a series of stacks, introduced by Tarjan and Knuth. We improve the asymptotic lower bound for the number of stacks necessary to sort $n$ elements to $0.561 \log_2 n + O(1)$. This is the first significant improvement since the previous lower bound, $1/2 \log_2 n + O(1)$, was established by Knuth in 1972.
Compressed Sensing Recoverability In Imaging Modalities
Venue: arXiv cs.IT 2012
Year: 2012

The paper introduces a framework for the recoverability analysis in compressive sensing for imaging applications such as CI cameras, rapid MRI and coded apertures. This is done using the fact that the Spherical Section Property (SSP) of a sensing matrix provides a lower bound for unique sparse recovery condition. The lower bound is evaluated for different sampling paradigms adopted from the aforementioned imaging modalities. In particular, a platform is provided to analyze the well-posedness of sub-sampling patterns commonly used in practical scenarios. The effectiveness of the various designed patterns for sparse image recovery is studied through numerical experiments.
mqr-tree: A 2-dimensional Spatial Access Method
Venue: arXiv cs.DB 2012
Year: 2012

In this paper, we propose the mqr-tree, a two-dimensional spatial access method that organizes spatial objects in a two-dimensional node and based on their spatial relationships. Previously proposed spatial access methods that attempt to maintain spatial relationships between objects in their structures are limited in their incorporation of existing one-dimensional spatial access methods, or have lower space utilization in its nodes, and higher tree height, overcoverage and overlap than is necessary. The mqr-tree utilizes a node organization, set of spatial relationship rules and insertion strategy in order to gain significant improvements in overlap and overcoverage. In addition, other desirable properties are identified as a result of the chosen node organization and insertion strategies. In particular, zero overlap is achieved when the mqr-tree is used to index point data. A comparison of the mqr-tree insertion strategy versus the R-tree shows significant improvements in overlap and overcoverage, with comparable space utilization. In addition, a comparison of region searching shows that the mqr-tree achieves a lower number of disk accesses in many cases
A Note on the Complexity of Model-Checking Bounded Multi-Pushdown Systems
Venue: arXiv cs.LO 2012
Year: 2012

In this note, we provide complexity characterizations of model checking multi-pushdown systems. Multi-pushdown systems model recursive concurrent programs in which any sequential process has a finite control. We consider three standard notions for boundedness: context boundedness, phase boundedness and stack ordering. The logical formalism is a linear-time temporal logic extending well-known logic CaRet but dedicated to multi-pushdown systems in which abstract operators (related to calls and returns) such as those for next-time and until are parameterized by stacks. We show that the problem is EXPTIME-complete for context-bounded runs and unary encoding of the number of context switches; we also prove that the problem is 2EXPTIME-complete for phase-bounded runs and unary encoding of the number of phase switches. In both cases, the value k is given as an input (whence it is not a constant of the model-checking problem), which makes a substantial difference in the complexity. In certain cases, our results improve previous complexity results.