OpenRaiser/Intern-Atlas huggingface dataset:
Spatial Spectrum Access Game
Venue: arXiv cs.NI 2014
Year: 2014

A key feature of wireless communications is the spatial reuse. However, the spatial aspect is not yet well understood for the purpose of designing efficient spectrum sharing mechanisms. In this paper, we propose a framework of spatial spectrum access games on directed interference graphs, which can model quite general interference relationship with spatial reuse in wireless networks. We show that a pure Nash equilibrium exists for the two classes of games: (1) any spatial spectrum access games on directed acyclic graphs, and (2) any games satisfying the congestion property on directed trees and directed forests. Under mild technical conditions, the spatial spectrum access games with random backoff and Aloha channel contention mechanisms on undirected graphs also have a pure Nash equilibrium. We also quantify the price of anarchy of the spatial spectrum access game. We then propose a distributed learning algorithm, which only utilizes users' local observations to adaptively adjust the spectrum access strategies. We show that the distributed learning algorithm can converge to an approximate mixed-strategy Nash equilibrium for any spatial spectrum access games. Numerical results demonstrate that the distributed learning algorithm achieves up to superior performance improvement over a random access algorithm.
Speeding up Convolutional Neural Networks with Low Rank Expansions
Venue: arXiv cs.CV 2014
Year: 2014

The focus of this paper is speeding up the evaluation of convolutional neural networks. While delivering impressive results across a range of computer vision and machine learning tasks, these networks are computationally demanding, limiting their deployability. Convolutional layers generally consume the bulk of the processing time, and so in this work we present two simple schemes for drastically speeding up these layers. This is achieved by exploiting cross-channel or filter redundancy to construct a low rank basis of filters that are rank-1 in the spatial domain. Our methods are architecture agnostic, and can be easily applied to existing CPU and GPU convolutional frameworks for tuneable speedup performance. We demonstrate this with a real world network designed for scene text character recognition, showing a possible 2.5x speedup with no loss in accuracy, and 4.5x speedup with less than 1% drop in accuracy, still achieving state-of-the-art on standard benchmarks.
Méthodes pour la représentation informatisée de données lexicales / Methoden der Speicherung lexikalischer Daten
Venue: arXiv cs.CL 2014
Year: 2014

In recent years, new developments in the area of lexicography have altered not only the management, processing and publishing of lexicographical data, but also created new types of products such as electronic dictionaries and thesauri. These expand the range of possible uses of lexical data and support users with more flexibility, for instance in assisting human translation. In this article, we give a short and easy-to-understand introduction to the problematic nature of the storage, display and interpretation of lexical data. We then describe the main methods and specifications used to build and represent lexical data. This paper is targeted for the following groups of people: linguists, lexicographers, IT specialists, computer linguists and all others who wish to learn more about the modelling, representation and visualization of lexical knowledge. This paper is written in two languages: French and German.
Enhancing Visual Fashion Recommendations with Users in the Loop
Venue: arXiv cs.HC 2014
Year: 2014

We describe a completely automated large scale visual recommendation system for fashion. Existing approaches have primarily relied on purely computational models to solving this problem that ignore the role of users in the system. In this paper, we propose to overcome this limitation by incorporating a user-centric design of visual fashion recommendations. Specifically, we propose a technique that augments 'user preferences' in models by exploiting elasticity in fashion choices. We further design a user study on these choices and gather results from the 'wisdom of crowd' for deeper analysis. Our key insights learnt through these results suggest that fashion preferences when constrained to a particular class, contain important behavioral signals that are often ignored in recommendation design. Further, presence of such classes also reflect strong correlations to visual perception which can be utilized to provide aesthetically pleasing user experiences. Finally, we illustrate that user approval of visual fashion recommendations can be substantially improved by carefully incorporating these user-centric feedback into the system framework.
Three-Way Joins on MapReduce: An Experimental Study
Venue: arXiv cs.DB 2014
Year: 2014

