OpenRaiser/Intern-Atlas huggingface dataset:
An innovative platform to improve the performance of exact string matching algorithms
Venue: arXiv cs.DC 2010
Year: 2010

Exact String Matching is an essential issue in many computer science applications. Unfortunately, the performance of Exact String Matching algorithms, namely, executing time, does not address the needs of these applications. This paper proposes a general platform for improving the existing Exact String Matching algorithms executing time, called the PXSMAlg platform. The function of this platform is to parallelize the Exact String Matching algorithms using the MPI model over the Master or Slaves paradigms. The PXSMAlg platform parallelization process is done by dividing the Text into several parts and working on these parts simultaneously. This improves the executing time of the Exact String Matching algorithms. We have simulated the PXSMAlg platform in order to show its competence, through applying the Quick Search algorithm on the PXSMAlg platform. The simulation result showed significant improvement in the Quick Search executing time, and therefore extreme competence in the PXSMAlg platform.
A Coordinate System for Gaussian Networks
Venue: arXiv cs.IT 2010
Year: 2010

This paper studies network information theory problems where the external noise is Gaussian distributed. In particular, the Gaussian broadcast channel with coherent fading and the Gaussian interference channel are investigated. It is shown that in these problems, non-Gaussian code ensembles can achieve higher rates than the Gaussian ones. It is also shown that the strong Shamai-Laroia conjecture on the Gaussian ISI channel does not hold. In order to analyze non-Gaussian code ensembles over Gaussian networks, a geometrical tool using the Hermite polynomials is proposed. This tool provides a coordinate system to analyze a class of non-Gaussian input distributions that are invariant over Gaussian networks.
Upstream traffic capacity of a WDM EPON under online GATE-driven scheduling
Venue: arXiv cs.NI 2010
Year: 2010

Passive optical networks are increasingly used for access to the Internet and it is important to understand the performance of future long-reach, multi-channel variants. In this paper we discuss requirements on the dynamic bandwidth allocation (DBA) algorithm used to manage the upstream resource in a WDM EPON and propose a simple novel DBA algorithm that is considerably more efficient than classical approaches. We demonstrate that the algorithm emulates a multi-server polling system and derive capacity formulas that are valid for general traffic processes. We evaluate delay performance by simulation demonstrating the superiority of the proposed scheduler. The proposed scheduler offers considerable flexibility and is particularly efficient in long-reach access networks where propagation times are high.
High Performance Hybrid Two Layer Router Architecture for FPGAs Using Network On Chip
Venue: arXiv cs.NI 2010
Year: 2010

Networks on Chip is a recent solution paradigm adopted to increase the performance of Multicore designs. The key idea is to interconnect various computation modules (IP cores) in a network fashion and transport packets simultaneously across them, thereby gaining performance. In addition to improving performance by having multiple packets in flight, NoCs also present a host of other advantages including scalability, power efficiency, and component reuse through modular design. This work focuses on design and development of high performance communication architectures for FPGAs using NoCs Once completely developed, the above methodology could be used to augment the current FPGA design flow for implementing multicore SoC applications. We design and implement an NoC framework for FPGAs, MultiClock OnChip Network for Reconfigurable Systems (MoCReS). We propose a novel microarchitecture for a hybrid two layer router that supports both packetswitched communications, across its local and directional ports, as well as, time multiplexed circuitswitched communications among the multiple IP cores directly connected to it. Results from place and route VHDL models of the advanced router architecture show an average improvement of 20.4 percent in NoC bandwidth (maximum of 24 percent compared to a traditional NoC). We parameterize the hybrid router model over the number of ports, channel width and bRAM depth and develop a library of network components (MoClib Library). For your paper to be published in the conference proceedings, you must use this document as both an instruction set and as a template into which you can type your own text. If your paper does not conform to the required format, you will be asked to fix it.
Performance Analysis of View Maintenance Techniques for DW
Venue: arXiv cs.SE 2010
Year: 2010

