OpenRaiser/Intern-Atlas huggingface dataset:
A Methodology for assessing Agile Software Development Approaches
Venue: arXiv cs.SE 2011
Year: 2011

Agile methods provide an organization or a team the flexibility to adopt a selected subset of principles and practices based on their culture, their values, and the types of systems that they develop. More specifically, every organization or team implements a customized agile method, tailored to better accommodate its needs. However, the extent to which a customized method supports the organizational objectives, or rather the 'goodness' of that method is questionable. Existing agile assessment approaches focus on a comparative analysis, or are limited in scope and application. In this research, we propose a structured, systematic and comprehensive approach to assess the 'goodness' of agile methods. We examine an agile method based on (1) its adequacy, (2) the capability of the organization to support the adopted principles and practices specified by the method, and (3) the method's effectiveness. We propose the Objectives, Principles and Practices (OPP) Framework to guide our assessment. The Framework identifies (1) objectives of the agile philosophy, (2) principles that support the objectives, (3) practices that are reflective of the principles, (4) the linkages between the objectives, principles and practices, and (5) indicators for each practice to assess the effectiveness of the practice and the extent to which the organization supports its implementation. In this document, we discuss our solution approach, preliminary results, and future work.
Symmetric Connectivity with Directional Antennas
Venue: arXiv cs.CG 2011
Year: 2011

Let P be a set of points in the plane, representing directional antennas of angle a and range r. The coverage area of the antenna at point p is a circular sector of angle a and radius r, whose orientation is adjustable. For a given orientation assignment, the induced symmetric communication graph (SCG) of P is the undirected graph that contains the edge (u,v) iff v lies in u's sector and vice versa. In this paper we ask what is the smallest angle a for which there exists an integer n=n(a), such that for any set P of n antennas of angle a and unbounded range, one can orient the antennas so that the induced SCG is connected, and the union of the corresponding wedges is the entire plane. We show that the answer to this problem is a=π/2, for which n=4. Moreover, we prove that if Q_1 and Q_2 are quadruplets of antennas of angle π/2 and unbounded range, separated by a line, to which one applies the above construction, independently, then the induced SCG of Q_1 \cup Q_2 is connected. This latter result enables us to apply the construction locally, and to solve the following two further problems. In the first problem, we are given a connected unit disk graph (UDG), corresponding to a set P of omni-directional antennas of range 1, and the goal is to replace these antennas by directional antennas of angle π/2 and range r=O(1) and to orient them, such that the induced SCG is connected, and, moreover, is an O(1)-spanner of the UDG, w.r.t. hop distance. In our solution r = 14\sqrt{2} and the spanning ratio is 8. In the second problem, we are given a set P of directional antennas of angle π/2 and adjustable range. The goal is to assign to each antenna p, an orientation and a range r_p, such that the resulting SCG is connected, and \sum_{p \in P} r_p^βis minimized, where β\ge 1 is a constant. We present an O(1)-approximation algorithm.
A Novel Trajectory Clustering technique for selecting cluster heads in Wireless Sensor Networks
Venue: arXiv cs.NI 2011
Year: 2011

Wireless sensor networks (WSNs) suffers from the hot spot problem where the sensor nodes closest to the base station are need to relay more packet than the nodes farther away from the base station. Thus, lifetime of sensory network depends on these closest nodes. Clustering methods are used to extend the lifetime of a wireless sensor network. However, current clustering algorithms usually utilize two techniques; selecting cluster heads with more residual energy, and rotating cluster heads periodically to distribute the energy consumption among nodes in each cluster and lengthen the network lifetime. Most of the algorithms use random selection for selecting the cluster heads. Here, we propose a novel trajectory clustering technique for selecting the cluster heads in WSNs. Our algorithm selects the cluster heads based on traffic and rotates periodically. It provides the first trajectory based clustering technique for selecting the cluster heads and to extenuate the hot spot problem by prolonging the network lifetime.
13/9-approximation for Graphic TSP
Venue: arXiv cs.DS 2011
Year: 2011