We study three-way joins on MapReduce. Joins are very useful in a multitude of applications from data integration and traversing social networks, to mining graphs and automata-based constructions. However, joins are expensive, even for moderate data sets; we need efficient algorithms to perform distributed computation of joins using clusters of many machines. MapReduce has become an increasingly popular distributed computing system and programming paradigm. We consider a state-of-the-art MapReduce multi-way join algorithm by Afrati and Ullman and show when it is appropriate for use on very large data sets. By providing a detailed experimental study, we demonstrate that this algorithm scales much better than what is suggested by the original paper. However, if the join result needs to be summarized or aggregated, as opposed to being only enumerated, then the aggregation step can be integrated into a cascade of two-way joins, making it more efficient than the other algorithm, and thus becomes the preferred solution.
Optimized Cartesian $K$-Means
Venue: arXiv cs.CV 2014
Year: 2014

Product quantization-based approaches are effective to encode high-dimensional data points for approximate nearest neighbor search. The space is decomposed into a Cartesian product of low-dimensional subspaces, each of which generates a sub codebook. Data points are encoded as compact binary codes using these sub codebooks, and the distance between two data points can be approximated efficiently from their codes by the precomputed lookup tables. Traditionally, to encode a subvector of a data point in a subspace, only one sub codeword in the corresponding sub codebook is selected, which may impose strict restrictions on the search accuracy. In this paper, we propose a novel approach, named Optimized Cartesian $K$-Means (OCKM), to better encode the data points for more accurate approximate nearest neighbor search. In OCKM, multiple sub codewords are used to encode the subvector of a data point in a subspace. Each sub codeword stems from different sub codebooks in each subspace, which are optimally generated with regards to the minimization of the distortion errors. The high-dimensional data point is then encoded as the concatenation of the indices of multiple sub codewords from all the subspaces. This can provide more flexibility and lower distortion errors than traditional methods. Experimental results on the standard real-life datasets demonstrate the superiority over state-of-the-art approaches for approximate nearest neighbor search.
A preliminary study of Croatian Language Syllable Networks
Venue: arXiv cs.CL 2014
Year: 2014

This paper presents preliminary results of Croatian syllable networks analysis. Syllable network is a network in which nodes are syllables and links between them are constructed according to their connections within words. In this paper we analyze networks of syllables generated from texts collected from the Croatian Wikipedia and Blogs. As a main tool we use complex network analysis methods which provide mechanisms that can reveal new patterns in a language structure. We aim to show that syllable networks have much higher clustering coefficient in comparison to Erdös-Renyi random networks. The results indicate that Croatian syllable networks exhibit certain properties of a small world networks. Furthermore, we compared Croatian syllable networks with Portuguese and Chinese syllable networks and we showed that they have similar properties.
Detecting unknots via equational reasoning, I: Exploration
Venue: arXiv cs.LO 2014
Year: 2014

We explore the application of automated reasoning techniques to unknot detection, a classical problem of computational topology. We adopt a two-pronged experimental approach, using a theorem prover to try to establish a positive result (i.e. that a knot is the unknot), whilst simultaneously using a model finder to try to establish a negative result (i.e. that the knot is not the unknot). The theorem proving approach utilises equational reasoning, whilst the model finder searches for a minimal size counter-model. We present and compare experimental data using the involutary quandle of the knot, as well as comparing with alternative approaches, highlighting instances of interest. Furthermore, we present theoretical connections of the minimal countermodels obtained with existing knot invariants, for all prime knots of up to 10 crossings: this may be useful for developing advanced search strategies.
Survey of Key Distribution Schemes for Wireless Sensor Networks
Venue: arXiv cs.CR 2014
Year: 2014

This paper presents a survey of key distribution schemes for wireless sensor networks. This survey includes the new approach of key distribution using the piggy bank method. Different Network architectures and different key pre-distribution schemes are described. The survey includes the use of the piggy bank approach to cryptography in which part of the key is pre-distributed and the remainder is varied in the application.
Touch Survey: Comparison with Paper and Web Questionnaires
Venue: arXiv cs.HC 2014
Year: 2014

