OpenRaiser/Intern-Atlas huggingface dataset:
A physically-based particle model of emergent crowd behaviors
Venue: arXiv cs.GR 2010
Year: 2010

This paper presents a modeling process in order to produce a realistic simulation of crowds in the ancient Greek agora of Argos. This place was a social theater in which two kinds of collective phenomena took place: interpersonal interactions (small group discussion and negotiation, etc.) and global collective phenomena, such as flowing and jamming. In this paper, we focus on the second type of collective human phenomena, called non-deliberative emergent crowd phenomena. This is a typical case of collective emergent self-organization. When a great number of individuals move within a confined environment and under a common fate, collective structures appear spontaneously: jamming with inner collapses, organized flowing with queues, curls, and vortices, propagation effects, etc. These are particularly relevant features to enhance the realism - more precisely the "truthfulness" - of models of this kind of collective phenomena. We assume that this truthfulness is strongly associated with the concept of emergence: evolutions are not predetermined by the individual characters, but emerge from the interaction of numerous characters. The evolutions are not repetitive, and evolve on the basis of small changes. This paper demonstrates that the physically-based interacting particles system is an adequate candidate to model emergent crowd effects: it associates a large number of elementary dynamic actors via elementary non-linear dynamic interactions. Our model of the scene is regulated as a large, dynamically coupled network of second order differential automata. We take advantage of symbolic non-photorealistic and efficient visualization to render the style of the person, rather than the person itself. As an artistic representation, NPR reinforces the symbolic acceptance of the scene by the observer, triggering an immediate and intuitive recognition of the scene as a plausible scene from ancient Greece.
Combining Naive Bayes and Decision Tree for Adaptive Intrusion Detection
Venue: arXiv cs.AI 2010
Year: 2010

In this paper, a new learning algorithm for adaptive network intrusion detection using naive Bayesian classifier and decision tree is presented, which performs balance detections and keeps false positives at acceptable level for different types of network attacks, and eliminates redundant attributes as well as contradictory examples from training data that make the detection model complex. The proposed algorithm also addresses some difficulties of data mining such as handling continuous attribute, dealing with missing attribute values, and reducing noise in training data. Due to the large volumes of security audit data as well as the complex and dynamic properties of intrusion behaviours, several data miningbased intrusion detection techniques have been applied to network-based traffic data and host-based data in the last decades. However, there remain various issues needed to be examined towards current intrusion detection systems (IDS). We tested the performance of our proposed algorithm with existing learning algorithms by employing on the KDD99 benchmark intrusion detection dataset. The experimental results prove that the proposed algorithm achieved high detection rates (DR) and significant reduce false positives (FP) for different types of network intrusions using limited computational resources.
Fuzzy Aided Application Layer Semantic Intrusion Detection System - FASIDS
Venue: arXiv cs.CR 2010
Year: 2010

The objective of this is to develop a Fuzzy aided Application layer Semantic Intrusion Detection System (FASIDS) which works in the application layer of the network stack. FASIDS consist of semantic IDS and Fuzzy based IDS. Rule based IDS looks for the specific pattern which is defined as malicious. A non-intrusive regular pattern can be malicious if it occurs several times with a short time interval. For detecting such malicious activities, FASIDS is proposed in this paper. At application layer, HTTP traffic's header and payload are analyzed for possible intrusion. In the proposed misuse detection module, the semantic intrusion detection system works on the basis of rules that define various application layer misuses that are found in the network. An attack identified by the IDS is based on a corresponding rule in the rule-base. An event that doesn't make a 'hit' on the rule-base is given to a Fuzzy Intrusion Detection System (FIDS) for further analysis.
Analysis of the Security of BB84 by Model Checking
Venue: arXiv cs.CR 2010
Year: 2010

