OpenRaiser/Intern-Atlas huggingface dataset:
Conscious Intelligent Systems - Part 1 : I X I
Venue: arXiv cs.AI 2006
Year: 2006

Did natural consciousness and intelligent systems arise out of a path that was co-evolutionary to evolution? Can we explain human self-consciousness as having risen out of such an evolutionary path? If so how could it have been? In this first part of a two-part paper (titled IXI), we take a learning system perspective to the problem of consciousness and intelligent systems, an approach that may look unseasonable in this age of fMRI's and high tech neuroscience. We posit conscious intelligent systems in natural environments and wonder how natural factors influence their design paths. Such a perspective allows us to explain seamlessly a variety of natural factors, factors ranging from the rise and presence of the human mind, man's sense of I, his self-consciousness and his looping thought processes to factors like reproduction, incubation, extinction, sleep, the richness of natural behavior, etc. It even allows us to speculate on a possible human evolution scenario and other natural phenomena.
Conscious Intelligent Systems - Part II - Mind, Thought, Language and Understanding
Venue: arXiv cs.AI 2006
Year: 2006

This is the second part of a paper on Conscious Intelligent Systems. We use the understanding gained in the first part (Conscious Intelligent Systems Part 1: IXI (arxiv id cs.AI/0612056)) to look at understanding. We see how the presence of mind affects understanding and intelligent systems; we see that the presence of mind necessitates language. The rise of language in turn has important effects on understanding. We discuss the humanoid question and how the question of self-consciousness (and by association mind/thought/language) would affect humanoids too.
Agile Adoption Process Framework
Venue: arXiv cs.SE 2006
Year: 2006

Today many organizations aspire to adopt agile processes in hope of overcoming some of the difficulties they are facing with their current software development process. There is no structured framework for the agile adoption process. This paper presents a 3-Stage process framework that assists organization and guides organizations through their agile adoption efforts. The Process Framework has been received significantly positive feedback from experts and leaders in agile adoption industry.
Improved results for a memory allocation problem
Venue: arXiv cs.DS 2006
Year: 2006

We consider a memory allocation problem that can be modeled as a version of bin packing where items may be split, but each bin may contain at most two (parts of) items. A 3/2-approximation algorithm and an NP-hardness proof for this problem was given by Chung et al. We give a simpler 3/2-approximation algorithm for it which is in fact an online algorithm. This algorithm also has good performance for the more general case where each bin may contain at most k parts of items. We show that this general case is also strongly NP-hard. Additionally, we give an efficient 7/5-approximation algorithm.
Consistent Streaming Through Time: A Vision for Event Stream Processing
Venue: arXiv cs.DB 2006
Year: 2006

Event processing will play an increasingly important role in constructing enterprise applications that can immediately react to business critical events. Various technologies have been proposed in recent years, such as event processing, data streams and asynchronous messaging (e.g. pub/sub). We believe these technologies share a common processing model and differ only in target workload, including query language features and consistency requirements. We argue that integrating these technologies is the next step in a natural progression. In this paper, we present an overview and discuss the foundations of CEDR, an event streaming system that embraces a temporal stream model to unify and further enrich query language features, handle imperfections in event delivery and define correctness guarantees. We describe specific contributions made so far and outline next steps in developing the CEDR system.
Generalizing the Paige-Tarjan Algorithm by Abstract Interpretation
Venue: arXiv cs.LO 2006
Year: 2006

