OpenRaiser/Intern-Atlas huggingface dataset:
Clique counting in MapReduce: theory and experiments
Venue: arXiv cs.DC 2014
Year: 2014

We tackle the problem of counting the number of $k$-cliques in large-scale graphs, for any constant $k \ge 3$. Clique counting is essential in a variety of applications, among which social network analysis. Due to its computationally intensive nature, we settle for parallel solutions in the MapReduce framework, which has become in the last few years a {\em de facto} standard for batch processing of massive data sets. We give both theoretical and experimental contributions. On the theory side, we design the first exact scalable algorithm for counting (and listing) $k$-cliques. Our algorithm uses $O(m^{3/2})$ total space and $O(m^{k/2})$ work, where $m$ is the number of graph edges. This matches the best-known bounds for triangle listing when $k=3$ and is work-optimal in the worst case for any $k$, while keeping the communication cost independent of $k$. We also design a sampling-based estimator that can dramatically reduce the running time and space requirements of the exact approach, while providing very accurate solutions with high probability. We then assess the effectiveness of different clique counting approaches through an extensive experimental analysis over the Amazon EC2 platform, considering both our algorithms and their state-of-the-art competitors. The experimental results clearly highlight the algorithm of choice in different scenarios and prove our exact approach to be the most effective when the number of $k$-cliques is large, gracefully scaling to non-trivial values of $k$ even on clusters of small/medium size. Our approximation algorithm achieves extremely accurate estimates and large speedups, especially on the toughest instances for the exact algorithms. As a side effect, our study also sheds light on the number of $k$-cliques of several real-world graphs, mainly social networks, and on its growth rate as a function of $k$.
QPTAS for Geometric Set-Cover Problems via Optimal Separators
Venue: arXiv cs.CG 2014
Year: 2014

Weighted geometric set-cover problems arise naturally in several geometric and non-geometric settings (e.g. the breakthrough of Bansal-Pruhs (FOCS 2010) reduces a wide class of machine scheduling problems to weighted geometric set-cover). More than two decades of research has succeeded in settling the $(1+ε)$-approximability status for most geometric set-cover problems, except for four basic scenarios which are still lacking. One is that of weighted disks in the plane for which, after a series of papers, Varadarajan (STOC 2010) presented a clever \emph{quasi-sampling} technique, which together with improvements by Chan \etal~(SODA 2012), yielded a $O(1)$-approximation algorithm. Even for the unweighted case, a PTAS for a fundamental class of objects called pseudodisks (which includes disks, unit-height rectangles, translates of convex sets etc.) is currently unknown. Another fundamental case is weighted halfspaces in $\Re^3$, for which a PTAS is currently lacking. In this paper, we present a QPTAS for all of these remaining problems. Our results are based on the separator framework of Adamaszek-Wiese (FOCS 2013, SODA 2014), who recently obtained a QPTAS for weighted independent set of polygonal regions. This rules out the possibility that these problems are APX-hard, assuming $\textbf{NP} \nsubseteq \textbf{DTIME}(2^{polylog(n)})$. Together with the recent work of Chan-Grant (CGTA 2014), this settles the APX-hardness status for all natural geometric set-cover problems.
How to Network in Online Social Networks
Venue: arXiv cs.SI 2014
Year: 2014

In this paper, we consider how to maximize users' influence in Online Social Networks (OSNs) by exploiting social relationships only. Our first contribution is to extend to OSNs the model of Kempe et al. [1] on the propagation of information in a social network and to show that a greedy algorithm is a good approximation of the optimal algorithm that is NP-hard. However, the greedy algorithm requires global knowledge, which is hardly practical. Our second contribution is to show on simulations on the full Twitter social graph that simple and practical strategies perform close to the greedy algorithm.
Algorithmic Verification of Continuous and Hybrid Systems
Venue: arXiv cs.SY 2014
Year: 2014

