OpenRaiser/Intern-Atlas huggingface dataset:
Modular exponentiation of matrices on FPGA-s
Venue: arXiv cs.DS 2011
Year: 2011

We describe an efficient FPGA implementation for the exponentiation of large matrices. The research is related to an algorithm for constructing uniformly distributed linear recurring sequences. The design utilizes the special properties of both the FPGA and the used matrices to achieve a very significant speedup compared to traditional architectures.
Channel Reordering with Time-shifted Streams to Improve Channel Change Latency in IPTV Networks
Venue: arXiv cs.NI 2011
Year: 2011

In IPTV networks, channel change latency is considered as a major obstacle in achieving broadcast-level quality video delivery. Because of the bandwidth limitations observed at the client side, users typically have access to a limited number of channels. As a result, channel change requests oftentimes need to go through the network, thereby leading to significant delays. In this paper, we address this problem by proposing a resource-efficient time-shifted channel reordering mechanism to minimize the channel change latency. The proposed framework exploits the differing key-frame delivery times for the adjacent sessions to dynamically arrange the switching order during the surfing periods. The simulation results show that, with the proposed framework, more than 50% improvement can be achieved in channel change latency without introducing any overhead in the network.
Corner Occupying Theorem for the Two-dimensional Integral Rectangle Packing Problem
Venue: arXiv cs.DM 2011
Year: 2011

This paper proves a corner occupying theorem for the two-dimensional integral rectangle packing problem, stating that if it is possible to orthogonally place n arbitrarily given integral rectangles into an integral rectangular container without overlapping, then we can achieve a feasible packing by successively placing an integral rectangle onto a bottom-left corner in the container. Based on this theorem, we might develop efficient heuristic algorithms for solving the integral rectangle packing problem. In fact, as a vague conjecture, this theorem has been implicitly mentioned with different appearances by many people for a long time.
A Bayesian Model for Plan Recognition in RTS Games applied to StarCraft
Venue: arXiv cs.LG 2011
Year: 2011

The task of keyhole (unobtrusive) plan recognition is central to adaptive game AI. "Tech trees" or "build trees" are the core of real-time strategy (RTS) game strategic (long term) planning. This paper presents a generic and simple Bayesian model for RTS build tree prediction from noisy observations, which parameters are learned from replays (game logs). This unsupervised machine learning approach involves minimal work for the game developers as it leverage players' data (com- mon in RTS). We applied it to StarCraft1 and showed that it yields high quality and robust predictions, that can feed an adaptive AI.
Steganography and Steganalysis: Different Approaches
Venue: arXiv cs.CR 2011
Year: 2011

Steganography is the technique of hiding confidential information within any media. Steganography is often confused with cryptography because the two are similar in the way that they both are used to protect confidential information. The difference between the two is in the appearance in the processed output; the output of steganography operation is not apparently visible but in cryptography the output is scrambled so that it can draw attention. Steganlysis is process to detect of presence of steganography. In this article we have tried to elucidate the different approaches towards implementation of steganography using 'multimedia' file (text, static image, audio and video) and Network IP datagram as cover. Also some methods of steganalysis will be discussed.
A Low-Delay Low-Complexity EKF Design for Joint Channel and CFO Estimation in Multi-User Cognitive Communications
Venue: arXiv cs.IT 2011
Year: 2011

Parameter estimation in cognitive communications can be formulated as a multi-user estimation problem, which is solvable under maximum likelihood solution but involves high computational complexity. This paper presents a time-sharing and interference mitigation based EKF (Extended Kalman Filter) design for joint CFO (carrier frequency offset) and channel estimation at multiple cognitive users. The key objective is to realize low implementation complexity by decomposing highdimensional parameters into multiple separate low-dimensional estimation problems, which can be solved in a time-shared manner via pipelining operation. We first present a basic EKF design that estimates the parameters from one TX user to one RX antenna. Then such basic design is time-shared and reused to estimate parameters from multiple TX users to multiple RX antennas. Meanwhile, we use interference mitigation module to cancel the co-channel interference at each RX sample. In addition, we further propose adaptive noise variance tracking module to improve the estimation performance. The proposed design enjoys low delay and low buffer size (because of its online real-time processing), as well as low implementation complexity (because of time-sharing and pipeling design). Its estimation performance is verified to be close to Cramer-Rao bound.
Elastic Fidelity: Trading-off Computational Accuracy for Energy Reduction
Venue: arXiv cs.AR 2011
Year: 2011

