OpenRaiser/Intern-Atlas huggingface dataset:
Coded Cooperative Data Exchange for a Secret Key
Venue: arXiv cs.IT 2014
Year: 2014

We consider a coded cooperative data exchange problem with the goal of generating a secret key. Specifically, we investigate the number of public transmissions required for a set of clients to agree on a secret key with probability one, subject to the constraint that it remains private from an eavesdropper. Although the problems are closely related, we prove that secret key generation with fewest number of linear transmissions is NP-hard, while it is known that the analogous problem in traditional cooperative data exchange can be solved in polynomial time. In doing this, we completely characterize the best possible performance of linear coding schemes, and also prove that linear codes can be strictly suboptimal. Finally, we extend the single-key results to characterize the minimum number of public transmissions required to generate a desired integer number of statistically independent secret keys.
Toward Energy-Efficient 5G Wireless Communications Technologies
Venue: arXiv cs.NI 2014
Year: 2014

The densification and expansion of wireless networks pose new challenges on energy efficiency. With a drastic increase of infrastructure nodes (e.g. ultra-dense deployment of small cells), the total energy consumption may easily exceed an acceptable level. While most studies focus on the energy radiated by the antennas, the bigger part of the total energy budget is actually consumed by the hardware (e.g., coolers and circuit energy consumption). The ability to shutdown infrastructure nodes (or parts of it) or to adapt the transmission strategy according to the traffic will therefore become an important design aspect of future wireless architectures. Network infrastructure should be regarded as a resource that can be occupied or released on demand. However, the modeling and optimization of such systems are complicated by the potential interference coupling between active nodes. In this article, we give an overview on different aspects of this problem. We show how prior knowledge of traffic patterns can be exploited for optimization. Then, we discuss the framework of interference functions, which has proved a useful tool for various types of coupled systems in the literature. Finally, we introduce different classes of algorithms that have the objective of improving the energy efficiency by adapting the network configuration to the traffic load.
Energy and Performance-Can a Wimpy-Node Cluster Challenge a Brawny Server?
Venue: arXiv cs.DB 2014
Year: 2014

Traditional DBMS servers are usually over-provisioned for most of their daily workloads and, because they do not show good energy proportionality, waste a lot of energy while underutilized. A cluster of small (wimpy) servers, where the number of nodes can dynamically adjust to the current workload, might offer better energy characteristics for these workloads. Yet, clusters suffer from "friction losses" and may not be able to quickly adapt to the workload, whereas a single, brawny server delivers performance instantaneously. In this paper, we compare a small cluster of lightweight nodes to a single server in terms of performance and energy efficiency. We run several benchmarks, consisting of OLTP and OLAP queries at variable utilization to test the system's ability to adjust to the workloads. To quantify possible energy saving and its conceivable drawback on query runtime, we evaluate our implementation on a cluster as well as on a single, brawny server and compare the results w.r.t. performance and energy consumption. Our findings confirm that - based on the workload - energy can be saved without sacrificing too much performance.
Measuring Team Creativity Through Longitudinal Social Signals
Venue: arXiv cs.SI 2014
Year: 2014

Research into human dynamical systems has long sought to identify robust signals for human behavior. We have discovered a series of social network-based indicators that are reliable predictors of team creativity and collaborative innovation. We extract these signals from electronic records of interpersonal interactions, including e-mail, and face-to-face interaction measured via sociometric badges. The first of these signals is Rotating Leadership, measuring the degree to which, over time, actors in a team vary in how central they are to team's communication network's structure. The second is Rotating Contribution, which measures the degree to which, over time, actors in a team vary in the ratio of communications they distribute versus receive. The third is Prompt Response Time, which measures, over time, the responsiveness of actors to one another's communications. Finally, we demonstrate the predictive utility of these signals in a variety of contexts, showing them to be robust to various methods of evaluating innovation.
Exact and approximate algorithms for movement problems on (special classes of) graphs
Venue: arXiv cs.DS 2014
Year: 2014

When a large collection of objects (e.g., robots, sensors, etc.) has to be deployed in a given environment, it is often required to plan a coordinated motion of the objects from their initial position to a final configuration enjoying some global property. In such a scenario, the problem of minimizing some function of the distance travelled, and therefore energy consumption, is of vital importance. In this paper we study several motion planning problems that arise when the objects must be moved on a graph, in order to reach certain goals which are of interest for several network applications. Among the others, these goals include broadcasting messages and forming connected or interference-free networks. We study these problems with the aim of minimizing a number of natural measures such as the average/overall distance travelled, the maximum distance travelled, or the number of objects that need to be moved. To this respect, we provide several approximability and inapproximability results, most of which are tight.
Enumeration of Spanning Trees Using Edge Exchange with Minimal Partitioning
Venue: arXiv cs.DS 2014
Year: 2014