The Travelling Salesman Problem is one the most fundamental and most studied problems in approximation algorithms. For more than 30 years, the best algorithm known for general metrics has been Christofides's algorithm with approximation factor of 3/2, even though the so-called Held-Karp LP relaxation of the problem is conjectured to have the integrality gap of only 4/3. Very recently, significant progress has been made for the important special case of graphic metrics, first by Oveis Gharan et al., and then by Momke and Svensson. In this paper, we provide an improved analysis for the approach introduced by Momke and Svensson yielding a bound of 13/9 on the approximation factor, as well as a bound of 19/12+epsilon for any epsilon>0 for a more general Travelling Salesman Path Problem in graphic metrics.
An index for regular expression queries: Design and implementation
Venue: arXiv cs.DB 2011
Year: 2011

The like regular expression predicate has been part of the SQL standard since at least 1989. However, despite its popularity and wide usage, database vendors provide only limited indexing support for regular expression queries which almost always require a full table scan. In this paper we propose a rigorous and robust approach for providing indexing support for regular expression queries. Our approach consists of formulating the indexing problem as a combinatorial optimization problem. We begin with a database, abstracted as a collection of strings. From this data set we generate a query workload. The input to the optimization problem is the database and the workload. The output is a set of multigrams (substrings) which can be used as keys to records which satisfy the query workload. The multigrams can then be integrated with the data structure (like B+ trees) to provide indexing support for the queries. We provide a deterministic and a randomized approximation algorithm (with provable guarantees) to solve the optimization problem. Extensive experiments on synthetic data sets demonstrate that our approach is accurate and efficient. We also present a case study on PROSITE patterns - which are complex regular expression signatures for classes of proteins. Again, we are able to demonstrate the utility of our indexing approach in terms of accuracy and efficiency. Thus, perhaps for the first time, there is a robust and practical indexing mechanism for an important class of database queries.
Secure and Robust IPV6 Autoconfiguration Protocol For Mobile Adhoc Networks Under Strong Adversarial Model
Venue: arXiv cs.NI 2011
Year: 2011

Automatic IP address assignment in Mobile Ad hoc Networks (MANETs) enables nodes to obtain routable addresses without any infrastructure. Different protocols have been developed throughout the last years to achieve this service. However, research primarily focused on correctness, efficiency and scalability; much less attention has been given to the security issues. The lack of security in the design of such protocols opens the possibility of many real threats leading to serious attacks in potentially hostile environments. Recently, few schemes have been proposed to solve this problem, but none of them has brought satisfactory solutions. Auto-configuration security issues are still an open problem. In this paper, a robust and secure stateful IP address allocation protocol for standalone MANETs is specified and evaluated within NS2. Our solution is based on mutual authentication, and a fully distributed Autoconfiguration and CA model, in conjunction with threshold cryptography. By deploying a new concept of joint IP address and public key certificate, we show that, instead of earlier approaches, our solution solves the problem of all possible attacks associated with dynamic IP address assignment in MANETs. The resulting protocol incurs low latency and control overhead
Architecture Of A Identity Based Firewall System
Venue: arXiv cs.CR 2011
Year: 2011

Classic firewall systems are built to filter traffic based on IP addresses, source and destination ports and protocol types. The modern networks have grown to a level where the possibility for users' mobility is a must. In such networks, modern firewalls may introduce such complexity where administration can become very frustrating since it needs the intervention of a firewall administrator. The solution for this problem is an identity based firewall system. In this paper we will present a new design of a firewall system that uses the user's identity to filter the traffic. In the design phase we will define key points which have to be satisfied as a crucial milestone for the functioning of the whole Identity based firewall system.
Savings in location management costs leveraging user statistics
Venue: arXiv cs.NI 2011
Year: 2011

