OpenRaiser/Intern-Atlas huggingface dataset:
Average Error Probability Analysis in mmWave Cellular Networks
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, a mathematical framework for the analysis of average symbol error probability (ASEP) in millimeter wave (mmWave) cellular networks with Poisson Point Process (PPP) distributed base stations (BSs) is developed using tools from stochastic geometry. The distinguishing features of mmWave communications such as directional beamforming and having different path loss laws for line-of-sight (LOS) and non-line-of-sight (NLOS) links are incorporated in the average error probability analysis. First, average pairwise error probability (APEP) expression is obtained by averaging pairwise error probability (PEP) over fading and random shortest distance from mobile user (MU) to its serving BS. Subsequently, average symbol error probability is approximated from APEP using the nearest neighbor (NN) approximation. ASEP is analyzed for different antenna gains and base station densities. Finally, the effect of beamforming alignment errors on ASEP is investigated to get insight on more realistic cases.
Temporal Identification of Latent Communities on Twitter
Venue: arXiv cs.SI 2015
Year: 2015

User communities in social networks are usually identified by considering explicit structural social connections between users. While such communities can reveal important information about their members such as family or friendship ties and geographical proximity, they do not necessarily succeed at pulling like-minded users that share the same interests together. In this paper, we are interested in identifying communities of users that share similar topical interests over time, regardless of whether they are explicitly connected to each other on the social network. More specifically, we tackle the problem of identifying temporal topic-based communities from Twitter, i.e., communities of users who have similar temporal inclination towards the current emerging topics on Twitter. We model each topic as a collection of highly correlated semantic concepts observed in tweets and identify them by clustering the time-series based representation of each concept built based on each concept's observation frequency over time. Based on the identified emerging topics in a given time period, we utilize multivariate time series analysis to model the contributions of each user towards the identified topics, which allows us to detect latent user communities. Through our experiments on Twitter data, we demonstrate i) the effectiveness of our topic detection method to detect real world topics and ii) the effectiveness of our approach compared to well-established approaches for community detection.
gSLICr: SLIC superpixels at over 250Hz
Venue: arXiv cs.CV 2015
Year: 2015

We introduce a parallel GPU implementation of the Simple Linear Iterative Clustering (SLIC) superpixel segmentation. Using a single graphic card, our implementation achieves speedups of up to $83\times$ from the standard sequential implementation. Our implementation is fully compatible with the standard sequential implementation and the software is now available online and is open source.
High Speed VLSI Architecture for 3-D Discrete Wavelet Transform
Venue: arXiv cs.AR 2015
Year: 2015

This paper presents a memory efficient, high throughput parallel lifting based running three dimensional discrete wavelet transform (3-D DWT) architecture. 3-D DWT is constructed by combining the two spatial and four temporal processors. Spatial processor (SP) apply the two dimensional DWT on a frame, using lifting based 9/7 filter bank through the row rocessor (RP) in row direction and then apply in the colum direction through column processor (CP). To reduce the temporal memory and the latency, the temporal processor (TP) has been designed with lifting based 1-D Haar wavelet filter. The proposed architecture replaced the multiplications by pipeline shift-add operations to reduce the CPD. Two spatial processors works simultaneously on two adjacent frames and provide 2-D DWT coefficients as inputs to the temporal processors. TPs apply the one dimensional DWT in temporal direction and provide eight 3-D DWT coefficients per clock (throughput). Higher throughput reduces the computing cycles per frame and enable the lower power consumption. Implementation results shows that the proposed architecture has the advantage in reduced memory, low power consumption, low latency, and high throughput over the existing designs. The RTL of the proposed architecture is described using verilog and synthesized using 90-nm technology CMOS standard cell library and results show that it consumes 43.42 mW power and occupies an area equivalent to 231.45 K equivalent gate at frequency of 200 MHz. The proposed architecture has also been synthesised for the Xilinx zynq 7020 series field programmable gate array (FPGA).
Precise Phase Transition of Total Variation Minimization
Venue: arXiv cs.IT 2015
Year: 2015

