OpenRaiser/Intern-Atlas huggingface dataset:
Scatter Networks: A New Approach for Analyzing Information Scatter on the Web
Venue: arXiv cs.IR 2007
Year: 2007

Information on any given topic is often scattered across the web. Previously this scatter has been characterized through the distribution of a set of facts (i.e. pieces of information) across web pages, showing that typically a few pages contain many facts on the topic, while many pages contain just a few. While such approaches have revealed important scatter phenomena, they are lossy in that they conceal how specific facts (e.g. rare facts) occur in specific types of pages (e.g. fact-rich pages). To reveal such regularities, we construct bi-partite networks, consisting of two types of vertices: the facts contained in webpages and the webpages themselves. Such a representation enables the application of a series of network analysis techniques, revealing structural features such as connectivity, robustness, and clustering. We discuss the implications of each of these features to the users' ability to find comprehensive information online. Finally, we compare the bipartite graph structure of webpages and facts with the hyperlink structure between the webpages.
Coding Improves the Optimal Delay-Throughput Trade-offs in Mobile Ad-Hoc Networks: Two-Dimensional I.I.D. Mobility Models
Venue: arXiv cs.NI 2007
Year: 2007

In this paper, we investigate the delay-throughput trade-offs in mobile ad-hoc networks under two-dimensional i.i.d. mobility models. We consider two mobility time-scales: (i) Fast mobility where node mobility is at the same time-scale as data transmissions; (ii) Slow mobility where node mobility is assumed to occur at a much slower time-scale than data transmissions. Given a delay constraint $D,$ the main results are as follows: (1) For the two-dimensional i.i.d. mobility model with fast mobiles, the maximum throughput per source-destination (S-D) pair is shown to be $O(\sqrt{D/n}),$ where $n$ is the number of mobiles. (2) For the two-dimensional i.i.d. mobility model with slow mobiles, the maximum throughput per S-D pair is shown to be $O(\sqrt[3]{D/n}).$ (3) For each case, we propose a joint coding-scheduling algorithm to achieve the optimal delay-throughput trade-offs.
Viewpoints in co-design: a field study in concurrent engineering
Venue: arXiv cs.HC 2007
Year: 2007

We present a field study aimed at analysing the use of viewpoints in co-design meetings. A viewpoint is a representation characterised by a certain combination of constraints. Three types of viewpoints are distinguished: prescribed viewpoint, discipline-specific viewpoint and integrated viewpoint. The contribution of our work consists in characterising the viewpoints of various stakeholders involved in co-design ("design office" disciplines, and production and maintenance disciplines), the dynamics of viewpoints confrontation and the cooperative modes that enable these different viewpoints to be integrated.
Quantitative Measurements of the Influence of Participant Roles during Peer Review Meetings
Venue: arXiv cs.HC 2007
Year: 2007

Peer review meetings (PRMs) are formal meetings during which peers systematically analyze artifacts to improve their quality and report on non-conformities. This paper presents an approach based on protocol analysis for quantifying the influence of participant roles during PRMs. Three views are used to characterize the seven defined participant roles. The project view defines three roles supervisor, procedure expert and developer. The meeting view defines two roles: author and reviewer, and the task view defines the roles reflecting direct and indirect interest in the artifact under review. The analysis, based on log-linear modeling, shows that review activities have different patterns, depending on their focus: form or content. The influence of each role is analyzed with respect to this focus. Interpretation of the quantitative data leads to the suggestion that PRMs could be improved by creating three different types of reviews, each of which collects together specific roles: form review, cognitive synchronization review and content review.
Stochastic Models for Budget Optimization in Search-Based Advertising
Venue: arXiv cs.DS 2007
Year: 2007

