OpenRaiser/Intern-Atlas huggingface dataset:
A Comparison of Techniques for Sampling Web Pages
Venue: arXiv cs.DS 2009
Year: 2009

As the World Wide Web is growing rapidly, it is getting increasingly challenging to gather representative information about it. Instead of crawling the web exhaustively one has to resort to other techniques like sampling to determine the properties of the web. A uniform random sample of the web would be useful to determine the percentage of web pages in a specific language, on a topic or in a top level domain. Unfortunately, no approach has been shown to sample the web pages in an unbiased way. Three promising web sampling algorithms are based on random walks. They each have been evaluated individually, but making a comparison on different data sets is not possible. We directly compare these algorithms in this paper. We performed three random walks on the web under the same conditions and analyzed their outcomes in detail. We discuss the strengths and the weaknesses of each algorithm and propose improvements based on experimental results.
Improvements of real coded genetic algorithms based on differential operators preventing premature convergence
Venue: arXiv cs.NE 2009
Year: 2009

This paper presents several types of evolutionary algorithms (EAs) used for global optimization on real domains. The interest has been focused on multimodal problems, where the difficulties of a premature convergence usually occurs. First the standard genetic algorithm (SGA) using binary encoding of real values and its unsatisfactory behavior with multimodal problems is briefly reviewed together with some improvements of fighting premature convergence. Two types of real encoded methods based on differential operators are examined in detail: the differential evolution (DE), a very modern and effective method firstly published by R. Storn and K. Price, and the simplified real-coded differential genetic algorithm SADE proposed by the authors. In addition, an improvement of the SADE method, called CERAF technology, enabling the population of solutions to escape from local extremes, is examined. All methods are tested on an identical set of objective functions and a systematic comparison based on a reliable methodology is presented. It is confirmed that real coded methods generally exhibit better behavior on real domains than the binary algorithms, even when extended by several improvements. Furthermore, the positive influence of the differential operators due to their possibility of self-adaptation is demonstrated. From the reliability point of view, it seems that the real encoded differential algorithm, improved by the technology described in this paper, is a universal and reliable method capable of solving all proposed test problems.
Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time
Venue: arXiv cs.DM 2009
Year: 2009

The described multicoloring problem has direct applications in the context of wireless ad hoc and sensor networks. In order to coordinate the access to the shared wireless medium, the nodes of such a network need to employ some medium access control (MAC) protocol. Typical MAC protocols control the access to the shared channel by time (TDMA), frequency (FDMA), or code division multiple access (CDMA) schemes. Many channel access schemes assign a fixed set of time slots, frequencies, or (orthogonal) codes to the nodes of a network such that nodes that interfere with each other receive disjoint sets of time slots, frequencies, or code sets. Finding a valid assignment of time slots, frequencies, or codes hence directly corresponds to computing a multicoloring of a graph $G$. The scarcity of bandwidth, energy, and computing resources in ad hoc and sensor networks, as well as the often highly dynamic nature of these networks require that the multicoloring can be computed based on as little and as local information as possible.
Polynomial Size Analysis of First-Order Shapely Functions
Venue: arXiv cs.LO 2009
Year: 2009

We present a size-aware type system for first-order shapely function definitions. Here, a function definition is called shapely when the size of the result is determined exactly by a polynomial in the sizes of the arguments. Examples of shapely function definitions may be implementations of matrix multiplication and the Cartesian product of two lists. The type system is proved to be sound w.r.t. the operational semantics of the language. The type checking problem is shown to be undecidable in general. We define a natural syntactic restriction such that the type checking becomes decidable, even though size polynomials are not necessarily linear or monotonic. Furthermore, we have shown that the type-inference problem is at least semi-decidable (under this restriction). We have implemented a procedure that combines run-time testing and type-checking to automatically obtain size dependencies. It terminates on total typable function definitions.
Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence
Venue: arXiv cs.CC 2009
Year: 2009

An infinite binary sequence has randomness rate at least $σ$ if, for almost every $n$, the Kolmogorov complexity of its prefix of length $n$ is at least $σn$. It is known that for every rational $σ\in (0,1)$, on one hand, there exists sequences with randomness rate $σ$ that can not be effectively transformed into a sequence with randomness rate higher than $σ$ and, on the other hand, any two independent sequences with randomness rate $σ$ can be transformed into a sequence with randomness rate higher than $σ$. We show that the latter result holds even if the two input sequences have linear dependency (which, informally speaking, means that all prefixes of length $n$ of the two sequences have in common a constant fraction of their information). The similar problem is studied for finite strings. It is shown that from any two strings with sufficiently large Kolmogorov complexity and sufficiently small dependence, one can effectively construct a string that is random even conditioned by any one of the input strings.
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences
Venue: arXiv cs.CC 2009
Year: 2009

