OpenRaiser/Intern-Atlas huggingface dataset:
Measuring the Optimality of Hadoop Optimization
Venue: arXiv cs.DC 2013
Year: 2013

In recent years, much research has focused on how to optimize Hadoop jobs. Their approaches are diverse, ranging from improving HDFS and Hadoop job scheduler to optimizing parameters in Hadoop configurations. Despite their success in improving the performance of Hadoop jobs, however, very little is known about the limit of their optimization performance. That is, how optimal is a given Hadoop optimization? When a Hadoop optimization method X improves the performance of a job by Y %, how do we know if this improvement is as good as it can be? To answer this question, in this paper, we first examine the ideal best case, the lower bound, of running time for Hadoop jobs and develop a measure to accurately estimate how optimal a given Hadoop optimization is with respect to the lower bound. Then, we demonstrate how one may exploit the proposed measure to improve the optimization of Hadoop jobs.
Content Distribution by Multiple Multicast Trees and Intersession Cooperation: Optimal Algorithms and Approximations
Venue: arXiv cs.NI 2013
Year: 2013

In traditional massive content distribution with multiple sessions, the sessions form separate overlay networks and operate independently, where some sessions may suffer from insufficient resources even though other sessions have excessive resources. To cope with this problem, we consider the universal swarming approach, which allows multiple sessions to cooperate with each other. We formulate the problem of finding the optimal resource allocation to maximize the sum of the session utilities and present a subgradient algorithm which converges to the optimal solution in the time-average sense. The solution involves an NP-hard subproblem of finding a minimum-cost Steiner tree. We cope with this difficulty by using a column generation method, which reduces the number of Steiner-tree computations. Furthermore, we allow the use of approximate solutions to the Steiner-tree subproblem. We show that the approximation ratio to the overall problem turns out to be no less than the reciprocal of the approximation ratio to the Steiner-tree subproblem. Simulation results demonstrate that universal swarming improves the performance of resource-poor sessions with negligible impact to resource-rich sessions. The proposed approach and algorithm are expected to be useful for infrastructure-based content distribution networks with long-lasting sessions and relatively stable network environment.
Spatio-Temporal Queries for moving objects Data warehousing
Venue: arXiv cs.DB 2013
Year: 2013

In the last decade, Moving Object Databases (MODs) have attracted a lot of attention from researchers. Several research works were conducted to extend traditional database techniques to accommodate the new requirements imposed by the continuous change in location information of moving objects. Managing, querying, storing, and mining moving objects were the key research directions. This extensive interest in moving objects is a natural consequence of the recent ubiquitous location-aware devices, such as PDAs, mobile phones, etc., as well as the variety of information that can be extracted from such new databases. In this paper we propose a Spatio-Temporal data warehousing (STDW) for efficiently querying location information of moving objects. The proposed schema introduces new measures like direction majority and other direction-based measures that enhance the decision making based on location information.
An improvement of the Feng-Rao bound for primary codes
Venue: arXiv cs.IT 2013
Year: 2013

We present a new bound for the minimum distance of a general primary linear code. For affine variety codes defined from generalised C_{ab} curves the new bound often improves dramatically on the Feng-Rao bound for primary codes. The method does not only work for the minimum distance but can be applied to any generalised Hamming weight
Compressive sensing based beamforming for noisy measurements
Venue: arXiv cs.IT 2013
Year: 2013

