OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Threshold Aggregation of Moving Objects
Venue: arXiv cs.DB 2007
Year: 2007

Calculating aggregation operators of moving point objects, using time as a continuous variable, presents unique problems when querying for congestion in a moving and changing (or dynamic) query space. We present a set of congestion query operators, based on a threshold value, that estimate the following 5 aggregation operations in d-dimensions. 1) We call the count of point objects that intersect the dynamic query space during the query time interval, the CountRange. 2) We call the Maximum (or Minimum) congestion in the dynamic query space at any time during the query time interval, the MaxCount (or MinCount). 3) We call the sum of time that the dynamic query space is congested, the ThresholdSum. 4) We call the number of times that the dynamic query space is congested, the ThresholdCount. And 5) we call the average length of time of all the time intervals when the dynamic query space is congested, the ThresholdAverage. These operators rely on a novel approach to transforming the problem of selection based on position to a problem of selection based on a threshold. These operators can be used to predict concentrations of migrating birds that may carry disease such as Bird Flu and hence the information may be used to predict high risk areas. On a smaller scale, those operators are also applicable to maintaining safety in airplane operations. We present the theory of our estimation operators and provide algorithms for exact operators. The implementations of those operators, and experiments, which include data from more than 7500 queries, indicate that our estimation operators produce fast, efficient results with error under 5%.
Prefix Codes for Power Laws with Countable Support
Venue: arXiv cs.IT 2007
Year: 2007

In prefix coding over an infinite alphabet, methods that consider specific distributions generally consider those that decline more quickly than a power law (e.g., Golomb coding). Particular power-law distributions, however, model many random variables encountered in practice. For such random variables, compression performance is judged via estimates of expected bits per input symbol. This correspondence introduces a family of prefix codes with an eye towards near-optimal coding of known distributions. Compression performance is precisely estimated for well-known probability distributions using these codes and using previously known prefix codes. One application of these near-optimal codes is an improved representation of rational numbers.
Effectiveness of Garbage Collection in MIT/GNU Scheme
Venue: arXiv cs.PL 2007
Year: 2007

Scheme uses garbage collection for heap memory management. Ideally, garbage collectors should be able to reclaim all dead objects, i.e. objects that will not be used in future. However, garbage collectors collect only those dead objects that are not reachable from any program variable. Dead objects that are reachable from program variables are not reclaimed. In this paper we describe our experiments to measure the effectiveness of garbage collection in MIT/GNU Scheme. We compute the drag time of objects, i.e. the time for which an object remains in heap memory after its last use. The number of dead objects and the drag time together indicate opportunities for improving garbage collection. Our experiments reveal that up to 26% of dead objects remain in memory. The average drag time is up to 37% of execution time. Overall, we observe memory saving potential ranging from 9% to 65%.
Relay Channels with Confidential Messages
Venue: arXiv cs.IT 2007
Year: 2007

We consider a relay channel where a relay helps the transmission of messages from one sender to one receiver. The relay is considered not only as a sender that helps the message transmission but as a wire-tapper who can obtain some knowledge about the transmitted messages. In this paper we study the coding problem of the relay channel under the situation that some of transmitted messages are confidential to the relay. A security of such confidential messages is measured by the conditional entropy. The rate region is defined by the set of transmission rates for which messages are reliably transmitted and the security of confidential messages is larger than a prescribed level. In this paper we give two definition of the rate region. We first define the rate region in the case of deterministic encoder and call it the deterministic rate region. Next, we define the rate region in the case of stochastic encoder and call it the stochastic rate region. We derive explicit inner and outer bounds for the above two rate regions and present a class of relay channels where two bounds match. Furthermore, we show that stochastic encoder can enlarge the rate region. We also evaluate the deterministic rate region of the Gaussian relay channel with confidential messages.
Assessing the cognitive consequences of the object-oriented approach: a survey of empirical research on object-oriented design by individuals and teams
Venue: arXiv cs.HC 2007
Year: 2007

