OpenRaiser/Intern-Atlas huggingface dataset:
Diversity of MIMO Linear Precoding
Venue: arXiv cs.IT 2012
Year: 2012

Linear precoding is a relatively simple method of MIMO signaling that can also be optimal in certain special cases. This paper is dedicated to high-SNR analysis of MIMO linear precoding. The Diversity-Multiplexing Tradeoff (DMT) of a number of linear precoders is analyzed. Furthermore, since the diversity at finite rate (also known as the fixed-rate regime, corresponding to multiplexing gain of zero) does not always follow from the DMT, linear precoders are also analyzed for their diversity at fixed rates. In several cases, the diversity at multiplexing gain of zero is found not to be unique, but rather to depend on spectral efficiency. The analysis includes the zero-forcing (ZF), regularized ZF, matched filtering and Wiener filtering precoders. We calculate the DMT of ZF precoding under two common design approaches, namely maximizing the throughput and minimizing the transmit power. It is shown that regularized ZF (RZF) or Matched filter (MF) suffer from error floors for all positive multiplexing gains. However, in the fixed rate regime, RZF and MF precoding achieve full diversity up to a certain spectral efficiency and zero diversity at rates above it. When the regularization parameter in the RZF is optimized in the MMSE sense, the structure is known as the Wiener precoder which in the fixed-rate regime is shown to have diversity that depends not only on the number of antennas, but also on the spectral efficiency. The diversity in the presence of both precoding and equalization is also analyzed.
Real-time detection and tracking of multiple objects with partial decoding in H.264/AVC bitstream domain
Venue: arXiv cs.MM 2012
Year: 2012

In this paper, we show that we can apply probabilistic spatiotemporal macroblock filtering (PSMF) and partial decoding processes to effectively detect and track multiple objects in real time in H.264|AVC bitstreams with stationary background. Our contribution is that our method cannot only show fast processing time but also handle multiple moving objects that are articulated, changing in size or internally have monotonous color, even though they contain a chaotic set of non-homogeneous motion vectors inside. In addition, our partial decoding process for H.264|AVC bitstreams enables to improve the accuracy of object trajectories and overcome long occlusion by using extracted color information.
Data Mining Applications: A comparative Study for Predicting Student's performance
Venue: arXiv cs.IR 2012
Year: 2012

Knowledge Discovery and Data Mining (KDD) is a multidisciplinary area focusing upon methodologies for extracting useful knowledge from data and there are several useful KDD tools to extracting the knowledge. This knowledge can be used to increase the quality of education. But educational institution does not use any knowledge discovery process approach on these data. Data mining can be used for decision making in educational system. A decision tree classifier is one of the most widely used supervised learning methods used for data exploration based on divide & conquer technique. This paper discusses use of decision trees in educational data mining. Decision tree algorithms are applied on students' past performance data to generate the model and this model can be used to predict the students' performance. It helps earlier in identifying the dropouts and students who need special attention and allow the teacher to provide appropriate advising/counseling.
A Note on Minimum-Sum Coverage by Aligned Disks
Venue: arXiv cs.CG 2012
Year: 2012

In this paper, we consider a facility location problem to find a minimum-sum coverage of n points by disks centered at a fixed line. The cost of a disk with radius r has a form of a non-decreasing function f(r) = r^a for any a >= 1. The goal is to find a set of disks under Lp metric such that the disks are centered on the x-axis, their union covers n points, and the sum of the cost of the disks is minimized. Alt et al. [1] presented an algorithm in O(n^4 log n) time for any a > 1 under any Lp metric. We present a faster algorithm for this problem in O(n^2 log n) time for any a > 1 and any Lp metric.
Automated Generation of User Guidance by Combining Computation and Deduction
Venue: arXiv cs.LO 2012
Year: 2012