Quantum Cryptography or Quantum key distribution (QKD) is a technique that allows the secure distribution of a bit string, used as key in cryptographic protocols. When it was noted that quantum computers could break public key cryptosystems based on number theory extensive studies have been undertaken on QKD. Based on quantum mechanics, QKD offers unconditionally secure communication. Now, the progress of research in this field allows the anticipation of QKD to be available outside of laboratories within the next few years. Efforts are made to improve the performance and reliability of the implemented technologies. But several challenges remain despite this big progress. The task of how to test the apparatuses of QKD For example did not yet receive enough attention. These devises become complex and demand a big verification effort. In this paper we are interested in an approach based on the technique of probabilistic model checking for studying quantum information. Precisely, we use the PRISM tool to analyze the security of BB84 protocol and we are focused on the specific security property of eavesdropping detection. We show that this property is affected by the parameters of quantum channel and the power of eavesdropper.
Security Issues in the Optimized Link State Routing Protocol Version 2 (OLSRV2)
Venue: arXiv cs.NI 2010
Year: 2010

Mobile Ad hoc NETworks (MANETs) are leaving the confines of research laboratories, to find place in real-world deployments. Outside specialized domains (military, vehicular, etc.), city-wide communitynetworks are emerging, connecting regular Internet users with each other, and with the Internet, via MANETs. Growing to encompass more than a handful of "trusted participants", the question of preserving the MANET network connectivity, even when faced with careless or malicious participants, arises, and must be addressed. A first step towards protecting a MANET is to analyze the vulnerabilities of the routing protocol, managing the connectivity. By understanding how the algorithms of the routing protocol operate, and how these can be exploited by those with ill intent, countermeasures can be developed, readying MANETs for wider deployment and use. This paper takes an abstract look at the algorithms that constitute the Optimized Link State Routing Protocol version 2 (OLSRv2), and identifies for each protocol element the possible vulnerabilities and attacks -- in a certain way, provides a "cookbook" for how to best attack an operational OLSRv2 network, or for how to proceed with developing protective countermeasures against these attacks.
A new weakly universal cellular automaton in the 3D hyperbolic space with two states
Venue: arXiv cs.FL 2010
Year: 2010

In this paper, we show a construction of a weakly universal cellular automaton in the 3D hyperbolic space with two states. The cellular automaton is rotation invariant and, moreover, based on a new implementation of a railway circuit in the dodecagrid,the construction is a truly 3D-one.
Using a Skewed Hamming Distance to Speed Up Deterministic Local Search
Venue: arXiv cs.CC 2010
Year: 2010

Schoening presents a simple randomized algorithm for (d,k)-CSP problems with running time (d(k-1)/k)^n poly(n). Here, d is the number of colors, k is the size of the constraints, and n is the number of variables. A derandomized version of this, given by Dantsin et al., achieves a running time of (dk/(k+1))^n poly(n), inferior to Schoening's. We come up with a simple modification of the deterministic algorithm, achieving a running time of (d(k-1)/k * k^d/(k^d-1))^n \poly(n). Though not completely eleminating the gap, this comes very close to the randomized bound for all but very small values of d. Our main idea is to define a graph structure on the set of d colors to speed up local search.
Filling the Gap between Business Process Modeling and Behavior Driven Development
Venue: arXiv cs.SE 2010
Year: 2010

Behavior Driven Development (NORTH, 2006) is a specification technique that is growing in acceptance in the Agile methods communities. BDD allows to securely verify that all functional requirements were treated properly by source code, by connecting the textual description of these requirements to tests. On the other side, the Enterprise Information Systems (EIS) researchers and practitioners defends the use of Business Process Modeling (BPM) to, before defining any part of the system, perform the modeling of the system's underlying business process. Therefore, it can be stated that, in the case of EIS, functional requirements are obtained by identifying Use Cases from the business process models. The aim of this paper is, in a narrower perspective, to propose the use of Finite State Machines (FSM) to model business process and then connect them to the BDD machinery, thus driving better quality for EIS. In a broader perspective, this article aims to provoke a discussion on the mapping of the various BPM notations, since there isn't a real standard for business process modeling (Moller et al., 2007), to BDD. Firstly a historical perspective of the evolution of previous proposals from which this one emerged will be presented, and then the reasons to change from Model Driven Development (MDD) to BDD will be presented also in a historical perspective. Finally the proposal of using FSM, specifically by using UML Statechart diagrams, will be presented, followed by some conclusions.
Little Dragon Two: An efficient Multivariate Public Key Cryptosystem
Venue: arXiv cs.CR 2010
Year: 2010

