OpenRaiser/Intern-Atlas huggingface dataset:
RetiNet: Automatic AMD identification in OCT volumetric data
Venue: arXiv cs.CV 2016
Year: 2016

Optical Coherence Tomography (OCT) provides a unique ability to image the eye retina in 3D at micrometer resolution and gives ophthalmologist the ability to visualize retinal diseases such as Age-Related Macular Degeneration (AMD). While visual inspection of OCT volumes remains the main method for AMD identification, doing so is time consuming as each cross-section within the volume must be inspected individually by the clinician. In much the same way, acquiring ground truth information for each cross-section is expensive and time consuming. This fact heavily limits the ability to acquire large amounts of ground truth, which subsequently impacts the performance of learning-based methods geared at automatic pathology identification. To avoid this burden, we propose a novel strategy for automatic analysis of OCT volumes where only volume labels are needed. That is, we train a classifier in a semi-supervised manner to conduct this task. Our approach uses a novel Convolutional Neural Network (CNN) architecture, that only needs volume-level labels to be trained to automatically asses whether an OCT volume is healthy or contains AMD. Our architecture involves first learning a cross-section pathology classifier using pseudo-labels that could be corrupted and then leverage these towards a more accurate volume-level classification. We then show that our approach provides excellent performances on a publicly available dataset and outperforms a number of existing automatic techniques.
Scheduling of Event-Triggered Networked Control Systems using Timed Game Automata
Venue: arXiv cs.SY 2016
Year: 2016

We discuss the scheduling of a set of networked control systems implemented over a shared communication network. Each control loop is described by a linear-time-invariant (LTI) system with an event-triggered implementation. We assume the network can be used by at most one control loop at any time instant and after each controller update, a pre-defined channel occupancy time elapses before the network is available. In our framework we offer the scheduler two options to avoid conflicts: using the event-triggering mechanism, where the scheduler can choose the triggering coefficient; or forcing controller updates at an earlier pre-defined time. Our objective is avoiding communication conflict while guaranteeing stability of all control loops. We formulate the original scheduling problem as a control synthesis problem over a network of timed game automata (NTGA) with a safety objective. The NTGA is obtained by taking the parallel composition of the timed game automata (TGA) associated with the network and with all control loops. The construction of TGA associated with control loops leverages recent results on the abstraction of timing models of event-triggered LTI systems. In our problem, the safety objective is to avoid that update requests from a control loop happen while the network is in use by another task. We showcase the results in some examples.
Technical Report: Improved Fourier Reconstruction using Jump Information with Applications to MRI
Venue: arXiv cs.NA 2016
Year: 2016

Certain applications such as Magnetic Resonance Imaging (MRI) require the reconstruction of functions from Fourier spectral data. When the underlying functions are piecewise-smooth, standard Fourier approximation methods suffer from the Gibbs phenomenon - with associated oscillatory artifacts in the vicinity of edges and an overall reduced order of convergence in the approximation. This paper proposes an edge-augmented Fourier reconstruction procedure which uses only the first few Fourier coefficients of an underlying piecewise-smooth function to accurately estimate jump information and then incorporate it into a Fourier partial sum approximation. We provide both theoretical and empirical results showing the improved accuracy of the proposed method, as well as comparisons demonstrating superior performance over existing state-of-the-art sparse optimization-based methods. Extensions of the proposed techniques to functions of several variables are also addressed preliminarily. All code used to generate the results in this report are made publicly available.
On Probabilistic Checking in Perfect Zero Knowledge
Venue: arXiv cs.CC 2016
Year: 2016