We provide a tutorial introduction to reachability computation, a class of computational techniques that exports verification technology toward continuous and hybrid systems. For open under-determined systems, this technique can sometimes replace an infinite number of simulations.
Parametrized Algorithms for Random Serial Dictatorship
Venue: arXiv cs.GT 2014
Year: 2014

Voting and assignment are two of the most fundamental settings in social choice theory. For both settings, random serial dictatorship (RSD) is a well-known rule that satisfies anonymity, ex post efficiency, and strategyproofness. Recently, it was shown that computing the resulting probabilities is #P-complete both in the voting and assignment setting. In this paper, we study RSD from a parametrized complexity perspective. More specifically, we present efficient algorithms to compute the RSD probabilities under the condition that the number of agent types, alternatives, or objects is bounded.
Signal Estimation from Nonuniform Samples with RMS Error Bound -- Application to OFDM Channel Estimation
Venue: arXiv cs.IT 2014
Year: 2014

We present a channel spectral estimator for OFDM signals containing pilot carriers, assuming a known delay spread or a bound on this parameter. The estimator is based on modeling the channel's spectrum as a band-limited function, instead of as the discrete Fourier transform of a tapped delay line (TDL). Its main advantage is its immunity to the truncation mismatch in usual TDL models (Gibbs phenomenon). In order to assess the estimator, we compare it with the well-known TDL maximum likelihood (ML) estimator in terms of root-mean-square (RMS) error. The main result is that the proposed estimator improves on the ML estimator significantly, whenever the average spectral sampling rate is above the channel's delay spread. The improvement increases with the spectral oversampling ratio.
Inducing Language Networks from Continuous Space Word Representations
Venue: arXiv cs.LG 2014
Year: 2014

Recent advancements in unsupervised feature learning have developed powerful latent representations of words. However, it is still not clear what makes one representation better than another and how we can learn the ideal representation. Understanding the structure of latent spaces attained is key to any future advancement in unsupervised learning. In this work, we introduce a new view of continuous space word representations as language networks. We explore two techniques to create language networks from learned features by inducing them for two popular word representation methods and examining the properties of their resulting networks. We find that the induced networks differ from other methods of creating language networks, and that they contain meaningful community structure.
Quantifying the Information Leakage in Timing Side Channels in Deterministic Work-Conserving Schedulers
Venue: arXiv cs.IT 2014
Year: 2014

When multiple job processes are served by a single scheduler, the queueing delays of one process are often affected by the others, resulting in a timing side channel that leaks the arrival pattern of one process to the others. In this work, we study such a timing side channel between a regular user and a malicious attacker. Utilizing Shannon's mutual information as a measure of information leakage between the user and attacker, we analyze privacy-preserving behaviors of common work-conserving schedulers. We find that the attacker can always learn perfectly the user's arrival process in a longest-queue-first (LQF) scheduler. When the user's job arrival rate is very low (near zero), first-come-first-serve (FCFS) and round robin schedulers both completely reveal the user's arrival pattern. The near-complete information leakage in the low-rate traffic region is proven to be reduced by half in a work-conserving version of TDMA (WC-TDMA) scheduler, which turns out to be privacy-optimal in the class of deterministic-working-conserving (det-WC) schedulers, according to a universal lower bound on information leakage we derive for all det-WC schedulers.
Integer Programming Relaxations for Integrated Clustering and Outlier Detection
Venue: arXiv cs.LG 2014
Year: 2014

In this paper we present methods for exemplar based clustering with outlier selection based on the facility location formulation. Given a distance function and the number of outliers to be found, the methods automatically determine the number of clusters and outliers. We formulate the problem as an integer program to which we present relaxations that allow for solutions that scale to large data sets. The advantages of combining clustering and outlier selection include: (i) the resulting clusters tend to be compact and semantically coherent (ii) the clusters are more robust against data perturbations and (iii) the outliers are contextualised by the clusters and more interpretable, i.e. it is easier to distinguish between outliers which are the result of data errors from those that may be indicative of a new pattern emergent in the data. We present and contrast three relaxations to the integer program formulation: (i) a linear programming formulation (LP) (ii) an extension of affinity propagation to outlier detection (APOC) and (iii) a Lagrangian duality based formulation (LD). Evaluation on synthetic as well as real data shows the quality and scalability of these different methods.
Collaborative Representation for Classification, Sparse or Non-sparse?
Venue: arXiv cs.CV 2014
Year: 2014

