OpenRaiser/Intern-Atlas huggingface dataset:
LIBSVX: A Supervoxel Library and Benchmark for Early Video Processing
Venue: arXiv cs.CV 2015
Year: 2015

Supervoxel segmentation has strong potential to be incorporated into early video analysis as superpixel segmentation has in image analysis. However, there are many plausible supervoxel methods and little understanding as to when and where each is most appropriate. Indeed, we are not aware of a single comparative study on supervoxel segmentation. To that end, we study seven supervoxel algorithms, including both off-line and streaming methods, in the context of what we consider to be a good supervoxel: namely, spatiotemporal uniformity, object/region boundary detection, region compression and parsimony. For the evaluation we propose a comprehensive suite of seven quality metrics to measure these desirable supervoxel characteristics. In addition, we evaluate the methods in a supervoxel classification task as a proxy for subsequent high-level uses of the supervoxels in video analysis. We use six existing benchmark video datasets with a variety of content-types and dense human annotations. Our findings have led us to conclusive evidence that the hierarchical graph-based (GBH), segmentation by weighted aggregation (SWA) and temporal superpixels (TSP) methods are the top-performers among the seven methods. They all perform well in terms of segmentation accuracy, but vary in regard to the other desiderata: GBH captures object boundaries best; SWA has the best potential for region compression; and TSP achieves the best undersegmentation error.
Collapsing Threads Safely with Soft Invariants
Venue: arXiv cs.LO 2015
Year: 2015

Canonical abstraction is a static analysis technique that represents states as 3-valued logical structures, and produces finite abstract systems. Despite providing a finite bound, these abstractions may still suffer from the state explosion problem. Notably, for concurrent programs with arbitrary interleaving, if threads in a state are abstracted based on their location, then the number of locations will be a combinatorial factor in the size of the statespace. We present an approach using canonical abstraction that avoids this state explosion by "collapsing" all of the threads in a state into a single abstract representative. Properties of threads that would be lost by the abstraction, but are needed for verification, are retained by defining conditional "soft invariant" instrumentation predicates. This technique is used to adapt previous models for verifying linearizability of nonblocking concurrent data structure algorithms, resulting in exponentially smaller statespaces.
Finite-time Analysis of the Distributed Detection Problem
Venue: arXiv cs.SY 2015
Year: 2015

This paper addresses the problem of distributed detection in fixed and switching networks. A network of agents observe partially informative signals about the unknown state of the world. Hence, they collaborate with each other to identify the true state. We propose an update rule building on distributed, stochastic optimization methods. Our main focus is on the finite-time analysis of the problem. For fixed networks, we bring forward the notion of Kullback-Leibler cost to measure the efficiency of the algorithm versus its centralized analog. We bound the cost in terms of the network size, spectral gap and relative entropy of agents' signal structures. We further consider the problem in random networks where the structure is realized according to a stationary distribution. We then prove that the convergence is exponentially fast (with high probability), and the non-asymptotic rate scales inversely in the spectral gap of the expected network.
Experiences in Implementing an ICT-Augmented Reality as an Immersive Learning System for a Philippine HEI
Venue: arXiv cs.CY 2015
Year: 2015

This paper presents the experiences in building and implementing a 3D avatar-based virtual world (3D-AVW) as a VLE (3D-AVLE) for the Technological University of the Philippines-Taguig (TUP-T), a higher education institution (HEI) in the Philippines. Free and Open Source Software (FOSS) systems were used, such as the OpenSimulator and various 3D renderers, to create a replica of the TUP-T campus in a simulated 3D world. The 3D-AVLE runs in a single server that is connected to the learners' computers via a simply-wired local area network (LAN). The use of various networking optimization techniques was experimented on to provide the learners and the instructors alike a seamless experience and lag-less immersion within the 3D-AVLE. With the current LAN setup in TUP-T, the optimal number of concurrent users that can be accommodated without sacrificing connectivity and the quality of virtual experience was found to be at 30 users, exactly the mean class size in TUP-T. The 3D-AVLE allows for recording of the learners' experiences which provides the learners a facility to review the lessons at a later time. Classes in fundamental topics in engineering sciences were conducted using the usual teaching aid technologies such as the presentation software, and by dragging-and-dropping the presentation files to the 3D-AVLE, resulting to increased learning curve by both the instructors and the learners.
Robust Detection of Intensity Variant Clones in Forged and JPEG Compressed Images
Venue: arXiv cs.CV 2015
Year: 2015

