OpenRaiser/Intern-Atlas huggingface dataset:
Vertex Sparsifiers and Abstract Rounding Algorithms
Venue: arXiv cs.DS 2010
Year: 2010

The notion of vertex sparsification is introduced in \cite{M}, where it was shown that for any graph $G = (V, E)$ and a subset of $k$ terminals $K \subset V$, there is a polynomial time algorithm to construct a graph $H = (K, E_H)$ on just the terminal set so that simultaneously for all cuts $(A, K-A)$, the value of the minimum cut in $G$ separating $A$ from $K -A$ is approximately the same as the value of the corresponding cut in $H$. We give the first super-constant lower bounds for how well a cut-sparsifier $H$ can simultaneously approximate all minimum cuts in $G$. We prove a lower bound of $Ω(\log^{1/4} k)$ -- this is polynomially-related to the known upper bound of $O(\log k/\log \log k)$. This is an exponential improvement on the $Ω(\log \log k)$ bound given in \cite{LM} which in fact was for a stronger vertex sparsification guarantee, and did not apply to cut sparsifiers. Despite this negative result, we show that for many natural problems, we do not need to incur a multiplicative penalty for our reduction. We obtain optimal $O(\log k)$-competitive Steiner oblivious routing schemes, which generalize the results in \cite{R}. We also demonstrate that for a wide range of graph packing problems (which includes maximum concurrent flow, maximum multiflow and multicast routing, among others, as a special case), the integrality gap of the linear program is always at most $O(\log k)$ times the integrality gap restricted to trees. This result helps to explain the ubiquity of the $O(\log k)$ guarantees for such problems. Lastly, we use our ideas to give an efficient construction for vertex-sparsifiers that match the current best existential results -- this was previously open. Our algorithm makes novel use of Earth-mover constraints.
A Study of User's Performance and Satisfaction on the Web Based Photo Annotation with Speech Interaction
Venue: arXiv cs.HC 2010
Year: 2010

This paper reports on empirical evaluation study of users' performance and satisfaction with prototype of Web Based speech photo annotation with speech interaction. Participants involved consist of Johor Bahru citizens from various background. They have completed two parts of annotation task; part A involving PhotoASys; photo annotation system with proposed speech interaction and part B involving Microsoft Microsoft Vista Speech Interaction style. They have completed eight tasks for each part including system login and selection of album and photos. Users' performance was recorded using computer screen recording software. Data were captured on the task completion time and subjective satisfaction. Participants need to complete a questionnaire on the subjective satisfaction when the task was completed. The performance data show the comparison between proposed speech interaction and Microsoft Vista Speech interaction applied in photo annotation system, PhotoASys. On average, the reduction in annotation performance time due to using proposed speech interaction style was 64.72% rather than using speech interaction Microsoft Vista style. Data analysis were showed in different statistical significant in annotation performance and subjective satisfaction for both styles of interaction. These results could be used for the next design in related software which involves personal belonging management.
A Novel Rough Set Reduct Algorithm for Medical Domain Based on Bee Colony Optimization
Venue: arXiv cs.LG 2010
Year: 2010

Feature selection refers to the problem of selecting relevant features which produce the most predictive outcome. In particular, feature selection task is involved in datasets containing huge number of features. Rough set theory has been one of the most successful methods used for feature selection. However, this method is still not able to find optimal subsets. This paper proposes a new feature selection method based on Rough set theory hybrid with Bee Colony Optimization (BCO) in an attempt to combat this. This proposed work is applied in the medical domain to find the minimal reducts and experimentally compared with the Quick Reduct, Entropy Based Reduct, and other hybrid Rough Set methods such as Genetic Algorithm (GA), Ant Colony Optimization (ACO) and Particle Swarm Optimization (PSO).
New Quantitative Study for Dissertations Repository System
Venue: arXiv cs.DL 2010
Year: 2010