Compressive sensing is the newly emerging method in information technology that could impact array beamforming and the associated engineering applications. However, practical measurements are inevitably polluted by noise from external interference and internal acquisition process. Then, compressive sensing based beamforming was studied in this work for those noisy measurements with a signal-to-noise ratio. In this article, we firstly introduced the fundamentals of compressive sensing theory. After that, we implemented two algorithms (CSB-I and CSB-II). Both algorithms are proposed for those presumably spatially sparse and incoherent signals. The two algorithms were examined using a simple simulation case and a practical aeroacoustic test case. The simulation case clearly shows that the CSB-I algorithm is quite sensitive to the sensing noise. The CSB-II algorithm, on the other hand, is more robust to noisy measurements. The results by CSB-II at $\mathrm{SNR}=-10\,$dB are still reasonable with good resolution and sidelobe rejection. Therefore, compressive sensing beamforming can be considered as a promising array signal beamforming method for those measurements with inevitably noisy interference.
Location Verification Systems in Emerging Wireless Networks
Venue: arXiv cs.NI 2013
Year: 2013

As location-based techniques and applications become ubiquitous in emerging wireless networks, the verification of location information will become of growing importance. This has led in recent years to an explosion of activity related to location verification techniques in wireless networks, with a specific focus on Intelligent Transport Systems (ITS) being evident. Such focus is largely due to the mission-critical nature of vehicle location verification within the ITS scenario. In this work we review recent research in wireless location verification related to the vehicular network scenario. We particularly focus on location verification systems that rely on formal mathematical classification frameworks, showing how many systems are either partially or fully encompassed by such frameworks.
Improving Data Security in Infrastructure Networks Based on Unipath Routing
Venue: arXiv cs.NI 2013
Year: 2013

An infrastructure network is a self-organizing network which uses Access Point (AP) of wireless links that connecting one node with another. These nodes can communicate without using ad hoc, instead these nodes form an arbitrary topology (BSS/ESS) in which these nodes play the role of routers. Though the efficiency of Infrastructure networks is high, they are highly vulnerable to security attacks. Detecting/Preventing these attacks over the network is highly challenging task. Many solutions are proposed to provide authentication, confidentiality, availability, secure routing and intrusion avoidance in infrastructure networks. Providing security in such dynamically changing networks is a hard task. Characteristic of infrastructure network should also be taken into consideration in order to design efficient solutions. In this study, we focus on efficiently increasing the flow transmission confidentiality in infrastructure networks based on multi-path routing. In order to increase confidentiality of transmitted data, we take advantage of the existence of multiple paths between nodes in an infrastructure network with the help of Access Point. In this approach the original data is split into package and are forwarded through access point. The encrypted packets are then forwarded in different disjoint paths that exist between sender and receiver. Even if an attacker succeeds to obtain one or more transmitted packets, the probability of reconstructing the original message is very low.
Performance Analysis of Clustering Algorithms for Gene Expression Data
Venue: arXiv cs.CE 2013
Year: 2013

Microarray technology is a process that allows thousands of genes simultaneously monitor to various experimental conditions. It is used to identify the co-expressed genes in specific cells or tissues that are actively used to make proteins, This method is used to analysis the gene expression, an important task in bioinformatics research. Cluster analysis of gene expression data has proved to be a useful tool for identifying co-expressed genes, biologically relevant groupings of genes and samples. In this paper we analysed K-Means with Automatic Generations of Merge Factor for ISODATA- AGMFI, to group the microarray data sets on the basic of ISODATA. AGMFI is to generate initial values for merge and Spilt factor, maximum merge times instead of selecting efficient values as in ISODATA. The initial seeds for each cluster were normally chosen either sequentially or randomly. The quality of the final clusters was found to be influenced by these initial seeds. For the real life problems, the suitable number of clusters cannot be predicted. To overcome the above drawback the current research focused on developing the clustering algorithms without giving the initial number of clusters.
Prophet Inequalities with Limited Information
Venue: arXiv cs.DS 2013
Year: 2013