A Data Warehouse stores integrated information as materialized views over data from one or more remote sources. These materialized views must be maintained in response to actual relation updates in the remote sources. The data warehouse view maintenance techniques are classified into four major categories self maintainable recomputation, not self maintainable recomputation, self maintainable incremental maintenance, and not self maintainable incremental maintenance. This paper provides a comprehensive comparison of the techniques in these four categories in terms of the data warehouse space usage and number of rows accessed in order to propagate an update from a remote data source to a target materialized view in the data warehouse.
Toward a Formal Semantics for Autonomic Components
Venue: arXiv cs.DC 2010
Year: 2010

Autonomic management can improve the QoS provided by parallel/ distributed applications. Within the CoreGRID Component Model, the autonomic management is tailored to the automatic - monitoring-driven - alteration of the component assembly and, therefore, is defined as the effect of (distributed) management code. This work yields a semantics based on hypergraph rewriting suitable to model the dynamic evolution and non-functional aspects of Service Oriented Architectures and component-based autonomic applications. In this regard, our main goal is to provide a formal description of adaptation operations that are typically only informally specified. We contend that our approach makes easier to raise the level of abstraction of management code in autonomic and adaptive applications.
Multibiometrics Belief Fusion
Venue: arXiv cs.CV 2010
Year: 2010

This paper proposes a multimodal biometric system through Gaussian Mixture Model (GMM) for face and ear biometrics with belief fusion of the estimated scores characterized by Gabor responses and the proposed fusion is accomplished by Dempster-Shafer (DS) decision theory. Face and ear images are convolved with Gabor wavelet filters to extracts spatially enhanced Gabor facial features and Gabor ear features. Further, GMM is applied to the high-dimensional Gabor face and Gabor ear responses separately for quantitive measurements. Expectation Maximization (EM) algorithm is used to estimate density parameters in GMM. This produces two sets of feature vectors which are then fused using Dempster-Shafer theory. Experiments are conducted on multimodal database containing face and ear images of 400 individuals. It is found that use of Gabor wavelet filters along with GMM and DS theory can provide robust and efficient multimodal fusion strategy.
On the Non-Coherent Wideband Multipath Fading Relay Channel
Venue: arXiv cs.IT 2010
Year: 2010

We investigate the multipath fading relay channel in the limit of a large bandwidth, and in the non-coherent setting, where the channel state is unknown to all terminals, including the relay and the destination. We propose a hypergraph model of the wideband multipath fading relay channel, and show that its min-cut is achieved by a non-coherent peaky frequency binning scheme. The so-obtained lower bound on the capacity of the wideband multipath fading relay channel turns out to coincide with the block-Markov lower bound on the capacity of the wideband frequency-division Gaussian (FD-AWGN) relay channel. In certain cases, this achievable rate also meets the cut-set upper-bound, and thus reaches the capacity of the non-coherent wideband multipath fading relay channel.
Using ATL to define advanced and flexible constraint model transformations
Venue: arXiv cs.AI 2010
Year: 2010

Transforming constraint models is an important task in re- cent constraint programming systems. User-understandable models are defined during the modeling phase but rewriting or tuning them is manda- tory to get solving-efficient models. We propose a new architecture al- lowing to define bridges between any (modeling or solver) languages and to implement model optimizations. This architecture follows a model- driven approach where the constraint modeling process is seen as a set of model transformations. Among others, an interesting feature is the def- inition of transformations as concept-oriented rules, i.e. based on types of model elements where the types are organized into a hierarchy called a metamodel.
L2C2: Logic-based LSC Consistency Checking
Venue: arXiv cs.LO 2010
Year: 2010

