A Linearly Convergent Algorithm for Support Vector Classification with a Core-set Result.
|
We present a simple, first-order approximation algorithm for the support vector classification
problem. Given a pair of linearly separable data sets and
0 < ε < 1, the proposed algorithm
computes a separating hyperplane whose margin is within a factor of
(1-ε)
of that of the maximum margin separating hyperplane.
We discuss how our algorithm can be extended
to nonlinearly separable and inseparable data sets.
The running time of our algorithm is linear in the size of input and
1/ε. The size of the core-set output by our algorithm is optimal
(within a constant factor).
Furthermore, we establish that our algorithm exhibits linear convergence.
[PDF] (Joint work with Alper Yildirim). (Accepted to INFORMS Journal on Computing, 2010)
|
Practical Nearest Neighbor Search in the Plane.
|
This paper shows that using some very simple practical assumptions,
one can design an algorithm that finds the nearest neighbor
of a given query point
in O(log n) time in theory and faster than the state of the art
in practice.
The algorithm and proof are both simple and the experimental results clearly
show that we can beat the state of the art on most distributions in
two dimensions.
[PDF] (Joint work with Michael Connor). Accepted to Symposium on Experimental Algorithms, 2010.
|
Group Enclosing Queries
|
Given a set of points P (which need to be preprocessed) and a query set Q, a group enclosing
query GEQ fetches the point p* in P such that the maximum
distance of p* to all points in Q is minimized. We give fast approximation algorithms
for the problem which we show to be also effective in practice.
[PDF] (Joint work with Feifei Li and Bin Yao). Accepted to IEEE Transactions on Knowledge and Data Engineering, 2010.
|
Geometric Minimum Spanning Trees with GeoFilterKruskal.
|
Let P be a set of points in Rd. We propose GeoFilterKruskal, an
algorithm that
computes the minimum spanning tree of P using
well separated pair decomposition in combination with a simple
modification of Kruskal's algorithm.
When P is sampled from uniform random distribution,
we show that our algorithm takes one parallel sort
plus a linear number of additional steps, with high probability,
to compute the minimum spanning tree.
Experiments show that our algorithm works better in practice
for most data distributions compared to the current
state of the art. Our algorithm is easy to
parallelize and to our knowledge, is currently the
best practical algorithm on multi-core machines for dimensions
greater than two.
[PDF] (Joint work with Samidh Chatterjee and Michael Connor). (Older Version: FSU Technical Report TR-090731, 2009) Accepted to Symposium on Experimental Algorithms, 2010. Software available at STANN's website.
|
|
Due to their light weight, low power, and practically
unlimited identification capacity,
radio frequency identification (RFID)
tags and associated devices
offer distinctive advantages and
are widely recognized for their promising potential in
context-aware computing; by tagging objects with RFID tags,
the environment can be sensed in
a cost- and energy-efficient means.
However, a prerequisite to fully realizing the potential is
accurate localization of RFID tags, which will enable and enhance
a wide range of applications.
In this paper we show how to exploit the phase difference between two
or more receiving antennas to compute accurate localization.
Phase difference based localization has better accuracy, robustness and sensitivity
when integrated with other measurements compared to the currently popular
technique of localization using received signal strength.
Using a software-defined radio setup, we show
experimental results that support accurate localization
of RFID tags and activity recognition
based on phase difference.
[PDF] (Joint work with Cory Hekimian-Williams, Brandon Grant, Xiuwen Liu and Zhenghao Zhang). Appeared in Proceedings of RFID 2010.
|
|
Finding the k nearest neighbors (kNN) of a query point, or a set
of query points (kNN-Join) are fundamental problems in many database
application. Most of the previous efforts to solve these
problems focused on spatial databases or stand-alone systems, where
changes to the database engine are required, which greatly limits
their application on large data sets that are stored in a relational
database management system. Furthermore, these methods cannot
automatically optimize kNN queries or kNN-Joins when additional
query conditions are specified. In this work, we study both the kNN
query and the kNN-Join in a relational database, possibly augmented
with additional query conditions. We search for relational
algorithms that require no changes to the database engine. The
straightforward solution uses the user-defined-function (UDF) that a
query optimizer cannot optimize. We design algorithms that could be
implemented by SQL operators without changes to the database engine,
hence enabling the query optimizer to understand and generate the
best query plan.
Extensive experiments on large, real and synthetic, data sets confirm
the superior efficiency and practicality of our approach, compared to
the state of the art.
[PDF] (Joint work with Bin Yao and Feifei Li). (Accepted to 26th International Conference on Data Engineering, 2010).
|
|
Given A = { a1,..., am } ⊂ Rn
with corresponding positive weights
W = { w1,..., wm}, the weighted Euclidean
one-center problem, which is a generalization of the minimum enclosing
ball problem,
involves the computation of a point cA
that minimizes the
maximum weighted
Euclidean distance from cA to each
point in A.
In this paper, given ε > 0,
we propose and analyze an algorithm that computes a
(1 + ε)-approximate solution to the weighted Euclidean one-center
problem. The approximation algorithm outputs a core-set for the problem as
well. We also implement our algorithm and show implementation results.
[PDF] (Joint work with Alper Yildirim). (Accepted to Informs Journal on Computing, 2009) Available at Optimization Online.
|
We present a parallel algorithm for k-nearest neighbor
graph construction
that uses Morton ordering.
Experiments show that our approach has the following advantages
over existing methods:
Invited and accepted to IEEE Transactions on Visualization and Computer Graphics, 2009. An earlier version of the paper appeared in Point Based Graphics 2008. Software available at STANN's website.
|
|
We implement an algorithm for
k-clustering for small k in fixed dimensions
and report experimental results here. Although the
theoretical bounds on the running time are hopeless for 1+ε
approximating k-clusters, we note that for
dimensions 2 and 3, k-clustering is practical
for small k ( k ≤ 4 ) and simple enough shapes.
For the purposes of this paper, k is a small
fixed constant.
[PDF] (Joint work with Pankaj Kumar).
|
|
Given a set of points P and a query point q, the
reverse furthest neighbor (RFN) query fetches the set of points
p ε P such that q is their furthest neighbor among all points in
P union q. This is the monochromatic RFN (MRFN) query. Another
interesting version of RFN query is the bichromatic reverse furthest
neighbor (BRFN) query. Given a set of points P, a query set
Q and a query point q ε Q, a BRFN query fetches the set
of points p ε P such that q is the furthest neighbor of p
among all points in Q. The RFN query has many interesting
applications in spatial databases and beyond. For instance, given
a large residential database (as P) and a set of potential sites
(as Q) for building a chemical plant complex, the construction
site should be selected as the one that has the maximum number
of reverse furthest neighbors. This is an instance of the BRFN
query. This paper presents the challenges associated with such
queries and proposes efficient, R-tree based algorithms for both
monochromatic and bichromatic versions of the RFN queries.
[PDF] (Joint work with Bin Yao and Feifei Li).
|
|
This paper presents a method for finding large empty convex bodies
within a 3D scene of polygonal models. The convex bodies we pack are
discrete orientation polytopes (k-dops) with a small number of
facets. The algorithm searches for a large empty k-dop within the
scene, using a combination of random sampling and physical simulation,
allowing the body to grow and interact (via rotation, translation, and
scaling) with the environment when collisions are detected.
We pack multiple empty k-dops in a 3D scene using a greedy
incremental approach, attempting to maximize the volume of each new
body found. We demonstrate the practicality of our method
experimentally, showing that it is fast and that it does
an effective job of packing on a variety of models.
[PDF] (Joint work with Uday Chebrolu and Joe Mitchell). Selected papers of the Sixth International Conference on Computational Science and Applications (ICCSA), IEEE CS, Perugia, Italy. Pages: 382-393, June 2008.
|
|
Given a set of points S = { x1,..., xm } ⊂ Rn and ε>0,
we propose and analyze an algorithm for the problem of computing a (1+ε)-approximation
to the the minimum volume axis-aligned ellipsoid enclosing S. We establish that our
algorithm is polynomial for fixed ε. In addition, the algorithm returns a
small core set X ⊆ S, whose size is independent of the number of points m,
with the property that the minimum volume axis-aligned ellipsoid enclosing X is a
good approximation of the minimum volume axis-aligned ellipsoid enclosing S. Our
computational results indicate that the algorithm exhibits significantly better
performance than that indicated by the theoretical worst-case complexity result.
(Joint work with Alper Yildirim). Journal of Optimization Theory and Applications 136 (2) pp. 211-228 (2008). [ DOI ] [ PDF ]. Also Presented at : Euro-OMS, Euro XXII: [PPT]
|
|
We study the problem of computing
the Minimum Volume Enclosing Ellipsoid (MVEE) containing
a given set of ellipsoids S =
{E1,E2,...,En }⊂ Rd.
We show how to efficiently compute a small set
X ⊆ S of size at most
|X| = O(d2 / ε)
whose minimum volume ellipsoid is an (1+ε)-approximation
to the minimum volume ellipsoid of S. We use an augmented real
number model of computation to achieve a running time of
O(|X|ndω+d3) where
ω < 2.376 is the exponent of matrix multiplication.
This is the best known complexity for solving the MVEE problem when n
is much larger than d, and ε is large.
The algorithm is built on the
previous work by Kumar and Yildirim.
[PDF] (Joint work with Sachin Jambawalikar). Selected papers of the Sixth International Conference on Computational Science and Applications (ICCSA), IEEE CS, Perugia, Italy. Pages: 478-490, June 2008.
|
|
We use projective clustering to design and implement a fast surface
reconstruction algorithm for point clouds that also works well for
sharp edges and corners. Our method relies on
two new approximation algorithms developed and implemented for the
first time, namely, fast projective clustering and parallel dynamic nearest
neighbor searching based on shifted quad-trees. Also, our implementation
is one of the first for this problem with
any kind of guarantees (for a
very restricted type of manifolds). Our algorithm
is easy to parallelize and is external-memory friendly. Finally
we provide a method for combining increasingly more complex fitters in
a cascade which allows planar regions of the point
cloud to be quickly processed while spending more time on high
curvature areas including sharp features. In the domain
of normal estimation, our method is faster and more accurate than
previous systems on a large number of point clouds.
(Joint work with Amit Mhatre) Proceedings of the twenty-second annual symposium on Computational geometry, Sedona, Arizona, USA, 2006. Multimedia abstracts. Pages: 477 - 478. Preliminary version appeared in Fall workshop on Computational Geometry. [ Paper: PDF ]
|
|
We study a class of optimization problems in polygons that seeks to
compute the largest subset of a prescribed type, e.g., a longest
line segment (stick) or a maximum-area triangle or convex body
(potato). Exact polynomial-time algorithms are known for some
of these problems, but their time bounds are high (e.g., O(n7)
for the largest convex polygon in a simple n-gon). We
devise efficient approximation algorithms for these problems. In
particular, we give near-linear time algorithms for a
(1-ε)-approximation of the biggest stick, a
constant factor approximation of the maximum-area convex body, and a
(1-ε)-approximation of the maximum-area fat triangle or
rectangle. In addition, we give efficient methods for computing
large ellipses inside a polygon (whose vertices are a dense sampling
of closed smooth curve). Our algorithms include both deterministic
and randomized methods, one of which has been implemented (for
computing large area ellipses in a well sampled closed smooth
curve).
(Joint work with Olaf Hall-Holt, Matya Katz, Joe Mitchell and Arik Sityon). In Proceedings of SODA 2006. [ Paper: PDF ] [Implementation] [SODA Talk: PPT PDF ]
|
In this paper we study the problem of computing the minimum volume enclosing ellipsoid containing
a given point set  .
Using ``core sets'' and a column generation approach, we develop a
 -approximation algorithm.
