OpenRaiser/Intern-Atlas huggingface dataset:
Enhancing congestion control to address link failure loss over mobile ad-hoc network
Venue: arXiv cs.NI 2011
Year: 2011

Standard congestion control cannot detect link failure losses which occur due to mobility and power scarcity in multi-hop Ad-Hoc network (MANET). Moreover, successive executions of Back-off algorithm deficiently grow Retransmission Timeout (RTO) exponentially for new route. The importance of detecting and responding link failure losses is to prevent sender from remaining idle unnecessarily and manage number of packet retransmission overhead. In contrast to Cross-layer approaches which require feedback information from lower layers, this paper operates purely in Transport layer. This paper explores an end-to-end threshold-based algorithm which enhances congestion control to address link failure loss in MANET. It consists of two phases. First, threshold-based loss classification algorithm distinguishes losses due to link failure by estimating queue usage based on Relative One-way Trip Time (ROTT). Second phase adjusts RTO for new route by comparing capabilities of new route to the broken route using available information in Transport layer such as ROTT and number of hops.
The new Excellence Indicator in the World Report of the SCImago Institutions Rankings 2011
Venue: arXiv cs.DL 2011
Year: 2011

The new excellence indicator in the World Report of the SCImago Institutions Rankings (SIR) makes it possible to test differences in the ranking in terms of statistical significance. For example, at the 17th position of these rankings, UCLA has an output of 37,994 papers with an excellence indicator of 28.9. Stanford University follows at the 19th position with 37,885 papers and 29.1 excellence, and z = - 0.607. The difference between these two institution thus is not statistically significant. We provide a calculator at http://www.leydesdorff.net/scimago11/scimago11.xls in which one can fill out this test for any two institutions and also for each institution on whether its score is significantly above or below expectation (assuming that 10% of the papers are for stochastic reasons in the top-10% set).
Annotated Raptor Codes
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, an extension of raptor codes is introduced which keeps all the desirable properties of raptor codes, including the linear complexity of encoding and decoding per information bit, unchanged. The new design, however, improves the performance in terms of the reception rate. Our simulations show a 10% reduction in the needed overhead at the benchmark block length of 64,520 bits and with the same complexity per information bit.
An Algebraic Graphical Model for Decision with Uncertainties, Feasibilities, and Utilities
Venue: arXiv cs.AI 2011
Year: 2011

Numerous formalisms and dedicated algorithms have been designed in the last decades to model and solve decision making problems. Some formalisms, such as constraint networks, can express "simple" decision problems, while others are designed to take into account uncertainties, unfeasible decisions, and utilities. Even in a single formalism, several variants are often proposed to model different types of uncertainty (probability, possibility...) or utility (additive or not). In this article, we introduce an algebraic graphical model that encompasses a large number of such formalisms: (1) we first adapt previous structures from Friedman, Chu and Halpern for representing uncertainty, utility, and expected utility in order to deal with generic forms of sequential decision making; (2) on these structures, we then introduce composite graphical models that express information via variables linked by "local" functions, thanks to conditional independence; (3) on these graphical models, we finally define a simple class of queries which can represent various scenarios in terms of observabilities and controllabilities. A natural decision-tree semantics for such queries is completed by an equivalent operational semantics, which induces generic algorithms. The proposed framework, called the Plausibility-Feasibility-Utility (PFU) framework, not only provides a better understanding of the links between existing formalisms, but it also covers yet unpublished frameworks (such as possibilistic influence diagrams) and unifies formalisms such as quantified boolean formulas and influence diagrams. Our backtrack and variable elimination generic algorithms are a first step towards unified algorithms.
Semantic Matchmaking as Non-Monotonic Reasoning: A Description Logic Approach
Venue: arXiv cs.AI 2011
Year: 2011

