OpenRaiser/Intern-Atlas huggingface dataset:
Automatic latency balancing in VHDL-implemented complex pipelined systems
Venue: arXiv cs.AR 2015
Year: 2015

Balancing (equalization) of latency in parallel paths in the pipelined data processing system is an important problem. Without that the data from different paths arrive at the processing blocks in different clock cycles, and incorrect results are produced. Manual correction of latencies is a tedious and error-prone work. This paper presents an automatic method of latency equalization in systems described in VHDL. The method is based on simulation and is portable between different simulation and synthesis tools. The method does not increase the complexity of the synthesized design comparing to the solution based on manual latency adjustment. The example implementation of the proposed methodology together with a simple design demonstrating its use is available as an open source project under BSD license.
Amplification and Derandomization Without Slowdown
Venue: arXiv cs.DS 2015
Year: 2015

We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (non-uniform) algorithms. Unlike most existing techniques that involve repetition of the randomized algorithm and hence a slowdown, our techniques produce algorithms with a similar run-time to the original randomized algorithms. The amplification technique is related to a certain stochastic multi-armed bandit problem. The derandomization technique - which is the main contribution of this work - points to an intriguing connection between derandomization and sketching/sparsification. We demonstrate the techniques by showing applications to Max-Cut on dense graphs, approximate clique on graphs that contain a large clique, constraint satisfaction problems on dense bipartite graphs and the list decoding to unique decoding problem for the Reed-Muller code.
Linear Arrangement of Halin Graphs
Venue: arXiv cs.DM 2015
Year: 2015

We study the Optimal Linear Arrangement (OLA) problem of Halin graphs, one of the simplest classes of non-outerplanar graphs. We present several properties of OLA of general Halin graphs. We prove a lower bound on the cost of OLA of any Halin graph, and define classes of Halin graphs for which the cost of OLA matches this lower bound. We show for these classes of Halin graphs, OLA can be computed in O(n log n), where n is the number of vertices.
External Memory Three-Sided Range Reporting and Top-$k$ Queries with Sublogarithmic Updates
Venue: arXiv cs.CG 2015
Year: 2015

An external memory data structure is presented for maintaining a dynamic set of $N$ two-dimensional points under the insertion and deletion of points, and supporting 3-sided range reporting queries and top-$k$ queries, where top-$k$ queries report the $k$~points with highest $y$-value within a given $x$-range. For any constant $0<\varepsilon\leq \frac{1}{2}$, a data structure is constructed that supports updates in amortized $O(\frac{1}{\varepsilon B^{1-\varepsilon}}\log_B N)$ IOs and queries in amortized $O(\frac{1}{\varepsilon}\log_B N+K/B)$ IOs, where $B$ is the external memory block size, and $K$ is the size of the output to the query (for top-$k$ queries $K$ is the minimum of $k$ and the number of points in the query interval). The data structure uses linear space. The update bound is a significant factor $B^{1-\varepsilon}$ improvement over the previous best update bounds for the two query problems, while staying within the same query and space bounds.
Rooted branching bisimulation as a congruence for probabilistic transition systems
Venue: arXiv cs.LO 2015
Year: 2015

We propose a probabilistic transition system specification format, referred to as probabilistic RBB safe, for which rooted branching bisimulation is a congruence. The congruence theorem is based on the approach of Fokkink for the qualitative case. For this to work, the theory of transition system specifications in the setting of labeled transition systems needs to be extended to deal with probability distributions, both syntactically and semantically. We provide a scheduler-free characterization of probabilistic branching bisimulation as adapted from work of Andova et al. for the alternating model. Counter examples are given to justify the various conditions required by the format.
Often harder than in the Constructive Case: Destructive Bribery in CP-nets
Venue: arXiv cs.CC 2015
Year: 2015

We study the complexity of the destructive bribery problem---an external agent tries to prevent a disliked candidate from winning by bribery actions---in voting over combinatorial domains, where the set of candidates is the Cartesian product of several issues. This problem is related to the concept of the margin of victory of an election which constitutes a measure of robustness of the election outcome and plays an important role in the context of electronic voting. In our setting, voters have conditional preferences over assignments to these issues, modelled by CP-nets. We settle the complexity of all combinations of this problem based on distinctions of four voting rules, five cost schemes, three bribery actions, weighted and unweighted voters, as well as the negative and the non-negative scenario. We show that almost all of these cases are NP-complete or NP-hard for weighted votes while approximately half of the cases can be solved in polynomial time for unweighted votes.
Long-Range Trajectories from Global and Local Motion Representations
Venue: arXiv cs.CV 2015
Year: 2015