Digitization of images has made image editing easier. Ease of image editing tempted users and professionals to manipulate digital images leading to digital image forgeries. Today digital image forgery has posed a great threat to the authenticity of the popular digital media, the digital images. A lot of research is going on worldwide to detect image forgery and to separate the forged images from their authentic counterparts. This paper provides a novel intensity invariant detection model (IIDM) for detection of intensity variant clones that is robust against JPEG compression, noise attacks and blurring.
Ultrafast a Distributed Arithmetic in multi-row codes
Venue: arXiv cs.NA 2015
Year: 2015

In this paper we consider the matrix structure of arithmetic processors based on distributed arithmetic in multi-row codes. Scope - development of supercomputers.
Near-Optimal Hybrid Analog and Digital Precoding for Downlink mmWave Massive MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

Millimeter wave (mmWave) massive MIMO can achieve orders of magnitude increase in spectral and energy efficiency, and it usually exploits the hybrid analog and digital precoding to overcome the serious signal attenuation induced by mmWave frequencies. However, most of hybrid precoding schemes focus on the full-array structure, which involves a high complexity. In this paper, we propose a near-optimal iterative hybrid precoding scheme based on the more realistic subarray structure with low complexity. We first decompose the complicated capacity optimization problem into a series of ones easier to be handled by considering each antenna array one by one. Then we optimize the achievable capacity of each antenna array from the first one to the last one by utilizing the idea of successive interference cancelation (SIC), which is realized in an iterative procedure that is easy to be parallelized. It is shown that the proposed hybrid precoding scheme can achieve better performance than other recently proposed hybrid precoding schemes, while it also enjoys an acceptable computational complexity.
Wireless Coverage Area Computation and Optimization
Venue: arXiv cs.NI 2015
Year: 2015

A wireless network's design must include the optimization of the area of coverage of its wireless transmitters - mobile and base stations in cellular networks, wireless access points in WLANs, or nodes on a transmit schedule in a wireless ad-hoc network. Typically, the coverage optimization for the common channels is solved by spatial multiplexing, i.e. keeping the access networks far apart. However, with increasing densities of wireless network deployments (including the Internet-of-Things) and paucity of spectrum, and new developments like whitespace devices and self-organizing, cognitive networks, there is a need to manage interference and optimize coverage by efficient algorithms that correctly set the transmit powers to ensure that transmissions only use the power necessary. In this work we study methods for computing and optimizing interference-limited coverage maps of a set of transmitters. We progress successively through increasingly realistic network scenarios. We begin with a disk model with a fixed set of transmitters and present an optimal algorithm for computing the coverage map. We then enhance the model to include updates to the network, in the form of addition or deletion of one transmitter. In this dynamic setting, we present an optimal algorithm to maintain updates to the coverage map. We then move to a more realistic interference model - the SINR model. For the SINR model we first show geometric bases for coverage maps. We then present a method to approximate the measure of the coverage area. Finally, we present an algorithm that uses this measure to optimize the coverage area with minimum total transmit power.
On the Role of Triadic Substructures in Complex Networks
Venue: arXiv cs.SI 2015
Year: 2015