We prove the existence of a core set  of size at most
 . We describe an algorithm
that computes the set  and a -approximation
to the minimum volume enclosing ellipsoid of 
in 
operations by using Khachiyan's algorithm to solve each subproblem.
This result is an improvement over the previously known algorithms
especially for input sets with  and reasonably small values
of  . We also discuss extensions to the cases in which the input set
consists of balls or ellipsoids.
Invited talks at: [ Informs ] [ Workshop on Geometric Optimization ] (Joint work with Alper Yildirim). Journal of Optimization Theory and Applications 126 (Vol 1) pp. 1-21 (July 2005). [ PDF ]
|
|
We develop here a cache oblivious voronoi diagram and delaunay triangulation algorithm.
We also develop and implement a simpler divide and conquer based out of core algorithm to
do delaunay triangulations in 2D.
(Joint work with Edgar Ramos) Coming Up
|
We present an algorithm to reconstruct a collection of disjoint smooth closed
curves from noisy samples. Our noise model assumes that the samples are
obtained by first drawing points on the curves according to a locally uniform
distribution followed by a uniform perturbation in the normal directions. Our
reconstruction is faithful with probability at least  , where 
is the number of noisy samples and  is the maximum local feature
size. We expect that our approach can lead to provable algorithms under less
restrictive noise models and for handling non-smooth features.
(Joint work with Siu-Wing Cheng, Stefan Funke, Mordecai Golin, Sheung-Hung Poon and Edgar Ramos) Preliminary version appeared in Proceedings of Symposium on Computational Geometry 2003. Invited to/Accepted in special issue of Computational Geometry - Theory and Applications (CGTA), Vol. 31, Issue 1-2, May 2005, p. 63-100. [ gzipped PS ] [ Latest Version PDF ] [More details]
|
We study the minimum enclosing ball (MEB) problem for sets of points
or balls in high dimensions. Using techniques of second-order cone
programming and ``core-sets'', we have developed
-approximation algorithms that perform well in
practice, especially for very high dimensions, in addition to having
provable guarantees. We prove the existence of core-sets of size
 , improving the previous bound of
 ,