Matchmaking arises when supply and demand meet in an electronic marketplace, or when agents search for a web service to perform some task, or even when recruiting agencies match curricula and job profiles. In such open environments, the objective of a matchmaking process is to discover best available offers to a given request. We address the problem of matchmaking from a knowledge representation perspective, with a formalization based on Description Logics. We devise Concept Abduction and Concept Contraction as non-monotonic inferences in Description Logics suitable for modeling matchmaking in a logical framework, and prove some related complexity results. We also present reasonable algorithms for semantic matchmaking based on the devised inferences, and prove that they obey to some commonsense properties. Finally, we report on the implementation of the proposed matchmaking framework, which has been used both as a mediator in e-marketplaces and for semantic web services discovery.
The Strategy-Proofness Landscape of Merging
Venue: arXiv cs.GT 2011
Year: 2011

Merging operators aim at defining the beliefs/goals of a group of agents from the beliefs/goals of each member of the group. Whenever an agent of the group has preferences over the possible results of the merging process (i.e., the possible merged bases), she can try to rig the merging process by lying on her true beliefs/goals if this leads to better merged base according to her point of view. Obviously, strategy-proof operators are highly desirable in order to guarantee equity among agents even when some of them are not sincere. In this paper, we draw the strategy-proof landscape for many merging operators from the literature, including model-based ones and formula-based ones. Both the general case and several restrictions on the merging process are considered.
Resource Allocation Among Agents with MDP-Induced Preferences
Venue: arXiv cs.MA 2011
Year: 2011

Allocating scarce resources among agents to maximize global utility is, in general, computationally challenging. We focus on problems where resources enable agents to execute actions in stochastic environments, modeled as Markov decision processes (MDPs), such that the value of a resource bundle is defined as the expected value of the optimal MDP policy realizable given these resources. We present an algorithm that simultaneously solves the resource-allocation and the policy-optimization problems. This allows us to avoid explicitly representing utilities over exponentially many resource bundles, leading to drastic (often exponential) reductions in computational complexity. We then use this algorithm in the context of self-interested agents to design a combinatorial auction for allocating resources. We empirically demonstrate the effectiveness of our approach by showing that it can, in minutes, optimally solve problems for which a straightforward combinatorial resource-allocation technique would require the agents to enumerate up to 2^100 resource bundles and the auctioneer to solve an NP-complete problem with an input of that size.
Towards a Query Language for the Web of Data (A Vision Paper)
Venue: arXiv cs.DB 2011
Year: 2011

Research on querying the Web of Data is still in its infancy. In this paper, we provide an initial set of general features that we envision should be considered in order to define a query language for the Web of Data. Furthermore, for each of these features, we pose questions that have not been addressed before in the context of querying the Web of Data. We believe that addressing these questions and studying these features may guide the next 10 years of research on the Web of Data.
Syndromic classification of Twitter messages
Venue: arXiv cs.CL 2011
Year: 2011

Recent studies have shown strong correlation between social networking data and national influenza rates. We expanded upon this success to develop an automated text mining system that classifies Twitter messages in real time into six syndromic categories based on key terms from a public health ontology. 10-fold cross validation tests were used to compare Naive Bayes (NB) and Support Vector Machine (SVM) models on a corpus of 7431 Twitter messages. SVM performed better than NB on 4 out of 6 syndromes. The best performing classifiers showed moderately strong F1 scores: respiratory = 86.2 (NB); gastrointestinal = 85.4 (SVM polynomial kernel degree 2); neurological = 88.6 (SVM polynomial kernel degree 1); rash = 86.0 (SVM polynomial kernel degree 1); constitutional = 89.3 (SVM polynomial kernel degree 1); hemorrhagic = 89.9 (NB). The resulting classifiers were deployed together with an EARS C2 aberration detection algorithm in an experimental online system.
Structure of lexicographic Groebner bases in three variables of ideals of dimension zero
Venue: arXiv cs.SC 2011
Year: 2011

We generalize the structural theorem of Lazard in 1985, from 2 variables to 3 variables. We use the Gianni-Kalkbrener result to do this, which implies some restrictions inside which lies the case of a radical ideal.
Non-memoryless Analog Network Coding in Two-Way Relay Channel
Venue: arXiv cs.IT 2011
Year: 2011

