OpenRaiser/Intern-Atlas huggingface dataset:
Passively Mobile Communicating Logarithmic Space Machines
Venue: arXiv cs.DC 2010
Year: 2010

We propose a new theoretical model for passively mobile Wireless Sensor Networks. We call it the PALOMA model, standing for PAssively mobile LOgarithmic space MAchines. The main modification w.r.t. the Population Protocol model is that agents now, instead of being automata, are Turing Machines whose memory is logarithmic in the population size n. Note that the new model is still easily implementable with current technology. We focus on complete communication graphs. We define the complexity class PLM, consisting of all symmetric predicates on input assignments that are stably computable by the PALOMA model. We assume that the agents are initially identical. Surprisingly, it turns out that the PALOMA model can assign unique consecutive ids to the agents and inform them of the population size! This allows us to give a direct simulation of a Deterministic Turing Machine of O(nlogn) space, thus, establishing that any symmetric predicate in SPACE(nlogn) also belongs to PLM. We next prove that the PALOMA model can simulate the Community Protocol model, thus, improving the previous lower bound to all symmetric predicates in NSPACE(nlogn). Going one step further, we generalize the simulation of the deterministic TM to prove that the PALOMA model can simulate a Nondeterministic TM of O(nlogn) space. Although providing the same lower bound, the important remark here is that the bound is now obtained in a direct manner, in the sense that it does not depend on the simulation of a TM by a Pointer Machine. Finally, by showing that a Nondeterministic TM of O(nlogn) space decides any language stably computable by the PALOMA model, we end up with an exact characterization for PLM: it is precisely the class of all symmetric predicates in NSPACE(nlogn).
Comparative Performance Investigations of different scenarios for 802.15.4 WPAN
Venue: arXiv cs.NI 2010
Year: 2010

This paper investigates the performance of WPAN based on various topological scenarios like: cluster, star and ring. The comparative results have been reported for the performance metrics like: Throughput, Traffic sent, Traffic received and Packets dropped. Cluster topology is best in comparison with star and ring topologies as it has been shown that the throughput in case of cluster topology (79.887 kbits / sec) as compared to star (31.815 kbits / sec) and ring (1.179 kbits / sec).
Simultaneous Bayesian inference of motion velocity fields and probabilistic models in successive video-frames described by spatio-temporal MRFs
Venue: arXiv cs.CV 2010
Year: 2010

We numerically investigate a mean-field Bayesian approach with the assistance of the Markov chain Monte Carlo method to estimate motion velocity fields and probabilistic models simultaneously in consecutive digital images described by spatio-temporal Markov random fields. Preliminary to construction of our procedure, we find that mean-field variables in the iteration diverge due to improper normalization factor of regularization terms appearing in the posterior. To avoid this difficulty, we rescale the regularization term by introducing a scaling factor and optimizing it by means of minimization of the mean-square error. We confirm that the optimal scaling factor stabilizes the mean-field iterative process of the motion velocity estimation. We next attempt to estimate the optimal values of hyper-parameters including the regularization term, which define our probabilistic model macroscopically, by using the Boltzmann-machine type learning algorithm based on gradient descent of marginal likelihood (type-II likelihood) with respect to the hyper-parameters. In our framework, one can estimate both the probabilistic model (hyper-parameters) and motion velocity fields simultaneously. We find that our motion estimation is much better than the result obtained by Zhang and Hanouer (1995) in which the hyper-parameters are set to some ad-hoc values without any theoretical justification.
An Object-Oriented Metamodel for Bunge-Wand-Weber Ontology
Venue: arXiv cs.SE 2010
Year: 2010

A UML based metamodel for Bunge-Wand-Weber (BWW) ontology is presented. BWW ontology is a generic framework for analysis and conceptualization of real world objects. It includes categories that can be applied to analyze and classify objects found in an information system. In the context of BWW ontology, the metamodel is a representation of the ontological categories and relationships among them. An objective behind developing an object-oriented metamodel has been to model BWW ontology in terms of widely used notions in software development. The main contributions of this paper are a classification for ontological categories, a description template, and representations through UML and typed based models.
Approximating the minimum directed tree cover
Venue: arXiv cs.DS 2010
Year: 2010

