OpenRaiser/Intern-Atlas huggingface dataset:
SOFA: An Extensible Logical Optimizer for UDF-heavy Dataflows
Venue: arXiv cs.DB 2013
Year: 2013

Recent years have seen an increased interest in large-scale analytical dataflows on non-relational data. These dataflows are compiled into execution graphs scheduled on large compute clusters. In many novel application areas the predominant building blocks of such dataflows are user-defined predicates or functions (UDFs). However, the heavy use of UDFs is not well taken into account for dataflow optimization in current systems. SOFA is a novel and extensible optimizer for UDF-heavy dataflows. It builds on a concise set of properties for describing the semantics of Map/Reduce-style UDFs and a small set of rewrite rules, which use these properties to find a much larger number of semantically equivalent plan rewrites than possible with traditional techniques. A salient feature of our approach is extensibility: We arrange user-defined operators and their properties into a subsumption hierarchy, which considerably eases integration and optimization of new operators. We evaluate SOFA on a selection of UDF-heavy dataflows from different domains and compare its performance to three other algorithms for dataflow optimization. Our experiments reveal that SOFA finds efficient plans, outperforming the best plans found by its competitors by a factor of up to 6.
Exploration in Interactive Personalized Music Recommendation: A Reinforcement Learning Approach
Venue: arXiv cs.MM 2013
Year: 2013

Current music recommender systems typically act in a greedy fashion by recommending songs with the highest user ratings. Greedy recommendation, however, is suboptimal over the long term: it does not actively gather information on user preferences and fails to recommend novel songs that are potentially interesting. A successful recommender system must balance the needs to explore user preferences and to exploit this information for recommendation. This paper presents a new approach to music recommendation by formulating this exploration-exploitation trade-off as a reinforcement learning task called the multi-armed bandit. To learn user preferences, it uses a Bayesian model, which accounts for both audio content and the novelty of recommendations. A piecewise-linear approximation to the model and a variational inference algorithm are employed to speed up Bayesian inference. One additional benefit of our approach is a single unified model for both music recommendation and playlist generation. Both simulation results and a user study indicate strong potential for the new approach.
Rate Adaptation and Admission Control for Video Transmission with Subjective Quality Constraints
Venue: arXiv cs.MM 2013
Year: 2013

Adapting video data rate during streaming can effectively reduce the risk of playback interruptions caused by channel throughput fluctuations. The variations in rate, however, also introduce video quality fluctuations and thus potentially affects viewers' Quality of Experience (QoE). We show how the QoE of video users can be improved by rate adaptation and admission control. We conducted a subjective study wherein we found that viewers' QoE was strongly correlated with the empirical cumulative distribution function (eCDF) of the predicted video quality. Based on this observation, we propose a rate-adaptation algorithm that can incorporate QoE constraints on the empirical cumulative quality distribution per user. We then propose a threshold-based admission control policy to block users whose empirical cumulative quality distribution is not likely to satisfy their QoE constraint. We further devise an online adaptation algorithm to automatically optimize the threshold. Extensive simulation results show that the proposed scheme can reduce network resource consumption by $40\%$ over conventional average-quality maximized rate-adaptation algorithms.
Evaluating the Impact of SDC on the GMRES Iterative Solver
Venue: arXiv cs.DC 2013
Year: 2013

Increasing parallelism and transistor density, along with increasingly tighter energy and peak power constraints, may force exposure of occasionally incorrect computation or storage to application codes. Silent data corruption (SDC) will likely be infrequent, yet one SDC suffices to make numerical algorithms like iterative linear solvers cease progress towards the correct answer. Thus, we focus on resilience of the iterative linear solver GMRES to a single transient SDC. We derive inexpensive checks to detect the effects of an SDC in GMRES that work for a more general SDC model than presuming a bit flip. Our experiments show that when GMRES is used as the inner solver of an inner-outer iteration, it can "run through" SDC of almost any magnitude in the computationally intensive orthogonalization phase. That is, it gets the right answer using faulty data without any required roll back. Those SDCs which it cannot run through, get caught by our detection scheme.
Enhancing Approximations for Regular Reachability Analysis
Venue: arXiv cs.FL 2013
Year: 2013

