Leaky Hash Tables


In a recent project, I've had to keep a set of elements in memory and a hash table was a possible candidate.
I ran a very simple benchmark on insertion times, using a C hashtable library.
This benchmark inserts 8-byte elements in a hash table, for numeric keys ranging from 1 to 20 million while measuring the insertion time for each element.

hash table insertion times

This graph reveals the internal structure of the hash table, which expands when a certain number of items is reached. The values for different thresholds are often prime numbers, or powers of 2.

All inserts were under 30 milliseconds, except for the following values:

ElementsInsertion time (ms)Time change
127,80032
255,60860×1.875
511,18393×1.55
1,022,366194×2.08
2,044,732415×2.14
4,089,456821×1.98
8,178,8971709×2.08
16,357,7993621×2.12

Here, powers of 2 times a thousand elements. Other algorithms manage to avoid this kind of problematic behaviour.

Abstractions can be considered leaky not only when the underlying data structure is exposed in the public API, but also when the behaviour of some special cases put a strain on the whole process.

For a great read on the implementation of hash tables in C, head to chapter 18 of Beautiful Code, called “Python's Dictionary Implementation: Being All Things to All People”.

SVD for fun and profit


I’m working on a recommendation system designed to suggest features to users who haven’t tried them yet, based on what other people use.
The method I’m looking at now is using the Singular Value Decomposition (SVD) technique to build suggestions; It has been used in the Netflix prize, among other places.

SVD for profit: the Netflix prize

The movie rental service Netflix offers recommendations to their clients, and have launched a contest in 2006 to improve their recommendation engine. Participants get a dataset of 100 million ratings for 480,189 users and 17,770 movies. The matrix of all ratings is 480,189×17,770 (over 8.5×109 items), of which almost 99% is empty.
It is such a hard problem (computation-wise) that Netflix is currently offering $1M for a 10% improvement over their existing system. My dataset is far from being as large as theirs, but is large enough to require some special attention—we can’t use naïve techniques, and can’t fit the entire matrix in memory.

Quick explanation of matrix approximations using the SVD

The SVD can be used to approximate a matrix, which is useful in this kind of system.
The SVD of a m-by-n matrix M is the collection of 3 matrices (U,Σ,V) where U is an m-by-m matrix, Σ an m-by-n diagonal matrix, and V* the conjugate transpose of an n-by-n matrix, such as M = UΣ(V*).

Using an example from the Wikipedia page:
svd

The SVD can be used to approximate a matrix: By keeping k columns of U as (Uk), k values of Σ as (Σk), and k lines of V* as (V*k), we still get M≈UkΣk(V*k).
If k is small enough, we can use a total number of cells lower than the original n×m.

Note: Running an SVD on a matrix as large as the Netflix one requires a special technique, which reduces these billions of cells to a few millions only while retaining a lot of information. See Timely Development for an example using the Netflix dataset.

Example of matrix approximation

Consider the following ratings table:

Books rated by users
User 1User 2User 3User 4
Book 1141
Book 225
Book 3414
Book 41
Book 53551
Book 632

Original matrix:
matrix-1.png
Rebuilt with k=4, the matrix is the same.

Approximation in rounded integers with k=3:
matrix-2.png
Three ratings are wrong: (User1, Book1) and  (User4, Book1) were both 1 and are now 0, (User1, Book3) was 0 and is now 1.
RMSE≈0.657

With k=2:
matrix-3.png
Quite a few mistakes here... one rating is -1 and one is 6! When the matrix is rebuilt, the values must always be recalibrated into the right range.
RMSE≈2.903

With k=1:
matrix-4.png
RMSE≈9.456

This one is way off! We can’t use such an approximation. One must then find a compromise between data size and precision by tweaking the value of k.
For reference, the first team to reach a RMSE under 0.8572  in their predictions on the Netflix dataset will win the prize.

SVD for fun: image compression

Let’s try on real data. If we load an image as a matrix of colours, how well can we compress it using the SVD? Pretty well, even if it’s not JPEG. Take a look at “Lenna”, using different values for k:

k = 1, image generated from (1×384 + 1 + 384×1) = 769 bytes.
lenna-1.png

k = 10; 7,690 bytes.
lenna-10.png

k = 20; 15,380 bytes.
lenna-20.png

k = 50; 38,450 bytes.
lenna-50.png

k = 100; 76,900 bytes.
lenna-100.png

k = 200; 153,800 bytes.
lenna-200.png

Here is lenna.png, the file used as an input to the program; Please excuse the very primitive PPM writer, this is not really the point of this article.
The code for image compression is in Haskell, using the hmatrix and pngload libraries:

module Main where

import Numeric.LinearAlgebra
import Codec.Image.PNG (loadPNGFile, dimensions, imageData)
import Data.Array.MArray (getElems)
import Data.Word (Word8)
import Data.Char (chr)

main = do
png <- loadPNGFile "lenna.png"
case png of
Left fail -> error fail
Right img -> do
m <- fmap (compress 10) $ mkMatrix img
savePPM "out.ppm" m

mkMatrix img = do -- creates a matrix from a PNGImage
let (w,h) = dimensions img
table <- getElems $ imageData img :: IO [Word8] -- read colours
return $ (fromEnum h><fromEnum (3*w)) $ map fromIntegral table

compress k m = u_k <> sigma_k <> v_k where
(u,sigma,v) = full svd m -- get SVD
sigma_k = (takeColumns k . takeRows k) sigma -- keep k values of Σ
u_k = takeColumns k u -- keep k columns of U
v_k = takeRows k $ trans v -- keep k rows of v

savePPM filename m = writeFile filename $ header ++ contents where
header = concat ["P6\n", show $ cols m `div` 3,
" ", show $ rows m, "\n255\n"]
contents = (concatMap . map) toChar $ toLists m -- format
toChar = chr . fromIntegral . round . max 0 . min 255.0 -- round & bound

Other techniques

There are many ways to recommend items; a lot of them are described (with Python code!) in the fantastic book Programming Collective Intelligence by Toby Segaran.

See also:

Older More recent