The Paige and Tarjan algorithm (PT) for computing the coarsest refinement of a state partition which is a bisimulation on some Kripke structure is well known. It is also well known in model checking that bisimulation is equivalent to strong preservation of CTL, or, equivalently, of Hennessy-Milner logic. Drawing on these observations, we analyze the basic steps of the PT algorithm from an abstract interpretation perspective, which allows us to reason on strong preservation in the context of generic inductively defined (temporal) languages and of possibly non-partitioning abstract models specified by abstract interpretation. This leads us to design a generalized Paige-Tarjan algorithm, called GPT, for computing the minimal refinement of an abstract interpretation-based model that strongly preserves some given language. It turns out that PT is a straight instance of GPT on the domain of state partitions for the case of strong preservation of Hennessy-Milner logic. We provide a number of examples showing that GPT is of general use. We first show how a well-known efficient algorithm for computing stuttering equivalence can be viewed as a simple instance of GPT. We then instantiate GPT in order to design a new efficient algorithm for computing simulation equivalence that is competitive with the best available algorithms. Finally, we show how GPT allows to compute new strongly preserving abstract models by providing an efficient algorithm that computes the coarsest refinement of a given partition that strongly preserves the language generated by the reachability operator.
bdbms -- A Database Management System for Biological Data
Venue: arXiv cs.DB 2006
Year: 2006

Biologists are increasingly using databases for storing and managing their data. Biological databases typically consist of a mixture of raw data, metadata, sequences, annotations, and related data obtained from various sources. Current database technology lacks several functionalities that are needed by biological databases. In this paper, we introduce bdbms, an extensible prototype database management system for supporting biological data. bdbms extends the functionalities of current DBMSs to include: (1) Annotation and provenance management including storage, indexing, manipulation, and querying of annotation and provenance as first class objects in bdbms, (2) Local dependency tracking to track the dependencies and derivations among data items, (3) Update authorization to support data curation via content-based authorization, in contrast to identity-based authorization, and (4) New access methods and their supporting operators that support pattern matching on various types of compressed biological data types. This paper presents the design of bdbms along with the techniques proposed to support these functionalities including an extension to SQL. We also outline some open issues in building bdbms.
Architecting Network-Centric Software Systems: A Style-Based Beginning
Venue: arXiv cs.SE 2006
Year: 2006

With the advent of potent network technology, software development has evolved from traditional platform-centric construction to network-centric evolution. This change involves largely the way we reason about systems as evidenced in the introduction of Network- Centric Operations (NCO). Unfortunately, it has resulted in conflicting interpretations of how to map NCO concepts to the field of software architecture. In this paper, we capture the core concepts and goals of NCO, investigate the implications of these concepts and goals on software architecture, and identify the operational characteristics that distinguish network-centric software systems from other systems. More importantly, we use architectural design principles to propose an outline for a network-centric architectural style that helps in characterizing network-centric software systems and that provides a means by which their distinguishing operational characteristics can be realized.
Tales of Huffman
Venue: arXiv cs.IT 2006
Year: 2006

We study the new problem of Huffman-like codes subject to individual restrictions on the code-word lengths of a subset of the source words. These are prefix codes with minimal expected code-word length for a random source where additionally the code-word lengths of a subset of the source words is prescribed, possibly differently for every such source word. Based on a structural analysis of properties of optimal solutions, we construct an efficient dynamic programming algorithm for this problem, and for an integer programming problem that may be of independent interest.
Geometric Complexity Theory II: Towards explicit obstructions for embeddings among class varieties
Venue: arXiv cs.CC 2006
Year: 2006

In part I we reduced the arithmetic (characteristic zero) version of the P \not \subseteq NP conjecture to the problem of showing that a variety associated with the complexity class NP cannot be embedded in the variety associated the complexity class P. We call these class varieties. In this paper, this approach is developed further, reducing the nonexistence problems, such as the P vs. NP and related lower bound problems, to existence problems: specifically to proving existence of obstructions to such embeddings among class varieties. It gives two results towards explicit construction of such obstructions. The first result is a generalization of the Borel-Weil theorem to a class of orbit closures, which include class varieties. The recond result is a weaker form of a conjectured analogue of the second fundamental theorem of invariant theory for the class variety associated with the complexity class NC. These results indicate that the fundamental lower bound problems in complexity theory are intimately linked with explicit construction problems in algebraic geometry and representation theory.
Accommodation of the Service Offered by the Network for Networked Control Systems
Venue: arXiv cs.NI 2006
Year: 2006

