OpenRaiser/Intern-Atlas huggingface dataset:
A Story of Suo Motos, Judicial Activism, and Article 184 (3)
Venue: arXiv cs.CY 2015
Year: 2015

The synergy between Big Data and Open Data has the potential to revolutionize information access in the developing world. Following this mantra, we present the analysis of more than a decade worth of open judgements and orders from the Supreme Court of Pakistan. Our overarching goal is to discern the presence of judicial activism in the country in the wake of the Lawyers' Movement. Using Apache Spark as the processing engine we analyze hundreds of unstructured PDF documents to sketch the evolution and various organs of judicial activism in Pakistan since 2009. Our results show that the judiciary has indeed been pursuing matters of public interest, especially those that pertain to the fundamental rights of the citizens. Furthermore, we show how the size of the presiding bench in a case and citations of Articles from the Constitution and prior judgements can aid in classifying legal judgements. Throughout the analysis we also highlight the challenges that anyone who aims to apply Big Data techniques to Open Data will face. We hope that this work will be one in a series of community efforts to use Open Data as a lens to analyze real-world events and phenomena in the developing world.
Adaptive Search over Sorted Sets
Venue: arXiv cs.DS 2015
Year: 2015

We revisit the classical algorithms for searching over sorted sets to introduce an algorithm refinement, called Adaptive Search, that combines the good features of Interpolation search and those of Binary search. W.r.t. Interpolation search, only a constant number of extra comparisons is introduced. Yet, under diverse input data distributions our algorithm shows costs comparable to that of Interpolation search, i.e., O(log log n) while the worst-case cost is always in O(log n), as with Binary search. On benchmarks drawn from large datasets, both synthetic and real-life, Adaptive search scores better times and lesser memory accesses even than Santoro and Sidney's Interpolation-Binary search.
Coding for Network-Coded Slotted ALOHA
Venue: arXiv cs.IT 2015
Year: 2015

Slotted ALOHA can benefit from physical-layer network coding (PNC) by decoding one or multiple linear combinations of the packets simultaneously transmitted in a timeslot, forming a system of linear equations. Different systems of linear equations are recovered in different timeslots. A message decoder then recovers the original packets of all the users by jointly solving multiple systems of linear equations obtained over different timeslots. We propose the batched BP decoding algorithm that combines belief propagation (BP) and local Gaussian elimination. Compared with pure Gaussian elimination decoding, our algorithm reduces the decoding complexity from cubic to linear function of the number of users. Compared with the ordinary BP decoding algorithm for low-density generator-matrix codes, our algorithm has better performance and the same order of computational complexity. We analyze the performance of the batched BP decoding algorithm by generalizing the tree-based approach and provide an approach to optimize the system performance.
Uniform Kernelization Complexity of Hitting Forbidden Minors
Venue: arXiv cs.DS 2015
Year: 2015

The F-Minor-Free Deletion problem asks, for a fixed set F and an input consisting of a graph G and integer k, whether k vertices can be removed from G such that the resulting graph does not contain any member of F as a minor. This paper analyzes to what extent provably effective and efficient preprocessing is possible for F-Minor-Free Deletion. Fomin et al. (FOCS 2012) showed that the special case Planar F-Deletion (when F contains at least one planar graph) has a kernel of size f(F) * k^{g(F)} for some functions f and g. The degree g of the polynomial grows very quickly; it is not even known to be computable. Fomin et al. left open whether Planar F-Deletion has kernels whose size is uniformly polynomial, i.e., of the form f(F) * k^c for some universal constant c that does not depend on F. Our results in this paper are twofold. (1) We prove that some Planar F-Deletion problems do not have uniformly polynomial kernels (unless NP is in coNP/poly). In particular, we prove that Treewidth-Eta Deletion does not have a kernel with O(k^{eta/4} - eps) vertices for any eps > 0, unless NP is in coNP/poly. In fact, we even prove the kernelization lower bound for the larger parameter vertex cover number. This resolves an open problem of Cygan et al. (IPEC 2011). It is a natural question whether further restrictions on F lead to uniformly polynomial kernels. However, we prove that even when F contains a path, the degree of the polynomial must, in general, depend on the set F. (2) A canonical F-Minor-Free Deletion problem when F contains a path is Treedepth-eta Deletion: can k vertices be removed to obtain a graph of treedepth at most eta? We prove that Treedepth-eta Deletion admits uniformly polynomial kernels with O(k^6) vertices for every fixed eta. In order to develop the kernelization we prove several new results about the structure of optimal treedepth-decompositions.
How essential are unstructured clinical narratives and information fusion to clinical trial recruitment?
Venue: arXiv cs.CY 2015
Year: 2015

