OpenRaiser/Intern-Atlas huggingface dataset:
A Flexible Structured-based Representation for XML Document Mining
Venue: arXiv cs.IR 2006
Year: 2006

This paper reports on the INRIA group's approach to XML mining while participating in the INEX XML Mining track 2005. We use a flexible representation of XML documents that allows taking into account the structure only or both the structure and content. Our approach consists of representing XML documents by a set of their sub-paths, defined according to some criteria (length, root beginning, leaf ending). By considering those sub-paths as words, we can use standard methods for vocabulary reduction, and simple clustering methods such as K-means that scale well. We actually use an implementation of the clustering algorithm known as "dynamic clouds" that can work with distinct groups of independent variables put in separate variables. This is useful in our model since embedded sub-paths are not independent: we split potentially dependant paths into separate variables, resulting in each of them containing independant paths. Experiments with the INEX collections show good results for the structure-only collections, but our approach could not scale well for large structure-and-content collections.
Path-independent load balancing with unreliable machines
Venue: arXiv cs.DS 2006
Year: 2006

We consider algorithms for load balancing on unreliable machines. The objective is to optimize the two criteria of minimizing the makespan and minimizing job reassignments in response to machine failures. We assume that the set of jobs is known in advance but that the pattern of machine failures is unpredictable. Motivated by the requirements of BGP routing, we consider path-independent algorithms, with the property that the job assignment is completely determined by the subset of available machines and not the previous history of the assignments. We examine first the question of performance measurement of path-independent load-balancing algorithms, giving the measure of makespan and the normalized measure of reassignments cost. We then describe two classes of algorithms for optimizing these measures against an oblivious adversary for identical machines. The first, based on independent random assignments, gives expected reassignment costs within a factor of 2 of optimal and gives a makespan within a factor of O(log m/log log m) of optimal with high probability, for unknown job sizes. The second, in which jobs are first grouped into bins and at most one bin is assigned to each machine, gives constant-factor ratios on both reassignment cost and makespan, for known job sizes. Several open problems are discussed.
Quasi-Optimal Leader Election Algorithms in Radio Networks with Loglogarithmic Awake Time Slots
Venue: arXiv cs.DC 2006
Year: 2006

A radio network (RN) is a distributed system consisting of $n$ radio stations. We design and analyze two distributed leader election protocols in RN where the number $n$ of radio stations is unknown. The first algorithm runs under the assumption of {\it limited collision detection}, while the second assumes that {\it no collision detection} is available. By ``limited collision detection'', we mean that if exactly one station sends (broadcasts) a message, then all stations (including the transmitter) that are listening at this moment receive the sent message. By contrast, the second no-collision-detection algorithm assumes that a station cannot simultaneously send and listen signals. Moreover, both protocols allow the stations to keep asleep as long as possible, thus minimizing their awake time slots (such algorithms are called {\it energy-efficient}). Both randomized protocols in RN areshown to elect a leader in $O(\log{(n)})$ expected time, with no station being awake for more than $O(\log{\log{(n)}})$ time slots. Therefore, a new class of efficient algorithms is set up that match the $Ω(\log{(n)})$ time lower-bound established by Kushilevitz and Mansour.
Towards a classical proof of exponential lower bound for 2-probe smooth codes
Venue: arXiv cs.CR 2006
Year: 2006

