We study a generalization of k-center clustering, first introduced by Kavand et. al., where instead of one set of centers, we have two types of centers, p red and q blue, and where each red center is at least α distant from each blue center. The goal is to minimize the covering radius. We provide an approximation algorithm for this problem, and a polynomial-time algorithm for the constrained problem, where all the centers must lie on a line 𝓁.

Predicting if red blood cells (RBC) are infected with the malaria parasite is an important problem in Pathology. Recently, supervised machine learning approaches have been used for this problem, and they have had reasonable success. In particular, state-of-the-art methods such as Convolutional Neural Networks automatically extract increasingly complex feature hierarchies from the image pixels. While such generalized automatic feature extraction methods have significantly reduced the burden of feature engineering in many domains, for niche tasks such as the one we consider in this paper, they result in two major problems. First, they use a very large number of features (that may or may not be relevant) and therefore training such models is computationally expensive. Further, more importantly, the large feature-space makes it very hard to interpret which features are truly important for predictions. Thus, a criticism of such methods is that learning algorithms pose as opaque blackboxes to its users, in this case medical experts. The recommendation of such algorithms can be understood easily, but the reason for their recommendation is not clear. This is the problem of non-interpretability of the model, and the best-performing algorithms are usually the least interpretable. To address these issues, in this paper, we propose an approach to extract a very small number of aggregated features that are easy to interpret and compute, and empirically show that we obtain high prediction accuracy even with a significantly reduced feature-space.

In multi-parameter decision making, data is usually modeled as a set of points whose dimension is the number of parameters, and the skyline or Pareto points represent the possible optimal solutions for various optimization problems. The structure and computation of such points have been well studied, particularly in the database community. As the skyline can be quite large in high dimensions, one often seeks a compact summary. In particular, for a given integer parameter k, a subset of k points is desired which best approximates the skyline under some measure. Various measures have been proposed, but they mostly treat the skyline as a discrete object. By viewing the skyline as a continuous geometric hull, we propose a new measure that evaluates the quality of a subset by the Hausdorff distance of its hull to the full hull. We argue that in many ways our measure more naturally captures what it means to approximate the skyline. For our new geometric skyline approximation measure, we provide a plethora of results. Specifically, we provide (1) a near linear time exact algorithm in two dimensions, (2) APX-hardness results for dimensions three and higher, (3) approximation algorithms for related variants of our problem, and (4) a practical and efficient heuristic which uses our geometric insights into the problem, as well as various experimental results to show the efficacy of our approach.

Efficient multi-criteria decision making often requires looking at a small set of representative objects from a large collection. A recently proposed method for finding representative objects is the k-regret minimizing set (k-RMS problem). Intuitively, given a large set of objects (points) in d dimensions, the goal is to choose a small representative subset, such that for every user preference, there is always an object in the subset whose preference score is not much worse than the score of the k-th most preferred object in the original set. We propose two new efficient approximation algorithms for the k-regret minimizing set problem with provable theoretical guarantees. Our algorithms improve on the space and time complexities of previous approximation algorithms for the k-RMS problem. In addition, we run extensive experiments on real and synthetic data sets showing that simple modifications of our theoretical algorithms run significantly faster than the previous implementations of the k-RMS problem. Finally, we present an efficient approximation algorithm with theoretical guarantees for an extension of the k-RMS problem, which is called the Top-k regret minimizing set problem.

Given a set of n disjoint balls $$b_1, \dots , b_n$$ in $$\mathrm{I\! R}^d$$ , we provide a data structure of near linear size that can answer $$(1\pm {\varepsilon })$$ -approximate kth-nearest neighbor queries on the balls in $$O(\log n + 1/{\varepsilon }^d)$$ time, where k and $${\varepsilon }$$ may be provided at query time. If k and $${\varepsilon }$$ are provided in advance, we provide a data structure to answer such queries requiring O(n / k) space; that is, the data structure requires sublinear space if k is sufficiently large.