Electronic health records capture patient information using structured controlled vocabularies and unstructured narrative text. While structured data typically encodes lab values, encounters and medication lists, unstructured data captures the physician's interpretation of the patient's condition, prognosis, and response to therapeutic intervention. In this paper, we demonstrate that information extraction from unstructured clinical narratives is essential to most clinical applications. We perform an empirical study to validate the argument and show that structured data alone is insufficient in resolving eligibility criteria for recruiting patients onto clinical trials for chronic lymphocytic leukemia (CLL) and prostate cancer. Unstructured data is essential to solving 59% of the CLL trial criteria and 77% of the prostate cancer trial criteria. More specifically, for resolving eligibility criteria with temporal constraints, we show the need for temporal reasoning and information integration with medical events within and across unstructured clinical narratives and structured data.
Overlapped-MIMO Radar Waveform Design for Coexistence With Communication Systems
Venue: arXiv cs.IT 2015
Year: 2015

This paper explores an overlapped-multiple-input multiple-output (MIMO) antenna architecture and a spectrum sharing algorithm via null space projection (NSP) for radar-communications coexistence. In the overlapped-MIMO architecture, the transmit array of a collocated MIMO radar is partitioned into a number of subarrays that are allowed to overlap. Each of the antenna elements in these subarrays have signals orthogonal to each other and to the elements of the other subarrays. The proposed architecture not only improves sidelobe suppression to reduce interference to communications system, but also enjoys the advantages of MIMO radar without sacrificing the main desirable characteristics. The radar-centric spectrum sharing algorithm then projects the radar signal onto the null space of the communications system's interference channel, which helps to avoid interference from the radar. Numerical results are presented which show the performance of the proposed waveform design algorithm in terms of overall beampattern and sidelobe levels of the radar waveform and finally shows a comparison of the proposed system with existing collocated MIMO radar architectures.
Extracting Hidden Groups and their Structure from Streaming Interaction Data
Venue: arXiv cs.SI 2015
Year: 2015

When actors in a social network interact, it usually means they have some general goal towards which they are collaborating. This could be a research collaboration in a company or a foursome planning a golf game. We call such groups \emph{planning groups}. In many social contexts, it might be possible to observe the \emph{dyadic interactions} between actors, even if the actors do not explicitly declare what groups they belong too. When groups are not explicitly declared, we call them \emph{hidden groups}. Our particular focus is hidden planning groups. By virtue of their need to further their goal, the actors within such groups must interact in a manner which differentiates their communications from random background communications. In such a case, one can infer (from these interactions) the composition and structure of the hidden planning groups. We formulate the problem of hidden group discovery from streaming interaction data, and we propose efficient algorithms for identifying the hidden group structures by isolating the hidden group's non-random, planning-related, communications from the random background communications. We validate our algorithms on real data (the Enron email corpus and Blog communication data). Analysis of the results reveals that our algorithms extract meaningful hidden group structures.
Coexistence of Wi-Fi and Heterogeneous Small Cell Networks Sharing Unlicensed Spectrum
Venue: arXiv cs.IT 2015
Year: 2015

As two major players in terrestrial wireless communications, Wi-Fi systems and cellular networks have different origins and have largely evolved separately. Motivated by the exponentially increasing wireless data demand, cellular networks are evolving towards a heterogeneous and small cell network architecture, wherein small cells are expected to provide very high capacity. However, due to the limited licensed spectrum for cellular networks, any effort to achieve capacity growth through network densification will face the challenge of severe inter-cell interference. In view of this, recent standardization developments have started to consider the opportunities for cellular networks to use the unlicensed spectrum bands, including the 2.4 GHz and 5 GHz bands that are currently used by Wi-Fi, Zigbee and some other communication systems. In this article, we look into the coexistence of Wi-Fi and 4G cellular networks sharing the unlicensed spectrum. We introduce a network architecture where small cells use the same unlicensed spectrum that Wi-Fi systems operate in without affecting the performance of Wi-Fi systems. We present an almost blank subframe (ABS) scheme without priority to mitigate the co-channel interference from small cells to Wi-Fi systems, and propose an interference avoidance scheme based on small cells estimating the density of nearby Wi-Fi access points to facilitate their coexistence while sharing the same unlicensed spectrum. Simulation results show that the proposed network architecture and interference avoidance schemes can significantly increase the capacity of 4G heterogeneous cellular networks while maintaining the service quality of Wi-Fi systems.
Nonparametric regression using needlet kernels for spherical data
Venue: arXiv cs.LG 2015
Year: 2015

