OpenRaiser/Intern-Atlas huggingface dataset:
Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing
Venue: arXiv cs.DS 2015
Year: 2015

We prove a tight lower bound for the exponent $ρ$ for data-dependent Locality-Sensitive Hashing schemes, recently used to design efficient solutions for the $c$-approximate nearest neighbor search. In particular, our lower bound matches the bound of $ρ\le \frac{1}{2c-1}+o(1)$ for the $\ell_1$ space, obtained via the recent algorithm from [Andoni-Razenshteyn, STOC'15]. In recent years it emerged that data-dependent hashing is strictly superior to the classical Locality-Sensitive Hashing, when the hash function is data-independent. In the latter setting, the best exponent has been already known: for the $\ell_1$ space, the tight bound is $ρ=1/c$, with the upper bound from [Indyk-Motwani, STOC'98] and the matching lower bound from [O'Donnell-Wu-Zhou, ITCS'11]. We prove that, even if the hashing is data-dependent, it must hold that $ρ\ge \frac{1}{2c-1}-o(1)$. To prove the result, we need to formalize the exact notion of data-dependent hashing that also captures the complexity of the hash functions (in addition to their collision properties). Without restricting such complexity, we would allow for obviously infeasible solutions such as the Voronoi diagram of a dataset. To preclude such solutions, we require our hash functions to be succinct. This condition is satisfied by all the known algorithmic results.
Verifying Response Times in Networked Automation Systems Using Jitter Bounds
Venue: arXiv cs.SY 2015
Year: 2015

Networked Automation Systems (NAS) have to meet stringent response time during operation. Verifying response time of automation is an important step during design phase before deployment. Timing discrepancies due to hardware, software and communication components of NAS affect the response time. This investigation uses model templates for verifying the response time in NAS. First, jitter bounds model the timing fluctuations of NAS components. These jitter bounds are the inputs to model templates that are formal models of timing fluctuations. The model templates are atomic action patterns composed of three composition operators- sequential, alternative, and parallel and embedded in time wrapper that specifies clock driven activation conditions. Model templates in conjunction with formal model of technical process offer an easier way to verify the response time. The investigation demonstrates the proposed verification method using an industrial steam boiler with typical NAS components in plant floor.
A New Metric for Quality of Network Community Structure
Venue: arXiv cs.SI 2015
Year: 2015

Modularity is widely used to effectively measure the strength of the community structure found by community detection algorithms. However, modularity maximization suffers from two opposite yet coexisting problems: in some cases, it tends to favor small communities over large ones while in others, large communities over small ones. The latter tendency is known in the literature as the resolution limit problem. To address them, we propose to modify modularity by subtracting from it the fraction of edges connecting nodes of different communities and by including community density into modularity. We refer to the modified metric as Modularity Density and we demonstrate that it indeed resolves both problems mentioned above. We describe the motivation for introducing this metric by using intuitively clear and simple examples. We also prove that this new metric solves the resolution limit problem. Finally, we discuss the results of applying this metric, modularity, and several other popular community quality metrics to two real dynamic networks. The results imply that Modularity Density is consistent with all the community quality measurements but not modularity, which suggests that Modularity Density is an improved measurement of the community quality compared to modularity.
A Deep Hashing Learning Network
Venue: arXiv cs.CV 2015
Year: 2015

Hashing-based methods seek compact and efficient binary codes that preserve the neighborhood structure in the original data space. For most existing hashing methods, an image is first encoded as a vector of hand-crafted visual feature, followed by a hash projection and quantization step to get the compact binary vector. Most of the hand-crafted features just encode the low-level information of the input, the feature may not preserve the semantic similarities of images pairs. Meanwhile, the hashing function learning process is independent with the feature representation, so the feature may not be optimal for the hashing projection. In this paper, we propose a supervised hashing method based on a well designed deep convolutional neural network, which tries to learn hashing code and compact representations of data simultaneously. The proposed model learn the binary codes by adding a compact sigmoid layer before the loss layer. Experiments on several image data sets show that the proposed model outperforms other state-of-the-art methods.
Approximation Algorithms for Generalized MST and TSP in Grid Clusters
Venue: arXiv cs.DM 2015
Year: 2015

We consider a special case of the generalized minimum spanning tree problem (GMST) and the generalized travelling salesman problem (GTSP) where we are given a set of points inside the integer grid (in Euclidean plane) where each grid cell is $1 \times 1$. In the MST version of the problem, the goal is to find a minimum tree that contains exactly one point from each non-empty grid cell (cluster). Similarly, in the TSP version of the problem, the goal is to find a minimum weight cycle containing one point from each non-empty grid cell. We give a $(1+4\sqrt{2}+ε)$ and $(1.5+8\sqrt{2}+ε)$-approximation algorithm for these two problems in the described setting, respectively. Our motivation is based on the problem posed in [7] for a constant approximation algorithm. The authors designed a PTAS for the more special case of the GMST where non-empty cells are connected end dense enough. However, their algorithm heavily relies on this connectivity restriction and is unpractical. Our results develop the topic further.
Low-complexity near-optimal signal detection for uplink large-scale MIMO systems
Venue: arXiv cs.IT 2015
Year: 2015

