OpenRaiser/Intern-Atlas huggingface dataset:
A Unified Approach to Online Allocation Algorithms via Randomized Dual Fitting
Venue: arXiv cs.DS 2013
Year: 2013

We present a unified framework for designing and analyzing algorithms for online budgeted allocation problems (including online matching) and their generalization, the Online Generalized Assignment Problem (OnGAP). These problems have been intensively studied as models of how to allocate impressions for online advertising. In contrast to previous analyses of online budgeted allocation algorithms (the so-called "balance" or "water-filling" family of algorithms) our analysis is based on the method of randomized dual fitting, analogous to the recent analysis of the RANKING algorithm for online matching due to Devanur et al. Our main contribution is thus to provide a unified method of proof that simultaneously derives the optimal competitive ratio bounds for online matching and online fractional budgeted allocation. The same method of proof also supplies $(1-1/e)$ competitive ratio bounds for greedy algorithms for both problems, in the random order arrival model; this simplifies existing analyses of greedy online allocation algorithms with random order of arrivals, while also strengthening them to apply to a larger family of greedy algorithms. Finally, for the more general OnGAP problem, we show that no algorithm can be constant-competitive; instead we present an algorithm whose competitive ratio depends logarithmically on a certain parameter of the problem instance, and we show that this dependence cannot be improved.
Rewriting XPath Queries using View Intersections: Tractability versus Completeness
Venue: arXiv cs.DB 2013
Year: 2013

The standard approach for optimization of XPath queries by rewriting using views techniques consists in navigating inside a view's output, thus allowing the usage of only one view in the rewritten query. Algorithms for richer classes of XPath rewritings, using intersection or joins on node identifiers, have been proposed, but they either lack completeness guarantees, or require additional information about the data. We identify the tightest restrictions under which an XPath can be rewritten in polynomial time using an intersection of views and propose an algorithm that works for any documents or type of identifiers. As a side-effect, we analyze the complexity of the related problem of deciding if an XPath with intersection can be equivalently rewritten as one without intersection or union. We extend our formal study of the view-based rewriting problem for XPath by describing also (i) algorithms for more complex rewrite plans, with no limitations on the number of intersection and navigation steps inside view outputs they employ, and (ii) adaptations of our techniques to deal with XML documents without persistent node Ids, in the presence of XML keys. Complementing our computational complexity study, we describe a proof-of-concept implementation of our techniques and possible choices that may speed up execution in practice, regarding how rewrite plans are built, tested and executed. We also give a thorough experimental evaluation of these techniques, focusing on scalability and the running time improvements achieved by the execution of view-based plans.
Implicit Resolution
Venue: arXiv cs.LO 2013
Year: 2013

Let Ωbe a set of unsatisfiable clauses, an implicit resolution refutation of Ωis a circuit βwith a resolution proof α of the statement "βdescribes a correct tree-like resolution refutation of Ω". We show that such system is p-equivalent to Extended Frege. More generally, let τ be a tautology, a [P, Q]-proof of τ is a pair (α,β) s.t. αis a P-proof of the statement "βis a circuit describing a correct Q-proof of τ". We prove that [EF,P] \leq p [R,P] for arbitrary Cook-Reckhow proof system P.
Multi-Objective Particle Swarm Optimization for Facility Location Problem in Wireless Mesh Networks
Venue: arXiv cs.NI 2013
Year: 2013

Wireless mesh networks have seen a real progress due of their implementation at a low cost. They present one of Next Generation Networks technologies and can serve as home, companies and universities networks. In this paper, we propose and discuss a new multi-objective model for nodes deployment optimization in Multi-Radio Multi-Channel Wireless Mesh Networks. We exploit the trade-off between network cost and the overall network performance. This optimization problem is solved simultaneously by using a meta-heuristic method that returns a non-dominated set of near optimal solutions. A comparative study was driven to evaluate the efficiency of the proposed model.
An Investigation of the Incidences of Repetitive Strain Injury among computer Users in Nigeria
Venue: arXiv cs.HC 2013
Year: 2013