In 1998 [8], Patarin proposed an efficient cryptosystem called Little Dragon which was a variant a variant of Matsumoto Imai cryptosystem C*. However Patarin latter found that Little Dragon cryptosystem is not secure [8], [3]. In this paper we propose a cryptosystem Little Dragon Two which is as efficient as Little Dragon cryptosystem but secure against all the known attacks. Like Little Dragon cryptosystem the public key of Little Dragon Two is mixed type that is quadratic in plaintext and cipher text variables. So the public key size of Little Dragon Two is equal to Little Dragon Cryptosystem. Our public key algorithm is bijective and can be used for both encryption and signatures.
Compression Rate Method for Empirical Science and Application to Computer Vision
Venue: arXiv cs.CV 2010
Year: 2010

This philosophical paper proposes a modified version of the scientific method, in which large databases are used instead of experimental observations as the necessary empirical ingredient. This change in the source of the empirical data allows the scientific method to be applied to several aspects of physical reality that previously resisted systematic interrogation. Under the new method, scientific theories are compared by instantiating them as compression programs, and examining the codelengths they achieve on a database of measurements related to a phenomenon of interest. Because of the impossibility of compressing random data, "real world" data can only be compressed by discovering and exploiting the empirical structure it exhibits. The method also provides a new way of thinking about two longstanding issues in the philosophy of science: the problem of induction and the problem of demarcation. The second part of the paper proposes to reformulate computer vision as an empirical science of visual reality, by applying the new method to large databases of natural images. The immediate goal of the proposed reformulation is to repair the chronic difficulties in evaluation experienced by the field of computer vision. The reformulation should bring a wide range of benefits, including a substantially increased degree of methodological rigor, the ability to justify complex theories without overfitting, a scalable evaluation paradigm, and the potential to make systematic progress. A crucial argument is that the change is not especially drastic, because most computer vision tasks can be reformulated as specialized image compression techniques. Finally, a concrete proposal is discussed in which a database is produced by recording from a roadside video camera, and compression is achieved by developing a computational understanding of the appearance of moving cars.
Attribute oriented induction with star schema
Venue: arXiv cs.DB 2010
Year: 2010

This paper will propose a novel star schema attribute induction as a new attribute induction paradigm and as improving from current attribute oriented induction. A novel star schema attribute induction will be examined with current attribute oriented induction based on characteristic rule and using non rule based concept hierarchy by implementing both of approaches. In novel star schema attribute induction some improvements have been implemented like elimination threshold number as maximum tuples control for generalization result, there is no ANY as the most general concept, replacement the role concept hierarchy with concept tree, simplification for the generalization strategy steps and elimination attribute oriented induction algorithm. Novel star schema attribute induction is more powerful than the current attribute oriented induction since can produce small number final generalization tuples and there is no ANY in the results.
Query Routing and Processing in Peer-To-Peer Data Sharing Systems
Venue: arXiv cs.DB 2010
Year: 2010

Sharing musical files via the Internet was the essential motivation of early P2P systems. Despite of the great success of the P2P file sharing systems, these systems support only "simple" queries. The focus in such systems is how to carry out an efficient query routing in order to find the nodes storing a desired file. Recently, several research works have been made to extend P2P systems to be able to share data having a fine granularity (i.e. atomic attribute) and to process queries written with a highly expressive language (i.e. SQL). These works have led to the emergence of P2P data sharing systems that represent a new generation of P2P systems and, on the other hand, a next stage in a long period of the database research area. ? The characteristics of P2P systems (e.g. large-scale, node autonomy and instability) make impractical to have a global catalog that represents often an essential component in traditional database systems. Usually, such a catalog stores information about data, schemas and data sources. Query routing and processing are two problems affected by the absence of a global catalog. Locating relevant data sources and generating a close to optimal execution plan become more difficult. In this paper, we concentrate our study on proposed solutions for the both problems. Furthermore, selected case studies of main P2P data sharing systems are analyzed and compared.
A Low Overhead Minimum Process Global Snapshop Collection Algorithm for Mobile Distributed System
Venue: arXiv cs.DC 2010
Year: 2010

