OpenRaiser/Intern-Atlas huggingface dataset:
Information Spreading in Dynamic Networks
Venue: arXiv cs.DC 2011
Year: 2011

We study the fundamental problem of information spreading (also known as gossip) in dynamic networks. In gossip, or more generally, $k$-gossip, there are $k$ pieces of information (or tokens) that are initially present in some nodes and the problem is to disseminate the $k$ tokens to all nodes. The goal is to accomplish the task in as few rounds of distributed computation as possible. The problem is especially challenging in dynamic networks where the network topology can change from round to round and can be controlled by an on-line adversary. The focus of this paper is on the power of token-forwarding algorithms, which do not manipulate tokens in any way other than storing and forwarding them. We first consider a worst-case adversarial model first studied by Kuhn, Lynch, and Oshman~\cite{kuhn+lo:dynamic} in which the communication links for each round are chosen by an adversary, and nodes do not know who their neighbors for the current round are before they broadcast their messages. Our main result is an $Ω(nk/\log n)$ lower bound on the number of rounds needed for any deterministic token-forwarding algorithm to solve $k$-gossip. This resolves an open problem raised in~\cite{kuhn+lo:dynamic}, improving their lower bound of $Ω(n \log k)$, and matching their upper bound of $O(nk)$ to within a logarithmic factor. We next show that token-forwarding algorithms can achieve subquadratic time in the offline version of the problem where the adversary has to commit all the topology changes in advance at the beginning of the computation, and present two polynomial-time offline token-forwarding algorithms. Our results are a step towards understanding the power and limitation of token-forwarding algorithms in dynamic networks.
Label Ranking with Abstention: Predicting Partial Orders by Thresholding Probability Distributions (Extended Abstract)
Venue: arXiv cs.AI 2011
Year: 2011

We consider an extension of the setting of label ranking, in which the learner is allowed to make predictions in the form of partial instead of total orders. Predictions of that kind are interpreted as a partial abstention: If the learner is not sufficiently certain regarding the relative order of two alternatives, it may abstain from this decision and instead declare these alternatives as being incomparable. We propose a new method for learning to predict partial orders that improves on an existing approach, both theoretically and empirically. Our method is based on the idea of thresholding the probabilities of pairwise preferences between labels as induced by a predicted (parameterized) probability distribution on the set of all rankings.
Analytical Evaluation of Fractional Frequency Reuse for Heterogeneous Cellular Networks
Venue: arXiv cs.IT 2011
Year: 2011

Interference management techniques are critical to the performance of heterogeneous cellular networks, which will have dense and overlapping coverage areas, and experience high levels of interference. Fractional frequency reuse (FFR) is an attractive interference management technique due to its low complexity and overhead, and significant coverage improvement for low-percentile (cell-edge) users. Instead of relying on system simulations based on deterministic access point locations, this paper instead proposes an analytical model for evaluating Strict FFR and Soft Frequency Reuse (SFR) deployments based on the spatial Poisson point process. Our results both capture the non-uniformity of heterogeneous deployments and produce tractable expressions which can be used for system design with Strict FFR and SFR. We observe that the use of Strict FFR bands reserved for the users of each tier with the lowest average SINR provides the highest gains in terms of coverage and rate, while the use of SFR allows for more efficient use of shared spectrum between the tiers, while still mitigating much of the interference. Additionally, in the context of multi-tier networks with closed access in some tiers, the proposed framework shows the impact of cross-tier interference on closed access FFR, and informs the selection of key FFR parameters in open access.
Scaling algorithms for approximate and exact maximum weight matching
Venue: arXiv cs.DS 2011
Year: 2011