This paper introduces two mechanisms for computing over-approximations of sets of reachable states, with the aim of ensuring termination of state-space exploration. The first mechanism consists in over-approximating the automata representing reachable sets by merging some of their states with respect to simple syntactic criteria, or a combination of such criteria. The second approximation mechanism consists in manipulating an auxiliary automaton when applying a transducer representing the transition relation to an automaton encoding the initial states. In addition, for the second mechanism we propose a new approach to refine the approximations depending on a property of interest. The proposals are evaluated on examples of mutual exclusion protocols.
Mobile Augmented Reality Applications to Discover New Environments
Venue: arXiv cs.CY 2013
Year: 2013

Although man has become sedentary over time, his wish to travel the world remains as strong as ever. The aim of this paper is to show how techniques based on imagery and Augmented Reality (AR) can prove to be of great help when discovering a new urban environment and observing the evolution of the natural environment. The study's support is naturally the Smartphone which in just a few years has become our most familiar device, which we take with us practically everywhere we go in our daily lives.
A Deterministic Polynomial Space Construction for eps-nets under any Norm
Venue: arXiv cs.CC 2013
Year: 2013

We give a deterministic polynomial space construction for nearly optimal eps-nets with respect to any input n-dimensional convex body K and norm |.|. More precisely, our algorithm can build and iterate over an eps-net of K with respect to |.| in time 2^O(n) x (size of the optimal net) using only poly(n)-space. This improves on previous constructions of Alon et al [STOC 2013] which achieve either a 2^O(n) approximation or an n^O(n) approximation of the optimal net size using 2^n space and poly(n)-space respectively. As in their work, our algorithm relies on the mathematically classical approach of building thin lattice coverings of space, which reduces the task of constructing eps-nets to the problem of enumerating lattice points. Our main technical contribution is a deterministic 2^O(n)-time and poly(n)-space construction of thin lattice coverings of space with respect to any convex body, where enumeration in these lattices can be efficiently performed using poly(n)-space. This also yields the first existential construction of poly(n)-space enumerable thin covering lattices for general convex bodies, which we believe is of independent interest. Our construction combines the use of the M-ellipsoid from convex geometry with lattice sparsification and densification techniques. As an application, we give a 2^O(n)(1+1/eps)^n time and poly(n)-space deterministic algorithm for computing a (1+eps)^n approximation to the volume of a general convex body, which nearly matches the lower bounds for volume estimation in the oracle model (the dependence on eps is larger by a factor 2 in the exponent). This improves on the previous results of Dadush and Vempala [PNAS 2013], which gave the above result only for symmetric bodies and achieved a dependence on eps of (1+log^{5/2}(1/eps)/eps^2)^n.
Robust algorithm for calibration of robotic manipulator model
Venue: arXiv cs.RO 2013
Year: 2013

The paper focuses on the robust identification of geometrical and elastostatic parameters of robotic manipulator. The main attention is paid to the efficiency improvement of the identification algorithm. To increase the identification accuracy, it is proposed to apply the weighted least square technique that employs a new algorithm for assigning of the weighting coefficients. The latter allows taking into account variation of the measurement system precision in different directions and throughout the robot workspace. The advantages of the proposed approach are illustrated by an application example that deals with the elasto-static calibration of industrial robot.
CAD-based approach for identification of elasto-static parameters of robotic manipulators
Venue: arXiv cs.RO 2013
Year: 2013