Coordinated checkpointing is an effective fault tolerant technique in distributed system as it avoids the domino effect and require minimum storage requirement. Most of the earlier coordinated checkpoint algorithms block their computation during checkpointing and forces minimum-process or non-blocking but forces all nodes to takes checkpoint even though many of them may not be necessary or non-blocking minimum-process but takes useless checkpoints or reduced useless checkpoint but has higher synchronization message overhead or has high checkpoint request propagation time. Hence in mobile distributed systems there is a great need of minimizing the number of communication message and checkpointing overhead as it raise new issues such as mobility, low bandwidth of wireless channels, frequently disconnections, limited battery power and lack of reliable stable storage on mobile nodes. In this paper, we propose a minimum-process coordinated checkpointing algorithm for mobile distributed system where no useless checkpoints are taken, no blocking of processes takes place and enforces a minimum-number of processes to take checkpoints. Our algorithm imposes low memory and computation overheads on MH's and low communication overheads on wireless channels. It avoids awakening of an MH if it is not required to take its checkpoint and has reduced latency time as each process involved in a global checkpoint can forward its own decision directly to the checkpoint initiator.
Eugene Garfield and Algorithmic Historiography: Co-Words, Co-Authors, and Journal Names
Venue: arXiv cs.DL 2010
Year: 2010

Algorithmic historiography was proposed by Eugene Garfield in collaboration with Irving Sher in the 1960s, but further developed only recently into HistCite^{TM} with Alexander Pudovkin. As in history writing, HistCite^{TM} reconstructs by drawing intellectual lineages. In addition to cited references, however, documents can be attributed a multitude of other variables such as title words, keywords, journal names, author names, and even full texts. New developments in multidimensional scaling (MDS) enable us not only to visualize these patterns at each moment of time, but also to animate them over time. Using title words, co-authors, and journal names in Garfield's oeuvre, the method is demonstrated and further developed in this paper (and in the animation at http://www.leydesdorff.net/garfield/animation). The variety and substantive content of the animation enables us to write, visualize, and animate the author's intellectual history.
sTeXIDE: An Integrated Development Environment for sTeX Collections
Venue: arXiv cs.OH 2010
Year: 2010

Authoring documents in MKM formats like OMDoc is a very tedious task. After years of working on a semantically annotated corpus of sTeX documents (GenCS), we identified a set of common, time-consuming subtasks, which can be supported in an integrated authoring environment. We have adapted the modular Eclipse IDE into sTeXIDE, an authoring solution for enhancing productivity in contributing to sTeX based corpora. sTeXIDE supports context-aware command completion, module management, semantic macro retrieval, and theory graph navigation.
Computational Transition at the Uniqueness Threshold
Venue: arXiv cs.CC 2010
Year: 2010