This paper presents a state-of-art review of empirical research on object-oriented (OO) design. Many claims about the cognitive benefits of the OO paradigm have been made by its advocates. These claims concern the ease of designing and reusing software at the individual level as well as the benefits of this paradigm at the team level. Since these claims are cognitive in nature, its seems important to assess them empirically. After a brief presentation of the main concepts of the OO paradigm, the claims about the superiority of OO design are outlined. The core of this paper consists of a review of empirical studies of OOD. We first discuss results concerning OOD by individuals. On the basis of empirical work, we (1) analyse the design activity of novice OO designers, (2) compare OO design with procedural design and, (3) discuss a typology of problems relevant for the OO approach. Then we assess the claims about naturalness and ease of OO design. The next part discusses results on OO software reuse. On the basis of empirical work, we (1) compare reuse in the OO versus procedural paradigm, (2) discuss the potential for OO software reuse and (3) analyse reuse activity in the OO paradigm. Then we assess claims on reusability. The final part reviews empirical work on OO design by teams. We present results on communication, coordination, knowledge dissemination and interactions with clients. Then we assess claims about OOD at the software design team level. In a general conclusion, we discuss the limitations of these studies and give some directions for future research.
Estimation of Bit and Frame Error Rates of Low-Density Parity-Check Codes on Binary Symmetric Channels
Venue: arXiv cs.IT 2007
Year: 2007

A method for estimating the performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms on binary symmetric channels (BSC) is proposed. Based on the enumeration of the smallest weight error patterns that can not be all corrected by the decoder, this method estimates both the frame error rate (FER) and the bit error rate (BER) of a given LDPC code with very good precision for all crossover probabilities of practical interest. Through a number of examples, we show that the proposed method can be effectively applied to both regular and irregular LDPC codes and to a variety of hard-decision iterative decoding algorithms. Compared with the conventional Monte Carlo simulation, the proposed method has a much smaller computational complexity, particularly for lower error rates.
Confrontation of viewpoints in a concurrent engineering process
Venue: arXiv cs.HC 2007
Year: 2007

We present an empirical study aimed at analysing the use of viewpoints in an industrial Concurrent Engineering context. Our focus is on the viewpoints expressed in the argumentative process taking place in evaluation meetings. Our results show that arguments enabling a viewpoint or proposal to be defended are often characterized by the use of constraints. One result involved the way in which the proposals for solutions are assessed during these meetings. We have revealed the existence of specific assessment modes in these meetings as well as their combination. Then, we show that, even if some constraints are apparently identically used by the different specialists involved in meetings, various meanings and weightings are associated with these constraints by these different specialists.
Mental Representations Constructed by Experts and Novices in Object-Oriented Program Comprehension
Venue: arXiv cs.HC 2007
Year: 2007

Previous studies on program comprehension were carried out largely in the context of procedural languages. Our purpose is to develop and evaluate a cognitive model of object-oriented (OO) program understanding. Our model is based on the van Dijk and Kintsch's model of text understanding (1983). One key aspect of this theoretical approach is the distinction between two kinds of representation the reader might construct from a text: the textbase and the situation model. On the basis of results of an experiment we have conducted, we evaluate the cognitive validity of this distinction in OO program understanding. We examine how the construction of these two representations is differentially affected by the programmer's expertise and how they evolve differentially over time.
Explicit factors of some iterated resultants and discriminants
Venue: arXiv cs.SC 2007
Year: 2007