We present the first constructions of single-prover proof systems that achieve perfect zero knowledge (PZK) for languages beyond NP, under no intractability assumptions: 1. The complexity class #P has PZK proofs in the model of Interactive PCPs (IPCPs) [KR08], where the verifier first receives from the prover a PCP and then engages with the prover in an Interactive Proof (IP). 2. The complexity class NEXP has PZK proofs in the model of Interactive Oracle Proofs (IOPs) [BCS16,RRR16], where the verifier, in every round of interaction, receives a PCP from the prover. Our constructions rely on succinct simulators that enable us to "simulate beyond NP", achieving exponential savings in efficiency over [BCGV16]. These simulators crucially rely on solving a problem that lies at the intersection of coding theory, linear algebra, and computational complexity, which we call the succinct constraint detection problem, and consists of detecting dual constraints with polynomial support size for codes of exponential block length. Our two results rely on solutions to this problem for fundamental classes of linear codes: * An algorithm to detect constraints for Reed--Muller codes of exponential length. * An algorithm to detect constraints for PCPs of Proximity of Reed--Solomon codes [BS08] of exponential degree. The first algorithm exploits the Raz--Shpilka [RS05] deterministic polynomial identity testing algorithm, and shows, to our knowledge, a first connection of algebraic complexity theory with zero knowledge. Along the way, we give a perfect zero knowledge analogue of the celebrated sumcheck protocol [LFKN92], by leveraging both succinct constraint detection and low-degree testing. The second algorithm exploits the recursive structure of the PCPs of Proximity to show that small-support constraints are "locally" spanned by a small number of small-support constraints.
MAC Rate Adaptation and Cross Layer Behavior for Vehicular WiFi Access: An Experimental Study
Venue: arXiv cs.NI 2016
Year: 2016

Vehicular WiFi is different from conventional WiFi access. Firstly, as the connections arise opportunistically, they are short lived and intermittent. Secondly, at vehicular speeds channel conditions change rapidly. Under these conditions, the MAC bit rate adaptation plays a critical role to ensure that devices can maximize throughput performance. The goal of this work is to gain a deeper understanding of current MAC bit rate adaptation algorithms and their interaction with higher layer protocols under vehicular settings. Towards this end, we evaluate the performance of four MAC bit rate adaptation algorithms; SampleRate, AMRR, Minstrel, and RRAA, and their interactions with transport layer protocols such as TCP in real world vehicular settings. Our experimental study reveals that in general these algorithm perform poorly in vehicular settings, and can have an extremely adverse impact on TCP performance.
Super-fast MST Algorithms in the Congested Clique using $o(m)$ Messages
Venue: arXiv cs.DC 2016
Year: 2016

In a sequence of recent results (PODC 2015 and PODC 2016), the running time of the fastest algorithm for the \emph{minimum spanning tree (MST)} problem in the \emph{Congested Clique} model was first improved to $O(\log \log \log n)$ from $O(\log \log n)$ (Hegeman et al., PODC 2015) and then to $O(\log^* n)$ (Ghaffari and Parter, PODC 2016). All of these algorithms use $Θ(n^2)$ messages independent of the number of edges in the input graph. This paper positively answers a question raised in Hegeman et al., and presents the first "super-fast" MST algorithm with $o(m)$ message complexity for input graphs with $m$ edges. Specifically, we present an algorithm running in $O(\log^* n)$ rounds, with message complexity $\tilde{O}(\sqrt{m \cdot n})$ and then build on this algorithm to derive a family of algorithms, containing for any $\varepsilon$, $0 < \varepsilon \le 1$, an algorithm running in $O(\log^* n/\varepsilon)$ rounds, using $\tilde{O}(n^{1 + \varepsilon}/\varepsilon)$ messages. Setting $\varepsilon = \log\log n/\log n$ leads to the first sub-logarithmic round Congested Clique MST algorithm that uses only $\tilde{O}(n)$ messages. Our primary tools in achieving these results are (i) a component-wise bound on the number of candidates for MST edges, extending the sampling lemma of Karger, Klein, and Tarjan (Karger, Klein, and Tarjan, JACM 1995) and (ii) $Θ(\log n)$-wise-independent linear graph sketches (Cormode and Firmani, Dist.~Par.~Databases, 2014) for generating MST candidate edges.
Single Controller Stochastic Games for Optimized Moving Target Defense
Venue: arXiv cs.GT 2016
Year: 2016