Power dissipation and energy consumption have become one of the most important problems in the design of processors today. This is especially true in power-constrained environments, such as embedded and mobile computing. While lowering the operational voltage can reduce power consumption, there are limits imposed at design time, beyond which hardware components experience faulty operation. Moreover, the decrease in feature size has led to higher susceptibility to process variations, leading to reliability issues and lowering yield. However, not all computations and all data in a workload need to maintain 100% fidelity. In this paper, we explore the idea of employing functional or storage units that let go the conservative guardbands imposed on the design to guarantee reliable execution. Rather, these units exhibit Elastic Fidelity, by judiciously lowering the voltage to trade-off reliable execution for power consumption based on the error guarantees required by the executing code. By estimating the accuracy required by each computational segment of a workload, and steering each computation to different functional and storage units, Elastic Fidelity Computing obtains power and energy savings while reaching the reliability targets required by each computational segment. Our preliminary results indicate that even with conservative estimates, Elastic Fidelity can reduce the power and energy consumption of a processor by 11-13% when executing applications involving human perception that are typically included in modern mobile platforms, such as audio, image, and video decoding.
Multi-font Multi-size Kannada Numeral Recognition Based on Structural Features
Venue: arXiv cs.CV 2011
Year: 2011

In this paper a fast and novel method is proposed for multi-font multi-size Kannada numeral recognition which is thinning free and without size normalization approach. The different structural feature are used for numeral recognition namely, directional density of pixels in four directions, water reservoirs, maximum profile distances, and fill hole density are used for the recognition of Kannada numerals. A Euclidian minimum distance criterion is used to find minimum distances and K-nearest neighbor classifier is used to classify the Kannada numerals by varying the size of numeral image from 16 to 50 font sizes for the 20 different font styles from NUDI and BARAHA popular word processing Kannada software. The total 1150 numeral images are tested and the overall accuracy of classification is found to be 100%. The average time taken by this method is 0.1476 seconds.
Homomorphic encryption from codes
Venue: arXiv cs.CR 2011
Year: 2011

We propose a new homomorphic encryption scheme based on the hardness of decoding under independent random noise from certain affine families of codes. Unlike in previous lattice-based homomorphic encryption schemes, where the message is hidden in the noisy part of the ciphertext, our scheme carries the message in the affine part of the transformation and applies noise only to achieve security. Our scheme can tolerate noise of arbitrary magnitude, as long as the noise vector has sufficiently small hamming weight (and its entries are independent). Our design achieves "proto-homomorphic" properties in an elementary manner: message addition and multiplication are emulated by pointwise addition and multiplication of the ciphertext vectors. Moreover, the extremely simple nature of our decryption makes the scheme easily amenable to bootstrapping. However, some complications are caused by the inherent presence of noticeable encryption error. Our main technical contribution is the development of two new techniques for handling this error in the homomorphic evaluation process. We also provide a definitional framework for homomorphic encryption that may be useful elsewhere.
Semantic Navigation on the Web of Data: Specification of Routes, Web Fragments and Actions
Venue: arXiv cs.NI 2011
Year: 2011

The massive semantic data sources linked in the Web of Data give new meaning to old features like navigation; introduce new challenges like semantic specification of Web fragments; and make it possible to specify actions relying on semantic data. In this paper we introduce a declarative language to face these challenges. Based on navigational features, it is designed to specify fragments of the Web of Data and actions to be performed based on these data. We implement it in a centralized fashion, and show its power and performance. Finally, we explore the same ideas in a distributed setting, showing their feasibility, potentialities and challenges.
Grid Security and Integration with Minimal Performance Degradation
Venue: arXiv cs.CR 2011
Year: 2011

Computational grids are believed to be the ultimate framework to meet the growing computational needs of the scientific community. Here, the processing power of geographically distributed resources working under different ownerships, having their own access policy, cost structure and the likes, is logically coupled to make them perform as a unified resource. The continuous increase of availability of high-bandwidth communication as well as powerful computers built of low-cost components further enhance chances of computational grids becoming a reality. However, the question of grid security remains one of the important open research issues. Here, we present some novel ideas about how to implement grid security, without appreciable performance degradation in grids. A suitable alternative to the computationally expensive encryption is suggested, which uses a key for message authentication. Methods of secure transfer and exchange of the required key(s) are also discussed.
GMF: A Model Migration Case for the Transformation Tool Contest
Venue: arXiv cs.SE 2011
Year: 2011

Using a real-life evolution taken from the Graphical Modeling Framework, we invite submissions to explore ways in which model transformation and migration tools can be used to migrate models in response to metamodel adaptation.
Solving the TTC 2011 Compiler Optimization Case with GrGen.NET
Venue: arXiv cs.PL 2011
Year: 2011

The challenge of the Compiler Optimization Case is to perform local optimizations and instruction selection on the graph-based intermediate representation of a compiler. The case is designed to compare participating tools regarding their performance. We tackle this task employing the general purpose graph rewrite system GrGen.NET (www.grgen.net).
Saying Hello World with GrGen.NET - A Solution to the TTC 2011 Instructive Case
Venue: arXiv cs.PL 2011
Year: 2011

