OpenRaiser/Intern-Atlas huggingface dataset:
Leveraging Software Architectures to Guide and Verify the Development of Sense/Compute/Control Applications
Venue: arXiv cs.PL 2011
Year: 2011

A software architecture describes the structure of a computing system by specifying software components and their interactions. Mapping a software architecture to an implementation is a well known challenge. A key element of this mapping is the architecture's description of the data and control-flow interactions between components. The characterization of these interactions can be rather abstract or very concrete, providing more or less implementation guidance, programming support, and static verification. In this paper, we explore one point in the design space between abstract and concrete component interaction specifications. We introduce a notion of behavioral contract that expresses the set of allowed interactions between components, describing both data and control-flow constraints. This declaration is part of the architecture description, allows generation of extensive programming support, and enables various verifications. We instantiate our approach in an architecture description language for the domain of Sense/Compute/Control applications, and describe associated compilation and verification strategies.
MDA-based ATL transformation to generate MVC 2 web models
Venue: arXiv cs.SE 2011
Year: 2011

Development and maintenance of Web application is still a complex and error-prone process. We need integrated techniques and tool support for automated generation of Web systems and a ready prescription for easy maintenance. The MDA approach proposes an architecture taking into account the development and maintenance of large and complex software. In this paper, we apply MDA approach for generating PSM from UML design to MVC 2Web implementation. That is why we have developed two meta-models handling UML class diagrams and MVC 2 Web applications, then we have to set up transformation rules. These last are expressed in ATL language. To specify the transformation rules (especially CRUD methods) we used a UML profiles. To clearly illustrate the result generated by this transformation, we converted the XMI file generated in an EMF (Eclipse Modeling Framework) model.
On the nonexistence of $[\binom{2m}{m-1}, 2m, \binom{2m-1}{m-1}]$, $m$ odd, complex orthogonal design
Venue: arXiv cs.IT 2011
Year: 2011

Complex orthogonal designs (CODs) are used to construct space-time block codes. COD $\mathcal{O}_z$ with parameter $[p, n, k]$ is a $p\times n$ matrix, where nonzero entries are filled by $\pm z_i$ or $\pm z^*_i$, $i = 1, 2,..., k$, such that $\mathcal{O}^H_z \mathcal{O}_z = (|z_1|^2+|z_2|^2+...+|z_k|^2)I_{n \times n}$. Adams et al. in "The final case of the decoding delay problem for maximum rate complex orthogonal designs," IEEE Trans. Inf. Theory, vol. 56, no. 1, pp. 103-122, Jan. 2010, first proved the nonexistence of $[\binom{2m}{m-1}, 2m, \binom{2m-1}{m-1}]$, $m$ odd, COD. Combining with the previous result that decoding delay should be an integer multiple of $\binom{2m}{m-1}$, they solved the final case $n \equiv 2 \pmod 4$ of the decoding delay problem for maximum rate complex orthogonal designs. In this paper, we give another proof of the nonexistence of COD with parameter $[\binom{2m}{m-1}, 2m, \binom{2m-1}{m-1}]$, $m$ odd. Our new proof is based on the uniqueness of $[\binom{2m}{m-1}, 2m-1, \binom{2m-1}{m-1}]$ under equivalence operation, where an explicit-form representation is proposed to help the proof. Then, by proving it's impossible to add an extra orthogonal column on COD $[\binom{2m}{m-1}, 2m-1, \binom{2m-1}{m-1}]$ when $m$ is odd, we complete the proof of the nonexistence of COD $[\binom{2m}{m-1}, 2m, \binom{2m-1}{m-1}]$.
Sufficient conditions for the genericity of feedback stabilisability of switching systems via Lie-algebraic solvability
Venue: arXiv cs.SY 2011
Year: 2011

This paper addresses the stabilisation of discrete-time switching linear systems (DTSSs) with control inputs under arbitrary switching, based on the existence of a common quadratic Lyapunov function (CQLF). The authors have begun a line of work dealing with control design based on the Lie-algebraic solvability property. The present paper expands on earlier work by deriving sufficient conditions under which the closed-loop system can be caused to satisfy the Lie-algebraic solvability property generically, i.e. for almost every set of system parameters, furthermore admitting straightforward and efficient numerical implementation.
On the use of reference points for the biobjective Inventory Routing Problem
Venue: arXiv cs.AI 2011
Year: 2011