The Gap-Hamming-Distance problem arose in the context of proving space lower bounds for a number of key problems in the data stream model. In this problem, Alice and Bob have to decide whether the Hamming distance between their $n$-bit input strings is large (i.e., at least $n/2 + \sqrt n$) or small (i.e., at most $n/2 - \sqrt n$); they do not care if it is neither large nor small. This $Θ(\sqrt n)$ gap in the problem specification is crucial for capturing the approximation allowed to a data stream algorithm. Thus far, for randomized communication, an $Ω(n)$ lower bound on this problem was known only in the one-way setting. We prove an $Ω(n)$ lower bound for randomized protocols that use any constant number of rounds. As a consequence we conclude, for instance, that $ε$-approximately counting the number of distinct elements in a data stream requires $Ω(1/ε^2)$ space, even with multiple (a constant number of) passes over the input stream. This extends earlier one-pass lower bounds, answering a long-standing open question. We obtain similar results for approximating the frequency moments and for approximating the empirical entropy of a data stream. In the process, we also obtain tight $n - Θ(\sqrt{n}\log n)$ lower and upper bounds on the one-way deterministic communication complexity of the problem. Finally, we give a simple combinatorial proof of an $Ω(n)$ lower bound on the one-way randomized communication complexity.
Group-Theoretic Partial Matrix Multiplication
Venue: arXiv cs.CC 2009
Year: 2009

A generalization of recent group-theoretic matrix multiplication algorithms to an analogue of the theory of partial matrix multiplication is presented. We demonstrate that the added flexibility of this approach can in some cases improve upper bounds on the exponent of matrix multiplication yielded by group-theoretic full matrix multiplication. The group theory behind our partial matrix multiplication algorithms leads to the problem of maximizing a quantity representing the "fullness" of a given partial matrix pattern. This problem is shown to be NP-hard, and two algorithms, one optimal and another non-optimal but polynomial-time, are given for solving it.
Creating modular and reusable DSL textual syntax definitions with Grammatic/ANTLR
Venue: arXiv cs.PL 2009
Year: 2009

In this paper we present Grammatic -- a tool for textual syntax definition. Grammatic serves as a front-end for parser generators (and other tools) and brings modularity and reuse to their development artifacts. It adapts techniques for separation of concerns from Apsect-Oriented Programming to grammars and uses templates for grammar reuse. We illustrate usage of Grammatic by describing a case study: bringing separation of concerns to ANTLR parser generator, which is achieved without a common time- and memory-consuming technique of building an AST to separate semantic actions from a grammar definition.
A Graph Reduction Step Preserving Element-Connectivity and Applications
Venue: arXiv cs.DS 2009
Year: 2009

Given an undirected graph G=(V,E) and subset of terminals T \subseteq V, the element-connectivity of two terminals u,v \in T is the maximum number of u-v paths that are pairwise disjoint in both edges and non-terminals V \setminus T (the paths need not be disjoint in terminals). Element-connectivity is more general than edge-connectivity and less general than vertex-connectivity. Hind and Oellermann gave a graph reduction step that preserves the global element-connectivity of the graph. We show that this step also preserves local connectivity, that is, all the pairwise element-connectivities of the terminals. We give two applications of this reduction step to connectivity and network design problems: 1. Given a graph G and disjoint terminal sets T_1, T_2, ..., T_m, we seek a maximum number of element-disjoint Steiner forests where each forest connects each T_i. We prove that if each T_i is k-element-connected then there exist Ω(\frac{k}{\log h \log m}) element-disjoint Steiner forests, where h = |\bigcup_i T_i|. If G is planar (or more generally, has fixed genus), we show that there exist Ω(k) Steiner forests. Our proofs are constructive, giving poly-time algorithms to find these forests; these are the first non-trivial algorithms for packing element-disjoint Steiner Forests. 2. We give a very short and intuitive proof of a spider-decomposition theorem of Chuzhoy and Khanna in the context of the single-sink k-vertex-connectivity problem; this yields a simple and alternative analysis of an O(k \log n) approximation. Our results highlight the effectiveness of the element-connectivity reduction step; we believe it will find more applications in the future.
Transmission protocols for instruction streams
Venue: arXiv cs.PL 2009
Year: 2009

Threads as considered in thread algebra model behaviours to be controlled by some execution environment: upon each action performed by a thread, a reply from its execution environment -- which takes the action as an instruction to be processed -- determines how the thread proceeds. In this paper, we are concerned with the case where the execution environment is remote: we describe and analyse some transmission protocols for passing instructions from a thread to a remote execution environment.
ImageSpace: An Environment for Image Ontology Management
Venue: arXiv cs.DL 2009
Year: 2009