Moving target defense (MTD) techniques that enable a system to randomize its configuration to thwart prospective attacks are an effective security solution for tomorrow's wireless networks. However, there is a lack of analytical techniques that enable one to quantify the benefits and tradeoffs of MTDs. In this paper, a novel approach for implementing MTD techniques that can be used to randomize cryptographic techniques and keys in wireless networks is proposed. In particular, the problem is formulated as a stochastic game in which a base station (BS), acting as a defender seeks to strategically change its cryptographic techniques and keys in an effort to deter an attacker that is trying to eavesdrop on the data. The game is shown to exhibit a single-controller property in which only one player, the defender, controls the state of the game. For this game, the existence and properties of the Nash equilibrium are studied, in the presence of a defense cost for using MTD. Then, a practical algorithm for deriving the equilibrium MTD strategies is derived. Simulation results show that the proposed game-theoretic MTD framework can significantly improve the overall utility of the defender, while enabling effective randomization over cryptographic techniques.
POPE: Partial Order Preserving Encoding
Venue: arXiv cs.CR 2016
Year: 2016

Recently there has been much interest in performing search queries over encrypted data to enable functionality while protecting sensitive data. One particularly efficient mechanism for executing such queries is order-preserving encryption/encoding (OPE) which results in ciphertexts that preserve the relative order of the underlying plaintexts thus allowing range and comparison queries to be performed directly on ciphertexts. In this paper, we propose an alternative approach to range queries over encrypted data that is optimized to support insert-heavy workloads as are common in "big data" applications while still maintaining search functionality and achieving stronger security. Specifically, we propose a new primitive called partial order preserving encoding (POPE) that achieves ideal OPE security with frequency hiding and also leaves a sizable fraction of the data pairwise incomparable. Using only O(1) persistent and $O(n^ε)$ non-persistent client storage for $0<ε<1$, our POPE scheme provides extremely fast batch insertion consisting of a single round, and efficient search with O(1) amortized cost for up to $O(n^{1-ε})$ search queries. This improved security and performance makes our scheme better suited for today's insert-heavy databases.
Predicting the dynamics of 2d objects with a deep residual network
Venue: arXiv cs.CV 2016
Year: 2016

We investigate how a residual network can learn to predict the dynamics of interacting shapes purely as an image-to-image regression task. With a simple 2d physics simulator, we generate short sequences composed of rectangles put in motion by applying a pulling force at a point picked at random. The network is trained with a quadratic loss to predict the image of the resulting configuration, given the image of the starting configuration and an image indicating the point of grasping. Experiments show that the network learns to predict accurately the resulting image, which implies in particular that (1) it segments rectangles as distinct components, (2) it infers which one contains the grasping point, (3) it models properly the dynamic of a single rectangle, including the torque, (4) it detects and handles collisions to some extent, and (5) it re-synthesizes properly the entire scene with displaced rectangles.
Truthful Mechanisms for Matching and Clustering in an Ordinal World
Venue: arXiv cs.GT 2016
Year: 2016

We study truthful mechanisms for matching and related problems in a partial information setting, where the agents' true utilities are hidden, and the algorithm only has access to ordinal preference information. Our model is motivated by the fact that in many settings, agents cannot express the numerical values of their utility for different outcomes, but are still able to rank the outcomes in their order of preference. Specifically, we study problems where the ground truth exists in the form of a weighted graph of agent utilities, but the algorithm can only elicit the agents' private information in the form of a preference ordering for each agent induced by the underlying weights. Against this backdrop, we design truthful algorithms to approximate the true optimum solution with respect to the hidden weights. Our techniques yield universally truthful algorithms for a number of graph problems: a 1.76-approximation algorithm for Max-Weight Matching, 2-approximation algorithm for Max k-matching, a 6-approximation algorithm for Densest k-subgraph, and a 2-approximation algorithm for Max Traveling Salesman as long as the hidden weights constitute a metric. We also provide improved approximation algorithms for such problems when the agents are not able to lie about their preferences. Our results are the first non-trivial truthful approximation algorithms for these problems, and indicate that in many situations, we can design robust algorithms even when the agents may lie and only provide ordinal information instead of precise utilities.
Pricing to Maximize Revenue and Welfare Simultaneously in Large Markets
Venue: arXiv cs.GT 2016
Year: 2016

