OpenRaiser/Intern-Atlas huggingface dataset:
Optimal topological simplification of discrete functions on surfaces
Venue: arXiv cs.CG 2010
Year: 2010

We solve the problem of minimizing the number of critical points among all functions on a surface within a prescribed distance δ from a given input function. The result is achieved by establishing a connection between discrete Morse theory and persistent homology. Our method completely removes homological noise with persistence less than 2δ, constructively proving the tightness of a lower bound on the number of critical points given by the stability theorem of persistent homology in dimension two for any input function. We also show that an optimal solution can be computed in linear time after persistence pairs have been computed.
A framework to model real-time databases
Venue: arXiv cs.DB 2010
Year: 2010

Real-time databases deal with time-constrained data and time-constrained transactions. The design of this kind of databases requires the introduction of new concepts to support both data structures and the dynamic behaviour of the database. In this paper, we give an overview about different aspects of real-time databases and we clarify requirements of their modelling. Then, we present a framework for real-time database design and describe its fundamental operations. A case study demonstrates the validity of the structural model and illustrates SQL queries and Java code generated from the classes of the model
Distributed scientific communication in the European information society: Some cases of "Mode 2" fields of research
Venue: arXiv cs.IR 2010
Year: 2010

Can self-organization of scientific communication be specified by using literature-based indicators? In this study, we explore this question by applying entropy measures to typical "Mode-2" fields of knowledge production. We hypothesized these scientific systems to be developing from a self-organization of the interaction between cognitive and institutional levels: European subsidized research programs aim at creating an institutional network, while a cognitive reorganization is continuously ongoing at the scientific field level. The results indicate that the European system develops towards a stable level of distribution of cited references and title-words among the European member states. We suggested that this distribution could be a property of the emerging European system. In order to measure to degree of specialization with respect to the respective distributions of countries, cited references and title words, the mutual information among the three frequency distributions was calculated. The so-called transmission values informed us that the European system shows increasing levels of differentiation.
Multi-Armed Bandit Mechanisms for Multi-Slot Sponsored Search Auctions
Venue: arXiv cs.GT 2010
Year: 2010

In pay-per click sponsored search auctions which are currently extensively used by search engines, the auction for a keyword involves a certain number of advertisers (say k) competing for available slots (say m) to display their ads. This auction is typically conducted for a number of rounds (say T). There are click probabilities mu_ij associated with each agent-slot pairs. The goal of the search engine is to maximize social welfare of the advertisers, that is, the sum of values of the advertisers. The search engine does not know the true values advertisers have for a click to their respective ads and also does not know the click probabilities mu_ij s. A key problem for the search engine therefore is to learn these click probabilities during the T rounds of the auction and also to ensure that the auction mechanism is truthful. Mechanisms for addressing such learning and incentives issues have recently been introduced and are aptly referred to as multi-armed-bandit (MAB) mechanisms. When m = 1, characterizations for truthful MAB mechanisms are available in the literature and it has been shown that the regret for such mechanisms will be O(T^{2/3}). In this paper, we seek to derive a characterization in the realistic but non-trivial general case when m > 1 and obtain several interesting results.
Cascade and Triangular Source Coding with Side Information at the First Two Nodes
Venue: arXiv cs.IT 2010
Year: 2010

We consider the cascade and triangular rate-distortion problem where side information is known to the source encoder and to the first user but not to the second user. We characterize the rate-distortion region for these problems. For the quadratic Gaussian case, we show that it is sufficient to consider jointly Gaussian distributions, a fact that leads to an explicit solution.
Assessing Cognitive Load on Web Search Tasks
Venue: arXiv cs.HC 2010
Year: 2010