In the classical prophet inequality, a gambler observes a sequence of stochastic rewards $V_1,...,V_n$ and must decide, for each reward $V_i$, whether to keep it and stop the game or to forfeit the reward forever and reveal the next value $V_i$. The gambler's goal is to obtain a constant fraction of the expected reward that the optimal offline algorithm would get. Recently, prophet inequalities have been generalized to settings where the gambler can choose $k$ items, and, more generally, where he can choose any independent set in a matroid. However, all the existing algorithms require the gambler to know the distribution from which the rewards $V_1,...,V_n$ are drawn. The assumption that the gambler knows the distribution from which $V_1,...,V_n$ are drawn is very strong. Instead, we work with the much simpler assumption that the gambler only knows a few samples from this distribution. We construct the first single-sample prophet inequalities for many settings of interest, whose guarantees all match the best possible asymptotically, \emph{even with full knowledge of the distribution}. Specifically, we provide a novel single-sample algorithm when the gambler can choose any $k$ elements whose analysis is based on random walks with limited correlation. In addition, we provide a black-box method for converting specific types of solutions to the related \emph{secretary problem} to single-sample prophet inequalities, and apply it to several existing algorithms. Finally, we provide a constant-sample prophet inequality for constant-degree bipartite matchings. We apply these results to design the first posted-price and multi-dimensional auction mechanisms with limited information in settings with asymmetric bidders.
Partially Blind Instantly Decodable Network Codes for Lossy Feedback Environment
Venue: arXiv cs.NI 2013
Year: 2013

In this paper, we study the multicast completion and decoding delay minimization problems of instantly decodable network coding (IDNC) in the case of lossy feedback. In such environments, the sender falls into uncertainties about packet reception at the different receivers, which forces it to perform partially blind selections of packet combinations in subsequent transmissions. To determine efficient partially blind policies that handle the completion and decoding delays of IDNC in such environment, we first extend the perfect feedback formulation in [2], [3] to the lossy feedback environment, by incorporating the uncertainties resulting from unheard feedback events in these formulations. For the completion delay problem, we use this formulation to identify the maximum likelihood state of the network in events of unheard feedback, and employ it to design a partially blind graph update extension to the multicast IDNC algorithm in [3]. For the decoding delay problem, we derive an expression for the expected decoding delay increment for any arbitrary transmission. This expression is then used to derive the optimal policy to reduce the decoding delay in such lossy feedback environment. Results show that our proposed solution both outperforms other approaches and achieves a tolerable degradation even at relatively high feedback loss rates.
Pebble Games, Proof Complexity, and Time-Space Trade-offs
Venue: arXiv cs.CC 2013
Year: 2013

Pebble games were extensively studied in the 1970s and 1980s in a number of different contexts. The last decade has seen a revival of interest in pebble games coming from the field of proof complexity. Pebbling has proven to be a useful tool for studying resolution-based proof systems when comparing the strength of different subsystems, showing bounds on proof space, and establishing size-space trade-offs. This is a survey of research in proof complexity drawing on results and tools from pebbling, with a focus on proof space lower bounds and trade-offs between proof size and proof space.
Empirical Evidence of Large-Scale Diversity in API Usage of Object-Oriented Software
Venue: arXiv cs.SE 2013
Year: 2013

In this paper, we study how object-oriented classes are used across thousands of software packages. We concentrate on "usage diversity'", defined as the different statically observable combinations of methods called on the same object. We present empirical evidence that there is a significant usage diversity for many classes. For instance, we observe in our dataset that Java's String is used in 2460 manners. We discuss the reasons of this observed diversity and the consequences on software engineering knowledge and research.
Explicit Maximally Recoverable Codes with Locality
Venue: arXiv cs.IT 2013
Year: 2013

Consider a systematic linear code where some (local) parity symbols depend on few prescribed symbols, while other (heavy) parity symbols may depend on all data symbols. Local parities allow to quickly recover any single symbol when it is erased, while heavy parities provide tolerance to a large number of simultaneous erasures. A code as above is maximally-recoverable if it corrects all erasure patterns which are information theoretically recoverable given the code topology. In this paper we present explicit families of maximally-recoverable codes with locality. We also initiate the study of the trade-off between maximal recoverability and alphabet size.
Human Brain Mapping based on COLD Signal Hemodynamic Response and Electrical Neuroimaging
Venue: arXiv cs.ET 2013
Year: 2013