Physical-layer Network Coding (PNC) can significantly improve the throughput of two-way relay channels. An interesting variant of PNC is Analog Network Coding (ANC). Almost all ANC schemes proposed to date, however, operate in a symbol by symbol manner (memoryless) and cannot exploit the redundant information in channel-coded packets to enhance performance. This paper proposes a non-memoryless ANC scheme. In particular, we design a soft-input soft-output decoder for the relay node to process the superimposed packets from the two end nodes to yield an estimated MMSE packet for forwarding back to the end nodes. Our decoder takes into account the correlation among different symbols in the packets due to channel coding, and provides significantly improved MSE performance. Our analysis shows that the SNR improvement at the relay node is lower bounded by 1/R (R is the code rate) with the simplest LDPC code (repeat code). The SNR improvement is also verified by numerical simulation with LDPC code. Our results indicate that LDPC codes of different degrees are preferred in different SNR regions. Generally speaking, smaller degrees are preferred for lower SNRs.
Tron, a combinatorial Game on abstract Graphs
Venue: arXiv cs.CC 2011
Year: 2011

We study the combinatorial two-player game Tron. We answer the extremal question on general graphs and also consider smaller graph classes. Bodlaender and Kloks conjectured in [2] PSPACE- completeness. We proof this conjecture.
Mining Patterns in Networks using Homomorphism
Venue: arXiv cs.DS 2011
Year: 2011

In recent years many algorithms have been developed for finding patterns in graphs and networks. A disadvantage of these algorithms is that they use subgraph isomorphism to determine the support of a graph pattern; subgraph isomorphism is a well-known NP complete problem. In this paper, we propose an alternative approach which mines tree patterns in networks by using subgraph homomorphism. The advantage of homomorphism is that it can be computed in polynomial time, which allows us to develop an algorithm that mines tree patterns in arbitrary graphs in incremental polynomial time. Homomorphism however entails two problems not found when using isomorphism: (1) two patterns of different size can be equivalent; (2) patterns of unbounded size can be frequent. In this paper we formalize these problems and study solutions that easily fit within our algorithm.
Partial Data Compression and Text Indexing via Optimal Suffix Multi-Selection
Venue: arXiv cs.DS 2011
Year: 2011

Consider an input text string T[1,N] drawn from an unbounded alphabet. We study partial computation in suffix-based problems for Data Compression and Text Indexing such as (I) retrieve any segment of K<=N consecutive symbols from the Burrows-Wheeler transform of T, and (II) retrieve any chunk of K<=N consecutive entries of the Suffix Array or the Suffix Tree. Prior literature would take O(N log N) comparisons (and time) to solve these problems by solving the total problem of building the entire Burrows-Wheeler transform or Text Index for T, and performing a post-processing to single out the wanted portion. We introduce a novel adaptive approach to partial computational problems above, and solve both the partial problems in O(K log K + N) comparisons and time, improving the best known running times of O(N log N) for K=o(N). These partial-computation problems are intimately related since they share a common bottleneck: the suffix multi-selection problem, which is to output the suffixes of rank r_1,r_2,...,r_K under the lexicographic order, where r_1<r_2<...<r_K, r_i in [1,N]. Special cases of this problem are well known: K=N is the suffix sorting problem that is the workhorse in Stringology with hundreds of applications, and K=1 is the recently studied suffix selection. We show that suffix multi-selection can be solved in Theta(N log N - sum_{j=0}^K Delta_j log Delta_j+N) time and comparisons, where r_0=0, r_{K+1}=N+1, and Delta_j=r_{j+1}-r_j for 0<=j<=K. This is asymptotically optimal, and also matches the bound in [Dobkin, Munro, JACM 28(3)] for multi-selection on atomic elements (not suffixes). Matching the bound known for atomic elements for strings is a long running theme and challenge from 70's, which we achieve for the suffix multi-selection problem. The partial suffix problems as well as the suffix multi-selection problem have many applications.
An Approach to Provide Security in Mobile Ad-Hoc Networks Using Counter Mode of Encryption on Mac Layer
Venue: arXiv cs.NI 2011
Year: 2011