Live sequence charts (LSCs) have been proposed as an inter-object scenario-based specification and visual programming language for reactive systems. In this paper, we introduce a logic-based framework to check the consistency of an LSC specification. An LSC simulator has been implemented in logic programming, utilizing a memoized depth-first search strategy, to show how a reactive system in LSCs would response to a set of external event sequences. A formal notation is defined to specify external event sequences, extending the regular expression with a parallel operator and a testing control. The parallel operator allows interleaved parallel external events to be tested in LSCs simultaneously; while the testing control provides users to a new approach to specify and test certain temporal properties (e.g., CTL formula) in a form of LSC. Our framework further provides either a state transition graph or a failure trace to justify the consistency checking results.
Convergence of Bayesian Control Rule
Venue: arXiv cs.AI 2010
Year: 2010

Recently, new approaches to adaptive control have sought to reformulate the problem as a minimization of a relative entropy criterion to obtain tractable solutions. In particular, it has been shown that minimizing the expected deviation from the causal input-output dependencies of the true plant leads to a new promising stochastic control rule called the Bayesian control rule. This work proves the convergence of the Bayesian control rule under two sufficient assumptions: boundedness, which is an ergodicity condition; and consistency, which is an instantiation of the sure-thing principle.
On the scaling of Polar Codes: II. The behavior of un-polarized channels
Venue: arXiv cs.IT 2010
Year: 2010

We provide upper and lower bounds on the escape rate of the Bhattacharyya process corresponding to polar codes and transmission over the the binary erasure channel. More precisely, we bound the exponent of the number of sub-channels whose Bhattacharyya constant falls in a fixed interval $[a,b]$. Mathematically this can be stated as bounding the limit $\lim_{n \to \infty} \frac{1}{n} \ln \mathbb{P}(Z_n \in [a,b])$, where $Z_n$ is the Bhattacharyya process. The quantity $\mathbb{P}(Z_n \in [a,b])$ represents the fraction of sub-channels that are still un-polarized at time $n$.
Efficiently Discovering Hammock Paths from Induced Similarity Networks
Venue: arXiv cs.AI 2010
Year: 2010

