OpenRaiser/Intern-Atlas huggingface dataset:
Statistical and Computational Tradeoffs in Stochastic Composite Likelihood
Venue: arXiv cs.LG 2010
Year: 2010

Maximum likelihood estimators are often of limited practical use due to the intensive computation they require. We propose a family of alternative estimators that maximize a stochastic variation of the composite likelihood function. Each of the estimators resolve the computation-accuracy tradeoff differently, and taken together they span a continuous spectrum of computation-accuracy tradeoff resolutions. We prove the consistency of the estimators, provide formulas for their asymptotic variance, statistical robustness, and computational complexity. We discuss experimental results in the context of Boltzmann machines and conditional random fields. The theoretical and experimental studies demonstrate the effectiveness of the estimators when the computational resources are insufficient. They also demonstrate that in some cases reduced computational complexity is associated with robustness thereby increasing statistical accuracy.
Information Fusion for Anomaly Detection with the Dendritic Cell Algorithm
Venue: arXiv cs.AI 2010
Year: 2010

Dendritic cells are antigen presenting cells that provide a vital link between the innate and adaptive immune system, providing the initial detection of pathogenic invaders. Research into this family of cells has revealed that they perform information fusion which directs immune responses. We have derived a Dendritic Cell Algorithm based on the functionality of these cells, by modelling the biological signals and differentiation pathways to build a control mechanism for an artificial immune system. We present algorithmic details in addition to experimental results, when the algorithm was applied to anomaly detection for the detection of port scans. The results show the Dendritic Cell Algorithm is sucessful at detecting port scans.
The complexity of positive first-order logic without equality
Venue: arXiv cs.LO 2010
Year: 2010

We study the complexity of evaluating positive equality-free sentences of first-order (FO) logic over a fixed, finite structure B. This may be seen as a natural generalisation of the non-uniform quantified constraint satisfaction problem QCSP(B). We introduce surjective hyper-endomorphisms and use them in proving a Galois connection that characterises definability in positive equality-free FO. Through an algebraic method, we derive a complete complexity classification for our problems as B ranges over structures of size at most three. Specifically, each problem is either in Logspace, is NP-complete, is co-NP-complete or is Pspace-complete.
Support Recovery of Sparse Signals
Venue: arXiv cs.IT 2010
Year: 2010

We consider the problem of exact support recovery of sparse signals via noisy measurements. The main focus is the sufficient and necessary conditions on the number of measurements for support recovery to be reliable. By drawing an analogy between the problem of support recovery and the problem of channel coding over the Gaussian multiple access channel, and exploiting mathematical tools developed for the latter problem, we obtain an information theoretic framework for analyzing the performance limits of support recovery. Sharp sufficient and necessary conditions on the number of measurements in terms of the signal sparsity level and the measurement noise level are derived. Specifically, when the number of nonzero entries is held fixed, the exact asymptotics on the number of measurements for support recovery is developed. When the number of nonzero entries increases in certain manners, we obtain sufficient conditions tighter than existing results. In addition, we show that the proposed methodology can deal with a variety of models of sparse signal recovery, hence demonstrating its potential as an effective analytical tool.
Tag Clusters as Information Retrieval Interfaces
Venue: arXiv cs.IR 2010
Year: 2010

The paper presents our design of a next generation information retrieval system based on tag co-occurrences and subsequent clustering. We help users getting access to digital data through information visualization in the form of tag clusters. Current problems like the absence of interactivity and semantics between tags or the difficulty of adding additional search arguments are solved. In the evaluation, based upon SERVQUAL and IT systems quality indicators, we found out that tag clusters are perceived as more useful than tag clouds, are much more trustworthy, and are more enjoyable to use.
Minimum Spanning Tree on Spatio-Temporal Networks
Venue: arXiv cs.DS 2010
Year: 2010