In the age of technology, the information communication technology becomes very important especially in education field. Students must be allowed to learn anytime, anywhere and at their own place. The facility of library in the university should be developed. In this paper we are going to present new Quantitative Study for Dissertations Repository System and also recommend future application of the approach.
Law-Aware Access Control and its Information Model
Venue: arXiv cs.CR 2010
Year: 2010

Cross-border access to a variety of data such as market information, strategic information, or customer-related information defines the daily business of many global companies, including financial institutions. These companies are obliged by law to keep a data processing legal for all offered services. They need to fulfill different security objectives specified by the legislation. Therefore, they control access to prevent unauthorized users from using data. Those security objectives, for example confidentiality or secrecy, are often defined in the eXtensible Access Control Markup Language that promotes interoperability between different systems. In this paper, we show the necessity of incorporating the requirements of legislation into access control. Based on the work flow in a banking scenario we describe a variety of available contextual information and their interrelations. Different from other access control systems our main focus is on law-compliant cross-border data access. By including legislation directly into access decisions, this lawfulness can be ensured. We also describe our information model to demonstrate how these policies can be implemented into an existing network and how the components and contextual information interrelate. Finally, we outline an event flow for a request made from a remote user exemplifying how such a system decides about access.
Analytical Study on Internet Banking System
Venue: arXiv cs.OH 2010
Year: 2010

The Internet era is a period in the information age in which communication and commerce via the Internet became a central focus for businesses, consumers, government, and the media. The Internet era also marks the convergence of the computer and communications industries and their associated services and products. Nowadays, the availability of the Internet make it widely used for everyday life. In order to led business to success, the business and specially the services should provide comfort use to its costumer. The bank system is one of the most important businesses who may use the website. The using for the web-based systems should contain special requirements to achieve the business goal. Since that the paper will present the functional and non-functional for the web-based banking system.
The State of the Art: Ontology Web-Based Languages: XML Based
Venue: arXiv cs.AI 2010
Year: 2010

Many formal languages have been proposed to express or represent Ontologies, including RDF, RDFS, DAML+OIL and OWL. Most of these languages are based on XML syntax, but with various terminologies and expressiveness. Therefore, choosing a language for building an Ontology is the main step. The main point of choosing language to represent Ontology is based mainly on what the Ontology will represent or be used for. That language should have a range of quality support features such as ease of use, expressive power, compatibility, sharing and versioning, internationalisation. This is because different kinds of knowledge-based applications need different language features. The main objective of these languages is to add semantics to the existing information on the web. The aims of this paper is to provide a good knowledge of existing language and understanding of these languages and how could be used.
An Overview: Extensible Markup Language Technology
Venue: arXiv cs.SE 2010
Year: 2010

XML stands for the Extensible Markup Language. It is a markup language for documents, Nowadays XML is a tool to develop and likely to become a much more common tool for sharing data and store. XML can communicate structured information to other users. In other words, if a group of users agree to implement the same kinds of tags to describe a certain kind of information, XML applications can assist these users in communicating their information in an more robust and efficient manner. XML can make it easier to exchange information between cooperating entities. In this paper we will present the XML technique by fourth factors Strength of XML, XML Parser, XML Goals and Types of XML Parsers.
Advanced Trace Pattern For Computer Intrusion Discovery
Venue: arXiv cs.CR 2010
Year: 2010

The number of crime committed based on the malware intrusion is never ending as the number of malware variants is growing tremendously and the usage of internet is expanding globally. Malicious codes easily obtained and use as one of weapon to gain their objective illegally. Hence, in this research, diverse logs from different OSI layer are explored to identify the traces left on the attacker and victim logs in order to establish worm trace pattern to defending against the attack and help revealing true attacker or victim. For the purpose of this paper, it focused on malware intrusion and traditional worm namely sasser worm variants. The concept of trace pattern is created by fusing the attacker's and victim's perspective. Therefore, the objective of this paper is to propose a general worm trace pattern for attacker's, victim's and multi-step (attacker/victim)'s by combining both perspectives. These three proposed worm trace patterns can be extended into research areas in alert correlation and computer forensic investigation.
Efficient Region-Based Image Querying
Venue: arXiv cs.CV 2010
Year: 2010