Needlets have been recognized as state-of-the-art tools to tackle spherical data, due to their excellent localization properties in both spacial and frequency domains. This paper considers developing kernel methods associated with the needlet kernel for nonparametric regression problems whose predictor variables are defined on a sphere. Due to the localization property in the frequency domain, we prove that the regularization parameter of the kernel ridge regression associated with the needlet kernel can decrease arbitrarily fast. A natural consequence is that the regularization term for the kernel ridge regression is not necessary in the sense of rate optimality. Based on the excellent localization property in the spacial domain further, we also prove that all the $l^{q}$ $(01\leq q < \infty)$ kernel regularization estimates associated with the needlet kernel, including the kernel lasso estimate and the kernel bridge estimate, possess almost the same generalization capability for a large range of regularization parameters in the sense of rate optimality. This finding tentatively reveals that, if the needlet kernel is utilized, then the choice of $q$ might not have a strong impact in terms of the generalization capability in some modeling contexts. From this perspective, $q$ can be arbitrarily specified, or specified merely by other no generalization criteria like smoothness, computational complexity, sparsity, etc..
A Row-parallel 8$\times$8 2-D DCT Architecture Using Algebraic Integer Based Exact Computation
Venue: arXiv cs.AR 2015
Year: 2015

An algebraic integer (AI) based time-multiplexed row-parallel architecture and two final-reconstruction step (FRS) algorithms are proposed for the implementation of bivariate AI-encoded 2-D discrete cosine transform (DCT). The architecture directly realizes an error-free 2-D DCT without using FRSs between row-column transforms, leading to an 8$\times$8 2-D DCT which is entirely free of quantization errors in AI basis. As a result, the user-selectable accuracy for each of the coefficients in the FRS facilitates each of the 64 coefficients to have its precision set independently of others, avoiding the leakage of quantization noise between channels as is the case for published DCT designs. The proposed FRS uses two approaches based on (i) optimized Dempster-Macleod multipliers and (ii) expansion factor scaling. This architecture enables low-noise high-dynamic range applications in digital video processing that requires full control of the finite-precision computation of the 2-D DCT. The proposed architectures and FRS techniques are experimentally verified and validated using hardware implementations that are physically realized and verified on FPGA chip. Six designs, for 4- and 8-bit input word sizes, using the two proposed FRS schemes, have been designed, simulated, physically implemented and measured. The maximum clock rate and block-rate achieved among 8-bit input designs are 307.787 MHz and 38.47 MHz, respectively, implying a pixel rate of 8$\times$307.787$\approx$2.462 GHz if eventually embedded in a real-time video-processing system. The equivalent frame rate is about 1187.35 Hz for the image size of 1920$\times$1080. All implementations are functional on a Xilinx Virtex-6 XC6VLX240T FPGA device.
Sketch-based Shape Retrieval using Pyramid-of-Parts
Venue: arXiv cs.GR 2015
Year: 2015

We present a multi-scale approach to sketch-based shape retrieval. It is based on a novel multi-scale shape descriptor called Pyramidof- Parts, which encodes the features and spatial relationship of the semantic parts of query sketches. The same descriptor can also be used to represent 2D projected views of 3D shapes, allowing effective matching of query sketches with 3D shapes across multiple scales. Experimental results show that the proposed method outperforms the state-of-the-art method, whether the sketch segmentation information is obtained manually or automatically by considering each stroke as a semantic part.
Solving $k$-means on High-dimensional Big Data
Venue: arXiv cs.DS 2015
Year: 2015

In recent years, there have been major efforts to develop data stream algorithms that process inputs in one pass over the data with little memory requirement. For the $k$-means problem, this has led to the development of several $(1+\varepsilon)$-approximations (under the assumption that $k$ is a constant), but also to the design of algorithms that are extremely fast in practice and compute solutions of high accuracy. However, when not only the length of the stream is high but also the dimensionality of the input points, then current methods reach their limits. We propose two algorithms, piecy and piecy-mr that are based on the recently developed data stream algorithm BICO that can process high dimensional data in one pass and output a solution of high quality. While piecy is suited for high dimensional data with a medium number of points, piecy-mr is meant for high dimensional data that comes in a very long stream. We provide an extensive experimental study to evaluate piecy and piecy-mr that shows the strength of the new algorithms.
Relative Squared Distances to a Conic Berserkless 8-Connected Midpoint Algorithm
Venue: arXiv cs.GR 2015
Year: 2015