Internet search companies sell advertisement slots based on users' search queries via an auction. Advertisers have to determine how to place bids on the keywords of their interest in order to maximize their return for a given budget: this is the budget optimization problem. The solution depends on the distribution of future queries. In this paper, we formulate stochastic versions of the budget optimization problem based on natural probabilistic models of distribution over future queries, and address two questions that arise. [Evaluation] Given a solution, can we evaluate the expected value of the objective function? [Optimization] Can we find a solution that maximizes the objective function in expectation? Our main results are approximation and complexity results for these two problems in our three stochastic models. In particular, our algorithmic results show that simple prefix strategies that bid on all cheap keywords up to some level are either optimal or good approximations for many cases; we show other cases to be NP-hard.
Sufficient Conditions for Coarse-Graining Evolutionary Dynamics
Venue: arXiv cs.NE 2007
Year: 2007

It is commonly assumed that the ability to track the frequencies of a set of schemata in the evolving population of an infinite population genetic algorithm (IPGA) under different fitness functions will advance efforts to obtain a theory of adaptation for the simple GA. Unfortunately, for IPGAs with long genomes and non-trivial fitness functions there do not currently exist theoretical results that allow such a study. We develop a simple framework for analyzing the dynamics of an infinite population evolutionary algorithm (IPEA). This framework derives its simplicity from its abstract nature. In particular we make no commitment to the data-structure of the genomes, the kind of variation performed, or the number of parents involved in a variation operation. We use this framework to derive abstract conditions under which the dynamics of an IPEA can be coarse-grained. We then use this result to derive concrete conditions under which it becomes computationally feasible to closely approximate the frequencies of a family of schemata of relatively low order over multiple generations, even when the bitstsrings in the evolving population of the IPGA are long.
Infinite-Alphabet Prefix Codes Optimal for $β$-Exponential Penalties
Venue: arXiv cs.IT 2007
Year: 2007

Let $P = \{p(i)\}$ be a measure of strictly positive probabilities on the set of nonnegative integers. Although the countable number of inputs prevents usage of the Huffman algorithm, there are nontrivial $P$ for which known methods find a source code that is optimal in the sense of minimizing expected codeword length. For some applications, however, a source code should instead minimize one of a family of nonlinear objective functions, $β$-exponential means, those of the form $\log_a \sum_i p(i) a^{n(i)}$, where $n(i)$ is the length of the $i$th codeword and $a$ is a positive constant. Applications of such minimizations include a problem of maximizing the chance of message receipt in single-shot communications ($a<1$) and a problem of minimizing the chance of buffer overflow in a queueing system ($a>1$). This paper introduces methods for finding codes optimal for such exponential means. One method applies to geometric distributions, while another applies to distributions with lighter tails. The latter algorithm is applied to Poisson distributions. Both are extended to minimizing maximum pointwise redundancy.
Analysis of Sequential Decoding Complexity Using the Berry-Esseen Inequality
Venue: arXiv cs.IT 2007
Year: 2007

his study presents a novel technique to estimate the computational complexity of sequential decoding using the Berry-Esseen theorem. Unlike the theoretical bounds determined by the conventional central limit theorem argument, which often holds only for sufficiently large codeword length, the new bound obtained from the Berry-Esseen theorem is valid for any blocklength. The accuracy of the new bound is then examined for two sequential decoding algorithms, an ordering-free variant of the generalized Dijkstra's algorithm (GDA)(or simplified GDA) and the maximum-likelihood sequential decoding algorithm (MLSDA). Empirically investigating codes of small blocklength reveals that the theoretical upper bound for the simplified GDA almost matches the simulation results as the signal-to-noise ratio (SNR) per information bit ($γ_b$) is greater than or equal to 8 dB. However, the theoretical bound may become markedly higher than the simulated average complexity when $γ_b$ is small. For the MLSDA, the theoretical upper bound is quite close to the simulation results for both high SNR ($γ_b\geq 6$ dB) and low SNR ($γ_b\leq 2$ dB). Even for moderate SNR, the simulation results and the theoretical bound differ by at most \makeblue{0.8} on a $\log_{10}$ scale.
The source coding game with a cheating switcher
Venue: arXiv cs.IT 2007
Year: 2007