Networked Controlled Systems (NCSs) are more and more used in industrial applications. They are strongly connected to real-time constraints because important delays induced by the network can lead to an unstable process control. Usually, the network used in NCSs is shared with many others applications requiring different Quality of Service. The objective of this paper is to optimize the tuning of the network scheduling mechanisms in taking into account the level of Quality of Control. The goal is to maximize the bandwidth allocation for unconstrained frames in guarantying that the control constraints are respected. In this paper, we focus on switched Ethernet network implementing the Classification of Service (IEEE 802.1p) based on a Weighted Round Robin policy.
Experiments on predictability of word in context and information rate in natural language
Venue: arXiv cs.IT 2006
Year: 2006

Based on data from a large-scale experiment with human subjects, we conclude that the logarithm of probability to guess a word in context (unpredictability) depends linearly on the word length. This result holds both for poetry and prose, even though with prose, the subjects don't know the length of the omitted word. We hypothesize that this effect reflects a tendency of natural language to have an even information rate.
On-line Viterbi Algorithm and Its Relationship to Random Walks
Venue: arXiv cs.DS 2007
Year: 2007

In this paper, we introduce the on-line Viterbi algorithm for decoding hidden Markov models (HMMs) in much smaller than linear space. Our analysis on two-state HMMs suggests that the expected maximum memory used to decode sequence of length $n$ with $m$-state HMM can be as low as $Θ(m\log n)$, without a significant slow-down compared to the classical Viterbi algorithm. Classical Viterbi algorithm requires $O(mn)$ space, which is impractical for analysis of long DNA sequences (such as complete human genome chromosomes) and for continuous data streams. We also experimentally demonstrate the performance of the on-line Viterbi algorithm on a simple HMM for gene finding on both simulated and real DNA sequences.
On Punctured Pragmatic Space-Time Codes in Block Fading Channel
Venue: arXiv cs.IT 2007
Year: 2007

This paper considers the use of punctured convolutional codes to obtain pragmatic space-time trellis codes over block-fading channel. We show that good performance can be achieved even when puncturation is adopted and that we can still employ the same Viterbi decoder of the convolutional mother code by using approximated metrics without increasing the complexity of the decoding operations.
On the Achievable Rate Regions for Interference Channels with Degraded Message Sets
Venue: arXiv cs.IT 2007
Year: 2007

The interference channel with degraded message sets (IC-DMS) refers to a communication model in which two senders attempt to communicate with their respective receivers simultaneously through a common medium, and one of the senders has complete and a priori (non-causal) knowledge about the message being transmitted by the other. A coding scheme that collectively has advantages of cooperative coding, collaborative coding, and dirty paper coding, is developed for such a channel. With resorting to this coding scheme, achievable rate regions of the IC-DMS in both discrete memoryless and Gaussian cases are derived, which, in general, include several previously known rate regions. Numerical examples for the Gaussian case demonstrate that in the high-interference-gain regime, the derived achievable rate regions offer considerable improvements over these existing results.
Learning from compressed observations
Venue: arXiv cs.IT 2007
Year: 2007

The problem of statistical learning is to construct a predictor of a random variable $Y$ as a function of a related random variable $X$ on the basis of an i.i.d. training sample from the joint distribution of $(X,Y)$. Allowable predictors are drawn from some specified class, and the goal is to approach asymptotically the performance (expected loss) of the best predictor in the class. We consider the setting in which one has perfect observation of the $X$-part of the sample, while the $Y$-part has to be communicated at some finite bit rate. The encoding of the $Y$-values is allowed to depend on the $X$-values. Under suitable regularity conditions on the admissible predictors, the underlying family of probability distributions and the loss function, we give an information-theoretic characterization of achievable predictor performance in terms of conditional distortion-rate functions. The ideas are illustrated on the example of nonparametric regression in Gaussian noise.
Lessons Learned from the deployment of a high-interaction honeypot
Venue: arXiv cs.CR 2007
Year: 2007