Sparse representation based classification (SRC) has been proved to be a simple, effective and robust solution to face recognition. As it gets popular, doubts on the necessity of enforcing sparsity starts coming up, and primary experimental results showed that simply changing the $l_1$-norm based regularization to the computationally much more efficient $l_2$-norm based non-sparse version would lead to a similar or even better performance. However, that's not always the case. Given a new classification task, it's still unclear which regularization strategy (i.e., making the coefficients sparse or non-sparse) is a better choice without trying both for comparison. In this paper, we present as far as we know the first study on solving this issue, based on plenty of diverse classification experiments. We propose a scoring function for pre-selecting the regularization strategy using only the dataset size, the feature dimensionality and a discrimination score derived from a given feature representation. Moreover, we show that when dictionary learning is taking into account, non-sparse representation has a more significant superiority to sparse representation. This work is expected to enrich our understanding of sparse/non-sparse collaborative representation for classification and motivate further research activities.
Phase Transitions in Phase Retrieval
Venue: arXiv cs.IT 2014
Year: 2014

Consider a scenario in which an unknown signal is transformed by a known linear operator, and then the pointwise absolute value of the unknown output function is reported. This scenario appears in several applications, and the goal is to recover the unknown signal -- this is called phase retrieval. Phase retrieval has been a popular subject of research in the last few years, both in determining whether complete information is available with a given linear operator, and in finding efficient and stable phase retrieval algorithms in the cases where complete information is available. Interestingly, there are a few ways to measure information completeness, and each way appears to be governed by a phase transition of sorts. This chapter will survey the state of the art with some of these phase transitions, and identify a few open problems for further research.
Lifespan and propagation of information in On-line Social Networks a Case Study
Venue: arXiv cs.SI 2014
Year: 2014

Since 1950, information flows have been in the centre of scientific research. Up until internet penetration in the late 90s, these studies were based over traditional offline social networks. Several observations in offline information flows studies, such as two-step flow of communication and the importance of weak ties, were verified in several online studies, showing that the diffused information flows from one Online Social Network (OSN) to several others. Within that flow, information is shared to and reproduced by the users of each network. Furthermore, the original content is enhanced or weakened according to its topic, the dynamic and exposure of each OSNs. In such a concept, each OSN is considered a layer of information flows that interacts with each other. In this paper, we examine such flows in several social networks, as well as their diffusion and lifespan across multiple OSNs, in terms of user-generated content. Our results verify the perception of content and information connection in various OSNs.
Social welfare in one-sided matchings: Random priority and beyond
Venue: arXiv cs.GT 2014
Year: 2014

We study the problem of approximate social welfare maximization (without money) in one-sided matching problems when agents have unrestricted cardinal preferences over a finite set of items. Random priority is a very well-known truthful-in-expectation mechanism for the problem. We prove that the approximation ratio of random priority is Theta(n^{-1/2}) while no truthful-in-expectation mechanism can achieve an approximation ratio better than O(n^{-1/2}), where n is the number of agents and items. Furthermore, we prove that the approximation ratio of all ordinal (not necessarily truthful-in-expectation) mechanisms is upper bounded by O(n^{-1/2}), indicating that random priority is asymptotically the best truthful-in-expectation mechanism and the best ordinal mechanism for the problem.
Robust PCA with Partial Subspace Knowledge
Venue: arXiv cs.IT 2014
Year: 2014

