OpenRaiser/Intern-Atlas huggingface dataset:
Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms
Venue: arXiv cs.LG 2014
Year: 2014

We consider stochastic multi-armed bandit problems where the expected reward is a Lipschitz function of the arm, and where the set of arms is either discrete or continuous. For discrete Lipschitz bandits, we derive asymptotic problem specific lower bounds for the regret satisfied by any algorithm, and propose OSLB and CKL-UCB, two algorithms that efficiently exploit the Lipschitz structure of the problem. In fact, we prove that OSLB is asymptotically optimal, as its asymptotic regret matches the lower bound. The regret analysis of our algorithms relies on a new concentration inequality for weighted sums of KL divergences between the empirical distributions of rewards and their true distributions. For continuous Lipschitz bandits, we propose to first discretize the action space, and then apply OSLB or CKL-UCB, algorithms that provably exploit the structure efficiently. This approach is shown, through numerical experiments, to significantly outperform existing algorithms that directly deal with the continuous set of arms. Finally the results and algorithms are extended to contextual bandits with similarities.
On Queue-Size Scaling for Input-Queued Switches
Venue: arXiv cs.NI 2014
Year: 2014

We study the optimal scaling of the expected total queue size in an $n\times n$ input-queued switch, as a function of the number of ports $n$ and the load factor $ρ$, which has been conjectured to be $Θ(n/(1-ρ))$. In a recent work, the validity of this conjecture has been established for the regime where $1-ρ= O(1/n^2)$. In this paper, we make further progress in the direction of this conjecture. We provide a new class of scheduling policies under which the expected total queue size scales as $O(n^{1.5}(1-ρ)^{-1}\log(1/(1-ρ)))$ when $1-ρ= O(1/n)$. This is an improvement over the state of the art; for example, for $ρ= 1 - 1/n$ the best known bound was $O(n^3)$, while ours is $O(n^{2.5}\log n)$.
Adapted Approach for Fruit Disease Identification using Images
Venue: arXiv cs.CV 2014
Year: 2014

Diseases in fruit cause devastating problem in economic losses and production in agricultural industry worldwide. In this paper, an adaptive approach for the identification of fruit diseases is proposed and experimentally validated. The image processing based proposed approach is composed of the following main steps; in the first step K-Means clustering technique is used for the defect segmentation, in the second step some state of the art features are extracted from the segmented image, and finally images are classified into one of the classes by using a Multi-class Support Vector Machine. We have considered diseases of apple as a test case and evaluated our approach for three types of apple diseases namely apple scab, apple blotch and apple rot. Our experimental results express that the proposed solution can significantly support accurate detection and automatic identification of fruit diseases. The classification accuracy for the proposed solution is achieved up to 93%.
Distributed Resource Allocation in Device-to-Device Enhanced Cellular Networks
Venue: arXiv cs.IT 2014
Year: 2014

Cellular network performance can significantly benefit from direct device-to-device (D2D) communication, but interference from cochannel D2D communication limits the performance gain. In hybrid networks consisting of D2D and cellular links, finding the optimal interference management is challenging. In particular, we show that the problem of maximizing network throughput while guaranteeing predefined service levels to cellular users is non- convex and hence intractable. Instead, we adopt a distributed approach that is computationally extremely efficient, and requires minimal coordination, communication and cooperation among the nodes. The key algorithmic idea is a signaling mechanism that can be seen as a fictional pricing mechanism, that the base stations optimize and transmit to the D2D users, who then play a best response (i.e., selfishly) to this signal. Numerical results show that our algorithms converge quickly, have low overhead, and achieve a significant throughput gain, while maintaining the quality of cellular links at a predefined service level.
PHD-Store: An Adaptive SPARQL Engine with Dynamic Partitioning for Distributed RDF Repositories
Venue: arXiv cs.DB 2014
Year: 2014

Many repositories utilize the versatile RDF model to publish data. Repositories are typically distributed and geographically remote, but data are interconnected (e.g., the Semantic Web) and queried globally by a language such as SPARQL. Due to the network cost and the nature of the queries, the execution time can be prohibitively high. Current solutions attempt to minimize the network cost by redistributing all data in a preprocessing phase, but here are two drawbacks: (i) redistribution is based on heuristics that may not benefit many of the future queries; and (ii) the preprocessing phase is very expensive even for moderate size datasets. In this paper we propose PHD-Store, a SPARQL engine for distributed RDF repositories. Our system does not assume any particular initial data placement and does not require prepartitioning; hence, it minimizes the startup cost. Initially, PHD-Store answers queries using a potentially slow distributed semi-join algorithm, but adapts dynamically to the query load by incrementally redistributing frequently accessed data. Redistribution is done in a way that future queries can benefit from fast hash-based parallel execution. Our experiments with synthetic and real data verify that PHD-Store scales to very large datasets; many repositories; converges to comparable or better quality of partitioning than existing methods; and executes large query loads 1 to 2 orders of magnitude faster than our competitors.
Distributed Storage for Data Security
Venue: arXiv cs.IT 2014
Year: 2014