and we study empirically how the core-set size grows with dimension.
We show that our algorithm, which is simple to implement, results in
fast computation of nearly optimal solutions for point sets in much
higher dimension than previously computable using exact techniques.
(Joint work with Joe Mitchell and Alper Yildirim). Proceedings of Alenex 2003, pages 45-55. [ PDF ] [ Alenex Talk PDF ] Also Presented at: [ Euro Informs ] [ Workshop on Geometric Optimization ] Invited to/Accepted in Special issue of Journal of Experimental Algorithmics [Journal Version PDF] [Alenex Version PDF] [More details of the implementation]
|
|
The cache oblivious model is a simple and elegant model to design algorithms
that perform well in hierarchical memory models ubiquitous on current
systems. This model was first formulated in
FLPR99
and has since been a topic of intense research. Analyzing and designing
algorithms and data structures in this model involves not only an
asymptotic analysis of the number of steps executed in terms of the
input size, but also the movement of data optimally among the
different levels of the memory hierarchy.
This chapter is aimed as an introduction to the ``ideal-cache'' model
of
FLPR99
and techniques used to design cache oblivious
algorithms. The chapter also presents some experimental insights
and results.
[Chapter Webpage] © Springer-Verlag 2003 Springer Verlag's Chapter Page. Algorithms for Memory Hierarchies, LNCS 2625, pages 193-212, Springer Verlag. Associated Talk: Cache Oblivious Algorithms: Theory and Practice
|
|
We discuss the issues and challenges in the design of a hand outline
based recognition system. Our system is easier to use, cheaper to
build and more accurate than previous systems.
Extensive tests on more than 700 images collected from 70 people are reported.
Classification, verification and identification of the input images
were done using two simple geometric classifiers. We describe a novel
minimum enclosing ball classifier which performs well for hand recognition
and could be of interest for other applications. The paper uses tricks from
a broad range of areas including computational geometry, image processing,
optimization and machine learning.
(Joint work with Yaroslav Bulatov, Saurabh Sethia, Sachin Jambawalikar) Fall Workshop on Computational Geometry 2002. [ PS ] [ PPT Slides ] [ GRC 2003 ] Best Paper Award in its Category To Appear in Proceedings of International Conference on Biometric Authentication 2004.
|
|
Given a set of points from a smooth surface, how do we create the connections to generate a manifold in 3D?
We give a practical provable algorithm to do so.
Fall Workshop on Computational Geometry 2001. [ PDF ] [ Reviver Web Page ] I also maintain a page on Surface reconstruction [ Link ]
|
|
Given a set of points from a smooth curve, we show using a simple algorithm how to create the connections. (Joint Work with T. K. Dey) Appeared in Symposium on Discrete Algorithms 99. [ PDF ] [ PS ]
|
|
We developed an
algorithm that can triangulate a polygon in near linear time when I was visiting Tata Institute of
Fundamental Research, Bombay in Summer of 99. Our Algorithm is currently based on the shape
complexity(k) of the input polygon and runs in O(nlogk). For instance, k = 1 for the polygon
drawn on the left.
(Joint work with Dr. Subir Ghosh) Technical Report. [ PDF ]
|
