-
Article
One-Pass Additive-Error Subset Selection for \(\ell _{p}\) Subspace Approximation and (k, p)-Clustering
We consider the problem of subset selection for \(\ell _{p}\) ℓ p ...
-
Chapter and Conference Paper
Minwise-Independent Permutations with Insertion and Deletion of Features
The seminal work of Broder et al. [5] introduces the \(\textrm{minHash}\) minHash ...
-
Article
Variance reduction in feature hashing using MLE and control variate method
The feature hashing algorithm introduced by Weinberger et al. (2009) is a popular dimensionality reduction algorithm that compresses high dimensional data points into low dimensional data points that closely appr...
-
Article
Efficient binary embedding of categorical data using BinSketch
In this work, we present a dimensionality reduction algorithm, aka. sketching, for categorical datasets. Our proposed sketching algorithm Cabin constructs low-dimensional binary sketches from high-dimensional cat...
-
Chapter and Conference Paper
Subspace Approximation with Outliers
The subspace approximation problem with outliers, for given n points in d dimensions \(x_{1}, x_{2}, \dotsc , x_{n} \in \mathbb {R}^{d}\) ...
-
Chapter and Conference Paper
Efficient Compression Technique for Sparse Sets
Recent growth in internet has generated large amount of data over web. Representations of most of such data are high-dimensional and sparse. Many fundamental subroutines of various data analytics tasks such as...
-
Chapter and Conference Paper
Faster Coreset Construction for Projective Clustering via Low-Rank Approximation
In this work, we present a randomized coreset construction for projective clustering, which involves computing a set of k closest j-dimensional linear (affine) subspaces of a given set of n vectors in d dimension...
-
Chapter and Conference Paper
Frequent-Itemset Mining Using Locality-Sensitive Hashing
The Apriori algorithm is a classical algorithm for the frequent itemset mining problem. A significant bottleneck in Apriori is the number of I/O operation involved, and the number of candidates it generates. W...
-
Chapter and Conference Paper
Helly-Type Theorems in Property Testing
Helly’s theorem is a fundamental result in discrete geometry, describing the ways in which convex sets intersect with each other. If S is a set of n points in ℝ d , we say that S
-
Chapter and Conference Paper
Testing uniformity of stationary distribution
In this paper, we prove that for a regular directed graph whether the uniform distribution on the vertices of the graph is a stationary distribution, depends on a local property of the graph, namely if (u, υ) is ...
-
Chapter and Conference Paper
Computing Bits of Algebraic Numbers
We initiate the complexity theoretic study of the problem of computing the bits of (real) algebraic numbers. This extends the work of Yap on computing the bits of transcendental numbers like π, in Logspace.