We introduce the graph transformation tool GrGen.NET (www.grgen.net) by solving the Hello World Case of the Transformation Tool Contest 2011 which consists of a collection of small transformation tasks; for each task a section is given explaining our implementation.
Saying Hello World with VIATRA2 - A Solution to the TTC 2011 Instructive Case
Venue: arXiv cs.SE 2011
Year: 2011

The paper presents a solution of the Hello World! An Instructive Case for the Transformation Tool Contest using the VIATRA2 model transformation tool.
Saying HelloWorld with QVTR-XSLT - A Solution to the TTC 2011 Instructive Case
Venue: arXiv cs.SE 2011
Year: 2011

In this short paper we present our solution for the Hello World case study of the Transformation Tool Contest (TTC) 2011 using the QVTR-XSLT tool. The tool supports editing and execution of the graphical notation of QVT Relations language. The case study consists of a set of simple transformation tasks which covers the basic functions required for a transformation language, such as creating, reading/querying, updating and deleting of model elements. We design a transformation for each of the tasks.
A Navigation Algorithm Inspired by Human Navigation
Venue: arXiv cs.SI 2011
Year: 2011

Human navigation has been a topic of interest in spatial cognition from the past few decades. It has been experimentally observed that humans accomplish the task of way-finding a destination in an unknown environment by recognizing landmarks. Investigations using network analytic techniques reveal that humans, when asked to way-find their destination, learn the top ranked nodes of a network. In this paper we report a study simulating the strategy used by humans to recognize the centers of a network. We show that the paths obtained from our simulation has the same properties as the paths obtained in human based experiment. The simulation thus performed leads to a novel way of path-finding in a network. We discuss the performance of our method and compare it with the existing techniques to find a path between a pair of nodes in a network.
A Frame Rate Optimization Framework For Improving Continuity In Video Streaming
Venue: arXiv cs.NI 2011
Year: 2011

This paper aims to reduce the prebuffering requirements, while maintaining continuity, for video streaming. Current approaches do this by making use of adaptive media playout (AMP) to reduce the playout rate. However, this introduces playout distortion to the viewers and increases the viewing latency. We approach this by proposing a frame rate optimization framework that adjusts both the encoder frame generation rate and the decoder playout frame rate. Firstly, we model this problem as the joint adjustment of the encoder frame generation interval and the decoder playout frame interval. This model is used with a discontinuity penalty virtual buffer to track the accumulated difference between the receiving frame interval and the playout frame interval. We then apply Lyapunov optimization to the model to systematically derive a pair of decoupled optimization policies. We show that the occupancy of the discontinuity penalty virtual buffer is correlated to the video discontinuity and that this framework produces a very low playout distortion in addition to a significant reduction in the prebuffering requirements compared to existing approaches. Secondly, we introduced a delay constraint into the framework by using a delay accumulator virtual buffer. Simulation results show that the the delay constrained framework provides a superior tradeoff between the video quality and the delay introduced compared to the existing approach. Finally, we analyzed the impact of delayed feedback between the receiver and the sender on the optimization policies. We show that the delayed feedbacks have a minimal impact on the optimization policies.
Awareness and Self-Awareness for Multi-Robot Organisms
Venue: arXiv cs.RO 2011
Year: 2011

Awareness and self-awareness are two different notions related to knowing the environment and itself. In a general context, the mechanism of self-awareness belongs to a class of co-called "self-issues" (self-* or self-star): self-adaptation, self-repairing, self-replication, self-development or self-recovery. The self-* issues are connected in many ways to adaptability and evolvability, to the emergence of behavior and to the controllability of long-term developmental processes. Self-* are either natural properties of several systems, such as self-assembling of molecular networks, or may emerge as a result of homeostatic regulation. Different computational processes, leading to a global optimization, increasing scalability and reliability of collective systems, create such a homeostatic regulation. Moreover, conditions of ecological survival, imposed on such systems, lead to a discrimination between "self" and "non-self" as well as to the emergence of different self-phenomena. There are many profound challenges, such as understanding these mechanisms, or long-term predictability, which have a considerable impact on research in the area of artificial intelligence and intelligent systems.
Fast Compressed Tries through Path Decompositions
Venue: arXiv cs.DS 2011
Year: 2011

Tries are popular data structures for storing a set of strings, where common prefixes are represented by common root-to-node paths. Over fifty years of usage have produced many variants and implementations to overcome some of their limitations. We explore new succinct representations of path-decomposed tries and experimentally evaluate the corresponding reduction in space usage and memory latency, comparing with the state of the art. We study two cases of applications: (1) a compressed dictionary for (compressed) strings, and (2) a monotone minimal perfect hash for strings that preserves their lexicographic order. For (1), we obtain data structures that outperform other state-of-the-art compressed dictionaries in space efficiency, while obtaining predictable query times that are competitive with data structures preferred by the practitioners. In (2), our tries perform several times faster than other trie-based monotone perfect hash functions, while occupying nearly the same space.
Evolution of a Modular Software Network
Venue: arXiv cs.OS 2011
Year: 2011