Herewith, a fairly old concept is published for the first time and named "Lucas Interpretation". This has been implemented in a prototype, which has been proved useful in educational practice and has gained academic relevance with an emerging generation of educational mathematics assistants (EMA) based on Computer Theorem Proving (CTP). Automated Theorem Proving (ATP), i.e. deduction, is the most reliable technology used to check user input. However ATP is inherently weak in automatically generating solutions for arbitrary problems in applied mathematics. This weakness is crucial for EMAs: when ATP checks user input as incorrect and the learner gets stuck then the system should be able to suggest possible next steps. The key idea of Lucas Interpretation is to compute the steps of a calculation following a program written in a novel CTP-based programming language, i.e. computation provides the next steps. User guidance is generated by combining deduction and computation: the latter is performed by a specific language interpreter, which works like a debugger and hands over control to the learner at breakpoints, i.e. tactics generating the steps of calculation. The interpreter also builds up logical contexts providing ATP with the data required for checking user input, thus combining computation and deduction. The paper describes the concepts underlying Lucas Interpretation so that open questions can adequately be addressed, and prerequisites for further work are provided.
Isabelle/PIDE as Platform for Educational Tools
Venue: arXiv cs.LO 2012
Year: 2012

The Isabelle/PIDE platform addresses the question whether proof assistants of the LCF family are suitable as technological basis for educational tools. The traditionally strong logical foundations of systems like HOL, Coq, or Isabelle have so far been counter-balanced by somewhat inaccessible interaction via the TTY (or minor variations like the well-known Proof General / Emacs interface). Thus the fundamental question of math education tools with fully-formal background theories has often been answered negatively due to accidental weaknesses of existing proof engines. The idea of "PIDE" (which means "Prover IDE") is to integrate existing provers like Isabelle into a larger environment, that facilitates access by end-users and other tools. We use Scala to expose the proof engine in ML to the JVM world, where many user-interfaces, editor frameworks, and educational tools already exist. This shall ultimately lead to combined mathematical assistants, where the logical engine is in the background, without obstructing the view on applications of formal methods, formalized mathematics, and math education in particular.
Fault Based Techniques for Testing Boolean Expressions: A Survey
Venue: arXiv cs.SE 2012
Year: 2012

Boolean expressions are major focus of specifications and they are very much prone to introduction of faults, this survey presents various fault based testing techniques. It identifies that the techniques differ in their fault detection capabilities and generation of test suite. The various techniques like Cause effect graph, meaningful impact strategy, Branch Operator Strategy (BOR), BOR+MI, MUMCUT, Modified Condition/ Decision Coverage (MCDC) has been considered. This survey describes the basic algorithms and fault categories used by these strategies for evaluating their performance. Finally, it contains short summaries of the papers that use Boolean expressions used to specify the requirements for detecting faults. These techniques have been empirically evaluated by various researchers on a simplified safety related real time control system.
Fabrication of Message Digest to Authenticate Audio Signals with Alternation of Coefficients of Harmonics in Multi-Stages (MDAC)
Venue: arXiv cs.CR 2012
Year: 2012

Providing security to audio songs for maintaining its intellectual property right (IPR) is one of chanllenging fields in commercial world especially in creative industry. In this paper, an effective approach has been incorporated to fabricate authentication of audio song through application of message digest method with alternation of coefficients of harmonics in multi-stages of higher frequency domain without affecting its audible quality. Decomposing constituent frequency components of song signal using Fourier transform with generating secret code via applying message digest followed by alternating coefficients of specific harmonics in multi-stages generates a secret code and this unique code is utilized to detect the originality of the song. A comparative study has been made with similar existing techniques and experimental results are also supported with mathematical formula based on Microsoft WAVE (".wav") stereo sound file.
Identifying Discriminating Network Motifs in YouTube Spam
Venue: arXiv cs.SI 2012
Year: 2012