The hardcore model is a model of lattice gas systems which has received much attention in statistical physics, probability theory and theoretical computer science. It is the probability distribution over independent sets $I$ of a graph weighted proportionally to $λ^{|I|}$ with fugacity parameter $λ$. We prove that at the uniqueness threshold of the hardcore model on the $d$-regular tree, approximating the partition function becomes computationally hard on graphs of maximum degree $d$. Specifically, we show that unless NP$=$RP there is no polynomial time approximation scheme for the partition function (the sum of such weighted independent sets) on graphs of maximum degree $d$ for fugacity $λ_c(d) < λ< λ_c(d) + ε(d)$ where $λ_c = \frac{(d-1)^{d-1}}{(d-2)^d}$ is the uniqueness threshold on the $d$-regular tree and $ε(d)>0$. Weitz produced an FPTAS for approximating the partition function when $0<λ< λ_c(d)$ so this result demonstrates that the computational threshold exactly coincides with the statistical physics phase transition thus confirming the main conjecture of [28]. We further analyze the special case of $λ=1, d=6$ and show there is no polynomial time algorithm for approximately counting independent sets on graphs of maximum degree $d= 6$ which is optimal. Our proof is based on specially constructed random bi-partite graphs which act as gadgets in a reduction to MAX-CUT. Building on the second moment method analysis of [28] and combined with an analysis of the reconstruction problem on the tree our proof establishes a strong version of 'replica' method heuristics developed by theoretical physicists. The result establishes the first rigorous correspondence between the hardness of approximate counting and sampling with statistical physics phase transitions.
An Automated Algorithm for Approximation of Temporal Video Data Using Linear B'EZIER Fitting
Venue: arXiv cs.MM 2010
Year: 2010

This paper presents an efficient method for approximation of temporal video data using linear Bezier fitting. For a given sequence of frames, the proposed method estimates the intensity variations of each pixel in temporal dimension using linear Bezier fitting in Euclidean space. Fitting of each segment ensures upper bound of specified mean squared error. Break and fit criteria is employed to minimize the number of segments required to fit the data. The proposed method is well suitable for lossy compression of temporal video data and automates the fitting process of each pixel. Experimental results show that the proposed method yields good results both in terms of objective and subjective quality measurement parameters without causing any blocking artifacts.
A Tree Logic with Graded Paths and Nominals
Venue: arXiv cs.LO 2010
Year: 2010

Regular tree grammars and regular path expressions constitute core constructs widely used in programming languages and type systems. Nevertheless, there has been little research so far on reasoning frameworks for path expressions where node cardinality constraints occur along a path in a tree. We present a logic capable of expressing deep counting along paths which may include arbitrary recursive forward and backward navigation. The counting extensions can be seen as a generalization of graded modalities that count immediate successor nodes. While the combination of graded modalities, nominals, and inverse modalities yields undecidable logics over graphs, we show that these features can be combined in a tree logic decidable in exponential time.
Distributed Creation and Adaptation of Random Scale-Free Overlay Networks
Venue: arXiv cs.NI 2010
Year: 2010

Random scale-free overlay topologies provide a number of properties like for example high resilience against failures of random nodes, small (average) diameter as well as good expansion and congestion characteristics that make them interesting for the use in large-scale distributed systems. A number of these properties have been shown to be influenced by the exponent γof their degree distribution P(k) ~ k^{-γ}. In this article, we present a distributed rewiring scheme that is suitable to effectuate scale-free overlay topologies with an adjustable exponent. The scheme uses a biased random walk strategy to sample new endpoints of edges being rewired and relies on a simple equilibrium model for scale-free networks. The bias of the random walk strategy can be tuned to produce random scale-free networks with arbitrary degree distribution exponents greater than two. We argue that the rewiring strategy can be implemented in a distributed fashion based on a node's information about its immediate neighbors. We present both analytical arguments as well as results that have been obtained using an implementation of the proposed protocol.
A New Framework for Join Product Skew
Venue: arXiv cs.DB 2010
Year: 2010

Different types of data skew can result in load imbalance in the context of parallel joins under the shared nothing architecture. We study one important type of skew, join product skew (JPS). A static approach based on frequency classes is proposed which takes for granted the data distribution of join attribute values. It comes from the observation that the join selectivity can be expressed as a sum of products of frequencies of the join attribute values. As a consequence, an appropriate assignment of join sub-tasks, that takes into consideration the magnitude of the frequency products can alleviate the join product skew. Motivated by the aforementioned remark, we propose an algorithm, called Handling Join Product Skew (HJPS), to handle join product skew.