OpenRaiser/Intern-Atlas huggingface dataset:
CoopGeo: A Beaconless Geographic Cross-Layer Protocol for Cooperative Wireless Ad Hoc Networks
Venue: arXiv cs.NI 2012
Year: 2012

Cooperative relaying has been proposed as a promising transmission technique that effectively creates spatial diversity through the cooperation among spatially distributed nodes. However, to achieve efficient communications while gaining full benefits from cooperation, more interactions at higher protocol layers, particularly the MAC (Medium Access Control) and network layers, are vitally required. This is ignored in most existing articles that mainly focus on physical (PHY)-layer relaying techniques. In this paper, we propose a novel cross-layer framework involving two levels of joint design---a MAC-network cross-layer design for forwarder selection (or termed routing) and a MAC-PHY for relay selection---over symbol-wise varying channels. Based on location knowledge and contention processes, the proposed cross-layer protocol, CoopGeo, aims at providing an efficient, distributed approach to select next hops and optimal relays along a communication path. Simulation results demonstrate that CoopGeo not only operates properly with varying densities of nodes, but performs significantly better than the existing protocol BOSS in terms of packet error rate, transmission error probability, and saturated throughput.
On cyclic codes over the ring $Z_p + uZ_p + ... + u^{k-1}Z_p$
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we study cyclic codes over the ring $ \Z_p + u\Z_p +...+ u^{k-1}\Z_p $, where $u^k =0$. We find a set of generator for these codes. We also study the rank, the dual and the Hamming distance of these codes.
Sample programs in C++ for matrix computations in max plus algebra
Venue: arXiv cs.MS 2012
Year: 2012

The main purpose of this paper is to propose five programs in C++ for matrix computations and solving recurrent equations systems with entries in max plus algebra.
Efficient Methods for Unsupervised Learning of Probabilistic Models
Venue: arXiv cs.LG 2012
Year: 2012

In this thesis I develop a variety of techniques to train, evaluate, and sample from intractable and high dimensional probabilistic models. Abstract exceeds arXiv space limitations -- see PDF.
Task-specific Word-Clustering for Part-of-Speech Tagging
Venue: arXiv cs.CL 2012
Year: 2012

While the use of cluster features became ubiquitous in core NLP tasks, most cluster features in NLP are based on distributional similarity. We propose a new type of clustering criteria, specific to the task of part-of-speech tagging. Instead of distributional similarity, these clusters are based on the beha vior of a baseline tagger when applied to a large corpus. These cluster features provide similar gains in accuracy to those achieved by distributional-similarity derived clusters. Using both types of cluster features together further improve tagging accuracies. We show that the method is effective for both the in-domain and out-of-domain scenarios for English, and for French, German and Italian. The effect is larger for out-of-domain text.
Results on the Fundamental Gain of Memory-Assisted Universal Source Coding
Venue: arXiv cs.IT 2012
Year: 2012

Many applications require data processing to be performed on individual pieces of data which are of finite sizes, e.g., files in cloud storage units and packets in data networks. However, traditional universal compression solutions would not perform well over the finite-length sequences. Recently, we proposed a framework called memory-assisted universal compression that holds a significant promise for reducing the amount of redundant data from the finite-length sequences. The proposed compression scheme is based on the observation that it is possible to learn source statistics (by memorizing previous sequences from the source) at some intermediate entities and then leverage the memorized context to reduce redundancy of the universal compression of finite-length sequences. We first present the fundamental gain of the proposed memory-assisted universal source coding over conventional universal compression (without memorization) for a single parametric source. Then, we extend and investigate the benefits of the memory-assisted universal source coding when the data sequences are generated by a compound source which is a mixture of parametric sources. We further develop a clustering technique within the memory-assisted compression framework to better utilize the memory by classifying the observed data sequences from a mixture of parametric sources. Finally, we demonstrate through computer simulations that the proposed joint memorization and clustering technique can achieve up to 6-fold improvement over the traditional universal compression technique when a mixture of non-binary Markov sources is considered.
From Exact Learning to Computing Boolean Functions and Back Again
Venue: arXiv cs.LG 2012
Year: 2012