We study the secrecy of a distributed storage system for passwords. The encoder, Alice, observes a length-n password and describes it using two hints, which she then stores in different locations. The legitimate receiver, Bob, observes both hints. The eavesdropper, Eve, sees only one of the hints; Alice cannot control which. We characterize the largest normalized (by n) exponent that we can guarantee for the number of guesses it takes Eve to guess the password subject to the constraint that either the number of guesses it takes Bob to guess the password or the size of the list that Bob must form to guarantee that it contain the password approach 1 as n tends to infinity.
Formal Consistency Checking over Specifications in Natural Languages
Venue: arXiv cs.SE 2014
Year: 2014

Early stages of system development involve outlining desired features such as functionality, availability, or usability. Specifications are derived from these features that concretize vague ideas presented in natural languages. The challenge for the validation of specifications arises from the syntax and semantic gap between different representations and the need of automatic tools. In this paper, we present a requirement-consistency maintenance framework to produce consistent representations. The first part is the automatic translation from natural languages describing functionalities to formal logic with an abstraction of time. It extends pure syntactic parsing by adding semantic reasoning and the support of partitioning input and output variables. The second part is the use of synthesis techniques to examine if the requirements are consistent in terms of realizability. When the process fails, the formulas that cause the inconsistency are reported to locate the problem.
Design of Efficient Sampling Methods on Hybrid Social-Affiliation Networks
Venue: arXiv cs.SI 2014
Year: 2014

Graph sampling via crawling has become increasingly popular and important in the study of measuring various characteristics of large scale complex networks. While powerful, it is known to be challenging when the graph is loosely connected or disconnected which slows down the convergence of random walks and can cause poor estimation accuracy. In this work, we observe that the graph under study, or called target graph, usually does not exist in isolation. In many situations, the target graph is related to an auxiliary graph and an affiliation graph, and the target graph becomes well connected when we view it from the perspective of these three graphs together, or called a hybrid social-affiliation graph in this paper. When directly sampling the target graph is difficult or inefficient, we can indirectly sample it efficiently with the assistances of the other two graphs. We design three sampling methods on such a hybrid social-affiliation network. Experiments conducted on both synthetic and real datasets demonstrate the effectiveness of our proposed methods.
Folding Alternant and Goppa Codes with Non-Trivial Automorphism Groups
Venue: arXiv cs.IT 2014
Year: 2014

The main practical limitation of the McEliece public-key encryption scheme is probably the size of its key. A famous trend to overcome this issue is to focus on subclasses of alternant/Goppa codes with a non trivial automorphism group. Such codes display then symmetries allowing compact parity-check or generator matrices. For instance, a key-reduction is obtained by taking quasi-cyclic (QC) or quasi-dyadic (QD) alternant/Goppa codes. We show that the use of such symmetric alternant/Goppa codes in cryptography introduces a fundamental weakness. It is indeed possible to reduce the key-recovery on the original symmetric public-code to the key-recovery on a (much) smaller code that has not anymore symmetries. This result is obtained thanks to a new operation on codes called folding that exploits the knowledge of the automorphism group. This operation consists in adding the coordinates of codewords which belong to the same orbit under the action of the automorphism group. The advantage is twofold: the reduction factor can be as large as the size of the orbits, and it preserves a fundamental property: folding the dual of an alternant (resp. Goppa) code provides the dual of an alternant (resp. Goppa) code. A key point is to show that all the existing constructions of alternant/Goppa codes with symmetries follow a common principal of taking codes whose support is globally invariant under the action of affine transformations (by building upon prior works of T. Berger and A. D{ü}r). This enables not only to present a unified view but also to generalize the construction of QC, QD and even quasi-monoidic (QM) Goppa codes. All in all, our results can be harnessed to boost up any key-recovery attack on McEliece systems based on symmetric alternant or Goppa codes, and in particular algebraic attacks.
Towards $k$-connectivity of the random graph induced by a pairwise key predistribution scheme with unreliable links
Venue: arXiv cs.DM 2014
Year: 2014

