OpenRaiser/Intern-Atlas huggingface dataset:
A Generalized Streaming Model for Concurrent Computing
Venue: arXiv cs.PL 2010
Year: 2010

Multicore parallel programming has some very difficult problems such as deadlocks during synchronizations and race conditions brought by concurrency. Added to the difficulty is the lack of a simple, well-accepted computing model for multicore architectures--because of that it is hard to develop powerful programming environments and debugging tools. To tackle the challenges, we promote a generalized stream computing model, inspired by previous researches on stream computing, that unifies parallelization strategies for programming language design, compiler design and operating system design. Our model provides a high-level abstraction in designing language constructs to convey concepts of concurrent operations, in organizing a program's runtime layout for parallel execution, and in scheduling concurrent instruction blocks through runtime and/or operating systems. In this paper, we give a high-level description of the proposed model: we define the foundation of the model, show its simplicity through algebraic/computational operation analysis, illustrate a programming framework enabled by the model, and demonstrate its potential through powerful design options for programming languages, compilers and operating systems.
The Rule Responder eScience Infrastructure
Venue: arXiv cs.MA 2010
Year: 2010

To a large degree information and services for chemical e-Science have become accessible - anytime, anywhere - but not necessarily useful. The Rule Responder eScience middleware is about providing information consumers with rule-based agents to transform existing information into relevant information of practical consequences, hence providing control to the end-users to express in a declarative rule-based way how to turn existing information into personally relevant information and how to react or make automated decisions on top of it.
Import of ENZYME data into the ConceptWiki and its representation as RDF
Venue: arXiv cs.DL 2010
Year: 2010

Solutions to the classic problems of dealing with heterogeneous data and making entire collections interoperable while ensuring that any annotation, which includes the recognition-and-reward system of scientific publishing, need to fit into a seamless beginning to end to attract large numbers of end users. The latest trend in Web applications encourages highly interactive Web sites with rich user interfaces featuring content integrated from various sources around the Web. The obvious potential of RDF, SPARQL, and OWL to provide flexible data modeling, easier data integration, and networked data access may be the answer to the classic problems. Using Semantic Web technologies we have created a Web application, the ConceptWiki, as an end-to-end solution for creating browserbased readwrite triples using RDF, which focus on data integration and ease of use for the end user. Here we will demonstrate the integration of a biological data source, the ENZYME database, into the ConceptWiki and it's representation in RDF.
Provenance and evidence in UniProtKB
Venue: arXiv cs.DB 2010
Year: 2010

The primary mission of UniProt is to support biological research by maintaining a stable, comprehensive, fully classified, richly and accurately annotated protein sequence knowledgebase, with extensive cross-references to external resources, that is freely available to the scientific community. To enable users of the knowledgebase to accurately assess the reliability of the information contained in this resource, the evidence for and provenance of the information must be recorded. This paper discusses the user requirements for this kind of metadata and the manner in which UniProtKB records it.
Examples of the Generalized Quantum Permanent Compromise Attack to the Blum-Micali Construction
Venue: arXiv cs.IT 2010
Year: 2010

This paper presents examples of the quantum permanent compromise attack to the Blum-Micali construction. Such attacks illustrate how a previous attack to the Blum-Micali generator can be extended to the whole Blum-Micali construction, including the Blum-Blum-Shub and Kaliski generators.
Towards Fully Optimized BICM Transceivers
Venue: arXiv cs.IT 2010
Year: 2010

Bit-interleaved coded modulation (BICM) transceivers often use equally spaced constellations and a random interleaver. In this paper, we propose a new BICM design, which considers hierarchical (nonequally spaced) constellations, a bit-level multiplexer, and multiple interleavers. It is shown that this new scheme increases the degrees of freedom that can be exploited in order to improve its performance. Analytical bounds on the bit error rate (BER) of the system in terms of the constellation parameters and the multiplexing rules are developed for the additive white Gaussian Noise (AWGN) and Nakagami-$m$ fading channels. These bounds are then used to design the BICM transceiver. Numerical results show that, compared to conventional BICM designs, and for a target BER of $10^{-6}$, gains up to 3 dB in the AWGN channel are obtained. For fading channels, the gains depend on the fading parameter, and reach 2 dB for a target BER of $10^{-7}$ and $m=5$.
NP-completeness Proof: RBCDN Reduction Problem
Venue: arXiv cs.CC 2010
Year: 2010

Computational complexity of the design problem for a network with a target value of Region-Based Component Decomposition Number (RBCDN) has been proven to be NP-complete.
On Two-way Communications for Cooperative Multiple Source Pairs Through a Multi-antenna Relay
Venue: arXiv cs.IT 2010
Year: 2010