Berger's paper `The Source Coding Game', IEEE Trans. Inform. Theory, 1971, considers the problem of finding the rate-distortion function for an adversarial source comprised of multiple known IID sources. The adversary, called the `switcher', was allowed only causal access to the source realizations and the rate-distortion function was obtained through the use of a type covering lemma. In this paper, the rate-distortion function of the adversarial source is described, under the assumption that the switcher has non-causal access to all source realizations. The proof utilizes the type covering lemma and simple conditional, random `switching' rules. The rate-distortion function is once again the maximization of the R(D) function for a region of attainable IID distributions.
Performance of Rake Receivers in IR-UWB Networks Using Energy-Efficient Power Control
Venue: arXiv cs.IT 2007
Year: 2007

This paper studies the performance of partial-Rake (PRake) receivers in impulse-radio ultrawideband wireless networks when an energy-efficient power control scheme is adopted. Due to the large bandwidth of the system, the multipath channel is assumed to be frequency-selective. By making use of noncooperative game-theoretic models and large-system analysis tools, explicit expressions are derived in terms of network parameters to measure the effects of self-interference and multiple-access interference at a receiving access point. Performance of the PRake receivers is thus compared in terms of achieved utilities and loss to that of the all-Rake receiver. Simulation results are provided to validate the analysis.
Coding, Scheduling, and Cooperation in Wireless Sensor Networks
Venue: arXiv cs.IT 2007
Year: 2007

We consider a single-hop data gathering sensor cluster consisting of a set of sensors that need to transmit data periodically to a base-station. We are interested in maximizing the lifetime of this network. Even though the setting of our problem is very simple, it turns out that the solution is far from easy. The complexity arises from several competing system-level opportunities available to reduce the energy consumed in radio transmission. First, sensor data is spatially and temporally correlated. Recent advances in distributed source-coding allow us to take advantage of these correlations to reduce the number of transmitted bits, with concomitant savings in energy. Second, it is also well-known that channel-coding can be used to reduce transmission energy by increasing transmission time. Finally, sensor nodes are cooperative, unlike nodes in an ad hoc network that are often modeled as competitive, allowing us to take full advantage of the first two opportunities for the purpose of maximizing cluster lifetime. In this paper, we pose the problem of maximizing lifetime as a max-min optimization problem subject to the constraint of successful data collection and limited energy supply at each node. By introducing the notion of instantaneous decoding, we are able to simplify this optimization problem into a joint scheduling and time allocation problem. We show that even with our ample simplification, the problem remains NP-hard. We provide some algorithms, heuristics and insight for various scenarios. Our chief contribution is to illustrate both the challenges and gains provided by joint source-channel coding and scheduling.
A Case For Amplify-Forward Relaying in the Block-Fading Multi-Access Channel
Venue: arXiv cs.IT 2007
Year: 2007

This paper demonstrates the significant gains that multi-access users can achieve from sharing a single amplify-forward relay in slow fading environments. The proposed protocol, namely the multi-access relay amplify-forward, allows for a low-complexity relay and achieves the optimal diversity-multiplexing trade-off at high multiplexing gains. Analysis of the protocol reveals that it uniformly dominates the compress-forward strategy and further outperforms the dynamic decode-forward protocol at high multiplexing gains. An interesting feature of the proposed protocol is that, at high multiplexing gains, it resembles a multiple-input single-output system, and at low multiplexing gains, it provides each user with the same diversity-multiplexing trade-off as if there is no contention for the relay from the other users.
Duadic Group Algebra Codes
Venue: arXiv cs.IT 2007
Year: 2007

Duadic group algebra codes are a generalization of quadratic residue codes. This paper settles an open problem raised by Zhu concerning the existence of duadic group algebra codes. These codes can be used to construct degenerate quantum stabilizer codes that have the nice feature that many errors of small weight do not need error correction; this fact is illustrated by an example.
Finding low-weight polynomial multiples using discrete logarithm
Venue: arXiv cs.CR 2007
Year: 2007