To understand Working of Human Brain measurements related to the brain function are required. These measurements should be possibly non-invasive. Brain should be disturbed as less as possible during the measurement. Integration of various modalities plays a vital role in understanding the cognitive and the behavioral changes in the human brain. It is an important source of converging evidence about specific aspects of neural functions and dysfunctions under certain pathological conditions. Focal changes in cortical blood flow are tightly coupled with the changes in neuronal activity. This constitutes the option to map the hemodynamic response and infer principles of the cortical processing, even of complex tasks. The very high temporal resolution of EEG and good spatial resolution by NIRS make this concurrent measurement unique to study the spatio-temporal dynamics of large scale neuronal networks in the human brain. Such integration of two techniques will help to overcome the limitations of a specific method. Such as insensitivity of electroencephalogram (EEG) to unsynchronized neural events or lack of near infrared spectroscopy (NIRS) to low metabolic demand. A combination of EEG and NIRS will be more informative than the two separate analyses in both modalities.
A QPTAS for Maximum Weight Independent Set of Polygons with Polylogarithmically Many Vertices
Venue: arXiv cs.DS 2013
Year: 2013

The Maximum Weight Independent Set of Polygons problem is a fundamental problem in computational geometry. Given a set of weighted polygons in the 2-dimensional plane, the goal is to find a set of pairwise non-overlapping polygons with maximum total weight. Due to its wide range of applications, the MWISP problem and its special cases have been extensively studied both in the approximation algorithms and the computational geometry community. Despite a lot of research, its general case is not well-understood. Currently the best known polynomial time algorithm achieves an approximation ratio of n^(epsilon) [Fox and Pach, SODA 2011], and it is not even clear whether the problem is APX-hard. We present a (1+epsilon)-approximation algorithm, assuming that each polygon in the input has at most a polylogarithmic number of vertices. Our algorithm has quasi-polynomial running time. We use a recently introduced framework for approximating maximum weight independent set in geometric intersection graphs. The framework has been used to construct a QPTAS in the much simpler case of axis-parallel rectangles. We extend it in two ways, to adapt it to our much more general setting. First, we show that its technical core can be reduced to the case when all input polygons are triangles. Secondly, we replace its key technical ingredient which is a method to partition the plane using only few edges such that the objects stemming from the optimal solution are evenly distributed among the resulting faces and each object is intersected only a few times. Our new procedure for this task is not more complex than the original one, and it can handle the arising difficulties due to the arbitrary angles of the polygons. Note that already this obstacle makes the known analysis for the above framework fail. Also, in general it is not well understood how to handle this difficulty by efficient approximation algorithms.
Rule Based Transliteration Scheme for English to Punjabi
Venue: arXiv cs.CL 2013
Year: 2013

Machine Transliteration has come out to be an emerging and a very important research area in the field of machine translation. Transliteration basically aims to preserve the phonological structure of words. Proper transliteration of name entities plays a very significant role in improving the quality of machine translation. In this paper we are doing machine transliteration for English-Punjabi language pair using rule based approach. We have constructed some rules for syllabification. Syllabification is the process to extract or separate the syllable from the words. In this we are calculating the probabilities for name entities (Proper names and location). For those words which do not come under the category of name entities, separate probabilities are being calculated by using relative frequency through a statistical machine translation toolkit known as MOSES. Using these probabilities we are transliterating our input text from English to Punjabi.
A Faster Tableau for CTL*
Venue: arXiv cs.LO 2013
Year: 2013

There have been several recent suggestions for tableau systems for deciding satisfiability in the practically important branching time temporal logic known as CTL*. In this paper we present a streamlined and more traditional tableau approach built upon the author's earlier theoretical work. Soundness and completeness results are proved. A prototype implementation demonstrates the significantly improved performance of the new approach on a range of test formulas. We also see that it compares favourably to state of the art, game and automata based decision procedures.
Profile Trees for Büchi Word Automata, with Application to Determinization
Venue: arXiv cs.FL 2013
Year: 2013

