Amirali Abdullah
PhD student graduated Fall 2015


Book Chapter  Journal  Conference  Workshop  Tech Report]

Journal

2016

  • Streaming Verification of Graph Properties. (Project Website)
    By Amirali Abdullah,   Samira Daruki,   Chitradeep Dutta Roy,   Suresh Venkatasubramanian,   
    Vol.abs/1602.08162, CoRR (CORR 2016),  2016.
    Abstract
  • 2015

  • Sketching, Embedding, and Dimensionality Reduction for Information Spaces. (Project Website)
    By Amirali Abdullah,   Ravi Kumar ,   Andrew McGregor ,   Sergei Vassilvitskii,   Suresh Venkatasubramanian,   
    Vol.abs/1503.05225, CoRR (CORR 2015),  2015.
    Abstract
  • Conference

    2016

  • Sketching, Embedding and Dimensionality Reduction in Information Theoretic Spaces. (Project Website)
    By Amirali Abdullah,   Ravi Kumar ,   Andrew McGregor ,   Sergei Vassilvitskii,   Suresh Venkatasubramanian,   
    In Proceedings of AISTATS (AISTATS 2016),  pages 948-956,  2016.
    Abstract
  • Streaming Verification of Graph Properties. (Project Website)
    By Amirali Abdullah,   Samira Daruki,   Chitradeep Dutta Roy,   Suresh Venkatasubramanian,   
    In Proceedings of ISAAC (ISAAC 2016),  pages 3:1-3:14,  2016.
    Abstract
  • 2013

  • Range Counting Coresets for Uncertain Data
    By Amirali Abdullah,    Samira Daruki,    and Jeff M. Phillips
    (To Appear) In Proceedings of 29th Annual ACM Symposium on Computational Geometry (SOCG),  pages ??-??,  June,  2013.
    Abstract

    We study coresets for various types of range counting queries on uncertain data. In our model each uncertain point has a probability density describing its location, sometimes defined as k distinct locations. Our goal is to construct a subset of the uncertain points, including their locational uncertainty, so that range counting queries can be answered by just examining this subset. We study three distinct types of queries. RE queries return the expected number of points in a query range. RC queries return the number of points in the range with probability at least a threshold. RQ queries returns the probability that fewer than some threshold fraction of the points are in the range. In both RC and RQ coresets the threshold is provided as part of the query. And for each type of query we provide coreset constructions with approximation-size tradeoffs. We show that random sampling can be used to construct each type of coreset, and we also provide significantly improved bounds using discrepancy-based approaches on axis-aligned range queries.

  • 2012

  • Approximate bregman near neighbors in sublinear time: beyond the triangle inequality
    By Amirali Abdullah,    John Moeller,    Suresh Venkatasubramanian
    In Proceedings of ACM Symposium on Computational Geometry (SOCG),  pages 31-40,  June,  2012.
    Abstract
  • Tech Report

    2014

  • A directed isoperimetric inequality with application to Bregman near neighbor lower bounds (Project Website)
    By Amirali Abdullah,    Suresh Venkatasubramanian
    ,  April,  2014.
    Abstract

    Bregman divergences Dϕ are a class of divergences parametrized by a convex function ϕ and include well known distance functions like ℓ22 and the Kullback-Leibler divergence. There has been extensive research on algorithms for problems like clustering and near neighbor search with respect to Bregman divergences; in all cases, the algorithms depend not just on the data size n and dimensionality d, but also on a structure constant μ≥1 that depends solely on ϕ and can grow without bound independently. In this paper, we provide the first evidence that this dependence on μ might be intrinsic. We focus on the problem of approximate near neighbor search for Bregman divergences. We show that under the cell probe model, any non-adaptive data structure (like locality-sensitive hashing) for c-approximate near-neighbor search that admits r probes must use space Ω(n1+μcr). In contrast, for LSH under ℓ1 the best bound is Ω(n1+1cr). Our new tool is a directed variant of the standard boolean noise operator. We show that a generalization of the Bonami-Beckner hypercontractivity inequality exists “in expectation” or upon restriction to certain subsets of the Hamming cube, and that this is sufficient to prove the desired isoperimetric inequality that we use in our data structure lower bound. We also present a structural result reducing the Hamming cube to a Bregman cube. This structure allows us to obtain lower bounds for problems under Bregman divergences from their ℓ1 analog. In particular, we get a (weaker) lower bound for approximate near neighbor search of the form Ω(n1+1cr) for an r-query non-adaptive data structure, and new cell probe lower bounds for a number of other near neighbor questions in Bregman space.