In the course of the growth of the Internet and due to increasing availability of data, over the last two decades, the field of network science has established itself as an own area of research. With quantitative scientists from computer science, mathematics, and physics working on datasets from biology, economics, sociology, political sciences, and many others, network science serves as a paradigm for interdisciplinary research. One of the major goals in network science is to unravel the relationship between topological graph structure and a network's function. As evidence suggests, systems from the same fields, i.e. with similar function, tend to exhibit similar structure. However, it is still vague whether a similar graph structure automatically implies likewise function. This dissertation aims at helping to bridge this gap, while particularly focusing on the role of triadic structures. After a general introduction to the main concepts of network science, existing work devoted to the relevance of triadic substructures is reviewed. A major challenge in modeling such structure is the fact that not all three-node subgraphs can be specified independently of each other, as pairs of nodes may participate in multiple triadic subgraphs. In order to overcome this obstacle, a novel class of generative network models based on pair-disjoint triadic building blocks is suggested. It is further investigated whether triad motifs - subgraph patterns which appear significantly more frequently than expected at random - occur homogeneously or heterogeneously distributed over graphs. Finally, the influence of triadic substructure on the evolution of dynamical processes acting on their nodes is studied. It is observed that certain motifs impose clear signatures on the systems' dynamics, even when embedded in a larger network structure.
Analysis of the modernization prospects of the WLCG monitoring framework's messaging subsystem
Venue: arXiv cs.DC 2015
Year: 2015

The purpose of the project is an analysis of the modernization prospects of the WLCG monitoring framework's messaging subsystem based on Nagios monitoring software and Apache ActiveMQ technologies. The modernization process demands thorough examination of the existing subsystem to determine the vital upgrade requirements. Thus the work is focused on research of the main underlying technologies, the existing subsystem's structure and revision of its design and used software.
A Hybrid Approach to Word Sense Disambiguation Combining Supervised and Unsupervised Learning
Venue: arXiv cs.CL 2015
Year: 2015

In this paper, we are going to find meaning of words based on distinct situations. Word Sense Disambiguation is used to find meaning of words based on live contexts using supervised and unsupervised approaches. Unsupervised approaches use online dictionary for learning, and supervised approaches use manual learning sets. Hand tagged data are populated which might not be effective and sufficient for learning procedure. This limitation of information is main flaw of the supervised approach. Our proposed approach focuses to overcome the limitation using learning set which is enriched in dynamic way maintaining new data. Trivial filtering method is utilized to achieve appropriate training data. We introduce a mixed methodology having Modified Lesk approach and Bag-of-Words having enriched bags using learning methods. Our approach establishes the superiority over individual Modified Lesk and Bag-of-Words approaches based on experimentation.
Lower bounds on the Deterministic and Quantum Communication Complexity of Hamming Distance
Venue: arXiv cs.CC 2015
Year: 2015

Alice and Bob want to know if two strings of length n are almost equal. That is, do they differ on \textit{at most} a bits? Let 0\leq a\leq n-1. We show that any deterministic protocol, as well as any error-free quantum protocol (C* version), for this problem requires at least n-2 bits of communication. We show the same bounds for the problem of determining if two strings differ in exactly a bits. We also prove a lower bound of n/2-1 for error-free Q* quantum protocols. Our results are obtained by lower-bounding the ranks of the appropriate matrices.
Collaborative OLAP with Tag Clouds: Web 2.0 OLAP Formalism and Experimental Evaluation
Venue: arXiv cs.DB 2016
Year: 2016

Increasingly, business projects are ephemeral. New Business Intelligence tools must support ad-lib data sources and quick perusal. Meanwhile, tag clouds are a popular community-driven visualization technique. Hence, we investigate tag-cloud views with support for OLAP operations such as roll-ups, slices, dices, clustering, and drill-downs. As a case study, we implemented an application where users can upload data and immediately navigate through its ad hoc dimensions. To support social networking, views can be easily shared and embedded in other Web sites. Algorithmically, our tag-cloud views are approximate range top-k queries over spontaneous data cubes. We present experimental evidence that iceberg cuboids provide adequate online approximations. We benchmark several browser-oblivious tag-cloud layout optimizations.
Breaking an image encryption algorithm based on chaos
Venue: arXiv cs.CR 2016
Year: 2016

