OpenRaiser/Intern-Atlas huggingface dataset:
A principal component analysis of 39 scientific impact measures
Venue: arXiv cs.DL 2009
Year: 2009

The impact of scientific publications has traditionally been expressed in terms of citation counts. However, scientific activity has moved online over the past decade. To better capture scientific impact in the digital era, a variety of new impact measures has been proposed on the basis of social network analysis and usage log data. Here we investigate how these new measures relate to each other, and how accurately and completely they express scientific impact. We performed a principal component analysis of the rankings produced by 39 existing and proposed measures of scholarly impact that were calculated on the basis of both citation and usage log data. Our results indicate that the notion of scientific impact is a multi-dimensional construct that can not be adequately measured by any single indicator, although some measures are more suitable than others. The commonly used citation Impact Factor is not positioned at the core of this construct, but at its periphery, and should thus be used with caution.
What's in a Message?
Venue: arXiv cs.CL 2009
Year: 2009

In this paper we present the first step in a larger series of experiments for the induction of predicate/argument structures. The structures that we are inducing are very similar to the conceptual structures that are used in Frame Semantics (such as FrameNet). Those structures are called messages and they were previously used in the context of a multi-document summarization system of evolving events. The series of experiments that we are proposing are essentially composed from two stages. In the first stage we are trying to extract a representative vocabulary of words. This vocabulary is later used in the second stage, during which we apply to it various clustering approaches in order to identify the clusters of predicates and arguments--or frames and semantic roles, to use the jargon of Frame Semantics. This paper presents in detail and evaluates the first stage.
Power Allocation Games for MIMO Multiple Access Channels with Coordination
Venue: arXiv cs.IT 2009
Year: 2009

A game theoretic approach is used to derive the optimal decentralized power allocation (PA) in fast fading multiple access channels where the transmitters and receiver are equipped with multiple antennas. The players (the mobile terminals) are free to choose their PA in order to maximize their individual transmission rates (in particular they can ignore some specified centralized policies). A simple coordination mechanism between users is introduced. The nature and influence of this mechanism is studied in detail. The coordination signal indicates to the users the order in which the receiver applies successive interference cancellation and the frequency at which this order is used. Two different games are investigated: the users can either adapt their temporal PA to their decoding rank at the receiver or optimize their spatial PA between their transmit antennas. For both games a thorough analysis of the existence, uniqueness and sum-rate efficiency of the network Nash equilibrium is conducted. Analytical and simulation results are provided to assess the gap between the decentralized network performance and its equivalent virtual multiple input multiple output system, which is shown to be zero in some cases and relatively small in general.
A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression
Venue: arXiv cs.CC 2009
Year: 2009

We present a unified framework for accelerating edit-distance computation between two compressible strings using straight-line programs. For two strings of total length $N$ having straight-line program representations of total size $n$, we provide an algorithm running in $O(n^{1.4}N^{1.2})$ time for computing the edit-distance of these two strings under any rational scoring function, and an $O(n^{1.34}N^{1.34})$ time algorithm for arbitrary scoring functions. This improves on a recent algorithm of Tiskin that runs in $O(nN^{1.5})$ time, and works only for rational scoring functions. Also, in the last part of the paper, we show how the classical four-russians technique can be incorporated into our SLP edit-distance scheme, giving us a simple $Ω(\lg N)$ speed-up in the case of arbitrary scoring functions, for any pair of strings.
Random Fruits on the Zielonka Tree
Venue: arXiv cs.GT 2009
Year: 2009

Stochastic games are a natural model for the synthesis of controllers confronted to adversarial and/or random actions. In particular, $ω$-regular games of infinite length can represent reactive systems which are not expected to reach a correct state, but rather to handle a continuous stream of events. One critical resource in such applications is the memory used by the controller. In this paper, we study the amount of memory that can be saved through the use of randomisation in strategies, and present matching upper and lower bounds for stochastic Muller games.
Ontology-Based Annotation of Multimedia Language Data for the Semantic Web
Venue: arXiv cs.DL 2009
Year: 2009