Let C: {0,1}^n -> {0,1}^m be a code encoding an n-bit string into an m-bit string. Such a code is called a (q, c, e) smooth code if there exists a decoding algorithm which while decoding any bit of the input, makes at most q probes on the code word and the probability that it looks at any location is at most c/m. The error made by the decoding algorithm is at most e. Smooth codes were introduced by Katz and Trevisan in connection with Locally decodable codes. For 2-probe smooth codes Kerenedis and de Wolf have shown exponential in n lower bound on m in case c and e are constants. Their lower bound proof went through quantum arguments and interestingly there is no completely classical argument as yet for the same (albeit completely classical !) statement. We do not match the bounds shown by Kerenedis and de Wolf but however show the following. Let C: {0,1}^n -> {0,1}^m be a (2,c,e) smooth code and if e <= c^2/8n^2, then m >= 2^(n/320c^2 - 1)$. We hope that the arguments and techniques used in this paper extend (or are helpful in making similar other arguments), to match the bounds shown using quantum arguments. More so, hopefully they extend to show bounds for codes with greater number of probes where quantum arguments unfortunately do not yield good bounds (even for 3-probe codes).
Secure Component Deployment in the OSGi(tm) Release 4 Platform
Venue: arXiv cs.CR 2006
Year: 2006

Last years have seen a dramatic increase in the use of component platforms, not only in classical application servers, but also more and more in the domain of Embedded Systems. The OSGi(tm) platform is one of these platforms dedicated to lightweight execution environments, and one of the most prominent. However, new platforms also imply new security flaws, and a lack of both knowledge and tools for protecting the exposed systems. This technical report aims at fostering the understanding of security mechanisms in component deployment. It focuses on securing the deployment of components. It presents the cryptographic mechanisms necessary for signing OSGi(tm) bundles, as well as the detailed process of bundle signature and validation. We also present the SFelix platform, which is a secure extension to Felix OSGi(tm) framework implementation. It includes our implementation of the bundle signature process, as specified by OSGi(tm) Release 4 Security Layer. Moreover, a tool for signing and publishing bundles, SFelix JarSigner, has been developed to conveniently integrate bundle signature in the bundle deployment process.
The Average Size of Giant Components Between the Double-Jump
Venue: arXiv cs.DM 2006
Year: 2006

We study the sizes of connected components according to their excesses during a random graph process built with $n$ vertices. The considered model is the continuous one defined in Janson 2000. An ${\ell}$-component is a connected component with ${\ell}$ edges more than vertices. $\ell$ is also called the \textit{excess} of such component. As our main result, we show that when $\ell$ and ${n \over \ell}$ are both large, the expected number of vertices that ever belong to an $\ell$-component is about ${12}^{1/3} {\ell}^{1/3} n^{2/3}$. We also obtain limit theorems for the number of creations of $\ell$-components.
On Some Peculiarities of Dynamic Switch between Component Implementations in an Autonomic Computing System
Venue: arXiv cs.DS 2006
Year: 2006

Behavior of the delta algorithm of autonomic switch between two component implementations is considered on several examples of a client-server systems involving, in particular, periodic change of intensities of requests for the component. It is shown that in the cases of some specific combinations of elementary requests costs, the number of clients in the system, the number of requests per unit of time, and the cost of switch between the implementations, the algorithm may reveal behavior that is rather far from the desired. A sufficient criterion of a success of the algorithm is proposed based on the analysis of the accumulated implementations costs difference as a function of time. Suggestions are pointed out of practical evaluation of the algorithm functioning regarding the observations made in this paper.
How to Find Good Finite-Length Codes: From Art Towards Science
Venue: arXiv cs.IT 2006
Year: 2006

We explain how to optimize finite-length LDPC codes for transmission over the binary erasure channel. Our approach relies on an analytic approximation of the erasure probability. This is in turn based on a finite-length scaling result to model large scale erasures and a union bound involving minimal stopping sets to take into account small error events. We show that the performances of optimized ensembles as observed in simulations are well described by our approximation. Although we only address the case of transmission over the binary erasure channel, our method should be applicable to a more general setting.
Generalized h-index for Disclosing Latent Facts in Citation Networks
Venue: arXiv cs.DL 2006
Year: 2006

