OpenRaiser/Intern-Atlas huggingface dataset:
Performance Analysis of DiffServ based Quality of Service in a Multimedia Wired Network and VPN effect using OPNET
Venue: arXiv cs.NI 2012
Year: 2012

Quality of Service (QoS) techniques are applied in IP networks to utilize available network resources in the most efficient manner to minimize delays and delay variations (jitters) in network traffic having multiple type of services. Multimedia services may include voice, video and database. Researchers have done considerable work on queuing disciplines to analyze and improve QoS performance in wired and wireless IP networks. This paper highlights QoS analysis in a wired IP network with more realistic enterprise modeling and presents simulation results of a few statistics not presented and discussed before. Four different applications are used i.e. FTP, Database, Voice over IP (VoIP) and Video Conferencing (VC). Two major queuing disciplines are evaluated i.e. 'Priority Queuing' and 'Weighted Fair Queuing' for packet identification under Differentiated Services Code Point (DSCP). The simulation results show that WFQ has an edge over PQ in terms of queuing delays and jitters experienced by low priority services. For high priority traffic, dependency of 'Traffic Drop', 'Buffer Usage' and 'Packet Delay Variation' on selected buffer sizes is simulated and discussed to evaluate QoS deeper. In the end, it is also analyzed how network's database service with applied Quality of Service may be affected in terms of throughput (average rate of data received) for internal network users when the server is also accessed by external user(s) through Virtual Private Network (VPN).
Enhanced MAC Parameters to Support Hybrid Dynamic Prioritization in MANETs
Venue: arXiv cs.NI 2012
Year: 2012

Quality of Service (QoS) for MANETs becomes a necessity because of its applications in decisive situations such as battle fields, flood and earth quake. Users belonging to diverse hierarchical category demanding various levels of QoS use MANETs. Sometimes, even a low category user may need to send an urgent message in time critical applications. Hence providing prioritization based on user category and urgency of the message the user is sending becomes necessary. In this paper we propose Enhanced MAC parameters to support Hybrid Dynamic priority in MANETs(H-MAC). It combines both prioritization based on user categorization and dynamic exigency. Order Statistics is used to implement dynamic priority. We propose dynamic TXOP, Proportional AIFS and Proportional dynamic Backoff timers based on weights and collision, to avoid packet dropping and starvation of lower priorities. The model is simulated in ns2. We compare our results with IEEE 802.11e and show that, 16% more throughput is achieved by H-MAC during extensive collision. We also observe that starvation and packet drops are reduced with proportionate bandwidth sharing compared to the existing model.
A Survey on Web Service Discovery Approaches
Venue: arXiv cs.IR 2012
Year: 2012

Web services are playing an important role in e-business and e-commerce applications. As web service applications are interoperable and can work on any platform, large scale distributed systems can be developed easily using web services. Finding most suitable web service from vast collection of web services is very crucial for successful execution of applications. Traditional web service discovery approach is a keyword based search using UDDI. Various other approaches for discovering web services are also available. Some of the discovery approaches are syntax based while other are semantic based. Having system for service discovery which can work automatically is also the concern of service discovery approaches. As these approaches are different, one solution may be better than another depending on requirements. Selecting a specific service discovery system is a hard task. In this paper, we give an overview of different approaches for web service discovery described in literature. We present a survey of how these approaches differ from each other.
Spatial Outlier Detection from GSM Mobility Data
Venue: arXiv cs.NI 2012
Year: 2012