Like other social media websites, YouTube is not immune from the attention of spammers. In particular, evidence can be found of attempts to attract users to malicious third-party websites. As this type of spam is often associated with orchestrated campaigns, it has a discernible network signature, based on networks derived from comments posted by users to videos. In this paper, we examine examples of different YouTube spam campaigns of this nature, and use a feature selection process to identify network motifs that are characteristic of the corresponding campaign strategies. We demonstrate how these discriminating motifs can be used as part of a network motif profiling process that tracks the activity of spam user accounts over time, enabling the process to scale to larger networks.
Computing Lempel-Ziv Factorization Online
Venue: arXiv cs.DS 2012
Year: 2012

We present an algorithm which computes the Lempel-Ziv factorization of a word $W$ of length $n$ on an alphabet $Σ$ of size $σ$ online in the following sense: it reads $W$ starting from the left, and, after reading each $r = O(\log_σ n)$ characters of $W$, updates the Lempel-Ziv factorization. The algorithm requires $O(n \log σ)$ bits of space and O(n \log^2 n) time. The basis of the algorithm is a sparse suffix tree combined with wavelet trees.
Enhancing Navigation on Wikipedia with Social Tags
Venue: arXiv cs.IR 2012
Year: 2012

Social tagging has become an interesting approach to improve search and navigation over the actual Web, since it aggregates the tags added by different users to the same resource in a collaborative way. This way, it results in a list of weighted tags describing its resource. Combined to a classical taxonomic classification system such as that by Wikipedia, social tags can enhance document navigation and search. On the one hand, social tags suggest alternative navigation ways, including pivot-browsing, popularity-driven navigation, and filtering. On the other hand, it provides new metadata, sometimes uncovered by documents' content, that can substantially improve document search. In this work, the inclusion of an interface to add user-defined tags describing Wikipedia articles is proposed, as a way to improve article navigation and retrieval. As a result, a prototype on applying tags over Wikipedia is proposed in order to evaluate its effectiveness.
Risk-Driven Compliant Access Controls for Clouds
Venue: arXiv cs.DC 2012
Year: 2012

There is widespread agreement that cloud computing have proven cost cutting and agility benefits. However, security and regulatory compliance issues are continuing to challenge the wide acceptance of such technology both from social and commercial stakeholders. An important facture behind this is the fact that clouds and in particular public clouds are usually deployed and used within broad geographical or even international domains. This implies that the exchange of private and other protected data within the cloud environment would be governed by multiple jurisdictions. These jurisdictions have a great degree of harmonisation; however, they present possible conflicts that are hard to negotiate at run time. So far, important efforts were played in order to deal with regulatory compliance management for large distributed systems. However, measurable solutions are required for the context of cloud. In this position paper, we are suggesting an approach that starts with a conceptual model of explicit regulatory requirements for exchanging private data on a multijurisdictional environment and build on it in order to define metrics for non-compliance or, in other terms, risks to compliance. These metrics will be integrated within usual data access-control policies and will be checked at policy analysis time before a decision to allow/deny the data access is made.
An Architecture for Integrated Intelligence in Urban Management using Cloud Computing
Venue: arXiv cs.DC 2012
Year: 2012

With the emergence of new methodologies and technologies it has now become possible to manage large amounts of environmental sensing data and apply new integrated computing models to acquire information intelligence. This paper advocates the application of cloud capacity to support the information, communication and decision making needs of a wide variety of stakeholders in the complex business of the management of urban and regional development. The complexity lies in the interactions and impacts embodied in the concept of the urban-ecosystem at various governance levels. This highlights the need for more effective integrated environmental management systems. This paper offers a user-orientated approach based on requirements for an effective management of the urban-ecosystem and the potential contributions that can be supported by the cloud computing community. Furthermore, the commonality of the influence of the drivers of change at the urban level offers the opportunity for the cloud computing community to develop generic solutions that can serve the needs of hundreds of cities from Europe and indeed globally.
Hierarchical Resource Allocation in Femtocell Networks using Graph Algorithms
Venue: arXiv cs.IT 2012
Year: 2012