Given a spatio-temporal network (ST network) where edge properties vary with time, a time-sub-interval minimum spanning tree (TSMST) is a collection of minimum spanning trees of the ST network, where each tree is associated with a time interval. During this time interval, the total cost of tree is least among all the spanning trees. The TSMST problem aims to identify a collection of distinct minimum spanning trees and their respective time-sub-intervals under the constraint that the edge weight functions are piecewise linear. This is an important problem in ST network application domains such as wireless sensor networks (e.g., energy efficient routing). Computing TSMST is challenging because the ranking of candidate spanning trees is non-stationary over a given time interval. Existing methods such as dynamic graph algorithms and kinetic data structures assume separable edge weight functions. In contrast, we propose novel algorithms to find TSMST for large ST networks by accounting for both separable and non-separable piecewise linear edge weight functions. The algorithms are based on the ordering of edges in edge-order-intervals and intersection points of edge weight functions.
Coding objects related to Catalan numbers
Venue: arXiv cs.DM 2010
Year: 2010

A coding method using binary sequences is presented for different computation problems related to Catalan numbers. This method proves in a very easy way the equivalence of these problems.
Current Conveyor Based Multifunction Filter
Venue: arXiv cs.OH 2010
Year: 2010

The paper presents a current conveyor based multifunction filter. The proposed circuit can be realized as low pass, high pass, band pass and elliptical notch filter. The circuit employs two balanced output current conveyors, four resistors and two grounded capacitors, ideal for integration. It has only one output terminal and the number of input terminals may be used. Further, there is no requirement for component matching in the circuit. The parameter resonance frequency (ω_0) and bandwidth (ω_0 /Q) enjoy orthogonal tuning. The complementary metal oxide semiconductor (CMOS) realization of the current conveyor is given for the simulation of the proposed circuit. A HSPICE simulation of circuit is also studied for the verification of theoretical results. The non-ideal analysis of CCII is also studied.
A Secure Hash Function MD-192 With Modified Message Expansion
Venue: arXiv cs.CR 2010
Year: 2010

Cryptographic hash functions play a central role in cryptography. Hash functions were introduced in cryptology to provide message integrity and authentication. MD5, SHA1 and RIPEMD are among the most commonly used message digest algorithm. Recently proposed attacks on well known and widely used hash functions motivate a design of new stronger hash function. In this paper a new approach is presented that produces 192 bit message digest and uses a modified message expansion mechanism which generates more bit difference in each working variable to make the algorithm more secure. This hash function is collision resistant and assures a good compression and preimage resistance.
Design and Performance Analysis of Unified Reconfigurable Data Integrity Unit for Mobile Terminals
Venue: arXiv cs.CR 2010
Year: 2010

Security has become one of the major issue in mobile services. In the development of recent mobile devices like Software Defined Radio (SDR) secure method of software downloading is found necessary for reconfiguration. Hash functions are the important security primitives used for authentication and data integrity. In this paper, VLSI architecture for implementation of integrity unit in SDR is proposed. The proposed architecture is reconfigurable in the sense it operates in two different modes: SHA-192 and MD-5.Due to applied design technique the proposed architecture achieves multi-mode operation, which keeps the allocated area resource at minimized level. The proposed architecture also achieves highspeed performance with pipelined designed structure. Comparison with related hash function implementation have been done in terms of operating frequency, allocated-area and area-delay product. The proposed Integrity Unity can be integrated in security systems for implementation of network for wireless protocol, with special needs of integrity in data transmission.
Roberts' Theorem with Neutrality: A Social Welfare Ordering Approach
Venue: arXiv cs.GT 2010
Year: 2010

We consider dominant strategy implementation in private values settings, when agents have multi-dimensional types, the set of alternatives is finite, monetary transfers are allowed, and agents have quasi-linear utilities. We show that any implementable and neutral social choice function must be a weighted welfare maximizer if the type space of every agent is an $m$-dimensional open interval, where $m$ is the number of alternatives. When the type space of every agent is unrestricted, Roberts' theorem with neutrality \cite{Roberts79} becomes a corollary to our result. Our proof technique uses a {\em social welfare ordering} approach, commonly used in aggregation literature in social choice theory. We also prove the general (affine maximizer) version of Roberts' theorem for unrestricted type spaces of agents using this approach.
Generalised Rabin(1) synthesis
Venue: arXiv cs.LO 2010
Year: 2010