The midpoint method or technique is a measurement and as each measurement it has a tolerance, but worst of all it can be invalid, called Out-of-Control or OoC. The core of all midpoint methods is the accurate measurement of the difference of the squared distances of two points to the polar of their midpoint with respect to the conic. When this measurement is valid, it also measures the difference of the squared distances of these points to the conic, although it may be inaccurate, called Out-of-Accuracy or OoA. The primary condition is the necessary and sufficient condition that a measurement is valid. It is comletely new and it can be checked ultra fast and before the actual measurement starts. Modeling an incremental algorithm, shows that the curve must be subdivided into piecewise monotonic sections, the start point must be optimal, and it explains that the 2D-incremental method can find, locally, the global Least Square Distance. Locally means that there are at most three candidate points for a given monotonic direction; therefore the 2D-midpoint method has, locally, at most three measurements. When all the possible measurements are invalid, the midpoint method cannot be applied, and in that case the ultra fast OoC-rule selects the candidate point. This guarantees, for the first time, a 100% stable, ultra-fast, berserkless midpoint algorithm, which can be easily transformed to hardware.
Multicoding Schemes for Interference Channels
Venue: arXiv cs.IT 2015
Year: 2015

The best known inner bound for the 2-user discrete memoryless interference channel is the Han-Kobayashi rate region. The coding schemes that achieve this region are based on rate-splitting and superposition coding. In this paper, we develop a multicoding scheme to achieve the same rate region. A key advantage of the multicoding nature of the proposed coding scheme is that it can be naturally extended to more general settings, such as when encoders have state information or can overhear each other. In particular, we extend our coding scheme to characterize the capacity region of the state-dependent deterministic Z-interference channel when noncausal state information is available at the interfering transmitter. We specialize our results to the case of the linear deterministic model with on/off interference which models a wireless system where a cognitive transmitter is noncausally aware of the times it interferes with a primary transmission. For this special case, we provide an explicit expression for the capacity region and discuss some interesting properties of the optimal strategy. We also extend our multicoding scheme to find the capacity region of the deterministic Z-interference channel when the signal of the interfering transmitter can be overheard at the other transmitter (a.k.a. unidirectional partial cribbing).
Counterexample-Guided Polynomial Loop Invariant Generation by Lagrange Interpolation
Venue: arXiv cs.SE 2015
Year: 2015

We apply multivariate Lagrange interpolation to synthesize polynomial quantitative loop invariants for probabilistic programs. We reduce the computation of an quantitative loop invariant to solving constraints over program variables and unknown coefficients. Lagrange interpolation allows us to find constraints with less unknown coefficients. Counterexample-guided refinement furthermore generates linear constraints that pinpoint the desired quantitative invariants. We evaluate our technique by several case studies with polynomial quantitative loop invariants in the experiments.
FrogWild! -- Fast PageRank Approximations on Graph Engines
Venue: arXiv cs.DC 2015
Year: 2015

We propose FrogWild, a novel algorithm for fast approximation of high PageRank vertices, geared towards reducing network costs of running traditional PageRank algorithms. Our algorithm can be seen as a quantized version of power iteration that performs multiple parallel random walks over a directed graph. One important innovation is that we introduce a modification to the GraphLab framework that only partially synchronizes mirror vertices. This partial synchronization vastly reduces the network traffic generated by traditional PageRank algorithms, thus greatly reducing the per-iteration cost of PageRank. On the other hand, this partial synchronization also creates dependencies between the random walks used to estimate PageRank. Our main theoretical innovation is the analysis of the correlations introduced by this partial synchronization process and a bound establishing that our approximation is close to the true PageRank vector. We implement our algorithm in GraphLab and compare it against the default PageRank implementation. We show that our algorithm is very fast, performing each iteration in less than one second on the Twitter graph and can be up to 7x faster compared to the standard GraphLab PageRank implementation.
Coset codes for communicating over non-additive channels
Venue: arXiv cs.IT 2015
Year: 2015

We present a case for the use of codes possessing algebraic closure properties - coset codes - in developing coding techniques and characterizing achievable rate regions for generic multi-terminal channels. In particular, we consider three diverse communication scenarios - $3-$user interference channel (many-to-many), $3-$user broadcast channel (one-to-many), and multiple access with distributed states (many-to-one) - and identify non-additive examples for which coset codes are analytically proven to yield strictly larger achievable rate regions than those achievable using iid codes. On the one hand, our findings motivate the need for multi-terminal information theory to step beyond iid codes. On the other, it encourages current research of linear code-based techniques to go beyond particular additive communication channels. Detailed proofs of our results are available in [1]-[3].
Community detection in bipartite networks using weighted symmetric binary matrix factorization
Venue: arXiv cs.SI 2015
Year: 2015

In this paper we propose weighted symmetric binary matrix factorization (wSBMF) framework to detect overlapping communities in bipartite networks, which describe relationships between two types of nodes. Our method improves performance by recognizing the distinction between two types of missing edges---ones among the nodes in each node type and the others between two node types. Our method can also explicitly assign community membership and distinguish outliers from overlapping nodes, as well as incorporating existing knowledge on the network. We propose a generalized partition density for bipartite networks as a quality function, which identifies the most appropriate number of communities. The experimental results on both synthetic and real-world networks demonstrate the effectiveness of our method.