Security in any of the networks became an important issue in this paper we have implemented a security mechanism on Medium Access Control layer by Assured Neighbor based Security Protocol to provide authentication and confidentiality of packets along with High speed transmission for Ad hoc networks. Here we have divided the protocol into two different parts. The first part deals with Routing layer information; in this part we have tried to implement a possible strategy for detecting and isolating the malicious nodes. A trust counter for each node is determined which can be actively increased and decreased depending upon the trust value for the purpose of forwarding the packets from source node to destination node with the help of intermediate nodes. A threshold level is also predetermined to detect the malicious nodes. If the value of the node in trust counter is less than the threshold value then the node is denoted 'malicious'. The second part of our protocol deals with the security in the link layer. For this security reason we have used CTR (Counter) approach for authentication and encryption. We have simulated all our strategies and schemes in NS-2, the result of which gives a conclusion that our proposed protocol i.e. Assured Neighbor based Security Protocol can perform high packet delivery against various intruders and also packet delivery ratio against mobility with low delays and low overheads.
Minimum Complexity Pursuit
Venue: arXiv cs.IT 2011
Year: 2011

The fast growing field of compressed sensing is founded on the fact that if a signal is 'simple' and has some 'structure', then it can be reconstructed accurately with far fewer samples than its ambient dimension. Many different plausible structures have been explored in this field, ranging from sparsity to low-rankness and to finite rate of innovation. However, there are important abstract questions that are yet to be answered. For instance, what are the general abstract meanings of 'structure' and 'simplicity'? Do there exist universal algorithms for recovering such simple structured objects from fewer samples than their ambient dimension? In this paper, we aim to address these two questions. Using algorithmic information theory tools such as Kolmogorov complexity, we provide a unified method of describing 'simplicity' and 'structure'. We then explore the performance of an algorithm motivated by Ocam's Razor (called MCP for minimum complexity pursuit) and show that it requires $O(k\log n)$ number of samples to recover a signal, where $k$ and $n$ represent its complexity and ambient dimension, respectively. Finally, we discuss more general classes of signals and provide guarantees on the performance of MCP.
Network on Chip: a New Approach of QoS Metric Modeling Based on Calculus Theory
Venue: arXiv cs.NI 2011
Year: 2011

A NoC is composed by IP cores (Intellectual Propriety) and switches connected among themselves by communication channels. End-to-End Delay (EED) communication is accomplished by the exchange of data among IP cores. Often, the structure of particular messages is not adequate for the communication purposes. This leads to the concept of packet switching. In the context of NoCs, packets are composed by header, payload, and trailer. Packets are divided into small pieces called Flits. It appears of importance, to meet the required performance in NoC hardware resources. It should be specified in an earlier step of the system design. The main attention should be given to the choice of some network parameters such as the physical buffer size in the node. The EED and packet loss are some of the critical QoS metrics. Some real-time and multimedia applications bound up these parameters and require specific hardware resources and particular management approaches in the NoC switch. A traffic contract (SLA, Service Level Agreement) specifies the ability of a network or protocol to give guaranteed performance, throughput or latency bounds based on mutually agreed measures, usually by prioritizing traffic. A defined Quality of Service (QoS) may be required for some types of network real time traffic or multimedia applications. The main goal of this paper is, using the Network on Chip modeling architecture, to define a QoS metric. We focus on the network delay bound and packet losses. This approach is based on the Network Calculus theory, a mathematical model to represent the data flows behavior between IPs interconnected over NoC. We propose an approach of QoS-metric based on QoS-parameter prioritization factors for multi applications-service using calculus model.
Playing Mastermind With Constant-Size Memory
Venue: arXiv cs.DS 2011
Year: 2011