Computer has been incorporated into day to day activities of almost every field of human endeavour, offices to different shops. Therefore many people are now working with computer for longer hours of time. There is no doubt that this incorporation of computer has helped users a lot but it also brings problems to the users. One of the problems is Repetitive Strain Injury (RSI). Five hundred and thirty one (531) questionnaires were personally administered to different categories of people that use computer in various works of life, ranging from banking sector, civil service, educational sector, health sector to private sector. The distribution cut across different professions. A statistical analysis was conducted on the data obtained using frequency distribution, Pearson Correlation and Linear Regression. The result obtained showed that 94.3% of the respondents suffered pain from one or more parts of the body. 86.8% of the respondents suffered from eyestrain, 63.9% suffered from low back pain, 67.4% with wrist pain, 64.7% finger pain while the least suffered pain was foot pain which only 19% responded positively to it. There are significant relationships between duration of computer usage, type of chair used, type and size of monitor used and the incidence of RSI. RSI modeled was formulated through linear regression which showed that a unit change in computer will result in corresponding 1.76 unit increases in RSI and a unit change in ergonomic deficiency will also result in corresponding 0.66 increases in RSI. The existence of RSI was established and it was discovered that the more time spent on the computer system, the more the proximity of having strain or pain in one or more part(s) of the body.
Theoretic Shaping Bounds for Single Letter Constraints and Mismatched Decoding
Venue: arXiv cs.IT 2013
Year: 2013

Shaping gain is attained in schemes where a shaped subcode is chosen from a larger codebook by a codeword selection process. This includes the popular method of Trellis Shaping (TS), originally proposed by Forney for average power reduction. The decoding process of such schemes is mismatched, since it is aware of only the large codebook. This study models such schemes by a random code construction and derives achievable bounds on the transmission rate under matched and mismatched decoding. For matched decoding the bound is obtained using a modified asymptotic equipartition property (AEP) theorem derived to suit this particular code construction. For mismatched decoding, relying on the large codebook performance is generally wrong, since the performance of the non-typical codewords within the large codebook may differ substantially from the typical ones. Hence, we present two novel lower bounds on the capacity under mismatched decoding. The first is based upon Gallager's random exponent, whereas the second on a modified version of the joint-typicality decoder.
Automated, Credible Autocoding of An Unmanned Aggressive Maneuvering Car Controller
Venue: arXiv cs.SY 2013
Year: 2013

This article describes the application of a credible autocoding framework for control systems towards a nonlinear car controller example. The framework generates code, along with guarantees of high level functional properties about the code that can be independently verified. These high-level functional properties not only serves as a certificate of good system behvaior but also can be used to guarantee the absence of runtime errors. In one of our previous works, we have constructed a prototype autocoder with proofs that demonstrates this framework in a fully automatic fashion for linear and quasi-nonlinear controllers. With the nonlinear car example, we propose to further extend the prototype's dataflow annotation language environment with with several new annotation symbols to enable the expression of general predicates and dynamical systems. We demonstrate manually how the new extensions to the prototype autocoder work on the car controller using the output language Matlab. Finally, we discuss the requirements and scalability issues of the automatic analysis and verification of the documented output code.
Security Issues on Cloud Computing
Venue: arXiv cs.CR 2013
Year: 2013

The Cloud Computing concept offers dynamically scalable resources provisioned as a service over the Internet.Economic benefits are the main driver for the Cloud, since it promises the reduction of capital expenditure and operational expenditure.In order for this to become reality, however, there are still some challenges to be solved. Amongst these are security and trust issues, since the user data has to be released to the Cloud and thus leaves the protection sphere of the data owner. Most of the discussions on these topics are mainly driven by arguments related to organisational means. This paper focuses on various security issues arising from the usage of Cloud services and especially by the rapid development of Cloud computing arena. It also discusses basic security model followed by various High Level Security threats in the industry.
Tree Codes and a Conjecture on Exponential Sums
Venue: arXiv cs.CC 2013
Year: 2013

