OpenRaiser/Intern-Atlas huggingface dataset:
The Open Access Citation Advantage: Quality Advantage Or Quality Bias?
Venue: arXiv cs.IR 2007
Year: 2007

Many studies have now reported the positive correlation between Open Access (OA) self-archiving and citation counts ("OA Advantage," OAA). But does this OAA occur because (QB) authors are more likely to self-selectively self-archive articles that are more likely to be cited (self-selection "Quality Bias": QB)? or because (QA) articles that are self-archived are more likely to be cited ("Quality Advantage": QA)? The probable answer is both. Three studies [by (i) Kurtz and co-workers in astrophysics, (ii) Moed in condensed matter physics, and (iii) Davis & Fromerth in mathematics] had reported the OAA to be due to QB [plus Early Advantage, EA, from self-archiving the preprint before publication, in (i) and (ii)] rather than QA. These three fields, however, (1) have less of a postprint access problem than most other fields and (i) and (ii) also happen to be among the minority of fields that (2) make heavy use of prepublication preprints. Chawki Hajjem has now analyzed preliminary evidence based on over 100,000 articles from multiple fields, comparing self-selected self-archiving with mandated self-archiving to estimate the contributions of QB and QA to the OAA. Both factors contribute, and the contribution of QA is greater.
Real-Time Model-Checking: Parameters everywhere
Venue: arXiv cs.LO 2007
Year: 2007

In this paper, we study the model-checking and parameter synthesis problems of the logic TCTL over discrete-timed automata where parameters are allowed both in the model (timed automaton) and in the property (temporal formula). Our results are as follows. On the negative side, we show that the model-checking problem of TCTL extended with parameters is undecidable over discrete-timed automata with only one parametric clock. The undecidability result needs equality in the logic. On the positive side, we show that the model-checking and the parameter synthesis problems become decidable for a fragment of the logic where equality is not allowed. Our method is based on automata theoretic principles and an extension of our method to express durations of runs in timed automata using Presburger arithmetic.
Knowledge State Algorithms: Randomization with Limited Information
Venue: arXiv cs.DS 2007
Year: 2007

We introduce the concept of knowledge states; many well-known algorithms can be viewed as knowledge state algorithms. The knowledge state approach can be used to to construct competitive randomized online algorithms and study the tradeoff between competitiveness and memory. A knowledge state simply states conditional obligations of an adversary, by fixing a work function, and gives a distribution for the algorithm. When a knowledge state algorithm receives a request, it then calculates one or more "subsequent" knowledge states, together with a probability of transition to each. The algorithm then uses randomization to select one of those subsequents to be the new knowledge state. We apply the method to the paging problem. We present optimally competitive algorithm for paging for the cases where the cache sizes are k=2 and k=3. These algorithms use only a very limited number of bookmarks.
Contains and Inside relationships within combinatorial Pyramids
Venue: arXiv cs.CV 2007
Year: 2007

Irregular pyramids are made of a stack of successively reduced graphs embedded in the plane. Such pyramids are used within the segmentation framework to encode a hierarchy of partitions. The different graph models used within the irregular pyramid framework encode different types of relationships between regions. This paper compares different graph models used within the irregular pyramid framework according to a set of relationships between regions. We also define a new algorithm based on a pyramid of combinatorial maps which allows to determine if one region contains the other using only local calculus.
Online Bandwidth Allocation
Venue: arXiv cs.DS 2007
Year: 2007

The paper investigates a version of the resource allocation problem arising in the wireless networking, namely in the OVSF code reallocation process. In this setting a complete binary tree of a given height $n$ is considered, together with a sequence of requests which have to be served in an online manner. The requests are of two types: an insertion request requires to allocate a complete subtree of a given height, and a deletion request frees a given allocated subtree. In order to serve an insertion request it might be necessary to move some already allocated subtrees to other locations in order to free a large enough subtree. We are interested in the worst case average number of such reallocations needed to serve a request. It was proved in previous work that the competitive ratio of the optimal online algorithm solving this problem is between 1.5 and O(n). We partially answer the question about its exact value by giving an O(1)-competitive online algorithm. Same model has been used in the context of memory management systems, and analyzed for the number of reallocations needed to serve a request in the worst case. In this setting, our result is a corresponding amortized analysis.
A Critique of ANSI SQL Isolation Levels
Venue: arXiv cs.DB 2007
Year: 2007