We study the secure and reliable connectivity of wireless sensor networks. Security is assumed to be ensured by the random pairwise key predistribution scheme of Chan, Perrig, and Song, and unreliable wireless links are represented by independent on/off channels. Modeling the network by an intersection of a random $K$-out graph and an Erdős-Rényi graph, we present scaling conditions (on the number of nodes, the scheme parameter $K$, and the probability of a wireless channel being on) such that the resulting graph contains no nodes with degree less than $k$ with high probability, when the number of nodes gets large. Results are given in the form of zero-one laws and are shown to improve the previous results by Yağan and Makowski on the absence of isolated nodes (i.e., absence of nodes with degree zero). Via simulations, the established zero-one laws are shown to hold also for the property of $k$-connectivity; i.e., the property that graph remains connected despite the deletion of any $k-1$ nodes or edges.
Efficient and Reliable Hybrid Cloud Architechture for Big Data
Venue: arXiv cs.DC 2014
Year: 2014

The objective of our paper is to propose a Cloud computing framework which is feasible and necessary for handling huge data. In our prototype system we considered national ID database structure of Bangladesh which is prepared by election commission of Bangladesh. Using this database we propose an interactive graphical user interface for Bangladeshi People Search (BDPS) that use a hybrid structure of cloud computing handled by apache Hadoop where database is implemented by HiveQL. The infrastructure divides into two parts: locally hosted cloud which is based on Eucalyptus and the remote cloud which is implemented on well-known Amazon Web Service (AWS). Some common problems of Bangladesh aspect which includes data traffic congestion, server time out and server down issue is also discussed.
Hidden Markov Model for Inferring Learner Task Using Mouse Movement
Venue: arXiv cs.HC 2014
Year: 2014

One of the issues of e-learning web based application is to understand how the learner interacts with an e-learning application to perform a given task. This study proposes a methodology to analyze learner mouse movement in order to infer the task performed. To do this, a Hidden Markov Model is used for modeling the interaction of the learner with an e-learning application. The obtained results show the ability of our model to analyze the interaction in order to recognize the task performed by the learner.
Effective Measurement Requirements for Network Security Management
Venue: arXiv cs.CR 2014
Year: 2014

Technical security metrics provide measurements in ensuring the effectiveness of technical security controls or technology devices/objects that are used in protecting the information systems. However, lack of understanding and method to develop the technical security metrics may lead to unachievable security control objectives and incompetence of the implementation. This paper proposes a model of technical security metric to measure the effectiveness of network security management. The measurement is based on the effectiveness of security performance for (1) network security controls such as firewall, Intrusion Detection Prevention System (IDPS), switch, wireless access point, wireless controllers and network architecture; and (2) network services such as Hypertext Transfer Protocol Secure (HTTPS) and virtual private network (VPN). We use the Goal-Question-Metric (GQM) paradigm [1] which links the measurement goals to measurement questions and produce the metrics that can easily be interpreted in compliance with the requirements. The outcome of this research method is the introduction of network security management metric as an attribute to the Technical Security Metric (TSM) model. Apparently, the proposed TSM model may provide guidance for organizations in complying with effective measurement requirements of ISO/IEC 27001 Information Security Management System (ISMS) standard. The proposed model will provide a comprehensive measurement and guidance to support the use of ISO/IEC 27004 ISMS Measurement template.
Fundamental Limits of Caching in Wireless D2D Networks
Venue: arXiv cs.IT 2014
Year: 2014

We consider a wireless Device-to-Device (D2D) network where communication is restricted to be single-hop. Users make arbitrary requests from a finite library of files and have pre-cached information on their devices, subject to a per-node storage capacity constraint. A similar problem has already been considered in an ``infrastructure'' setting, where all users receive a common multicast (coded) message from a single omniscient server (e.g., a base station having all the files in the library) through a shared bottleneck link. In this work, we consider a D2D ``infrastructure-less'' version of the problem. We propose a caching strategy based on deterministic assignment of subpackets of the library files, and a coded delivery strategy where the users send linearly coded messages to each other in order to collectively satisfy their demands. We also consider a random caching strategy, which is more suitable to a fully decentralized implementation. Under certain conditions, both approaches can achieve the information theoretic outer bound within a constant multiplicative factor. In our previous work, we showed that a caching D2D wireless network with one-hop communication, random caching, and uncoded delivery, achieves the same throughput scaling law of the infrastructure-based coded multicasting scheme, in the regime of large number of users and files in the library. This shows that the spatial reuse gain of the D2D network is order-equivalent to the coded multicasting gain of single base station transmission. It is therefore natural to ask whether these two gains are cumulative, i.e.,if a D2D network with both local communication (spatial reuse) and coded multicasting can provide an improved scaling law. Somewhat counterintuitively, we show that these gains do not cumulate (in terms of throughput scaling law).
A hybrid video quality metric for analyzing quality degradation due to frame drop
Venue: arXiv cs.MM 2014
Year: 2014