Assessing cognitive load on web search is useful for characterizing search system features and search tasks with respect to their demands on the searcher's mental effort. It is also helpful for examining how individual differences among searchers (e.g. cognitive abilities) affect the search process. We examined cognitive load from the perspective of primary and secondary task performance. A controlled web search study was conducted with 48 participants. The primary task performance components were found to be significantly related to both the objective and the subjective task difficulty. However, the relationship between objective and subjective task difficulty and the secondary task performance measures was weaker than expected. The results indicate that the dual-task approach needs to be used with caution.
Internet voting protocol based on implicit data security
Venue: arXiv cs.CR 2010
Year: 2010

This paper presents a new protocol for Internet voting based on implicit data security. This protocol allows recasting of votes, which permits a change of mind by voters either during the time window over which polling is open or during a shorter period over which recasting is permitted. The security of votes depends on multiple servers such that each vote is divided into partitions and these partitions are distributed among the servers, all of which need to be brought together to reconstruct the votes. Such a protocol has potential applications in bargaining and electronic commerce.
On the Secure DoF of the Single-Antenna MAC
Venue: arXiv cs.IT 2010
Year: 2010

A new achievability rate region for the secure discrete memoryless Multiple-Access-Channel (MAC) is presented. Thereafter, a novel secure coding scheme is proposed to achieve a positive Secure Degrees-of-Freedom (S-DoF) in the single-antenna MAC. This scheme converts the single-antenna system into a multiple-dimension system with fractional dimensions. The achievability scheme is based on the alignment of signals into a small sub-space at the eavesdropper, and the simultaneous separation of the signals at the intended receiver. Tools from the field of Diophantine Approximation in number theory are used to analyze the probability of error in the coding scheme.
Fountain Codes with Varying Probability Distributions
Venue: arXiv cs.IT 2010
Year: 2010

Fountain codes are rateless erasure-correcting codes, i.e., an essentially infinite stream of encoded packets can be generated from a finite set of data packets. Several fountain codes have been proposed recently to minimize overhead, many of which involve modifications of the Luby transform (LT) code. These fountain codes, like the LT code, have the implicit assumption that the probability distribution is fixed throughout the encoding process. In this paper, we will use the theory of posets to show that this assumption is unnecessary, and by dropping it, we can achieve overhead reduction by as much as 64% lower than LT codes. We also present the fundamental theory of probability distribution designs for fountain codes with non-constant probability distributions that minimize overhead.
OMI4papps: Optimisation, Modelling and Implementation for Highly Parallel Applications
Venue: arXiv cs.PF 2010
Year: 2010

This article reports on first results of the KONWIHR-II project OMI4papps at the Leibniz Supercomputing Centre (LRZ). The first part describes Apex-MAP, a tunable synthetic benchmark designed to simulate the performance of typical scientific applications. Apex-MAP mimics common memory access patterns and different computational intensity of scientific codes. An approach for modelling LRZ's application mix is given whichh makes use of performance counter measurements of real applications running on "HLRB II", an SGI Altix system based on 9728 Intel Montecito dual-cores. The second part will show how the Apex-MAP benchmark could be used to simulate the performance of two mathematical kernels frequently used in scientific applications: a dense matrix-matrix multiplication and a sparse matrix-vector multiplication. The performance of both kernels has been intensively studied on x86 cores and hardware accelerators. We will compare the predicted performance with measured data to validate our Apex-MAP approach.
RapidMind: Portability across Architectures and its Limitations
Venue: arXiv cs.PF 2010
Year: 2010

Recently, hybrid architectures using accelerators like GPGPUs or the Cell processor have gained much interest in the HPC community. The RapidMind Multi-Core Development Platform is a programming environment that allows generating code which is able to seamlessly run on hardware accelerators like GPUs or the Cell processor and multicore CPUs both from AMD and Intel. This paper describes the ports of three mathematical kernels to RapidMind which are chosen as synthetic benchmarks and representatives of scientific codes. Performance of these kernels has been measured on various RapidMind backends (cuda, cell and x86) and compared to other hardware-specific implementations (using CUDA, Cell SDK and Intel MKL). The results give an insight in the degree of portability of RapidMind code and code performance across different architectures.
Geometrical interpretation and improvements of the Blahut-Arimoto's algorithm
Venue: arXiv cs.IT 2010
Year: 2010