Finding low-weight multiples of a binary polynomial is a difficult problem arising in the context of stream ciphers cryptanalysis. The classical algorithm to solve this problem is based on a time memory trade-off. We will present an improvement to this approach using discrete logarithm rather than a direct representation of the involved polynomials. This gives an algorithm which improves the theoretical complexity, and is also very flexible in practice.
On the robustness of the h-index
Venue: arXiv cs.DL 2007
Year: 2007

The h-index (Hirsch, 2005) is robust, remaining relatively unaffected by errors in the long tails of the citations-rank distribution, such as typographic errors that short-change frequently-cited papers and create bogus additional records. This robustness, and the ease with which h-indices can be verified, support the use of a Hirsch-type index over alternatives such as the journal impact factor. These merits of the h-index apply to both individuals and to journals.
Fingerprinting Logic Programs
Venue: arXiv cs.PL 2007
Year: 2007

In this work we present work in progress on functionality duplication detection in logic programs. Eliminating duplicated functionality recently became prominent in context of refactoring. We describe a quantitative approach that allows to measure the ``similarity'' between two predicate definitions. Moreover, we show how to compute a so-called ``fingerprint'' for every predicate. Fingerprints capture those characteristics of the predicate that are significant when searching for duplicated functionality. Since reasoning on fingerprints is much easier than reasoning on predicate definitions, comparing the fingerprints is a promising direction in automated code duplication in logic programs.
Artificiality in Social Sciences
Venue: arXiv cs.MA 2007
Year: 2007

This text provides with an introduction to the modern approach of artificiality and simulation in social sciences. It presents the relationship between complexity and artificiality, before introducing the field of artificial societies which greatly benefited from the computer power fast increase, gifting social sciences with formalization and experimentation tools previously owned by "hard" sciences alone. It shows that as "a new way of doing social sciences", artificial societies should undoubtedly contribute to a renewed approach in the study of sociality and should play a significant part in the elaboration of original theories of social phenomena.
Analysis and design of raptor codes for joint decoding using Information Content evolution
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, we present an analytical analysis of the convergence of raptor codes under joint decoding over the binary input additive white noise channel (BIAWGNC), and derive an optimization method. We use Information Content evolution under Gaussian approximation, and focus on a new decoding scheme that proves to be more efficient: the joint decoding of the two code components of the raptor code. In our general model, the classical tandem decoding scheme appears to be a subcase, and thus, the design of LT codes is also possible.
ExSched: Solving Constraint Satisfaction Problems with the Spreadsheet Paradigm
Venue: arXiv cs.PL 2007
Year: 2007

We report on the development of a general tool called ExSched, implemented as a plug-in for Microsoft Excel, for solving a class of constraint satisfaction problems. The traditional spreadsheet paradigm is based on attaching arithmetic expressions to individual cells and then evaluating them. The ExSched interface generalizes the spreadsheet paradigm to allow finite domain constraints to be attached to the individual cells that are then solved to get a solution. This extension provides a user-friendly interface for solving constraint satisfaction problems that can be modeled as 2D tables, such as scheduling problems, timetabling problems, product configuration, etc. ExSched can be regarded as a spreadsheet interface to CLP(FD) that hides the syntactic and semantic complexity of CLP(FD) and enables novice users to solve many scheduling and timetabling problems interactively.
The problem determination of Functional Dependencies between attributes Relation Scheme in the Relational Data Model. El problema de determinar Dependencias Funcionales entre atributos en los esquemas en el Modelo Relacional
Venue: arXiv cs.DB 2007
Year: 2007

An alternative definition of the concept is given of functional dependence among the attributes of the relational schema in the Relational Model, this definition is obtained in terms of the set theory. For that which a theorem is demonstrated that establishes equivalence and on the basis theorem an algorithm is built for the search of the functional dependences among the attributes. The algorithm is illustrated by a concrete example
Optimal Order of Decoding for Max-Min Fairness in $K$-User Memoryless Interference Channels
Venue: arXiv cs.IT 2007
Year: 2007