In this paper we study the following problem: given a set of m sensors that collectively cover a set of n target points with heterogeneous coverage requirements (target j needs to be covered every fjslots), how to schedule the sensor duty cycles such that all coverage requirements are satisfied and the maximum number of sensors turned on at any time slot is minimized. The problem models varied real-world applications in which sensing tasks exhibit high discrepancy in coverage requirements - critical locations often need to be covered much more frequently. We provide multiple algorithms with best approximation ratio of O (log n + log m) for the maximum number of sensors to turn on, and bi-criteria algorithm with (α, β)-approximation factors with high probability, where the number of sensors turned on is an α = O(δ(log (n) + log(m))/β)-approximation of the optimal (satisfying all requirements) and the coverage requirement is a β-approximation; δ is the approximation ratio achievable in an appropriate instance of set multi-cover. When the sensor coverage exhibits extra geometric properties, the approximation ratios can be further improved. We also evaluated our algorithms via simulations and experiments on a camera testbed. The performance improvement (energy saving) is substantial compared to turning on all sensors all the time, or a random scheduling baseline.

A regret minimizing set Q is a small size representation of a much larger database P so that user queries executed on Q return answers whose scores are not much worse than those on the full dataset. In particular, a k-regret minimizing set has the property that the regret ratio between the score of the top-1 item in Q and the score of the top-k item in P is minimized, where the score of an item is the inner product of the item's attributes with a user's weight (preference) vector. The problem is challenging because we want to find a single representative set Q whose regret ratio is small with respect to all possible user weight vectors. We show that k-regret minimization is NP-Complete for all dimensions d>=3, settling an open problem from Chester et al. [VLDB 2014]. Our main algorithmic contributions are two approximation algorithms, both with provable guarantees, one based on coresets and another based on hitting sets. We perform extensive experimental evaluation of our algorithms, using both real-world and synthetic data, and compare their performance against the solution proposed in [VLDB 14]. The results show that our algorithms are significantly faster and scalable to much larger sets than the greedy algorithm of Chester et al. for comparable quality answers.

We describe an O(n^d) time algorithm for computing the exact probability that two d-dimensional probabilistic point sets are linearly separable, for any fixed d >= 2. A probabilistic point in d-space is the usual point, but with an associated (independent) probability of existence. We also show that the d-dimensional separability problem is equivalent to a (d+1)-dimensional convex hull membership problem, which asks for the probability that a query point lies inside the convex hull of n probabilistic points. Using this reduction, we improve the current best bound for the convex hull membership by a factor of n [Agarwal et al., ESA, 2014]. In addition, our algorithms can handle "input degeneracies" in which more than k+1 points may lie on a k-dimensional subspace, thus resolving an open problem in [Agarwal et al., ESA, 2014]. Finally, we prove lower bounds for the separability problem via a reduction from the k-SUM problem, which shows in particular that our O(n^2) algorithms for 2-dimensional separability and 3-dimensional convex hull membership are nearly optimal.

The Most Likely Voronoi Diagram is a generalization of the well known Voronoi Diagrams to a stochastic setting, where a stochastic point is a point associated with a given probability of existence, and the cell for such a point is the set of points which would classify the given point as its most likely nearest neighbor. We investigate the complexity of this subdivision of space in d dimensions. We show that in the general case, the complexity of such a subdivision is Omega(n^{2d}) where n is the number of points. This settles an open question raised in a recent (ISAAC 2014) paper of Suri and Verbeek, which first defined the Most Likely Voronoi Diagram. We also show that when the probabilities are assigned using a random permutation of a fixed set of values, in expectation the complexity is only ~O(n^{ceil{d/2}}) where the ~O(*) means that logarithmic factors are suppressed. In the worst case, this bound is tight up to polylog factors.

Let P be a set of n uncertain points in Red, where each point pi ∈ P is associated with a real value vi and a probability αi ∈ (0,1] of existence, i.e., each pi exists with an independent probability αi. We present algorithms for building an index on P so that for a d-dimensional query rectangle ρ, the expected maximum value or the most-likely maximum value in ρ can be computed quickly. The specific contributions of our paper include the following: (i) The first index of sub-quadratic size to achieve a sub-linear query time in any dimension d ≥ 1. It also provides a trade-off between query time and size of the index. (ii) A conditional lower bound for the most-likely range-max queries, based on the conjectured hardness of the set-intersection problem, which suggests that in the worst case the product (query time)2 x (index size) is Ω((n2}/polylog(n)). (iii) A linear-size index for estimating the expected range-max value within approximation factor 1/2 in O(logc n) time, for some constant c > 0; that is, if the expected maximum value is μ then the query procedure returns a value μ' with μ/2 ≤ μ' ≤ μ. (iv) Extensions of our algorithm to more general uncertainty models and for computing the top-k values of the range-max.