We propose a new conjecture on some exponential sums. These particular sums have not apparently been considered in the literature. Subject to the conjecture we obtain the first effective construction of asymptotically good tree codes. The available numerical evidence is consistent with the conjecture and is sufficient to certify codes for significant-length communications.
Toward Cloud-based Vehicular Networks with Efficient Resource Management
Venue: arXiv cs.DC 2013
Year: 2013

In the era of Internet of Things, all components in intelligent transportation systems will be connected to improve transport safety, relieve traffic congestion, reduce air pollution and enhance the comfort of driving. The vision of all vehicles connected poses a significant challenge to the collection and storage of large amounts of traffic-related data. In this article, we propose to integrate cloud computing into vehicular networks such that the vehicles can share computation resources, storage resources and bandwidth resources. The proposed architecture includes a vehicular cloud, a roadside cloud, and a central cloud. Then, we study cloud resource allocation and virtual machine migration for effective resource management in this cloud-based vehicular network. A game-theoretical approach is presented to optimally allocate cloud resources. Virtual machine migration due to vehicle mobility is solved based on a resource reservation scheme.
Securing Cognitive Radio Networks against Primary User Emulation Attacks
Venue: arXiv cs.ET 2013
Year: 2013

Cognitive Radio (CR) is a promising technology for next-generation wireless networks in order to efficiently utilize the limited spectrum resources and satisfy the rapidly increasing demand for wireless applications and services. Security is a very important but not well addressed issue in CR networks. In this paper we focus on security problems arising from Primary User Emulation (PUE) attacks in CR networks. We present a comprehensive introduction to PUE attacks, from the attacking rationale and its impact on CR networks, to detection and defense approaches. In order to secure CR networks against PUE attacks, a two-level database-assisted detection approach is proposed to detect such attacks. Energy detection and location verification are combined for fast and reliable detection. An admission control based defense approach is proposed to mitigate the performance degradation of a CR network under a PUE attack. Illustrative results are presented to demonstrate the effectiveness of the proposed detection and defense approaches.
Retroactive Anti-Jamming for MISO Broadcast Channels
Venue: arXiv cs.IT 2013
Year: 2013

Jamming attacks can significantly impact the performance of wireless communication systems. In addition to reducing the capacity, such attacks may lead to insurmountable overhead in terms of re-transmissions and increased power consumption. In this paper, we consider the multiple-input single-output (MISO) broadcast channel (BC) in the presence of a jamming attack in which a subset of the receivers can be jammed at any given time. Further, countermeasures for mitigating the effects of such jamming attacks are presented. The effectiveness of these anti-jamming countermeasures is quantified in terms of the degrees-of-freedom (DoF) of the MISO BC under various assumptions regarding the availability of the channel state information (CSIT) and the jammer state information at the transmitter (JSIT). The main contribution of this paper is the characterization of the DoF region of the two user MISO BC under various assumptions on the availability of CSIT and JSIT. Partial extensions to the multi-user broadcast channels are also presented.
Respondent-Driven Sampling in Online Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

Respondent-driven sampling (RDS) is a commonly used method for acquiring data on hidden communities, i.e., those that lack unbiased sampling frames or face social stigmas that make their mem- bers unwilling to identify themselves. Obtaining accurate statistical data about such communities is important because, for instance, they often have different health burdens from the greater population, and without good statistics it is hard and expensive to effectively reach them for pre- vention or treatment interventions. Online social networks (OSN) have the potential to transform RDS for the better. We present a new RDS recruitment protocol for (OSNs) and show via simulation that it out- performs the standard RDS protocol in terms of sampling accuracy and approaches the accuracy of Markov chain Monte Carlo random walks.
Coding with Scrambling, Concatenation, and HARQ for the AWGN Wire-Tap Channel: A Security Gap Analysis
Venue: arXiv cs.IT 2013
Year: 2013

