FIGTree: Fast Improved Gauss Transform with Tree Data Structure

A library for fast computation of Gauss transforms in multiple dimensions, using the Improved Fast Gauss Transform and Approximate Nearest Neighbor searching. The nearest neighbor searching is performed using the ANN library, available at This software allows for efficient computation of probabilities by Kernel Density Estimation (KDE), and can reduce complexity of algorithms commonly used in Computer Vision, Machine Learning, etc, that must evaluate the Gauss transform.

Related Publications

The publication describing the newest improvements in the code is the NIPS 2008 paper by Morariu et al (see below). Previous publications related to this approach are provided on Vikas Raykar's page. If you use FIGTree in a publication, please cite the following paper:

Vlad I. Morariu, Balaji Vasan Srinivasan, Vikas C. Raykar, Ramani Duraiswami, and Larry S. Davis. Automatic online tuning for fast Gaussian summation. Advances in Neural Information Processing Systems (NIPS), 2008. PDF BibTeX


The author of the most recent versions of FIGTree is Vlad Morariu. Improvements include online parameter tuning and method selection, as well as a C/C++ interface. Vikas Raykar and Changjiang Yang were the initial authors of previous versions of IFGT and FIGTree. The authors worked under the supervision of Professor Ramani Duraiswami and Professor Larry Davis, at the University of Maryland.


This code extends Vikas Raykar's version of the IFGT code, which was provided under the GNU Lesser General Public License (LGPL). As a result, the FIGTree library is also released under the LGPL.


Download (from SourceForge) Logo