OpenRaiser/Intern-Atlas huggingface dataset:
An Optimization Model for Outlier Detection in Categorical Data
Venue: arXiv cs.DB 2005
Year: 2005

The task of outlier detection is to find small groups of data objects that are exceptional when compared with rest large amount of data. Detection of such outliers is important for many applications such as fraud detection and customer migration. Most existing methods are designed for numeric data. They will encounter problems with real-life applications that contain categorical data. In this paper, we formally define the problem of outlier detection in categorical data as an optimization problem from a global viewpoint. Moreover, we present a local-search heuristic based algorithm for efficiently finding feasible solutions. Experimental results on real datasets and large synthetic datasets demonstrate the superiority of our model and algorithm.
Coarse and Sharp Thresholds of Boolean Constraint Satisfaction Problems
Venue: arXiv cs.DM 2005
Year: 2005

We study threshold properties of random constraint satisfaction problems under a probabilistic model due to Molloy. We give a sufficient condition for the existence of a sharp threshold that leads (for boolean constraints) to a necessary and sufficient for the existence of a sharp threshold in the case where constraint templates are applied with equal probability, solving thus an open problem of Creignou and Daude.
General non-asymptotic and asymptotic formulas in channel resolvability and identification capacity and their application to wire-tap channel
Venue: arXiv cs.IT 2005
Year: 2005

Several non-asymptotic formulas are established in channel resolvability and identification capacity, and they are applied to wire-tap channel. By using these formulas, the $ε$ capacities of the above three problems are considered in the most general setting, where no structural assumptions such as the stationary memoryless property are made on a channel. As a result, we solve an open problem proposed in Han & Verdu and Han. Moreover, we obtain lower bounds of the exponents of error probability and the wire-tapper's information in wire-tap channel.
Effects of variations of load distribution on network performance
Venue: arXiv cs.NI 2005
Year: 2005

This paper is concerned with the characterization of the relationship between topology and traffic dynamics. We use a model of network generation that allows the transition from random to scale free networks. Specifically, we consider three different topological types of network: random, scale-free with γ= 3, scale-free with γ= 2. By using a novel LRD traffic generator, we observe best performance, in terms of transmission rates and delivered packets, in the case of random networks. We show that, even if scale-free networks are characterized by shorter characteristic-path- length (the lower the exponent, the lower the path-length), they show worst performances in terms of communication. We conjecture this could be explained in terms of changes in the load distribution, defined here as the number of shortest paths going through a given vertex. In fact, that distribu- tion is characterized by (i) a decreasing mean (ii) an increas- ing standard deviation, as the networks becomes scale-free (especially scale-free networks with low exponents). The use of a degree-independent server also discriminates against a scale-free structure. As a result, since the model is un- controlled, most packets will go through the same vertices, favoring the onset of congestion.
Resource Bounded Unprovability of Computational Lower Bounds
Venue: arXiv cs.CC 2005
Year: 2005

This paper introduces new notions of asymptotic proofs, PT(polynomial-time)-extensions, PTM(polynomial-time Turing machine)-omega-consistency, etc. on formal theories of arithmetic including PA (Peano Arithmetic). This paper shows that P not= NP (more generally, any super-polynomial-time lower bound in PSPACE) is unprovable in a PTM-omega-consistent theory T, where T is a consistent PT-extension of PA. This result gives a unified view to the existing two major negative results on proving P not= NP, Natural Proofs and relativizable proofs, through the two manners of characterization of PTM-omega-consistency. We also show that the PTM-omega-consistency of T cannot be proven in any PTM-omega-consistent theory S, where S is a consistent PT-extension of T.
The Bandwidth Exchange Architecture
Venue: arXiv cs.NI 2005
Year: 2005

New applications for the Internet such as video on demand, grid computing etc. depend on the availability of high bandwidth connections with acceptable Quality of Service (QoS). There appears to be, therefore, a requirement for a market where bandwidth-related transactions can take place. For this market to be effective, it must be efficient for both the provider (seller) and the user (buyer) of the bandwidth. This implies that: (a) the buyer must have a wide choice of providers that operate in a competitive environment, (b) the seller must be assured that a QoS transaction will be paid by the customer, and (c) the QoS transaction establishment must have low overheads so that it may be used by individual customers without a significant burden to the provider. In order to satisfy these requirements, we propose a framework that allows customers to purchase bandwidth using an open market where providers advertise links and capacities and customers bid for these services. The model is close to that of a commodities market that offers both advance bookings (futures) and a spot market. We explore the mechanisms that can support such a model.
Towards a Group Theoretic Quantum Encryption Scheme Based on Generalized Hidden Subgroup Problem
Venue: arXiv cs.DM 2005
Year: 2005