Motion is a fundamental cue for scene analysis and human activity understan- ding in videos. It can be encoded in trajectories for tracking objects and for action recognition, or in form of flow to address behaviour analysis in crowded scenes. Each approach can only be applied on limited scenarios. We propose a motion-based system that represents the spatial and temporal features of the flow in terms of long-range trajectories. The novelty resides on the system formulation, its generic approach to handle scene variability and motion variations, motion integration from local and global representations, and the resulting long-range trajectories that overcome trajectory-based approach problems. We report the results and conclusions that state its pertinence on different scenarios, comparing and correlating the extracted trajectories of individual pedestrians, manually annotated. We also propose an evaluation framework and stress the diverse system characteristics that can be used for human activity tasks, namely on motion segmentation.
Traffic signal optimization: combining static and dynamic models
Venue: arXiv cs.DM 2015
Year: 2015

In this paper, we present a cyclically time-expanded network model for simultaneous optimization of traffic assignment and traffic signal parameters, in particular offsets, split times, and phase orders. Since travel times are of great importance for developing realistic solutions for traffic assignment and traffic signal coordination in urban road networks, we perform an extensive analysis of the model. We show that a linear time-expanded model can reproduce realistic travel times especially for use with traffic signals and we verify this by simulation. Furthermore, we show how exact mathematical programming techniques can be used for optimizing the control of traffic signals. We provide computational results for real world instances and demonstrate the capabilities of the cyclically time-expanded by simulation results obtained with state-of-the-art traffic simulation tools.
Retinex filtering of foggy images: generation of a bulk set with selection and ranking
Venue: arXiv cs.CV 2015
Year: 2015

In this paper we are proposing the use of GIMP Retinex, a filter of the GNU Image Manipulation Program, for enhancing foggy images. This filter involves adjusting four different parameters to find the output image which has to be preferred according to some specific purposes. Aiming to obtain a processing, which is able of choosing automatically the best image from a given set, we are proposing a method for the generation a bulk set of GIMP Retinex filtered images and a preliminary approach for selecting and ranking them.
A non iterative method of separation of points by planes in n dimensions and its application
Venue: arXiv cs.CG 2015
Year: 2015

Given a set of N points, we have discovered an algorithm that can separate these points from one another by n-dimensional planes. Each point is chosen at random and put into a set S and planes which separate them are determined and put into S. The algorithm gives a method of choosing points and planes which separate them, till all the points are separated. A proof is provided with a worked example. The algorithm is non iterative and always halts successfully and the algorithm strictly follows Shannon's principle of making optimal use of information as it advances stage by stage. It also has a restart facility and can take care of new points from where it left off.At some later stage if the dimension of the data is increased from n to n+r, the algorithm can still continue from where it left off, after some simple adjustments, and tackle the new data points which are of a higher dimension. and separate them. The computational complexity is O(n.N log(N)) + O(n3 log(N)), where N is the given number of points and n3 is the cube of n - the dimension of space. The algorithm is made possible because a new concept called Orientation Vector is used. This vector is a Hamming vector and is associated with each point and has been so devised that it has all the information necessary to ascertain if two points are separate or not when among a collection of planes.Its application to data retrieval problems in very large medical data bases is also given.
How to Formulate and Solve Statistical Recognition and Learning Problems
Venue: arXiv cs.LG 2015
Year: 2015

We formulate problems of statistical recognition and learning in a common framework of complex hypothesis testing. Based on arguments from multi-criteria optimization, we identify strategies that are improper for solving these problems and derive a common form of the remaining strategies. We show that some widely used approaches to recognition and learning are improper in this sense. We then propose a generalized formulation of the recognition and learning problem which embraces the whole range of sizes of the learning sample, including the zero size. Learning becomes a special case of recognition without learning. We define the concept of closest to optimal strategy, being a solution to the formulated problem, and describe a technique for finding such a strategy. On several illustrative cases, the strategy is shown to be superior to the widely used learning methods based on maximal likelihood estimation.
Polish - English Speech Statistical Machine Translation Systems for the IWSLT 2014
Venue: arXiv cs.CL 2015
Year: 2015

This research explores effects of various training settings between Polish and English Statistical Machine Translation systems for spoken language. Various elements of the TED parallel text corpora for the IWSLT 2014 evaluation campaign were used as the basis for training of language models, and for development, tuning and testing of the translation system as well as Wikipedia based comparable corpora prepared by us. The BLEU, NIST, METEOR and TER metrics were used to evaluate the effects of data preparations on translation results. Our experiments included systems, which use lemma and morphological information on Polish words. We also conducted a deep analysis of provided Polish data as preparatory work for the automatic data correction and cleaning phase.
Two Phase $Q-$learning for Bidding-based Vehicle Sharing
Venue: arXiv cs.AI 2015
Year: 2015