We present a novel method for the synthesis of finite state systems that is a generalisation of the generalised reactivity(1) synthesis approach by Piterman, Pnueli and Sa'ar. In particular, we describe an efficient method to synthesize systems from linear-time temporal logic specifications for which all assumptions and guarantees have a Rabin index of one. We show how to build a parity game with at most five colours that captures all solutions to the synthesis problem from such a specification. This parity game has a structure that is amenable to symbolic implementations. We furthermore show that the results obtained are in some sense tight, i.e., that there does not exist a similar synthesis method for assumptions and specifications of higher Rabin index, unless P=NP.
Vulnerability of MRD-Code-based Universal Secure Network Coding against Stronger Eavesdroppers
Venue: arXiv cs.IT 2010
Year: 2010

Silva et al. proposed a universal secure network coding scheme based on MRD codes, which can be applied to any underlying network code. This paper considers a stronger eavesdropping model where the eavesdroppers possess the ability to re-select the tapping links during the transmission. We give a proof for the impossibility of attaining universal security against such adversaries using Silva et al.'s code for all choices of code parameters, even with restricted number of tapped links. We also consider the cases with restricted tapping duration and derive some conditions for this code to be secure.
A Survey of Naïve Bayes Machine Learning approach in Text Document Classification
Venue: arXiv cs.LG 2010
Year: 2010

Text Document classification aims in associating one or more predefined categories based on the likelihood suggested by the training set of labeled documents. Many machine learning algorithms play a vital role in training the system with predefined categories among which Naïve Bayes has some intriguing facts that it is simple, easy to implement and draws better accuracy in large datasets in spite of the naïve dependence. The importance of Naïve Bayes Machine learning approach has felt hence the study has been taken up for text document classification and the statistical event models available. This survey the various feature selection methods has been discussed and compared along with the metrics related to text document classification.
Secure Multicast Key Distribution for Mobile Ad Hoc Networks
Venue: arXiv cs.CR 2010
Year: 2010

Many emerging applications in mobile adhoc networks involve group-oriented communication. Multicast is an efficient way of supporting group oriented applications, mainly in mobile environment with limited bandwidth and limited power. For using such applications in an adversarial environment as military, it is necessary to provide secure multicast communication. Key management is the fundamental challenge in designing secure multicast communications. In many multicast interactions, new member can join and current members can leave at any time and existing members must communicate securely using multicast key distribution within constrained energy for mobile adhoc networks. This has to overcome the challenging element of "1 affects n" problem which is due to high dynamicity of groups. Thus this paper shows the specific challenges towards multicast key management protocols for securing multicast key distribution in mobile ad hoc networks, and present relevant multicast key management protocols in mobile ad hoc networks. A comparison is done against some pertinent performance criteria.
Wireless IP Telephony
Venue: arXiv cs.OH 2010
Year: 2010

The convergence of traditional telecommunications and the Internet is creating new network-based service delivery opportunities for telecommunications companies carriers, service providers, and network equipment providers. Voice over Wireless IP is one of the most exciting new developments emerging within the telephony market. It is set to revolutionize the delivery of mobile voice Services and provide exciting new opportunities for operators and service providers alike. This survey discusses principal of Wireless IP Telephony.
Decoding Complexity of Irregular LDGM-LDPC Codes Over the BISOM Channels
Venue: arXiv cs.IT 2010
Year: 2010