The growth in the number of users in mobile communications networks and the rise in the traffic generated by each user, are responsible for the increasing importance of Mobility Management. Within Mobility Management, the main objective of Location Management is to enable the roaming of the user in the coverage area. In this paper, we analyze the savings in Location Management costs obtained leveraging the users' statistics, in comparison with the classical strategy. In particular, we introduce two novel algorithms to obtain the Beta parameters (useful terms in the calculation of location update costs for different Location Management strategies), utilizing a geographical study of relative positions of the cells within the location areas. Eventually, we discuss the influence of the different network parameters on the total Location Management costs savings for both the radio interface and the fixed network part, providing useful guidelines for the optimum design of the networks.
On the Secrecy Degrees of Freedom of Multi-Antenna Wiretap Channels with Delayed CSIT
Venue: arXiv cs.IT 2011
Year: 2011

The secrecy degrees of freedom (SDoF) of the Gaussian multiple-input and single-output (MISO) wiretap channel is studied under the assumption that delayed channel state information (CSI) is available at the transmitter and each receiver knows its own instantaneous channel. We first show that a strictly positive SDoF can be guaranteed whenever the transmitter has delayed CSI (either on the legitimate channel or/and the eavesdropper channel). In particular, in the case with delayed CSI on both channels, it is shown that the optimal SDoF is 2/3. We then generalize the result to the two-user Gaussian MISO broadcast channel with confidential messages and characterize the SDoF region when the transmitter has delayed CSI of both receivers. Interestingly, the artificial noise schemes exploiting several time instances are shown to provide the optimal SDoF region by masking the confidential message to the unintended receiver while aligning the interference at each receiver.
Load Balancing for MapReduce-based Entity Resolution
Venue: arXiv cs.DC 2011
Year: 2011

The effectiveness and scalability of MapReduce-based implementations of complex data-intensive tasks depend on an even redistribution of data between map and reduce tasks. In the presence of skewed data, sophisticated redistribution approaches thus become necessary to achieve load balancing among all reduce tasks to be executed in parallel. For the complex problem of entity resolution, we propose and evaluate two approaches for such skew handling and load balancing. The approaches support blocking techniques to reduce the search space of entity resolution, utilize a preprocessing MapReduce job to analyze the data distribution, and distribute the entities of large blocks among multiple reduce tasks. The evaluation on a real cloud infrastructure shows the value and effectiveness of the proposed load balancing approaches.
Sub-modularity and Antenna Selection in MIMO systems
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we show that the optimal receive antenna subset selection problem for maximizing the mutual information in a point-to-point MIMO system is sub-modular. Consequently, a greedy step-wise optimization approach, where at each step an antenna that maximizes the incremental gain is added to the existing antenna subset, is guaranteed to be within a (1 - 1/e) fraction of the global optimal value. For a single antenna equipped source and destination with multiple relays, we show that the relay antenna selection problem to maximize the mutual information is modular, when complete channel state information is available at the relays. As a result a greedy step-wise optimization approach leads to an optimal solution for the relay antenna selection problem with linear complexity in comparison to the brute force search that incurs exponential complexity.
Towards reduction of Paradigm coordination models
Venue: arXiv cs.LO 2011
Year: 2011

The coordination modelling language Paradigm addresses collaboration between components in terms of dynamic constraints. Within a Paradigm model, component dynamics are consistently specified at a detailed and a global level of abstraction. To enable automated verification of Paradigm models, a translation of Paradigm into process algebra has been defined in previous work. In this paper we investigate, guided by a client-server example, reduction of Paradigm models based on a notion of global inertness. Representation of Paradigm models as process algebraic specifications helps to establish a property-preserving equivalence relation between the original and the reduced Paradigm model. Experiments indicate that in this way larger Paradigm models can be analyzed.
An Achievable Rate Region for Cognitive Radio Channel With Common Message
Venue: arXiv cs.IT 2011
Year: 2011

