OpenRaiser/Intern-Atlas huggingface dataset:
A survey on algorithmic aspects of modular decomposition
Venue: arXiv cs.DM 2009
Year: 2009

The modular decomposition is a technique that applies but is not restricted to graphs. The notion of module naturally appears in the proofs of many graph theoretical theorems. Computing the modular decomposition tree is an important preprocessing step to solve a large number of combinatorial optimization problems. Since the first polynomial time algorithm in the early 70's, the algorithmic of the modular decomposition has known an important development. This paper survey the ideas and techniques that arose from this line of research.
Subgraph Sparsification and Nearly Optimal Ultrasparsifiers
Venue: arXiv cs.DM 2009
Year: 2009

We consider a variation of the spectral sparsification problem where we are required to keep a subgraph of the original graph. Formally, given a union of two weighted graphs $G$ and $W$ and an integer $k$, we are asked to find a $k$-edge weighted graph $W_k$ such that $G+W_k$ is a good spectral sparsifer of $G+W$. We will refer to this problem as the subgraph (spectral) sparsification. We present a nontrivial condition on $G$ and $W$ such that a good sparsifier exists and give a polynomial time algorithm to find the sparsifer. %$O(\frac{n}{k})\log n \tilde{O}(\log \log n)$ As a significant application of our technique, we show that for each positive integer $k$, every $n$-vertex weighted graph has an $(n-1+k)$-edge spectral sparsifier with relative condition number at most $\frac{n}{k} \log n \tilde{O}(\log\log n)$ where $\tilde{O}()$ hides lower order terms. Our bound is within a factor of $\tilde{O}(\log \log n)$ from optimal. This nearly settles a question left open by Spielman and Teng about ultrasparsifiers, which is a key component in their nearly linear-time algorithms for solving diagonally dominant symmetric linear systems. We also present another application of our technique to spectral optimization in which the goal is to maximize the algebraic connectivity of a graph (e.g. turn it into an expander) with a limited number of edges.
Maximum-likelihood co-channel interference cancellation with power control for cellular OFDM networks
Venue: arXiv cs.IT 2009
Year: 2009

In cellular Orthogonal Frequency Division Multiplexing (OFDM) networks, Co-Channel Interference (CCI) leads to severe degradation in the BER performance. To solve this problem, Maximum-Likelihood Estimation (MLE) CCI cancellation scheme has been proposed in the literature. MLE CCI cancellation scheme generates weighted replicas of the transmitted signals and selects replica with the smallest Euclidean distance from the received signal. When the received power of the desired and interference signals are nearly the same, the BER performance is degraded. In this paper, we propose an improved MLE CCI canceler with closed-loop Power Control (PC) scheme capable of detecting and combating against the equal received power situation at the Mobile Station (MS) receiver by using the newly introduced parameter Power Ratio (PR). At cell edge where Signal to Interferer Ratio (SIR) is considered to have average value between -5 and 10 dB, computer simulations show that the proposed closed-loop PC scheme has a gain of 7 dB at 28 km/h and about 2 dB at 120 km/h.
Using social annotation and web log to enhance search engine
Venue: arXiv cs.IR 2009
Year: 2009

Search services have been developed rapidly in social Internet. It can help web users easily to find their documents. So that, finding a best method search is always an imagine. This paper would like introduce hybrid method of LPageRank algorithm and Social Sim Rank algorithm. LPageRank is the method using link structure to rank priority of page. It doesn't care content of page and content of query. Therefore, we want to use benefit of social annotations to create the latent semantic association between queries and annotations. This model, we use algorithm SocialPageRank and LPageRank to enhance accuracy of search system. To experiment and evaluate the proposed of the new model, we have used this model for Music Machine Website with their web logs.
A Brief History of Context
Venue: arXiv cs.HC 2009
Year: 2009

Context is a rich concept and is an elusive concept to define. The concept of context has been studied by philosophers, linguists, psychologists, and recently by computer scientists. Within each research community the term context was interpreted in a certain way that is well-suited for their goals, however no attempt was made to define context. In many areas of research in computer science, notably on web-based services, human-computer interaction (HCI), ubiquitous computing applications, and context-aware systems there is a need to provide a formal operational definition of context. In this brief survey an account of the early work on context, as well as the recent work on many working definitions of context, context modeling, and a formalization of context are given. An attempt is made to unify the different context models within the formalization. A brief commentary on the usefulness of the formalization in the development of context-aware and dependable systems is included.
Computation Tree Logic with Deadlock Detection
Venue: arXiv cs.LO 2009
Year: 2009

