OpenRaiser/Intern-Atlas huggingface dataset:
A Comprehensive Study of an Online Packet Scheduling Algorithm
Venue: arXiv cs.DS 2011
Year: 2011

We study the \emph{bounded-delay model} for Qualify-of-Service buffer management. Time is discrete. There is a buffer. Unit-length jobs (also called \emph{packets}) arrive at the buffer over time. Each packet has an integer release time, an integer deadline, and a positive real value. A packet's characteristics are not known to an online algorithm until the packet actually arrives. In each time step, at most one packet can be sent out of the buffer. The objective is to maximize the total value of the packets sent by their respective deadlines in an online manner. An online algorithm's performance is usually measured in terms of \emph{competitive ratio}, when this online algorithm is compared with a clairvoyant algorithm achieving the best total value. In this paper, we study a simple and intuitive online algorithm. We analyze its performance in terms of competitive ratio for the general model and a few important variants.
On the reaction time of some synchronous systems
Venue: arXiv cs.SE 2011
Year: 2011

This paper presents an investigation of the notion of reaction time in some synchronous systems. A state-based description of such systems is given, and the reaction time of such systems under some classic composition primitives is studied. Reaction time is shown to be non-compositional in general. Possible solutions are proposed, and applications to verification are discussed. This framework is illustrated by some examples issued from studies on real-time embedded systems.
Formal Analysis of Quantum Systems using Process Calculus
Venue: arXiv cs.LO 2011
Year: 2011

Quantum communication and cryptographic protocols are well on the way to becoming an important practical technology. Although a large amount of successful research has been done on proving their correctness, most of this work does not make use of familiar techniques from formal methods, such as formal logics for specification, formal modelling languages, separation of levels of abstraction, and compositional analysis. We argue that these techniques will be necessary for the analysis of large-scale systems that combine quantum and classical components, and summarize the results of initial investigation using behavioural equivalence in process calculus. This paper is a summary of Simon Gay's invited talk at ICE'11.
Contracts in distributed systems
Venue: arXiv cs.PL 2011
Year: 2011

We present a parametric calculus for contract-based computing in distributed systems. By abstracting from the actual contract language, our calculus generalises both the contracts-as-processes and contracts-as-formulae paradigms. The calculus features primitives for advertising contracts, for reaching agreements, and for querying the fulfilment of contracts. Coordination among principals happens via multi-party sessions, which are created once agreements are reached. We present two instances of our calculus, by modelling contracts as (i) processes in a variant of CCS, and (ii) as formulae in a logic. With the help of a few examples, we discuss the primitives of our calculus, as well as some possible variants.
Enhanced User Authentication through Trajectory Clustering
Venue: arXiv cs.CR 2011
Year: 2011

Password authentication is the most commonly used technique to authenticate the user validity. However, due to its simplicity, it is vulnerable to pseudo attacks. It can be enhanced using various biometric techniques such as thumb impression, finger movement, eye movement etc. In this paper, we concentrate on the most economic technique, based on the user habitual rhythm pattern i.e. not what they type but how they type is the measure for authenticating the user. We consider the latency between key events as the trajectory, and trajectory clustering is used to obtain the hidden patterns of the user. Obtained pattern can be considered as a cluster of measurements that can be used to differentiate from other users. We evaluated the proposed technique on the data obtained from the 100 users.
Binary Particle Swarm Optimization based Biclustering of Web usage Data
Venue: arXiv cs.IR 2011
Year: 2011

Web mining is the nontrivial process to discover valid, novel, potentially useful knowledge from web data using the data mining techniques or methods. It may give information that is useful for improving the services offered by web portals and information access and retrieval tools. With the rapid development of biclustering, more researchers have applied the biclustering technique to different fields in recent years. When biclustering approach is applied to the web usage data it automatically captures the hidden browsing patterns from it in the form of biclusters. In this work, swarm intelligent technique is combined with biclustering approach to propose an algorithm called Binary Particle Swarm Optimization (BPSO) based Biclustering for Web Usage Data. The main objective of this algorithm is to retrieve the global optimal bicluster from the web usage data. These biclusters contain relationships between web users and web pages which are useful for the E-Commerce applications like web advertising and marketing. Experiments are conducted on real dataset to prove the efficiency of the proposed algorithms.
Towards Optimal Sorting of 16 Elements
Venue: arXiv cs.DS 2011
Year: 2011

One of the fundamental problem in the theory of sorting is to find the pessimistic number of comparisons sufficient to sort a given number of elements. Currently 16 is the lowest number of elements for which we do not know the exact value. We know that 46 comparisons suffices and that 44 do not. There is an open question if 45 comparisons are sufficient. We present an attempt to resolve that problem by performing an exhaustive computer search. We also present an algorithm for counting linear extensions which substantially speeds up computations.
Noisy-Interference Sum-Rate Capacity for Vector Gaussian Interference Channels
Venue: arXiv cs.IT 2011
Year: 2011