Characterizing the phase transitions of convex optimizations in recovering structured signals or data is of central importance in compressed sensing, machine learning and statistics. The phase transitions of many convex optimization signal recovery methods such as $\ell_1$ minimization and nuclear norm minimization are well understood through recent years' research. However, rigorously characterizing the phase transition of total variation (TV) minimization in recovering sparse-gradient signal is still open. In this paper, we fully characterize the phase transition curve of the TV minimization. Our proof builds on Donoho, Johnstone and Montanari's conjectured phase transition curve for the TV approximate message passing algorithm (AMP), together with the linkage between the minmax Mean Square Error of a denoising problem and the high-dimensional convex geometry for TV minimization.
Adaptive Lookup for Unstructured Peer-to-Peer Overlays
Venue: arXiv cs.NI 2015
Year: 2015

Scalability and efficient global search in unstructured peer-to-peer overlays have been extensively studied in the literature. The global search comes at the expense of local interactions between peers. Most of the unstructured peer-to-peer overlays do not provide any performance guarantee. In this work we propose a novel Quality of Service enabled lookup for unstructured peer-to-peer overlays that will allow the user's query to traverse only those overlay links which satisfy the given constraints. Additionally, it also improves the scalability by judiciously using the overlay resources. Our approach selectively forwards the queries using QoS metrics like latency, bandwidth, and overlay link status so as to ensure improved performance in a scenario where the degree of peer joins and leaves are high. User is given only those results which can be downloaded with the given constraints. Also, the protocol aims at minimizing the message overhead over the overlay network.
On Reasoning with RDF Statements about Statements using Singleton Property Triples
Venue: arXiv cs.AI 2015
Year: 2015

The Singleton Property (SP) approach has been proposed for representing and querying metadata about RDF triples such as provenance, time, location, and evidence. In this approach, one singleton property is created to uniquely represent a relationship in a particular context, and in general, generates a large property hierarchy in the schema. It has become the subject of important questions from Semantic Web practitioners. Can an existing reasoner recognize the singleton property triples? And how? If the singleton property triples describe a data triple, then how can a reasoner infer this data triple from the singleton property triples? Or would the large property hierarchy affect the reasoners in some way? We address these questions in this paper and present our study about the reasoning aspects of the singleton properties. We propose a simple mechanism to enable existing reasoners to recognize the singleton property triples, as well as to infer the data triples described by the singleton property triples. We evaluate the effect of the singleton property triples in the reasoning processes by comparing the performance on RDF datasets with and without singleton properties. Our evaluation uses as benchmark the LUBM datasets and the LUBM-SP datasets derived from LUBM with temporal information added through singleton properties.
Adapting Resilient Propagation for Deep Learning
Venue: arXiv cs.NE 2015
Year: 2015

The Resilient Propagation (Rprop) algorithm has been very popular for backpropagation training of multilayer feed-forward neural networks in various applications. The standard Rprop however encounters difficulties in the context of deep neural networks as typically happens with gradient-based learning algorithms. In this paper, we propose a modification of the Rprop that combines standard Rprop steps with a special drop out technique. We apply the method for training Deep Neural Networks as standalone components and in ensemble formulations. Results on the MNIST dataset show that the proposed modification alleviates standard Rprop's problems demonstrating improved learning speed and accuracy.
Confluence of Layered Rewrite Systems
Venue: arXiv cs.LO 2015
Year: 2015

We investigate the new, Turing-complete class of layered systems, whose lefthand sides of rules can only be overlapped at a multiset of disjoint or equal positions. Layered systems define a natural notion of rank for terms: the maximal number of non-overlapping redexes along a path from the root to a leaf. Overlappings are allowed in finite or infinite trees. Rules may be non-terminating, non-left-linear, or non-right-linear. Using a novel unification technique, cyclic unification, and the so-alled subrewriting relation, we show that rank non-increasing layered systems are confluent provided their cyclic critical pairs have cyclic-joinable decreasing diagrams.
On the Use of Multiple Satellites to Improve the Spectral Efficiency of Broadcast Transmissions
Venue: arXiv cs.IT 2015
Year: 2015

