OpenRaiser/Intern-Atlas huggingface dataset:
Acdmcp: An adaptive and completely distributed multi-hop clustering protocol for wireless sensor networks
Venue: arXiv cs.NI 2010
Year: 2010

Clustering is a very popular network structuring technique which mainly addresses the issue of scalability in large scale Wireless Sensor Networks. Additionally, it has been shown to improve the energy efficiency and prolong the life of the network. The suggested protocols mostly base their clustering criteria on some grouping attribute(s) of the nodes. One important attribute that is largely ignored by most of the existing multi-hop clustering protocols is the reliability of the communication links between the nodes. In this paper, we suggest an adaptive and completely distributed multi-hop clustering protocol that incorporates different notions of reliability of the communication links, among other things, into a composite metric and uses it in all phases of the clustering process. The joining criteria for the nodes, which lie at one hop from the elected cluster heads, to a particular cluster not only consider the reliability of their communication link with their cluster head but also other important attributes. The nodes that lie outside the communication range of cluster heads become cluster members transitively through existing cluster members utilizing the end-to-end notion of link reliability, between the nodes and the cluster heads, along with other important attributes. Similarly, inter-cluster communication paths are selected using a set of criteria that includes the end-to-end communication link reliability with the sink node along with other important node and network attributes. We believe that incorporating link reliability in all phases of clustering process results in an efficient multi-hop communication hierarchy that has the potential of bringing down the total communication costs in the network.
Mobile Information Collectors' Trajectory Data Warehouse Design
Venue: arXiv cs.DB 2010
Year: 2010

To analyze complex phenomena which involve moving objects, Trajectory Data Warehouse (TDW) seems to be an answer for many recent decision problems related to various professions (physicians, commercial representatives, transporters, ecologists ...) concerned with mobility. This work aims to make trajectories as a first class concept in the trajectory data conceptual model and to design a TDW, in which data resulting from mobile information collectors' trajectory are gathered. These data will be analyzed, according to trajectory characteristics, for decision making purposes, such as new products commercialization, new commerce implementation, etc.
Automatable Evaluation Method Oriented toward Behaviour Believability for Video Games
Venue: arXiv cs.AI 2010
Year: 2010

Classic evaluation methods of believable agents are time-consuming because they involve many human to judge agents. They are well suited to validate work on new believable behaviours models. However, during the implementation, numerous experiments can help to improve agents' believability. We propose a method which aim at assessing how much an agent's behaviour looks like humans' behaviours. By representing behaviours with vectors, we can store data computed for humans and then evaluate as many agents as needed without further need of humans. We present a test experiment which shows that even a simple evaluation following our method can reveal differences between quite believable agents and humans. This method seems promising although, as shown in our experiment, results' analysis can be difficult.
Optimizing Selective Search in Chess
Venue: arXiv cs.AI 2010
Year: 2010

In this paper we introduce a novel method for automatically tuning the search parameters of a chess program using genetic algorithms. Our results show that a large set of parameter values can be learned automatically, such that the resulting performance is comparable with that of manually tuned parameters of top tournament-playing chess programs.
Encoded packet-Assisted Rescue Approach to Reliable Unicast in Wireless Networks
Venue: arXiv cs.IT 2010
Year: 2010

Recently, network coding technique has emerged as a promising approach that supports reliable transmission over wireless loss channels. In existing protocols where users have no interest in considering the encoded packets they had in coding or decoding operations, this rule is expensive and inefficient. This paper studies the impact of encoded packets in the reliable unicast network coding via some theoretical analysis. Using our approach, receivers do not only store the encoded packets they overheard, but also report these information to their neighbors, such that users enable to take account of encoded packets in their coding decisions as well as decoding operations. Moreover, we propose a redistribution algorithm to maximize the coding opportunities, which achieves better retransmission efficiency. Finally, theoretical analysis and simulation results for a wheel network illustrate the improvement in retransmissions efficiency due to the encoded packets.
Weighted Attribute Fusion Model for Face Recognition
Venue: arXiv cs.CV 2010
Year: 2010

Recognizing a face based on its attributes is an easy task for a human to perform as it is a cognitive process. In recent years, Face Recognition is achieved with different kinds of facial features which were used separately or in a combined manner. Currently, Feature fusion methods and parallel methods are the facial features used and performed by integrating multiple feature sets at different levels. However, this integration and the combinational methods do not guarantee better result. Hence to achieve better results, the feature fusion model with multiple weighted facial attribute set is selected. For this feature model, face images from predefined data set has been taken from Olivetti Research Laboratory (ORL) and applied on different methods like Principal Component Analysis (PCA) based Eigen feature extraction technique, Discrete Cosine Transformation (DCT) based feature extraction technique, Histogram Based Feature Extraction technique and Simple Intensity based features. The extracted feature set obtained from these methods were compared and tested for accuracy. In this work we have developed a model which will use the above set of feature extraction techniques with different levels of weights to attain better accuracy. The results show that the selection of optimum weight for a particular feature will lead to improvement in recognition rate.
Empirical study and modeling of human behaviour dynamics of comments on Blog posts
Venue: arXiv cs.SI 2010
Year: 2010