In last decade, ever growing internet technologies provided platform to share the multimedia data among different communities. As the ultimate users are human subjects who are concerned about quality of visual information, it is often desired to have good resumed perceptual quality of videos, thus arises the need of quality assessment. This paper presents a full reference hybrid video quality metric which is capable to analyse the video quality for spatially or temporally (frame drop) or spatio-temporally distorted video sequences. Simulated results show that the metric efficiently analyses the quality degradation and more closer to the developed human visual system
HATP: An HTN Planner for Robotics
Venue: arXiv cs.RO 2014
Year: 2014

Hierarchical Task Network (HTN) planning is a popular approach that cuts down on the classical planning search space by relying on a given hierarchical library of domain control knowledge. This provides an intuitive methodology for specifying high-level instructions on how robots and agents should perform tasks, while also giving the planner enough flexibility to choose the lower-level steps and their ordering. In this paper we present the HATP (Hierarchical Agent-based Task Planner) planning framework which extends the traditional HTN planning domain representation and semantics by making them more suitable for roboticists, and treating agents as "first class" entities in the language. The former is achieved by allowing "social rules" to be defined which specify what behaviour is acceptable/unacceptable by the agents/robots in the domain, and interleaving planning with geometric reasoning in order to validate online -with respect to a detailed geometric 3D world- the human/robot actions currently being pursued by HATP.
Circle detection on images using Learning Automata
Venue: arXiv cs.CV 2014
Year: 2014

Circle detection over digital images has received considerable attention from the computer vision community over the last few years devoting a tremendous amount of research seeking for an optimal detector. This article presents an algorithm for the automatic detection of circular shapes from complicated and noisy images with no consideration of conventional Hough transform principles. The proposed algorithm is based on Learning Automata (LA) which is a probabilistic optimization method that explores an unknown random environment by progressively improving the performance via a reinforcement signal (objective function). The approach uses the encoding of three non-collinear points as a candidate circle over the edge image. A reinforcement signal (matching function) indicates if such candidate circles are actually present in the edge map. Guided by the values of such reinforcement signal, the probability set of the encoded candidate circles is modified through the LA algorithm so that they can fit to the actual circles on the edge map. Experimental results over several complex synthetic and natural images have validated the efficiency of the proposed technique regarding accuracy, speed and robustness.
New quantum MDS codes derived from constacyclic codes
Venue: arXiv cs.IT 2014
Year: 2014

Quantum maximal-distance-separable (MDS) codes form an important class of quantum codes. It is very hard to construct quantum MDS codes with relatively large minimum distance. In this paper, based on classical constacyclic codes, we construct two classes of quantum MDS codes with parameters $$[[λ(q-1),λ(q-1)-2d+2,d]]_q$$ where $2\leq d\leq (q+1)/2+λ-1$, and $q+1=λr$ with $r$ even, and $$[[λ(q-1),λ(q-1)-2d+2,d]]_q$$ where $2\leq d\leq (q+1)/2+λ/2-1$, and $q+1=λr$ with $r$ odd. The quantum MDS codes exhibited here have parameters better than the ones available in the literature.
The LevelArray: A Fast, Practical Long-Lived Renaming Algorithm
Venue: arXiv cs.DC 2014
Year: 2014

The long-lived renaming problem appears in shared-memory systems where a set of threads need to register and deregister frequently from the computation, while concurrent operations scan the set of currently registered threads. Instances of this problem show up in concurrent implementations of transactional memory, flat combining, thread barriers, and memory reclamation schemes for lock-free data structures. In this paper, we analyze a randomized solution for long-lived renaming. The algorithmic technique we consider, called the LevelArray, has previously been used for hashing and one-shot (single-use) renaming. Our main contribu- tion is to prove that, in long-lived executions, where processes may register and deregister polynomially many times, the technique guarantees constant steps on average and O(log log n) steps with high probability for registering, unit cost for deregistering, and O(n) steps for collect queries, where n is an upper bound on the number of processes that may be active at any point in time. We also show that the algorithm has the surprising property that it is self-healing: under reasonable assumptions on the schedule, operations running while the data structure is in a degraded state implicitly help the data structure re-balance itself. This subtle mechanism obviates the need for expensive periodic rebuilding procedures. Our benchmarks validate this approach, showing that, for typical use parameters, the average number of steps a process takes to register is less than two and the worst-case number of steps is bounded by six, even in executions with billions of operations. We contrast this with other randomized implementations, whose worst-case behavior we show to be unreliable, and with deterministic implementations, whose cost is linear in n.