Retrieving images from large and varied repositories using visual contents has been one of major research items, but a challenging task in the image management community. In this paper we present an efficient approach for region-based image classification and retrieval using a fast multi-level neural network model. The advantages of this neural model in image classification and retrieval domain will be highlighted. The proposed approach accomplishes its goal in three main steps. First, with the help of a mean-shift based segmentation algorithm, significant regions of the image are isolated. Secondly, color and texture features of each region are extracted by using color moments and 2D wavelets decomposition technique. Thirdly the multi-level neural classifier is trained in order to classify each region in a given image into one of five predefined categories, i.e., "Sky", "Building", "SandnRock", "Grass" and "Water". Simulation results show that the proposed method is promising in terms of classification and retrieval accuracy results. These results compare favorably with the best published results obtained by other state-of-the-art image retrieval techniques.
Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability
Venue: arXiv cs.DS 2010
Year: 2010

We study vertex cut and flow sparsifiers that were recently introduced by Moitra, and Leighton and Moitra. We improve and generalize their results. We give a new polynomial-time algorithm for constructing O(log k / log log k) cut and flow sparsifiers, matching the best existential upper bound on the quality of a sparsifier, and improving the previous algorithmic upper bound of O(log^2 k / log log k). We show that flow sparsifiers can be obtained from linear operators approximating minimum metric extensions. We introduce the notion of (linear) metric extension operators, prove that they exist, and give an exact polynomial-time algorithm for finding optimal operators. We then establish a direct connection between flow and cut sparsifiers and Lipschitz extendability of maps in Banach spaces, a notion studied in functional analysis since 1930s. Using this connection, we prove a lower bound of Omega(sqrt{log k/log log k}) for flow sparsifiers and a lower bound of Omega(sqrt{log k}/log log k) for cut sparsifiers. We show that if a certain open question posed by Ball in 1992 has a positive answer, then there exist \tilde O(sqrt{log k}) cut sparsifiers. On the other hand, any lower bound on cut sparsifiers better than \tilde Omega(sqrt{log k}) would imply a negative answer to this question.
Dynamic Observers for Fault Diagnosis of Timed Systems
Venue: arXiv cs.FL 2010
Year: 2010

In this paper we extend the work on \emph{dynamic ob\-servers} for fault diagnosis to timed automata. We study sensor minimization problems with static observers and then address the problem of computing the most permissive dynamic observer for a system given by a timed automaton.
A Survey on Peer-to-Peer and DHT
Venue: arXiv cs.DC 2010
Year: 2010

Distributed systems with different levels of dependence to central services have been designed and used during recent years. Pure peer-to-peer systems among distributed systems have no dependence on a central resource. DHT is one of the main techniques behind these systems resulting into failure tolerant systems which are also able to isolate continuous changes to the network to a small section of it and therefore making it possible to scale up such networks to millions of nodes. This survey takes a look at P2P in general and DHT algorithms and implementations in more detail.
Cut-Elimination and Proof Search for Bi-Intuitionistic Tense Logic
Venue: arXiv cs.LO 2010
Year: 2010