On-line communities offer a great opportunity to investigate human dynamics, because much information about individuals is registered in databases. In this paper, based on data statistics of online comments on Blog posts, we first present an empirical study of a comment arrival-time interval distribution. We find that people interested in some subjects gradually disappear and the interval distribution is a power law. According to this feature, we propose a model with gradually decaying interest. We give a rigorous analysis on the model by non-homogeneous Poisson processes and obtain an analytic expression of the interval distribution. Our analysis indicates that the time interval between two consecutive events follows the power-law distribution with a tunable exponent, which can be controlled by the model parameters and is in interval (1,+{\infty}). The analytical result agrees with the empirical results well, obeying an approximately power-law form. Our model provides a theoretical basis for human behaviour dynamics of comments on Blog posts.
A Note on the Membrane Computer
Venue: arXiv cs.OH 2010
Year: 2010

Inspired by the emergent membrane computing (P Systems) concepts, some efforts are carried out introducing simulation models, some are software oriented, and others are hardware, yet all are applied with the current vision of the conventional computers, based on "Von Neumann architecture", which is a sequential design in its essence. We think that these models will need "as a consequent result" to a new architecture exposing a true parallel design, in this paper; we try to investigate and introduce a global view for how it would be like to have such architecture. The main goal is to point out to this direction broadly, suggesting that it might be useful considering some aspects, like the need for a new definition of an operating system and its programs, which will eventually lead to a higher scope: the membrane computer.
Nonlinear Vector Filtering for Impulsive Noise Removal from Color Images
Venue: arXiv cs.CV 2010
Year: 2010

In this paper, a comprehensive survey of 48 filters for impulsive noise removal from color images is presented. The filters are formulated using a uniform notation and categorized into 8 families. The performance of these filters is compared on a large set of images that cover a variety of domains using three effectiveness and one efficiency criteria. In order to ensure a fair efficiency comparison, a fast and accurate approximation for the inverse cosine function is introduced. In addition, commonly used distance measures (Minkowski, angular, and directional-distance) are analyzed and evaluated. Finally, suggestions are provided on how to choose a filter given certain requirements.
Efficient Collaborative Application Monitoring Scheme for Mobile Networks
Venue: arXiv cs.MA 2010
Year: 2010

New operating systems for mobile devices allow their users to download millions of applications created by various individual programmers, some of which may be malicious or flawed. In order to detect that an application is malicious, monitoring its operation in a real environment for a significant period of time is often required. Mobile devices have limited computation and power resources and thus are limited in their monitoring capabilities. In this paper we propose an efficient collaborative monitoring scheme that harnesses the collective resources of many mobile devices, "vaccinating" them against potentially unsafe applications. We suggest a new local information flooding algorithm called "TTL Probabilistic Propagation" (TPP). The algorithm periodically monitors one or more application and reports its conclusions to a small number of other mobile devices, who then propagate this information onwards. The algorithm is analyzed, and is shown to outperform existing state of the art information propagation algorithms, in terms of convergence time as well as network overhead. The maximal "load" of the algorithm (the fastest arrival rate of new suspicious applications, that can still guarantee complete monitoring), is analytically calculated and shown to be significantly superior compared to any non-collaborative approach. Finally, we show both analytically and experimentally using real world network data that implementing the proposed algorithm significantly reduces the number of infected mobile devices. In addition, we analytically prove that the algorithm is tolerant to several types of Byzantine attacks where some adversarial agents may generate false information, or abuse the algorithm in other ways.
Coarse Network Coding: A Simple Relay Strategy to Resolve Interference
Venue: arXiv cs.IT 2010
Year: 2010