We investigate what computational tasks can be performed on a point set in R^d, if we are only given black-box access to it via nearest-neighbor search. This is a reasonable assumption if the underlying point set is either provided implicitly, or it is stored in a data structure that can answer such queries. In particular, we show the following: (A) One can compute an approximate bi-criteria k-center clustering of the point set, and more generally compute a greedy permutation of the point set. (B) One can decide if a query point is (approximately) inside the convex-hull of the point set. We also investigate the problem of clustering the given point set, such that meaningful proximity queries can be carried out on the centers of the clusters, instead of the whole point set.

Compaction plays a crucial role in NoSQL systems to ensure a high overall read throughput. In this work, we formally define compaction as an optimization problem that attempts to minimize disk I/O. We prove this problem to be NP-Hard. We then propose a set of algorithms and mathematically analyze upper bounds on worst-case cost. We evaluate the proposed algorithms on real-life workloads. Our results show that our algorithms incur low I/O costs and that a compaction approach using a balanced tree is most preferable.

We investigate the classes of functions whose minimization diagrams can be approximated efficiently in $\mathbb{R}^d$. We present a general framework and a data-structure that can be used to approximate the minimization diagram of such functions. The resulting data-structure has near linear size and can answer queries in logarithmic time. Applications include approximating the Voronoi diagram of multiplicatively weighted points, but the new technique also works for more general distance functions. For example, we get such data-structures for metrics induced by convex bodies, and the nearest furthest-neighbor distance to a set of point sets. Interestingly, our framework also works for distance functions that do not obey the triangle inequality. For many of these functions no near linear size approximation was known before.

For a set of $n$ points in $\mathbb{R}^d$, and parameters $k$ and $\varepsilon$, we present a data structure that answers $(1+\varepsilon,k)$ approximate nearest neighbor queries in logarithmic time. Surprisingly, the space used by the data structure is $\widetilde{O}(n /k)$, where the $\widetilde{O}(\cdot)$ notation here hides terms that are exponential in $d$, roughly varying as $1/\varepsilon^d$; as such, the space used is sublinear in the input size if $k$ is sufficiently large. Our approach provides a novel way to summarize geometric data, such that meaningful proximity queries on the data can be carried out using this sketch. Using this, we provide a sublinear space data structure that can estimate the density of a point set under various measures, including (i) sum of distances of $k$ closest points to the query point and (ii) sum of squared distances of $k$ closest points to the query point. Our approach generalizes to other distance-based estimations of densities of similar flavor. We also study the problem of approximating some of these quantities when using sampling. In particular, we show that a sample of size $\widetilde{O} (n /k)$ is sufficient, in some restricted cases, to estimate the above quantities. Remarkably, the sample size has only linear dependency on the dimension.

We investigate the classes of functions whose minimization diagrams can be approximated efficiently in Red. We present a general framework and a data-structure that can be used to approximate the minimization diagram of such functions. The resulting data-structure has near linear size and can answer queries in logarithmic time. Applications include approximating the Voronoi diagram of (additively or multiplicatively) weighted points. Our technique also works for more general distance functions, such as metrics induced by convex bodies, and the nearest furthest-neighbor distance to a set of point sets. Interestingly, our framework works also for distance functions that do not obey the triangle inequality. For many of these functions no near-linear size approximation was known before.

We study the approximate nearest neighbor problem for metric spaces where the query points are constrained to lie on a subspace of low doubling dimension, while the data is high dimensional. We show that this problem can be solved efficiently despite the high dimensionality of the data.

For a set of n points in Rd, and parameters k and e, we present a data structure that answers (1 + e)-approximate k nearest neighbor queries in logarithmic time. Surprisingly, the space used by the data-structure is Õ(n/k), that is, the space used is sub linear in the input size if k is sufficiently large. Our approach provides a novel way to summarize geometric data, such that meaningful proximity queries on the data can be carried out using this sketch. Using this we provide a sub linear space data-structure that can estimate the density of a point set under various measures, including: (i) sum of distances of k closest points to the query point, and (ii) sum of squared distances of k closest points to the query point. Our approach generalizes to other distance based estimation of densities of similar flavor.

We study the Approximate Nearest Neighbor problem for metric spaces where the query points are constrained to lie on a subspace of low doubling dimension, while the data is high-dimensional. We show that this problem can be solved efficiently despite the high dimensionality of the data.