We developed a prototype of touch-based survey tool for tablets and conducted an experiment to compare interaction patterns of touch-based, PC-based, and paper-based questionnaires. Our findings suggest that a touch-based interface allows users to complete ranking questions easily, quickly, and accurately although it can increase the time to complete a location input task for well-known, prominent locations.
Lessons from the Congested Clique Applied to MapReduce
Venue: arXiv cs.DC 2014
Year: 2014

The main results of this paper are (I) a simulation algorithm which, under quite general constraints, transforms algorithms running on the Congested Clique into algorithms running in the MapReduce model, and (II) a distributed $O(Δ)$-coloring algorithm running on the Congested Clique which has an expected running time of (i) $O(1)$ rounds, if $Δ\geq Θ(\log^4 n)$; and (ii) $O(\log \log n)$ rounds otherwise. Applying the simulation theorem to the Congested-Clique $O(Δ)$-coloring algorithm yields an $O(1)$-round $O(Δ)$-coloring algorithm in the MapReduce model. Our simulation algorithm illustrates a natural correspondence between per-node bandwidth in the Congested Clique model and memory per machine in the MapReduce model. In the Congested Clique (and more generally, any network in the $\mathcal{CONGEST}$ model), the major impediment to constructing fast algorithms is the $O(\log n)$ restriction on message sizes. Similarly, in the MapReduce model, the combined restrictions on memory per machine and total system memory have a dominant effect on algorithm design. In showing a fairly general simulation algorithm, we highlight the similarities and differences between these models.
That's sick dude!: Automatic identification of word sense change across different timescales
Venue: arXiv cs.CL 2014
Year: 2014

In this paper, we propose an unsupervised method to identify noun sense changes based on rigorous analysis of time-varying text data available in the form of millions of digitized books. We construct distributional thesauri based networks from data at different time points and cluster each of them separately to obtain word-centric sense clusters corresponding to the different time points. Subsequently, we compare these sense clusters of two different time points to find if (i) there is birth of a new sense or (ii) if an older sense has got split into more than one sense or (iii) if a newer sense has been formed from the joining of older senses or (iv) if a particular sense has died. We conduct a thorough evaluation of the proposed methodology both manually as well as through comparison with WordNet. Manual evaluation indicates that the algorithm could correctly identify 60.4% birth cases from a set of 48 randomly picked samples and 57% split/join cases from a set of 21 randomly picked samples. Remarkably, in 44% cases the birth of a novel sense is attested by WordNet, while in 46% cases and 43% cases split and join are respectively confirmed by WordNet. Our approach can be applied for lexicography, as well as for applications like word sense disambiguation or semantic search.
Geometric Series as Nontermination Arguments for Linear Lasso Programs
Venue: arXiv cs.LO 2014
Year: 2014

We present a new kind of nontermination argument for linear lasso programs, called geometric nontermination argument. A geometric nontermination argument is a finite representation of an infinite execution of the form $(\vec{x} + \sum_{i=0}^t λ^i \vec{y})_{t \geq 0}$. The existence of this nontermination argument can be stated as a set of nonlinear algebraic constraints. We show that every linear loop program that has a bounded infinite execution also has a geometric nontermination argument. Furthermore, we discuss nonterminating programs that do not have a geometric nontermination argument.
Online Learning with Composite Loss Functions
Venue: arXiv cs.LG 2014
Year: 2014