The cognitive radio channel with common message (CRCC) is considered. In this channel, similar to the cognitive radio channel (CRC), we have a cognitive user which has full non-causal knowledge of the primary message, and like the interference channel with common message (ICC), the information sources at the two transmitters are statistically dependent and the senders need to transmit not only the private message but also certain common message to their corresponding receivers. By using a specific combination of superposition coding, binning scheme and simultaneous decoding, we propose a unified achievable rate region for the CRCC which subsumes the several existing results for the CRC, ICC, interference channel without common message (IC), strong interference channel and compound multiple access channel with common information (SICC and CMACC).
A Comparative Study of Various Routing Protocols in VANET
Venue: arXiv cs.NI 2011
Year: 2011

Vehicular Ad Hoc Networks (VANET) is a subclass of Mobile ad hoc networks which provides a distinguished approach for Intelligent Transport System (ITS). The survey of routing protocols in VANET is important and necessary for smart ITS. This paper discusses the advantages / disadvantages and the applications of various routing protocols for vehicular ad hoc networks. It explores the motivation behind the designed, and traces the evolution of these routing protocols. F inally the paper concludes by a tabular comparison of the various routing protocols for VANET.
Analysis and Implementation of Distinct Steganographic Methods
Venue: arXiv cs.CR 2011
Year: 2011

In this paper, different steganographic methods have been analyzed and implementations of those techniques have been performed. Those methods include hiding in text, hiding in audio file, hiding in file system, and hiding in image files.
Graph and Election Problems Parameterized by Feedback Set Numbers
Venue: arXiv cs.CC 2011
Year: 2011

This work investigates the parameterized complexity of three related graph modification problems. Given a directed graph, a distinguished vertex, and a positive integer k, Minimum Indegree Deletion asks for a vertex subset of size at most k whose removal makes the distinguished vertex the only vertex with minimum indegree. Minimum Degree Deletion is analogously defined, but deals with undirected graphs. Bounded Degree Deletion is also defined on undirected graphs, but has a positive integer d instead of a distinguished vertex as part of the input. It asks for a vertex subset of size at most k whose removal results in a graph in which every vertex has degree at most d. The first two problems have applications in computational social choice whereas the third problem is used in computational biology. We investigate the parameterized complexity with respect to the parameters "treewidth", "size of a feedback vertex set" and "size of a feedback edge set" respectively "size of a feedback arc set". Each of these parameters measures the "degree of acyclicity" in different ways.
Competitive Privacy in the Smart Grid: An Information-theoretic Approach
Venue: arXiv cs.IT 2011
Year: 2011

Advances in sensing and communication capabilities as well as power industry deregulation are driving the need for distributed state estimation in the smart grid at the level of the regional transmission organizations (RTOs). This leads to a new competitive privacy problem amongst the RTOs since there is a tension between sharing data to ensure network reliability (utility/benefit to all RTOs) and withholding data for profitability and privacy reasons. The resulting tradeoff between utility, quantified via fidelity of its state estimate at each RTO, and privacy, quantified via the leakage of the state of one RTO at other RTOs, is captured precisely using a lossy source coding problem formulation for a two RTO network. For a two-RTO model, it is shown that the set of all feasible utility-privacy pairs can be achieved via a single round of communication when each RTO communicates taking into account the correlation between the measured data at both RTOs. The lossy source coding problem and solution developed here is also of independent interest.
Automated Functional Testing based on the Navigation of Web Applications
Venue: arXiv cs.SE 2011
Year: 2011