More and more researchers have realized that ontologies will play a critical role in the development of the Semantic Web, the next generation Web in which content is not only consumable by humans, but also by software agents. The development of tools to support ontology management including creation, visualization, annotation, database storage, and retrieval is thus extremely important. We have developed ImageSpace, an image ontology creation and annotation tool that features (1) full support for the standard web ontology language DAML+OIL; (2) image ontology creation, visualization, image annotation and display in one integrated framework; (3) ontology consistency assurance; and (4) storing ontologies and annotations in relational databases. It is expected that the availability of such a tool will greatly facilitate the creation of image repositories as islands of the Semantic Web.
OntoELAN: An Ontology-based Linguistic Multimedia Annotator
Venue: arXiv cs.DL 2009
Year: 2009

Despite its scientific, political, and practical value, comprehensive information about human languages, in all their variety and complexity, is not readily obtainable and searchable. One reason is that many language data are collected as audio and video recordings which imposes a challenge to document indexing and retrieval. Annotation of multimedia data provides an opportunity for making the semantics explicit and facilitates the searching of multimedia documents. We have developed OntoELAN, an ontology-based linguistic multimedia annotator that features: (1) support for loading and displaying ontologies specified in OWL; (2) creation of a language profile, which allows a user to choose a subset of terms from an ontology and conveniently rename them if needed; (3) creation of ontological tiers, which can be annotated with profile terms and, therefore, corresponding ontological terms; and (4) saving annotations in the XML format as Multimedia Ontology class instances and, linked to them, class instances of other ontologies used in ontological tiers. To our best knowledge, OntoELAN is the first audio/video annotation tool in linguistic domain that provides support for ontology-based annotation.
Compact Ancestry Labeling Schemes for Trees of Small Depth
Venue: arXiv cs.DS 2009
Year: 2009

An {\em ancestry labeling scheme} labels the nodes of any tree in such a way that ancestry queries between any two nodes in a tree can be answered just by looking at their corresponding labels. The common measure to evaluate the quality of an ancestry labeling scheme is by its {\em label size}, that is the maximal number of bits stored in a label, taken over all $n$-node trees. The design of ancestry labeling schemes finds applications in XML search engines. In the context of these applications, even small improvements in the label size are important. In fact, the literature about this topic is interested in the exact label size rather than just its order of magnitude. As a result, following the proposal of an original scheme of size $2\log n$ bits, a considerable amount of work was devoted to improve the bound on the label size. The current state of the art upper bound is $\log n + O(\sqrt{\log n})$ bits which is still far from the known $\log n + Ω(\log\log n)$ lower bound. Moreover, the hidden constant factor in the additive $O(\sqrt{\log n})$ term is large, which makes this term dominate the label size for typical current XML trees. In attempt to provide good performances for real XML data, we rely on the observation that the depth of a typical XML tree is bounded from above by a small constant. Having this in mind, we present an ancestry labeling scheme of size $\log n+2\log d +O(1)$, for the family of trees with at most $n$ nodes and depth at most $d$. In addition to our main result, we prove a result that may be of independent interest concerning the existence of a linear {\em universal graph} for the family of forests with trees of bounded depth.
A distributed editing environment for XML documents
Venue: arXiv cs.SE 2009
Year: 2009

XML is based on two essential aspects: the modelization of data in a tree like structure and the separation between the information itself and the way it is displayed. XML structures are easily serializable. The separation between an abstract representation and one or several views on it allows the elaboration of specialized interfaces to visualize or modify data. A lot of developments were made to interact with XML data but the use of these applications over the Internet is just starting. This paper presents a prototype of a distributed editing environment over the Internet. The key point of our system is the way user interactions are handled. Selections and modifications made by a user are not directly reflected on the concrete view, they are serialized in XML and transmitted to a server which applies them to the document and broadcasts updates to the views. This organization has several advantages. XML documents coding selection and modification operations are usually smaller than the edited document and can be directly processed with a transformation engine which can adapt them to different representations. In addition, several selections or modifications can be combined into an unique XML document. This allows one to update multiple views with different frequencies and fits the requirement of an asynchronous communication mode like HTTP.
Coverage in Multi-Antenna Two-Tier Networks
Venue: arXiv cs.NI 2009
Year: 2009