We consider the use of multiple co-located satellites to improve the spectral efficiency of broadcast transmissions. In particular, we assume that two satellites transmit on overlapping geographical coverage areas, with overlapping frequencies. We first describe the theoretical framework based on network information theory and, in particular, on the theory for multiple access channels. The application to different scenarios will be then considered, including the bandlimited additive white Gaussian noise channel with average power constraint and different models for the nonlinear satellite channel. The comparison with the adoption of frequency division multiplexing and with the Alamouti space-time block coding is also provided. The main conclusion is that a strategy based on overlapped signals is the most convenient in the case of no power unbalance, although it requires the adoption of a multiuser detection strategy at the receiver.
An FPT 2-Approximation for Tree-Cut Decomposition
Venue: arXiv cs.DS 2015
Year: 2015

The tree-cut width of a graph is a graph parameter defined by Wollan [J. Comb. Theory, Ser. B, 110:47-66, 2015] with the help of tree-cut decompositions. In certain cases, tree-cut width appears to be more adequate than treewidth as an invariant that, when bounded, can accelerate the resolution of intractable problems. While designing algorithms for problems with bounded tree-cut width, it is important to have a parametrically tractable way to compute the exact value of this parameter or, at least, some constant approximation of it. In this paper we give a parameterized 2-approximation algorithm for the computation of tree-cut width; for an input $n$-vertex graph $G$ and an integer $w$, our algorithm either confirms that the tree-cut width of $G$ is more than $w$ or returns a tree-cut decomposition of $G$ certifying that its tree-cut width is at most $2w$, in time $2^{O(w^2\log w)} \cdot n^2$. Prior to this work, no constructive parameterized algorithms, even approximated ones, existed for computing the tree-cut width of a graph. As a consequence of the Graph Minors series by Robertson and Seymour, only the existence of a decision algorithm was known.
Cycles in enhanced hypercubes
Venue: arXiv cs.DM 2015
Year: 2015

The enhanced hypercube $Q_{n,k}$ is a variant of the hypercube $Q_n$. We investigate all the lengths of cycles that an edge of the enhanced hypercube lies on. It is proved that every edge of $Q_{n,k}$ lies on a cycle of every even length from $4$ to $2^n$; if $k$ is even, every edge of $Q_{n,k}$ also lies on a cycle of every odd length from $k+3$ to $2^n-1$, and some special edges lie on a shortest odd cycle of length $k+1$.
Guiding Long-Short Term Memory for Image Caption Generation
Venue: arXiv cs.CV 2015
Year: 2015

In this work we focus on the problem of image caption generation. We propose an extension of the long short term memory (LSTM) model, which we coin gLSTM for short. In particular, we add semantic information extracted from the image as extra input to each unit of the LSTM block, with the aim of guiding the model towards solutions that are more tightly coupled to the image content. Additionally, we explore different length normalization strategies for beam search in order to prevent from favoring short sentences. On various benchmark datasets such as Flickr8K, Flickr30K and MS COCO, we obtain results that are on par with or even outperform the current state-of-the-art.
Convexities in Some Special Graph Classes ---New Results in AT-free Graphs and Beyond
Venue: arXiv cs.DM 2015
Year: 2015

We study convexity properties of graphs. In this paper we present a linear-time algorithm for the geodetic number in tree-cographs. Settling a 10-year-old conjecture, we prove that the Steiner number is at least the geodetic number in AT-free graphs. Computing a maximal and proper monophonic set in $\AT$-free graphs is NP-complete. We present polynomial algorithms for the monophonic number in permutation graphs and the geodetic number in $P_4$- sparse graphs.
Hybrid Analog-Digital Channel Estimation and Beamforming: Training-Throughput Tradeoff
Venue: arXiv cs.IT 2015
Year: 2015