The paper presents an approach for the identification of elasto-static parameters of a robotic manipulator using the virtual experiments in a CAD environment. It is based on the numerical processing of the data extracted from the finite element analysis results, which are obtained for isolated manipulator links. This approach allows to obtain the desired stiffness matrices taking into account the complex shape of the links, couplings between rotational/translational deflections and particularities of the joints connecting adjacent links. These matrices are integral parts of the manipulator lumped stiffness model that are widely used in robotics due to its high computational efficiency. To improve the identification accuracy, recommendations for optimal settings of the virtual experiments are given, as well as relevant statistical processing techniques are proposed. Efficiency of the developed approach is confirmed by a simulation study that shows that the accuracy in evaluating the stiffness matrix elements is about 0.1%.
The Limits of Depth Reduction for Arithmetic Formulas: It's all about the top fan-in
Venue: arXiv cs.CC 2013
Year: 2013

In recent years, a very exciting and promising method for proving lower bounds for arithmetic circuits has been proposed. This method combines the method of {\it depth reduction} developed in the works of Agrawal-Vinay [AV08], Koiran [Koi12] and Tavenas [Tav13], and the use of the shifted partial derivative complexity measure developed in the works of Kayal [Kay12] and Gupta et al [GKKS13a]. These results inspired a flurry of other beautiful results and strong lower bounds for various classes of arithmetic circuits, in particular a recent work of Kayal et al [KSS13] showing superpolynomial lower bounds for {\it regular} arithmetic formulas via an {\it improved depth reduction} for these formulas. It was left as an intriguing question if these methods could prove superpolynomial lower bounds for general (homogeneous) arithmetic formulas, and if so this would indeed be a breakthrough in arithmetic circuit complexity. In this paper we study the power and limitations of depth reduction and shifted partial derivatives for arithmetic formulas. We do it via studying the class of depth 4 homogeneous arithmetic circuits. We show: (1) the first {\it superpolynomial lower bounds} for the class of homogeneous depth 4 circuits with top fan-in $o(\log n)$. The core of our result is to show {\it improved depth reduction} for these circuits. (2) We show that improved depth reduction {\it is not possible} when the top fan-in is $Ω(\log n)$. In particular this shows that the depth reduction procedure of Koiran and Tavenas [Koi12, Tav13] cannot be improved even for homogeneous formulas, thus strengthening the results of Fournier et al [FLMS13] who showed that depth reduction is tight for circuits, and answering some of the main open questions of [KSS13, FLMS13].
Stiffness modeling of robotic manipulator with gravity compensator
Venue: arXiv cs.RO 2013
Year: 2013

The paper focuses on the stiffness modeling of robotic manipulators with gravity compensators. The main attention is paid to the development of the stiffness model of a spring-based compensator located between sequential links of a serial structure. The derived model allows us to describe the compensator as an equivalent non-linear virtual spring integrated in the corresponding actuated joint. The obtained results have been efficiently applied to the stiffness modeling of a heavy industrial robot of the Kuka family.
Ergodicity of Random Walks on Random DFA
Venue: arXiv cs.FL 2013
Year: 2013

Given a DFA we consider the random walk that starts at the initial state and at each time step moves to a new state by taking a random transition from the current state. This paper shows that for typical DFA this random walk induces an ergodic Markov chain. The notion of typical DFA is formalized by showing that ergodicity holds with high probability when a DFA is sampled uniformly at random from the set of all automata with a fixed number of states. We also show the same result applies to DFA obtained by minimizing typical DFA.
The Degrees of Freedom of the $K$-pair-user Full-Duplex Two-way Interference Channel with and without a MIMO Relay
Venue: arXiv cs.IT 2013
Year: 2013

In a $K$-pair-user two-way interference channel (TWIC), $2K$ messages and $2K$ transmitters/receivers form a $K$-user IC in the forward direction ($K$ messages) and another $K$-user IC in the backward direction which operate in full-duplex mode. All nodes may interact, or adapt inputs to past received signals. We derive a new outer bound to demonstrate that the optimal degrees of freedom (DoF, also known as the multiplexing gain) is $K$: full-duplex operation doubles the DoF, but interaction does not further increase the DoF. We next characterize the DoF of the $K$-pair-user TWIC with a MIMO, full-duplex relay. If the relay is non-causal/instantaneous (at time $k$ forwards a function of its received signals up to time $k$) and has $2K$ antennas, we demonstrate a one-shot scheme where the relay mitigates all interference to achieve the interference-free $2K$ DoF. In contrast, if the relay is causal (at time $k$ forwards a function of its received signals up to time $k-1$), we show that a full-duplex MIMO relay cannot increase the DoF of the $K$-pair-user TWIC beyond $K$, as if no relay or interaction is present. We comment on reducing the number of antennas at the instantaneous relay.
A novel framework for image forgery localization
Venue: arXiv cs.CV 2013
Year: 2013