This paper introduces a completely new approach to encryption based on group theoretic quantum framework. Quantum cryptography has essentially focused only on key distribution and proceeded with classical encryption algorithm with the generated key. Here, we present a first step towards a quantum encryption scheme based on the solution for the hidden subgroup problem. The shared secret key K from QKD evolves as a generator for a subgroup H of a group G, in combination of the plain text data modeled as group elements. The key K helps in regeneration of the plain data on the receiver's side based on subgroup reconstruction. This paper models all quantum computations using group representations. A non-constructive proof is attempted towards the security of the encryption scheme. We also address the issues involved in a such a venture into the realms of Quantum data encryption.
On Extrinsic Information of Good Codes Operating Over Discrete Memoryless Channels
Venue: arXiv cs.IT 2005
Year: 2005

We show that the Extrinsic Information about the coded bits of any good (capacity achieving) code operating over a wide class of discrete memoryless channels (DMC) is zero when channel capacity is below the code rate and positive constant otherwise, that is, the Extrinsic Information Transfer (EXIT) chart is a step function of channel quality, for any capacity achieving code. It follows that, for a common class of iterative receivers where the error correcting decoder must operate at first iteration at rate above capacity (such as in turbo equalization, turbo channel estimation, parallel and serial concatenated coding and the like), classical good codes which achieve capacity over the DMC are not effective and should be replaced by different new ones. Another meaning of the results is that a good code operating at rate above channel capacity falls apart into its individual transmitted symbols in the sense that all the information about a coded transmitted symbol is contained in the corresponding received symbol and no information about it can be inferred from the other received symbols. The binary input additive white Gaussian noise channel is treated in part 1 of this report. Part 2 extends the results to the symmetric binary channel and to the binary erasure channel and provides an heuristic extension to wider class of channel models.
Resource Management Services for a Grid Analysis Environment
Venue: arXiv cs.DC 2005
Year: 2005

Selecting optimal resources for submitting jobs on a computational Grid or accessing data from a data grid is one of the most important tasks of any Grid middleware. Most modern Grid software today satisfies this responsibility and gives a best-effort performance to solve this problem. Almost all decisions regarding scheduling and data access are made by the software automatically, giving users little or no control over the entire process. To solve this problem, a more interactive set of services and middleware is desired that provides users more information about Grid weather, and gives them more control over the decision making process. This paper presents a set of services that have been developed to provide more interactive resource management capabilities within the Grid Analysis Environment (GAE) being developed collaboratively by Caltech, NUST and several other institutes. These include a steering service, a job monitoring service and an estimator service that have been designed and written using a common Grid-enabled Web Services framework named Clarens. The paper also presents a performance analysis of the developed services to show that they have indeed resulted in a more interactive and powerful system for user-centric Grid-enabled physics analysis.
Scientific impact quantity and quality: Analysis of two sources of bibliographic data
Venue: arXiv cs.IR 2005
Year: 2005

Attempts to understand the consequence of any individual scientist's activity within the long-term trajectory of science is one of the most difficult questions within the philosophy of science. Because scientific publications play such as central role in the modern enterprise of science, bibliometric techniques which measure the ``impact'' of an individual publication as a function of the number of citations it receives from subsequent authors have provided some of the most useful empirical data on this question. Until recently, Thompson/ISI has provided the only source of large-scale ``inverted'' bibliographic data of the sort required for impact analysis. In the end of 2004, Google introduced a new service, GoogleScholar, making much of this same data available. Here we analyze 203 publications, collectively cited by more than 4000 other publications. We show surprisingly good agreement between data citation counts provided by the two services. Data quality across the systems is analyzed, and potentially useful complementarities between are considered. The additional robustness offered by multiple sources of such data promises to increase the utility of these measurements as open citation protocols and open access increase their impact on electronic scientific publication practices.
DTN Routing in a Mobility Pattern Space
Venue: arXiv cs.NI 2005
Year: 2005

Routing in Delay Tolerant Networks (DTNs) benefits considerably if one can take advantage of knowledge concerning node mobility. The main contribution of this paper is the definition of a generic routing scheme for DTNs using a high-dimensional Euclidean space constructed upon nodes' mobility patterns. For example, nodes are represented as points having as coordinates their probability of being found in each possible location. We present simulation results indicating that such a scheme can be beneficial in a scenario inspired by studies done on real mobility traces. This work should open the way to further use of the virtual space formalism in DTN routing.
Analyzing Worms and Network Traffic using Compression
Venue: arXiv cs.CR 2005
Year: 2005