This paper designs hybrid analog-digital channel estimation and beamforming techniques for multiuser massive multiple input multiple output (MIMO) systems with limited number of radio frequency (RF) chains. For these systems, first we design novel minimum mean square error (MMSE) hybrid analog-digital channel estimator by considering both perfect and imperfect channel covariance matrix knowledge cases. Then, we utilize the estimated channels to enable beamforming for data transmission. When the channel covariance matrices of all user equipments (UEs) are known perfectly, we show that there is a tradeoff between the training duration and throughput. Specifically, we exploit that the optimal training duration that maximizes the throughput depends on the covariance matrices of all UEs, number of RF chains and channel coherence time ($T_c$). We also show that the training time optimization problem can be formulated as a concave maximization problem {for some system parameter settings} where its global optimal solution is obtained efficiently using existing tools. In particular, when the base station equipped with $64$ antennas and $1$ RF chain is serving one single antenna UE, $T_c=128$ symbol periods ($T_s$) and signal to noise ratio of $10$dB, we have found that the optimal training durations are $4T_s$ and $20T_s$ for highly correlated and uncorrelated Rayleigh fading channel coefficients, respectively. The analytical expressions are validated by performing numerical and extensive Monte Carlo simulations.
Joint Channel and Queue Aware Scheduling for Wireless Links with Multiple Fading States
Venue: arXiv cs.IT 2015
Year: 2015

In this work, we address the delay optimal scheduling problem for wireless transmission with fixed modulation over multi-state fading channels. We propose a stochastic scheduling policy which schedules the source to transmit with probability jointly based on the buffer and channel states, with an average power constraint at the transmitter. Our objective is to minimize the average queueing delay by choosing the optimal transmission probabilities. Using Markov chain modeling, we formulate a power-constrained delay minimization problem, and then transform it into a Linear Programming (LP) one. By analyzing its property, we can derive the optimal threshold-based scheduling policy together with the corresponding transmission probabilities. Our theoretical analysis is corroborated by simulation results.
Efficient Task Collaboration with Execution Uncertainty
Venue: arXiv cs.AI 2015
Year: 2015

We study a general task allocation problem, involving multiple agents that collaboratively accomplish tasks and where agents may fail to successfully complete the tasks assigned to them (known as execution uncertainty). The goal is to choose an allocation that maximises social welfare while taking their execution uncertainty into account. We show that this can be achieved by using the post-execution verification (PEV)-based mechanism if and only if agents' valuations satisfy a multilinearity condition. We then consider a more complex setting where an agent's execution uncertainty is not completely predictable by the agent alone but aggregated from all agents' private opinions (known as trust). We show that PEV-based mechanism with trust is still truthfully implementable if and only if the trust aggregation is multilinear.
HCLAE: High Capacity Locally Aggregating Encodings for Approximate Nearest Neighbor Search
Venue: arXiv cs.CV 2015
Year: 2015

Vector quantization-based approaches are successful to solve Approximate Nearest Neighbor (ANN) problems which are critical to many applications. The idea is to generate effective encodings to allow fast distance approximation. We propose quantization-based methods should partition the data space finely and exhibit locality of the dataset to allow efficient non-exhaustive search. In this paper, we introduce the concept of High Capacity Locality Aggregating Encodings (HCLAE) to this end, and propose Dictionary Annealing (DA) to learn HCLAE by a simulated annealing procedure. The quantization error is lower than other state-of-the-art. The algorithms of DA can be easily extended to an online learning scheme, allowing effective handle of large scale data. Further, we propose Aggregating-Tree (A-Tree), a non-exhaustive search method using HCLAE to perform efficient ANN-Search. A-Tree achieves magnitudes of speed-up on ANN-Search tasks, compared to the state-of-the-art.
Quasi-perfect codes in the $\ell_p$ metric
Venue: arXiv cs.IT 2015
Year: 2015