The paper first recalls the Blahut Arimoto algorithm for computing the capacity of arbitrary discrete memoryless channels, as an example of an iterative algorithm working with probability density estimates. Then, a geometrical interpretation of this algorithm based on projections onto linear and exponential families of probabilities is provided. Finally, this understanding allows also to propose to write the Blahut-Arimoto algorithm, as a true proximal point algorithm. it is shown that the corresponding version has an improved convergence rate, compared to the initial algorithm, as well as in comparison with other improved versions.
Multiprocessor Scheduling For Tasks With Priority Using GA
Venue: arXiv cs.NE 2010
Year: 2010

Multiprocessors have emerged as a powerful computing means for running realtime applications, especially where a uniprocessor system would not be sufficient enough to execute all the tasks. The high performance and reliability of multiprocessors have made them a powerful computing resource. Such computing environment requires an efficient algorithm to determine when and on which processor a given task should execute. In multiprocessor systems, an efficient scheduling of a parallel program onto the processors that minimizes the entire execution time is vital for achieving a high performance. This scheduling problem is known to be NPHard. In multiprocessor scheduling problem, a given program is to be scheduled in a given multiprocessor system such that the programs execution time is minimized. The last job must be completed as early as possible. Genetic algorithm (GA) is one of the widely used techniques for constrained optimization problems. Genetic algorithms are basically search algorithms based on the mechanics of natural selection and natural genesis. The main goal behind research on genetic algorithms is robustness i.e. balance between efficiency and efficacy. This paper proposes Genetic algorithm to solve scheduling problem of multiprocessors that minimizes the make span.
An Improved Image Mining Technique For Brain Tumour Classification Using Efficient Classifier
Venue: arXiv cs.CV 2010
Year: 2010

An improved image mining technique for brain tumor classification using pruned association rule with MARI algorithm is presented in this paper. The method proposed makes use of association rule mining technique to classify the CT scan brain images into three categories namely normal, benign and malign. It combines the low level features extracted from images and high level knowledge from specialists. The developed algorithm can assist the physicians for efficient classification with multiple keywords per image to improve the accuracy. The experimental result on prediagnosed database of brain images showed 96 percent and 93 percent sensitivity and accuracy respectively.
Seeing Beyond the Surface, Understanding and Tracking Fraudulent Cyber Activities
Venue: arXiv cs.CR 2010
Year: 2010

The malaise of electronic spam mail that solicit illicit partnership using bogus business proposals (popularly called 419 mails) remained unabated on the internet despite concerted efforts. In addition to these are the emergence and prevalence of phishing scams that use social engineering tactics to obtain online access codes such as credit card number, ATM pin numbers, bank account details, social security number and other personal information (22). In an age where dependence on electronic transaction is on the increase, the web security community will have to devise more pragmatic measures to make the cyberspace safe from these demeaning ills. Understanding the perpetrators of internet crimes and their mode of operation is a basis for any meaningful effort towards stemming these crimes. This paper discusses the nature of the criminals engaged in fraudulent cyberspace activities with special emphasis on the Nigeria 419 scam mails. Based on a qualitative analysis and experiments to trace the source of electronic spam and phishing emails received over a six months period, we provide information about the scammers personalities, motivation, methodologies and victims. We posited that popular email clients are deficient in the provision of effective mechanisms that can aid users in identifying fraud mails and protect them against phishing attacks. We demonstrate, using state of the art techniques, how users can detect and avoid fraudulent emails and conclude by making appropriate recommendations based on our findings.
On the Power of Unambiguity in Logspace
Venue: arXiv cs.CC 2010
Year: 2010