In two-tier networks -- comprising a conventional cellular network overlaid with shorter range hotspots (e.g. femtocells, distributed antennas, or wired relays) -- with universal frequency reuse, the near-far effect from cross-tier interference creates dead spots where reliable coverage cannot be guaranteed to users in either tier. Equipping the macrocell and femtocells with multiple antennas enhances robustness against the near-far problem. This work derives the maximum number of simultaneously transmitting multiple antenna femtocells meeting a per-tier outage probability constraint. Coverage dead zones are presented wherein cross-tier interference bottlenecks cellular and hotspot coverage. Two operating regimes are shown namely 1) a cellular-limited regime in which femtocell users experience unacceptable cross-tier interference and 2) a hotspot-limited regime wherein both femtocell users and cellular users are limited by hotspot interference. Our analysis accounts for the per-tier transmit powers, the number of transmit antennas (single antenna transmission being a special case) and terrestrial propagation such as the Rayleigh fading and the path loss exponents. Single-user (SU) multiple antenna transmission at each tier is shown to provide significantly superior coverage and spatial reuse relative to multiuser (MU) transmission. We propose a decentralized carrier-sensing approach to regulate femtocell transmission powers based on their location. Considering a worst-case cell-edge location, simulations using typical path loss scenarios show that our interference management strategy provides reliable cellular coverage with about 60 femtocells per cellsite.
An Algebraic Dexter-Based Hypertext Reference Model
Venue: arXiv cs.AI 2009
Year: 2009

We present the first formal algebraic specification of a hypertext reference model. It is based on the well-known Dexter Hypertext Reference Model and includes modifications with respect to the development of hypertext since the WWW came up. Our hypertext model was developed as a product model with the aim to automatically support the design process and is extended to a model of hypertext-systems in order to be able to describe the state transitions in this process. While the specification should be easy to read for non-experts in algebraic specification, it guarantees a unique understanding and enables a close connection to logic-based development and verification.
A minimalistic look at widening operators
Venue: arXiv cs.LO 2009
Year: 2009

We consider the problem of formalizing the familiar notion of widening in abstract interpretation in higher-order logic. It turns out that many axioms of widening (e.g. widening sequences are ascending) are not useful for proving correctness. After keeping only useful axioms, we give an equivalent characterization of widening as a lazily constructed well-founded tree. In type systems supporting dependent products and sums, this tree can be made to reflect the condition of correct termination of the widening sequence.
Bounded Independence Fools Halfspaces
Venue: arXiv cs.CC 2009
Year: 2009

We show that any distribution on {-1,1}^n that is k-wise independent fools any halfspace h with error \eps for k = O(\log^2(1/\eps) /\eps^2). Up to logarithmic factors, our result matches a lower bound by Benjamini, Gurel-Gurevich, and Peled (2007) showing that k = Ω(1/(\eps^2 \cdot \log(1/\eps))). Using standard constructions of k-wise independent distributions, we obtain the first explicit pseudorandom generators G: {-1,1}^s --> {-1,1}^n that fool halfspaces. Specifically, we fool halfspaces with error eps and seed length s = k \log n = O(\log n \cdot \log^2(1/\eps) /\eps^2). Our approach combines classical tools from real approximation theory with structural results on halfspaces by Servedio (Computational Complexity 2007).
Yet Another Deep Embedding of B:Extending de Bruijn Notations
Venue: arXiv cs.LO 2009
Year: 2009

We present Bicoq3, a deep embedding of the B system in Coq, focusing on the technical aspects of the development. The main subjects discussed are related to the representation of sets and maps, the use of induction principles, and the introduction of a new de Bruijn notation providing solutions to various problems related to the mechanisation of languages and logics.
Antichains for the Automata-Based Approach to Model-Checking
Venue: arXiv cs.LO 2009
Year: 2009

We propose and evaluate antichain algorithms to solve the universality and language inclusion problems for nondeterministic Buechi automata, and the emptiness problem for alternating Buechi automata. To obtain those algorithms, we establish the existence of simulation pre-orders that can be exploited to efficiently evaluate fixed points on the automata defined during the complementation step (that we keep implicit in our approach). We evaluate the performance of the algorithm to check the universality of Buechi automata using the random automaton model recently proposed by Tabakov and Vardi. We show that on the difficult instances of this probabilistic model, our algorithm outperforms the standard ones by several orders of magnitude.
Optimal Control of a Single Queue with Retransmissions: Delay-Dropping Tradeoffs
Venue: arXiv cs.MM 2009
Year: 2009

A single queue incorporating a retransmission protocol is investigated, assuming that the sequence of per effort success probabilities in the Automatic Retransmission reQuest (ARQ) chain is a priori defined and no channel state information at the transmitter is available. A Markov Decision Problem with an average cost criterion is formulated where the possible actions are to either continue the retransmission process of an erroneous packet at the next time slot or to drop the packet and move on to the next packet awaiting for transmission. The cost per slot is a linear combination of the current queue length and a penalty term in case dropping is chosen as action. The investigation seeks policies that provide the best possible average packet delay-dropping trade-off for Quality of Service guarantees. An optimal deterministic stationary policy is shown to exist, several structural properties of which are obtained. Based on that, a class of suboptimal <L,K>-policies is introduced. These suggest that it is almost optimal to use a K-truncated ARQ protocol as long as the queue length is lower than L, else send all packets in one shot. The work concludes with an evaluation of the optimal delay-dropping tradeoff using dynamic programming and a comparison between the optimal and suboptimal policies.