An irregular LDGM-LDPC code is studied as a sub-code of an LDPC code with some randomly \emph{punctured} output-bits. It is shown that the LDGM-LDPC codes achieve rates arbitrarily close to the channel-capacity of the binary-input symmetric-output memoryless (BISOM) channel with bounded \emph{complexity}. The measure of complexity is the average-degree (per information-bit) of the check-nodes for the factor-graph of the code. A lower-bound on the average degree of the check-nodes of the irregular LDGM-LDPC codes is obtained. The bound does not depend on the decoder used at the receiver. The stability condition for decoding the irregular LDGM-LDPC codes over the binary-erasure channel (BEC) under iterative-decoding with message-passing is described.
Structure-Aware Stochastic Control for Transmission Scheduling
Venue: arXiv cs.LG 2010
Year: 2010

In this paper, we consider the problem of real-time transmission scheduling over time-varying channels. We first formulate the transmission scheduling problem as a Markov decision process (MDP) and systematically unravel the structural properties (e.g. concavity in the state-value function and monotonicity in the optimal scheduling policy) exhibited by the optimal solutions. We then propose an online learning algorithm which preserves these structural properties and achieves -optimal solutions for an arbitrarily small . The advantages of the proposed online method are that: (i) it does not require a priori knowledge of the traffic arrival and channel statistics and (ii) it adaptively approximates the state-value functions using piece-wise linear functions and has low storage and computation complexity. We also extend the proposed low-complexity online learning solution to the prioritized data transmission. The simulation results demonstrate that the proposed method achieves significantly better utility (or delay)-energy trade-offs when comparing to existing state-of-art online optimization methods.
Making Web Annotations Persistent over Time
Venue: arXiv cs.DL 2010
Year: 2010

As Digital Libraries (DL) become more aligned with the web architecture, their functional components need to be fundamentally rethought in terms of URIs and HTTP. Annotation, a core scholarly activity enabled by many DL solutions, exhibits a clearly unacceptable characteristic when existing models are applied to the web: due to the representations of web resources changing over time, an annotation made about a web resource today may no longer be relevant to the representation that is served from that same resource tomorrow. We assume the existence of archived versions of resources, and combine the temporal features of the emerging Open Annotation data model with the capability offered by the Memento framework that allows seamless navigation from the URI of a resource to archived versions of that resource, and arrive at a solution that provides guarantees regarding the persistence of web annotations over time. More specifically, we provide theoretical solutions and proof-of-concept experimental evaluations for two problems: reconstructing an existing annotation so that the correct archived version is displayed for all resources involved in the annotation, and retrieving all annotations that involve a given archived version of a web resource.
Efficient Queue-based CSMA with Collisions
Venue: arXiv cs.IT 2010
Year: 2010

Recently there has been considerable interest in the design of efficient carrier sense multiple access(CSMA) protocol for wireless network. The basic assumption underlying recent results is availability of perfect carrier sense information. This allows for design of continuous time algorithm under which collisions are avoided. The primary purpose of this note is to show how these results can be extended in the case when carrier sense information may not be perfect, or equivalently delayed. Specifically, an adaptation of algorithm in Rajagopalan, Shah, Shin (2009) is presented here for time slotted setup with carrier sense information available only at the end of the time slot. To establish its throughput optimality, in additon to method developed in Rajagopalan, Shah, Shin (2009), understanding properties of stationary distribution of a certain non-reversible Markov chain as well as bound on its mixing time is essential. This note presents these key results. A longer version of this note will provide detailed account of how this gets incorporated with methods of Rajagopalan, Shah, Shin (2009) to provide the positive recurrence of underlying network Markov process. In addition, these results will help design optimal rate control in conjunction with CSMA in presence of collision building upon the method of Jiang, Shah, Shin, Walrand (2009).
On the monotonicity, log-concavity and tight bounds of the generalized Marcum and Nuttall Q-functions
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we present a comprehensive study of the monotonicity and log-concavity of the generalized Marcum and Nuttall Q-functions. More precisely, a simple probabilistic method is firstly given to prove the monotonicity of these two functions. Then, the log-concavity of the generalized Marcum Q-function and its deformations is established with respect to each of the three parameters. Since the Nuttall Q-function has similar probabilistic interpretations as the generalized Marcum Q-function, we deduce the log-concavity of the Nuttall Q-function. By exploiting the log-concavity of these two functions, we propose new tight lower and upper bounds for the generalized Marcum and Nuttall Q-functions. Our proposed bounds are much tighter than the existing bounds in the literature in most of the cases. The relative errors of our proposed bounds converge to 0 as b tends to infinity. The numerical results show that the absolute relative errors of the proposed bounds are less than 5% in most of the cases. The proposed bounds can be effectively applied to the outage probability analysis of interference-limited systems such as cognitive radio and wireless sensor network, in the study of error performance of various wireless communication systems operating over fading channels and extracting the log-likelihood ratio for differential phase-shift keying (DPSK) signals.
Approaching optimality for solving SDD systems
Venue: arXiv cs.DS 2010
Year: 2010