This paper presents an experimental study and the lessons learned from the observation of the attackers when logged on a compromised machine. The results are based on a six months period during which a controlled experiment has been run with a high interaction honeypot. We correlate our findings with those obtained with a worldwide distributed system of lowinteraction honeypots.
Availability assessment of SunOS/Solaris Unix Systems based on Syslogd and wtmpx logfiles : a case study
Venue: arXiv cs.PF 2007
Year: 2007

This paper presents a measurement-based availability assessment study using field data collected during a 4-year period from 373 SunOS/Solaris Unix workstations and servers interconnected through a local area network. We focus on the estimation of machine uptimes, downtimes and availability based on the identification of failures that caused total service loss. Data corresponds to syslogd event logs that contain a large amount of information about the normal activity of the studied systems as well as their behavior in the presence of failures. It is widely recognized that the information contained in such event logs might be incomplete or imperfect. The solution investigated in this paper to address this problem is based on the use of auxiliary sources of data obtained from wtmpx files maintained by the SunOS/Solaris Unix operating system. The results obtained suggest that the combined use of wtmpx and syslogd log files provides more complete information on the state of the target systems that is useful to provide availability estimations that better reflect reality.
A Hierarchical Approach for Dependability Analysis of a Commercial Cache-Based RAID Storage Architecture
Venue: arXiv cs.PF 2007
Year: 2007

We present a hierarchical simulation approach for the dependability analysis and evaluation of a highly available commercial cache-based RAID storage system. The archi-tecture is complex and includes several layers of overlap-ping error detection and recovery mechanisms. Three ab-straction levels have been developed to model the cache architecture, cache operations, and error detection and recovery mechanism. The impact of faults and errors oc-curring in the cache and in the disks is analyzed at each level of the hierarchy. A simulation submodel is associated with each abstraction level. The models have been devel-oped using DEPEND, a simulation-based environment for system-level dependability analysis, which provides facili-ties to inject faults into a functional behavior model, to simulate error detection and recovery mechanisms, and to evaluate quantitative measures. Several fault models are defined for each submodel to simulate cache component failures, disk failures, transmission errors, and data errors in the cache memory and in the disks. Some of the parame-ters characterizing fault injection in a given submodel cor-respond to probabilities evaluated from the simulation of the lower-level submodel. Based on the proposed method-ology, we evaluate and analyze 1) the system behavior un-der a real workload and high error rate (focusing on error bursts), 2) the coverage of the error detection mechanisms implemented in the system and the error latency distribu-tions, and 3) the accumulation of errors in the cache and in the disks.
A neural network approach to ordinal regression
Venue: arXiv cs.LG 2007
Year: 2007

Ordinal regression is an important type of learning, which has properties of both classification and regression. Here we describe a simple and effective approach to adapt a traditional neural network to learn ordinal categories. Our approach is a generalization of the perceptron method for ordinal regression. On several benchmark datasets, our method (NNRank) outperforms a neural network classification method. Compared with the ordinal regression methods using Gaussian processes and support vector machines, NNRank achieves comparable performance. Moreover, NNRank has the advantages of traditional neural networks: learning in both online and batch modes, handling very large training datasets, and making rapid predictions. These features make NNRank a useful and complementary tool for large-scale data processing tasks such as information retrieval, web page ranking, collaborative filtering, and protein ranking in Bioinformatics.
Novel algorithm to calculate hypervolume indicator of Pareto approximation set
Venue: arXiv cs.CG 2007
Year: 2007