Reminiscent of the parity function in network coding for the butterfly network, it is shown that forwarding an even/odd indicator bit for a scalar quantization of a relay observation recovers 1 bit of information at the two destinations in a noiseless interference channel where interference is treated as noise. Based on this observation, a coding strategy is proposed to improve the rate of both users at the same time using a relay node in an interference channel. In this strategy, the relay observes a linear combination of the two source signals, and broadcasts a common message to the two destinations over a shared out-of-band link of rate R0 bits per channel use. The relay message consists of the bin index of a structured binning scheme obtained from a 2^R0-way partition of the squared lattice in the complex plane. We show that such scalar quantization-binning relay strategy asymptotically achieves the cut-set bound in an interference channel with a common out-of-band relay link of limited rate, improving the sum rate by two bits for every bit relayed, asymptotically at high signal to noise ratios (SNR) and when interference is treated as noise. We then use low-density parity-check (LDPC) codes along with bit-interleaved coded-modulation (BICM) as a practical coding scheme for the proposed strategy. We consider matched and mismatched scenarios, depending on whether the input alphabet of the interference signal is known or unknown to the decoder, respectively. For the matched scenario, we show the proposed strategy results in significant gains in SNR. For the mismatched scenario, we show that the proposed strategy results in rate improvements that, without the relay, cannot be achieved by merely increasing transmit powers. Finally, we use generalized mutual information analysis to characterize the theoretical performance of the mismatched scenario and validate our simulation results.
Wideband Spectrum Sensing at Sub-Nyquist Rates
Venue: arXiv cs.AR 2010
Year: 2010

We present a mixed analog-digital spectrum sensing method that is especially suited to the typical wideband setting of cognitive radio (CR). The advantages of our system with respect to current architectures are threefold. First, our analog front-end is fixed and does not involve scanning hardware. Second, both the analog-to-digital conversion (ADC) and the digital signal processing (DSP) rates are substantially below Nyquist. Finally, the sensing resources are shared with the reception path of the CR, so that the lowrate streaming samples can be used for communication purposes of the device, besides the sensing functionality they provide. Combining these advantages leads to a real time map of the spectrum with minimal use of mobile resources. Our approach is based on the modulated wideband converter (MWC) system, which samples sparse wideband inputs at sub-Nyquist rates. We report on results of hardware experiments, conducted on an MWC prototype circuit, which affirm fast and accurate spectrum sensing in parallel to CR communication.
LinBox founding scope allocation, parallel building blocks, and separate compilation
Venue: arXiv cs.SE 2010
Year: 2010

To maximize efficiency in time and space, allocations and deallocations, in the exact linear algebra library \linbox, must always occur in the founding scope. This provides a simple lightweight allocation model. We present this model and its usage for the rebinding of matrices between different coefficient domains. We also present automatic tools to speed-up the compilation of template libraries and a software abstraction layer for the introduction of transparent parallelism at the algorithmic level.
A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set
Venue: arXiv cs.DS 2010
Year: 2010

An independent dominating set D of a graph G = (V,E) is a subset of vertices such that every vertex in V \ D has at least one neighbor in D and D is an independent set, i.e. no two vertices of D are adjacent in G. Finding a minimum independent dominating set in a graph is an NP-hard problem. Whereas it is hard to cope with this problem using parameterized and approximation algorithms, there is a simple exact O(1.4423^n)-time algorithm solving the problem by enumerating all maximal independent sets. In this paper we improve the latter result, providing the first non trivial algorithm computing a minimum independent dominating set of a graph in time O(1.3569^n). Furthermore, we give a lower bound of Ω(1.3247^n) on the worst-case running time of this algorithm, showing that the running time analysis is almost tight.
A Practical Approach to Managing Spreadsheet Risk in a Global Business
Venue: arXiv cs.SE 2010
Year: 2010

Spreadsheets are used extensively within today's organisations. Although spreadsheets have many benefits, they can also present a significant risk exposure, requiring appropriate management. Protiviti has worked with a number of organisations, ranging in size up to huge multi-nationals, to help them build appropriate spreadsheet governance frameworks, including the design and implementation of policies, minimum design standards, control processes, training and awareness programmes and the consideration and implementation of spreadsheet management tools. This paper presents a case-study explaining the practical and pragmatic approach that was recently taken to control spreadsheet risk at one of Protiviti's clients - a global energy firm.
Transforming Critical Spreadsheets into Web Applications at Zurich Financial
Venue: arXiv cs.SE 2010
Year: 2010

In the insurance industry, spreadsheets have emerged as an invaluable tool to for product pricing, because it is relatively straightforward to create and maintain complex pricing models using Excel. In fact, Excel is often preferred to "hard-code" whenever there are frequent changes to the calculations and business logic which under-pin the pricing of an insurance product. However, problems arise as soon as spreadsheets are deployed to end-users: version control, security of intellectual property, and ensuring correct usage are obvious issues; frequently, integration with other systems is also a requirement. Zurich Financial Services Group is a leading financial services provider; several possible solutions to these problems have been evaluated, and EASA has been selected as the preferred technology. Other spreadsheet collaboration approaches which were considered include Excel Services, and/or custom-built software; however, EASA has provided clear benefits over these strategies.
Spreadsheet Refactoring
Venue: arXiv cs.SE 2010
Year: 2010