In this paper, the result of applying iterative univariate resultant constructions to multivariate polynomials is analyzed. We consider the input polynomials as generic polynomials of a given degree and exhibit explicit decompositions into irreducible factors of several constructions involving two times iterated univariate resultants and discriminants over the integer universal ring of coefficients of the entry polynomials. Cases involving from two to four generic polynomials and resultants or discriminants in one of their variables are treated. The decompositions into irreducible factors we get are obtained by exploiting fundamental properties of the univariate resultants and discriminants and induction on the degree of the polynomials. As a consequence, each irreducible factor can be separately and explicitly computed in terms of a certain multivariate resultant. With this approach, we also obtain as direct corollaries some results conjectured by Collins and McCallum which correspond to the case of polynomials whose coefficients are themselves generic polynomials in other variables. Finally, a geometric interpretation of the algebraic factorization of the iterated discriminant of a single polynomial is detailled.
An asynchronous, decentralised commitment protocol for semantic optimistic replication
Venue: arXiv cs.DB 2007
Year: 2007

We study large-scale distributed cooperative systems that use optimistic replication. We represent a system as a graph of actions (operations) connected by edges that reify semantic constraints between actions. Constraint types include conflict, execution order, dependence, and atomicity. The local state is some schedule that conforms to the constraints; because of conflicts, client state is only tentative. For consistency, site schedules should converge; we designed a decentralised, asynchronous commitment protocol. Each client makes a proposal, reflecting its tentative and{\slash}or preferred schedules. Our protocol distributes the proposals, which it decomposes into semantically-meaningful units called candidates, and runs an election between comparable candidates. A candidate wins when it receives a majority or a plurality. The protocol is fully asynchronous: each site executes its tentative schedule independently, and determines locally when a candidate has won an election. The committed schedule is as close as possible to the preferences expressed by clients.
Bias in the journal impact factor
Venue: arXiv cs.DL 2007
Year: 2007

The ISI journal impact factor (JIF) is based on a sample that may represent half the whole-of-life citations to some journals, but a small fraction (<10%) of the citations accruing to other journals. This disproportionate sampling means that the JIF provides a misleading indication of the true impact of journals, biased in favour of journals that have a rapid rather than a prolonged impact. Many journals exhibit a consistent pattern of citation accrual from year to year, so it may be possible to adjust the JIF to provide a more reliable indication of a journal's impact.
On High Spatial Reuse Link Scheduling in STDMA Wireless Ad Hoc Networks
Venue: arXiv cs.PF 2007
Year: 2007

Graph-based algorithms for point-to-point link scheduling in Spatial reuse Time Division Multiple Access (STDMA) wireless ad hoc networks often result in a significant number of transmissions having low Signal to Interference and Noise density Ratio (SINR) at intended receivers, leading to low throughput. To overcome this problem, we propose a new algorithm for STDMA link scheduling based on a graph model of the network as well as SINR computations. The performance of our algorithm is evaluated in terms of spatial reuse and computational complexity. Simulation results demonstrate that our algorithm achieves better performance than existing algorithms.
Relay Assisted F/TDMA Ad Hoc Networks: Node Classification, Power Allocation and Relaying Strategies
Venue: arXiv cs.IT 2007
Year: 2007

This paper considers the design of relay assisted F/TDMA ad hoc networks with multiple relay nodes each of which assists the transmission of a predefined subset of source nodes to their respective destinations. Considering the sum capacity as the performance metric, we solve the problem of optimally allocating the total power of each relay node between the transmissions it is assisting. We consider four different relay transmission strategies, namely regenerative decode-and-forward (RDF), nonregenerative decode-and-forward (NDF), amplify-and-forward (AF) and compress-and-forward (CF). We first obtain the optimum power allocation policies for the relay nodes that employ a uniform relaying strategy for all nodes. We show that the optimum power allocation for the RDF and NDF cases are modified water-filling solutions. We observe that for a given relay transmit power, NDF always outperforms RDF whereas CF always provides higher sum capacity than AF. When CF and NDF are compared, it is observed that either of CF or NDF may outperform the other in different scenarios. This observation suggests that the sum capacity can be further improved by having each relay adopt its relaying strategy in helping different source nodes. We investigate this problem next and determine the optimum power allocation and relaying strategy for each source node that relay nodes assist. We observe that optimum power allocation for relay nodes with hybrid relaying strategies provides higher sum capacity than pure RDF, NDF, AF or CF relaying strategies.
Asynchronous Implementation of Failure Detectors with partial connectivity and unknown participants
Venue: arXiv cs.DC 2007
Year: 2007