Recently, a chaos-based image encryption algorithm called MCKBA (Modified Chaotic-Key Based Algorithm) was proposed. This paper analyzes the security of MCKBA and finds that it can be broken with a differential attack, which requires only four chosen plain-images. Performance of the attack is verified by experimental results. In addition, some defects of MCKBA, including insensitivity with respect to changes of plain-image/secret key, are reported.
Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems
Venue: arXiv cs.DS 2016
Year: 2016

We study the stochastic versions of a broad class of combinatorial problems where the weights of the elements in the input dataset are uncertain. The class of problems that we study includes shortest paths, minimum weight spanning trees, and minimum weight matchings, and other combinatorial problems like knapsack. We observe that the expected value is inadequate in capturing different types of {\em risk-averse} or {\em risk-prone} behaviors, and instead we consider a more general objective which is to maximize the {\em expected utility} of the solution for some given utility function, rather than the expected weight (expected weight becomes a special case). Under the assumption that there is a pseudopolynomial time algorithm for the {\em exact} version of the problem (This is true for the problems mentioned above), we can obtain the following approximation results for several important classes of utility functions: (1) If the utility function $\uti$ is continuous, upper-bounded by a constant and $\lim_{x\rightarrow+\infty}\uti(x)=0$, we show that we can obtain a polynomial time approximation algorithm with an {\em additive error} $ε$ for any constant $ε>0$. (2) If the utility function $\uti$ is a concave increasing function, we can obtain a polynomial time approximation scheme (PTAS). (3) If the utility function $\uti$ is increasing and has a bounded derivative, we can obtain a polynomial time approximation scheme. Our results recover or generalize several prior results on stochastic shortest path, stochastic spanning tree, and stochastic knapsack. Our algorithm for utility maximization makes use of the separability of exponential utility and a technique to decompose a general utility function into exponential utility functions, which may be useful in other stochastic optimization problems.
Maximizing Non-monotone Submodular Set Functions Subject to Different Constraints: Combined Algorithms
Venue: arXiv cs.DS 2016
Year: 2016

We study the problem of maximizing constrained non-monotone submodular functions and provide approximation algorithms that improve existing algorithms in terms of either the approximation factor or simplicity. Our algorithms combine existing local search and greedy based algorithms. Different constraints that we study are exact cardinality and multiple knapsack constraints. For the multiple-knapsack constraints we achieve a $(0.25-2ε)$-factor algorithm. We also show, as our main contribution, how to use the continuous greedy process for non-monotone functions and, as a result, obtain a $0.13$-factor approximation algorithm for maximization over any solvable down-monotone polytope. The continuous greedy process has been previously used for maximizing smooth monotone submodular function over a down-monotone polytope \cite{CCPV08}. This implies a 0.13-approximation for several discrete problems, such as maximizing a non-negative submodular function subject to a matroid constraint and/or multiple knapsack constraints.
A Unified Framework for Approximating and Clustering Data
Venue: arXiv cs.LG 2016
Year: 2016