We study amplified-and-forward (AF)-based two-way relaying (TWR) with multiple source pairs, which are exchanging information through the relay. Each source has single antenna and the relay has multi-antenna. The optimal beamforming matrix structure that achieves maximum signal-to-interference-plus-noise ratio (SINR) for TWR with multiple source pairs is derived. We then present two new non-zero-forcing based beamforming schemes for TWR, which take into consideration the tradeoff between preserving the desired signals and suppressing inter-pair interference between different source pairs. Joint grouping and beamforming scheme is proposed to achieve a better signal-to-interference-plus-noise ratio (SINR) when the total number of source pairs is large and the signal-to-noise ratio (SNR) at the relay is low.
A Robust and Efficient Trust Management Scheme for Peer-to-Peer Networks
Venue: arXiv cs.DC 2010
Year: 2010

Studies on the large scale peer-to-peer (P2P) network like Gnutella have shown the presence of large number of free riders. Moreover, the open and decentralized nature of P2P network is exploited by malicious users who distribute unauthentic or harmful contents. Despite the existence of a number of trust management schemes in the literature for combating against free riding and distribution of malicious files, these mechanisms are not scalable due to their high computational, communication and storage overhead. These schemes also do not consider effect of trust management on quality-of-service (QoS) of the search. This paper presents a trust management scheme for P2P networks that minimizes distribution of spurious files by a novel technique called topology adaptation. It also reduces search time since most of the queries are resolved within the community of trustworthy peers. Simulation results indicate that the trust management overhead due to the pr oposed mechanism decreases considerably as the network topology stabilizes. The mechanism is also found to be robust even in presence of a large percentage of malicious peers.
Stiffness modelling of parallelogram-based parallel manipulators
Venue: arXiv cs.RO 2010
Year: 2010

The paper presents a methodology to enhance the stiffness analysis of parallel manipulators with parallelogram-based linkage. It directly takes into account the influence of the external loading and allows computing both the non-linear ``load-deflection" relation and relevant rank-deficient stiffness matrix. An equivalent bar-type pseudo-rigid model is also proposed to describe the parallelogram stiffness by means of five mutually coupled virtual springs. The contributions of this paper are highlighted with a parallelogram-type linkage used in a manipulator from the Orthoglide family.
Performance Evaluation of Parallel Message Passing and Thread Programming Model on Multicore Architectures
Venue: arXiv cs.DC 2010
Year: 2010

The current trend of multicore architectures on shared memory systems underscores the need of parallelism. While there are some programming model to express parallelism, thread programming model has become a standard to support these system such as OpenMP, and POSIX threads. MPI (Message Passing Interface) which remains the dominant model used in high-performance computing today faces this challenge. Previous version of MPI which is MPI-1 has no shared memory concept, and Current MPI version 2 which is MPI-2 has a limited support for shared memory systems. In this research, MPI-2 version of MPI will be compared with OpenMP to see how well does MPI perform on multicore / SMP (Symmetric Multiprocessor) machines. Comparison between OpenMP for thread programming model and MPI for message passing programming model will be conducted on multicore shared memory machine architectures to see who has a better performance in terms of speed and throughput. Application used to assess the scalability of the evaluated parallel programming solutions is matrix multiplication with customizable matrix dimension. Many research done on a large scale parallel computing which using high scale benchmark such as NSA Parallel Benchmark (NPB) for their testing standarization [1]. This research will be conducted on a small scale parallel computing that emphasize more on the performance evaluation between MPI and OpenMPI parallel programming model using self created benchmark.
The Exact String Matching Problem: a Comprehensive Experimental Evaluation
Venue: arXiv cs.DS 2010
Year: 2010

This paper addresses the online exact string matching problem which consists in finding all occurrences of a given pattern p in a text t. It is an extensively studied problem in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, data compression, information retrieval, computational biology and chemistry. Since 1970 more than 80 string matching algorithms have been proposed, and more than 50% of them in the last ten years. In this note we present a comprehensive list of all string matching algorithms and present experimental results in order to compare them from a practical point of view. From our experimental evaluation it turns out that the performance of the algorithms are quite different for different alphabet sizes and pattern length.
Scope Logic with Local Reasoning and Pre/Post-State Properties
Venue: arXiv cs.LO 2010
Year: 2010