The article presents a study on the biobjective inventory routing problem. Contrary to most previous research, the problem is treated as a true multi-objective optimization problem, with the goal of identifying Pareto-optimal solutions. Due to the hardness of the problem at hand, a reference point based optimization approach is presented and implemented into an optimization and decision support system, which allows for the computation of a true subset of the optimal outcomes. Experimental investigation involving local search metaheuristics are conducted on benchmark data, and numerical results are reported and analyzed.
Reconstruction of sequential data with density models
Venue: arXiv cs.LG 2011
Year: 2011

We introduce the problem of reconstructing a sequence of multidimensional real vectors where some of the data are missing. This problem contains regression and mapping inversion as particular cases where the pattern of missing data is independent of the sequence index. The problem is hard because it involves possibly multivalued mappings at each vector in the sequence, where the missing variables can take more than one value given the present variables; and the set of missing variables can vary from one vector to the next. To solve this problem, we propose an algorithm based on two redundancy assumptions: vector redundancy (the data live in a low-dimensional manifold), so that the present variables constrain the missing ones; and sequence redundancy (e.g. continuity), so that consecutive vectors constrain each other. We capture the low-dimensional nature of the data in a probabilistic way with a joint density model, here the generative topographic mapping, which results in a Gaussian mixture. Candidate reconstructions at each vector are obtained as all the modes of the conditional distribution of missing variables given present variables. The reconstructed sequence is obtained by minimising a global constraint, here the sequence length, by dynamic programming. We present experimental results for a toy problem and for inverse kinematics of a robot arm.
Design of an Optical Character Recognition System for Camera-based Handheld Devices
Venue: arXiv cs.CV 2011
Year: 2011

This paper presents a complete Optical Character Recognition (OCR) system for camera captured image/graphics embedded textual documents for handheld devices. At first, text regions are extracted and skew corrected. Then, these regions are binarized and segmented into lines and characters. Characters are passed into the recognition module. Experimenting with a set of 100 business card images, captured by cell phone camera, we have achieved a maximum recognition accuracy of 92.74%. Compared to Tesseract, an open source desktop-based powerful OCR engine, present recognition accuracy is worth contributing. Moreover, the developed technique is computationally efficient and consumes low memory so as to be applicable on handheld devices.
Packing-Based Approximation Algorithm for the k-Set Cover Problem
Venue: arXiv cs.DS 2011
Year: 2011

We present a packing-based approximation algorithm for the $k$-Set Cover problem. We introduce a new local search-based $k$-set packing heuristic, and call it Restricted $k$-Set Packing. We analyze its tight approximation ratio via a complicated combinatorial argument. Equipped with the Restricted $k$-Set Packing algorithm, our $k$-Set Cover algorithm is composed of the $k$-Set Packing heuristic \cite{schrijver} for $k\geq 7$, Restricted $k$-Set Packing for $k=6,5,4$ and the semi-local $(2,1)$-improvement \cite{furer} for 3-Set Cover. We show that our algorithm obtains a tight approximation ratio of $H_k-0.6402+Θ(\frac{1}{k})$, where $H_k$ is the $k$-th harmonic number. For small $k$, our results are 1.8667 for $k=6$, 1.7333 for $k=5$ and 1.5208 for $k=4$. Our algorithm improves the currently best approximation ratio for the $k$-Set Cover problem of any $k\geq 4$.
Near Optimality in Covering and Packing Games by Exposing Global Information
Venue: arXiv cs.GT 2011
Year: 2011