Image forgery localization is a very active and open research field for the difficulty to handle the large variety of manipulations a malicious user can perform by means of more and more sophisticated image editing tools. Here, we propose a localization framework based on the fusion of three very different tools, based, respectively, on sensor noise, patch-matching, and machine learning. The binary masks provided by these tools are finally fused based on some suitable reliability indexes. According to preliminary experiments on the training set, the proposed framework provides often a very good localization accuracy and sometimes valuable clues for visual scrutiny.
A customized flocking algorithm for swarms of sensors tracking a swarm of targets
Venue: arXiv cs.OH 2013
Year: 2013

Wireless mobile sensor networks (WMSNs) are groups of mobile sensing agents with multi-modal sensing capabilities that communicate over wireless networks. WMSNs have more flexibility in terms of deployment and exploration abilities over static sensor networks. Sensor networks have a wide range of applications in security and surveillance systems, environmental monitoring, data gathering for network-centric healthcare systems, monitoring seismic activities and atmospheric events, tracking traffic congestion and air pollution levels, localization of autonomous vehicles in intelligent transportation systems, and detecting failures of sensing, storage, and switching components of smart grids. The above applications require target tracking for processes and events of interest occurring in an environment. Various methods and approaches have been proposed in order to track one or more targets in a pre-defined area. Usually, this turns out to be a complicated job involving higher order mathematics coupled with artificial intelligence due to the dynamic nature of the targets. To optimize the resources we need to have an approach that works in a more straightforward manner while resulting in fairly satisfactory data. In this paper we have discussed the various cases that might arise while flocking a group of sensors to track targets in a given environment. The approach has been developed from scratch although some basic assumptions have been made keeping in mind some previous theories. This paper outlines a customized approach for feasibly tracking swarms of targets in a specific area so as to minimize the resources and optimize tracking efficiency.
Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions
Venue: arXiv cs.CC 2013
Year: 2013

Let $g: \{-1,1\}^k \to \{-1,1\}$ be any Boolean function and $q_1,\dots,q_k$ be any degree-2 polynomials over $\{-1,1\}^n.$ We give a \emph{deterministic} algorithm which, given as input explicit descriptions of $g,q_1,\dots,q_k$ and an accuracy parameter $\eps>0$, approximates \[\Pr_{x \sim \{-1,1\}^n}[g(\sign(q_1(x)),\dots,\sign(q_k(x)))=1]\] to within an additive $\pm \eps$. For any constant $\eps > 0$ and $k \geq 1$ the running time of our algorithm is a fixed polynomial in $n$. This is the first fixed polynomial-time algorithm that can deterministically approximately count satisfying assignments of a natural class of depth-3 Boolean circuits. Our algorithm extends a recent result \cite{DDS13:deg2count} which gave a deterministic approximate counting algorithm for a single degree-2 polynomial threshold function $\sign(q(x)),$ corresponding to the $k=1$ case of our result. Our algorithm and analysis requires several novel technical ingredients that go significantly beyond the tools required to handle the $k=1$ case in \cite{DDS13:deg2count}. One of these is a new multidimensional central limit theorem for degree-2 polynomials in Gaussian random variables which builds on recent Malliavin-calculus-based results from probability theory. We use this CLT as the basis of a new decomposition technique for $k$-tuples of degree-2 Gaussian polynomials and thus obtain an efficient deterministic approximate counting algorithm for the Gaussian distribution. Finally, a third new ingredient is a "regularity lemma" for \emph{$k$-tuples} of degree-$d$ polynomial threshold functions. This generalizes both the regularity lemmas of \cite{DSTW:10,HKM:09} and the regularity lemma of Gopalan et al \cite{GOWZ10}. Our new regularity lemma lets us extend our deterministic approximate counting results from the Gaussian to the Boolean domain.
Knowledge-Aided STAP Using Low Rank and Geometry Properties
Venue: arXiv cs.IT 2013
Year: 2013