We consider quasi-perfect codes in $\mathbb{Z}^n$ over the $\ell_p$ metric, $2 \leq p < \infty$. Through a computational approach, we determine all radii for which there are linear quasi-perfect codes for $p = 2$ and $n = 2, 3$. Moreover, we study codes with a certain \textit{degree of imperfection}, a notion that generalizes the quasi-perfect codes. Numerical results concerning the codes with the smallest degree of imperfection are presented.
Triple cyclic codes over $\mathbb{Z}_2$
Venue: arXiv cs.IT 2015
Year: 2015

Let $r,s,t$ be three positive integers and $\mathcal{C}$ be a binary linear code of lenght $r+s+t$. We say that $\mathcal{C}$ is a triple cyclic code of lenght $(r,s,t)$ over $\mathbb{Z}_2$ if the set of coordinates can be partitioned into three parts that any cyclic shift of the coordinates of the parts leaves invariant the code. These codes can be considered as $\mathbb{Z}_2[x]$-submodules of $\frac{\mathbb{Z}_2[x]}{\langle x^r-1\rangle}\times\frac{\mathbb{Z}_2[x]}{\langle x^s-1\rangle}\times\frac{\mathbb{Z}_2[x]}{\langle x^t-1\rangle}$. We give the minimal generating sets of this kind of codes. Also, we determine the relationship between the generators of triple cyclic codes and their duals.
HVACMeter: Apportionment of HVAC Power to Thermal Zones and Air Handler Units
Venue: arXiv cs.SY 2015
Year: 2015

Heating, Ventilation and Air Conditioning (HVAC) systems consume almost half of the total energy use of commercial buildings. To optimize HVAC energy usage, it is important to understand the energy consumption of individual HVAC components at fine granularities. However, buildings typically only have aggregate building level power and thermal meters. We present HVACMeter, a system which leverages existing sensors in commercial HVAC systems to estimate the energy consumed by individual components of the HVAC system, as well by each thermal zone in buildings. HVACMeter can be generalized to any HVAC system as it uses the basic understanding of HVAC operation, heat transfer equations, and historical sensor data to estimate energy. We deploy HVACMeter to three buildings on our campus, to identify the set of sensors that are important for accurately disaggregating energy use at the level of each Air Handler Unit and each thermal zone within these buildings. HVACMeter power estimations have on an average 44.5 % less RMSE than that of mean power estimates. Furthermore, we highlight the usefulness of HVACMeter energy estimation model for a building fault detection application by quantifying the amount of energy that can be saved by fixing particular faults.
Exploring Query Categorisation for Query Expansion: A Study
Venue: arXiv cs.IR 2015
Year: 2015

The vocabulary mismatch problem is one of the important challenges facing traditional keyword-based Information Retrieval Systems. The aim of query expansion (QE) is to reduce this query-document mismatch by adding related or synonymous words or phrases to the query. Several existing query expansion algorithms have proved their merit, but they are not uniformly beneficial for all kinds of queries. Our long-term goal is to formulate methods for applying QE techniques tailored to individual queries, rather than applying the same general QE method to all queries. As an initial step, we have proposed a taxonomy of query classes (from a QE perspective) in this report. We have discussed the properties of each query class with examples. We have also discussed some QE strategies that might be effective for each query category. In future work, we intend to test the proposed techniques using standard datasets, and to explore automatic query categorisation methods.
SignEPC : A Digital Signature Scheme for Efficient and Scalable Access Control in EPCglobal Network
Venue: arXiv cs.CR 2015
Year: 2015

The EPCglobal network is a computer network which allows supply chain companies to search for their unknown partners globally and share information stored in product RFID tags with each other. Although there have been quite a number of recent research works done to improve the security of EPCglobal Network, the existing access control solutions are not efficient and scalable. For instance, when a user queries Electronic Product Code Information Service (EPCIS) for EPC event information, the EPCIS would have to query the Electronic Product Code Discovery Service (EPCDS) to check the access rights of the user. This implementation is not efficient and creates a bottleneck at EPCDS. In this paper, we design and propose a digital signature scheme, SignEPC, as a more efficient and scalable access control solution for EPCglobal network. Our paper will also evaluate SignEPC by considering the various possible attacks that could be done on our proposed model