New sufficient conditions for a vector Gaussian interference channel to achieve the sum-rate capacity by treating interference as noise are derived, which generalize the existing results. More concise conditions for multiple-input-single-output, and single-input-multiple-output scenarios are obtained.
UWB Array Design Using Variable Zo Technology and Central Force Optimization
Venue: arXiv cs.OH 2011
Year: 2011

This note applies Variable Zo technology to the design of an Ultra Wideband (UWB) Yagi-Uda array optimized using Central Force Optimization. Variable Zo is a novel and proprietary approach to antenna design and optimization that treats the feed system characteristic impedance, Zo, as a design variable instead of a fixed design parameter as is traditionally done. Variable Zo is applicable to any antenna design or optimization methodology, and using it will generally produce better antenna designs across any user-specified set of performance objectives.
Optimal Base Station Placement: A Stochastic Method Using Interference Gradient In Downlink Case
Venue: arXiv cs.NI 2011
Year: 2011

In this paper, we study the optimal placement and optimal number of base stations added to an existing wireless data network through the interference gradient method. This proposed method considers a sub-region of the existing wireless data network, hereafter called region of interest. In this region, the provider wants to increase the network coverage and the users throughput. In this aim, the provider needs to determine the optimal number of base stations to be added and their optimal placement. The proposed approach is based on the Delaunay triangulation of the region of interest and the gradient descent method in each triangle to compute the minimum interference locations. We quantify the increase of coverage and throughput.
Phagocytes: A Holistic Defense and Protection Against Active P2P Worms
Venue: arXiv cs.NI 2011
Year: 2011

Active Peer-to-Peer (P2P) worms present serious threats to the global Internet by exploiting popular P2P applications to perform rapid topological self-propagation. Active P2P worms pose more deadly threats than normal scanning worms because they do not exhibit easily detectable anomalies, thus many existing defenses are no longer effective. We propose an immunity system with Phagocytes --- a small subset of elected P2P hosts that are immune with high probability and specialized in finding and "eating" worms in the P2P overlay. The Phagocytes will monitor their managed P2P hosts' connection patterns and traffic volume in an attempt to detect active P2P worm attacks. Once detected, local isolation, alert propagation and software patching will take place for containment. The Phagocytes further provide the access control and filtering mechanisms for communication establishment between the internal P2P overlay and the external hosts. We design a novel adaptive and interaction-based computational puzzle scheme at the Phagocytes to restrain external worms attacking the P2P overlay, without influencing legitimate hosts' experiences significantly. We implement a prototype system, and evaluate its performance based on realistic massive-scale P2P network traces. The evaluation results illustrate that our Phagocytes are capable of achieving a total defense against active P2P worms.
Fast k-means algorithm clustering
Venue: arXiv cs.DS 2011
Year: 2011

k-means has recently been recognized as one of the best algorithms for clustering unsupervised data. Since k-means depends mainly on distance calculation between all data points and the centers, the time cost will be high when the size of the dataset is large (for example more than 500millions of points). We propose a two stage algorithm to reduce the time cost of distance calculation for huge datasets. The first stage is a fast distance calculation using only a small portion of the data to produce the best possible location of the centers. The second stage is a slow distance calculation in which the initial centers used are taken from the first stage. The fast and slow stages represent the speed of the movement of the centers. In the slow stage, the whole dataset can be used to get the exact location of the centers. The time cost of the distance calculation for the fast stage is very low due to the small size of the training data chosen. The time cost of the distance calculation for the slow stage is also minimized due to small number of iterations. Different initial locations of the clusters have been used during the test of the proposed algorithms. For large datasets, experiments show that the 2-stage clustering method achieves better speed-up (1-9 times).
A Driven Backup Routing Table to Find Alternative Dijoint Path in Ad Hoc Wireless
Venue: arXiv cs.NI 2011
Year: 2011

The performances of the routing protocols are important since they compute the primary path between source and destination. In addition, routing protocols need to detect failure within a short period of time when nodes move to start updating the routing table in order to find a new primary path to the destination. Meantime, loss of packets and end-to- end delays will increase thereby reducing throughput and degrading the performance of the network. This paper proposes a new algorithm, DBRT (Driven Backup Routing Table), to improve the existing proactive protocols such as DSDV (Destination Sequenced Distance Vector) protocol by creating a backup routing table to provide multiple alternative routes. The DBRT algorithm identifies adjacent nodes for each node in the same range and then selects one of these as a backup next hop according to the available path to the destination. The results show that loss of data packets, throughput and end-to-end delay times between source and destination are improved. The results show that the new protocol does not degrade the network's performance despite sending extra messages to construct and update the new backup routing table. Simulations (using an NS2 simulator) are undertaken to demonstrate the difference between using a DSDV protocol with or without the proposed schema.
System Support for Managing Invalid Bindings
Venue: arXiv cs.OH 2011
Year: 2011