In this thesis, Minimal Partitioning (MP) algorithm, an innovative algorithm for enumerating all the spanning trees in an undirected graph is presented. While MP algorithm uses a computational tree graph to traverse all possible spanning trees by the edge exchange technique, it has two unique properties compared to previous algorithms. In the first place, the algorithm maintains a state of minimal partition size in the spanning tree due to edge deletion. This is realized by swapping peripheral edges, more precisely leaf edges, in most of edge exchange operations. Consequently, the main structure of the spanning trees is preserved during the steps of the enumeration process. This extra constraint proves to be advantageous in many applications where the partition size is a factor in the solution cost. Secondly, we introduce, and utilize, the new concept of edge promotion: the exchanged edges always share one end. Practically, and as a result of this property, the interface between the two partitions of the spanning tree during edge exchange has to be maintained from one side only. For a graph $G(V,E)$, MP algorithm requires $O(log V+E/V)$ expected time and $OV log V)$ worst case time for generating each spanning tree. MP algorithm requires a total expected space limit of $O(E log V)$ with worst case limit of $O(EV)$. Like all edge exchange algorithms, MP algorithm retains the advantage of compacted output of $O(1)$ per spanning tree by listing the relative differences only. Three sample real-world applications of spanning trees enumeration are explored and the effects of using MP algorithm are studied. Namely: construction of nets of polyhedra, multi-robots spanning tree routing, and computing the electric current in edges of a network. We report that MP algorithm outperforms other algorithm by $O(V)$ time complexity.
Geometrical Localization Algorithm for 3-D Wireless Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

In this paper, we propose an efficient range free localization scheme for large scale three dimensional wireless sensor networks. Our system environment consists of two type of sensors, randomly deployed static sensors and global positioning system equipped moving sensors. These moving anchors travels across the network field and broadcast their current locations on specified intervals. As soon as the sensors which are deployed in random fashion receives three beacon messages (known locations broadcasted by anchors), they computes their locations automatically by using our proposed algorithm. One of our significant contributions is, we use only three different beacon messages to localize one sensor, while in the best of our knowledge, all previously proposed methods use at least four different known locations. The ability of our method to localize by using only three known locations not only saves computation, time, energy, but also reduces the number of anchors needed to be deployed and more importantly reduces the communication overheads. Experimental results demonstrate that our proposed scheme improves the overall efficiency of localization process significantly. Important Note: Final version of this paper is accepted and published by Journal of Wireless Personal Communication, Springer : June, 2014 The final version of publication is available at link.springer.com Link: http://link.springer.com/article/10.1007\%2Fs11277-014-1852-6
Acoustic Fingerprinting Revisited: Generate Stable Device ID Stealthy with Inaudible Sound
Venue: arXiv cs.CR 2014
Year: 2014

The popularity of mobile device has made people's lives more convenient, but threatened people's privacy at the same time. As end users are becoming more and more concerned on the protection of their private information, it is even harder to track a specific user using conventional technologies. For example, cookies might be cleared by users regularly. Apple has stopped apps accessing UDIDs, and Android phones use some special permission to protect IMEI code. To address this challenge, some recent studies have worked on tracing smart phones using the hardware features resulted from the imperfect manufacturing process. These works have demonstrated that different devices can be differentiated to each other. However, it still has a long way to go in order to replace cookie and be deployed in real world scenarios, especially in terms of properties like uniqueness, robustness, etc. In this paper, we presented a novel method to generate stable and unique device ID stealthy for smartphones by exploiting the frequency response of the speaker. With carefully selected audio frequencies and special sound wave patterns, we can reduce the impacts of non-linear effects and noises, and keep our feature extraction process un-noticeable to users. The extracted feature is not only very stable for a given smart phone speaker, but also unique to that phone. The feature contains rich information that is equivalent to around 40 bits of entropy, which is enough to identify billions of different smart phones of the same model. We have built a prototype to evaluate our method, and the results show that the generated device ID can be used as a replacement of cookie.
COFFEE: an Optimizing Compiler for Finite Element Local Assembly
Venue: arXiv cs.MS 2014
Year: 2014

The numerical solution of partial differential equations using the finite element method is one of the key applications of high performance computing. Local assembly is its characteristic operation. This entails the execution of a problem-specific kernel to numerically evaluate an integral for each element in the discretized problem domain. Since the domain size can be huge, executing efficient kernels is fundamental. Their op- timization is, however, a challenging issue. Even though affine loop nests are generally present, the short trip counts and the complexity of mathematical expressions make it hard to determine a single or unique sequence of successful transformations. Therefore, we present the design and systematic evaluation of COF- FEE, a domain-specific compiler for local assembly kernels. COFFEE manipulates abstract syntax trees generated from a high-level domain-specific language for PDEs by introducing domain-aware composable optimizations aimed at improving instruction-level parallelism, especially SIMD vectorization, and register locality. It then generates C code including vector intrinsics. Experiments using a range of finite-element forms of increasing complexity show that significant performance improvement is achieved.
An Enhanced Multiway Sorting Network Based on n-Sorters
Venue: arXiv cs.DS 2014
Year: 2014