There is an increasing interest and effort in preserving and documenting endangered languages. Language data are valuable only when they are well-cataloged, indexed and searchable. Many language data, particularly those of lesser-spoken languages, are collected as audio and video recordings. While multimedia data provide more channels and dimensions to describe a language's function, and gives a better presentation of the cultural system associated with the language of that community, they are not text-based or structured (in binary format), and their semantics is implicit in their content. The content is thus easy for a human being to understand, but difficult for computers to interpret. Hence, there is a great need for a powerful and user-friendly system to annotate multimedia data with text-based, well-structured and searchable metadata. This chapter describes an ontology-based multimedia annotation tool, OntoELAN, that enables annotation of language multimedia data with a linguistic ontology.
The Multi-Branched Method of Moments for Queueing Networks
Venue: arXiv cs.PF 2009
Year: 2009

We propose a new exact solution algorithm for closed multiclass product-form queueing networks that is several orders of magnitude faster and less memory consuming than established methods for multiclass models, such as the Mean Value Analysis (MVA) algorithm. The technique is an important generalization of the recently proposed Method of Moments (MoM) which, differently from MVA, recursively computes higher-order moments of queue-lengths instead of mean values. The main contribution of this paper is to prove that the information used in the MoM recursion can be increased by considering multiple recursive branches that evaluate models with different number of queues. This reformulation allows to formulate a simpler matrix difference equation which leads to large computational savings with respect to the original MoM recursion. Computational analysis shows several cases where the proposed algorithm is between 1,000 and 10,000 times faster and less memory consuming than the original MoM, thus extending the range of multiclass models where exact solutions are feasible.
Syntactic variation of support verb constructions
Venue: arXiv cs.CL 2009
Year: 2009

We report experiments about the syntactic variations of support verb constructions, a special type of multiword expressions (MWEs) containing predicative nouns. In these expressions, the noun can occur with or without the verb, with no clear-cut semantic difference. We extracted from a large French corpus a set of examples of the two situations and derived statistical results from these data. The extraction involved large-coverage language resources and finite-state techniques. The results show that, most frequently, predicative nouns occur without a support verb. This fact has consequences on methods of extracting or recognising MWEs.
On Framework and Hybrid Auction Approach to the Spectrum Licensing Procedure
Venue: arXiv cs.GT 2009
Year: 2009

Inspired by the recent developments in the field of Spectrum Auctions, we have tried to provide a comprehensive framework for the complete procedure of Spectrum Licensing. We have identified the various issues the Governments need to decide upon while designing the licensing procedure and what are the various options available in each issue. We also provide an in depth study of how each of this options impact the overall procedure along with theoretical and practical results from the past. Lastly we argue as to how we can combine the positives two most widely used Spectrum Auctions mechanisms into the Hybrid Multiple Round Auction mechanism being proposed by us.
The One-Way Communication Complexity of Group Membership
Venue: arXiv cs.CC 2009
Year: 2009

This paper studies the one-way communication complexity of the subgroup membership problem, a classical problem closely related to basic questions in quantum computing. Here Alice receives, as input, a subgroup $H$ of a finite group $G$; Bob receives an element $x \in G$. Alice is permitted to send a single message to Bob, after which he must decide if his input $x$ is an element of $H$. We prove the following upper bounds on the classical communication complexity of this problem in the bounded-error setting: (1) The problem can be solved with $O(\log |G|)$ communication, provided the subgroup $H$ is normal; (2) The problem can be solved with $O(d_{\max} \cdot \log |G|)$ communication, where $d_{\max}$ is the maximum of the dimensions of the irreducible complex representations of $G$; (3) For any prime $p$ not dividing $|G|$, the problem can be solved with $O(d_{\max} \cdot \log p)$ communication, where $d_{\max}$ is the maximum of the dimensions of the irreducible $\F_p$-representations of $G$.
Symbolic Computing with Incremental Mindmaps to Manage and Mine Data Streams - Some Applications
Venue: arXiv cs.NE 2009
Year: 2009