This paper has been withdrawn by the authors. With the rigorous growth of cellular network many mobility datasets are available publically, which attracted researchers to study human mobility fall under spatio-temporal phenomenon. Mobility profile building is main task in spatio-temporal trend analysis which can be extracted from the location information available in the dataset. The location information is usually gathered through the GPS, service provider assisted faux GPS and Cell Global Identity (CGI). Because of high power consumption and extra resource installation requirement in GPS related methods, Cell Global Identity is most inexpensive method and readily available solution for location information. CGI location information is four set head i.e. Mobile country code (MCC), Mobile network code (MNC), Location area code (LAC) and Cell ID, location information is retrieved in form of longitude and latitude coordinates through any of publically available Cell Id databases e.g. Google location API using CGI. However due to of fast growth in GSM network, change in topology by the GSM service provider and technology shift toward 3G exact spatial extraction is somehow a problem in it, so location extraction must dealt with spatial outlier's problem first for mobility building. In this paper we proposed a methodology for the detection of spatial outliers from GSM CGI data, the proposed methodology is hierarchical clustering based and used the basic GSM network architecture properties.
A retrial system with two input streams and two orbit queues
Venue: arXiv cs.DM 2012
Year: 2012

Two independent Poisson streams of jobs flow into a single-server service system having a limited common buffer that can hold at most one job. If a type-i job (i=1,2) finds the server busy, it is blocked and routed to a separate type-i retrial (orbit) queue that attempts to re-dispatch its jobs at its specific Poisson rate. This creates a system with three dependent queues. Such a queueing system serves as a model for two competing job streams in a carrier sensing multiple access system. We study the queueing system using multi-dimensional probability generating functions, and derive its necessary and sufficient stability conditions while solving a boundary value problem. Various performance measures are calculated and numerical results are presented.
Soundness of Unravelings for Conditional Term Rewriting Systems via Ultra-Properties Related to Linearity
Venue: arXiv cs.LO 2012
Year: 2012

Unravelings are transformations from a conditional term rewriting system (CTRS, for short) over an original signature into an unconditional term rewriting systems (TRS, for short) over an extended signature. They are not sound w.r.t. reduction for every CTRS, while they are complete w.r.t. reduction. Here, soundness w.r.t. reduction means that every reduction sequence of the corresponding unraveled TRS, of which the initial and end terms are over the original signature, can be simulated by the reduction of the original CTRS. In this paper, we show that an optimized variant of Ohlebusch's unraveling for a deterministic CTRS is sound w.r.t. reduction if the corresponding unraveled TRS is left-linear or both right-linear and non-erasing. We also show that soundness of the variant implies that of Ohlebusch's unraveling. Finally, we show that soundness of Ohlebusch's unraveling is the weakest in soundness of the other unravelings and a transformation, proposed by Serbanuta and Rosu, for (normal) deterministic CTRSs, i.e., soundness of them respectively implies that of Ohlebusch's unraveling.
Spectrum Sharing with Distributed Relay Selection and Clustering
Venue: arXiv cs.IT 2012
Year: 2012

We consider a spectrum-sharing network where n secondary relays are used to increase secondary rate and also mitigate interference on the primary by reducing the required overall secondary emitted power. We propose a distributed relay selection and clustering framework, obtain closed-form expressions for the secondary rate, and show that secondary rate increases proportionally to log n. Remarkably, this is on the same order as the growth rate obtained in the absence of a primary system and its imposed constraints. Our results show that to maximize the rate, the secondary relays must transmit with power proportional to n^(-1) (thus the sum of relay powers is bounded) and also that the secondary source may not operate at its maximum allowable power. The tradeoff between the secondary rate and the interference on the primary is also characterized, showing that the primary interference can be reduced asymptotically to zero as n increases, while still maintaining a secondary rate that grows proportionally to log n. Finally, to address the rate loss due to half-duplex relaying in the secondary, we propose an alternating relay protocol and investigate its performance.
Exact Recovery of Sparsely-Used Dictionaries
Venue: arXiv cs.LG 2012
Year: 2012

We consider the problem of learning sparsely used dictionaries with an arbitrary square dictionary and a random, sparse coefficient matrix. We prove that $O (n \log n)$ samples are sufficient to uniquely determine the coefficient matrix. Based on this proof, we design a polynomial-time algorithm, called Exact Recovery of Sparsely-Used Dictionaries (ER-SpUD), and prove that it probably recovers the dictionary and coefficient matrix when the coefficient matrix is sufficiently sparse. Simulation results show that ER-SpUD reveals the true dictionary as well as the coefficients with probability higher than many state-of-the-art algorithms.
Linear spaces and transversal designs: k-anonymous combinatorial configurations for anonymous database search
Venue: arXiv cs.CR 2012
Year: 2012