In recent work, robust Principal Components Analysis (PCA) has been posed as a problem of recovering a low-rank matrix $\mathbf{L}$ and a sparse matrix $\mathbf{S}$ from their sum, $\mathbf{M}:= \mathbf{L} + \mathbf{S}$ and a provably exact convex optimization solution called PCP has been proposed. This work studies the following problem. Suppose that we have partial knowledge about the column space of the low rank matrix $\mathbf{L}$. Can we use this information to improve the PCP solution, i.e. allow recovery under weaker assumptions? We propose here a simple but useful modification of the PCP idea, called modified-PCP, that allows us to use this knowledge. We derive its correctness result which shows that, when the available subspace knowledge is accurate, modified-PCP indeed requires significantly weaker incoherence assumptions than PCP. Extensive simulations are also used to illustrate this. Comparisons with PCP and other existing work are shown for a stylized real application as well. Finally, we explain how this problem naturally occurs in many applications involving time series data, i.e. in what is called the online or recursive robust PCA problem. A corollary for this case is also given.
Massively parallel read mapping on GPUs with PEANUT
Venue: arXiv cs.DS 2014
Year: 2014

We present PEANUT (ParallEl AligNment UTility), a highly parallel GPU-based read mapper with several distinguishing features, including a novel q-gram index (called the q-group index) with small memory footprint built on-the-fly over the reads and the possibility to output both the best hits or all hits of a read. Designing the algorithm particularly for the GPU architecture, we were able to reach maximum core occupancy for several key steps. Our benchmarks show that PEANUT outperforms other state-of- the-art mappers in terms of speed and sensitivity. The software is available at http://peanut.readthedocs.org.
Designing an FPGA Synthesizable Computer Vision Algorithm to Detect the Greening of Potatoes
Venue: arXiv cs.CV 2014
Year: 2014

Potato quality control has improved in the last years thanks to automation techniques like machine vision, mainly making the classification task between different quality degrees faster, safer and less subjective. In our study we are going to design a computer vision algorithm for grading of potatoes according to the greening of the surface color of potato. The ratio of green pixels to the total number of pixels of the potato surface is found. The higher the ratio the worse is the potato. First the image is converted into serial data and then processing is done in RGB colour space. Green part of the potato is also shown by de-serializing the output. The same algorithm is then synthesized on FPGA and the result shows thousand times speed improvement in case of hardware synthesis.
Time Series Analysis on Stock Market for Text Mining Correlation of Economy News
Venue: arXiv cs.CE 2014
Year: 2014

This paper proposes an information retrieval method for the economy news. The effect of economy news, are researched in the word level and stock market values are considered as the ground proof. The correlation between stock market prices and economy news is an already addressed problem for most of the countries. The most well-known approach is applying the text mining approaches to the news and some time series analysis techniques over stock market closing values in order to apply classification or clustering algorithms over the features extracted. This study goes further and tries to ask the question what are the available time series analysis techniques for the stock market closing values and which one is the most suitable? In this study, the news and their dates are collected into a database and text mining is applied over the news, the text mining part has been kept simple with only term frequency-inverse document frequency method. For the time series analysis part, we have studied 10 different methods such as random walk, moving average, acceleration, Bollinger band, price rate of change, periodic average, difference, momentum or relative strength index and their variation. In this study we have also explained these techniques in a comparative way and we have applied the methods over Turkish Stock Market closing values for more than a 2 year period. On the other hand, we have applied the term frequency-inverse document frequency method on the economy news of one of the high-circulating newspapers in Turkey.
Technical Report: Efficient Buffering and Scheduling for a Single-Chip Crosspoint-Queued Switch
Venue: arXiv cs.NI 2014
Year: 2014