This paper presents an extension to Hoare logic for pointer program verification. Logic formulas with user-defined recursive functions are used to specify properties on the program states before/after program executions. Three basic functions are introduced to represents memory access, record-field access and array-element access. Some axioms are introduced to specify these basic functions in our logic. The concept Memory Scope Function (MSF) is introduced in our logic. Given a recursive function $f$, the MSF of $f$ computes the set of memory units accessed during the evaluation of $f$. A set of rules are given to derive the definition of this MSF syntactically from the definition of $f$. As MSFs are also recursive functions, they also have their MSFs. An axiom is given to specify that an MSF contains its MSF. Based on this axiom, local reasoning is supported with predicate variables. Pre-state terms are used to specify the relations between pre-states and post-states. People can use pre-state terms in post-conditions to represents the values on the pre-state. The axiom of assignment statements in Hoare's logic is modified to deal with pointers. The basic idea is that during the program execution, a recursive function is evaluated to the same value as long as no memory unit in its memory scope is modified. Another proof rule is added for memory allocation statements. We use a simple example to show that our logic can deal with pointer programs in this paper. In the appendix, the Shorre-Waite algorithm is proved using our logic. We also use the selection-sort program to show that our logic can be used to prove program with indirectly-specified components.
Phase Transitions of Plan Modification in Conformant Planning
Venue: arXiv cs.AI 2010
Year: 2010

We explore phase transitions of plan modification, which mainly focus on the conformant planning problems. By analyzing features of plan modification in conformant planning problems, quantitative results are obtained. If the number of operators is less than, almost all conformant planning problems can't be solved with plan modification. If the number of operators is more than, almost all conformant planning problems can be solved with plan modification. The results of the experiments also show that there exists an experimental threshold of density (ratio of number of operators to number of propositions), which separates the region where almost all conformant planning problems can't be solved with plan modification from the region where almost all conformant planning problems can be solved with plan modification.
Relational transducers for declarative networking
Venue: arXiv cs.DB 2010
Year: 2010

Motivated by a recent conjecture concerning the expressiveness of declarative networking, we propose a formal computation model for "eventually consistent" distributed querying, based on relational transducers. A tight link has been conjectured between coordination-freeness of computations, and monotonicity of the queries expressed by such computations. Indeed, we propose a formal definition of coordination-freeness and confirm that the class of monotone queries is captured by coordination-free transducer networks. Coordination-freeness is a semantic property, but the syntactic class that we define of "oblivious" transducers also captures the same class of monotone queries. Transducer networks that are not coordination-free are much more powerful.
Seamless Flow Migration on Smartphones without Network Support
Venue: arXiv cs.NI 2010
Year: 2010

This paper addresses the following question: Is it possible to migrate TCP/IP flows between different networks on modern mobile devices, without infrastructure support or protocol changes? To answer this question, we make three research contributions. (i) We report a comprehensive characterization of IP traffic on smartphones using traces collected from 27 iPhone 3GS users for three months. (ii) Driven by the findings from the characterization, we devise two novel system mechanisms for mobile devices to sup-port seamless flow migration without network support, and extensively evaluate their effectiveness using our field collected traces of real-life usage. Wait-n-Migrate leverages the fact that most flows are short lived. It establishes new flows on newly available networks but allows pre-existing flows on the old network to terminate naturally, effectively decreasing, or even eliminating, connectivity gaps during network switches. Resumption Agent takes advantage of the functionality integrated into many modern protocols to securely resume flows without application intervention. When combined, Wait-n-Migrate and Resumption Agent provide an unprecedented opportunity to immediately deploy performance and efficiency-enhancing policies that leverage multiple networks to improve the performance, efficiency, and connectivity of mobile devices. (iii) Finally, we report an iPhone 3GS based implementation of these two system mechanisms and show that their overhead is negligible. Furthermore, we employ an example network switching policy, called AutoSwitch, to demonstrate their performance. AutoSwitch improves the Wi-Fi user experience by intelligently migrating TCP flows between Wi-Fi and cellular networks. Through traces and field measurements, we show that AutoSwitch reduces the number of user disruptions by an order of magnitude.
On the performance of the variational multiscale formulation for subsurface flow and transport in heterogeneous porous media
Venue: arXiv cs.NA 2010
Year: 2010

The following work compares two popular mixed finite elements used to model subsurface flow and transport in heterogeneous porous media; the lowest order Raviart-Thomas element and the variational multiscale stabilized element. Comparison is made based on performance for several problems of engineering relevance that involve highly heterogenous material properties (permeability ratios of up to $1\times10^5$), open flow boundary conditions (pressure driven flows), and large scale domains in two dimensions. Numerical experiments are performed to show the degree to which mass conservation is violated when a flow field computed using either element is used as the advection velocity in a transport model. The results reveal that the variational multiscale element shows considerable mass production or loss for problems that involve flow tangential to layers of differing permeability, but marginal violation of local mass balance for problems of less orthogonality in the permeability. The results are useful in establishing rudimentary estimates of the error produced by using the variational mutliscale element for several different types of problems.
Théorie de Galois effective : aide mémoire
Venue: arXiv cs.SC 2010
Year: 2010

This paper collects many results on galoisian ideals and Galois theory.
Customer Appeasement Scheduling
Venue: arXiv cs.OS 2010
Year: 2010