We consider an extension of bi-intuitionistic logic with the traditional modalities from tense logic Kt. Proof theoretically, this extension is obtained simply by extending an existing sequent calculus for bi-intuitionistic logic with typical inference rules for the modalities used in display logics. As it turns out, the resulting calculus, LBiKt, seems to be more basic than most intuitionistic tense or modal logics considered in the literature, in particular, those studied by Ewald and Simpson, as it does not assume any a priori relationship between the diamond and the box modal operators. We recover Ewald's intuitionistic tense logic and Simpson's intuitionistic modal logic by modularly extending LBiKt with additional structural rules. The calculus LBiKt is formulated in a variant of display calculus, using a form of sequents called nested sequents. Cut elimination is proved for LBiKt, using a technique similar to that used in display calculi. As in display calculi, the inference rules of LBiKt are ``shallow'' rules, in the sense that they act on top-level formulae in a nested sequent. The calculus LBiKt is ill-suited for backward proof search due to the presence of certain structural rules called ``display postulates'' and the contraction rules on arbitrary structures. We show that these structural rules can be made redundant in another calculus, DBiKt, which uses deep inference, allowing one to apply inference rules at an arbitrary depth in a nested sequent. We prove the equivalence between LBiKt and DBiKt and outline a proof search strategy for DBiKt. We also give a Kripke semantics and prove that LBiKt is sound with respect to the semantics, but completeness is still an open problem. We then discuss various extensions of LBiKt.
An Efficient Algorithm For Chinese Postman Walk on Bi-directed de Bruijn Graphs
Venue: arXiv cs.DS 2010
Year: 2010

Sequence assembly from short reads is an important problem in biology. It is known that solving the sequence assembly problem exactly on a bi-directed de Bruijn graph or a string graph is intractable. However finding a Shortest Double stranded DNA string (SDDNA) containing all the k-long words in the reads seems to be a good heuristic to get close to the original genome. This problem is equivalent to finding a cyclic Chinese Postman (CP) walk on the underlying un-weighted bi-directed de Bruijn graph built from the reads. The Chinese Postman walk Problem (CPP) is solved by reducing it to a general bi-directed flow on this graph which runs in O(|E|2 log2(|V |)) time. In this paper we show that the cyclic CPP on bi-directed graphs can be solved without reducing it to bi-directed flow. We present a ?(p(|V | + |E|) log(|V |) + (dmaxp)3) time algorithm to solve the cyclic CPP on a weighted bi-directed de Bruijn graph, where p = max{|{v|din(v) - dout(v) > 0}|, |{v|din(v) - dout(v) < 0}|} and dmax = max{|din(v) - dout(v)}. Our algorithm performs asymptotically better than the bidirected flow algorithm when the number of imbalanced nodes p is much less than the nodes in the bi-directed graph. From our experimental results on various datasets, we have noticed that the value of p/|V | lies between 0.08% and 0.13% with 95% probability.
Distributed Greedy Scheduling for Multihop Wireless Networks
Venue: arXiv cs.NI 2010
Year: 2010

We consider the problem of scheduling in multihop wireless networks subject to interference constraints. We consider a graph based representation of wireless networks, where scheduled links adhere to the K-hop link interference model. We develop a distributed greedy heuristic for this scheduling problem. Further, we show that this distributed greedy heuristic computes the exact same schedule as the centralized greedy heuristic.
Local Termination: theory and practice
Venue: arXiv cs.LO 2010
Year: 2010

The characterisation of termination using well-founded monotone algebras has been a milestone on the way to automated termination techniques, of which we have seen an extensive development over the past years. Both the semantic characterisation and most known termination methods are concerned with global termination, uniformly of all the terms of a term rewriting system (TRS). In this paper we consider local termination, of specific sets of terms within a given TRS. The principal goal of this paper is generalising the semantic characterisation of global termination to local termination. This is made possible by admitting the well-founded monotone algebras to be partial. We also extend our approach to local relative termination. The interest in local termination naturally arises in program verification, where one is probably interested only in sensible inputs, or just wants to characterise the set of inputs for which a program terminates. Local termination will be also be of interest when dealing with a specific class of terms within a TRS that is known to be non-terminating, such as combinatory logic (CL) or a TRS encoding recursive program schemes or Turing machines. We show how some of the well-known techniques for proving global termination, such as stepwise removal of rewrite rules and semantic labelling, can be adapted to the local case. We also describe transformations reducing local to global termination problems. The resulting techniques for proving local termination have in some cases already been automated. One of our applications concerns the characterisation of the terminating S-terms in CL as regular language. Previously this language had already been found via a tedious analysis of the reduction behaviour of S-terms. These findings have now been vindicated by a fully automated and verified proof.
PAC learnability of a concept class under non-atomic measures: a problem by Vidyasagar
Venue: arXiv cs.LG 2010
Year: 2010