We analyze the classic board game of Mastermind with $n$ holes and a constant number of colors. A result of Chvátal (Combinatorica 3 (1983), 325-329) states that the codebreaker can find the secret code with $Θ(n / \log n)$ questions. We show that this bound remains valid if the codebreaker may only store a constant number of guesses and answers. In addition to an intrinsic interest in this question, our result also disproves a conjecture of Droste, Jansen, and Wegener (Theory of Computing Systems 39 (2006), 525-544) on the memory-restricted black-box complexity of the OneMax function class.
Accelerating Algorithms using a Dataflow Graph in a Reconfigurable System
Venue: arXiv cs.AR 2011
Year: 2011

In this paper, the acceleration of algorithms using a design of a field programmable gate array (FPGA) as a prototype of a static dataflow architecture is discussed. The static dataflow architecture using operators interconnected by parallel buses was implemented. Accelerating algorithms using a dataflow graph in a reconfigurable system shows the potential for high computation rates. The results of benchmarks implemented using the static dataflow architecture are reported at the end of this paper.
Time-Stampless Adaptive Nonuniform Sampling for Stochastic Signals
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we introduce a time-stampless adaptive nonuniform sampling (TANS) framework, in which time increments between samples are determined by a function of the $m$ most recent increments and sample values. Since only past samples are used in computing time increments, it is not necessary to save sampling times (time stamps) for use in the reconstruction process. We focus on two TANS schemes for discrete-time stochastic signals: a greedy method, and a method based on dynamic programming. We analyze the performances of these schemes by computing (or bounding) their trade-offs between sampling rate and expected reconstruction distortion for autoregressive and Markovian signals. Simulation results support the analysis of the sampling schemes. We show that, by opportunistically adapting to local signal characteristics, TANS may lead to improved power efficiency in some applications.
An Upper Bound on Broadcast Subspace Codes
Venue: arXiv cs.IT 2011
Year: 2011

Linear operator broadcast channel (LOBC) models the scenario of multi-rate packet broadcasting over a network, when random network coding is applied. This paper presents the framework of algebraic coding for LOBCs and provides a Hamming-like upper bound on (multishot) subspace codes for LOBCs.
Traffic-Redundancy Aware Network Design
Venue: arXiv cs.DS 2011
Year: 2011

We consider network design problems for information networks where routers can replicate data but cannot alter it. This functionality allows the network to eliminate data-redundancy in traffic, thereby saving on routing costs. We consider two problems within this framework and design approximation algorithms. The first problem we study is the traffic-redundancy aware network design (RAND) problem. We are given a weighted graph over a single server and many clients. The server owns a number of different data packets and each client desires a subset of the packets; the client demand sets form a laminar set system. Our goal is to connect every client to the source via a single path, such that the collective cost of the resulting network is minimized. Here the transportation cost over an edge is its weight times times the number of distinct packets that it carries. The second problem is a facility location problem that we call RAFL. Here the goal is to find an assignment from clients to facilities such that the total cost of routing packets from the facilities to clients (along unshared paths), plus the total cost of "producing" one copy of each desired packet at each facility is minimized. We present a constant factor approximation for the RAFL and an O(log P) approximation for RAND, where P is the total number of distinct packets. We remark that P is always at most the number of different demand sets desired or the number of clients, and is generally much smaller.
Ideogram Based Chinese Sentiment Word Orientation Computation
Venue: arXiv cs.CL 2011
Year: 2011

This paper presents a novel algorithm to compute sentiment orientation of Chinese sentiment word. The algorithm uses ideograms which are a distinguishing feature of Chinese language. The proposed algorithm can be applied to any sentiment classification scheme. To compute a word's sentiment orientation using the proposed algorithm, only the word itself and a precomputed character ontology is required, rather than a corpus. The influence of three parameters over the algorithm performance is analyzed and verified by experiment. Experiment also shows that proposed algorithm achieves an F Measure of 85.02% outperforming existing ideogram based algorithm.