The {\em maximum cardinality} and {\em maximum weight matching} problems can be solved in time $\tilde{O}(m\sqrt{n})$, a bound that has resisted improvement despite decades of research. (Here $m$ and $n$ are the number of edges and vertices.) In this article we demonstrate that this "$m\sqrt{n}$ barrier" is extremely fragile, in the following sense. For any $ε>0$, we give an algorithm that computes a $(1-ε)$-approximate maximum weight matching in $O(mε^{-1}\logε^{-1})$ time, that is, optimal {\em linear time} for any fixed $ε$. Our algorithm is dramatically simpler than the best exact maximum weight matching algorithms on general graphs and should be appealing in all applications that can tolerate a negligible relative error. Our second contribution is a new {\em exact} maximum weight matching algorithm for integer-weighted bipartite graphs that runs in time $O(m\sqrt{n}\log N)$. This improves on the $O(Nm\sqrt{n})$-time and $O(m\sqrt{n}\log(nN))$-time algorithms known since the mid 1980s, for $1\ll \log N \ll \log n$. Here $N$ is the maximum integer edge weight.
Using Quasigroups for Generating Pseudorandom Numbers
Venue: arXiv cs.CR 2011
Year: 2011

This paper presents an algorithm for generating pseudorandom numbers using quasigroups. Random numbers have several applications in the area of secure communication. The proposed algorithm uses a matrix of size n x n which is pre-generated and stored. The quality of random numbers generated is compared with other pseudorandom number generator using Marsaglia's Diehard battery of tests.
The Dimension of Spline Spaces with Highest Order Smoothness over Hierarchical T-meshes
Venue: arXiv cs.CG 2011
Year: 2011

This paper discusses the dimension of spline spaces with highest order smoothness over hierarchical T-meshes over certain type of hierarchical T-meshes. The major step is to set up a bijection between the spline space with highest order smoothness over a hierarchical T-mesh and a univariate spline space whose definition depends on the l-edges of the extended T-mesh. We decompose the univariate spline space into direct sums in the sense of isomorphism using the theory of the short exact sequence in homological algebra. According to the decomposition of the univariate spline space, the dimension formula of the spline space with highest order smoothness over certain type of hierarchical T-mesh is presented. A set of basis functions of the spline space is also constructed.
A multi-feature tracking algorithm enabling adaptation to context variations
Venue: arXiv cs.CV 2011
Year: 2011

We propose in this paper a tracking algorithm which is able to adapt itself to different scene contexts. A feature pool is used to compute the matching score between two detected objects. This feature pool includes 2D, 3D displacement distances, 2D sizes, color histogram, histogram of oriented gradient (HOG), color covariance and dominant color. An offline learning process is proposed to search for useful features and to estimate their weights for each context. In the online tracking process, a temporal window is defined to establish the links between the detected objects. This enables to find the object trajectories even if the objects are misdetected in some frames. A trajectory filter is proposed to remove noisy trajectories. Experimentation on different contexts is shown. The proposed tracker has been tested in videos belonging to three public datasets and to the Caretaker European project. The experimental results prove the effect of the proposed feature weight learning, and the robustness of the proposed tracker compared to some methods in the state of the art. The contributions of our approach over the state of the art trackers are: (i) a robust tracking algorithm based on a feature pool, (ii) a supervised learning scheme to learn feature weights for each context, (iii) a new method to quantify the reliability of HOG descriptor, (iv) a combination of color covariance and dominant color features with spatial pyramid distance to manage the case of object occlusion.
Multiuser Cellular Network
Venue: arXiv cs.NI 2011
Year: 2011

Modern radio communication is faced with a problem about how to distribute restricted frequency to users in a certain space. Since our task is to minimize the number of repeaters, a natural idea is enlarging coverage area. However, coverage has restrictions. First, service area has to be divided economically as repeater's coverage is limited. In this paper, our fundamental method is to adopt seamless cellular network division. Second, underlying physics content in frequency distribution problem is interference between two close frequencies. Consequently, we choose a proper frequency width of 0.1MHz and a relevantly reliable setting to apply one frequency several times. We make a few general assumptions to simplify real situation. For instance, immobile users yield to homogenous distribution; repeaters can receive and transmit information in any given frequency in duplex operation; coverage is mainly decided by antenna height. Two models are built up to solve 1000 users and 10000 users situations respectively. In order to utilize restricted frequency and PL code, three stratified terms - "cell", "cluster", "group" - are introduced to describe the models in detail. Under our analysis, 91 repeaters for 1000 users and 469 repeaters for 10000 users are viable results. Next, to test stability and sensitivity of models, we give total consideration to the variation of sum of users, antenna height, and frequency width and service radius. Evaluation about models is offered qualitatively. Finally, two practical cases are put forward to gain a partial knowledge of mountainous area. The brief method in dealing with mountains is classified discussion in two ideal conditions. It may provide some constructive suggestions to avoid shortcomings or take proper measures in similar locations.
On an Approach to the Design of a Logical Model of Innovation Project Data
Venue: arXiv cs.OH 2011
Year: 2011