What is the value of a scientist and its impact upon the scientific thinking? How can we measure the prestige of a journal or of a conference? The evaluation of the scientific work of a scientist and the estimation of the quality of a journal or conference has long attracted significant interest, due to the benefits from obtaining an unbiased and fair criterion. Although it appears to be simple, defining a quality metric is not an easy task. To overcome the disadvantages of the present metrics used for ranking scientists and journals, J.E. Hirsch proposed a pioneering metric, the now famous h-index. In this article, we demonstrate several inefficiencies of this index and develop a pair of generalizations and effective variants of it to deal with scientist ranking and with publication forum ranking. The new citation indices are able to disclose trendsetters in scientific research, as well as researchers that constantly shape their field with their influential work, no matter how old they are. We exhibit the effectiveness and the benefits of the new indices to unfold the full potential of the h-index, with extensive experimental results obtained from DBLP, a widely known on-line digital library.
The B-Exponential Map: A Generalization of the Logistic Map, and Its Applications In Generating Pseudo-random Numbers
Venue: arXiv cs.CR 2006
Year: 2006

A 1-dimensional generalization of the well known Logistic Map is proposed. The proposed family of maps is referred to as the B-Exponential Map. The dynamics of this map are analyzed and found to have interesting properties. In particular, the B-Exponential Map exhibits robust chaos for all real values of the parameter B >= e^(-4). We then propose a pseudo-random number generator based on the B-Exponential Map by chaotically hopping between different trajectories for different values of B. We call this BEACH (B-Exponential All-Chaotic Map Hopping) pseudo-random number generator. BEACH successfully passes stringent statistical randomness tests such as ENT, NIST and Diehard. An implementation of BEACH is also outlined.
Citation as a Representation Process
Venue: arXiv cs.DL 2006
Year: 2006

The presented work proposes a novel approach to model the citation rate. The paper begins with a brief introduction into informetrics studies and highlights drawbacks of the contemporary approaches to modeling the citation process as a product of social interactions. An alternative modeling framework based on results obtained in cognitive psychology is then introduced and applied in an experiment to investigate properties of the citation process, as they are revealed by a large collection of citation statistics. Major research findings are discussed, and a summary is given.
Effect of Interface Style in Peer Review Comments for UML Designs
Venue: arXiv cs.HC 2006
Year: 2006

This paper presents our evaluation of using a Tablet-PC to provide peer-review comments in the first year Computer Science course. Our exploration consisted of an evaluation of how students write comments on other students' assignments using three different methods: pen and paper, a Tablet-PC, and a desktop computer. Our ultimate goal is to explore the effect that interface style (Tablet vs. Desktop) has on the quality and quantity of the comments provided.
On Construction of the (24,12,8) Golay Codes
Venue: arXiv cs.IT 2006
Year: 2006

Two product array codes are used to construct the (24, 12, 8) binary Golay code through the direct sum operation. This construction provides a systematic way to find proper (8, 4, 4) linear block component codes for generating the Golay code, and it generates and extends previously existing methods that use a similar construction framework. The code constructed is simple to decode.
Mathematical Modelling of the Thermal Accumulation in Hot Water Solar Systems
Venue: arXiv cs.CE 2006
Year: 2006

Mathematical modelling and defining useful recommendations for construction and regimes of exploitation for hot water solar installation with thermal stratification is the main purpose of this work. A special experimental solar module for hot water was build and equipped with sufficient measure apparatus. The main concept of investigation is to optimise the stratified regime of thermal accumulation and constructive parameters of heat exchange equipment (heat serpentine in tank). Accumulation and heat exchange processes were investigated by theoretical end experimental means. Special mathematical model was composed to simulate the energy transfer in stratified tank. Computer program was developed to solve mathematical equations for thermal accumulation and energy exchange. Extensive numerical and experimental tests were carried out. A good correspondence between theoretical and experimental data was arrived. Keywords: Mathematical modelling, accumulation
Dynamic Packet Aggregation to Solve Performance Anomaly in 802.11 Wireless Networks
Venue: arXiv cs.NI 2006
Year: 2006