ANSI SQL-92 defines Isolation Levels in terms of phenomena: Dirty Reads, Non-Repeatable Reads, and Phantoms. This paper shows that these phenomena and the ANSI SQL definitions fail to characterize several popular isolation levels, including the standard locking implementations of the levels. Investigating the ambiguities of the phenomena leads to clearer definitions; in addition new phenomena that better characterize isolation types are introduced. An important multiversion isolation type, Snapshot Isolation, is defined.
Supporting Finite Element Analysis with a Relational Database Backend, Part II: Database Design and Access
Venue: arXiv cs.DB 2007
Year: 2007

This is Part II of a three article series on using databases for Finite Element Analysis (FEA). It discusses (1) db design, (2) data loading, (3) typical use cases during grid building, (4) typical use cases during simulation (get and put), (5) typical use cases during analysis (also done in Part III) and some performance measures of these cases. It argues that using a database is simpler to implement than custom data schemas, has better performance because it can use data parallelism, and better supports FEA modularity and tool evolution because database schema evolution, data independence, and self-defining data.
Empirical Measurements of Disk Failure Rates and Error Rates
Venue: arXiv cs.DB 2007
Year: 2007

The SATA advertised bit error rate of one error in 10 terabytes is frightening. We moved 2 PB through low-cost hardware and saw five disk read error events, several controller failures, and many system reboots caused by security patches. We conclude that SATA uncorrectable read errors are not yet a dominant system-fault source - they happen, but are rare compared to other problems. We also conclude that UER (uncorrectable error rate) is not the relevant metric for our needs. When an uncorrectable read error happens, there are typically several damaged storage blocks (and many uncorrectable read errors.) Also, some uncorrectable read errors may be masked by the operating system. The more meaningful metric for data architects is Mean Time To Data Loss (MTTDL.)
Large-Scale Query and XMatch, Entering the Parallel Zone
Venue: arXiv cs.DB 2007
Year: 2007

Current and future astronomical surveys are producing catalogs with millions and billions of objects. On-line access to such big datasets for data mining and cross-correlation is usually as highly desired as unfeasible. Providing these capabilities is becoming critical for the Virtual Observatory framework. In this paper we present various performance tests that show how using Relational Database Management Systems (RDBMS) and a Zoning algorithm to partition and parallelize the computation, we can facilitate large-scale query and cross-match.
To BLOB or Not To BLOB: Large Object Storage in a Database or a Filesystem?
Venue: arXiv cs.DB 2007
Year: 2007

Application designers often face the question of whether to store large objects in a filesystem or in a database. Often this decision is made for application design simplicity. Sometimes, performance measurements are also used. This paper looks at the question of fragmentation - one of the operational issues that can affect the performance and/or manageability of the system as deployed long term. As expected from the common wisdom, objects smaller than 256KB are best stored in a database while objects larger than 1M are best stored in the filesystem. Between 256KB and 1MB, the read:write ratio and rate of object overwrite or replacement are important factors. We used the notion of "storage age" or number of object overwrites as way of normalizing wall clock time. Storage age allows our results or similar such results to be applied across a number of read:write ratios and object replacement rates.
Fitting the WHOIS Internet data
Venue: arXiv cs.NI 2007
Year: 2007

We consider the RIPE WHOIS Internet data as characterized by the Cooperative Association for Internet Data Analysis (CAIDA), and show that the Tempered Preferential Attachment model [1] provides an excellent fit to this data. [1] D'Souza, Borgs, Chayes, Berger and Kleinberg, to appear PNAS USA, 2007.
Reasoning from a schema and from an analog in software code reuse
Venue: arXiv cs.SE 2007
Year: 2007