Refactoring is a change made to the internal structure of software to make it easier to understand and cheaper to modify without changing its observable behaviour. A database refactoring is a small change to the database schema which improves its design without changing its semantics. This paper presents example 'spreadsheet refactorings', derived from the above and taking into account the unique characteristics of spreadsheet formulas and VBA code. The techniques are constrained by the tightly coupled data and code in spreadsheets.
Applications of semidefinite programming to coding theory
Venue: arXiv cs.IT 2010
Year: 2010

We survey recent generalizations and improvements of the linear programming method that involve semidefinite programming. A general framework using group representations and tools from graph theory is provided.
Pan-private Algorithms: When Memory Does Not Help
Venue: arXiv cs.CR 2010
Year: 2010

Consider updates arriving online in which the $t$th input is $(i_t,d_t)$, where $i_t$'s are thought of as IDs of users. Informally, a randomized function $f$ is {\em differentially private} with respect to the IDs if the probability distribution induced by $f$ is not much different from that induced by it on an input in which occurrences of an ID $j$ are replaced with some other ID $k$ Recently, this notion was extended to {\em pan-privacy} where the computation of $f$ retains differential privacy, even if the internal memory of the algorithm is exposed to the adversary (say by a malicious break-in or by fiat by the government). This is a strong notion of privacy, and surprisingly, for basic counting tasks such as distinct counts, heavy hitters and others, Dwork et al~\cite{dwork-pan} present pan-private algorithms with reasonable accuracy. The pan-private algorithms are nontrivial, and rely on sampling. We reexamine these basic counting tasks and show improved bounds. In particular, we estimate the distinct count $\Dt$ to within $(1\pm \eps)\Dt \pm O(\polylog m)$, where $m$ is the number of elements in the universe. This uses suitably noisy statistics on sketches known in the streaming literature. We also present the first known lower bounds for pan-privacy with respect to a single intrusion. Our lower bounds show that, even if allowed to work with unbounded memory, pan-private algorithms for distinct counts can not be significantly more accurate than our algorithms. Our lower bound uses noisy decoding. For heavy hitter counts, we present a pan private streaming algorithm that is accurate to within $O(k)$ in worst case; previously known bound for this problem is arbitrarily worse. An interesting aspect of our pan-private algorithms is that, they deliberately use very small (polylogarithmic) space and tend to be streaming algorithms, even though using more space is not forbidden.
Statistical Behavior of Embeddedness and Communities of Overlapping Cliques in Online Social Networks
Venue: arXiv cs.SI 2010
Year: 2010

Degree distribution of nodes, especially a power law degree distribution, has been regarded as one of the most significant structural characteristics of social and information networks. Node degree, however, only discloses the first-order structure of a network. Higher-order structures such as the edge embeddedness and the size of communities may play more important roles in many online social networks. In this paper, we provide empirical evidence on the existence of rich higherorder structural characteristics in online social networks, develop mathematical models to interpret and model these characteristics, and discuss their various applications in practice. In particular, 1) We show that the embeddedness distribution of social links in many social networks has interesting and rich behavior that cannot be captured by well-known network models. We also provide empirical results showing a clear correlation between the embeddedness distribution and the average number of messages communicated between pairs of social network nodes. 2) We formally prove that random k-tree, a recent model for complex networks, has a power law embeddedness distribution, and show empirically that the random k-tree model can be used to capture the rich behavior of higherorder structures we observed in real-world social networks. 3) Going beyond the embeddedness, we show that a variant of the random k-tree model can be used to capture the power law distribution of the size of communities of overlapping cliques discovered recently.
Refinement Types for Logical Frameworks and Their Interpretation as Proof Irrelevance
Venue: arXiv cs.PL 2010
Year: 2010

Refinement types sharpen systems of simple and dependent types by offering expressive means to more precisely classify well-typed terms. We present a system of refinement types for LF in the style of recent formulations where only canonical forms are well-typed. Both the usual LF rules and the rules for type refinements are bidirectional, leading to a straightforward proof of decidability of typechecking even in the presence of intersection types. Because we insist on canonical forms, structural rules for subtyping can now be derived rather than being assumed as primitive. We illustrate the expressive power of our system with examples and validate its design by demonstrating a precise correspondence with traditional presentations of subtyping. Proof irrelevance provides a mechanism for selectively hiding the identities of terms in type theories. We show that LF refinement types can be interpreted as predicates using proof irrelevance, establishing a uniform relationship between two previously studied concepts in type theory. The interpretation and its correctness proof are surprisingly complex, lending support to the claim that refinement types are a fundamental construct rather than just a convenient surface syntax for certain uses of proof irrelevance.