@INPROCEEDINGS{bjks03svc, author = {Y.~Bulatov and S.~Jambawalikar and P.~Kumar and S.~Sethia.}, title = {Hand recognition using geometric classifiers.}, booktitle = {Proceedings of International Conference on Biometric Authentication}, year = {2004}, volume = {3072}, series = {Lecture Notes Comput. Sci.}, pages = {753--759}, publisher = {Springer-Verlag} } @INCOLLECTION{mst10, author = {Chatterjee, Samidh and Connor, Michael and Kumar, Piyush}, title = {Geometric Minimum Spanning Trees with GeoFilterKruskal}, booktitle = {Experimental Algorithms}, publisher = {Springer Berlin / Heidelberg}, year = {2010}, editor = {Festa, Paola}, volume = {6049}, series = {Lecture Notes in Computer Science}, pages = {486-500}, abstract = {Let P be a set of points in d . 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 Kruskals 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 ur algorithm is easy to parallelize and to our knowledge, is currently the best practical algorithm on multi-core machines for d>2.}, affiliation = {Florida State University Department of Computer Science Tallahassee FL 32306-4530}, } @ARTICLE{10.1109/ICCSA.2008.25, author = {Uday Chebrolu and Piyush Kumar and Joseph S.B. Mitchell}, title = {On Finding Large Empty Convex Bodies in 3D Scenes of Polygonal Models}, journal = {iccsa}, year = {2008}, volume = {0}, pages = {382-393}, address = {Los Alamitos, CA, USA}, doi = {http://doi.ieeecomputersociety.org/10.1109/ICCSA.2008.25}, isbn = {978-0-7695-3243-1}, publisher = {IEEE Computer Society} } @INPROCEEDINGS{cfg-crns-03, author = {S. W. Cheng and S. Funke and M. Golin and P. Kumar and S. Poon and E. Ramos}, title = {Curve Reconstruction from Noisy Samples}, booktitle = {Proc. 19th Annual ACM Symposium on Computational Geometry}, year = {2003}, pages = {302--311}, site = {San Diego} } @INCOLLECTION{nn2d10, author = {Connor, Michael and Kumar, Piyush}, title = {Practical Nearest Neighbor Search in the Plane}, booktitle = {Experimental Algorithms}, publisher = {Springer Berlin / Heidelberg}, year = {2010}, editor = {Festa, Paola}, volume = {6049}, series = {Lecture Notes in Computer Science}, pages = {501-512}, abstract = {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 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.}, affiliation = {Florida State University Department of Computer Science Tallahassee FL 32306-4530}, } @ARTICLE{10.1109/TVCG.2010.9, author = {Michael Connor and Piyush Kumar}, title = {Fast Construction of k-Nearest Neighbor Graphs for Point Clouds}, journal = {IEEE Transactions on Visualization and Computer Graphics}, year = {2010}, volume = {16}, pages = {599-608}, number = {4}, address = {Los Alamitos, CA, USA}, doi = {http://doi.ieeecomputersociety.org/10.1109/TVCG.2010.9}, issn = {1077-2626}, publisher = {IEEE Computer Society} } @INPROCEEDINGS{connor08ann, author = {Michael Connor and Piyush Kumar}, title = {Parallel Construction of k-Nearest Neighbor Graphs for Point Clouds}, booktitle = {Proceedings of Volume and Point-Based Graphics. }, year = {2008}, pages = {25--32}, month = Aug, publisher = {IEEE VGTC} } @INPROCEEDINGS{dk-nnc-99, author = {T. K. Dey and P. Kumar}, title = {A simple provable algorithm for curve reconstruction.}, booktitle = {Proc. 10th Annual ACM-SIAM Symposium on Discrete Algogrithms.}, year = {1999}, pages = {893--894}, update = {00.04 kumar} } @INPROCEEDINGS{1109610, author = {Olaf Hall-Holt and Matthew J. Katz and Piyush Kumar and Joseph S. B. Mitchell and Arik Sityon}, title = {Finding large sticks and potatoes in polygons}, booktitle = {SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm}, year = {2006}, pages = {474--483}, address = {New York, NY, USA}, publisher = {ACM Press}, doi = {http://doi.acm.org/10.1145/1109557.1109610}, isbn = {0-89871-605-5}, location = {Miami, Florida} } @INPROCEEDINGS{5467268, author = {Hekimian-Williams, C. and Grant, B. and Xiuwen Liu and Zhenghao Zhang and Kumar, P.}, title = {Accurate localization of RFID tags using phase difference}, year = {2010}, pages = {89 -96}, month = {apr.}, abstract = {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.}, doi = {10.1109/RFID.2010.5467268}, journal = {RFID, 2010 IEEE International Conference on}, keywords = {RFID tags localization;activity recognition;context-aware computing;phase difference;radio frequency identification tags;received signal strength;software-defined radio setup;radiofrequency identification;software radio;} } @ARTICLE{10.1109/ICCSA.2008.24, author = {Sachin Jambawalikar and Piyush Kumar}, title = {A Note on Approximate Minimum Volume Enclosing Ellipsoid of Ellipsoids}, journal = {International Conference on Computational Sciences and Its Applications}, year = {2008}, volume = {0}, pages = {478-487}, address = {Los Alamitos, CA, USA}, doi = {http://doi.ieeecomputersociety.org/10.1109/ICCSA.2008.24}, isbn = {978-0-7695-3243-1}, publisher = {IEEE Computer Society} } @INPROCEEDINGS{k-coa-03, author = {P. Kumar}, title = {Cache Oblivious Algorithms}, booktitle = {Algorithms for Memory Hierarchies, LNCS 2625}, year = {2003}, editor = {U. Meyer and P. Sanders and J. Sibeyn}, pages = {193--212}, publisher = {Springer-Verlag}, url = {http://link.springer.de/link/service/series/0558/tocs/t2625.htm} } @PHDTHESIS{p-crld-04, author = {P. Kumar}, title = {Clustering and Reconstructing Large Data Sets}, school = {Dept. Comput. Sci., Stony Brook Univ.}, year = {2004}, type = {Ph.{D}. Thesis}, address = {New York, NY}, month = jun, keywords = {doctoral thesis} } @ARTICLE{kk10, author = {P.~Kumar and P.~Kumar}, title = {Almost optimal solutions to k-clustering problems}, journal = {International Journal of Computational Geometry and Applications}, year = {2010}, volume = {20}, issue = {4}, pages = {431--447}, note = {To Appear} } @ARTICLE{kmy-ameb-03, author = {P. Kumar and J. S. B. Mitchell and A. Y{\i}ld{\i}r{\i}m}, title = {Approximate minimum enclosing balls in high dimensions using core-sets}, journal = {The ACM Journal of Experimental Algorithmics}, year = {2003}, volume = {8}, publisher = {ACM}, url = {http://www.compgeom.com/meb/} } @INPROCEEDINGS{kmy-meb-03, author = {P. Kumar and J. S. B. Mitchell and A. Y{\i}ld{\i}r{\i}m}, title = {Computing Core-Sets and Approximate Smallest Enclosing HyperSpheres in High Dimensions}, booktitle = {Algorithm Engineering and Experimentation (Proc. ALENEX~'03)}, year = {2003}, series = {Lecture Notes Comput. Sci.}, pages = {45--55}, publisher = {Springer-Verlag}, url = {http://www.compgeom.com/meb/} } @UNPUBLISHED{kr-iecv-03, author = {P. Kumar and E. Ramos}, title = {I/O Efficient Construction of Voronoi diagrams.}, note = {Unpublished manuscript}, month = jul, year = {2002}, update = {03. kumar} } @ARTICLE{PiyushKumar04072009, author = {Kumar, Piyush and Yildirim, E. Alper}, title = {{An Algorithm and a Core Set Result for the Weighted Euclidean One-Center Problem}}, journal = {INFORMS JOURNAL ON COMPUTING}, year = {2009}, pages = {ijoc.1080.0315}, abstract = {Given a set [A] of m points in n-dimensional space with corresponding positive weights, the weighted Euclidean one-center problem, which is a generalization of the minimum enclosing ball problem, involves the computation of a point c[A] [isin] [R]n that minimizes the maximum weighted Euclidean distance from c[A] to each point in [A]. In this paper, given {epsilon} > 0, we propose and analyze an algorithm that computes a (1 + {epsilon})-approximate solution to the weighted Euclidean one-center problem. Our algorithm explicitly constructs a small subset [X] [subE] [A], called an {epsilon}-core set of [A], for which the optimal solution of the corresponding weighted Euclidean one-center problem is a close approximation to that of [A]. In addition, we establish that |[X]| depends only on {epsilon} and on the ratio of the smallest and largest weights, but is independent of the number of points m and the dimension n. This result subsumes and generalizes the previously known core set results for the minimum enclosing ball problem. Our algorithm computes a (1 + {epsilon})-approximate solution to the weighted Euclidean one-center problem for [A] in [O] (mn|[X]|) arithmetic operations. Our computational results indicate that the size of the {epsilon}-core set computed by the algorithm is, in general, significantly smaller than the theoretical worst-case estimate, which contributes to the efficiency of the algorithm, especially for large-scale instances. We shed some light on the possible reasons for this discrepancy between the theoretical estimate and the practical performance.}, doi = {10.1287/ijoc.1080.0315}, url = {http://joc.journal.informs.org/cgi/content/abstract/ijoc.1080.0315v1} } @ARTICLE{ky-aamve-08, author = {P. Kumar and A. Y{\i}ld{\i}r{\i}m}, title = {Computing Minimum Volume Enclosing Axis-Aligned Ellipsoids.}, journal = {Journal of Optimization Theory and Applications}, year = {2008}, volume = {136}, pages = {211--228}, number = {2}, update = {04.08 piyush} } @ARTICLE{ky-mve-04, author = {P. Kumar and A. Y{\i}ld{\i}r{\i}m}, title = {Minimum volume enclosing ellipsoids and core sets}, journal = {Journal of Optimization Theory and Applications}, year = {2005}, volume = {126}, pages = {1--21}, number = {1}, update = {04.08 piyush} } @ARTICLE{kysvm10, author = {P.~Kumar and E.~A.~Y{\i}ld{\i}r{\i}m}, title = {A Linearly Convergent Algorithm for Support Vector Classification with a Core-set Result}, journal = {INFORMS Journal on Computing}, year = {2010}, note = {To Appear} } @ARTICLE{lyk10, author = {F. Li and B. Yao and P.~Kumar}, title = {Group Enclosing Queries}, journal = {IEEE Transactions on Knowledge and Data Engineering}, year = {2010}, note = {To Appear} } @INPROCEEDINGS{1137927, author = {Amit Mhatre and Piyush Kumar}, title = {Projective clustering and its application to surface reconstruction: extended abstract}, booktitle = {SCG '06: Proceedings of the twenty-second annual symposium on Computational geometry}, year = {2006}, pages = {477--478}, address = {New York, NY, USA}, publisher = {ACM Press}, doi = {http://doi.acm.org/10.1145/1137856.1137927}, isbn = {1-59593-340-9}, location = {Sedona, Arizona, USA} } @INPROCEEDINGS{5447837, author = {Bin Yao and Feifei Li and Kumar, P.}, title = {K nearest neighbor queries and kNN-Joins in large relational databases (almost) for free}, year = {2010}, pages = {4 -15}, month = {mar.}, abstract = {Finding the k nearest neighbors (kNN) of a query point, or a set of query points (kNN-Join) are fundamental problems in many application domains. Many previous efforts to solve these problems focused on spatial databases or stand-alone systems, where changes to the database engine may be required, which may limit their application on large data sets that are stored in a relational database management system. Furthermore, these methods may not 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 tht yienn. Using only a small constant number of random shifts for databases in any fixed dimension, our approach guarantees to find the approximate kNN with only logarithmic number of page accesses in expectation with a constant approximation ratio and it could be extended to find the exact kNN efficiently in any fixed dimension. Our design paradigm easily supports the kNN-Join and updates. Extensive experiments on large, real and synthetic, data sets confirm the efficiency and practicality of our approach.}, doi = {10.1109/ICDE.2010.5447837}, journal = {Data Engineering (ICDE), 2010 IEEE 26th International Conference on}, keywords = {SQL operators;database engine;k nearest neighbor queries;kNN-joins;query conditions;query optimization;query point;relational databases;spatial databases;stand-alone systems;user-defined-function;SQL;learning (artificial intelligence);query processing;relational databases;} } @INPROCEEDINGS{4812444, author = {Bin Yao and Feifei Li and Kumar, P.}, title = {Reverse Furthest Neighbors in Spatial Databases}, year = {2009}, pages = {664 -675}, month = {mar.}, abstract = {Given a set of points P and a query point q, the reverse furthest neighbor (Rfn) query fetches the set of points p isin P such that q is their furthest neighbor among all points in PU{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 isin Q, a Brfn query fetches the set of points p isin P such that q is the furthest neighbor of p among all points in Q. The Rrfn 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 Rrfn queries. We analyze properties of the Rrfn query that differentiate it from the widely studied reverse nearest neighbor queries and enable the design of novel algorithms. Our approach takes advantage of the furthest Voronoi diagrams as well as the convex hulls of either the data set P (in the Mrfn case) or the query set Q (in the Brfn case). For the Brfn queries, we also extend the analysis to the situation when Q is large in size and becomes disk-resident. Experiments on both synthetic and real data sets confirm the efficiency and scalability of proposed algorithms over the brute-force search based approach.}, doi = {10.1109/ICDE.2009.62}, issn = {1084-4627}, journal = {Data Engineering, 2009. ICDE '09. IEEE 25th International Conference on}, keywords = {Voronoi diagrams;large residential database;monochromatic query;spatial databases;computational geometry;query processing;set theory;very large databases;visual databases;} }