This paper presents a hierarchical approach to resource allocation in open-access femtocell networks. The major challenge in femtocell networks is interference management which in our system, based on the Long Term Evolution (LTE) standard, translates to which user should be allocated which physical resource block (or fraction thereof) from which femtocell access point (FAP). The globally optimal solution requires integer programming and is mathematically intractable. We propose a hierarchical three-stage solution: first, the load of each FAP is estimated considering the number of users connected to the FAP, their average channel gain and required data rates. Second, based on each FAP's load, the physical resource blocks (PRBs) are allocated to FAPs in a manner that minimizes the interference by coloring the modified interference graph. Finally, the resource allocation is performed at each FAP considering users' instantaneous channel gain. The two major advantages of this suboptimal approach are the significantly reduced computation complexity and the fact that the proposed algorithm only uses information that is already likely to be available at the nodes executing the relevant optimization step. The performance of the proposed solution is evaluated in networks based on the LTE standard.
The warm-start bias of Yelp ratings
Venue: arXiv cs.SI 2012
Year: 2012

Yelp ratings are often viewed as a reputation metric for local businesses. In this paper we study how Yelp ratings evolve over time. Our main finding is that on average the first ratings that businesses receive overestimate their eventual reputation. In particular, the first review that a business receives in our dataset averages 4.1 stars, while the 20th review averages just 3.69 stars. This significant warm-start bias which may be attributed to the limited exposure of a business in its first steps may mask analysis performed on ratings and reputational ramifications. Therefore, we study techniques to identify and correct for this bias. Further, we perform a case study to explore the effect of a Groupon deal on the merchant's subsequent ratings and show both that previous research has overestimated Groupon's effect to merchants' reputation and that average ratings anticorrelate with the number of reviews received. Our analysis points to the importance of identifying and removing biases from Yelp reviews.
Stochastic Vehicle Routing with Recourse
Venue: arXiv cs.DS 2012
Year: 2012

We study the classic Vehicle Routing Problem in the setting of stochastic optimization with recourse. StochVRP is a two-stage optimization problem, where demand is satisfied using two routes: fixed and recourse. The fixed route is computed using only a demand distribution. Then after observing the demand instantiations, a recourse route is computed -- but costs here become more expensive by a factor lambda. We present an O(log^2 n log(n lambda))-approximation algorithm for this stochastic routing problem, under arbitrary distributions. The main idea in this result is relating StochVRP to a special case of submodular orienteering, called knapsack rank-function orienteering. We also give a better approximation ratio for knapsack rank-function orienteering than what follows from prior work. Finally, we provide a Unique Games Conjecture based omega(1) hardness of approximation for StochVRP, even on star-like metrics on which our algorithm achieves a logarithmic approximation.
Algebraic Fast-Decodable Relay Codes for Distributed Communications
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, fast-decodable lattice code constructions are designed for the nonorthogonal amplify-and-forward (NAF) multiple-input multiple-output (MIMO) channel. The constructions are based on different types of algebraic structures, e.g. quaternion division algebras. When satisfying certain properties, these algebras provide us with codes whose structure naturally reduces the decoding complexity. The complexity can be further reduced by shortening the block length, i.e., by considering rectangular codes called less than minimum delay (LMD) codes.
Approximate Counting of Matchings in Sparse Hypergraphs
Venue: arXiv cs.DS 2012
Year: 2012

In this paper we give a fully polynomial randomized approximation scheme (FPRAS) for the number of all matchings in hypergraphs belonging to a class of sparse, uniform hypergraphs. Our method is based on a generalization of the canonical path method to the case of uniform hypergraphs.
A Note on Interference in Random Point Sets
Venue: arXiv cs.CG 2012
Year: 2012

The (maximum receiver-centric) interference of a geometric graph (von Rickenbach etal (2005)) is studied. It is shown that, with high probability, the following results hold for a set, V, of n points independently and uniformly distributed in the unit d-cube, for constant dimension d: (1) there exists a connected graph with vertex set V that has interference O((log n)^{1/3}); (2) no connected graph with vertex set V has interference o((log n)^{1/4}); and (3) the minimum spanning tree of $V$ has interference Theta((\log n)^{1/2}).
Marginality: a numerical mapping for enhanced treatment of nominal and hierarchical attributes
Venue: arXiv cs.AI 2012
Year: 2012