Internet worms have become a widespread threat to system and network operations. In order to fight them more efficiently, it is necessary to analyze newly discovered worms and attack patterns. This paper shows how techniques based on Kolmogorov Complexity can help in the analysis of internet worms and network traffic. Using compression, different species of worms can be clustered by type. This allows us to determine whether an unknown worm binary could in fact be a later version of an existing worm in an extremely simple, automated, manner. This may become a useful tool in the initial analysis of malicious binaries. Furthermore, compression can also be useful to distinguish different types of network traffic and can thus help to detect traffic anomalies: Certain anomalies may be detected by looking at the compressibility of a network session alone. We furthermore show how to use compression to detect malicious network sessions that are very similar to known intrusion attempts. This technique could become a useful tool to detect new variations of an attack and thus help to prevent IDS evasion. We provide two new plugins for Snort which demonstrate both approaches.
Pushdown dimension
Venue: arXiv cs.IT 2005
Year: 2005

This paper develops the theory of pushdown dimension and explores its relationship with finite-state dimension. Pushdown dimension is trivially bounded above by finite-state dimension for all sequences, since a pushdown gambler can simulate any finite-state gambler. We show that for every rational 0 < d < 1, there exists a sequence with finite-state dimension d whose pushdown dimension is at most d/2. This establishes a quantitative analogue of the well-known fact that pushdown automata decide strictly more languages than finite automata.
Diagnostic Rule Extraction Using Neural Networks
Venue: arXiv cs.NE 2005
Year: 2005

The neural networks have trained on incomplete sets that a doctor could collect. Trained neural networks have correctly classified all the presented instances. The number of intervals entered for encoding the quantitative variables is equal two. The number of features as well as the number of neurons and layers in trained neural networks was minimal. Trained neural networks are adequately represented as a set of logical formulas that more comprehensible and easy-to-understand. These formulas are as the syndrome-complexes, which may be easily tabulated and represented as a diagnostic table that the doctors usually use. Decision rules provide the evaluations of their confidence in which interested a doctor. Conducted clinical researches have shown that iagnostic decisions produced by symbolic rules have coincided with the doctor's conclusions.
A Neural Network Decision Tree for Learning Concepts from EEG Data
Venue: arXiv cs.NE 2005
Year: 2005

To learn the multi-class conceptions from the electroencephalogram (EEG) data we developed a neural network decision tree (DT), that performs the linear tests, and a new training algorithm. We found that the known methods fail inducting the classification models when the data are presented by the features some of them are irrelevant, and the classes are heavily overlapped. To train the DT, our algorithm exploits a bottom up search of the features that provide the best classification accuracy of the linear tests. We applied the developed algorithm to induce the DT from the large EEG dataset consisted of 65 patients belonging to 16 age groups. In these recordings each EEG segment was represented by 72 calculated features. The DT correctly classified 80.8% of the training and 80.1% of the testing examples. Correspondingly it correctly classified 89.2% and 87.7% of the EEG recordings.
Estimating Classification Uncertainty of Bayesian Decision Tree Technique on Financial Data
Venue: arXiv cs.AI 2005
Year: 2005

Bayesian averaging over classification models allows the uncertainty of classification outcomes to be evaluated, which is of crucial importance for making reliable decisions in applications such as financial in which risks have to be estimated. The uncertainty of classification is determined by a trade-off between the amount of data available for training, the diversity of a classifier ensemble and the required performance. The interpretability of classification models can also give useful information for experts responsible for making reliable classifications. For this reason Decision Trees (DTs) seem to be attractive classification models. The required diversity of the DT ensemble can be achieved by using the Bayesian model averaging all possible DTs. In practice, the Bayesian approach can be implemented on the base of a Markov Chain Monte Carlo (MCMC) technique of random sampling from the posterior distribution. For sampling large DTs, the MCMC method is extended by Reversible Jump technique which allows inducing DTs under given priors. For the case when the prior information on the DT size is unavailable, the sweeping technique defining the prior implicitly reveals a better performance. Within this Chapter we explore the classification uncertainty of the Bayesian MCMC techniques on some datasets from the StatLog Repository and real financial data. The classification uncertainty is compared within an Uncertainty Envelope technique dealing with the class posterior distribution and a given confidence probability. This technique provides realistic estimates of the classification uncertainty which can be easily interpreted in statistical terms with the aim of risk evaluation.
Prediction of Large Alphabet Processes and Its Application to Adaptive Source Coding
Venue: arXiv cs.IT 2005
Year: 2005

The problem of predicting a sequence $x_1,x_2,...$ generated by a discrete source with unknown statistics is considered. Each letter $x_{t+1}$ is predicted using information on the word $x_1x_2... x_t$ only. In fact, this problem is a classical problem which has received much attention. Its history can be traced back to Laplace. We address the problem where each $x_i$ belongs to some large (or even infinite) alphabet. A method is presented for which the precision is greater than for known algorithms, where precision is estimated by the Kullback-Leibler divergence. The results can readily be translated to results about adaptive coding.
A Decomposition Approach to Multi-Vehicle Cooperative Control
Venue: arXiv cs.RO 2005
Year: 2005