Questions concerning the development of a logical model of innovation project data, as well as those concerning the design of information systems for decision-making support in the management of innovation projects, are discussed.
Improved hardness results for unique shortest vector problem
Venue: arXiv cs.CC 2011
Year: 2011

We give several improvements on the known hardness of the unique shortest vector problem. - We give a deterministic reduction from the shortest vector problem to the unique shortest vector problem. As a byproduct, we get deterministic NP-hardness for unique shortest vector problem in the $\ell_\infty$ norm. - We give a randomized reduction from SAT to uSVP_{1+1/poly(n)}. This shows that uSVP_{1+1/poly(n)} is NP-hard under randomized reductions. - We show that if GapSVP_γ\in coNP (or coAM) then uSVP_{\sqrtγ} \in coNP (coAM respectively). This simplifies previously known uSVP_{n^{1/4}} \in coAM proof by Cai \cite{Cai98} to uSVP_{(n/\log n)^{1/4}} \in coAM, and additionally generalizes it to uSVP_{n^{1/4}} \in coNP. - We give a deterministic reduction from search-uSVP_γto the decision-uSVP_{γ/2}. We also show that the decision-uSVP is {\bf NP}-hard for randomized reductions, which does not follow from Kumar-Sivakumar \cite{KS01}.
Unicode in Domain-Specific Programming Languages for Modeling & Simulation: ScalaTion as a Case Study
Venue: arXiv cs.PL 2011
Year: 2011

As recent programming languages provide improved conciseness and flexibility of syntax, the development of embedded or internal Domain-Specific Languages has increased. The field of Modeling and Simulation has had a long history of innovation in programming languages (e.g. Simula-67, GPSS). Much effort has gone into the development of Simulation Programming Languages. The ScalaTion project is working to develop an embedded or internal Domain-Specific Language for Modeling and Simulation which could streamline language innovation in this domain. One of its goals is to make the code concise, readable, and in a form familiar to experts in the domain. In some cases the code looks very similar to textbook formulas. To enhance readability by domain experts, a version of ScalaTion is provided that heavily utilizes Unicode. This paper discusses the development of the ScalaTion DSL and the underlying features of Scala that make this possible. It then provides an overview of ScalaTion highlighting some uses of Unicode. Statistical analysis capabilities needed for Modeling and Simulation are presented in some detail. The notation developed is clear and concise which should lead to improved usability and extendibility.
A Formally Specified Program Logic for Higher-Order Procedural Variables and non-local Jumps
Venue: arXiv cs.LO 2011
Year: 2011

We formally specified a program logic for higher-order procedural variables and non-local jumps with Ott and Twelf. Moreover, the dependent type systems and the translation are both executable specifications thanks to Twelf's logic programming engine. In particular, relying on Filinski's encoding of shift/reset using callcc/throw and a global meta-continuation (simulated in state passing style), we have mechanically checked the correctness of a few examples (all source files are available on request).
Combined Base Station Association and Power Control in Multi-channel Cellular Networks
Venue: arXiv cs.NI 2011
Year: 2011