We study the equivalence relation on states of labelled transition systems of satisfying the same formulas in Computation Tree Logic without the next state modality (CTL-X). This relation is obtained by De Nicola & Vaandrager by translating labelled transition systems to Kripke structures, while lifting the totality restriction on the latter. They characterised it as divergence sensitive branching bisimulation equivalence. We find that this equivalence fails to be a congruence for interleaving parallel composition. The reason is that the proposed application of CTL-X to non-total Kripke structures lacks the expressiveness to cope with deadlock properties that are important in the context of parallel composition. We propose an extension of CTL-X, or an alternative treatment of non-totality, that fills this hiatus. The equivalence induced by our extension is characterised as branching bisimulation equivalence with explicit divergence, which is, moreover, shown to be the coarsest congruence contained in divergence sensitive branching bisimulation equivalence.
Effective Carrier Sensing in CSMA Networks under Cumulative Interference
Venue: arXiv cs.NI 2009
Year: 2009

This paper proposes and investigates the concept of a safe carrier-sensing range that can guarantee interference safe (also termed hidden-node-free) transmissions in CSMA networks under the cumulative interference model. Compared with the safe carrier-sensing range under the commonly assumed but less realistic pairwise interference model, we show that the safe carrier-sensing range required under the cumulative interference model is larger by a constant multiplicative factor. The concept of a safe carrier-sensing range, although amenable to elegant analytical results, is inherently not compatible with the conventional power threshold carrier-sensing mechanism (e.g., that used in IEEE 802.11). Specifically, the absolute power sensed by a node in the conventional mechanism does not contain enough information for it to derive its distances from other concurrent transmitter nodes. We show that, fortunately, a carrier-sensing mechanism called Incremental-Power Carrier-Sensing (IPCS) can realize the carrier-sensing range concept in a simple way. Instead of monitoring the absolute detected power, the IPCS mechanism monitors every increment in the detected power. This means that IPCS can separate the detected power of every concurrent transmitter, and map the power profile to the required distance information.
Matrix Graph Grammars: Transformation of Restrictions
Venue: arXiv cs.DM 2009
Year: 2009

In the Matrix approach to graph transformation we represent simple digraphs and rules with Boolean matrices and vectors, and the rewriting is expressed using Boolean operations only. In previous works, we developed analysis techniques enabling the study of the applicability of rule sequences, their independence, stated reachability and the minimal digraph able to fire a sequence. In [20], graph constraints and application conditions (so-called restrictions) have been studied in detail. In the present contribution we tackle the problem of translating post-conditions into pre-conditions and vice versa. Moreover, we shall see that application conditions can be moved along productions inside a sequence (restriction delocalization). As a practical-theoretical application we show how application conditions allow us to perform multidigraph rewriting (as opposed to simple digraph rewriting) using Matrix Graph Grammars
Design of Intelligent layer for flexible querying in databases
Venue: arXiv cs.DB 2009
Year: 2009

Computer-based information technologies have been extensively used to help many organizations, private companies, and academic and education institutions manage their processes and information systems hereby become their nervous centre. The explosion of massive data sets created by businesses, science and governments necessitates intelligent and more powerful computing paradigms so that users can benefit from this data. Therefore most new-generation database applications demand intelligent information management to enhance efficient interactions between database and the users. Database systems support only a Boolean query model. A selection query on SQL database returns all those tuples that satisfy the conditions in the query.
Performance Metrics Analysis of Torus Embedded Hypercube Interconnection Network
Venue: arXiv cs.NI 2009
Year: 2009

Advantages of hypercube network and torus topology are used to derive an embedded architecture for product network known as torus embedded hypercube scalable interconnection network. This paper analyzes torus embedded hypercube network pertinent to parallel architecture. The network metrics are used to show how good embedded network can be designed for parallel computation. Network parameter analysis and comparison of embedded network with basic networks is presented.
Synthesis of supervised classification algorithm using intelligent and statistical tools
Venue: arXiv cs.CV 2009
Year: 2009

A fundamental task in detecting foreground objects in both static and dynamic scenes is to take the best choice of color system representation and the efficient technique for background modeling. We propose in this paper a non-parametric algorithm dedicated to segment and to detect objects in color images issued from a football sports meeting. Indeed segmentation by pixel concern many applications and revealed how the method is robust to detect objects, even in presence of strong shadows and highlights. In the other hand to refine their playing strategy such as in football, handball, volley ball, Rugby..., the coach need to have a maximum of technical-tactics information about the on-going of the game and the players. We propose in this paper a range of algorithms allowing the resolution of many problems appearing in the automated process of team identification, where each player is affected to his corresponding team relying on visual data. The developed system was tested on a match of the Tunisian national competition. This work is prominent for many next computer vision studies as it's detailed in this study.
Rank Based Clustering For Document Retrieval From Biomedical Databases
Venue: arXiv cs.IR 2009
Year: 2009