The goal of the paper is to relate complexity measures associated with the evaluation of Boolean functions (certificate complexity, decision tree complexity) and learning dimensions used to characterize exact learning (teaching dimension, extended teaching dimension). The high level motivation is to discover non-trivial relations between exact learning of an unknown concept and testing whether an unknown concept is part of a concept class or not. Concretely, the goal is to provide lower and upper bounds of complexity measures for one problem type in terms of the other.
Detours in Scope-Based Route Planning
Venue: arXiv cs.DS 2012
Year: 2012

We study a dynamic scenario of the static route planning problem in road networks. Particularly, we put accent on the most practical dynamic case - increased edge weights (up to infinity). We show how to enhance the scope-based route planning approach presented at ESA'11 to intuitively by-pass closures by detours. Three variants of a detour "admissibility" are presented - from a simple one with straightforward implementation through its enhanced version to a full and very complex variant variant which always returns an optimal detour.
Inferring Taxi Status Using GPS Trajectories
Venue: arXiv cs.AI 2012
Year: 2012

In this paper, we infer the statuses of a taxi, consisting of occupied, non-occupied and parked, in terms of its GPS trajectory. The status information can enable urban computing for improving a city's transportation systems and land use planning. In our solution, we first identify and extract a set of effective features incorporating the knowledge of a single trajectory, historical trajectories and geographic data like road network. Second, a parking status detection algorithm is devised to find parking places (from a given trajectory), dividing a trajectory into segments (i.e., sub-trajectories). Third, we propose a two-phase inference model to learn the status (occupied or non-occupied) of each point from a taxi segment. This model first uses the identified features to train a local probabilistic classifier and then carries out a Hidden Semi-Markov Model (HSMM) for globally considering long term travel patterns. We evaluated our method with a large-scale real-world trajectory dataset generated by 600 taxis, showing the advantages of our method over baselines.
Memory Lower Bounds for Randomized Collaborative Search and Applications to Biology
Venue: arXiv cs.DC 2012
Year: 2012

Initial knowledge regarding group size can be crucial for collective performance. We study this relation in the context of the {\em Ants Nearby Treasure Search (ANTS)} problem \cite{FKLS}, which models natural cooperative foraging behavior such as that performed by ants around their nest. In this problem, $k$ (probabilistic) agents, initially placed at some central location, collectively search for a treasure on the two-dimensional grid. The treasure is placed at a target location by an adversary and the goal is to find it as fast as possible as a function of both $k$ and $D$, where $D$ is the (unknown) distance between the central location and the target. It is easy to see that $T=Ω(D+D^2/k)$ time units are necessary for finding the treasure. Recently, it has been established that $O(T)$ time is sufficient if the agents know their total number $k$ (or a constant approximation of it), and enough memory bits are available at their disposal \cite{FKLS}. In this paper, we establish lower bounds on the agent memory size required for achieving certain running time performances. To the best our knowledge, these bounds are the first non-trivial lower bounds for the memory size of probabilistic searchers. For example, for every given positive constant $ε$, terminating the search by time $O(\log^{1-ε} k \cdot T)$ requires agents to use $Ω(\log\log k)$ memory bits. Such distributed computing bounds may provide a novel, strong tool for the investigation of complex biological systems.
Sparse Signal Recovery in Hilbert Spaces
Venue: arXiv cs.IT 2012
Year: 2012