Given a directed graph $G$ with non negative cost on the arcs, a directed tree cover of $G$ is a rooted directed tree such that either head or tail (or both of them) of every arc in $G$ is touched by $T$. The minimum directed tree cover problem (DTCP) is to find a directed tree cover of minimum cost. The problem is known to be $NP$-hard. In this paper, we show that the weighted Set Cover Problem (SCP) is a special case of DTCP. Hence, one can expect at best to approximate DTCP with the same ratio as for SCP. We show that this expectation can be satisfied in some way by designing a purely combinatorial approximation algorithm for the DTCP and proving that the approximation ratio of the algorithm is $\max\{2, \ln(D^+)\}$ with $D^+$ is the maximum outgoing degree of the nodes in $G$.
Multi-Criteria Evaluation of Partitioning Schemes for Real-Time Systems
Venue: arXiv cs.OS 2010
Year: 2010

In this paper we study the partitioning approach for multiprocessor real-time scheduling. This approach seems to be the easiest since, once the partitioning of the task set has been done, the problem reduces to well understood uniprocessor issues. Meanwhile, there is no optimal and polynomial solution to partition tasks on processors. In this paper we analyze partitioning algorithms from several points of view such that for a given task set and specific constraints (processor number, task set type, etc.) we should be able to identify the best heuristic and the best schedulability test. We also analyze the influence of the heuristics on the performance of the uniprocessor tests and the impact of a specific task order on the schedulability. A study on performance difference between Fixed Priority schedulers and EDF in the case of partitioning scheduling is also considered.
Improved Inapproximability For Submodular Maximization
Venue: arXiv cs.CC 2010
Year: 2010

We show that it is Unique Games-hard to approximate the maximum of a submodular function to within a factor 0.695, and that it is Unique Games-hard to approximate the maximum of a symmetric submodular function to within a factor 0.739. These results slightly improve previous results by Feige, Mirrokni and Vondrák (FOCS 2007) who showed that these problems are NP-hard to approximate to within $3/4 + ε \approx 0.750$ and $5/6 + ε \approx 0.833$, respectively.
Interference Cancellation at the Relay for Multi-User Wireless Cooperative Networks
Venue: arXiv cs.IT 2010
Year: 2010

We study multi-user transmission and detection schemes for a multi-access relay network (MARN) with linear constraints at all nodes. In a $(J, J_a, R_a, M)$ MARN, $J$ sources, each equipped with $J_a$ antennas, communicate to one $M$-antenna destination through one $R_a$-antenna relay. A new protocol called IC-Relay-TDMA is proposed which takes two phases. During the first phase, symbols of different sources are transmitted concurrently to the relay. At the relay, interference cancellation (IC) techniques, previously proposed for systems with direct transmission, are applied to decouple the information of different sources without decoding. During the second phase, symbols of different sources are forwarded to the destination in a time division multi-access (TDMA) fashion. At the destination, the maximum-likelihood (ML) decoding is performed source-by-source. The protocol of IC-Relay-TDMA requires the number of relay antennas no less than the number of sources, i.e., $R_a\ge J$. Through outage analysis, the achievable diversity gain of the proposed scheme is shown to be $\min\{J_a(R_a-J+1),R_aM\}$. When {\small$M\le J_a\left(1-\frac{J-1}{R_a}\right)$}, the proposed scheme achieves the maximum interference-free (int-free) diversity gain $R_aM$. Since concurrent transmission is allowed during the first phase, compared to full TDMA transmission, the proposed scheme achieves the same diversity, but with a higher symbol rate.
Where is Randomness Needed to Break the Square-Root Bottleneck?
Venue: arXiv cs.IT 2010
Year: 2010