Anonymous database search protocols allow users to query a database anonymously. This can be achieved by letting the users form a peer-to-peer community and post queries on behalf of each other. In this article we discuss an application of combinatorial configurations (also known as regular and uniform partial linear spaces) to a protocol for anonymous database search, as defining the key-distribution within the user community that implements the protocol. The degree of anonymity that can be provided by the protocol is determined by properties of the neighborhoods and the closed neighborhoods of the points in the combinatorial configuration that is used. Combinatorial configurations with unique neighborhoods or unique closed neighborhoods are described and we show how to attack the protocol if such configurations are used. We apply k-anonymity arguments and present the combinatorial configurations with k-anonymous neighborhoods and with k-anonymous closed neighborhoods. The transversal designs and the linear spaces are presented as optimal configurations among the configurations with k-anonymous neighborhoods and k-anonymous closed neighborhoods, respectively.
Performance Evaluation of Ant-Based Routing Protocols for Wireless Sensor Networks
Venue: arXiv cs.DC 2012
Year: 2012

High efficient routing is an important issue in the design of limited energy resource Wireless Sensor Networks (WSNs). Due to the characteristic of the environment at which the sensor node is to operate, coupled with severe resources; on-board energy, transmission power, processing capability, and storage limitations, prompt for careful resource management and new routing protocol so as to counteract the differences and challenges. To this end, we present an Improved Energy-Efficient Ant-Based Routing (IEEABR) Algorithm in wireless sensor networks. Compared to the state-of-the-art Ant-Based routing protocols; Basic Ant-Based Routing (BABR) Algorithm, Sensor-driven and Cost-aware ant routing (SC), Flooded Forward ant routing (FF), Flooded Piggybacked ant routing (FP), and Energy-Efficient Ant-Based Routing (EEABR), the proposed IEEABR approach has advantages in terms of reduced energy usage which can effectively balance the WSN node's power consumption, and high energy efficiency. The performance evaluations for the algorithms on a real application are conducted in a well known WSN MATLAB-based simulator (RMASE) using both static and dynamic scenario.
Bootstrapping Monte Carlo Tree Search with an Imperfect Heuristic
Venue: arXiv cs.AI 2012
Year: 2012

We consider the problem of using a heuristic policy to improve the value approximation by the Upper Confidence Bound applied in Trees (UCT) algorithm in non-adversarial settings such as planning with large-state space Markov Decision Processes. Current improvements to UCT focus on either changing the action selection formula at the internal nodes or the rollout policy at the leaf nodes of the search tree. In this work, we propose to add an auxiliary arm to each of the internal nodes, and always use the heuristic policy to roll out simulations at the auxiliary arms. The method aims to get fast convergence to optimal values at states where the heuristic policy is optimal, while retaining similar approximation as the original UCT in other states. We show that bootstrapping with the proposed method in the new algorithm, UCT-Aux, performs better compared to the original UCT algorithm and its variants in two benchmark experiment settings. We also examine conditions under which UCT-Aux works well.
The Online Replacement Path Problem
Venue: arXiv cs.DS 2012
Year: 2012