Given a set $F$ of $n$ positive functions over a ground set $X$, we consider the problem of computing $x^*$ that minimizes the expression $\sum_{f\in F}f(x)$, over $x\in X$. A typical application is \emph{shape fitting}, where we wish to approximate a set $P$ of $n$ elements (say, points) by a shape $x$ from a (possibly infinite) family $X$ of shapes. Here, each point $p\in P$ corresponds to a function $f$ such that $f(x)$ is the distance from $p$ to $x$, and we seek a shape $x$ that minimizes the sum of distances from each point in $P$. In the $k$-clustering variant, each $x\in X$ is a tuple of $k$ shapes, and $f(x)$ is the distance from $p$ to its closest shape in $x$. Our main result is a unified framework for constructing {\em coresets} and {\em approximate clustering} for such general sets of functions. To achieve our results, we forge a link between the classic and well defined notion of $\varepsilon$-approximations from the theory of PAC Learning and VC dimension, to the relatively new (and not so consistent) paradigm of coresets, which are some kind of "compressed representation" of the input set $F$. Using traditional techniques, a coreset usually implies an LTAS (linear time approximation scheme) for the corresponding optimization problem, which can be computed in parallel, via one pass over the data, and using only polylogarithmic space (i.e, in the streaming model). We show how to generalize the results of our framework for squared distances (as in $k$-mean), distances to the $q$th power, and deterministic constructions.
Approximate Aggregate Utility Maximization in Multi-Hop Wireless Networks using Distributed Greedy Scheduling
Venue: arXiv cs.NI 2016
Year: 2016

In this paper, we study the performance of greedy scheduling in multihop wireless networks, where the objective is aggregate utility maximization. Following standard approaches, we consider the dual of the original optimization problem. The dual can be solved optimally, only with the knowledge of the maximal independent sets in the network. But computation of maximal independent sets is known to be NP-hard. Motivated by this, we propose a distributed greedy heuristic to address the problem of link scheduling. We evaluate the effect of the distributed greedy heuristic on aggregate utility maximization in detail, for the case of an arbitrary graph. We provide some insights into the factors affecting aggregate utility maximization in a network, by providing bounds on the same. We give simulation results for the approximate aggregate utility maximization achieved under distributed implementation of the greedy heuristic and find them close to the maximum aggregate utility obtained using optimal scheduling.
A Generalization of Multiple Choice Balls-into-Bins: Tight Bounds
Venue: arXiv cs.DM 2016
Year: 2016

This paper investigates a general version of the multiple choice model called the $(k,d)$-choice process in which $n$ balls are assigned to $n$ bins. In the process, $k<d$ balls are placed into $k$ least loaded out of $d$ bins chosen independently and uniformly at random in each of $\frac{n}{k}$ rounds. The primary goal is to derive tight bounds on the maximum bin load for $(k,d)$-choice for any $1 \leq k < d \leq n$. Our results enable one to choose suitable parameters $k$ and $d$ for which the $(k,d)$-choice process achieves the optimal tradeoff between the maximum bin load and message cost: a constant maximum load and $2n$ messages. It is also shown that the maximum load for a heavily loaded case, in which $m>n$ balls are placed into $n$ bins, if $d \geq 2k$. Potential applications are also discussed such as distributed storage as well as parallel job scheduling in a cluster.
Faster and Simpler Width-Independent Parallel Algorithms for Positive Semidefinite Programming
Venue: arXiv cs.DS 2016
Year: 2016

This paper studies the problem of finding an $(1+ε)$-approximate solution to positive semidefinite programs. These are semidefinite programs in which all matrices in the constraints and objective are positive semidefinite and all scalars are non-negative. We present a simpler \NC parallel algorithm that on input with $n$ constraint matrices, requires $O(\frac{1}{ε^3} log^3 n)$ iterations, each of which involves only simple matrix operations and computing the trace of the product of a matrix exponential and a positive semidefinite matrix. Further, given a positive SDP in a factorized form, the total work of our algorithm is nearly-linear in the number of non-zero entries in the factorization.
The Complexity of Controlling Candidate-Sequential Elections
Venue: arXiv cs.GT 2016
Year: 2016

Candidate control of elections is the study of how adding or removing candidates can affect the outcome. However, the traditional study of the complexity of candidate control is in the model in which all candidates and votes are known up front. This paper develops a model for studying online control for elections where the structure is sequential with respect to the candidates, and in which the decision regarding adding and deleting must be irrevocably made at the moment the candidate is presented. We show that great complexity---PSPACE-completeness---can occur in this setting, but we also provide within this setting polynomial-time algorithms for the most important of election systems, plurality.