As shown by Tropp, 2008, for the concatenation of two orthonormal bases (ONBs), breaking the square-root bottleneck in compressed sensing does not require randomization over all the positions of the nonzero entries of the sparse coefficient vector. Rather the positions corresponding to one of the two ONBs can be chosen arbitrarily. The two-ONB structure is, however, restrictive and does not reveal the property that is responsible for allowing to break the bottleneck with reduced randomness. For general dictionaries we show that if a sub-dictionary with small enough coherence and large enough cardinality can be isolated, the bottleneck can be broken under the same probabilistic model on the sparse coefficient vector as in the two-ONB case.
Price Trackers Inspired by Immune Memory
Venue: arXiv cs.AI 2010
Year: 2010

In this paper we outline initial concepts for an immune inspired algorithm to evaluate price time series data. The proposed solution evolves a short term pool of trackers dynamically through a process of proliferation and mutation, with each member attempting to map to trends in price movements. Successful trackers feed into a long term memory pool that can generalise across repeating trend patterns. Tests are performed to examine the algorithm's ability to successfully identify trends in a small data set. The influence of the long term memory pool is then examined. We find the algorithm is able to identify price trends presented successfully and efficiently.
STORM - A Novel Information Fusion and Cluster Interpretation Technique
Venue: arXiv cs.AI 2010
Year: 2010

Analysis of data without labels is commonly subject to scrutiny by unsupervised machine learning techniques. Such techniques provide more meaningful representations, useful for better understanding of a problem at hand, than by looking only at the data itself. Although abundant expert knowledge exists in many areas where unlabelled data is examined, such knowledge is rarely incorporated into automatic analysis. Incorporation of expert knowledge is frequently a matter of combining multiple data sources from disparate hypothetical spaces. In cases where such spaces belong to different data types, this task becomes even more challenging. In this paper we present a novel immune-inspired method that enables the fusion of such disparate types of data for a specific set of problems. We show that our method provides a better visual understanding of one hypothetical space with the help of data from another hypothetical space. We believe that our model has implications for the field of exploratory data analysis and knowledge discovery.
Displacement Calculus
Venue: arXiv cs.CL 2010
Year: 2010

The Lambek calculus provides a foundation for categorial grammar in the form of a logic of concatenation. But natural language is characterized by dependencies which may also be discontinuous. In this paper we introduce the displacement calculus, a generalization of Lambek calculus, which preserves its good proof-theoretic properties while embracing discontinuiity and subsuming it. We illustrate linguistic applications and prove Cut-elimination, the subformula property, and decidability
New Results on Secret Key Establishment over a Pair of Broadcast Channels
Venue: arXiv cs.IT 2010
Year: 2010

The problem of Secret Key Establishment (SKE) over a pair of independent Discrete Memoryless Broadcast Channels (DMBCs) has already been studied in \cite{Ah10}, where we provided lower and upper bounds on the secret-key capacity. In this paper, we study the above setup under each of the following two cases: (1) the DMBCs have secrecy potential, and (2) the DMBCs are stochastically degraded with independent channels. In the former case, we propose a simple SKE protocol based on a novel technique, called Interactive Channel Coding (ICC), and prove that it achieves the lower bound. In the latter case, we give a simplified expression for the lower bound and prove a single-letter capacity formula under the condition that one of the legitimate parties sends only i.i.d. variables.
Browser-Based Covert Data Exfiltration
Venue: arXiv cs.CR 2010
Year: 2010

Current best practices heavily control user permissions on network systems. This effectively mitigates many insider threats regarding the collection and exfiltration of data. Many methods of covert communication involve crafting custom packets, typically requiring both the necessary software and elevated privileges on the system. By exploiting the functionality of a browser, covert channels for data exfiltration may be created without additional software or user privileges. This paper explores novel methods of using a browser's JavaScript engine to exfiltrate documents over the Domain Name System (DNS) protocol without sending less covert Hypertext Transfer Protocol (HTTP) requests.
Optimal Data Placement on Networks With Constant Number of Clients
Venue: arXiv cs.DS 2010
Year: 2010