Similarity networks are important abstractions in many information management applications such as recommender systems, corpora analysis, and medical informatics. For instance, by inducing similarity networks between movies rated similarly by users, or between documents containing common terms, and or between clinical trials involving the same themes, we can aim to find the global structure of connectivities underlying the data, and use the network as a basis to make connections between seemingly disparate entities. In the above applications, composing similarities between objects of interest finds uses in serendipitous recommendation, in storytelling, and in clinical diagnosis, respectively. We present an algorithmic framework for traversing similarity paths using the notion of `hammock' paths which are generalization of traditional paths. Our framework is exploratory in nature so that, given starting and ending objects of interest, it explores candidate objects for path following, and heuristics to admissibly estimate the potential for paths to lead to a desired destination. We present three diverse applications: exploring movie similarities in the Netflix dataset, exploring abstract similarities across the PubMed corpus, and exploring description similarities in a database of clinical trials. Experimental results demonstrate the potential of our approach for unstructured knowledge discovery in similarity networks.
Deriving Relationship Between Semantic Models - An Approach for cCSP
Venue: arXiv cs.LO 2010
Year: 2010

Formal semantics offers a complete and rigorous definition of a language. It is important to define different semantic models for a language and different models serve different purposes. Building equivalence between different semantic models of a language strengthen its formal foundation. This paper shows the derivation of denotational semantics from operational semantics of the language cCSP. The aim is to show the correspondence between operational and trace semantics. We extract traces from operational rules and use induction over traces to show the correspondence between the two semantics of cCSP.
Iterative exact global histogram specification and SSIM gradient ascent: a proof of convergence, step size and parameter selection
Venue: arXiv cs.CV 2010
Year: 2010

The SSIM-optimized exact global histogram specification (EGHS) is shown to converge in the sense that the first order approximation of the result's quality (i.e., its structural similarity with input) does not decrease in an iteration, when the step size is small. Each iteration is composed of SSIM gradient ascent and basic EGHS with the specified target histogram. Selection of step size and other parameters is also discussed.
Aryabhata's Mathematics
Venue: arXiv cs.CR 2010
Year: 2010

This paper presents certains aspects of the mathematics of Aryabhata that are of interest to the cryptography community.
Finite Volume Spaces and Sparsification
Venue: arXiv cs.DS 2010
Year: 2010

We introduce and study finite $d$-volumes - the high dimensional generalization of finite metric spaces. Having developed a suitable combinatorial machinery, we define $\ell_1$-volumes and show that they contain Euclidean volumes and hypertree volumes. We show that they can approximate any $d$-volume with $O(n^d)$ multiplicative distortion. On the other hand, contrary to Bourgain's theorem for $d=1$, there exists a $2$-volume that on $n$ vertices that cannot be approximated by any $\ell_1$-volume with distortion smaller than $\tildeΩ(n^{1/5})$. We further address the problem of $\ell_1$-dimension reduction in the context of $\ell_1$ volumes, and show that this phenomenon does occur, although not to the same striking degree as it does for Euclidean metrics and volumes. In particular, we show that any $\ell_1$ metric on $n$ points can be $(1+ ε)$-approximated by a sum of $O(n/ε^2)$ cut metrics, improving over the best previously known bound of $O(n \log n)$ due to Schechtman. In order to deal with dimension reduction, we extend the techniques and ideas introduced by Karger and Bencz{ú}r, and Spielman et al.~in the context of graph Sparsification, and develop general methods with a wide range of applications.
Theory of Regulatory Compliance for Requirements Engineering
Venue: arXiv cs.SE 2010
Year: 2010

Regulatory compliance is increasingly being addressed in the practice of requirements engineering as a main stream concern. This paper points out a gap in the theoretical foundations of regulatory compliance, and presents a theory that states (i) what it means for requirements to be compliant, (ii) the compliance problem, i.e., the problem that the engineer should resolve in order to verify whether requirements are compliant, and (iii) testable hypotheses (predictions) about how compliance of requirements is verified. The theory is instantiated by presenting a requirements engineering framework that implements its principles, and is exemplified on a real-world case study.
Fast Flooding over Manhattan
Venue: arXiv cs.DC 2010
Year: 2010

We consider a Mobile Ad-hoc NETwork (MANET) formed by n agents that move at speed V according to the Manhattan Random-Way Point model over a square region of side length L. The resulting stationary (agent) spatial probability distribution is far to be uniform: the average density over the "central zone" is asymptotically higher than that over the "suburb". Agents exchange data iff they are at distance at most R within each other. We study the flooding time of this MANET: the number of time steps required to broadcast a message from one source agent to all agents of the network in the stationary phase. We prove the first asymptotical upper bound on the flooding time. This bound holds with high probability, it is a decreasing function of R and V, and it is tight for a wide and relevant range of the network parameters (i.e. L, R and V). A consequence of our result is that flooding over the sparse and highly-disconnected suburb can be as fast as flooding over the dense and connected central zone. Rather surprisingly, this property holds even when R is exponentially below the connectivity threshold of the MANET and the speed V is very low.
The lattice of embedded subsets
Venue: arXiv cs.DM 2010
Year: 2010

In cooperative game theory, games in partition function form are real-valued function on the set of so-called embedded coalitions, that is, pairs $(S,π)$ where $S$ is a subset (coalition) of the set $N$ of players, and $π$ is a partition of $N$ containing $S$. Despite the fact that many studies have been devoted to such games, surprisingly nobody clearly defined a structure (i.e., an order) on embedded coalitions, resulting in scattered and divergent works, lacking unification and proper analysis. The aim of the paper is to fill this gap, thus to study the structure of embedded coalitions (called here embedded subsets), and the properties of games in partition function form.
Partitionability to two trees is NP-complete
Venue: arXiv cs.CC 2010
Year: 2010

We show that P2T - the problem of deciding whether the edge set of a simple graph can be partitioned into two trees or not - is NP-complete.
Supervised Learning of Digital image restoration based on Quantization Nearest Neighbor algorithm
Venue: arXiv cs.CV 2010
Year: 2010

In this paper, an algorithm is proposed for Image Restoration. Such algorithm is different from the traditional approaches in this area, by utilizing priors that are learned from similar images. Original images and their degraded versions by the known degradation operators are utilized for designing the Quantization. The code vectors are designed using the blurred images. For each such vector, the high frequency information obtained from the original images is also available. During restoration, the high frequency information of a given degraded image is estimated from its low frequency information based on the artificial noise. For the restoration problem, a number of techniques are designed corresponding to various versions of the blurring function. Given a noisy and blurred image, one of the techniques is chosen based on a similarity measure, therefore providing the identification of the blur. To make the restoration process computationally efficient, the Quantization Nearest Neighborhood approaches are utilized.
Determining the quality evaluation procedures using the expert systems
Venue: arXiv cs.OH 2010
Year: 2010

At this time, quality is a strategic instrument of the entities' global management, but it is also a determining element of their competitive spirit. The importance given to quality is abundantly found in the preoccupations of the European Union's Minister Board, by elaborating documents with a high impact over the quality of products/ services in special, and organizations in general. We live in an era, when the evolution of the social life puts the accent more and more on quality, resulted from various processes, at the level of various domains of the economical and social development.
A Modified ck-Secure Sum Protocol for Multi-Party Computation
Venue: arXiv cs.CR 2010
Year: 2010

Secure Multi-Party Computation (SMC) allows multiple parties to compute some function of their inputs without disclosing the actual inputs to one another. Secure sum computation is an easily understood example and the component of the various SMC solutions. Secure sum computation allows parties to compute the sum of their individual inputs without disclosing the inputs to one another. In this paper, we propose a modified version of our ck-Secure Sum protocol with more security when a group of the computing parties conspire to know the data of some party.
Multi-Objective Geometric Programming Problem Being Cost Coefficients as Continous Function with Weighted Mean Method
Venue: arXiv cs.DS 2010
Year: 2010

Geometric programming problems occur frequently in engineering design and management. In multiobjective optimization, the trade-off information between different objective functions is probably the most important piece of information in a solution process to reach the most preferred solution. In this paper we have discussed the basic concepts and principles of multiple objective optimization problems and developed a solution procedure to solve this optimization problem where the cost coefficients are continuous functions using weighted method to obtain the non-inferior solutions.
Word level Script Identification from Bangla and Devanagri Handwritten Texts mixed with Roman Script
Venue: arXiv cs.LG 2010
Year: 2010

India is a multi-lingual country where Roman script is often used alongside different Indic scripts in a text document. To develop a script specific handwritten Optical Character Recognition (OCR) system, it is therefore necessary to identify the scripts of handwritten text correctly. In this paper, we present a system, which automatically separates the scripts of handwritten words from a document, written in Bangla or Devanagri mixed with Roman scripts. In this script separation technique, we first, extract the text lines and words from document pages using a script independent Neighboring Component Analysis technique. Then we have designed a Multi Layer Perceptron (MLP) based classifier for script separation, trained with 8 different wordlevel holistic features. Two equal sized datasets, one with Bangla and Roman scripts and the other with Devanagri and Roman scripts, are prepared for the system evaluation. On respective independent text samples, word-level script identification accuracies of 99.29% and 98.43% are achieved.
An Alternative Proof for the Capacity Region of the Degraded Gaussian MIMO Broadcast Channel
Venue: arXiv cs.IT 2010
Year: 2010

We provide an alternative proof for the capacity region of the degraded Gaussian multiple-input multiple-output (MIMO) broadcast channel. Our proof does not use the channel enhancement technique as opposed to the original proof of Weingertan {\it et. al.} and the alternative proof of Liu {\it et. al}. Our proof starts with the single-letter description of the capacity region of the degraded broadcast channel, and directly evaluates it for the degraded Gaussian MIMO broadcast channel by using two main technical tools. The first one is the generalized de Bruijn identity due to Palomar \emph{et. al.} which provides a connection between the differential entropy and the Fisher information matrix. The second tool we use is an inequality due to Dembo which lower bounds the differential entropy in terms of the Fisher information matrix.