Now a day's, search engines are been most widely used for extracting information's from various resources throughout the world. Where, majority of searches lies in the field of biomedical for retrieving related documents from various biomedical databases. Currently search engines lacks in document clustering and representing relativeness level of documents extracted from the databases. In order to overcome these pitfalls a text based search engine have been developed for retrieving documents from Medline and PubMed biomedical databases. The search engine has incorporated page ranking bases clustering concept which automatically represents relativeness on clustering bases. Apart from this graph tree construction is made for representing the level of relatedness of the documents that are networked together. This advance functionality incorporation for biomedical document based search engine found to provide better results in reviewing related documents based on relativeness.
Early Detection of Breast Cancer using SVM Classifier Technique
Venue: arXiv cs.LG 2009
Year: 2009

This paper presents a tumor detection algorithm from mammogram. The proposed system focuses on the solution of two problems. One is how to detect tumors as suspicious regions with a very weak contrast to their background and another is how to extract features which categorize tumors. The tumor detection method follows the scheme of (a) mammogram enhancement. (b) The segmentation of the tumor area. (c) The extraction of features from the segmented tumor area. (d) The use of SVM classifier. The enhancement can be defined as conversion of the image quality to a better and more understandable level. The mammogram enhancement procedure includes filtering, top hat operation, DWT. Then the contrast stretching is used to increase the contrast of the image. The segmentation of mammogram images has been playing an important role to improve the detection and diagnosis of breast cancer. The most common segmentation method used is thresholding. The features are extracted from the segmented breast area. Next stage include, which classifies the regions using the SVM classifier. The method was tested on 75 mammographic images, from the mini-MIAS database. The methodology achieved a sensitivity of 88.75%.
Steganography An Art of Hiding Data
Venue: arXiv cs.CR 2009
Year: 2009

In today's world the art of sending & displaying the hidden information especially in public places, has received more attention and faced many challenges. Therefore, different methods have been proposed so far for hiding information in different cover media. In this paper a method for hiding of information on the billboard display is presented. It is well known that encryption provides secure channels for communicating entities. However, due to lack of covertness on these channels, an eavesdropper can identify encrypted streams through statistical tests and capture them for further cryptanalysis. In this paper we propose a new form of steganography, on-line hiding of information on the output screens of the instrument. This method can be used for announcing a secret message in public place. It can be extended to other means such as electronic advertising board around sports stadium, railway station or airport. This method of steganography is very similar to image steganography and video steganography. Private marking system using symmetric key steganography technique and LSB technique is used here for hiding the secret information.
Faster Algorithms for Finding and Counting Subgraphs
Venue: arXiv cs.DS 2009
Year: 2009

In this paper we study a natural generalization of both {\sc $k$-Path} and {\sc $k$-Tree} problems, namely, the {\sc Subgraph Isomorphism} problem. In the {\sc Subgraph Isomorphism} problem we are given two graphs $F$ and $G$ on $k$ and $n$ vertices respectively as an input, and the question is whether there exists a subgraph of $G$ isomorphic to $F$. We show that if the treewidth of $F$ is at most $t$, then there is a randomized algorithm for the {\sc Subgraph Isomorphism} problem running in time $\cO^*(2^k n^{2t})$. To do so, we associate a new multivariate {Homomorphism polynomial} of degree at most $k$ with the {\sc Subgraph Isomorphism} problem and construct an arithmetic circuit of size at most $n^{\cO(t)}$ for this polynomial. Using this polynomial, we also give a deterministic algorithm to count the number of homomorphisms from $F$ to $G$ that takes $n^{\cO(t)}$ time and uses polynomial space. For the counting version of the {\sc Subgraph Isomorphism} problem, where the objective is to count the number of distinct subgraphs of $G$ that are isomorphic to $F$, we give a deterministic algorithm running in time and space $\cO^*({n \choose k/2}n^{2p})$ or ${n\choose k/2}n^{\cO(t \log k)}$. We also give an algorithm running in time $\cO^{*}(2^{k}{n \choose k/2}n^{5p})$ and taking space polynomial in $n$. Here $p$ and $t$ denote the pathwidth and the treewidth of $F$, respectively. Thus our work not only improves on known results on {\sc Subgraph Isomorphism} but it also extends and generalize most of the known results on {\sc $k$-Path} and {\sc $k$-Tree}.
LAGOVirtual: A Collaborative Environment for the Large Aperture GRB Observatory
Venue: arXiv cs.CE 2009
Year: 2009