We present methods that generate cooperative strategies for multi-vehicle control problems using a decomposition approach. By introducing a set of tasks to be completed by the team of vehicles and a task execution method for each vehicle, we decomposed the problem into a combinatorial component and a continuous component. The continuous component of the problem is captured by task execution, and the combinatorial component is captured by task assignment. In this paper, we present a solver for task assignment that generates near-optimal assignments quickly and can be used in real-time applications. To motivate our methods, we apply them to an adversarial game between two teams of vehicles. One team is governed by simple rules and the other by our algorithms. In our study of this game we found phase transitions, showing that the task assignment problem is most difficult to solve when the capabilities of the adversaries are comparable. Finally, we implement our algorithms in a multi-level architecture with a variable replanning rate at each level to provide feedback on a dynamically changing and uncertain environment.
The Convergence of Digital-Libraries and the Peer-Review Process
Venue: arXiv cs.DL 2005
Year: 2005

Pre-print repositories have seen a significant increase in use over the past fifteen years across multiple research domains. Researchers are beginning to develop applications capable of using these repositories to assist the scientific community above and beyond the pure dissemination of information. The contribution set forth by this paper emphasizes a deconstructed publication model in which the peer-review process is mediated by an OAI-PMH peer-review service. This peer-review service uses a social-network algorithm to determine potential reviewers for a submitted manuscript and for weighting the relative influence of each participating reviewer's evaluations. This paper also suggests a set of peer-review specific metadata tags that can accompany a pre-print's existing metadata record. The combinations of these contributions provide a unique repository-centric peer-review model that fits within the widely deployed OAI-PMH framework.
Universal Similarity
Venue: arXiv cs.IR 2005
Year: 2005

We survey a new area of parameter-free similarity distance measures useful in data-mining, pattern recognition, learning and automatic semantics extraction. Given a family of distances on a set of objects, a distance is universal up to a certain precision for that family if it minorizes every distance in the family between every two objects in the set, up to the stated precision (we do not require the universal distance to be an element of the family). We consider similarity distances for two types of objects: literal objects that as such contain all of their meaning, like genomes or books, and names for objects. The latter may have literal embodyments like the first type, but may also be abstract like ``red'' or ``christianity.'' For the first type we consider a family of computable distance measures corresponding to parameters expressing similarity according to particular features between pairs of literal objects. For the second type we consider similarity distances generated by web users corresponding to particular semantic relations between the (names for) the designated objects. For both families we give universal similarity distance measures, incorporating all particular distance measures in the family. In the first case the universal distance is based on compression and in the second case it is based on Google page counts related to search terms. In both cases experiments on a massive scale give evidence of the viability of the approaches.
A Probabilistic Upper Bound on Differential Entropy
Venue: arXiv cs.IT 2005
Year: 2005

A novel, non-trivial, probabilistic upper bound on the entropy of an unknown one-dimensional distribution, given the support of the distribution and a sample from that distribution, is presented. No knowledge beyond the support of the unknown distribution is required, nor is the distribution required to have a density. Previous distribution-free bounds on the cumulative distribution function of a random variable given a sample of that variable are used to construct the bound. A simple, fast, and intuitive algorithm for computing the entropy bound from a sample is provided.
A Multi-proxy Signature Scheme for Partial delegation with Warrant
Venue: arXiv cs.CR 2005
Year: 2005

In some cases, the original signer may delegate its signing power to a specified proxy group while ensuring individual accountability of each participantsigner. The proxy signature scheme that achieves such purpose is called the multi-proxy signature scheme and the signature generated by the specified proxy group is called multi-proxy signature for the original signer. Recently such scheme has been discussed by Lin et al. Lins scheme is based on partial delegation by Mambo et al. In present chapter we introduce a new multi-proxy signature scheme, which requires less computational overhead in comparison to Lin et al, and also fulfill the requirement of partial delegation with warrant simultaneously.
ID-based Ring Signature and Proxy Ring Signature Schemes from Bilinear Pairings
Venue: arXiv cs.CR 2005
Year: 2005

In 2001, Rivest et al. firstly introduced the concept of ring signatures. A ring signature is a simplified group signature without any manager. It protects the anonymity of a signer. The first scheme proposed by Rivest et al. was based on RSA cryptosystem and certificate based public key setting. The first ring signature scheme based on DLP was proposed by Abe, Ohkubo, and Suzuki. Their scheme is also based on the general certificate-based public key setting too. In 2002, Zhang and Kim proposed a new ID-based ring signature scheme using pairings. Later Lin and Wu proposed a more efficient ID-based ring signature scheme. Both these schemes have some inconsistency in computational aspect. In this paper we propose a new ID-based ring signature scheme and a proxy ring signature scheme. Both the schemes are more efficient than existing one. These schemes also take care of the inconsistencies in above two schemes.