In the widely used 802.11 standard, the so called performance anomaly is a well known issue. Several works have tried to solve this problem by introducing mechanisms such as packet fragmentation, backoff adaptation, or packet aggregation during a fixed time interval. In this paper, we propose a novel approach solving the performance anomaly problem by packet aggregation using a dynamic time interval, which depends on the busy time of the wireless medium. Our solution differs from other proposition in the literature because of this dynamic time interval, which allows increasing fairness, reactivity, and in some cases efficiency. In this article, we emphasize the performance evaluation of our proposal.
List decoding of noisy Reed-Muller-like codes
Venue: arXiv cs.DS 2006
Year: 2006

First- and second-order Reed-Muller (RM(1) and RM(2), respectively) codes are two fundamental error-correcting codes which arise in communication as well as in probabilistically-checkable proofs and learning. In this paper, we take the first steps toward extending the quick randomized decoding tools of RM(1) into the realm of quadratic binary and, equivalently, Z_4 codes. Our main algorithmic result is an extension of the RM(1) techniques from Goldreich-Levin and Kushilevitz-Mansour algorithms to the Hankel code, a code between RM(1) and RM(2). That is, given signal s of length N, we find a list that is a superset of all Hankel codewords phi with dot product to s at least (1/sqrt(k)) times the norm of s, in time polynomial in k and log(N). We also give a new and simple formulation of a known Kerdock code as a subcode of the Hankel code. As a corollary, we can list-decode Kerdock, too. Also, we get a quick algorithm for finding a sparse Kerdock approximation. That is, for k small compared with 1/sqrt{N} and for epsilon > 0, we find, in time polynomial in (k log(N)/epsilon), a k-Kerdock-term approximation s~ to s with Euclidean error at most the factor (1+epsilon+O(k^2/sqrt{N})) times that of the best such approximation.
UCLog+ : A Security Data Management System for Correlating Alerts, Incidents, and Raw Data From Remote Logs
Venue: arXiv cs.CR 2006
Year: 2006

Source data for computer network security analysis takes different forms (alerts, incidents, logs) and each source may be voluminous. Due to the challenge this presents for data management, this has often lead to security stovepipe operations which focus primarily on a small number of data sources for analysis with little or no automated correlation between data sources (although correlation may be done manually). We seek to address this systemic problem. In previous work we developed a unified correlated logging system (UCLog) that automatically processes alerts from different devices. We take this work one step further by presenting the architecture and applications of UCLog+ which adds the new capability to correlate between alerts and incidents and raw data located on remote logs. UCLog+ can be used for forensic analysis including queries and report generation but more importantly it can be used for near-real-time situational awareness of attack patterns in progress. The system, implemented with open source tools, can also be a repository for secure information sharing by different organizations.
Polynomial-time algorithm for vertex k-colorability of P_5-free graphs
Venue: arXiv cs.DM 2006
Year: 2006

We give the first polynomial-time algorithm for coloring vertices of P_5-free graphs with k colors. This settles an open problem and generalizes several previously known results.
Web-Based Enterprise Information Systems Development: The Integrated Methodology
Venue: arXiv cs.SE 2006
Year: 2006

The paper considers software development issues for large-scale enterprise information systems (IS) with databases (DB) in global heterogeneous distributed computational environment. Due to high IT development rates, the present-day society has accumulated and rapidly increases an extremely huge data burden. Manipulating with such huge data arrays becomes an essential problem, particularly due to their global distribution, heterogeneous and weak-structured character. The conceptual approach to integrated Internet-based IS design, development and implementation is presented, including formal models, software development methodology and original software development tools for visual problem-oriented development and content management. IS implementation results proved shortening terms and reducing costs of implementation compared to commercial software available.
Enterprise Resource Planning Systems: the Integrated Approach
Venue: arXiv cs.SE 2006
Year: 2006

Enterprise resource planning (ERP) systems enjoy an increasingly wide coverage. However, no truly integrate solution has been proposed as yet. ERP classification is given. Recent trends in commercial systems are analyzed on the basis of human resources (HR) management software. An innovative "straight through" design and implementation process of an open, secure, and scalable integrated event-driven enterprise solution is suggested. Implementation results are presented.
Logic Column 16: Higher-Order Abstract Syntax: Setting the Record Straight
Venue: arXiv cs.LO 2006
Year: 2006