We consider the problem of failure detection in dynamic networks such as MANETs. Unreliable failure detectors are classical mechanisms which provide information about process failures. However, most of current implementations consider that the network is fully connected and that the initial number of nodes of the system is known. This assumption is not applicable to dynamic environments. Furthermore, such implementations are usually timer-based while in dynamic networks there is no upper bound for communication delays since nodes can move. This paper presents an asynchronous implementation of a failure detector for unknown and mobile networks. Our approach does not rely on timers and neither the composition nor the number of nodes in the system are known. We prove that our algorithm can implement failure detectors of class <>S when behavioral properties and connectivity conditions are satisfied by the underlying system.
The Inhabitation Problem for Rank Two Intersection Types
Venue: arXiv cs.LO 2007
Year: 2007

We prove that the inhabitation problem for rank two intersection types is decidable, but (contrary to common belief) EXPTIME-hard. The exponential time hardness is shown by reduction from the in-place acceptance problem for alternating Turing machines.
On the implementation of construction functions for non-free concrete data types
Venue: arXiv cs.LO 2007
Year: 2007

Many algorithms use concrete data types with some additional invariants. The set of values satisfying the invariants is often a set of representatives for the equivalence classes of some equational theory. For instance, a sorted list is a particular representative wrt commutativity. Theories like associativity, neutral element, idempotence, etc. are also very common. Now, when one wants to combine various invariants, it may be difficult to find the suitable representatives and to efficiently implement the invariants. The preservation of invariants throughout the whole program is even more difficult and error prone. Classically, the programmer solves this problem using a combination of two techniques: the definition of appropriate construction functions for the representatives and the consistent usage of these functions ensured via compiler verifications. The common way of ensuring consistency is to use an abstract data type for the representatives; unfortunately, pattern matching on representatives is lost. A more appealing alternative is to define a concrete data type with private constructors so that both compiler verification and pattern matching on representatives are granted. In this paper, we detail the notion of private data type and study the existence of construction functions. We also describe a prototype, called Moca, that addresses the entire problem of...
Polygon Convexity: Another O(n) Test
Venue: arXiv cs.CG 2007
Year: 2007

An n-gon is defined as a sequence ¶=(V_0,...,V_{n-1}) of n points on the plane. An n-gon ¶is said to be convex if the boundary of the convex hull of the set {V_0,...,V_{n-1}} of the vertices of ¶coincides with the union of the edges [V_0,V_1],...,[V_{n-1},V_0]; if at that no three vertices of ¶are collinear then ¶is called strictly convex. We prove that an n-gon ¶with n\ge3 is strictly convex if and only if a cyclic shift of the sequence (\al_0,...,\al_{n-1})\in[0,2π)^n of the angles between the x-axis and the vectors V_1-V_0,...,V_0-V_{n-1} is strictly monotone. A ``non-strict'' version of this result is also proved.
On the Complexity of a Derivative Chess Problem
Venue: arXiv cs.CC 2007
Year: 2007

We introduce QUEENS, a derivative chess problem based on the classical n-queens problem. We prove that QUEENS is NP-complete, with respect to polynomial-time reductions.
A Simple Proof of the Entropy-Power Inequality via Properties of Mutual Information
Venue: arXiv cs.IT 2007
Year: 2007