We study a natural online variant of the replacement path problem. The \textit{replacement path problem} asks to find for a given graph $G = (V,E)$, two designated vertices $s,t\in V$ and a shortest $s$-$t$ path $P$ in $G$, a \textit{replacement path} $P_e$ for every edge $e$ on the path $P$. The replacement path $P_e$ is simply a shortest $s$-$t$ path in the graph, which avoids the \textit{failed} edge $e$. We adapt this problem to deal with the natural scenario, that the edge which failed is not known at the time of solution implementation. Instead, our problem assumes that the identity of the failed edge only becomes available when the routing mechanism tries to cross the edge. This situation is motivated by applications in distributed networks, where information about recent changes in the network is only stored locally, and fault-tolerant optimization, where an adversary tries to delay the discovery of the materialized scenario as much as possible. Consequently, we define the \textit{online replacement path problem}, which asks to find a nominal $s$-$t$ path $Q$ and detours $Q_e$ for every edge on the path $Q$, such that the worst-case arrival time at the destination is minimized. Our main contribution is a label setting algorithm, which solves the problem in undirected graphs in time $O(m \log n)$ and linear space for all sources and a single destination. We also present algorithms for extensions of the model to any bounded number of failed edges.
To Sense or Not To Sense
Venue: arXiv cs.IT 2012
Year: 2012

A longer sensing time improves the sensing performance; however, with a fixed frame size, the longer sensing time will reduce the allowable data transmission time of the secondary user (SU). In this paper, we try to address the tradeoff between sensing the primary channel for $τ$ seconds of the time slot proceeded by randomly accessing it and randomly accessing primary channel without sensing to avoid wasting $τ$ seconds in sensing. The SU senses primary channel to exploit the periods of silence, if the primary user (PU) is declared to be idle the SU randomly accesses the channel with some access probability $a_s$. In addition to randomly accesses the channel if the PU is sensed to be idle, it possibly accesses it if the channel is declared to be busy with some access probability $b_s$. This is because the probability of false alarm and misdetection cause significant secondary throughput degradation and affect the PU QoS. We propose variable sensing duration schemes where the SU optimizes over the optimal sensing time to achieve the maximum stable throughput for both primary and secondary queues. The results reveal the performance gains of the proposed schemes over the conventional sensing scheme, i.e., the SU senses the primary channel for $τ$ seconds and accesses with probability 1 if the PU is declared to be idle. Also, the proposed schemes overcome random access without sensing scheme. The theoretical and numerical results show that pairs of misdetection and false alarm probabilities may exist such that sensing the primary channel for very small duration overcomes sensing it for large portion of the time slot. In addition, for certain average arrival rate to the primary queue pairs of misdetection and false alarm probabilities may exist such that the random access without sensing overcomes the random access with long sensing duration.
Mining Preserving Structures in a Graph Sequence
Venue: arXiv cs.DS 2012
Year: 2012

In the recent research of data mining, frequent structures in a sequence of graphs have been studied intensively, and one of the main concern is changing structures along a sequence of graphs that can capture dynamic properties of data. On the contrary, we newly focus on "preserving structures" in a graph sequence that satisfy a given property for a certain period, and mining such structures is studied. As for an onset, we bring up two structures, a connected vertex subset and a clique that exist for a certain period. We consider the problem of enumerating these structures. and present polynomial delay algorithms for the problems. Their running time may depend on the size of the representation, however, if each edge has at most one time interval in the representation, the running time is O(|V||E|^3) for connected vertex subsets and O(min{Δ^5, |E|^2Δ}) for cliques, where the input graph is G = (V,E) with maximum degree Δ. To the best of our knowledge, this is the first approach to the treatment of this notion, namely, preserving structures.
Two Step CCA: A new spectral method for estimating vector models of words
Venue: arXiv cs.CL 2012
Year: 2012

Unlabeled data is often used to learn representations which can be used to supplement baseline features in a supervised learner. For example, for text applications where the words lie in a very high dimensional space (the size of the vocabulary), one can learn a low rank "dictionary" by an eigen-decomposition of the word co-occurrence matrix (e.g. using PCA or CCA). In this paper, we present a new spectral method based on CCA to learn an eigenword dictionary. Our improved procedure computes two set of CCAs, the first one between the left and right contexts of the given word and the second one between the projections resulting from this CCA and the word itself. We prove theoretically that this two-step procedure has lower sample complexity than the simple single step procedure and also illustrate the empirical efficacy of our approach and the richness of representations learned by our Two Step CCA (TSCCA) procedure on the tasks of POS tagging and sentiment classification.
Dynamic Traitor Tracing for Arbitrary Alphabets: Divide and Conquer
Venue: arXiv cs.CR 2012
Year: 2012