We consider one-way vehicle sharing systems where customers can rent a car at one station and drop it off at another. The problem we address is to optimize the distribution of cars, and quality of service, by pricing rentals appropriately. We propose a bidding approach that is inspired from auctions and takes into account the significant uncertainty inherent in the problem data (e.g., pick-up and drop-off locations, time of requests, and duration of trips). Specifically, in contrast to current vehicle sharing systems, the operator does not set prices. Instead, customers submit bids and the operator decides whether to rent or not. The operator can even accept negative bids to motivate drivers to rebalance available cars to unpopular destinations within a city. We model the operator's sequential decision-making problem as a \emph{constrained Markov decision problem} (CMDP) and propose and rigorously analyze a novel two phase $Q$-learning algorithm for its solution. Numerical experiments are presented and discussed.
GRAPLEr: A Distributed Collaborative Environment for Lake Ecosystem Modeling that Integrates Overlay Networks, High-throughput Computing, and Web Services
Venue: arXiv cs.DC 2015
Year: 2015

The GLEON Research And PRAGMA Lake Expedition -- GRAPLE -- is a collaborative effort between computer science and lake ecology researchers. It aims to improve our understanding and predictive capacity of the threats to the water quality of our freshwater resources, including climate change. This paper presents GRAPLEr, a distributed computing system used to address the modeling needs of GRAPLE researchers. GRAPLEr integrates and applies overlay virtual network, high-throughput computing, and Web service technologies in a novel way. First, its user-level IP-over-P2P (IPOP) overlay network allows compute and storage resources distributed across independently-administered institutions (including private and public clouds) to be aggregated into a common virtual network, despite the presence of firewalls and network address translators. Second, resources aggregated by the IPOP virtual network run unmodified high-throughput computing middleware (HTCondor) to enable large numbers of model simulations to be executed concurrently across the distributed computing resources. Third, a Web service interface allows end users to submit job requests to the system using client libraries that integrate with the R statistical computing environment. The paper presents the GRAPLEr architecture, describes its implementation and reports on its performance for batches of General Lake Model (GLM) simulations across three cloud infrastructures (University of Florida, CloudLab, and Microsoft Azure).
Symbol Emergence in Robotics: A Survey
Venue: arXiv cs.AI 2015
Year: 2015

Humans can learn the use of language through physical interaction with their environment and semiotic communication with other people. It is very important to obtain a computational understanding of how humans can form a symbol system and obtain semiotic skills through their autonomous mental development. Recently, many studies have been conducted on the construction of robotic systems and machine-learning methods that can learn the use of language through embodied multimodal interaction with their environment and other systems. Understanding human social interactions and developing a robot that can smoothly communicate with human users in the long term, requires an understanding of the dynamics of symbol systems and is crucially important. The embodied cognition and social interaction of participants gradually change a symbol system in a constructive manner. In this paper, we introduce a field of research called symbol emergence in robotics (SER). SER is a constructive approach towards an emergent symbol system. The emergent symbol system is socially self-organized through both semiotic communications and physical interactions with autonomous cognitive developmental agents, i.e., humans and developmental robots. Specifically, we describe some state-of-art research topics concerning SER, e.g., multimodal categorization, word discovery, and a double articulation analysis, that enable a robot to obtain words and their embodied meanings from raw sensory--motor information, including visual information, haptic information, auditory information, and acoustic speech signals, in a totally unsupervised manner. Finally, we suggest future directions of research in SER.
Moving Object Detection in Video Using Saliency Map and Subspace Learning
Venue: arXiv cs.CV 2015
Year: 2015

Moving object detection is a key to intelligent video analysis. On the one hand, what moves is not only interesting objects but also noise and cluttered background. On the other hand, moving objects without rich texture are prone not to be detected. So there are undesirable false alarms and missed alarms in many algorithms of moving object detection. To reduce the false alarms and missed alarms, in this paper, we propose to incorporate a saliency map into an incremental subspace analysis framework where the saliency map makes estimated background has less chance than foreground (i.e., moving objects) to contain salient objects. The proposed objective function systematically takes account into the properties of sparsity, low-rank, connectivity, and saliency. An alternative minimization algorithm is proposed to seek the optimal solutions. Experimental results on the Perception Test Images Sequences demonstrate that the proposed method is effective in reducing false alarms and missed alarms.
Real-Time Statistical Speech Translation
Venue: arXiv cs.CL 2015
Year: 2015

This research investigates the Statistical Machine Translation approaches to translate speech in real time automatically. Such systems can be used in a pipeline with speech recognition and synthesis software in order to produce a real-time voice communication system between foreigners. We obtained three main data sets from spoken proceedings that represent three different types of human speech. TED, Europarl, and OPUS parallel text corpora were used as the basis for training of language models, for developmental tuning and testing of the translation system. We also conducted experiments involving part of speech tagging, compound splitting, linear language model interpolation, TrueCasing and morphosyntactic analysis. We evaluated the effects of variety of data preparations on the translation results using the BLEU, NIST, METEOR and TER metrics and tried to give answer which metric is most suitable for PL-EN language pair.
Cooperative Task Planning of Multi-Agent Systems Under Timed Temporal Specifications
Venue: arXiv cs.SY 2015
Year: 2015