In our understanding, a mind-map is an adaptive engine that basically works incrementally on the fundament of existing transactional streams. Generally, mind-maps consist of symbolic cells that are connected with each other and that become either stronger or weaker depending on the transactional stream. Based on the underlying biologic principle, these symbolic cells and their connections as well may adaptively survive or die, forming different cell agglomerates of arbitrary size. In this work, we intend to prove mind-maps' eligibility following diverse application scenarios, for example being an underlying management system to represent normal and abnormal traffic behaviour in computer networks, supporting the detection of the user behaviour within search engines, or being a hidden communication layer for natural language interaction.
Random numbers from the tails of probability distributions using the transformation method
Venue: arXiv cs.MS 2009
Year: 2009

The speed of many one-line transformation methods for the production of, for example, Levy alpha-stable random numbers, which generalize Gaussian ones, and Mittag-Leffler random numbers, which generalize exponential ones, is very high and satisfactory for most purposes. However, for the class of decreasing probability densities fast rejection implementations like the Ziggurat by Marsaglia and Tsang promise a significant speed-up if it is possible to complement them with a method that samples the tails of the infinite support. This requires the fast generation of random numbers greater or smaller than a certain value. We present a method to achieve this, and also to generate random numbers within any arbitrary interval. We demonstrate the method showing the properties of the transform maps of the above mentioned distributions as examples of stable and geometric stable random numbers used for the stochastic solution of the space-time fractional diffusion equation.
Computing k-Centers On a Line
Venue: arXiv cs.CG 2009
Year: 2009

In this paper we consider several instances of the k-center on a line problem where the goal is, given a set of points S in the plane and a parameter k >= 1, to find k disks with centers on a line l such that their union covers S and the maximum radius of the disks is minimized. This problem is a constraint version of the well-known k-center problem in which the centers are constrained to lie in a particular region such as a segment, a line, and a polygon. We first consider the simplest version of the problem where the line l is given in advance; we can solve this problem in O(n log^2 n) time. We then investigate the cases where only the orientation of the line l is fixed and where the line l can be arbitrary. We can solve these problems in O(n^2 log^2 n) time and in O(n^4 log^2 n) expected time, respectively. For the last two problems, we present (1 + e)-approximation algorithms, which run in O((1/e) n log^2 n) time and O((1/e^2) n log^2 n) time, respectively.
A Superstabilizing $\log(n)$-Approximation Algorithm for Dynamic Steiner Trees
Venue: arXiv cs.DC 2009
Year: 2009

In this paper we design and prove correct a fully dynamic distributed algorithm for maintaining an approximate Steiner tree that connects via a minimum-weight spanning tree a subset of nodes of a network (referred as Steiner members or Steiner group) . Steiner trees are good candidates to efficiently implement communication primitives such as publish/subscribe or multicast, essential building blocks for the new emergent networks (e.g. P2P, sensor or adhoc networks). The cost of the solution returned by our algorithm is at most $\log |S|$ times the cost of an optimal solution, where $S$ is the group of members. Our algorithm improves over existing solutions in several ways. First, it tolerates the dynamism of both the group members and the network. Next, our algorithm is self-stabilizing, that is, it copes with nodes memory corruption. Last but not least, our algorithm is \emph{superstabilizing}. That is, while converging to a correct configuration (i.e., a Steiner tree) after a modification of the network, it keeps offering the Steiner tree service during the stabilization time to all members that have not been affected by this modification.
lim+, delta+, and Non-Permutability of beta-Steps
Venue: arXiv cs.AI 2009
Year: 2009