Merging-based sorting networks are an important family of sorting networks. Most merge sorting networks are based on 2-way or multi-way merging algorithms using 2-sorters as basic building blocks. An alternative is to use n-sorters, instead of 2-sorters, as the basic building blocks so as to greatly reduce the number of sorters as well as the latency. Based on a modified Leighton's columnsort algorithm, an n-way merging algorithm, referred to as SS-Mk, that uses n-sorters as basic building blocks was proposed. In this work, we first propose a new multiway merging algorithm with n-sorters as basic building blocks that merges n sorted lists of m values each in 1 + ceil(m/2) stages (n <= m). Based on our merging algorithm, we also propose a sorting algorithm, which requires O(N log2 N) basic sorters to sort N inputs. While the asymptotic complexity (in terms of the required number of sorters) of our sorting algorithm is the same as the SS-Mk, for wide ranges of N, our algorithm requires fewer sorters than the SS-Mk. Finally, we consider a binary sorting network, where the basic sorter is implemented in threshold logic and scales linearly with the number of inputs, and compare the complexity in terms of the required number of gates. For wide ranges of N, our algorithm requires fewer gates than the SS-Mk.
Online Submodular Maximization under a Matroid Constraint with Application to Learning Assignments
Venue: arXiv cs.LG 2014
Year: 2014

Which ads should we display in sponsored search in order to maximize our revenue? How should we dynamically rank information sources to maximize the value of the ranking? These applications exhibit strong diminishing returns: Redundancy decreases the marginal utility of each ad or information source. We show that these and other problems can be formalized as repeatedly selecting an assignment of items to positions to maximize a sequence of monotone submodular functions that arrive one by one. We present an efficient algorithm for this general problem and analyze it in the no-regret model. Our algorithm possesses strong theoretical guarantees, such as a performance ratio that converges to the optimal constant of 1 - 1/e. We empirically evaluate our algorithm on two real-world online optimization problems on the web: ad allocation with submodular utilities, and dynamically ranking blogs to detect information cascades. Finally, we present a second algorithm that handles the more general case in which the feasible sets are given by a matroid constraint, while still maintaining a 1 - 1/e asymptotic performance ratio.
Calibration of Multiple Fish-Eye Cameras Using a Wand
Venue: arXiv cs.CV 2014
Year: 2014

Fish-eye cameras are becoming increasingly popular in computer vision, but their use for 3D measurement is limited partly due to the lack of an accurate, efficient and user-friendly calibration procedure. For such a purpose, we propose a method to calibrate the intrinsic and extrinsic parameters (including radial distortion parameters) of two/multiple fish-eye cameras simultaneously by using a wand under general motions. Thanks to the generic camera model used, the proposed calibration method is also suitable for two/multiple conventional cameras and mixed cameras (e.g. two conventional cameras and a fish-eye camera). Simulation and real experiments demonstrate the effectiveness of the proposed method. Moreover, we develop the camera calibration toolbox, which is available online.
Non-regular graphs with minimal total irregularity
Venue: arXiv cs.DM 2014
Year: 2014

The {\it total irregularity} of a simple undirected graph $G$ is defined as ${\rm irr}_t(G) =$ $\frac{1}{2}\sum_{u,v \in V(G)}$ $\left| d_G(u)-d_G(v) \right|$, where $d_G(u)$ denotes the degree of a vertex $u \in V(G)$. Obviously, ${\rm irr}_t(G)=0$ if and only if $G$ is regular. Here, we characterize the non-regular graphs with minimal total irregularity and thereby resolve the recent conjecture by Zhu, You and Yang~\cite{zyy-mtig-2014} about the lower bound on the minimal total irregularity of non-regular connected graphs. We show that the conjectured lower bound of $2n-4$ is attained only if non-regular connected graphs of even order are considered, while the sharp lower bound of $n-1$ is attained by graphs of odd order. We also characterize the non-regular graphs with the second and the third smallest total irregularity.
Reinforcement Learning Based Algorithm for the Maximization of EV Charging Station Revenue
Venue: arXiv cs.CE 2014
Year: 2014

This paper presents an online reinforcement learning based application which increases the revenue of one particular electric vehicles (EV) station, connected to a renewable source of energy. Moreover, the proposed application adapts to changes in the trends of the station's average number of customers and their types. Most of the parameters in the model are simulated stochastically and the algorithm used is a Q-learning algorithm. A computer simulation was implemented which demonstrates and confirms the utility of the model.
MobiCacher: Mobility-Aware Content Caching in Small-Cell Networks
Venue: arXiv cs.NI 2014
Year: 2014