Context-aware adaptation is a central aspect of pervasive computing applications, enabling them to adapt and perform tasks based on contextual information. One of the aspects of context-aware adaptation is reconfiguration in which bindings are created between application component and remote services in order to realize new behaviour in response to contextual information. Various research efforts provide reconfiguration support and allow the development of adaptive context-aware applications from high-level specifications, but don't consider failure conditions that might arise during execution of such applications, making bindings between application and remote services invalid. To this end, we propose and implement our design approach to reconfiguration to manage invalid bindings. The development and modification of adaptive context-aware applications is a complex task, and an issue of an invalidity of bindings further complicates development efforts. To reduce the development efforts, our approach provides an application-transparent solution where the issue of the invalidity of bindings is handled by our system, Policy-Based Contextual Reconfiguration and Adaptation (PCRA), not by an application developer. In this paper, we present and describe our approach to managing invalid bindings and compare it with other approaches to this problem. We also provide performance evaluation of our approach.
'Just Enough' Ontology Engineering
Venue: arXiv cs.AI 2011
Year: 2011

This paper introduces 'just enough' principles and 'systems engineering' approach to the practice of ontology development to provide a minimal yet complete, lightweight, agile and integrated development process, supportive of stakeholder management and implementation independence.
A frequency approach to topological identification and graphical modeling
Venue: arXiv cs.SY 2011
Year: 2011

This works explores and illustrates recent results developed by the author in field of dynamical network analysis. The considered approach is blind, i.e., no a priori assumptions on the interconnected systems are available. Moreover, the perspective is that of a simple "observer" who can perform no kind of test on the network in order to study the related response, that is no action or forcing input aimed to reveal particular responses of the system can be performed. In such a scenario a frequency based method of investigation is developed to obtain useful insights on the network. The information thus derived can be fruitfully exploited to build acyclic graphical models, which can be seen as extension of Bayesian Networks or Markov Chains. Moreover, it is shown that the topology of polytree linear networks can be exactly identified via the same mathematical tools. In this respect, it is worth observing that important real systems, such as all the transportation networks, fit this class.
Optimal Rate for Irregular LDPC Codes in Binary Erasure Channel
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we introduce a new practical and general method for solving the main problem of designing the capacity approaching, optimal rate, irregular low-density parity-check (LDPC) code ensemble over binary erasure channel (BEC). Compared to some new researches, which are based on application of asymptotic analysis tools out of optimization process, the proposed method is much simpler, faster, accurate and practical. Because of not using any relaxation or any approximate solution like previous works, the found answer with this method is optimal. We can construct optimal variable node degree distribution for any given binary erasure rate, ε, and any check node degree distribution. The presented method is implemented and works well in practice. The time complexity of this method is of polynomial order. As a result, we obtain some degree distribution which their rates are close to the capacity.
A new embedding quality assessment method for manifold learning
Venue: arXiv cs.CV 2011
Year: 2011

Manifold learning is a hot research topic in the field of computer science. A crucial issue with current manifold learning methods is that they lack a natural quantitative measure to assess the quality of learned embeddings, which greatly limits their applications to real-world problems. In this paper, a new embedding quality assessment method for manifold learning, named as Normalization Independent Embedding Quality Assessment (NIEQA), is proposed. Compared with current assessment methods which are limited to isometric embeddings, the NIEQA method has a much larger application range due to two features. First, it is based on a new measure which can effectively evaluate how well local neighborhood geometry is preserved under normalization, hence it can be applied to both isometric and normalized embeddings. Second, it can provide both local and global evaluations to output an overall assessment. Therefore, NIEQA can serve as a natural tool in model selection and evaluation tasks for manifold learning. Experimental results on benchmark data sets validate the effectiveness of the proposed method.
Uniform Labeled Transition Systems for Nondeterministic, Probabilistic, and Stochastic Process Calculi
Venue: arXiv cs.DC 2011
Year: 2011

Labeled transition systems are typically used to represent the behavior of nondeterministic processes, with labeled transitions defining a one-step state to-state reachability relation. This model has been recently made more general by modifying the transition relation in such a way that it associates with any source state and transition label a reachability distribution, i.e., a function mapping each possible target state to a value of some domain that expresses the degree of one-step reachability of that target state. In this extended abstract, we show how the resulting model, called ULTraS from Uniform Labeled Transition System, can be naturally used to give semantics to a fully nondeterministic, a fully probabilistic, and a fully stochastic variant of a CSP-like process language.
A Distributed Newton Approach for Joint Multi-Hop Routing and Flow Control: Theory and Algorithm
Venue: arXiv cs.NI 2011
Year: 2011