The single-chip crosspoint-queued (CQ) switch is a compact switching architecture that has all its buffers placed at the crosspoints of input and output lines. Scheduling is also performed inside the switching core, and does not rely on latency-limited communications with input or output line-cards. Compared with other legacy switching architectures, the CQ switch has the advantages of high throughput, minimal delay, low scheduling complexity, and no speedup requirement. However, the crosspoint buffers are small and segregated, thus how to efficiently use the buffers and avoid packet drops remains a major problem that needs to be addressed. In this paper, we consider load balancing, deflection routing, and buffer pooling for efficient buffer sharing in the CQ switch. We also design scheduling algorithms to maintain the correct packet order even while employing multi-path switching and resolve contentions caused by multiplexing. All these techniques require modest hardware modifications and memory speedup in the switching core, but can greatly boost the buffer utilizations by up to 10 times and reduce the packet drop rates by one to three orders of magnitude. Extensive simulations and analyses have been done to demonstrate the advantages of the proposed buffering and scheduling techniques in various aspects. By pushing the on-chip memory to the limit of current ASIC technology, we show that a cell drop rate of 10e-8, which is low enough for practical uses, can be achieved under real Internet traffic traces corresponding to a load of 0.9.
Protograph-Based Raptor-Like LDPC Codes
Venue: arXiv cs.IT 2014
Year: 2014

This paper proposes a class of rate-compatible LDPC codes, called protograph-based Raptor-like (PBRL) codes. The construction is focused on binary codes for BI-AWGN channels. As with the Raptor codes, additional parity bits are produced by exclusive-OR operations on the precoded bits, providing extensive rate compatibility. Unlike Raptor codes, the structure of each additional parity bit in the protograph is explicitly designed through density evolution. The construction method provides low iterative decoding thresholds and the lifted codes result in excellent error rate performance for long-blocklength PBRL codes. For short-blocklength PBRL codes the protograph design and lifting must avoid undesired graphical structures such as trapping sets and absorbing sets while also seeking to minimize the density evolution threshold. Simulation results are shown in information block sizes of $k=192$, $16368$ and $16384$. Comparing at the same information block size of $k=16368$ bits, the PBRL codes outperform the best known standardized code, the AR4JA codes in the waterfall region. The PBRL codes also perform comparably to DVB-S2 codes even though the DVB-S2 codes use LDPC codes with longer blocklengths and are concatenated with outer BCH codes.
Global Synchronization of Pulse-Coupled Oscillators Interacting on Cycle Graphs
Venue: arXiv cs.SY 2014
Year: 2014

The importance of pulse-coupled oscillators (PCOs) in biology and engineering has motivated research to understand basic properties of PCO networks. Despite the large body of work addressing PCOs, a global synchronization result for networks that are more general than all-to-all connected is still unavailable. In this paper we address global synchronization of PCO networks described by cycle graphs. It is shown for the bidirectional cycle case that as the number of oscillators in the cycle grows, the coupling strength must be increased in order to guarantee synchronization for arbitrary initial conditions. For the unidirectional cycle case, the strongest coupling cannot ensure global synchronization yet a refractory period in the phase response curve is sufficient to enable global synchronization. Analytical findings are confirmed by numerical simulations.
Scientometrics: Untangling the topics
Venue: arXiv cs.DL 2014
Year: 2014

Measuring science is based on comparing articles to similar others. However, keyword-based groups of thematically similar articles are dominantly small. These small sizes keep the statistical errors of comparisons high. With the growing availability of bibliographic data such statistical errors can be reduced by merging methods of thematic grouping, citation networks and keyword co-usage.
A New Technique for INS/GNSS Attitude and Parameter Estimation Using Online Optimization
Venue: arXiv cs.RO 2014
Year: 2014

Integration of inertial navigation system (INS) and global navigation satellite system (GNSS) is usually implemented in engineering applications by way of Kalman-like filtering. This form of INS/GNSS integration is prone to attitude initialization failure, especially when the host vehicle is moving freely. This paper proposes an online constrained-optimization method to simultaneously estimate the attitude and other related parameters including GNSS antenna's lever arm and inertial sensor biases. This new technique benefits from self-initialization in which no prior attitude or sensor measurement noise information is required. Numerical results are reported to validate its effectiveness and prospect in high accurate INS/GNSS applications.