We study a new class of online learning problems where each of the online algorithm's actions is assigned an adversarial value, and the loss of the algorithm at each step is a known and deterministic function of the values assigned to its recent actions. This class includes problems where the algorithm's loss is the minimum over the recent adversarial values, the maximum over the recent values, or a linear combination of the recent values. We analyze the minimax regret of this class of problems when the algorithm receives bandit feedback, and prove that when the minimum or maximum functions are used, the minimax regret is $\tilde Ω(T^{2/3})$ (so called hard online learning problems), and when a linear function is used, the minimax regret is $\tilde O(\sqrt{T})$ (so called easy learning problems). Previously, the only online learning problem that was known to be provably hard was the multi-armed bandit with switching costs.
AND-compression of NP-complete problems: Streamlined proof and minor observations
Venue: arXiv cs.CC 2014
Year: 2014

Drucker (2012) proved the following result: Unless the unlikely complexity-theoretic collapse coNP is in NP/poly occurs, there is no AND-compression for SAT. The result has implications for the compressibility and kernelizability of a whole range of NP-complete parameterized problems. We present a streamlined proof of Drucker's theorem. An AND-compression is a deterministic polynomial-time algorithm that maps a set of SAT-instances $x_1,\dots,x_t$ to a single SAT-instance $y$ of size poly(max $|x_i|$) such that $y$ is satisfiable if and only if all $x_i$ are satisfiable. The "AND" in the name stems from the fact that the predicate "$y$ is satisfiable" can be written as the AND of all predicates "$x_i$ is satisfiable". Drucker's result complements the result by Bodlaender et al. (2009) and Fortnow and Santhanam (2010), who proved the analogous statement for OR-compressions, and Drucker's proof not only subsumes that result but also extends it to randomized compression algorithms that are allowed to have a certain probability of failure. Drucker (2012) presented two proofs: The first uses information theory and the minimax theorem from game theory, and the second is an elementary, iterative proof that is not as general. In our proof, we realize the iterative structure as a generalization of the arguments of Ko (1983) for P-selective sets, which use the fact that tournaments have dominating sets of logarithmic size. We generalize this fact to hypergraph tournaments. Our proof achieves the full generality of Drucker's theorem, avoids the minimax theorem, and restricts the use of information theory to a single, intuitive lemma about the average noise sensitivity of compressive maps. To prove this lemma, we use the same information-theoretic inequalities as Drucker.
Secure Transmission in Amplify and Forward Networks for Multiple Degraded Eavesdroppers
Venue: arXiv cs.IT 2014
Year: 2014

We have evaluated the optimal secrecy rate for Amplify-and-Forward (AF) relay networks with multiple eavesdroppers. Assuming i.i.d. Gaussian noise at the destination and the eavesdroppers, we have devised technique to calculate optimal scaling factor for relay nodes to obtain optimal secrecy rate under both sum power constraint and individual power constraint. Initially, we have considered special channel conditions for both destination and eavesdroppers, which led us to analytical solution of the problem. Contrarily, the general scenario being a non-convex optimization problem, not only lacks an analytical solution, but also is hard to solve. Therefore, we have proposed an efficiently solvable quadratic program (QP) which provides a sub-optimal solution to the original problem. Then, we have devised an iterative scheme for calculating optimal scaling factor efficiently for both the sum power and individual power constraint scenario. Necessary figures are provided in result section to affirm the validity of our proposed solution.
Polynomial-time Approximation Algorithm for finding Highly Comfortable Team in any given Social Network
Venue: arXiv cs.DS 2014
Year: 2014

There are many indexes (measures or metrics) in Social Network Analysis (SNA), like density, cohesion, etc. In this paper, we define a new SNA index called "comfortability". One among the lack of many factors, which affect the effectiveness of a group, is "comfortability". So, comfortability is one of the important attributes (characteristics) for a successful team work. It is important to find a comfortable and successful team in any given social network. In this paper, comfortable team, better comfortable team and highly comfortable team of a social network are defined based on \textbf{graph theoretic concepts} and some of their structural properties are analyzed. It is proved that forming better comfortable team or highly comfortable team in any connected network are NP-Complete using the concepts of domination in graph theory. Next, we give a polynomial-time approximation algorithm for finding such a highly comfortable team in any given network with performance ratio O(\ln Δ), where Δis the maximum degree of a given network (graph). The time complexity of the algorithm is proved to be O(n^{3}), where n is the number of persons (vertices) in the network (graph). It is also proved that our algorithm has reasonably reduced the dispersion rate.
Fast Adaptive Beamforming based on kernel method under Small Sample Support
Venue: arXiv cs.IT 2014
Year: 2014