This article responds to a critique of higher-order abstract syntax appearing in Logic Column 14, ``Nominal Logic and Abstract Syntax'', cs.LO/0511025.
Fusion of qualitative beliefs using DSmT
Venue: arXiv cs.AI 2006
Year: 2006

This paper introduces the notion of qualitative belief assignment to model beliefs of human experts expressed in natural language (with linguistic labels). We show how qualitative beliefs can be efficiently combined using an extension of Dezert-Smarandache Theory (DSmT) of plausible and paradoxical quantitative reasoning to qualitative reasoning. We propose a new arithmetic on linguistic labels which allows a direct extension of classical DSm fusion rule or DSm Hybrid rules. An approximate qualitative PCR5 rule is also proposed jointly with a Qualitative Average Operator. We also show how crisp or interval mappings can be used to deal indirectly with linguistic labels. A very simple example is provided to illustrate our qualitative fusion rules.
Localization for Anchoritic Sensor Networks
Venue: arXiv cs.NI 2006
Year: 2006

We introduce a class of anchoritic sensor networks, where communications between sensor nodes is undesirable or infeasible, e.g., due to harsh environment, energy constraints, or security considerations.
Infinite Qualitative Simulations by Means of Constraint Programming
Venue: arXiv cs.AI 2006
Year: 2006

We introduce a constraint-based framework for studying infinite qualitative simulations concerned with contingencies such as time, space, shape, size, abstracted into a finite set of qualitative relations. To define the simulations, we combine constraints that formalize the background knowledge concerned with qualitative reasoning with appropriate inter-state constraints that are formulated using linear temporal logic. We implemented this approach in a constraint programming system by drawing on ideas from bounded model checking. The resulting system allows us to test and modify the problem specifications in a straightforward way and to combine various knowledge aspects.
New Cross-Layer Channel Switching Policy for TCP Transmission on 3G UMTS Downlink
Venue: arXiv cs.NI 2006
Year: 2006

In 3G UMTS, two main transport channels have been provided for downlink data transmission: a common FACH channel and a dedicated DCH channel. The performance of TCP in UMTS depends much on the channel switching policy used. In this paper, we propose and analyze three new basic threshold-based channel switching policies for UMTS that we name as QS (Queue Size), FS (Flow Size) and QSFS (QS & FS combined) policy. These policies significantly improve over a modified threshold policy in [1] by about 17% in response time metrics. We further propose and evaluate a new improved switching policy that we call FS-DCH (at-least flow-size threshold on DCH) policy. This policy is biased towards short TCP flows of few packets and is thus a cross-layer policy that improves the performance of TCP by giving priority to the initial few packets of a flow on the fast DCH channel. Extensive simulation results confirm this improvement for the case when number of TCP connections is low.
Guessing Facets: Polytope Structure and Improved LP Decoder
Venue: arXiv cs.IT 2006
Year: 2006

A new approach for decoding binary linear codes by solving a linear program (LP) over a relaxed codeword polytope was recently proposed by Feldman et al. In this paper we investigate the structure of the polytope used in the LP relaxation decoding. We begin by showing that for expander codes, every fractional pseudocodeword always has at least a constant fraction of non-integral bits. We then prove that for expander codes, the active set of any fractional pseudocodeword is smaller by a constant fraction than the active set of any codeword. We exploit this fact to devise a decoding algorithm that provably outperforms the LP decoder for finite blocklengths. It proceeds by guessing facets of the polytope, and resolving the linear program on these facets. While the LP decoder succeeds only if the ML codeword has the highest likelihood over all pseudocodewords, we prove that for expander codes the proposed algorithm succeeds even with a constant number of pseudocodewords of higher likelihood. Moreover, the complexity of the proposed algorithm is only a constant factor larger than that of the LP decoder.