The determinization of Buchi automata is a celebrated problem, with applications in synthesis, probabilistic verification, and multi-agent systems. Since the 1960s, there has been a steady progress of constructions: by McNaughton, Safra, Piterman, Schewe, and others. Despite the proliferation of solutions, they are all essentially ad-hoc constructions, with little theory behind them other than proofs of correctness. Since Safra, all optimal constructions employ trees as states of the deterministic automaton, and transitions between states are defined operationally over these trees. The operational nature of these constructions complicates understanding, implementing, and reasoning about them, and should be contrasted with complementation, where a solid theory in terms of automata run DAGs underlies modern constructions. In 2010, we described a profile-based approach to Buchi complementation, where a profile is simply the history of visits to accepting states. We developed a structural theory of profiles and used it to describe a complementation construction that is deterministic in the limit. Here we extend the theory of profiles to prove that every run DAG contains a profile tree with at most a finite number of infinite branches. We then show that this property provides a theoretical grounding for a new determinization construction where macrostates are doubly preordered sets of states. In contrast to extant determinization constructions, transitions in the new construction are described declaratively rather than operationally.
Slot Games for Detecting Timing Leaks of Programs
Venue: arXiv cs.PL 2013
Year: 2013

In this paper we describe a method for verifying secure information flow of programs, where apart from direct and indirect flows a secret information can be leaked through covert timing channels. That is, no two computations of a program that differ only on high-security inputs can be distinguished by low-security outputs and timing differences. We attack this problem by using slot-game semantics for a quantitative analysis of programs. We show how slot-games model can be used for performing a precise security analysis of programs, that takes into account both extensional and intensional properties of programs. The practicality of this approach for automated verification is also shown.
AWGN Channel Capacity of Energy Harvesting Transmitters with a Finite Energy Buffer
Venue: arXiv cs.IT 2013
Year: 2013

We consider an AWGN channel with a transmitter powered by an energy harvesting source. The node is equipped with a finite energy buffer. Such a system can be modelled as a channel with side information (about energy in the energy buffer) causally known at the transmitter. The receiver may or may not have the side information. We prove that Markov energy management policies are sufficient to achieve the capacity of the system and provide a single letter characterization for the capacity. The computation of the capacity is expensive. Therefore, we discuss an achievable scheme that is easy to compute. This achievable rate converges to the infinite buffer capacity as the buffer length increases.
Joint Channel Estimation and Channel Decoding in Physical-Layer Network Coding Systems: An EM-BP Factor Graph Framework
Venue: arXiv cs.IT 2013
Year: 2013

This paper addresses the problem of joint channel estimation and channel decoding in physical-layer network coding (PNC) systems. In PNC, multiple users transmit to a relay simultaneously. PNC channel decoding is different from conventional multi-user channel decoding: specifically, the PNC relay aims to decode a network-coded message rather than the individual messages of the users. Although prior work has shown that PNC can significantly improve the throughput of a relay network, the improvement is predicated on the availability of accurate channel estimates. Channel estimation in PNC, however, can be particularly challenging because of 1) the overlapped signals of multiple users; 2) the correlations among data symbols induced by channel coding; and 3) time-varying channels. We combine the expectation-maximization (EM) algorithm and belief propagation (BP) algorithm on a unified factor-graph framework to tackle these challenges. In this framework, channel estimation is performed by an EM subgraph, and channel decoding is performed by a BP subgraph that models a virtual encoder matched to the target of PNC channel decoding. Iterative message passing between these two subgraphs allow the optimal solutions for both to be approached progressively. We present extensive simulation results demonstrating the superiority of our PNC receivers over other PNC receivers.