Using a human-oriented formal example proof of the (lim+) theorem, i.e. that the sum of limits is the limit of the sum, which is of value for reference on its own, we exhibit a non-permutability of beta-steps and delta+-steps (according to Smullyan's classification), which is not visible with non-liberalized delta-rules and not serious with further liberalized delta-rules, such as the delta++-rule. Besides a careful presentation of the search for a proof of (lim+) with several pedagogical intentions, the main subject is to explain why the order of beta-steps plays such a practically important role in some calculi.
Full First-Order Sequent and Tableau Calculi With Preservation of Solutions and the Liberalized delta-Rule but Without Skolemization
Venue: arXiv cs.AI 2009
Year: 2009

We present a combination of raising, explicit variable dependency representation, the liberalized delta-rule, and preservation of solutions for first-order deductive theorem proving. Our main motivation is to provide the foundation for our work on inductive theorem proving, where the preservation of solutions is indispensable.
Coordination in multiagent systems and Laplacian spectra of digraphs
Venue: arXiv cs.MA 2009
Year: 2009

Constructing and studying distributed control systems requires the analysis of the Laplacian spectra and the forest structure of directed graphs. In this paper, we present some basic results of this analysis partially obtained by the present authors. We also discuss the application of these results to decentralized control and touch upon some problems of spectral graph theory.
Multiplicative updates For Non-Negative Kernel SVM
Venue: arXiv cs.LG 2009
Year: 2009

We present multiplicative updates for solving hard and soft margin support vector machines (SVM) with non-negative kernels. They follow as a natural extension of the updates for non-negative matrix factorization. No additional param- eter setting, such as choosing learning, rate is required. Ex- periments demonstrate rapid convergence to good classifiers. We analyze the rates of asymptotic convergence of the up- dates and establish tight bounds. We test the performance on several datasets using various non-negative kernels and report equivalent generalization errors to that of a standard SVM.
From Theory to Practice: Sub-Nyquist Sampling of Sparse Wideband Analog Signals
Venue: arXiv cs.IT 2009
Year: 2009

Conventional sub-Nyquist sampling methods for analog signals exploit prior information about the spectral support. In this paper, we consider the challenging problem of blind sub-Nyquist sampling of multiband signals, whose unknown frequency support occupies only a small portion of a wide spectrum. Our primary design goals are efficient hardware implementation and low computational load on the supporting digital processing. We propose a system, named the modulated wideband converter, which first multiplies the analog signal by a bank of periodic waveforms. The product is then lowpass filtered and sampled uniformly at a low rate, which is orders of magnitude smaller than Nyquist. Perfect recovery from the proposed samples is achieved under certain necessary and sufficient conditions. We also develop a digital architecture, which allows either reconstruction of the analog input, or processing of any band of interest at a low rate, that is, without interpolating to the high Nyquist rate. Numerical simulations demonstrate many engineering aspects: robustness to noise and mismodeling, potential hardware simplifications, realtime performance for signals with time-varying support and stability to quantization effects. We compare our system with two previous approaches: periodic nonuniform sampling, which is bandwidth limited by existing hardware devices, and the random demodulator, which is restricted to discrete multitone signals and has a high computational load. In the broader context of Nyquist sampling, our scheme has the potential to break through the bandwidth barrier of state-of-the-art analog conversion technologies such as interleaved converters.
Stability of Finite Population ALOHA with Variable Packets
Venue: arXiv cs.PF 2009
Year: 2009

ALOHA is one of the most basic Medium Access Control (MAC) protocols and represents a foundation for other more sophisticated distributed and asynchronous MAC protocols, e.g., CSMA. In this paper, unlike in the traditional work that focused on mean value analysis, we study the distributional properties of packet transmission delays over an ALOHA channel. We discover a new phenomenon showing that a basic finite population ALOHA model with variable size (exponential) packets is characterized by power law transmission delays, possibly even resulting in zero throughput. These results are in contrast to the classical work that shows exponential delays and positive throughput for finite population ALOHA with fixed packets. Furthermore, we characterize a new stability condition that is entirely derived from the tail behavior of the packet and backoff distributions that may not be determined by mean values. The power law effects and the possible instability might be diminished, or perhaps eliminated, by reducing the variability of packets. However, we show that even a slotted (synchronized) ALOHA with packets of constant size can exhibit power law delays when the number of active users is random. From an engineering perspective, our results imply that the variability of packet sizes and number of active users need to be taken into consideration when designing robust MAC protocols, especially for ad-hoc/sensor networks where other factors, such as link failures and mobility, might further compound the problem.
Cyclic Codes and Sequences from Kasami-Welch Functions
Venue: arXiv cs.IT 2009
Year: 2009

Let $q=2^n$, $0\leq k\leq n-1$ and $k\neq n/2$. In this paper we determine the value distribution of following exponential sums \[\sum\limits_{x\in \bF_q}(-1)^{\Tra_1^n(αx^{2^{3k}+1}+βx^{2^k+1})}\quad(α,β\in \bF_{q})\] and \[\sum\limits_{x\in \bF_q}(-1)^{\Tra_1^n(αx^{2^{3k}+1}+βx^{2^k+1}+\ga x)}\quad(α,β,\ga\in \bF_{q})\] where $\Tra_1^n: \bF_{2^n}\ra \bF_2$ is the canonical trace mapping. As applications: (1). We determine the weight distribution of the binary cyclic codes $\cC_1$ and $\cC_2$ with parity-check polynomials $h_2(x)h_3(x)$ and $h_1(x)h_2(x)h_3(x)$ respectively where $h_1(x)$, $h_2(x)$ and $h_3(x)$ are the minimal polynomials of $π^{-1}$, $π^{-(2^k+1)}$ and $π^{-(2^{3k}+1)}$ respectively for a primitive element $π$ of $\bF_q$. (2). We determine the correlation distribution among a family of binary m-sequences.
Are Tensor Decomposition Solutions Unique? On the global convergence of HOSVD and ParaFac algorithms
Venue: arXiv cs.CV 2009
Year: 2009

For tensor decompositions such as HOSVD and ParaFac, the objective functions are nonconvex. This implies, theoretically, there exists a large number of local optimas: starting from different starting point, the iteratively improved solution will converge to different local solutions. This non-uniqueness present a stability and reliability problem for image compression and retrieval. In this paper, we present the results of a comprehensive investigation of this problem. We found that although all tensor decomposition algorithms fail to reach a unique global solution on random data and severely scrambled data; surprisingly however, on all real life several data sets (even with substantial scramble and occlusions), HOSVD always produce the unique global solution in the parameter region suitable to practical applications, while ParaFac produce non-unique solutions. We provide an eigenvalue based rule for the assessing the solution uniqueness.
EXtensible Animator for Mobile Simulations: EXAMS
Venue: arXiv cs.NI 2009
Year: 2009

One of the most widely used simulation environments for mobile wireless networks is the Network Simulator 2 (NS-2). However NS-2 stores its outcome in a text file, so there is a need for a visualization tool to animate the simulation of the wireless network. The purpose of this tool is to help the researcher examine in detail how the wireless protocol works both on a network and a node basis. It is clear that much of this information is protocol dependent and cannot be depicted properly by a general purpose animation process. Existing animation tools do not provide this level of information neither permit the specific protocol to control the animation at all. EXAMS is an NS-2 visualization tool for mobile simulations which makes possible the portrayal of NS-2 internal information like transmission properties and node data structures. This is mainly possible due to EXAMS extensible architecture which separates the animation process into a general and a protocol specific part. The latter can be developed independently by the protocol designer and loaded on demand. These and other useful characteristics of the EXAMS tool can be an invaluable help for a researcher in order to investigate and debug a mobile networking protocol.