Minimum mean square error (MMSE) signal detection algorithm is near- optimal for uplink multi-user large-scale multiple input multiple output (MIMO) systems, but involves matrix inversion with high complexity. In this letter, we firstly prove that the MMSE filtering matrix for large- scale MIMO is symmetric positive definite, based on which we propose a low-complexity near-optimal signal detection algorithm by exploiting the Richardson method to avoid the matrix inversion. The complexity can be reduced from O(K3) to O(K2), where K is the number of users. We also provide the convergence proof of the proposed algorithm. Simulation results show that the proposed signal detection algorithm converges fast, and achieves the near-optimal performance of the classical MMSE algorithm.
Towards Predicting First Daily Departure Times: a Gaussian Modeling Approach for Load Shift Forecasting
Venue: arXiv cs.LG 2015
Year: 2015

This work provides two statistical Gaussian forecasting methods for predicting First Daily Departure Times (FDDTs) of everyday use electric vehicles. This is important in smart grid applications to understand disconnection times of such mobile storage units, for instance to forecast storage of non dispatchable loads (e.g. wind and solar power). We provide a review of the relevant state-of-the-art driving behavior features towards FDDT prediction, to then propose an approximated Gaussian method which qualitatively forecasts how many vehicles will depart within a given time frame, by assuming that departure times follow a normal distribution. This method considers sampling sessions as Poisson distributions which are superimposed to obtain a single approximated Gaussian model. Given the Gaussian distribution assumption of the departure times, we also model the problem with Gaussian Mixture Models (GMM), in which the priorly set number of clusters represents the desired time granularity. Evaluation has proven that for the dataset tested, low error and high confidence ($\approx 95\%$) is possible for 15 and 10 minute intervals, and that GMM outperforms traditional modeling but is less generalizable across datasets, as it is a closer fit to the sampling data. Conclusively we discuss future possibilities and practical applications of the discussed model.
Accessible Banking: Experiences and Future Directions
Venue: arXiv cs.CY 2015
Year: 2015

This is a short position paper drawing on experience working with the UK banking industry and their disabled and ageing customers in the Business Disability Forum, a UK non-profit member organisation funded by a large body of UK private and public sector businesses. We describe some commonly reported problems of disabled customers who use modern banking technologies, relating them to UK law and best practice. We describe some of the recent banking industry innovations and the hope they may offer for improved inclusive and accessible multi-channel banking.
Extension of Modularity Density for Overlapping Community Structure
Venue: arXiv cs.SI 2015
Year: 2015

Modularity is widely used to effectively measure the strength of the disjoint community structure found by community detection algorithms. Although several overlapping extensions of modularity were proposed to measure the quality of overlapping community structure, there is lack of systematic comparison of different extensions. To fill this gap, we overview overlapping extensions of modularity to select the best. In addition, we extend the Modularity Density metric to enable its usage for overlapping communities. The experimental results on four real networks using overlapping extensions of modularity, overlapping modularity density, and six other community quality metrics show that the best results are obtained when the product of the belonging coefficients of two nodes is used as the belonging function. Moreover, our experiments indicate that overlapping modularity density is a better measure of the quality of overlapping community structure than other metrics considered.
LDQL: A Query Language for the Web of Linked Data (Extended Version)
Venue: arXiv cs.DB 2015
Year: 2015

The Web of Linked Data is composed of tons of RDF documents interlinked to each other forming a huge repository of distributed semantic data. Effectively querying this distributed data source is an important open problem in the Semantic Web area. In this paper, we propose LDQL, a declarative language to query Linked Data on the Web. One of the novelties of LDQL is that it expresses separately (i) patterns that describe the expected query result, and (ii) Web navigation paths that select the data sources to be used for computing the result. We present a formal syntax and semantics, prove equivalence rules, and study the expressiveness of the language. In particular, we show that LDQL is strictly more expressive than the query formalisms that have been proposed previously for Linked Data on the Web. The high expressiveness allows LDQL to define queries for which a complete execution is not computationally feasible over the Web. We formally study this issue and provide a syntactic sufficient condition to avoid this problem; queries satisfying this condition are ensured to have a procedure to be effectively evaluated over the Web of Linked Data.
Window Flow Control Systems with Random Service
Venue: arXiv cs.PF 2015
Year: 2015

