rp-tree 0.4 → 0.5

raw patch · 5 files changed

+41/−30 lines, 5 filesdep ~hspec

Dependency ranges changed: hspec

Files

Changelog.md +4/−0
app/Main.hs +7/−7
rp-tree.cabal +3/−1
src/Data/RPTree.hs +21/−11
src/Data/RPTree/Conduit.hs +6/−11

Changelog.md view

@@ -1,3 +1,7 @@+0.5++- fixed intermittent bug in 'knn', originally due to messing up the order of 'take' and 'sort'.+ 0.4  - add function to compute the forest construction parameters from the dataset dimensions (rpTreeCfg)

app/Main.hs view

@@ -41,21 +41,21 @@     chunk = 500     dim = 2     -- cfg = rpTreeCfg n dim-    cfg = RPCfg maxd minl 3 chunk 1.0-  csvTree0 n cfg-  tree0dot n cfg+    cfg = RPCfg maxd chunk 1.0+  csvTree0 n minl cfg+  tree0dot n minl cfg   -tree0dot :: Int -> RPTreeConfig -> IO ()-tree0dot n (RPCfg maxd minl _ chunk _) =+tree0dot :: Int -> Int -> RPTreeConfig -> IO ()+tree0dot n minl (RPCfg maxd chunk _) =   writeDot f fpath "tree0" $ tree0 n maxd minl chunk   where     f = show . length     fpath = "tree0.dot" -csvTree0 :: Int -> RPTreeConfig -> IO ()-csvTree0 n (RPCfg maxd minl _ chunk _) = do+csvTree0 :: Int -> Int -> RPTreeConfig -> IO ()+csvTree0 n minl (RPCfg maxd chunk _) = do   let     tt = tree0 n maxd minl chunk     ttlab = prep tt

rp-tree.cabal view

@@ -1,5 +1,5 @@ name:                rp-tree-version:             0.4+version:             0.5 synopsis:            Random projection trees description:         Random projection trees for approximate nearest neighbor search in high-dimensional vector spaces                      .@@ -35,6 +35,7 @@                      , conduit >= 1.3.1                      , containers >= 0.6                      , deepseq >= 1.4+                                           , microlens                      , microlens-th                      , mtl >= 2.2.2@@ -49,6 +50,7 @@                      -- -- -- DEBUG                      -- , benchpress                      -- , hspec+                     , hspec >= 2.7.1                      -- , mnist-idx-conduit                       test-suite spec

src/Data/RPTree.hs view

@@ -158,11 +158,13 @@     -> RPForest d (V.Vector (Embed u d x)) -- ^ random projection forest     -> v d -- ^ query point     -> V.Vector (p, Embed u d x) -- ^ ordered in increasing distance order to the query point-knn distf k tts q = sortByVG fst cs+knn distf k tts q = VG.take k $ sortByVG fst cs   where-    cs = VG.map (\xe -> (eEmbed xe `distf` q, xe)) $ VG.take k $ fold $ (`candidates` q) <$> tts+    cs = VG.map (\xe -> (eEmbed xe `distf` q, xe)) $ fold $ (`candidates` q) <$> tts --- | Same as 'knn' but with a (hopefully) faster implementation+-- | Same as 'knn' but accumulating the result in low margin order (following the intuition in 'annoy').+--+-- FIXME to be verified knnPQ :: (Ord p, Inner SVector v, VU.Unbox d, RealFrac d) =>          (u d -> v d -> p) -- ^ distance function       -> Int -- ^ k neighbors@@ -177,13 +179,21 @@     n = length tts  --- | average recall-at-k, computed over a set of trees-recallWith :: (Inner SVector v, VU.Unbox d, Fractional a1, Ord d, Ord a2, Ord x, Ord (u d), Num d) =>-              (u d -> v d -> a2)+-- | Average recall-at-k, computed over a set of trees+-- +-- The supplied distance function @d@ must satisfy the definition of a metric, i.e.+--+-- * identity of indiscernible elements : \( d(x, y) = 0 \leftrightarrow x \equiv y \)+--+-- * symmetry : \(  d(x, y) = d(y, x)  \)+--+-- * triangle inequality : \( d(x, y) + d(y, z) \geq d(x, z) \)+recallWith :: (Inner SVector v, VU.Unbox d, Fractional b, Ord d, Ord a, Ord x, Ord (u d), Num d) =>+              (u d -> v d -> a) -- ^ distance function            -> RPForest d (V.Vector (Embed u d x))            -> Int -- ^ k : number of nearest neighbors to consider            -> v d -- ^ query point-           -> a1+           -> b recallWith distf tt k q = sum rs / fromIntegral n   where     rs = fmap (\t -> recallWith1 distf t k q) tt@@ -197,11 +207,11 @@            -> p recallWith1 distf tt k q = fromIntegral (length aintk) / fromIntegral k   where-    xs = points tt-    dists = sortBy (comparing snd) $ toList $ fmap (\x -> (x, eEmbed x `distf` q)) xs-    kk = S.fromList $ map fst $ take k dists -- first k nn's-    aa = set $ candidates tt q     aintk = aa `S.intersection` kk+    aa = set $ candidates tt q+    kk = S.fromList $ map fst $ take k dists -- first k nn's+    dists = sortBy (comparing snd) $ toList $ fmap (\x -> (x, eEmbed x `distf` q)) xs+    xs = points tt  set :: (Foldable t, Ord a) => t a -> S.Set a set = foldl (flip S.insert) mempty

src/Data/RPTree/Conduit.hs view

@@ -122,25 +122,20 @@  data RPTreeConfig = RPCfg {   fpMaxTreeDepth :: Int -- ^ max tree depth \(l > 1\) -  , fpMinLeafSize :: Int -- ^ min leaf size -  , fpNumTrees :: Int -- ^ number of trees \(n_t > 1\)+  -- , fpMinLeafSize :: Int -- ^ min leaf size    , fpDataChunkSize :: Int -- ^ data chunk size   , fpProjNzDensity :: Double -- ^ nonzero density of projection vectors \(p_{nz} \in (0, 1)\)                           } deriving (Show) -defaultParams :: RPTreeConfig-defaultParams = RPCfg 5 10 3 100 0.5 --- | Configure the rp-tree forest construction process with some natural defaults-rpTreeCfg :: Integral a =>-             a -- ^ data size-          -> Int -- ^ vector dimension+-- | Configure the rp-tree tree construction process with some natural defaults+rpTreeCfg :: Int -- ^ min leaf size+          -> Int -- ^ number of points in the dataset+          -> Int -- ^ vector dimension of the data points           -> RPTreeConfig-rpTreeCfg n d = RPCfg maxd minl ntree nchunk pnz+rpTreeCfg minl n d = RPCfg maxd nchunk pnz   where-    minl = 10     maxd = ceiling $ logBase 2 (fromIntegral n / fromIntegral minl)-    ntree = 3     nchunk = ceiling $ fromIntegral n / 100     pnzMin = 1 / logBase 10 (fromIntegral d)     pnz = pnzMin `min` 1.0