The purpose of statistical disclosure control (SDC) of microdata, a.k.a. data anonymization or privacy-preserving data mining, is to publish data sets containing the answers of individual respondents in such a way that the respondents corresponding to the released records cannot be re-identified and the released data are analytically useful. SDC methods are either based on masking the original data, generating synthetic versions of them or creating hybrid versions by combining original and synthetic data. The choice of SDC methods for categorical data, especially nominal data, is much smaller than the choice of methods for numerical data. We mitigate this problem by introducing a numerical mapping for hierarchical nominal data which allows computing means, variances and covariances on them.
Local Routing in Graphs Embedded on Surfaces of Arbitrary Genus
Venue: arXiv cs.CG 2012
Year: 2012

We present a local routing algorithm which guarantees delivery in all connected graphs embedded on a known surface of genus $g$. The algorithm transports $O(g\log n)$ memory and finishes in time $O(g^2n^2)$, where $n$ is the size of the graph. It requires access to a homology basis for the surface. This algorithm, GFR, may be viewed as a suitable generalization of Face Routing (FR), the well-known algorithm for plane graphs, which we previously showed does {\it not} guarantee delivery in graphs embedded on positive genus surfaces. The problem for such surfaces is the potential presence of homologically non-trivial closed walks which may be traversed by the right-hand rule. We use an interesting mathematical property of homology bases (proven in Lemma \ref{lem:connectFaceBdr}) to show that such walks will not impede GFR. FR is at the base of most routing algorithms used in modern (2D) ad hoc networks: these algorithms all involve additional local techniques to deal with edge-crossings so FR may be applied. GFR should be viewed in the same light, as a base algorithm which could for example be tailored to sensor networks on surfaces in 3D. Currently there are no known efficient local, logarithmic memory algorithms for 3D ad hoc networks. From a theoretical point of view our work suggests that the efficiency advantages from which FR benefits are related to the codimension one nature of an embedded graph in a surface rather than the flatness of that surface (planarity).
Towards Symbolic Model-Based Mutation Testing: Combining Reachability and Refinement Checking
Venue: arXiv cs.SE 2012
Year: 2012

Model-based mutation testing uses altered test models to derive test cases that are able to reveal whether a modelled fault has been implemented. This requires conformance checking between the original and the mutated model. This paper presents an approach for symbolic conformance checking of action systems, which are well-suited to specify reactive systems. We also consider nondeterminism in our models. Hence, we do not check for equivalence, but for refinement. We encode the transition relation as well as the conformance relation as a constraint satisfaction problem and use a constraint solver in our reachability and refinement checking algorithms. Explicit conformance checking techniques often face state space explosion. First experimental evaluations show that our approach has potential to outperform explicit conformance checkers.
Talking quiescence: a rigorous theory that supports parallel composition, action hiding and determinisation
Venue: arXiv cs.SE 2012
Year: 2012

The notion of quiescence - the absence of outputs - is vital in both behavioural modelling and testing theory. Although the need for quiescence was already recognised in the 90s, it has only been treated as a second-class citizen thus far. This paper moves quiescence into the foreground and introduces the notion of quiescent transition systems (QTSs): an extension of regular input-output transition systems (IOTSs) in which quiescence is represented explicitly, via quiescent transitions. Four carefully crafted rules on the use of quiescent transitions ensure that our QTSs naturally capture quiescent behaviour. We present the building blocks for a comprehensive theory on QTSs supporting parallel composition, action hiding and determinisation. In particular, we prove that these operations preserve all the aforementioned rules. Additionally, we provide a way to transform existing IOTSs into QTSs, allowing even IOTSs as input that already contain some quiescent transitions. As an important application, we show how our QTS framework simplifies the fundamental model-based testing theory formalised around ioco.