Small-cell networks have been proposed to meet the demand of ever growing mobile data traffic. One of the prominent challenges faced by small-cell networks is the lack of sufficient backhaul capacity to connect small-cell base stations (small-BSs) to the core network. We exploit the effective application layer semantics of both spatial and temporal locality to reduce the backhaul traffic. Specifically, small-BSs are equipped with storage facility to cache contents requested by users. As the {\em cache hit ratio} increases, most of the users' requests can be satisfied locally without incurring traffic over the backhaul. To make informed caching decisions, the mobility patterns of users must be carefully considered as users might frequently migrate from one small cell to another. We study the issue of mobility-aware content caching, which is formulated into an optimization problem with the objective to maximize the caching utility. As the problem is NP-complete, we develop a polynomial-time heuristic solution termed {\em MobiCacher} with bounded approximation ratio. We also conduct trace-based simulations to evaluate the performance of {\em MobiCacher}, which show that {\em MobiCacher} yields better caching utility than existing solutions.
Homophilic Clustering by Locally Asymmetric Geometry
Venue: arXiv cs.CV 2014
Year: 2014

Clustering is indispensable for data analysis in many scientific disciplines. Detecting clusters from heavy noise remains challenging, particularly for high-dimensional sparse data. Based on graph-theoretic framework, the present paper proposes a novel algorithm to address this issue. The locally asymmetric geometries of neighborhoods between data points result in a directed similarity graph to model the structural connectivity of data points. Performing similarity propagation on this directed graph simply by its adjacency matrix powers leads to an interesting discovery, in the sense that if the in-degrees are ordered by the corresponding sorted out-degrees, they will be self-organized to be homophilic layers according to the different distributions of cluster densities, which is dubbed the Homophilic In-degree figure (the HI figure). With the HI figure, we can easily single out all cores of clusters, identify the boundary between cluster and noise, and visualize the intrinsic structures of clusters. Based on the in-degree homophily, we also develop a simple efficient algorithm of linear space complexity to cluster noisy data. Extensive experiments on toy and real-world scientific data validate the effectiveness of our algorithms.
CB-REFIM: A Practical Coordinated Beamforming in Multicell Networks
Venue: arXiv cs.IT 2014
Year: 2014

Performance of multicell systems is inevitably limited by interference and available resources. Although intercell interference can be mitigated by Base Station (BS) Coordination, the demand on inter-BS information exchange and computational complexity grows rapidly with the number of cells, subcarriers, and users. On the other hand, some of the existing coordination beamforming methods need computation of pseudo-inverse or generalized eigenvector of a matrix, which are practically difficult to implement in a real system. To handle these issues, we propose a novel linear beamforming across a set of coordinated cells only with limiting backhaul signalling. Resource allocation (i.e. precoding and power control) is formulated as an optimization problem with objective function of signal-to-interference-plus-noise ratios (SINRs) in order to maximize the instantaneous weighted sum-rate subject to power constraints. Although the primal problem is nonconvex and difficult to be optimally solved, an iterative algorithm is presented based on the Karush-Kuhn-Tucker (KKT) condition. To have a practical solution with low computational complexity and signalling overhead, we present CB-REFIM (coordination beamforming-reference based interference management) and show the recently proposed REFIM algorithm can be interpreted as a special case of CB-REFIM. We evaluate CB-REFIM through extensive simulation and observe that the proposed strategies achieve close-to-optimal performance.
Exploiting the Unexploited of Coded Caching for Wireless Content Distribution: Detailed Theoretical Proofs
Venue: arXiv cs.NI 2014
Year: 2014

Recent studies show that the coded caching technique can facilitate the wireless content distribution by mitigating the wireless traffic rate during the peak-traffic time, where the contents are partially prefetched to the local cache of mobile devices during the off-peak time. The remaining contents are then jointly coded and delivered in multicast, when many content requests are initiated in the peak-traffic time. The requested contents can be recovered from the local-prefetched and multicast data with requesters experiencing less congestions. However, the benefit of the coded caching scheme is still under estimated, where the potential gain by appropriate caching distribution is under exploited. In this paper, we propose a theoretical model to minimize the average wireless traffic rate required in the coded caching, for which the optimized caching distribution is derived with the content popularity distribution taken into account. In order to improve the computational efficiency for determining the appropriate caching distribution, we transform the objective function from the average wireless traffic rate into the average size of un-prefetched contents. We theoretically show the order optimality of the derived results from both the primal model and the relaxed one. Simulation results show that the coded caching performance can be further improved with the derived caching distribution.