This paper reports an effort to consolidate numerous coherence-based sparse signal recovery results available in the literature. We present a single theory that applies to general Hilbert spaces with the sparsity of a signal defined as the number of (possibly infinite-dimensional) subspaces participating in the signal's representation. Our general results recover uncertainty relations and coherence-based recovery thresholds for sparse signals, block-sparse signals, multi-band signals, signals in shift-invariant spaces, and signals in finite unions of (possibly infinite-dimensional) subspaces. Moreover, we improve upon and generalize several of the existing results and, in many cases, we find shortened and simplified proofs.
Visual and semantic interpretability of projections of high dimensional data for classification tasks
Venue: arXiv cs.HC 2012
Year: 2012

A number of visual quality measures have been introduced in visual analytics literature in order to automatically select the best views of high dimensional data from a large number of candidate data projections. These methods generally concentrate on the interpretability of the visualization and pay little attention to the interpretability of the projection axes. In this paper, we argue that interpretability of the visualizations and the feature transformation functions are both crucial for visual exploration of high dimensional labeled data. We present a two-part user study to examine these two related but orthogonal aspects of interpretability. We first study how humans judge the quality of 2D scatterplots of various datasets with varying number of classes and provide comparisons with ten automated measures, including a number of visual quality measures and related measures from various machine learning fields. We then investigate how the user perception on interpretability of mathematical expressions relate to various automated measures of complexity that can be used to characterize data projection functions. We conclude with a discussion of how automated measures of visual and semantic interpretability of data projections can be used together for exploratory analysis in classification tasks.
Selective Coding Strategy for Unicast Composite Networks
Venue: arXiv cs.IT 2012
Year: 2012

Consider a composite unicast relay network where the channel statistic is randomly drawn from a set of conditional distributions indexed by a random variable, which is assumed to be unknown at the source, fully known at the destination and only partly known at the relays. Commonly, the coding strategy at each relay is fixed regardless of its channel measurement. A novel coding for unicast composite networks with multiple relays is introduced. This enables the relays to select dynamically --based on its channel measurement-- the best coding scheme between compress-and-forward (CF) and decode-and-forward (DF). As a part of the main result, a generalization of Noisy Network Coding is shown for the case of unicast general networks where the relays are divided between those using DF and CF coding. Furthermore, the relays using DF scheme can exploit the help of those based on CF scheme via offset coding. It is demonstrated via numerical results that this novel coding, referred to as Selective Coding Strategy (SCS), outperforms conventional coding schemes.
Effective and efficient approximations of the generalized inverse of the graph Laplacian matrix with an application to current-flow betweenness centrality
Venue: arXiv cs.SI 2012
Year: 2012

We devise methods for finding approximations of the generalized inverse of the graph Laplacian matrix, which arises in many graph-theoretic applications. Finding this matrix in its entirety involves solving a matrix inversion problem, which is resource demanding in terms of consumed time and memory and hence impractical whenever the graph is relatively large. Our approximations use only few eigenpairs of the Laplacian matrix and are parametric with respect to this number, so that the user can compromise between effectiveness and efficiency of the approximated solution. We apply the devised approximations to the problem of computing current-flow betweenness centrality on a graph. However, given the generality of the Laplacian matrix, many other applications can be sought. We experimentally demonstrate that the approximations are effective already with a constant number of eigenpairs. These few eigenpairs can be stored with a linear amount of memory in the number of nodes of the graph and, in the realistic case of sparse networks, they can be efficiently computed using one of the many methods for retrieving few eigenpairs of sparse matrices that abound in the literature.
FragIt: A Tool to Prepare Input Files for Fragment Based Quantum Chemical Calculations
Venue: arXiv cs.CE 2012
Year: 2012