Hypervolume indicator is a commonly accepted quality measure for comparing Pareto approximation set generated by multi-objective optimizers. The best known algorithm to calculate it for $n$ points in $d$-dimensional space has a run time of $O(n^{d/2})$ with special data structures. This paper presents a recursive, vertex-splitting algorithm for calculating the hypervolume indicator of a set of $n$ non-comparable points in $d>2$ dimensions. It splits out multiple child hyper-cuboids which can not be dominated by a splitting reference point. In special, the splitting reference point is carefully chosen to minimize the number of points in the child hyper-cuboids. The complexity analysis shows that the proposed algorithm achieves $O((\frac{d}{2})^n)$ time and $O(dn^2)$ space complexity in the worst case.
Parametric Learning and Monte Carlo Optimization
Venue: arXiv cs.LG 2007
Year: 2007

This paper uncovers and explores the close relationship between Monte Carlo Optimization of a parametrized integral (MCO), Parametric machine-Learning (PL), and `blackbox' or `oracle'-based optimization (BO). We make four contributions. First, we prove that MCO is mathematically identical to a broad class of PL problems. This identity potentially provides a new application domain for all broadly applicable PL techniques: MCO. Second, we introduce immediate sampling, a new version of the Probability Collectives (PC) algorithm for blackbox optimization. Immediate sampling transforms the original BO problem into an MCO problem. Accordingly, by combining these first two contributions, we can apply all PL techniques to BO. In our third contribution we validate this way of improving BO by demonstrating that cross-validation and bagging improve immediate sampling. Finally, conventional MC and MCO procedures ignore the relationship between the sample point locations and the associated values of the integrand; only the values of the integrand at those locations are considered. We demonstrate that one can exploit the sample location information using PL techniques, for example by forming a fit of the sample locations to the associated values of the integrand. This provides an additional way to apply PL techniques to improve MCO.
A Disciplined Approach to Adopting Agile Practices: The Agile Adoption Framework
Venue: arXiv cs.SE 2007
Year: 2007

Many organizations aspire to adopt agile processes to take advantage of the numerous benefits that it offers to an organization. Those benefits include, but are not limited to, quicker return on investment, better software quality, and higher customer satisfaction. To date however, there is no structured process (at least in the public domain) that guides organizations in adopting agile practices. To address this problem we present the Agile Adoption Framework. The framework consists of two components: an agile measurement index, and a 4-Stage process, that together guide and assist the agile adoption efforts of organizations. More specifically, the agile measurement index is used to identify the agile potential of projects and organizations. The 4-Stage process, on the other hand, helps determine (a) whether or not organizations are ready for agile adoption, and (b) guided by their potential, what set of agile practices can and should be introduced.
GLRT-Optimal Noncoherent Lattice Decoding
Venue: arXiv cs.IT 2007
Year: 2007

This paper presents new low-complexity lattice-decoding algorithms for noncoherent block detection of QAM and PAM signals over complex-valued fading channels. The algorithms are optimal in terms of the generalized likelihood ratio test (GLRT). The computational complexity is polynomial in the block length; making GLRT-optimal noncoherent detection feasible for implementation. We also provide even lower complexity suboptimal algorithms. Simulations show that the suboptimal algorithms have performance indistinguishable from the optimal algorithms. Finally, we consider block based transmission, and propose to use noncoherent detection as an alternative to pilot assisted transmission (PAT). The new technique is shown to outperform PAT.
On restrictions of balanced 2-interval graphs
Venue: arXiv cs.DM 2007
Year: 2007

The class of 2-interval graphs has been introduced for modelling scheduling and allocation problems, and more recently for specific bioinformatic problems. Some of those applications imply restrictions on the 2-interval graphs, and justify the introduction of a hierarchy of subclasses of 2-interval graphs that generalize line graphs: balanced 2-interval graphs, unit 2-interval graphs, and (x,x)-interval graphs. We provide instances that show that all the inclusions are strict. We extend the NP-completeness proof of recognizing 2-interval graphs to the recognition of balanced 2-interval graphs. Finally we give hints on the complexity of unit 2-interval graphs recognition, by studying relationships with other graph classes: proper circular-arc, quasi-line graphs, K_{1,5}-free graphs, ...