We study large markets with a single seller which can produce many types of goods, and many multi-minded buyers. The seller chooses posted prices for its many items, and the buyers purchase bundles to maximize their utility. For this setting, we consider the following questions: What fraction of the optimum social welfare does a revenue maximizing solution achieve? Are there pricing mechanisms which achieve both good revenue and good welfare simultaneously? To address these questions, we give efficient pricing schemes which are guaranteed to result in both good revenue and welfare, as long as the buyer valuations for the goods they desire have a nice (although reasonable) structure, e.g., that the aggregate buyer demand has a monotone hazard rate or is not too convex. We also show that our pricing schemes have implications for any pricing which achieves high revenue: specifically that even if the seller cares only about revenue, they can still ensure that their prices result in good social welfare without sacrificing profit. Our results holds for general multi-minded buyers in large markets; we also provide improved guarantees for the important special case of unit-demand buyers.
Hierarchical Clustering Given Confidence Intervals of Metric Distances
Venue: arXiv cs.SI 2016
Year: 2016

This paper considers metric spaces where distances between a pair of nodes are represented by distance intervals. The goal is to study methods for the determination of hierarchical clusters, i.e., a family of nested partitions indexed by a resolution parameter, induced from the given distance intervals of the metric spaces. Our construction of hierarchical clustering methods is based on defining admissible methods to be those methods that abide to the axioms of value - nodes in a metric space with two nodes are clustered together at the convex combination of the distance bounds between them - and transformation - when both distance bounds are reduced, the output may become more clustered but not less. Two admissible methods are constructed and are shown to provide universal upper and lower bounds in the space of admissible methods. Practical implications are explored by clustering moving points via snapshots and by clustering networks representing brain structural connectivity using the lower and upper bounds of the network distance. The proposed clustering methods succeed in identifying underlying clustering structures via the maximum and minimum distances in all snapshots, as well as in differentiating brain connectivity networks of patients from those of healthy controls.
Rare Association Rule Mining for Network Intrusion Detection
Venue: arXiv cs.CR 2016
Year: 2016

In this paper, we propose a new practical association rule mining algorithm for anomaly detection in Intrusion Detection System (IDS). First, with a view of anomaly cases being relatively rarely occurred in network packet database, we define a rare association rule among infrequent itemsets rather than the traditional association rule mining method. And then, we discuss an interest measure to catch differences between interesting relations and uninteresting ones, and what interest there is, and develop a hash based rare association rule mining algorithm for finding rare, but useful anomaly patterns to user. Finally, we define a quantitative association rule in relational database, propose a practical algorithm to mine rare association rules from network packet database, and show advantages of it giving a concrete example. Our algorithm can be applied to fields need to mine hidden patterns which are rare, but valuable, like IDS, and it is based on hashing method among infrequent itemsets, so that it has obvious advantages of speed and memory space limitation problems over the traditional association rule mining algorithms. Keywords: rare association mining algorithm, infrequent itemsets, quantitative association rule, network intrusion detection system, anomaly detection
SNR Maximization as a Non-Linear Programming -Towards Optimal Spreading Sequence-
Venue: arXiv cs.IT 2016
Year: 2016

Signal to Noise Ratio (SNR) is an important index for wireless communications. There are many methods for increasing SNR. In CDMA systems, spreading sequences are used. We consider the frequency-selective wide-sense-stationary uncorrelated-scattering (WSSUS) channel and evaluate the worst case of SNR. We construct the non-linear programing for maximizing the lower bound of the average of SNR. This problem becomes the convex programming if we did not take into account the norm constraint. We derive necessary conditions for optimal spreading sequences for the problem.
Tuning Crowdsourced Human Computation
Venue: arXiv cs.HC 2016
Year: 2016