It is well-known that the high computational complexity and the insufficient samples in large-scale array signal processing restrict the real-world applications of the conventional full-dimensional adaptive beamforming (sample matrix inversion) algorithms. In this paper, we propose a computationally efficient and fast adaptive beamforming algorithm under small sample support. The proposed method is implemented by formulating the adaptive weight vector as a linear combination of training samples plus a signal steering vector, on the basis of the fact that the adaptive weight vector lies in the signal-plus-interference subspace. Consequently, by using the well-known linear kernel methods with very good small-sample performance, only a low-dimension combination vector needs to be computed instead of the high-dimension adaptive weight vector itself, which remarkably reduces the degree of freedom and the computational complexity. Experimental results validate the good performance and the computational effectiveness of the proposed methods for small samples.
A novel energy-efficient resource allocation algorithm based on immune clonal optimization for green cloud computing
Venue: arXiv cs.DC 2014
Year: 2014

Cloud computing is a style of computing in which dynamically scalable and other virtualized resources are provided as a service over the Internet. The energy consumption and makespan associated with the resources allocated should be taken into account. This paper proposes an improved clonal selection algorithm based on time cost and energy consumption models in cloud computing environment. We have analyzed the performance of our approach using the CloudSim toolkit. The experimental results show that our approach has immense potential as it offers significant improvement in the aspects of response time and makespan, demonstrates high potential for the improvement in energy efficiency of the data center, and can effectively meet the service level agreement requested by the users.
Space Shuffle: A Scalable, Flexible, and High-Bandwidth Data Center Network
Venue: arXiv cs.NI 2014
Year: 2014

Data center applications require the network to be scalable and bandwidth-rich. Current data center network architectures often use rigid topologies to increase network bandwidth. A major limitation is that they can hardly support incremental network growth. Recent work proposes to use random interconnects to provide growth flexibility. However routing on a random topology suffers from control and data plane scalability problems, because routing decisions require global information and forwarding state cannot be aggregated. In this paper we design a novel flexible data center network architecture, Space Shuffle (S2), which applies greedy routing on multiple ring spaces to achieve high-throughput, scalability, and flexibility. The proposed greedy routing protocol of S2 effectively exploits the path diversity of densely connected topologies and enables key-based routing. Extensive experimental studies show that S2 provides high bisectional bandwidth and throughput, near-optimal routing path lengths, extremely small forwarding state, fairness among concurrent data flows, and resiliency to network failures.
Trends and Perspectives for Signal Processing in Consumer Audio
Venue: arXiv cs.SD 2014
Year: 2014

The trend in media consumption towards streaming and portability offers new challenges and opportunities for signal processing in audio and acoustics. The most significant embodiment of this trend is that most music consumption now happens on-the-go which has recently led to an explosion in headphone sales and small portable speakers. In particular, premium headphones offer a gateway for a younger generation to experience high quality sound. Additionally, through technologies incorporating head-related transfer functions headphones can also offer unique new experiences in gaming, augmented reality, and surround sound listening. Home audio has also seen a transition to smaller sound systems in the form of sound bars. This speaker configuration offers many exciting challenges for surround sound reproduction which has traditionally used five speakers surrounding the listener. Furthermore, modern home entertainment systems offer more than just content delivery; users now expect wireless and connected smart devices with video conferencing, gaming, and other interactive capabilities. With this comes challenges for voice interaction at a distance and in demanding conditions, e.g., during content playback, and opportunities for new smart interactive experiences based on awareness of environment and user biometrics.