The fast growing scale and heterogeneity of current communication networks necessitate the design of distributed cross-layer optimization algorithms. So far, the standard approach of distributed cross-layer design is based on dual decomposition and the subgradient algorithm, which is a first-order method that has a slow convergence rate. In this paper, we focus on solving a joint multi-path routing and flow control (MRFC) problem by designing a new distributed Newton's method, which is a second-order method and enjoys a quadratic rate of convergence. The major challenges in developing a distributed Newton's method lie in decentralizing the computation of the Hessian matrix and its inverse for both the primal Newton direction and dual variable updates. By appropriately reformulating, rearranging, and exploiting the special problem structures, we show that it is possible to decompose such computations into source nodes and links in the network, thus eliminating the need for global information. Furthermore, we derive closed-form expressions for both the primal Newton direction and dual variable updates, thus significantly reducing the computational complexity. The most attractive feature of our proposed distributed Newton's method is that it requires almost the same scale of information exchange as in first-order methods, while achieving a quadratic rate of convergence as in centralized Newton methods. We provide extensive numerical results to demonstrate the efficacy of our proposed algorithm. Our work contributes to the advanced paradigm shift in cross-layer network design that is evolving from first-order to second-order methods.
Efficient computation of the branching structure of an algebraic curve
Venue: arXiv cs.CG 2011
Year: 2011

An efficient algorithm for computing the branching structure of a compact Riemann surface defined via an algebraic curve is presented. Generators of the fundamental group of the base of the ramified covering punctured at the discriminant points of the curve are constructed via a minimal spanning tree of the discriminant points. This leads to paths of minimal length between the points, which is important for a later stage where these paths are used as integration contours to compute periods of the surface. The branching structure of the surface is obtained by analytically continuing the roots of the equation defining the algebraic curve along the constructed generators of the fundamental group.
Witness Rectangle Graphs
Venue: arXiv cs.CG 2011
Year: 2011

In a witness rectangle graph (WRG) on vertex point set P with respect to witness points set W in the plane, two points x, y in P are adjacent whenever the open isothetic rectangle with x and y as opposite corners contains at least one point in W. WRGs are representative of a a larger family of witness proximity graphs introduced in two previous papers. We study graph-theoretic properties of WRGs. We prove that any WRG has at most two non-trivial connected components. We bound the diameter of the non-trivial connected components of a WRG in both the one-component and two-component cases. In the latter case, we prove that a graph is representable as a WRG if and only if each component is a connected co-interval graph, thereby providing a complete characterization of WRGs of this type. We also completely characterize trees drawable as WRGs. In addition, we prove that a WRG with no isolated vertices has domination number at most four. Moreover, we show that any combinatorial graph can be drawn as a WRG using a combination of positive and negative witnesses. Finally we conclude with some related results on the number of points required to stab all the rectangles defined by a set of n point.
Can User-Level Probing Detect and Diagnose Common Home-WLAN Pathologies?
Venue: arXiv cs.NI 2011
Year: 2011

Common WLAN pathologies include low signal-to-noise ratio, congestion, hidden terminals or interference from non-802.11 devices and phenomena. Prior work has focused on the detection and diagnosis of such problems using layer-2 information from 802.11 devices and special-purpose access points and monitors, which may not be generally available. Here, we investigate a userlevel approach: is it possible to detect and diagnose 802.11 pathologies with strictly user-level active probing, without any cooperation from, and without any visibility in, layer-2 devices? In this paper, we present preliminary but promising results indicating that such diagnostics are feasible.
Privacy Preserving Data Aggregation in Wireless Sensor Networks
Venue: arXiv cs.CR 2011
Year: 2011

Privacy preservation is an important issue in today's context of extreme penetration of internet and mobile technologies. It is more important in the case of Wireless Sensor Networks (WSNs) where collected data often requires in-network processing and collaborative computing. Researches in this area are mostly concentrated in applying data mining techniques to preserve the privacy content of the data. These techniques are mostly computationally expensive and not suitable for resource limited WSN nodes. In this paper, a scheme is developed to provide privacy preservation in a much simpler way with the help of a secure key management scheme and randomized data perturbation technique. We consider a scenario in which two or more parties owning confidential data need to share only for aggregation purpose to a third party, without revealing the content of the data. Through simulation results the efficacy of our scheme and compare the result with one of the established scheme [1].