Almost all of the current process scheduling algorithms which are used in modern operating systems (OS) have their roots in the classical scheduling paradigms which were developed during the 1970's. But modern computers have different types of software loads and user demands. We think it is important to run what the user wants at the current moment. A user can be a human, sitting in front of a desktop machine, or it can be another machine sending a request to a server through a network connection. We think that OS should become intelligent to distinguish between different processes and allocate resources, including CPU, to those processes which need them most. In this work, as a first step to make the OS aware of the current state of the system, we consider process dependencies and interprocess communications. We are developing a model, which considers the need to satisfy interactive users and other possible remote users or customers, by making scheduling decisions based on process dependencies and interprocess communications. Our simple proof of concept implementation and experiments show the effectiveness of this approach in the real world applications. Our implementation does not require any change in the software applications nor any special kind of configuration in the system, Moreover, it does not require any additional information about CPU needs of applications nor other resource requirements. Our experiments show significant performance improvement for real world applications. For example, almost constant average response time for Mysql data base server and constant frame rate for mplayer under different simulated load values.
Adaptive Cluster Expansion (ACE): A Multilayer Network for Estimating Probability Density Functions
Venue: arXiv cs.NE 2010
Year: 2010

We derive an adaptive hierarchical method of estimating high dimensional probability density functions. We call this method of density estimation the "adaptive cluster expansion" or ACE for short. We present an application of this approach, based on a multilayer topographic mapping network, that adaptively estimates the joint probability density function of the pixel values of an image, and presents this result as a "probability image". We apply this to the problem of identifying statistically anomalous regions in otherwise statistically homogeneous images.
A New Formula for the BER of Binary Modulations with Dual-Branch Selection over Generalized-K Composite Fading Channels
Venue: arXiv cs.IT 2010
Year: 2010

Error performance is one of the main performance measures and derivation of its closed-form expression has proved to be quite involved for certain systems. In this letter, a unified closed-form expression, applicable to different binary modulation schemes, for the bit error rate of dual-branch selection diversity based systems undergoing independent but not necessarily identically distributed generalized-K fading is derived in terms of the extended generalized bivariate Meijer G-function.
A Note on Solid Coloring of Pure Simplicial Complexes
Venue: arXiv cs.DM 2010
Year: 2010

We establish a simple generalization of a known result in the plane. The simplices in any pure simplicial complex in R^d may be colored with d+1 colors so that no two simplices that share a (d-1)-facet have the same color. In R^2 this says that any planar map all of whose faces are triangles may be 3-colored, and in R^3 it says that tetrahedra in a collection may be "solid 4-colored" so that no two glued face-to-face receive the same color.
Application of Global and One-Dimensional Local Optimization to Operating System Scheduler Tuning
Venue: arXiv cs.OS 2010
Year: 2010

This paper describes a study of comparison of global and one-dimensional local optimization methods to operating system scheduler tuning. The operating system scheduler we use is the Linux 2.6.23 Completely Fair Scheduler (CFS) running in simulator (LinSched). We have ported the Hackbench scheduler benchmark to this simulator and use this as the workload. The global optimization approach we use is Particle Swarm Optimization (PSO). We make use of Response Surface Methodology (RSM) to specify optimal parameters for our PSO implementation. The one-dimensional local optimization approach we use is the Golden Section method. In order to use this approach, we convert the scheduler tuning problem from one involving setting of three parameters to one involving the manipulation of one parameter. Our results show that the global optimization approach yields better response but the one- dimensional optimization approach converges to a solution faster than the global optimization approach.
Motif Analysis in the Amazon Product Co-Purchasing Network
Venue: arXiv cs.SI 2010
Year: 2010

Online stores like Amazon and Ebay are growing by the day. Fewer people go to departmental stores as opposed to the convenience of purchasing from stores online. These stores may employ a number of techniques to advertise and recommend the appropriate product to the appropriate buyer profile. This article evaluates various 3-node and 4-node motifs occurring in such networks. Community structures are evaluated too.These results may provide interesting insights into user behavior and a better understanding of marketing techniques.
Non Abelian Bent Functions
Venue: arXiv cs.CR 2010
Year: 2010

Perfect nonlinear functions from a finite group $G$ to another one $H$ are those functions $f: G \rightarrow H$ such that for all nonzero $α\in G$, the derivative $d_αf: x \mapsto f(αx) f(x)^{-1}$ is balanced. In the case where both $G$ and $H$ are Abelian groups, $f: G \rightarrow H$ is perfect nonlinear if and only if $f$ is bent i.e for all nonprincipal character $χ$ of $H$, the (discrete) Fourier transform of $χ\circ f$ has a constant magnitude equals to $|G|$. In this paper, using the theory of linear representations, we exhibit similar bentness-like characterizations in the cases where $G$ and/or $H$ are (finite) non Abelian groups. Thus we extend the concept of bent functions to the framework of non Abelian groups.