A $K$-user memoryless interference channel is considered where each receiver sequentially decodes the data of a subset of transmitters before it decodes the data of the designated transmitter. Therefore, the data rate of each transmitter depends on (i) the subset of receivers which decode the data of that transmitter, (ii) the decoding order, employed at each of these receivers. In this paper, a greedy algorithm is developed to find the users which are decoded at each receiver and the corresponding decoding order such that the minimum rate of the users is maximized. It is proven that the proposed algorithm is optimal.
Interference Automata
Venue: arXiv cs.CC 2007
Year: 2007

We propose a computing model, the Two-Way Optical Interference Automata (2OIA), that makes use of the phenomenon of optical interference. We introduce this model to investigate the increase in power, in terms of language recognition, of a classical Deterministic Finite Automaton (DFA) when endowed with the facility of optical interference. The question is in the spirit of Two-Way Finite Automata With Quantum and Classical States (2QCFA) [A. Ambainis and J. Watrous, Two-way Finite Automata With Quantum and Classical States, Theoretical Computer Science, 287 (1), 299-311, (2002)] wherein the classical DFA is augmented with a quantum component of constant size. We test the power of 2OIA against the languages mentioned in the above paper. We give efficient 2OIA algorithms to recognize languages for which 2QCFA machines have been shown to exist, as well as languages whose status vis-a-vis 2QCFA has been posed as open questions. Finally we show the existence of a language that cannot be recognized by a 2OIA but can be recognized by an $O(n^3)$ space Turing machine.
On the Correlation of Geographic and Network Proximity at Internet Edges and its Implications for Mobile Unicast and Multicast Routing
Venue: arXiv cs.NI 2007
Year: 2007

Significant effort has been invested recently to accelerate handover operations in a next generation mobile Internet. Corresponding works for developing efficient mobile multicast management are emergent. Both problems simultaneously expose routing complexity between subsequent points of attachment as a characteristic parameter for handover performance in access networks. As continuous mobility handovers necessarily occur between access routers located in geographic vicinity, this paper investigates on the hypothesis that geographically adjacent edge networks attain a reduced network distances as compared to arbitrary Internet nodes. We therefore evaluate and analyze edge distance distributions in various regions for clustered IP ranges on their geographic location such as a city. We use traceroute to collect packet forwarding path and round-trip-time of each intermediate node to scan-wise derive an upper bound of the node distances. Results of different scanning origins are compared to obtain the best estimation of network distance of each pair. Our results are compared with corresponding analysis of CAIDA Skitter data, overall leading to fairly stable, reproducible edge distance distributions. As a first conclusion on expected impact on handover performance measures, our results indicate a general optimum for handover anticipation time in 802.11 networks of 25 ms.
Citation Advantage For OA Self-Archiving Is Independent of Journal Impact Factor, Article Age, and Number of Co-Authors
Venue: arXiv cs.IR 2007
Year: 2007

Eysenbach has suggested that the OA (Green) self-archiving advantage might just be an artifact of potential uncontrolled confounding factors such as article age (older articles may be both more cited and more likely to be self-archived), number of authors (articles with more authors might be more cited and more self-archived), subject matter (the subjects that are cited more, self-archive more), country (same thing), number of authors, citation counts of authors, etc. Chawki Hajjem (doctoral candidate, UQaM) had already shown that the OA advantage was present in all cases when articles were analysed separately by age, subject matter or country. He has now done a multiple regression analysis jointly testing (1) article age, (2) journal impact factor, (3) number of authors, and (4) OA self-archiving as separate factors for 442,750 articles in 576 (biomedical) journals across 11 years, and has shown that each of the four factors contributes an independent, statistically significant increment to the citation counts. The OA-self-archiving advantage remains a robust, independent factor. Having successfully responded to his challenge, we now challenge Eysenbach to demonstrate -- by testing a sufficiently broad and representative sample of journals at all levels of the journal quality, visibility and prestige hierarchy -- that his finding of a citation advantage for Gold OA (articles published OA on the high-profile website of the only journal he tested (PNAS) over Green OA articles in the same journal (self-archived on the author's website) was not just an artifact of having tested only one very high-profile journal.