The activity of design involves the decomposition of problems into subproblems and the development and evaluation of solutions. In many cases, solution development is not done from scratch. Designers often evoke and adapt solutions developed in the past. These solutions may come from an internal source, i.e. the memory of the designers, and/or from an external source. The goal of this paper is to analyse the characteristics of the cognitive mechanisms, the knowledge and the representations involved in the code reuse activity performed by experienced programmers. More generally, the focus is the control structure of the reuse activity. Data collected in an experiment in which programmers had to design programs are analyzed. Two code reuse situations are distinguished depending on whether or not the processes involved in reuse start before the elaboration of what acts as a source-solution. Our analysis highlights the use of reasoning from a schema and from an analog in the code reuse activity.
The Effect of Object-Oriented Programming Expertise in Several Dimensions of Comprehension Strategies
Venue: arXiv cs.HC 2007
Year: 2007

This study analyzes object-oriented (OO) program comprehension by experts and novices. We examine the effect of expertise in three dimensions of comprehension strategies: the scope of the comprehension, the top-down versus bottom-up direction of the processes, and the guidance of the comprehension activity. Overall, subjects were similar in the scope of their comprehension, although the experts tended to consult more files. We found strong evidence of top-down, inference-driven behaviors, as well as multiple guidance in expert comprehension. We also found evidence of execution-based guidance and less use of top-down processes in novice comprehension. Guidance by inheritance and composition relationships in the OO program was not dominant, but nevertheless played a substantial role in expert program comprehension. However, these static relationships more closely tied to the OO nature of the program were exploited poorly by novices. To conclude, these results are discussed with respect to the literature on procedural program comprehension.
What model(s) for program understanding?
Venue: arXiv cs.HC 2007
Year: 2007

The first objective of this paper is to present and discuss various types of models of program understanding. They are discussed in relation to models of text understanding. The second objective of this paper is to assess the effect of purpose for reading, or more specifically programming task, on the cognitive processes involved and representations constructed in program understanding. This is done in the theoretical framework of van Dijk and Kintsch's model of text understanding (1983).
MMSE Optimal Algebraic Space-Time Codes
Venue: arXiv cs.IT 2007
Year: 2007

Design of Space-Time Block Codes (STBCs) for Maximum Likelihood (ML) reception has been predominantly the main focus of researchers. However, the ML decoding complexity of STBCs becomes prohibitive large as the number of transmit and receive antennas increase. Hence it is natural to resort to a suboptimal reception technique like linear Minimum Mean Squared Error (MMSE) receiver. Barbarossa et al and Liu et al have independently derived necessary and sufficient conditions for a full rate linear STBC to be MMSE optimal, i.e achieve least Symbol Error Rate (SER). Motivated by this problem, certain existing high rate STBC constructions from crossed product algebras are identified to be MMSE optimal. Also, it is shown that a certain class of codes from cyclic division algebras which are special cases of crossed product algebras are MMSE optimal. Hence, these STBCs achieve least SER when MMSE reception is employed and are fully diverse when ML reception is employed.
Network Coding for Distributed Storage Systems
Venue: arXiv cs.IT 2007
Year: 2007

Peer-to-peer distributed storage systems provide reliable access to data through redundancy spread over nodes across the Internet. A key goal is to minimize the amount of bandwidth used to maintain that redundancy. Storing a file using an erasure code, in fragments spread across nodes, promises to require less redundancy and hence less maintenance bandwidth than simple replication to provide the same level of reliability. However, since fragments must be periodically replaced as nodes fail, a key question is how to generate a new fragment in a distributed way while transferring as little data as possible across the network. In this paper, we introduce a general technique to analyze storage architectures that combine any form of coding and replication, as well as presenting two new schemes for maintaining redundancy using erasure codes. First, we show how to optimally generate MDS fragments directly from existing fragments in the system. Second, we introduce a new scheme called Regenerating Codes which use slightly larger fragments than MDS but have lower overall bandwidth use. We also show through simulation that in realistic environments, Regenerating Codes can reduce maintenance bandwidth use by 25 percent or more compared with the best previous design--a hybrid of replication and erasure codes--while simplifying system architecture.
A Dynamic I/O Model for TRACON Traffic Management
Venue: arXiv cs.OH 2007
Year: 2007