In response to a 1997 problem of M. Vidyasagar, we state a necessary and sufficient condition for distribution-free PAC learnability of a concept class $\mathscr C$ under the family of all non-atomic (diffuse) measures on the domain $Ω$. Clearly, finiteness of the classical Vapnik-Chervonenkis dimension of $\mathscr C$ is a sufficient, but no longer necessary, condition. Besides, learnability of $\mathscr C$ under non-atomic measures does not imply the uniform Glivenko-Cantelli property with regard to non-atomic measures. Our learnability criterion is stated in terms of a combinatorial parameter $\VC({\mathscr C}\,{\mathrm{mod}}\,ω_1)$ which we call the VC dimension of $\mathscr C$ modulo countable sets. The new parameter is obtained by ``thickening up'' single points in the definition of VC dimension to uncountable ``clusters''. Equivalently, $\VC(\mathscr C\moddω_1)\leq d$ if and only if every countable subclass of $\mathscr C$ has VC dimension $\leq d$ outside a countable subset of $Ω$. The new parameter can be also expressed as the classical VC dimension of $\mathscr C$ calculated on a suitable subset of a compactification of $Ω$. We do not make any measurability assumptions on $\mathscr C$, assuming instead the validity of Martin's Axiom (MA).
Testing Reactive Probabilistic Processes
Venue: arXiv cs.LO 2010
Year: 2010

We define a testing equivalence in the spirit of De Nicola and Hennessy for reactive probabilistic processes, i.e. for processes where the internal nondeterminism is due to random behaviour. We characterize the testing equivalence in terms of ready-traces. From the characterization it follows that the equivalence is insensitive to the exact moment in time in which an internal probabilistic choice occurs, which is inherent from the original testing equivalence of De Nicola and Hennessy. We also show decidability of the testing equivalence for finite systems for which the complete model may not be known.
Probabilistic Model-Based Safety Analysis
Venue: arXiv cs.LO 2010
Year: 2010

Model-based safety analysis approaches aim at finding critical failure combinations by analysis of models of the whole system (i.e. software, hardware, failure modes and environment). The advantage of these methods compared to traditional approaches is that the analysis of the whole system gives more precise results. Only few model-based approaches have been applied to answer quantitative questions in safety analysis, often limited to analysis of specific failure propagation models, limited types of failure modes or without system dynamics and behavior, as direct quantitative analysis is uses large amounts of computing resources. New achievements in the domain of (probabilistic) model-checking now allow for overcoming this problem. This paper shows how functional models based on synchronous parallel semantics, which can be used for system design, implementation and qualitative safety analysis, can be directly re-used for (model-based) quantitative safety analysis. Accurate modeling of different types of probabilistic failure occurrence is shown as well as accurate interpretation of the results of the analysis. This allows for reliable and expressive assessment of the safety of a system in early design stages.
Feature Construction for Relational Sequence Learning
Venue: arXiv cs.AI 2010
Year: 2010

We tackle the problem of multi-class relational sequence learning using relevant patterns discovered from a set of labelled sequences. To deal with this problem, firstly each relational sequence is mapped into a feature vector using the result of a feature construction method. Since, the efficacy of sequence learning algorithms strongly depends on the features used to represent the sequences, the second step is to find an optimal subset of the constructed features leading to high classification accuracy. This feature selection task has been solved adopting a wrapper approach that uses a stochastic local search algorithm embedding a naive Bayes classifier. The performance of the proposed method applied to a real-world dataset shows an improvement when compared to other established methods, such as hidden Markov models, Fisher kernels and conditional random fields for relational sequences.