"Evolution behaves like a tinkerer" (Francois Jacob, Science, 1977). Software systems provide a unique opportunity to understand biological processes using concepts from network theory. The Debian GNU/Linux operating system allows us to explore the evolution of a complex network in a novel way. The modular design detected during its growth is based on the reuse of existing code in order to minimize costs during programming. The increase of modularity experienced by the system over time has not counterbalanced the increase in incompatibilities between software packages within modules. This negative effect is far from being a failure of design. A random process of package installation shows that the higher the modularity the larger the fraction of packages working properly in a local computer. The decrease in the relative number of conflicts between packages from different modules avoids a failure in the functionality of one package spreading throughout the entire system. Some potential analogies with the evolutionary and ecological processes determining the structure of ecological networks of interacting species are discussed.
On the Expected Complexity of Random Convex Hulls
Venue: arXiv cs.CG 2011
Year: 2011

In this paper we present several results on the expected complexity of a convex hull of $n$ points chosen uniformly and independently from a convex shape. (i) We show that the expected number of vertices of the convex hull of $n$ points, chosen uniformly and independently from a disk is $O(n^{1/3})$, and $O(k \log{n})$ for the case a convex polygon with $k$ sides. Those results are well known (see \cite{rs-udkhv-63,r-slcdn-70,ps-cgi-85}), but we believe that the elementary proof given here are simpler and more intuitive. (ii) Let $\D$ be a set of directions in the plane, we define a generalized notion of convexity induced by $\D$, which extends both rectilinear convexity and standard convexity. We prove that the expected complexity of the $\D$-convex hull of a set of $n$ points, chosen uniformly and independently from a disk, is $O(n^{1/3} + \sqrt{nα(\D)})$, where $α(\D)$ is the largest angle between two consecutive vectors in $\D$. This result extends the known bounds for the cases of rectilinear and standard convexity. (iii) Let $\B$ be an axis parallel hypercube in $\Re^d$. We prove that the expected number of points on the boundary of the quadrant hull of a set $S$ of $n$ points, chosen uniformly and independently from $\B$ is $O(\log^{d-1}n)$. Quadrant hull of a set of points is an extension of rectilinear convexity to higher dimensions. In particular, this number is larger than the number of maxima in $S$, and is also larger than the number of points of $S$ that are vertices of the convex hull of $S$. Those bounds are known \cite{bkst-anmsv-78}, but we believe the new proof is simpler.
DECENT: A Decentralized Architecture for Enforcing Privacy in Online Social Networks
Venue: arXiv cs.CR 2011
Year: 2011

A multitude of privacy breaches, both accidental and malicious, have prompted users to distrust centralized providers of online social networks (OSNs) and investigate decentralized solutions. We examine the design of a fully decentralized (peer-to-peer) OSN, with a special focus on privacy and security. In particular, we wish to protect the confidentiality, integrity, and availability of user content and the privacy of user relationships. We propose DECENT, an architecture for OSNs that uses a distributed hash table to store user data, and features cryptographic protections for confidentiality and integrity, as well as support for flexible attribute policies and fast revocation. DECENT ensures that neither data nor social relationships are visible to unauthorized users and provides availability through replication and authentication of updates. We evaluate DECENT through simulation and experiments on the PlanetLab network and show that DECENT is able to replicate the main functionality of current centralized OSNs with manageable overhead.
Edit Distance to Monotonicity in Sliding Windows
Venue: arXiv cs.DS 2011
Year: 2011

Given a stream of items each associated with a numerical value, its edit distance to monotonicity is the minimum number of items to remove so that the remaining items are non-decreasing with respect to the numerical value. The space complexity of estimating the edit distance to monotonicity of a data stream is becoming well-understood over the past few years. Motivated by applications on network quality monitoring, we extend the study to estimating the edit distance to monotonicity of a sliding window covering the $w$ most recent items in the stream for any $w \ge 1$. We give a deterministic algorithm which can return an estimate within a factor of $(4+\eps)$ using $O(\frac{1}{\eps^2} \log^2(\eps w))$ space. We also extend the study in two directions. First, we consider a stream where each item is associated with a value from a partial ordered set. We give a randomized $(4+ε)$-approximate algorithm using $O(\frac{1}{ε^2} \log ε^2 w \log w)$ space. Second, we consider an out-of-order stream where each item is associated with a creation time and a numerical value, and items may be out of order with respect to their creation times. The goal is to estimate the edit distance to monotonicity with respect to the numerical value of items arranged in the order of creation times. We show that any randomized constant-approximate algorithm requires linear space.