As the use of crowdsourcing increases, it is important to think about performance optimization. For this purpose, it is possible to think about each worker as a HPU(Human Processing Unit), and to draw inspiration from performance optimization on traditional computers or cloud nodes with CPUs. However, as we characterize HPUs in detail for this purpose, we find that there are important differences between CPUs and HPUs, leading to the need for completely new optimization algorithms. In this paper, we study the specific optimization problem of obtaining results fastest for a crowd sourced job with a fixed total budget. In crowdsourcing, jobs are usually broken down into sets of small tasks, which are assigned to workers one at a time. We consider three scenarios of increasing complexity: Identical Round Homogeneous tasks, Multiplex Round Homogeneous tasks, and Multiple Round Heterogeneous tasks. For each scenario, we analyze the stochastic behavior of the HPU clock-rate as a function of the remuneration offered. After that, we develop an optimum Budget Allocation strategy to minimize the latency for job completion. We validate our results through extensive simulations and experiments on Amazon Mechanical Turk.
On Communication Cost vs. Load Balancing in Content Delivery Networks
Venue: arXiv cs.NI 2016
Year: 2016

It is well known that load balancing and low delivery communication cost are two critical issues in mapping requests to servers in Content Delivery Networks (CDNs). However, the trade-off between these two performance metrics has not been yet quantitatively investigated in designing efficient request mapping schemes. In this work, we formalize this trade-off through a stochastic optimization problem. While the solutions to the problem in the extreme cases of minimum communication cost and optimum load balancing can be derived in closed form, finding the general solution is hard to derive. Thus we propose three heuristic mapping schemes and compare the trade-off performance of them through extensive simulations. Our simulation results show that at the expense of high query cost, we can achieve a good trade-off curve. Moreover, by benefiting from the power of multiple choices phenomenon, we can achieve almost the same performance with much less query cost. Finally, we can handle requests with different delay requirements at the cost of degrading network performance.
On Duality Of Multiple Target Tracking and Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

Traditionally, object tracking and segmentation are treated as two separate problems and solved independently. However, in this paper, we argue that tracking and segmentation are actually closely related and solving one should help the other. On one hand, the object track, which is a set of bounding boxes with one bounding box in every frame, would provide strong high-level guidance for the target/background segmentation task. On the other hand, the object segmentation would separate object from other objects and background, which will be useful for determining track locations in every frame. We propose a novel framework which combines online multiple target tracking and segmentation in a video. In our approach, the tracking and segmentation problems are coupled by Lagrange dual decomposition, which leads to more accurate segmentation results and also \emph{helps resolve typical difficulties in multiple target tracking, such as occlusion handling, ID-switch and track drifting}. To track targets, an individual appearance model is learned for each target via structured learning and network flow is employed to generate tracks from densely sampled candidates. For segmentation, multi-label Conditional Random Field (CRF) is applied to a superpixel based spatio-temporal graph in a segment of video to assign background or target labels to every superpixel. The experiments on diverse sequences show that our method outperforms state-of-the-art approaches for multiple target tracking as well as segmentation.
Big Data Analytics in Cloud environment using Hadoop
Venue: arXiv cs.DC 2016
Year: 2016

The Big Data management is a problem right now. The Big Data growth is very high. It is very difficult to manage due to various characteristics. This manuscript focuses on Big Data analytics in cloud environment using Hadoop. We have classified the Big Data according to its characteristics like Volume, Value, Variety and Velocity. We have made various nodes to process the data based on their volume, velocity, value and variety. In this work we have classify the input data and routed to various processing node. At the last after processing from each node, we can combine the output of all nodes to get the final result. We have used Hadoop to partition the data as well as process it.