We present the LAGOVirtual Project: an ongoing project to develop platform to collaborate in the Large Aperture GRB Observatory (LAGO). This continental-wide observatory is devised to detect high energy (around 100 GeV) component of Gamma Ray Bursts, by using the single particle technique in arrays of Water Cherenkov Detectors (WCD) at high mountain sites (Chacaltaya, Bolivia, 5300 m a.s.l., Pico Espejo, Venezuela, 4750 m a.s.l., Sierra Negra, Mexico, 4650 m a.s.l). This platform will allow LAGO collaboration to share data, and computer resources through its different sites. This environment has the possibility to generate synthetic data by simulating the showers through AIRES application and to store/preserve distributed data files collected by the WCD at the LAGO sites. The present article concerns the implementation of a prototype of LAGO-DR adapting DSpace, with a hierarchical structure (i.e. country, institution, followed by collections that contain the metadata and data files), for the captured/simulated data. This structure was generated by using the community, sub-community, collection, item model; available at the DSpace software. Each member institution-country of the project has the appropriate permissions on the system to publish information (descriptive metadata and associated data files). The platform can also associate multiple files to each item of data (data from the instruments, graphics, postprocessed-data, etc.).
Closing the Learning-Planning Loop with Predictive State Representations
Venue: arXiv cs.LG 2009
Year: 2009

A central problem in artificial intelligence is that of planning to maximize future reward under uncertainty in a partially observable environment. In this paper we propose and demonstrate a novel algorithm which accurately learns a model of such an environment directly from sequences of action-observation pairs. We then close the loop from observations to actions by planning in the learned model and recovering a policy which is near-optimal in the original environment. Specifically, we present an efficient and statistically consistent spectral algorithm for learning the parameters of a Predictive State Representation (PSR). We demonstrate the algorithm by learning a model of a simulated high-dimensional, vision-based mobile robot planning task, and then perform approximate point-based planning in the learned PSR. Analysis of our results shows that the algorithm learns a state space which efficiently captures the essential features of the environment. This representation allows accurate prediction with a small number of parameters, and enables successful and efficient planning.
Distributed Branching Bisimulation Minimization by Inductive Signatures
Venue: arXiv cs.LO 2009
Year: 2009

We present a new distributed algorithm for state space minimization modulo branching bisimulation. Like its predecessor it uses signatures for refinement, but the refinement process and the signatures have been optimized to exploit the fact that the input graph contains no tau-loops. The optimization in the refinement process is meant to reduce both the number of iterations needed and the memory requirements. In the former case we cannot prove that there is an improvement, but our experiments show that in many cases the number of iterations is smaller. In the latter case, we can prove that the worst case memory use of the new algorithm is linear in the size of the state space, whereas the old algorithm has a quadratic upper bound. The paper includes a proof of correctness of the new algorithm and the results of a number of experiments that compare the performance of the old and the new algorithms.
Efficient Parallel Statistical Model Checking of Biochemical Networks
Venue: arXiv cs.CE 2009
Year: 2009

We consider the problem of verifying stochastic models of biochemical networks against behavioral properties expressed in temporal logic terms. Exact probabilistic verification approaches such as, for example, CSL/PCTL model checking, are undermined by a huge computational demand which rule them out for most real case studies. Less demanding approaches, such as statistical model checking, estimate the likelihood that a property is satisfied by sampling executions out of the stochastic model. We propose a methodology for efficiently estimating the likelihood that a LTL property P holds of a stochastic model of a biochemical network. As with other statistical verification techniques, the methodology we propose uses a stochastic simulation algorithm for generating execution samples, however there are three key aspects that improve the efficiency: first, the sample generation is driven by on-the-fly verification of P which results in optimal overall simulation time. Second, the confidence interval estimation for the probability of P to hold is based on an efficient variant of the Wilson method which ensures a faster convergence. Third, the whole methodology is designed according to a parallel fashion and a prototype software tool has been implemented that performs the sampling/verification process in parallel over an HPC architecture.
An Efficient Explicit-time Description Method for Timed Model Checking
Venue: arXiv cs.LO 2009
Year: 2009

Timed model checking, the method to formally verify real-time systems, is attracting increasing attention from both the model checking community and the real-time community. Explicit-time description methods verify real-time systems using general model constructs found in standard un-timed model checkers. Lamport proposed an explicit-time description method using a clock-ticking process (Tick) to simulate the passage of time together with a group of global variables to model time requirements. Two methods, the Sync-based Explicit-time Description Method using rendezvous synchronization steps and the Semaphore-based Explicit-time Description Method using only one global variable were proposed; they both achieve better modularity than Lamport's method in modeling the real-time systems. In contrast to timed automata based model checkers like UPPAAL, explicit-time description methods can access and store the current time instant for future calculations necessary for many real-time systems, especially those with pre-emptive scheduling. However, the Tick process in the above three methods increments the time by one unit in each tick; the state spaces therefore grow relatively fast as the time parameters increase, a problem when the system's time period is relatively long. In this paper, we propose a more efficient method which enables the Tick process to leap multiple time units in one tick. Preliminary experimental results in a high performance computing environment show that this new method significantly reduces the state space and improves both the time and memory efficiency.