A combined base station association and power control problem is studied for the uplink of multichannel multicell cellular networks, in which each channel is used by exactly one cell (i.e., base station). A distributed association and power update algorithm is proposed and shown to converge to a Nash equilibrium of a noncooperative game. We consider network models with discrete mobiles (yielding an atomic congestion game), as well as a continuum of mobiles (yielding a population game). We find that the equilibria need not be Pareto efficient, nor need they be system optimal. To address the lack of system optimality, we propose pricing mechanisms. It is shown that these mechanisms can be implemented in a distributed fashion.
Future Robotics Database Management System along with Cloud TPS
Venue: arXiv cs.DB 2011
Year: 2011

This paper deals with memory management issues of robotics. In our proposal we break one of the major issues in creating humanoid. . Database issue is the complicated thing in robotics schema design here in our proposal we suggest new concept called NOSQL database for the effective data retrieval, so that the humanoid robots will get the massive thinking ability in searching each items using chained instructions. For query transactions in robotics we need an effective consistency transactions so by using latest technology called CloudTPS which guarantees full ACID properties so that the robot can make their queries using multi-item transactions through this we obtain data consistency in data retrievals. In addition we included map reduce concepts it can splits the job to the respective workers so that it can process the data in a parallel way.
Ontology-Based Emergency Management System in a Social Cloud
Venue: arXiv cs.SI 2011
Year: 2011

The need for Emergency Management continually grows as the population and exposure to catastrophic failures increase. The ability to offer appropriate services at these emergency situations can be tackled through group communication mechanisms. The entities involved in the group communication include people, organizations, events, locations and essential services. Cloud computing is a "as a service" style of computing that enables on-demand network access to a shared pool of resources. So this work focuses on proposing a social cloud constituting group communication entities using an open source platform, Eucalyptus. The services are exposed as semantic web services, since the availability of machine-readable metadata (Ontology) will enable the access of these services more intelligently. The objective of this paper is to propose an Ontology-based Emergency Management System in a social cloud and demonstrate the same using emergency healthcare domain.
Compact Weighted Class Association Rule Mining using Information Gain
Venue: arXiv cs.DB 2011
Year: 2011

Weighted association rule mining reflects semantic significance of item by considering its weight. Classification constructs the classifier and predicts the new data instance. This paper proposes compact weighted class association rule mining method, which applies weighted association rule mining in the classification and constructs an efficient weighted associative classifier. This proposed associative classification algorithm chooses one non class informative attribute from dataset and all the weighted class association rules are generated based on that attribute. The weight of the item is considered as one of the parameter in generating the weighted class association rules. This proposed algorithm calculates the weight using the HITS model. Experimental results show that the proposed system generates less number of high quality rules which improves the classification accuracy.
A comparative study of aggregate TCP retransmission rates
Venue: arXiv cs.NI 2011
Year: 2011

Segment retransmissions are an essential tool in assuring reliable end-to-end communication in the Internet. Their crucial role in TCP design and operation has been studied extensively, in particular with respect to identifying non-conformant, buggy, or underperforming behaviour. However, TCP segment retransmissions are often overlooked when examining and analyzing large traffic traces. In fact, some have come to believe that retransmissions are a rare oddity, characteristically associated with faulty network paths, which, typically, tend to disappear as networking technology advances and link capacities grow. We find that this may be far from the reality experienced by TCP flows. We quantify aggregate TCP segment retransmission rates using publicly available network traces from six passive monitoring points attached to the egress gateways at large sites. In virtually half of the traces examined we observed aggregate TCP retransmission rates exceeding 1%, and of these, about half again had retransmission rates exceeding 2%. Even for sites with low utilization and high capacity gateway links, retransmission rates of 1%, and sometimes higher, were not uncommon. Our results complement, extend and bring up to date partial and incomplete results in previous work, and show that TCP retransmissions continue to constitute a non-negligible percentage of the overall traffic, despite significant advances across the board in telecommunications technologies and network protocols. The results presented are pertinent to end-to-end protocol designers and evaluators as they provide a range of "realistic" scenarios under which, and a "marker" against which, simulation studies can be configured and calibrated, and future protocols evaluated.
Exact Safety Verification of Hybrid Systems Using Sums-Of-Squares Representation
Venue: arXiv cs.SE 2011
Year: 2011