We present an extension of the window flow control analysis by R. Agrawal et.al. (Reference [1]), C.-S. Chang (Reference [6]), and C.-S. Chang et. al. (Reference [8]) to a system with random service time and fixed feedback delay. We consider two network service models. In the first model, the network service process itself has no time correlations. The second model addresses a two-state Markov-modulated service.
Simple and Fast Rounding Algorithms for Directed and Node-weighted Multiway Cut
Venue: arXiv cs.DS 2015
Year: 2015

In Directed Multiway Cut(Dir-MC) the input is an edge-weighted directed graph $G=(V,E)$ and a set of $k$ terminal nodes $\{s_1,s_2,\ldots,s_k\} \subseteq V$; the goal is to find a min-weight subset of edges whose removal ensures that there is no path from $s_i$ to $s_j$ for any $i \neq j$. In Node-weighted Multiway Cut(Node-MC) the input is a node-weighted undirected graph $G$ and a set of $k$ terminal nodes $\{s_1,s_2,\ldots,s_k\} \subseteq V$; the goal is to remove a min-weight subset of nodes to disconnect each pair of terminals. Dir-MC admits a $2$-approximation [Naor, Zosin '97] and Node-MC admits a $2(1-\frac{1}{k})$-approximation [Garg, Vazirani, Yannakakis '94], both via rounding of LP relaxations. Previous rounding algorithms for these problems, from nearly twenty years ago, are based on careful rounding of an "optimum" solution to an LP relaxation. This is particularly true for Dir-MC for which the rounding relies on a custom LP formulation instead of the natural distance based LP relaxation [Naor, Zosin '97]. In this paper we describe extremely simple and near linear-time rounding algorithms for Dir-MC and Node-MC via a natural distance based LP relaxation. The dual of this relaxation is a special case of the maximum multicommodity flow problem. Our algorithms achieve the same bounds as before but have the significant advantage in that they can work with "any feasible" solution to the relaxation. Consequently, in addition to obtaining "book" proofs of LP rounding for these two basic problems, we also obtain significantly faster approximation algorithms by taking advantage of known algorithms for computing near-optimal solutions for maximum multicommodity flow problems. We also investigate lower bounds for Dir-MC when $k=2$ and in particular prove that the integrality gap of the LP relaxation is $2$ even in directed planar graphs.
Analysis of women leadership in enterprise social networks
Venue: arXiv cs.SI 2015
Year: 2015

This paper describes a Social Network Analysis toolkit to monitor an Enterprise Social Network and help analyzing informal leadership as a function of social ties and topic discussions. The toolkit has been developed in the context of a regional project, Fiordaliso, funded by Regione Lazio (a region of central Italy) and leaded by Reply, an international network of specialized companies in the field of digital services.
Lower Bounds for Multi-armed Bandit with Non-equivalent Multiple Plays
Venue: arXiv cs.LG 2015
Year: 2015

We study the stochastic multi-armed bandit problem with non-equivalent multiple plays where, at each step, an agent chooses not only a set of arms, but also their order, which influences reward distribution. In several problem formulations with different assumptions, we provide lower bounds for regret with standard asymptotics $O(\log{t})$ but novel coefficients and provide optimal algorithms, thus proving that these bounds cannot be improved.
Massively Deep Artificial Neural Networks for Handwritten Digit Recognition
Venue: arXiv cs.CV 2015
Year: 2015

Greedy Restrictive Boltzmann Machines yield an fairly low 0.72% error rate on the famous MNIST database of handwritten digits. All that was required to achieve this result was a high number of hidden layers consisting of many neurons, and a graphics card to greatly speed up the rate of learning.
Forward Invariant Cuts to Simplify Proofs of Safety
Venue: arXiv cs.LO 2015
Year: 2015

The use of deductive techniques, such as theorem provers, has several advantages in safety verification of hybrid sys- tems; however, state-of-the-art theorem provers require ex- tensive manual intervention. Furthermore, there is often a gap between the type of assistance that a theorem prover requires to make progress on a proof task and the assis- tance that a system designer is able to provide. This paper presents an extension to KeYmaera, a deductive verification tool for differential dynamic logic; the new technique allows local reasoning using system designer intuition about per- formance within particular modes as part of a proof task. Our approach allows the theorem prover to leverage for- ward invariants, discovered using numerical techniques, as part of a proof of safety. We introduce a new inference rule into the proof calculus of KeYmaera, the forward invariant cut rule, and we present a methodology to discover useful forward invariants, which are then used with the new cut rule to complete verification tasks. We demonstrate how our new approach can be used to complete verification tasks that lie out of the reach of existing deductive approaches us- ing several examples, including one involving an automotive powertrain control system.
Persistent Topology of Syntax
Venue: arXiv cs.CL 2015
Year: 2015

We study the persistent homology of the data set of syntactic parameters of the world languages. We show that, while homology generators behave erratically over the whole data set, non-trivial persistent homology appears when one restricts to specific language families. Different families exhibit different persistent homology. We focus on the cases of the Indo-European and the Niger-Congo families, for which we compare persistent homology over different cluster filtering values. We investigate the possible significance, in historical linguistic terms, of the presence of persistent generators of the first homology. In particular, we show that the persistent first homology generator we find in the Indo-European family is not due (as one might guess) to the Anglo-Norman bridge in the Indo-European phylogenetic network, but is related to the position of Ancient Greek and the Hellenic branch within the network.
Fifty Years of MIMO Detection: The Road to Large-Scale MIMOs
Venue: arXiv cs.IT 2015
Year: 2015

The emerging massive/large-scale MIMO (LS-MIMO) systems relying on very large antenna arrays have become a hot topic of wireless communications. Compared to the LTE based 4G mobile communication system that allows for up to 8 antenna elements at the base station (BS), the LS-MIMO system entails an unprecedented number of antennas, say 100 or more, at the BS. The huge leap in the number of BS antennas opens the door to a new research field in communication theory, propagation and electronics, where random matrix theory begins to play a dominant role. In this paper, we provide a recital on the historic heritages and novel challenges facing LS-MIMOs from a detection perspective. Firstly, we highlight the fundamentals of MIMO detection, including the nature of co-channel interference, the generality of the MIMO detection problem, the received signal models of both linear memoryless MIMO channels and dispersive MIMO channels exhibiting memory, as well as the complex-valued versus real-valued MIMO system models. Then, an extensive review of the representative MIMO detection methods conceived during the past 50 years (1965-2015) is presented, and relevant insights as well as lessons are inferred for designing complexity-scalable MIMO detection algorithms that are potentially applicable to LS-MIMO systems. Furthermore, we divide the LS-MIMO systems into two types, and elaborate on the distinct detection strategies suitable for each of them. The type-I LS-MIMO corresponds to the case where the number of active users is much smaller than the number of BS antennas, which is currently the mainstream definition of LS-MIMO. The type-II LS-MIMO corresponds to the case where the number of active users is comparable to the number of BS antennas. Finally, we discuss the applicability of existing MIMO detection algorithms in LS-MIMO systems, and review some of the recent advances in LS-MIMO detection.
Cover Song Identification with Timbral Shape Sequences
Venue: arXiv cs.SD 2015
Year: 2015

We introduce a novel low level feature for identifying cover songs which quantifies the relative changes in the smoothed frequency spectrum of a song. Our key insight is that a sliding window representation of a chunk of audio can be viewed as a time-ordered point cloud in high dimensions. For corresponding chunks of audio between different versions of the same song, these point clouds are approximately rotated, translated, and scaled copies of each other. If we treat MFCC embeddings as point clouds and cast the problem as a relative shape sequence, we are able to correctly identify 42/80 cover songs in the "Covers 80" dataset. By contrast, all other work to date on cover songs exclusively relies on matching note sequences from Chroma derived features.
Centralized Adaptation for Parameter Estimation over Wireless Sensor Networks
Venue: arXiv cs.SY 2015
Year: 2015

We study the performance of centralized least mean-squares (CLMS) algorithms in wireless sensor networks where nodes transmit their data over fading channels to a central processing unit (e.g., fusion center or cluster head), for parameter estimation. Wireless channel impairments, including fading and path loss, distort the transmitted data, cause link failure and degrade the performance of the adaptive solutions. To address this problem, we propose a novel CLMS algorithm that uses a refined version of the transmitted data and benefits from a link failure alarm strategy to discard severely distorted data. Furthermore, to remove the bias due to communication noise from the estimate, we introduce a bias-elimination scheme that also leads to a lower steady-state mean-square error. Our theoretical findings are supported by numerical simulation results.
Joint Data Scheduling and FEC Coding for Multihomed Wireless Video Delivery
Venue: arXiv cs.MM 2015
Year: 2015

This paper studies the problem of mobile video delivery in heterogenous wireless networks from a server to multihomed device. Most existing works only consider delivering video streaming on single path which bandwidth is limited causing ultimate video transmission rate. To solve this live video streaming transmission bottleneck problem, we propose a novel solution named Joint Data Allocation and Fountain Coding (JDAFC) method that contain below characters: (1) path selection, (2) dynamic data allocation, and (3) fountain coding. We evaluate the performance of JDAFC by simulation experiments using Exata and JVSM and compare it with some reference solutions. Experimental results represent that JDAFC outperforms the competing solutions in improving the video peak signal-to-noise ratio as well as reducing the end-to-end delay.