Covering and packing problems can be modeled as games to encapsulate interesting social and engineering settings. These games have a high Price of Anarchy in their natural formulation. However, existing research applicable to specific instances of these games has only been able to prove fast convergence to arbitrary equilibria. This paper studies general classes of covering and packing games with learning dynamics models that incorporate a central authority who broadcasts weak, socially beneficial signals to agents that otherwise only use local information in their decision-making. Rather than illustrating convergence to an arbitrary equilibrium that may have very high social cost, we show that these systems quickly achieve near-optimal performance. In particular, we show that in the public service advertising model, reaching a small constant fraction of the agents is enough to bring the system to a state within a log n factor of optimal in a broad class of set cover and set packing games or a constant factor of optimal in the special cases of vertex cover and maximum independent set, circumventing social inefficiency of bad local equilibria that could arise without a central authority. We extend these results to the learn-then-decide model, in which agents use any of a broad class of learning algorithms to decide in a given round whether to behave according to locally optimal behavior or the behavior prescribed by the broadcast signal. The new techniques we use for analyzing these games could be of broader interest for analyzing more general classic optimization problems in a distributed fashion.
Generalised Object Detection and Semantic Analysis: Casino Example using Matlab
Venue: arXiv cs.CV 2011
Year: 2011

Matlab version 7.1 had been used to detect playing cards on a Casino table and the suits and ranks of these cards had been identified. The process gives an example of an application of computer vision to a problem where rectangular objects are to be detected and the information content of the objects are extracted out. In the case of playing cards, it is the suit and rank of each card. The image processing system is done in two passes. Pass 1 detects rectangular shapes and template matched with a template of the left and right edges of the cards. Pass 2 extracts the suit and rank of the cards by matching the top left portion of the card that contains both rank and suit information, with stored templates of ranks and suits of the playing cards using a series of if-then statements.
An Algorithmic Approach to Information and Meaning
Venue: arXiv cs.IT 2011
Year: 2011

I will survey some matters of relevance to a philosophical discussion of information, taking into account developments in algorithmic information theory (AIT). I will propose that meaning is deep in the sense of Bennett's logical depth, and that algorithmic probability may provide the stability needed for a robust algorithmic definition of meaning, one that takes into consideration the interpretation and the recipient's own knowledge encoded in the story attached to a message.
Monitoring Breathing via Signal Strength in Wireless Networks
Venue: arXiv cs.NI 2011
Year: 2011

This paper shows experimentally that standard wireless networks which measure received signal strength (RSS) can be used to reliably detect human breathing and estimate the breathing rate, an application we call "BreathTaking". We show that although an individual link cannot reliably detect breathing, the collective spectral content of a network of devices reliably indicates the presence and rate of breathing. We present a maximum likelihood estimator (MLE) of breathing rate, amplitude, and phase, which uses the RSS data from many links simultaneously. We show experimental results which demonstrate that reliable detection and frequency estimation is possible with 30 seconds of data, within 0.3 breaths per minute (bpm) RMS error. Use of directional antennas is shown to improve robustness to motion near the network.
A linear-time algorithm for the strong chromatic index of Halin graphs
Venue: arXiv cs.DS 2011
Year: 2011

We show that there exists a linear-time algorithm that computes the strong chromatic index of Halin graphs.
Gaussian Two-way Relay Channel with Private Information for the Relay
Venue: arXiv cs.IT 2011
Year: 2011

We introduce a generalized two-way relay channel where two sources exchange information (not necessarily of the same rate) with help from a relay, and each source additionally sends private information to the relay. We consider the Gaussian setting where all point-to-point links are Gaussian channels. For this channel, we consider a two-phase protocol consisting of a multiple access channel (MAC) phase and a broadcast channel (BC) phase. We propose a general decode-and-forward (DF) scheme where the MAC phase is related to computation over MAC, while the BC phase is related to BC with receiver side information. In the MAC phase, we time share a capacity-achieving code for the MAC and a superposition code with a lattice code as its component code. We show that the proposed DF scheme is near optimal for any channel conditions, in that it achieves rates within half bit of the capacity region of the two-phase protocol.
Clustering of Mobile Ad Hoc Networks: An Adaptive Broadcast Period Approach
Venue: arXiv cs.DC 2011
Year: 2011