We report progress on the \NL vs \UL problem. [-] We show unconditionally that the complexity class $\ReachFewL\subseteq\UL$. This improves on the earlier known upper bound $\ReachFewL \subseteq \FewL$. [-] We investigate the complexity of min-uniqueness - a central notion in studying the \NL vs \UL problem. We show that min-uniqueness is necessary and sufficient for showing $\NL =\UL$. We revisit the class $\OptL[\log n]$ and show that {\sc ShortestPathLength} - computing the length of the shortest path in a DAG, is complete for $\OptL[\log n]$. We introduce $\UOptL[\log n]$, an unambiguous version of $\OptL[\log n]$, and show that (a) $\NL =\UL$ if and only if $\OptL[\log n] = \UOptL[\log n]$, (b) $\LogFew \leq \UOptL[\log n] \leq \SPL$. [-] We show that the reachability problem over graphs embedded on 3 pages is complete for \NL. This contrasts with the reachability problem over graphs embedded on 2 pages which is logspace equivalent to the reachability problem in planar graphs and hence is in \UL.
Block Sensitivity of Minterm-Transitive Functions
Venue: arXiv cs.CC 2010
Year: 2010

Boolean functions with symmetry properties are interesting from a complexity theory perspective; extensive research has shown that these functions, if nonconstant, must have high `complexity' according to various measures. In recent work of this type, Sun gave bounds on the block sensitivity of nonconstant Boolean functions invariant under a transitive permutation group. Sun showed that all such functions satisfy bs(f) = Omega(N^{1/3}), and that there exists such a function for which bs(f) = O(N^{3/7}ln N). His example function belongs to a subclass of transitively invariant functions called the minterm-transitive functions (defined in earlier work by Chakraborty). We extend these results in two ways. First, we show that nonconstant minterm-transitive functions satisfy bs(f) = Omega(N^{3/7}). Thus Sun's example function has nearly minimal block sensitivity for this subclass. Second, we give an improved example: a minterm-transitive function for which bs(f) = O(N^{3/7}ln^{1/7}N).
Outage Capacity of Bursty Amplify-and-Forward with Incremental Relaying
Venue: arXiv cs.IT 2010
Year: 2010

We derive the outage capacity of a bursty version of the amplify-and-forward (BAF) protocol for small signal-to-noise ratios when incremental relaying is used. We show that the ratio between the outage capacities of BAF and the cut-set bound is independent of the relay position and that BAF is outage optimal for certain conditions on the target rate R. This is in contrast to decode-and-forward with incremental relaying, where the relay location strongly determines the performance of the cooperative protocol. We further derive the outage capacity for a network consisting of an arbitrary number of relay nodes. In this case the relays transmit in subsequent partitions of the overall transmission block and the destination accumulates signal-to-noise ratio until it is able to decode.
Evolving MultiAlgebras unify all usual sequential computation models
Venue: arXiv cs.FL 2010
Year: 2010

It is well-known that Abstract State Machines (ASMs) can simulate "step-by-step" any type of machines (Turing machines, RAMs, etc.). We aim to overcome two facts: 1) simulation is not identification, 2) the ASMs simulating machines of some type do not constitute a natural class among all ASMs. We modify Gurevich's notion of ASM to that of EMA ("Evolving MultiAlgebra") by replacing the program (which is a syntactic object) by a semantic object: a functional which has to be very simply definable over the static part of the ASM. We prove that very natural classes of EMAs correspond via "literal identifications" to slight extensions of the usual machine models and also to grammar models. Though we modify these models, we keep their computation approach: only some contingencies are modified. Thus, EMAs appear as the mathematical model unifying all kinds of sequential computation paradigms.
Comparing Simulation Output Accuracy of Discrete Event and Agent Based Models: A Quantitive Approach
Venue: arXiv cs.AI 2010
Year: 2010

In our research we investigate the output accuracy of discrete event simulation models and agent based simulation models when studying human centric complex systems. In this paper we focus on human reactive behaviour as it is possible in both modelling approaches to implement human reactive behaviour in the model by using standard methods. As a case study we have chosen the retail sector, and here in particular the operations of the fitting room in the women wear department of a large UK department store. In our case study we looked at ways of determining the efficiency of implementing new management policies for the fitting room operation through modelling the reactive behaviour of staff and customers of the department. First, we have carried out a validation experiment in which we compared the results from our models to the performance of the real system. This experiment also allowed us to establish differences in output accuracy between the two modelling methids. In a second step a multi-scenario experiment was carried out to study the behaviour of the models when they are used for the purpose of operational improvement. Overall we have found that for our case study example both discrete event simulation and agent based simulation have the same potential to support the investigation into the efficiency of implementing new management policies.
Building reputation systems for better ranking
Venue: arXiv cs.IR 2010
Year: 2010

How to rank web pages, scientists and online resources has recently attracted increasing attention from both physicists and computer scientists. In this paper, we study the ranking problem of rating systems where users vote objects by discrete ratings. We propose an algorithm that can simultaneously evaluate the user reputation and object quality in an iterative refinement way. According to both the artificially generated data and the real data from MovieLens and Amazon, our algorithm can considerably enhance the ranking accuracy. This work highlights the significance of reputation systems in the Internet era and points out a way to evaluate and compare the performances of different reputation systems.
Towards a Generic Framework to Generate Explanatory Traces of Constraint Solving and Rule-Based Reasoning
Venue: arXiv cs.PL 2010
Year: 2010

In this report, we show how to use the Simple Fluent Calculus (SFC) to specify generic tracers, i.e. tracers which produce a generic trace. A generic trace is a trace which can be produced by different implementations of a software component and used independently from the traced component. This approach is used to define a method for extending a java based CHRor platform called CHROME (Constraint Handling Rule Online Model-driven Engine) with an extensible generic tracer. The method includes a tracer specification in SFC, a methodology to extend it, and the way to integrate it with CHROME, resulting in the platform CHROME-REF (for Reasoning Explanation Facilities), which is a constraint solving and rule based reasoning engine with explanatory traces.
DCA for Bot Detection
Venue: arXiv cs.AI 2010
Year: 2010

Ensuring the security of computers is a non-trivial task, with many techniques used by malicious users to compromise these systems. In recent years a new threat has emerged in the form of networks of hijacked zombie machines used to perform complex distributed attacks such as denial of service and to obtain sensitive data such as password information. These zombie machines are said to be infected with a 'bot' - a malicious piece of software which is installed on a host machine and is controlled by a remote attacker, termed the 'botmaster of a botnet'. In this work, we use the biologically inspired Dendritic Cell Algorithm (DCA) to detect the existence of a single bot on a compromised host machine. The DCA is an immune-inspired algorithm based on an abstract model of the behaviour of the dendritic cells of the human body. The basis of anomaly detection performed by the DCA is facilitated using the correlation of behavioural attributes such as keylogging and packet flooding behaviour. The results of the application of the DCA to the detection of a single bot show that the algorithm is a successful technique for the detection of such malicious software without responding to normally running programs.
Bounds on the Capacity of the Relay Channel with Noncausal State Information at Source
Venue: arXiv cs.IT 2010
Year: 2010

We consider a three-terminal state-dependent relay channel with the channel state available non-causally at only the source. Such a model may be of interest for node cooperation in the framework of cognition, i.e., collaborative signal transmission involving cognitive and non-cognitive radios. We study the capacity of this communication model. One principal problem in this setup is caused by the relay's not knowing the channel state. In the discrete memoryless (DM) case, we establish lower bounds on channel capacity. For the Gaussian case, we derive lower and upper bounds on the channel capacity. The upper bound is strictly better than the cut-set upper bound. We show that one of the developed lower bounds comes close to the upper bound, asymptotically, for certain ranges of rates.