Web applications are becoming more and more complex. Testing such applications is an intricate hard and time-consuming activity. Therefore, testing is often poorly performed or skipped by practitioners. Test automation can help to avoid this situation. Hence, this paper presents a novel approach to perform automated software testing for web applications based on its navigation. On the one hand, web navigation is the process of traversing a web application using a browser. On the other hand, functional requirements are actions that an application must do. Therefore, the evaluation of the correct navigation of web applications results in the assessment of the specified functional requirements. The proposed method to perform the automation is done in four levels: test case generation, test data derivation, test case execution, and test case reporting. This method is driven by three kinds of inputs: i) UML models; ii) Selenium scripts; iii) XML files. We have implemented our approach in an open-source testing framework named Automatic Testing Platform. The validation of this work has been carried out by means of a case study, in which the target is a real invoice management system developed using a model-driven approach.
Debugging of Web Applications with Web-TLR
Venue: arXiv cs.LO 2011
Year: 2011

Web-TLR is a Web verification engine that is based on the well-established Rewriting Logic--Maude/LTLR tandem for Web system specification and model-checking. In Web-TLR, Web applications are expressed as rewrite theories that can be formally verified by using the Maude built-in LTLR model-checker. Whenever a property is refuted, a counterexample trace is delivered that reveals an undesired, erroneous navigation sequence. Unfortunately, the analysis (or even the simple inspection) of such counterexamples may be unfeasible because of the size and complexity of the traces under examination. In this paper, we endow Web-TLR with a new Web debugging facility that supports the efficient manipulation of counterexample traces. This facility is based on a backward trace-slicing technique for rewriting logic theories that allows the pieces of information that we are interested to be traced back through inverse rewrite sequences. The slicing process drastically simplifies the computation trace by dropping useless data that do not influence the final result. By using this facility, the Web engineer can focus on the relevant fragments of the failing application, which greatly reduces the manual debugging effort and also decreases the number of iterative verifications.
A type checking algorithm for qualified session types
Venue: arXiv cs.PL 2011
Year: 2011

We present a type checking algorithm for establishing a session-based discipline in the pi calculus of Milner, Parrow and Walker. Our session types are qualified as linear or unrestricted. Linearly typed communication channels are guaranteed to occur in exactly one thread, possibly multiple times; afterwards they evolve as unrestricted channels. Session protocols are described by a type constructor that denotes the two ends of one and the same communication channel. We ensure the soundness of the algorithm by showing that processes consuming all linear resources are accepted by a type system preserving typings during the computation and that type checking is consistent w.r.t. structural congruence.
Grothendieck-type inequalities in combinatorial optimization
Venue: arXiv cs.DS 2011
Year: 2011

We survey connections of the Grothendieck inequality and its variants to combinatorial optimization and computational complexity.
Efficient Multicore Collaborative Filtering
Venue: arXiv cs.LG 2011
Year: 2011

This paper describes the solution method taken by LeBuSiShu team for track1 in ACM KDD CUP 2011 contest (resulting in the 5th place). We identified two main challenges: the unique item taxonomy characteristics as well as the large data set size.To handle the item taxonomy, we present a novel method called Matrix Factorization Item Taxonomy Regularization (MFITR). MFITR obtained the 2nd best prediction result out of more then ten implemented algorithms. For rapidly computing multiple solutions of various algorithms, we have implemented an open source parallel collaborative filtering library on top of the GraphLab machine learning framework. We report some preliminary performance results obtained using the BlackLight supercomputer.
Improving bit-vector representation of points-to sets using class hierarchy
Venue: arXiv cs.PL 2011
Year: 2011

Points-to analysis is the problem of approximating run-time values of pointers statically or at compile-time. Points-to sets are used to store the approximated values of pointers during points-to analysis. Memory usage and running time limit the ability of points-to analysis to analyze large programs. To our knowledge, works which have implemented a bit-vector representation of points-to sets so far, allocates bits for each pointer without considering pointer's type. By considering the type, we are able to allocate bits only for a subset of all abstract objects which are of compatible type with the pointer's type and as a consequence improve the memory usage and running time. To achieve this goal, we number abstract objects in a way that all the abstract objects of a type and all of its sub-types be consecutive in order. Our most efficient implementation uses about 2.5 times less memory than hybrid points-to set (default points-to set in Spark) and also improves the analysis time for sufficiently large programs.