Organization, scalability and routing have been identified as key problems hindering viability and commercial success of mobile ad hoc networks. Clustering of mobile nodes among separate domains has been proposed as an efficient approach to address those issues. In this work, we introduce an efficient distributed clustering algorithm that uses both location and energy metrics for cluster formation. Our proposed solution mainly addresses cluster stability, manageability and energy efficiency issues. Also, unlike existing active clustering methods, our algorithm relieves the network from the unnecessary burden of control messages broadcasting, especially for relatively static network topologies. This is achieved through adapting broadcast period according to mobile nodes mobility pattern. The efficiency, scalability and competence of our algorithm against alternative approaches have been demonstrated through simulation results.
k-means Approach to the Karhunen-Loeve Transform
Venue: arXiv cs.IT 2011
Year: 2011

We present a simultaneous generalization of the well-known Karhunen-Loeve (PCA) and k-means algorithms. The basic idea lies in approximating the data with k affine subspaces of a given dimension n. In the case n=0 we obtain the classical k-means, while for k=1 we obtain PCA algorithm. We show that for some data exploration problems this method gives better result then either of the classical approaches.
Approximate Distance Oracles with Improved Preprocessing Time
Venue: arXiv cs.DM 2011
Year: 2011

Given an undirected graph $G$ with $m$ edges, $n$ vertices, and non-negative edge weights, and given an integer $k\geq 1$, we show that for some universal constant $c$, a $(2k-1)$-approximate distance oracle for $G$ of size $O(kn^{1 + 1/k})$ can be constructed in $O(\sqrt km + kn^{1 + c/\sqrt k})$ time and can answer queries in $O(k)$ time. We also give an oracle which is faster for smaller $k$. Our results break the quadratic preprocessing time bound of Baswana and Kavitha for all $k\geq 6$ and improve the $O(kmn^{1/k})$ time bound of Thorup and Zwick except for very sparse graphs and small $k$. When $m = Ω(n^{1 + c/\sqrt k})$ and $k = O(1)$, our oracle is optimal w.r.t.\ both stretch, size, preprocessing time, and query time, assuming a widely believed girth conjecture by Erdős.
Energy-Efficient Full Diversity Collaborative Unitary Space-Time Block Code Design via Unique Factorization of Signals
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, a novel concept called a \textit{uniquely factorable constellation pair} (UFCP) is proposed for the systematic design of a noncoherent full diversity collaborative unitary space-time block code by normalizing two Alamouti codes for a wireless communication system having two transmitter antennas and a single receiver antenna. It is proved that such a unitary UFCP code assures the unique identification of both channel coefficients and transmitted signals in a noise-free case as well as full diversity for the noncoherent maximum likelihood (ML) receiver in a noise case. To further improve error performance, an optimal unitary UFCP code is designed by appropriately and uniquely factorizing a pair of energy-efficient cross quadrature amplitude modulation (QAM) constellations to maximize the coding gain subject to a transmission bit rate constraint. After a deep investigation of the fractional coding gain function, a technical approach developed in this paper to maximizing the coding gain is to carefully design an energy scale to compress the first three largest energy points in the corner of the QAM constellations in the denominator of the objective as well as carefully design a constellation triple forming two UFCPs, with one collaborating with the other two so as to make the accumulated minimum Euclidean distance along the two transmitter antennas in the numerator of the objective as large as possible and at the same time, to avoid as many corner points of the QAM constellations with the largest energy as possible to achieve the minimum of the numerator. In other words, the optimal coding gain is attained by intelligent constellations collaboration and efficient energy compression.
Offering A Product Recommendation System in E-commerce
Venue: arXiv cs.IR 2011
Year: 2011

This paper proposes a number of explicit and implicit ratings in product recommendation system for Business-to-customer e-commerce purposes. The system recommends the products to a new user. It depends on the purchase pattern of previous users whose purchase pattern is close to that of a user who asks for a recommendation. The system is based on weighted cosine similarity measure to find out the closest user profile among the profiles of all users in database. It also implements Association rule mining rule in recommending the products. Also, this product recommendation system takes into consideration the time of transaction of purchasing the items, thus eliminating sequence recognition problem. Experimental result shows for implicit rating, the proposed method gives acceptable performance in recommending the products. It also shows introduction of association rule improves the performance measure of recommendation system.
Subspace Alignment Chains and the Degrees of Freedom of the Three-User MIMO Interference Channel
Venue: arXiv cs.IT 2011
Year: 2011