We introduce optimal algorithms for the problems of data placement (DP) and page placement (PP) in networks with a constant number of clients each of which has limited storage availability and issues requests for data objects. The objective for both problems is to efficiently utilize each client's storage (deciding where to place replicas of objects) so that the total incurred access and installation cost over all clients is minimized. In the PP problem an extra constraint on the maximum number of clients served by a single client must be satisfied. Our algorithms solve both problems optimally when all objects have uniform lengths. When objects lengths are non-uniform we also find the optimal solution, albeit a small, asymptotically tight violation of each client's storage size by $ε$lmax where lmax is the maximum length of the objects and $ε$ some arbitrarily small positive constant. We make no assumption on the underlying topology of the network (metric, ultrametric etc.), thus obtaining the first non-trivial results for non-metric data placement problems.
Throughput-Delay-Reliability Tradeoff with ARQ in Wireless Ad Hoc Networks
Venue: arXiv cs.IT 2010
Year: 2010

Delay-reliability (D-R), and throughput-delay-reliability (T-D-R) tradeoffs in an ad hoc network are derived for single hop and multi-hop transmission with automatic repeat request (ARQ) on each hop. The delay constraint is modeled by assuming that each packet is allowed at most $D$ retransmissions end-to-end, and the reliability is defined as the probability that the packet is successfully decoded in at most $D$ retransmissions. The throughput of the ad hoc network is characterized by the transmission capacity, which is defined to be the maximum allowable density of transmitting nodes satisfying a per transmitter receiver rate, and an outage probability constraint, multiplied with the rate of transmission and the success probability. Given an end-to-end retransmission constraint of $D$, the optimal allocation of the number of retransmissions allowed at each hop is derived that maximizes a lower bound on the transmission capacity. Optimizing over the number of hops, single hop transmission is shown to be optimal for maximizing a lower bound on the transmission capacity in the sparse network regime.
A Survey on Network Codes for Distributed Storage
Venue: arXiv cs.IT 2010
Year: 2010

Distributed storage systems often introduce redundancy to increase reliability. When coding is used, the repair problem arises: if a node storing encoded information fails, in order to maintain the same level of reliability we need to create encoded information at a new node. This amounts to a partial recovery of the code, whereas conventional erasure coding focuses on the complete recovery of the information from a subset of encoded packets. The consideration of the repair network traffic gives rise to new design challenges. Recently, network coding techniques have been instrumental in addressing these challenges, establishing that maintenance bandwidth can be reduced by orders of magnitude compared to standard erasure codes. This paper provides an overview of the research results on this topic.
Combination of Subtractive Clustering and Radial Basis Function in Speaker Identification
Venue: arXiv cs.MM 2010
Year: 2010

Speaker identification is the process of determining which registered speaker provides a given utterance. Speaker identification required to make a claim on the identity of speaker from the Ns trained speaker in its user database. In this study, we propose the combination of clustering algorithm and the classification technique - subtractive and Radial Basis Function (RBF). The proposed technique is chosen because RBF is a simpler network structures and faster learning algorithm. RBF finds the input to output map using the local approximators which will combine the linear of the approximators and cause the linear combiner have few weights. Besides that, RBF neural network model using subtractive clustering algorithm for selecting the hidden node centers, which can achieve faster training speed. In the meantime, the RBF network was trained with a regularization term so as to minimize the variances of the nodes in the hidden layer and perform more accu-rate prediction.
A Metrics Based Model for Understandability Quantification
Venue: arXiv cs.SE 2010
Year: 2010

