madlib/madlib — pull request #152 by fschopp (2012-05-15 14:53:29+00:00)
Title: k-Means Rewrite

*This is a big pull request. It may be advisable to look at the individual commits that I grouped into logical units. Please do not merge without checking back with me.*

k-Means:
- Complete redesign and rewrite. Main new features: 1) The new implementation is nothing more but an iteratively called aggregate function. Now conversion between temporary tables and iteration states takes place. 2) The distance metric is fully pluggable. 3) Clear separation between the seeding algorithm and Lloyd's local search heuristic 4) The new code should be much easier to read and maintain
- Uses C++ AL
- First incarnation of general Python abstraction layer (currently still in kmeans.py, though). Main feature: No data movement between backend and PL/Python.

Utilities:
- Implemented a C function exec_sql_using() that can be used to emulate the EXECUTE ... USING command that is not available before PostgreSQL 8.4. This seems to be the only "guaranteed lossless" way to write function arguments into a table.

Linear-Algebra Operations:
- Function closest_column() for determining the column of a matrix that is closest to a vector, according to the given metric
- Function squared_dist_2norm() for determining the square of the Euclidean distance between two vectors
Both functions will be needed for k-means

C++ AL:
- Increased support for Eigen types: (Non-mapped) vectors and matrices can now directly be converted to AnyType (and thus returned or passed to FunctionHandles)
- Added types [Mutable]Mapped{ColumnVector|Matrix} that can now be used as template parameters for AnyType::getAs
- ArrayHandles now understand multi-dimensional PostgreSQL arrays. We store matrices as an array of columns, i.e., in PostgreSQL one would write matrix[col][row] whereas in C++ code the row index comes first (as one would expect)

Linear/logistic regression:
- Minor changes to make use of the [Mutable]MappedColumnVector types.

Sampling module:
- Added a data-parallel UDA for weighted sampling of a single row
- This uses boost's Mersenne Twister, and the random_device class for initialization. Instead of linking to boost's random library, I for now added boost's random_device.cpp to the repository. As we move forward, we probably want to extend our build system to build boost libraries on demand. Because of problems with the boost v1.46.1 headers in the context of using random_device, I bumped the required boost version to v1.47 and the automatically downloaded version to 1.49.0.