We show that the 3 user M_T x M_R MIMO interference channel has d(M,N)=min(M/(2-1/k),N/(2+1/k)) degrees of freedom (DoF) normalized by time, frequency, and space dimensions, where M=min(M_T,M_R), N=max(M_T,M_R), k=ceil{M/(N-M)}. While the DoF outer bound is established for every M_T, M_R value, the achievability is established in general subject to normalization with respect to spatial-extensions. Given spatial-extensions, the achievability relies only on linear beamforming based interference alignment schemes with no need for time/frequency extensions. In the absence of spatial extensions, we show through examples how essentially the same scheme may be applied over time/frequency extensions. The central new insight to emerge from this work is the notion of subspace alignment chains as DoF bottlenecks. The DoF value d(M,N) is a piecewise linear function of M,N, with either M or N being the bottleneck within each linear segment. The corner points of these piecewise linear segments correspond to A={1/2,2/3,3/4,...} and B={1/3,3/5,5/7,...}. The set A contains all values of M/N and only those for which there is redundancy in both M and N. The set B contains all values of M/N and only those for which there is no redundancy in either M or N. Our results settle the feasibility of linear interference alignment, introduced by Cenk et al., for the 3 user M_T x M_R MIMO interference channel, completely for all values of M_T, M_R. Specifically, the linear interference alignment problem (M_T x M_R, d)^3 (as defined in previous work by Cenk et al.) is feasible if and only if d<=floor{d(M,N)}. With and only with the exception of the values M/N\in B, we show that for every M/N value there are proper systems that are not feasible. Our results show that M/N\in A are the only values for which there is no DoF benefit of joint processing among co-located antennas at the transmitters or receivers.
Vertical Handover decision schemes using SAW and WPM for Network selection in Heterogeneous Wireless Networks
Venue: arXiv cs.NI 2011
Year: 2011

Seamless continuity is the main goal and challenge in fourth generation Wireless networks (FGWNs), to achieve seamless connectivity "HANDOVER" technique is used,Handover mechanism are mainly used when a mobile terminal(MT) is in overlapping area for service continuity. In Heterogeneous wireless networks main challenge is continual connection among the different networks like WiFi, WiMax, WLAN, WPAN etc. In this paper, Vertical handover decision schemes are compared, Simple Additive Weighting method (SAW) and Weighted product model (WPM) are used to choose the best network from the available Visitor networks(VTs) for the continuous connection by the mobile terminal. In our work we mainly concentrated to the handover decision phase and to reduce the processing delay in the period of handover. In this paper both SAW and WPM methods are compared with the Qos parameters of the mobile terminal (MT) to connect with the best network. Keywords: Handover, Vertical handover decision schemes, Simple additive weighting, Weight product method.
A Probabilistic Approach to Pronunciation by Analogy
Venue: arXiv cs.CL 2011
Year: 2011

The relationship between written and spoken words is convoluted in languages with a deep orthography such as English and therefore it is difficult to devise explicit rules for generating the pronunciations for unseen words. Pronunciation by analogy (PbA) is a data-driven method of constructing pronunciations for novel words from concatenated segments of known words and their pronunciations. PbA performs relatively well with English and outperforms several other proposed methods. However, the best published word accuracy of 65.5% (for the 20,000 word NETtalk corpus) suggests there is much room for improvement in it. Previous PbA algorithms have used several different scoring strategies such as the product of the frequencies of the component pronunciations of the segments, or the number of different segmentations that yield the same pronunciation, and different combinations of these methods, to evaluate the candidate pronunciations. In this article, we instead propose to use a probabilistically justified scoring rule. We show that this principled approach alone yields better accuracy (66.21% for the NETtalk corpus) than any previously published PbA algorithm. Furthermore, combined with certain ad hoc modifications motivated by earlier algorithms, the performance climbs up to 66.6%, and further improvements are possible by combining this method with other methods.