Software developers and maintainers need to read and understand source programs and other software artifacts. The increase in size and complexity of software drastically affects several quality attributes, especially understandability and maintainability. False interpretation often leads to ambiguities, misunderstanding and hence to faulty development results. Despite the fact that software understandability is vital and one of the most significant components of the software development process, it is poorly managed. This is mainly due to the lack of its proper management and control. The paper highlights the importance of understandability in general and as a factor of software testability. Two major contributions are made in the paper. A relation between testability factors and object oriented characteristics has been established as a first contribution. In second contribution, a model has been proposed for estimating understandability of object oriented software using design metrics. In addition, the proposed model has been validated using experimental try-out.
Audio enabled information extraction system for cricket and hockey domains
Venue: arXiv cs.IR 2010
Year: 2010

The proposed system aims at the retrieval of the summarized information from the documents collected from web based search engine as per the user query related to cricket and hockey domain. The system is designed in a manner that it takes the voice commands as keywords for search. The parts of speech in the query are extracted using the natural language extractor for English. Based on the keywords the search is categorized into 2 types: - 1.Concept wise - information retrieved to the query is retrieved based on the keywords and the concept words related to it. The retrieved information is summarized using the probabilistic approach and weighted means algorithm.2.Keyword search - extracts the result relevant to the query from the highly ranked document retrieved from the search by the search engine. The relevant search results are retrieved and then keywords are used for summarizing part. During summarization it follows the weighted and probabilistic approaches in order to identify the data comparable to the keywords extracted. The extracted information is then refined repeatedly through the aggregation process to reduce redundancy. Finally the resultant data is submitted to the user in the form of audio output.
Optimal Beamforming in Interference Networks with Perfect Local Channel Information
Venue: arXiv cs.IT 2010
Year: 2010

We consider settings in which T multi-antenna transmitters and K single-antenna receivers concurrently utilize the available communication resources. Each transmitter sends useful information only to its intended receivers and can degrade the performance of unintended systems. Here, we assume the performance measures associated with each receiver are monotonic with the received power gains. In general, the systems' joint operation is desired to be Pareto optimal. However, designing Pareto optimal resource allocation schemes is known to be difficult. In order to reduce the complexity of achieving efficient operating points, we show that it is sufficient to consider rank-1 transmit covariance matrices and propose a framework for determining the efficient beamforming vectors. These beamforming vectors are thereby also parameterized by T(K-1) real-valued parameters each between zero and one. The framework is based on analyzing each transmitter's power gain-region which is composed of all jointly achievable power gains at the receivers. The efficient beamforming vectors are on a specific boundary section of the power gain-region, and in certain scenarios it is shown that it is necessary to perform additional power allocation on the beamforming vectors. Two examples which include broadcast and multicast data as well as a cognitive radio application scenario illustrate the results.
Clustering of Content Supporting Computer Mediated Courseware Development
Venue: arXiv cs.OH 2010
Year: 2010

Computer Mediated Courseware (CMC) has been developed so far for individual courses considering single or multiple text books. A group of courseware can be developed by using multiple text books and in this case, it is a requirement to cluster the contents of different books to form a generalized clustered content. No work has been found to develop courseware applying generalized clustered content. We have proposed a clustering of content supporting computer mediated courseware development based on data mining techniques to construct a hierarchical general structure of a group of courseware combining the individual structure of a set of books. The clustering will help the courseware developer to dynamically allocate contents to develop different courses using a group of books. The authors have applied this methodology for different level of courses on database. The methodology is generalized and can be applied to any other courses.
Wireless sensors networks MAC protocols analysis
Venue: arXiv cs.NI 2010
Year: 2010

Wireless sensors networks performance are strictly related to the medium access mechanism. An effective one, require non-conventional paradigms for protocol design due to several constraints. An adequate equilibrium between communication improvement and data processing capabilities must be accomplished. To achieve low power operation, several MAC protocols already proposed for WSN. The aim of this paper is to survey and to analyze the most energy efficient MAC protocol in order to categorize them and to compare their performances. Furthermore we have implemented some of WSN MAC protocol under OMNET++ with the purpose to evaluate their performances.