In this paper the problem of cooperative task planning of multi-agent systems when timed constraints are imposed to the system is investigated. We consider timed constraints given by Metric Interval Temporal Logic (MITL). We propose a method for automatic control synthesis in a two-stage systematic procedure. With this method we guarantee that all the agents satisfy their own individual task specifications as well as that the team satisfies a team global task specification.
Technical Report on Intruder Detection and Alert System
Venue: arXiv cs.CY 2015
Year: 2015

This work presents a smart trespasser detection and alert system which aims to increase the amount of security as well as the likelihood of positively identifying or stopping trespassers and intruders as compared to other commonly deployed home security system. Using multiple sensors, this system can gauge the extent of danger exhibited by a person or animal in or around the home premises, and can forward certain critical information regarding the same to home owners as well as other specified persons such as relevant security authorities.
Joint Scheduling and Power Allocations for Traffic Offloading via Dual-Connectivity
Venue: arXiv cs.NI 2015
Year: 2015

With the rapid growth of mobile traffic demand, a promising approach to relieve cellular network congestion is to offload users' traffic to small-cell networks. In this paper, we investigate how the mobile users (MUs) can effectively offload traffic by taking advantage of the capability of dual-connectivity, which enables an MU to simultaneously communicate with a macro base station (BS) and a small-cell access point (AP) via two radio-interfaces. Offloading traffic to the AP usually reduces the MUs' mobile data cost, but often at the expense of suffering increased interferences from other MUs at the same AP. We thus formulate an optimization problem that jointly determines each MU's traffic schedule (between the BS and AP) and power control (between two radio-interfaces). The system objective is to minimize all MUs' total cost, while satisfying each MU's transmit-power constraints through proper interference control. In spite of the non-convexity of the problem, we design both a centralized algorithm and a distributed algorithm to solve the joint optimization problem. Numerical results show that the proposed algorithms can achieve the close-to-optimum results comparing with the ones achieved by the LINGO (a commercial optimization software), but with significantly less computational complexity. The results also show that the proposed adaptive offloading can significantly reduce the MUs' cost, i.e., save more than 75% of the cost without offloading traffic and 65% of the cost with a fixed offloading.
Incremental Aggregated Proximal and Augmented Lagrangian Algorithms
Venue: arXiv cs.SY 2015
Year: 2015

We consider minimization of the sum of a large number of convex functions, and we propose an incremental aggregated version of the proximal algorithm, which bears similarity to the incremental aggregated gradient and subgradient methods that have received a lot of recent attention. Under cost function differentiability and strong convexity assumptions, we show linear convergence for a sufficiently small constant stepsize. This result also applies to distributed asynchronous variants of the method, involving bounded interprocessor communication delays. We then consider dual versions of incremental proximal algorithms, which are incremental augmented Lagrangian methods for separable equality-constrained optimization problems. Contrary to the standard augmented Lagrangian method, these methods admit decomposition in the minimization of the augmented Lagrangian, and update the multipliers far more frequently. Our incremental aggregated augmented Lagrangian methods bear similarity to several known decomposition algorithms, including the alternating direction method of multipliers (ADMM) and more recent variations. We compare these methods in terms of their properties, and highlight their potential advantages and limitations. We also address the solution of separable inequality-constrained optimization problems through the use of nonquadratic augmented Lagrangiias such as the exponential, and we dually consider a corresponding incremental aggregated version of the proximal algorithm that uses nonquadratic regularization, such as an entropy function. We finally propose a closely related linearly convergent method for minimization of large differentiable sums subject to an orthant constraint, which may be viewed as an incremental aggregated version of the mirror descent method.
Understanding the IoT Connectivity Landscape: A Contemporary M2M Radio Technology Roadmap
Venue: arXiv cs.NI 2015
Year: 2015

This article addresses the market-changing phenomenon of the Internet of Things (IoT), which relies on the underlying paradigm of machine-to-machine (M2M) communications to integrate a plethora of various sensors, actuators, and smart meters across a wide spectrum of businesses. The M2M landscape features today an extreme diversity of available connectivity solutions which -- due to the enormous economic promise of the IoT -- need to be harmonized across multiple industries. To this end, we comprehensively review the most prominent existing and novel M2M radio technologies, as well as share our first-hand real-world deployment experiences, with the goal to provide a unified insight into enabling M2M architectures, unique technology features, expected performance, and related standardization developments. We pay particular attention to the cellular M2M sector employing 3GPP LTE technology. This work is a systematic recollection of our many recent research, industrial, entrepreneurial, and standardization efforts within the contemporary M2M ecosystem.