This study examines the use of nonsystematic channel codes to obtain secure transmissions over the additive white Gaussian noise (AWGN) wire-tap channel. Unlike the previous approaches, we propose to implement nonsystematic coded transmission by scrambling the information bits, and characterize the bit error rate of scrambled transmissions through theoretical arguments and numerical simulations. We have focused on some examples of Bose-Chaudhuri-Hocquenghem (BCH) and low-density parity-check (LDPC) codes to estimate the security gap, which we have used as a measure of physical layer security, in addition to the bit error rate. Based on a number of numerical examples, we found that such a transmission technique can outperform alternative solutions. In fact, when an eavesdropper (Eve) has a worse channel than the authorized user (Bob), the security gap required to reach a given level of security is very small. The amount of degradation of Eve's channel with respect to Bob's that is needed to achieve sufficient security can be further reduced by implementing scrambling and descrambling operations on blocks of frames, rather than on single frames. While Eve's channel has a quality equal to or better than that of Bob's channel, we have shown that the use of a hybrid automatic repeat-request (HARQ) protocol with authentication still allows achieving a sufficient level of security. Finally, the secrecy performance of some practical schemes has also been measured in terms of the equivocation rate about the message at the eavesdropper and compared with that of ideal codes.
Nonparametric Decentralized Sequential Detection via Universal Source Coding
Venue: arXiv cs.IT 2013
Year: 2013

We consider nonparametric or universal sequential hypothesis testing problem when the distribution under the null hypothesis is fully known but the alternate hypothesis corresponds to some other unknown distribution. These algorithms are primarily motivated from spectrum sensing in Cognitive Radios and intruder detection in wireless sensor networks. We use easily implementable universal lossless source codes to propose simple algorithms for such a setup. The algorithms are first proposed for discrete alphabet. Their performance and asymptotic properties are studied theoretically. Later these are extended to continuous alphabets. Their performance with two well known universal source codes, Lempel-Ziv code and Krichevsky-Trofimov estimator with Arithmetic Encoder are compared. These algorithms are also compared with the tests using various other nonparametric estimators. Finally a decentralized version utilizing spatial diversity is also proposed. Its performance is analysed and asymptotic properties are proved.
A New Algorithm of Speckle Filtering using Stochastic Distances
Venue: arXiv cs.IT 2013
Year: 2013

This paper presents a new approach for filter design based on stochastic distances and tests between distributions. A window is defined around each pixel, overlapping samples are compared and only those which pass a goodness-of-fit test are used to compute the filtered value. The technique is applied to intensity SAR data with homogeneous regions using the Gamma model. The proposal is compared with the Lee's filter using a protocol based on Monte Carlo. Among the criteria used to quantify the quality of filters, we employ the equivalent number of looks, line and edge preservation. Moreover, we also assessed the filters by the Universal Image Quality Index and the Pearson's correlation on edges regions.
Resource Allocation in MIMO Radar With Multiple Targets for Non-Coherent Localization
Venue: arXiv cs.IT 2013
Year: 2013

In a MIMO radar network the multiple transmit elements may emit waveforms that differ on power and bandwidth. In this paper, we are asking, given that these two resources are limited, what is the optimal power, optimal bandwidth and optimal joint power and bandwidth allocation for best localization of multiple targets. The well known Crámer-Rao lower bound for target localization accuracy is used as a figure of merit and approximate solutions are found by minimizing a sequence of convex problems. Their quality is assessed through extensive numerical simulations and with the help of a lower-bound on the true solution. Simulations results reveal that bandwidth allocation policies have a definitely stronger impact on performance than power.
Image Set based Collaborative Representation for Face Recognition
Venue: arXiv cs.CV 2013
Year: 2013