This paper presents knowledge-aided space-time adaptive processing (KA-STAP) algorithms that exploit the low-rank dominant clutter and the array geometry properties (LRGP) for airborne radar applications. The core idea is to exploit the fact that the clutter subspace is only determined by the space-time steering vectors, {red}{where the Gram-Schmidt orthogonalization approach is employed to compute the clutter subspace. Specifically, for a side-looking uniformly spaced linear array, the} algorithm firstly selects a group of linearly independent space-time steering vectors using LRGP that can represent the clutter subspace. By performing the Gram-Schmidt orthogonalization procedure, the orthogonal bases of the clutter subspace are obtained, followed by two approaches to compute the STAP filter weights. To overcome the performance degradation caused by the non-ideal effects, a KA-STAP algorithm that combines the covariance matrix taper (CMT) is proposed. For practical applications, a reduced-dimension version of the proposed KA-STAP algorithm is also developed. The simulation results illustrate the effectiveness of our proposed algorithms, and show that the proposed algorithms converge rapidly and provide a SINR improvement over existing methods when using a very small number of snapshots.
A Hybrid Web Recommendation System based on the Improved Association Rule Mining Algorithm
Venue: arXiv cs.IR 2013
Year: 2013

As the growing interest of web recommendation systems those are applied to deliver customized data for their users, we started working on this system. Generally the recommendation systems are divided into two major categories such as collaborative recommendation system and content based recommendation system. In case of collaborative recommen-dation systems, these try to seek out users who share same tastes that of given user as well as recommends the websites according to the liking given user. Whereas the content based recommendation systems tries to recommend web sites similar to those web sites the user has liked. In the recent research we found that the efficient technique based on asso-ciation rule mining algorithm is proposed in order to solve the problem of web page recommendation. Major problem of the same is that the web pages are given equal importance. Here the importance of pages changes according to the fre-quency of visiting the web page as well as amount of time user spends on that page. Also recommendation of newly added web pages or the pages those are not yet visited by users are not included in the recommendation set. To over-come this problem, we have used the web usage log in the adaptive association rule based web mining where the asso-ciation rules were applied to personalization. This algorithm was purely based on the Apriori data mining algorithm in order to generate the association rules. However this method also suffers from some unavoidable drawbacks. In this paper we are presenting and investigating the new approach based on weighted Association Rule Mining Algorithm and text mining. This is improved algorithm which adds semantic knowledge to the results, has more efficiency and hence gives better quality and performances as compared to existing approaches.
Hierarchies
Venue: arXiv cs.CC 2013
Year: 2013

We study the complexity theory for the local distributed setting introduced by Korman, Peleg and Fraigniaud. They have defined three complexity classes LD (Local Decision), NLD (Nondeterministic Local Decision) and NLD^#n. The class LD consists of all languages which can be decided with a constant number of communication rounds. The class NLD consists of all languages which can be verified by a nondeterministic algorithm with a constant number of communication rounds. In order to define the nondeterministic classes, they have transferred the notation of nondeterminism into the distributed setting by the use of certificates and verifiers. The class NLD^#n consists of all languages which can be verified by a nondeterministic algorithm where each node has access to an oracle for the number of nodes. They have shown the hierarchy LD subset NLD subset NLD^#n. Our main contributions are strict hierarchies within the classes defined by Korman, Peleg and Fraigniaud. We define additional complexity classes: the class LD(t) consists of all languages which can be decided with at most t communication rounds. The class NLD-O(f) consists of all languages which can be verified by a local verifier such that the size of the certificates that are needed to verify the language are bounded by a function from O(f). Our main results are refined strict hierarchies within these nondeterministic classes.