Near linear scaling fragment based quantum chemical calculations are becoming increasingly popular for treating large systems with high accuracy and is an active field of research. However, it remains difficult to set up these calculations without expert knowledge. To facilitate the use of such methods, software tools need to be available to support these methods and help to set up reasonable input files which will lower the barrier of entry for usage by non-experts. Previous tools relies on specific annotations in structure files for automatic and successful fragmentation such as residues in PDB files. We present a general fragmentation methodology and accompanying tools called FragIt to help setup these calculations. FragIt uses the SMARTS language to locate chemically appropriate fragments in large structures and is applicable to fragmentation of any molecular system given suitable SMARTS patterns. We present SMARTS patterns of fragmentation for proteins, DNA and polysaccharides, specifically for D-galactopyranose for use in cyclodextrins. FragIt is used to prepare input files for the Fragment Molecular Orbital method in the GAMESS program package, but can be extended to other computational methods easily.
Interference and Throughput in Aloha-based Ad Hoc Networks with Isotropic Node Distribution
Venue: arXiv cs.IT 2012
Year: 2012

We study the interference and outage statistics in a slotted Aloha ad hoc network, where the spatial distribution of nodes is non-stationary and isotropic. In such a network, outage probability and local throughput depend on both the particular location in the network and the shape of the spatial distribution. We derive in closed-form certain distributional properties of the interference that are important for analyzing wireless networks as a function of the location and the spatial shape. Our results focus on path loss exponents 2 and 4, the former case not being analyzable before due to the stationarity assumption of the spatial node distribution. We propose two metrics for measuring local throughput in non-stationary networks and discuss how our findings can be applied to both analysis and optimization.
Proportional Fair Resource Allocation on an Energy Harvesting Downlink - Part I: Structure
Venue: arXiv cs.NI 2012
Year: 2012

This paper considers the allocation of time slots in a frame, as well as power and rate to multiple receivers on an energy harvesting downlink. Energy arrival times that will occur within the frame are known at the beginning of the frame. The goal is to optimize throughput in a proportionally fair way, taking into account the inherent differences of channel quality among users. Analysis of structural characteristics of the problem reveals that it can be formulated as a biconvex optimization problem, and that it has multiple optima. Due to the biconvex nature of the problem, a Block Coordinate Descent (BCD) based optimization algorithm that converges to an optimal solution is presented. Numerical and simulation results show that the power-time allocations found by BCD achieve a good balance between total throughput and fairness.
Coloring and Guarding Arrangements
Venue: arXiv cs.CG 2012
Year: 2012

Given an arrangement of lines in the plane, what is the minimum number $c$ of colors required to color the lines so that no cell of the arrangement is monochromatic? In this paper we give bounds on the number c both for the above question, as well as some of its variations. We redefine these problems as geometric hypergraph coloring problems. If we define $\Hlinecell$ as the hypergraph where vertices are lines and edges represent cells of the arrangement, the answer to the above question is equal to the chromatic number of this hypergraph. We prove that this chromatic number is between $Ω(\log n / \log\log n)$. and $O(\sqrt{n})$. Similarly, we give bounds on the minimum size of a subset $S$ of the intersections of the lines in $\mathcal{A}$ such that every cell is bounded by at least one of the vertices in $S$. This may be seen as a problem on guarding cells with vertices when the lines act as obstacles. The problem can also be defined as the minimum vertex cover problem in the hypergraph $\Hvertexcell$, the vertices of which are the line intersections, and the hyperedges are vertices of a cell. Analogously, we consider the problem of touching the lines with a minimum subset of the cells of the arrangement, which we identify as the minimum vertex cover problem in the $\Hcellzone$ hypergraph.
On Optimality of Myopic Policy for Restless Multi-armed Bandit Problem with Non i.i.d. Arms and Imperfect Detection
Venue: arXiv cs.SY 2012
Year: 2012

We consider the channel access problem in a multi-channel opportunistic communication system with imperfect channel sensing, where the state of each channel evolves as a non independent and identically distributed Markov process. This problem can be cast into a restless multi-armed bandit (RMAB) problem that is intractable for its exponential computation complexity. A natural alternative is to consider the easily implementable myopic policy that maximizes the immediate reward but ignores the impact of the current strategy on the future reward. In particular, we develop three axioms characterizing a family of generic and practically important functions termed as $g$-regular functions which includes a wide spectrum of utility functions in engineering. By pursuing a mathematical analysis based on the axioms, we establish a set of closed-form structural conditions for the optimality of myopic policy.
Beyond citations: Scholars' visibility on the social Web
Venue: arXiv cs.DL 2012
Year: 2012