This work investigates the TRACON flow management around a major airport. Aircraft flows are analyzed through a study of TRACON trajectories records. Rerouting and queuing processes are highlighted and airport characteristics are shown as function of the number of planes in the TRACON. Then, a simple input-output TRACON queuing and landing model is proposed. This model is calibrated and validated using available TRACON data. It reproduces the same phenomenon as the real system. This model is used to show the impact of limiting the number of aircrafts in the TRACON. A limited number of aircraft does not increase delays but reduces the controller's workload and increases safety.
Finding large and small dense subgraphs
Venue: arXiv cs.DS 2007
Year: 2007

We consider two optimization problems related to finding dense subgraphs. The densest at-least-k-subgraph problem (DalkS) is to find an induced subgraph of highest average degree among all subgraphs with at least k vertices, and the densest at-most-k-subgraph problem (DamkS) is defined similarly. These problems are related to the well-known densest k-subgraph problem (DkS), which is to find the densest subgraph on exactly k vertices. We show that DalkS can be approximated efficiently, while DamkS is nearly as hard to approximate as the densest k-subgraph problem.
The Gaussian multiple access wire-tap channel: wireless secrecy and cooperative jamming
Venue: arXiv cs.IT 2007
Year: 2007

We consider the General Gaussian Multiple Access Wire-Tap Channel (GGMAC-WT). In this scenario, multiple users communicate with an intended receiver in the presence of an intelligent and informed eavesdropper. We define two suitable secrecy measures, termed individual and collective, to reflect the confidence in the system for this multi-access environment. We determine achievable rates such that secrecy to some pre-determined degree can be maintained, using Gaussian codebooks. We also find outer bounds for the case when the eavesdropper receives a degraded version of the intended receiver's signal. In the degraded case, Gaussian codewords are shown to achieve the sum capacity for collective constraints. In addition, a TDMA scheme is shown to also achieve sum capacity for both sets of constraints. Numerical results showing the new rate region are presented and compared with the capacity region of the Gaussian Multiple-Access Channel (GMAC) with no secrecy constraints. We then find the secrecy sum-rate maximizing power allocations for the transmitters, and show that a cooperative jamming scheme can be used to increase achievable rates in this scenario.
On Random Network Coding for Multicast
Venue: arXiv cs.IT 2007
Year: 2007

Random linear network coding is a particularly decentralized approach to the multicast problem. Use of random network codes introduces a non-zero probability however that some sinks will not be able to successfully decode the required sources. One of the main theoretical motivations for random network codes stems from the lower bound on the probability of successful decoding reported by Ho et. al. (2003). This result demonstrates that all sinks in a linearly solvable network can successfully decode all sources provided that the random code field size is large enough. This paper develops a new bound on the probability of successful decoding.
Distributed Decision Through Self-Synchronizing Sensor Networks in the Presence of Propagation Delays and Nonreciprocal Channels
Venue: arXiv cs.IT 2007
Year: 2007

In this paper we propose and analyze a distributed algorithm for achieving globally optimal decisions, either estimation or detection, through a self-synchronization mechanism among linearly coupled integrators initialized with local measurements. We model the interaction among the nodes as a directed graph with weights dependent on the radio interface and we pose special attention to the effect of the propagation delays occurring in the exchange of data among sensors, as a function of the network geometry. We derive necessary and sufficient conditions for the proposed system to reach a consensus on globally optimal decision statistics. One of the major results proved in this work is that a consensus is achieved for any bounded delay condition if and only if the directed graph is quasi-strongly connected. We also provide a closed form expression for the global consensus, showing that the effect of delays is, in general, to introduce a bias in the final decision. The closed form expression is also useful to modify the consensus mechanism in order to get rid of the bias with minimum extra complexity.
Tradeoff between decoding complexity and rate for codes on graphs
Venue: arXiv cs.IT 2007
Year: 2007