In this paper we discuss how to generate inductive invariants for safety verification of hybrid systems. A hybrid symbolic-numeric method is presented to compute inequality inductive invariants of the given systems. A numerical invariant of the given system can be obtained by solving a parameterized polynomial optimization problem via sum-of-squares (SOS) relaxation. And a method based on Gauss-Newton refinement and rational vector recovery is deployed to obtain the invariants with rational coefficients, which exactly satisfy the conditions of invariants. Several examples are given to illustrate our algorithm.
Performance Analysis of Bidirectional Relay Selection with Imperfect Channel State Information
Venue: arXiv cs.NI 2011
Year: 2011

In this paper, we investigate the performance of bidirectional relay selection using amplify-and-forward protocol with imperfect channel state information, i.e., delay effect and channel estimation error. The asymptotic expression of end-to-end SER in high SNR regime is derived in a closed form, which indicates that the delay effect causes the loss of both coding gain and diversity order, while the channel estimation error merely affects the coding gain. Finally, analytical results are verified by Monte-Carlo simulations.
Improvement of BM3D Algorithm and Employment to Satellite and CFA Images Denoising
Venue: arXiv cs.CV 2011
Year: 2011

This paper proposes a new procedure in order to improve the performance of block matching and 3-D filtering (BM3D) image denoising algorithm. It is demonstrated that it is possible to achieve a better performance than that of BM3D algorithm in a variety of noise levels. This method changes BM3D algorithm parameter values according to noise level, removes prefiltering, which is used in high noise level; therefore Peak Signal-to-Noise Ratio (PSNR) and visual quality get improved, and BM3D complexities and processing time are reduced. This improved BM3D algorithm is extended and used to denoise satellite and color filter array (CFA) images. Output results show that the performance has upgraded in comparison with current methods of denoising satellite and CFA images. In this regard this algorithm is compared with Adaptive PCA algorithm, that has led to superior performance for denoising CFA images, on the subject of PSNR and visual quality. Also the processing time has decreased significantly.
A Real-Time Database QoS-aware Service Selection Protocol for MANET
Venue: arXiv cs.DB 2011
Year: 2011

The real-time database service selection depends typically to the system stability in order to handle the time-constrained transactions within their deadline. However, applying the real-time database system in the mobile ad hoc networks requires considering the mobile nodes limited capacities. In this paper, we propose cross-layer service selection which combines performance metrics measured in the real-time database system to those used by the routing protocol in order to make the best selection decision. It ensures both timeliness and energy efficiency by avoiding low-power and busy service provider node. A multicast packet is used in order to reduce the transmission cost and network load when sending the same packet to multiple service providers. In this paper, we evaluate the performance of our proposed protocol. Simulation results, using the Network Simulator NS2, improve that the protocol decreases the deadline miss ratio of packets, increases the service availability and reduces the service response time.
Performance Evaluation and Impact of Weighting Factors on an Energy and Delay Aware Dynamic Source Routing Protocol
Venue: arXiv cs.NI 2011
Year: 2011

Typical applications of the mobile ad-hoc network, MANET, are in disaster recovery operations which have to respect time constraint needs. Since MANET is affected by limited resources such as power constraints, it is a challenge to respect the deadline of a real-time data. This paper proposes the Energy and Delay aware based on Dynamic Source Routing protocol, ED-DSR. ED-DSR efficiently utilizes the network resources such as the intermediate mobile nodes energy and load. It ensures both timeliness and energy efficiency by avoiding low-power and overloaded intermediate mobile nodes. Through simulations, we compare our proposed routing protocol with the basic routing protocol Dynamic Source Routing, DSR. Weighting factors are introduced to improve the route selection. Simulation results, using the NS-2 simulator, show that the proposed protocol prolongs the network lifetime (up to 66%), increases the volume of packets delivered while meeting the data flows real-time constraints and shortens the endto- end delay.