While most useful information theoretic inequalities can be deduced from the basic properties of entropy or mutual information, Shannon's entropy power inequality (EPI) seems to be an exception: available information theoretic proofs of the EPI hinge on integral representations of differential entropy using either Fisher's information (FI) or minimum mean-square error (MMSE). In this paper, we first present a unified view of proofs via FI and MMSE, showing that they are essentially dual versions of the same proof, and then fill the gap by providing a new, simple proof of the EPI, which is solely based on the properties of mutual information and sidesteps both FI or MMSE representations.
A bounded-degree network formation game
Venue: arXiv cs.GT 2007
Year: 2007

Motivated by applications in peer-to-peer and overlay networks we define and study the \emph{Bounded Degree Network Formation} (BDNF) game. In an $(n,k)$-BDNF game, we are given $n$ nodes, a bound $k$ on the out-degree of each node, and a weight $w_{vu}$ for each ordered pair $(v,u)$ representing the traffic rate from node $v$ to node $u$. Each node $v$ uses up to $k$ directed links to connect to other nodes with an objective to minimize its average distance, using weights $w_{vu}$, to all other destinations. We study the existence of pure Nash equilibria for $(n,k)$-BDNF games. We show that if the weights are arbitrary, then a pure Nash wiring may not exist. Furthermore, it is NP-hard to determine whether a pure Nash wiring exists for a given $(n,k)$-BDNF instance. A major focus of this paper is on uniform $(n,k)$-BDNF games, in which all weights are 1. We describe how to construct a pure Nash equilibrium wiring given any $n$ and $k$, and establish that in all pure Nash wirings the cost of individual nodes cannot differ by more than a factor of nearly 2, whereas the diameter cannot exceed $O(\sqrt{n \log_k n})$. We also analyze best-response walks on the configuration space defined by the uniform game, and show that starting from any initial configuration, strong connectivity is reached within $Θ(n^2)$ rounds. Convergence to a pure Nash equilibrium, however, is not guaranteed. We present simulation results that suggest that loop-free best-response walks always exist, but may not be polynomially bounded. We also study a special family of \emph{regular} wirings, the class of Abelian Cayley graphs, in which all nodes imitate the same wiring pattern, and show that if $n$ is sufficiently large no such regular wiring can be a pure Nash equilibrium.
Recurrence with affine level mappings is P-time decidable for CLP(R)
Venue: arXiv cs.PL 2007
Year: 2007

In this paper we introduce a class of constraint logic programs such that their termination can be proved by using affine level mappings. We show that membership to this class is decidable in polynomial time.
A Backtracking-Based Algorithm for Computing Hypertree-Decompositions
Venue: arXiv cs.DS 2007
Year: 2007

Hypertree decompositions of hypergraphs are a generalization of tree decompositions of graphs. The corresponding hypertree-width is a measure for the cyclicity and therefore tractability of the encoded computation problem. Many NP-hard decision and computation problems are known to be tractable on instances whose structure corresponds to hypergraphs of bounded hypertree-width. Intuitively, the smaller the hypertree-width, the faster the computation problem can be solved. In this paper, we present the new backtracking-based algorithm det-k-decomp for computing hypertree decompositions of small width. Our benchmark evaluations have shown that det-k-decomp significantly outperforms opt-k-decomp, the only exact hypertree decomposition algorithm so far. Even compared to the best heuristic algorithm, we obtained competitive results as long as the hypergraphs are not too large.
Variations on the Fibonacci Universal Code
Venue: arXiv cs.IT 2007
Year: 2007

This note presents variations on the Fibonacci universal code, that may also be called the Gopala-Hemachandra code, that can have applications in source coding as well as in cryptography.
Propositional theories are strongly equivalent to logic programs
Venue: arXiv cs.AI 2007
Year: 2007

This paper presents a property of propositional theories under the answer sets semantics (called Equilibrium Logic for this general syntax): any theory can always be reexpressed as a strongly equivalent disjunctive logic program, possibly with negation in the head. We provide two different proofs for this result: one involving a syntactic transformation, and one that constructs a program starting from the countermodels of the theory in the intermediate logic of here-and-there.