We consider transmission over a general memoryless channel, with bounded decoding complexity per bit under message passing decoding. We show that the achievable rate is bounded below capacity if there is a finite success in the decoding in a specified number of operations per bit at the decoder for some codes on graphs. These codes include LDPC and LDGM codes. Good performance with low decoding complexity suggests strong local structures in the graphs of these codes, which are detrimental to the code rate asymptotically. The proof method leads to an interesting necessary condition on the code structures which could achieve capacity with bounded decoding complexity. We also show that if a code sequence achieves a rate epsilon close to the channel capacity, the decoding complexity scales at least as O(log(1/epsilon).
Dynamic Random Geometric Graphs
Venue: arXiv cs.DM 2007
Year: 2007

In this work we introduce Dynamic Random Geometric Graphs as a basic rough model for mobile wireless sensor networks, where communication distances are set to the known threshold for connectivity of static random geometric graphs. We provide precise asymptotic results for the expected length of the connectivity and disconnectivity periods of the network. We believe the formal tools developed in this work could be of use in future studies in more concrete settings. In addition, for static random geometric graphs at the threshold for connectivity, we provide asymptotic expressions on the probability of existence of components according to their sizes.
The Hadwiger Number of Jordan Regions is Unbounded
Venue: arXiv cs.CG 2007
Year: 2007

We show that for every n > 0 there is a planar topological disk A_0 and n translates A_1, A_2, ..., A_n of A_0 such that the interiors of A_0, ... A_n are pairwise disjoint, but with each A_i touching A_0 for 1 <= i <= n.
Improving Prolog programs: Refactoring for Prolog
Venue: arXiv cs.SE 2007
Year: 2007

Refactoring is an established technique from the object-oriented (OO) programming community to restructure code: it aims at improving software readability, maintainability and extensibility. Although refactoring is not tied to the OO-paradigm in particular, its ideas have not been applied to Logic Programming until now. This paper applies the ideas of refactoring to Prolog programs. A catalogue is presented listing refactorings classified according to scope. Some of the refactorings have been adapted from the OO-paradigm, while others have been specifically designed for Prolog. The discrepancy between intended and operational semantics in Prolog is also addressed by some of the refactorings. In addition, ViPReSS, a semi-automatic refactoring browser, is discussed and the experience with applying ViPReSS to a large Prolog legacy system is reported. The main conclusion is that refactoring is both a viable technique in Prolog and a rather desirable one.
Performance of Ultra-Wideband Impulse Radio in Presence of Impulsive Interference
Venue: arXiv cs.IT 2007
Year: 2007

We analyze the performance of coherent impulsive-radio (IR) ultra-wideband (UWB) channel in presence of the interference generated by concurrent transmissions of the systems with the same impulsive radio. We derive a novel algorithm, using Monte-Carlo method, to calculate a lower bound on the rate that can be achieved using maximum-likelihood estimator. Using this bound we show that such a channel is very robust to interference, in contrast to the nearest-neighbor detector.
Social Behaviours Applied to P2P Systems: An efficient Algorithm for Resource Organisation
Venue: arXiv cs.DC 2007
Year: 2007

P2P systems are a great solution to the problem of distributing resources. The main issue of P2P networks is that searching and retrieving resources shared by peers is usually expensive and does not take into account similarities among peers. In this paper we present preliminary simulations of PROSA, a novel algorithm for P2P network structuring, inspired by social behaviours. Peers in PROSA self--organise in social groups of similar peers, called ``semantic--groups'', depending on the resources they are sharing. Such a network smoothly evolves to a small--world graph, where queries for resources are efficiently and effectively routed.