We give a generic divide-and-conquer approach for constructing collusion-resistant probabilistic dynamic traitor tracing schemes with larger alphabets from schemes with smaller alphabets. This construction offers a linear tradeoff between the alphabet size and the codelength. In particular, we show that applying our results to the binary dynamic Tardos scheme of Laarhoven et al. leads to schemes that are shorter by a factor equal to half the alphabet size. Asymptotically, these codelengths correspond, up to a constant factor, to the fingerprinting capacity for static probabilistic schemes. This gives a hierarchy of probabilistic dynamic traitor tracing schemes, and bridges the gap between the low bandwidth, high codelength scheme of Laarhoven et al. and the high bandwidth, low codelength scheme of Fiat and Tassa.
Elimination of Spurious Ambiguity in Transition-Based Dependency Parsing
Venue: arXiv cs.CL 2012
Year: 2012

We present a novel technique to remove spurious ambiguity from transition systems for dependency parsing. Our technique chooses a canonical sequence of transition operations (computation) for a given dependency tree. Our technique can be applied to a large class of bottom-up transition systems, including for instance Nivre (2004) and Attardi (2006).
An Empirical Comparison of Algorithms for Aggregating Expert Predictions
Venue: arXiv cs.AI 2012
Year: 2012

Predicting the outcomes of future events is a challenging problem for which a variety of solution methods have been explored and attempted. We present an empirical comparison of a variety of online and offline adaptive algorithms for aggregating experts' predictions of the outcomes of five years of US National Football League games (1319 games) using expert probability elicitations obtained from an Internet contest called ProbabilitySports. We find that it is difficult to improve over simple averaging of the predictions in terms of prediction accuracy, but that there is room for improvement in quadratic loss. Somewhat surprisingly, a Bayesian estimation algorithm which estimates the variance of each expert's prediction exhibits the most consistent superior performance over simple averaging among our collection of algorithms.
A Variational Approach for Approximating Bayesian Networks by Edge Deletion
Venue: arXiv cs.AI 2012
Year: 2012

We consider in this paper the formulation of approximate inference in Bayesian networks as a problem of exact inference on an approximate network that results from deleting edges (to reduce treewidth). We have shown in earlier work that deleting edges calls for introducing auxiliary network parameters to compensate for lost dependencies, and proposed intuitive conditions for determining these parameters. We have also shown that our method corresponds to IBP when enough edges are deleted to yield a polytree, and corresponds to some generalizations of IBP when fewer edges are deleted. In this paper, we propose a different criteria for determining auxiliary parameters based on optimizing the KL-divergence between the original and approximate networks. We discuss the relationship between the two methods for selecting parameters, shedding new light on IBP and its generalizations. We also discuss the application of our new method to approximating inference problems which are exponential in constrained treewidth, including MAP and nonmyopic value of information.
Robust Learning Equilibrium
Venue: arXiv cs.GT 2012
Year: 2012

We introduce robust learning equilibrium. The idea of learning equilibrium is that learning algorithms in multi-agent systems should themselves be in equilibrium rather than only lead to equilibrium. That is, learning equilibrium is immune to strategic deviations: Every agent is better off using its prescribed learning algorithm, if all other agents follow their algorithms, regardless of the unknown state of the environment. However, a learning equilibrium may not be immune to non strategic mistakes. For example, if for a certain period of time there is a failure in the monitoring devices (e.g., the correct input does not reach the agents), then it may not be in equilibrium to follow the algorithm after the devices are corrected. A robust learning equilibrium is immune also to such non-strategic mistakes. The existence of (robust) learning equilibrium is especially challenging when the monitoring devices are 'weak'. That is, the information available to each agent at each stage is limited. We initiate a study of robust learning equilibrium with general monitoring structure and apply it to the context of auctions. We prove the existence of robust learning equilibrium in repeated first-price auctions, and discuss its properties.