We present an algorithm that on input of an $n$-vertex $m$-edge weighted graph $G$ and a value $k$, produces an {\em incremental sparsifier} $\hat{G}$ with $n-1 + m/k$ edges, such that the condition number of $G$ with $\hat{G}$ is bounded above by $\tilde{O}(k\log^2 n)$, with probability $1-p$. The algorithm runs in time $$\tilde{O}((m \log{n} + n\log^2{n})\log(1/p)).$$ As a result, we obtain an algorithm that on input of an $n\times n$ symmetric diagonally dominant matrix $A$ with $m$ non-zero entries and a vector $b$, computes a vector ${x}$ satisfying $||{x}-A^{+}b||_A<ε||A^{+}b||_A $, in expected time $$\tilde{O}(m\log^2{n}\log(1/ε)).$$ The solver is based on repeated applications of the incremental sparsifier that produces a chain of graphs which is then used as input to a recursive preconditioned Chebyshev iteration.
Agreement Maintenance Based on Schema and Ontology Change in P2P Environment
Venue: arXiv cs.AI 2010
Year: 2010

This paper is concern about developing a semantic agreement maintenance method based on semantic distance by calculating the change of local schema or ontology. This approach is important in dynamic and autonomous environment, in which the current approach assumed that agreement or mapping in static environment. The contribution of this research is to develop a framework based on semantic agreement maintenance approach for P2P environment. This framework based on two level hybrid P2P model architecture, which consist of two peer type: (1) super peer that use to register and manage the other peers, and (2) simple peer, as a simple peer, it exports and shares its contents with others. This research develop a model to maintain the semantic agreement in P2P environment, so the current approach which does not have the mechanism to know the change, since it assumed that ontology and local schema are in the static condition, and it is different in dynamic condition. The main issues are how to calculate the change of local schema or common ontology and the calculation result is used to determine which algorithm in maintaining the agreement. The experiment on the job matching domain in Indonesia have been done to show how far the performance of the approach. From the experiment, the main result are (i) the more change so the F-measure value tend to be decreased, (ii) there is no significant different in F-measure value for various modification type (add, delete, rename), and (iii) the correct choice of algorithm would improve the F-measure value.
Private Information Disclosure from Web Searches. (The case of Google Web History)
Venue: arXiv cs.CR 2010
Year: 2010

As the amount of personal information stored at remote service providers increases, so does the danger of data theft. When connections to remote services are made in the clear and authenticated sessions are kept using HTTP cookies, data theft becomes extremely easy to achieve. In this paper, we study the architecture of the world's largest service provider, i.e., Google. First, with the exception of a few services that can only be accessed over HTTPS (e.g., Gmail), we find that many Google services are still vulnerable to simple session hijacking. Next, we present the Historiographer, a novel attack that reconstructs the web search history of Google users, i.e., Google's Web History, even though such a service is supposedly protected from session hijacking by a stricter access control policy. The Historiographer uses a reconstruction technique inferring search history from the personalized suggestions fed by the Google search engine. We validate our technique through experiments conducted over real network traffic and discuss possible countermeasures. Our attacks are general and not only specific to Google, and highlight privacy concerns of mixed architectures using both secure and insecure connections.