With the rapid development of digital imaging and communication technologies, image set based face recognition (ISFR) is becoming increasingly important. One key issue of ISFR is how to effectively and efficiently represent the query face image set by using the gallery face image sets. The set-to-set distance based methods ignore the relationship between gallery sets, while representing the query set images individually over the gallery sets ignores the correlation between query set images. In this paper, we propose a novel image set based collaborative representation and classification method for ISFR. By modeling the query set as a convex or regularized hull, we represent this hull collaboratively over all the gallery sets. With the resolved representation coefficients, the distance between the query set and each gallery set can then be calculated for classification. The proposed model naturally and effectively extends the image based collaborative representation to an image set based one, and our extensive experiments on benchmark ISFR databases show the superiority of the proposed method to state-of-the-art ISFR methods under different set sizes in terms of both recognition rate and efficiency.
Detect adverse drug reactions for drug Atorvastatin
Venue: arXiv cs.CE 2013
Year: 2013

Adverse drug reactions (ADRs) are big concern for public health. ADRs are one of most common causes to withdraw some drugs from markets. Now two major methods for detecting ADRs are spontaneous reporting system (SRS), and prescription event monitoring (PEM). The World Health Organization (WHO) defines a signal in pharmacovigilance as "any reported information on a possible causal relationship between an adverse event and a drug, the relationship being unknown or incompletely documented previously". For spontaneous reporting systems, many machine learning methods are used to detect ADRs, such as Bayesian confidence propagation neural network (BCPNN), decision support methods, genetic algorithms, knowledge based approaches, etc. One limitation is the reporting mechanism to submit ADR reports, which has serious underreporting and is not able to accurately quantify the corresponding risk. Another limitation is hard to detect ADRs with small number of occurrences of each drug-event association in the database. In this paper we propose feature selection approach to detect ADRs from The Health Improvement Network (THIN) database. First a feature matrix, which represents the medical events for the patients before and after taking drugs, is created by linking patients' prescriptions and corresponding medical events together. Then significant features are selected based on feature selection methods, comparing the feature matrix before patients take drugs with one after patients take drugs. Finally the significant ADRs can be detected from thousands of medical events based on corresponding features. Experiments are carried out on the drug Atorvastatin. Good performance is achieved.
Enhanced Data Integration for LabVIEW Laboratory Systems
Venue: arXiv cs.DB 2013
Year: 2013

Integrating data is a basic concern in many accredited laboratories that perform a large variety of measurements. However, the present working style in engineering faculties does not focus much on this aspect. To deal with this challenge, we developed an educational platform that allows characterization of acquisition ensembles, generation of Web pages for lessons, as well as transformation of measured data and storage in a common format. As generally we had to develop individual parsers for each instrument, we also added the possibility to integrate the LabVIEW workbench, often used for rapid development of applications in electrical engineering and automatic control. This paper describes how we configure the platform for specific equipment, i.e. how we model it, how we create the learning material and how we integrate the results in a central database. It also introduces a case study for collecting data from a thermocouple-based acquisition system based on LabVIEW, used by students for a laboratory of measurement technologies and transducers.
Twins:Device-free Object Tracking using Passive Tags
Venue: arXiv cs.NI 2013
Year: 2013

Without requiring objects to carry any transceiver, device-free based object tracking provides a promising solution for many localization and tracking systems to monitor non-cooperative objects such as intruders. However, existing device-free solutions mainly use sensors and active RFID tags, which are much more expensive compared to passive tags. In this paper, we propose a novel motion detection and tracking method using passive RFID tags, named Twins. The method leverages a newly observed phenomenon called critical state caused by interference among passive tags. We contribute to both theory and practice of such phenomenon by presenting a new interference model that perfectly explains this phenomenon and using extensive experiments to validate it. We design a practical Twins based intrusion detection scheme and implement a real prototype with commercial off-the-shelf reader and tags. The results show that Twins is effective in detecting the moving object, with low location error of 0.75m in average.