Traditionally, scholarly impact and visibility have been measured by counting publications and citations in the scholarly literature. However, increasingly scholars are also visible on the Web, establishing presences in a growing variety of social ecosystems. But how wide and established is this presence, and how do measures of social Web impact relate to their more traditional counterparts? To answer this, we sampled 57 presenters from the 2010 Leiden STI Conference, gathering publication and citations counts as well as data from the presenters' Web "footprints." We found Web presence widespread and diverse: 84% of scholars had homepages, 70% were on LinkedIn, 23% had public Google Scholar profiles, and 16% were on Twitter. For sampled scholars' publications, social reference manager bookmarks were compared to Scopus and Web of Science citations; we found that Mendeley covers more than 80% of sampled articles, and that Mendeley bookmarks are significantly correlated (r=.45) to Scopus citation counts.
Implementation of an Onboard Visual Tracking System with Small Unmanned Aerial Vehicle (UAV)
Venue: arXiv cs.RO 2012
Year: 2012

This paper presents a visual tracking system that is capable or running real time on-board a small UAV (Unmanned Aerial Vehicle). The tracking system is computationally efficient and invariant to lighting changes and rotation of the object or the camera. Detection and tracking is autonomously carried out on the payload computer and there are two different methods for creation of the image patches. The first method starts detecting and tracking using a stored image patch created prior to flight with previous flight data. The second method allows the operator on the ground to select the interest object for the UAV to track. The tracking system is capable of re-detecting the object of interest in the events of tracking failure. Performance of the tracking system was verified both in the lab and during actual flights of the UAV. Results show that the system can run on-board and track a diverse set of objects in real time.
Joint Compute and Forward for the Two Way Relay Channel with Spatially Coupled LDPC Codes
Venue: arXiv cs.IT 2012
Year: 2012

We consider the design and analysis of coding schemes for the binary input two way relay channel with erasure noise. We are particularly interested in reliable physical layer network coding in which the relay performs perfect error correction prior to forwarding messages. The best known achievable rates for this problem can be achieved through either decode and forward or compute and forward relaying. We consider a decoding paradigm called joint compute and forward which we numerically show can achieve the best of these rates with a single encoder and decoder. This is accomplished by deriving the exact performance of a message passing decoder based on joint compute and forward for spatially coupled LDPC ensembles.
Achievable Rate Regions for the Dirty Multiple Access Channel with Partial Side Information at the Transmitters
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we establish achievable rate regions for the multiple access channel (MAC) with side information partially known (estimated or sensed version) at the transmitters. Actually, we extend the lattice strategies used by Philosof-Zamir for the MAC with full side information at the transmitters to the partially known case. We show that the sensed or estimated side information reduces the rate regions, the same as that occurs for Costa Gaussian channel.
Consumer Search with Chain Stores
Venue: arXiv cs.GT 2012
Year: 2012

The paper explores a consumer search setting where the sellers have asymmetries. The model is an extension of the popular Stahl Model, which is widely used in the literature. The extension introduces sellers with heterogeneous stores number, reflecting the typical market structure. The market consists of several sellers heterogeneous in size consumers, some of which face a cost when sequentially searching. The paper shows that no symmetric model exist in the extension and asymmetric NE of the Stahl model are found for comparison. Additional results suggest that smallest sellers will be the ones offering lowest prices, in line with several real world examples provided in the paper. However, profits remain in most cases fixed per store, making a larger firm more profitable, yet with lower sold quantity. The findings suggest that on some level price dispersion will still exist, together with some level of price stickiness, both observed in reality.