VPTree: use a secondary hash-table for point lookups

2 files changed, 24 insertions, 8 deletions

diff --git a/include/framework/RecordInterface.h b/include/framework/RecordInterface.h
index 6936a8b..ab4c6f9 100644
--- a/include/framework/RecordInterface.h
+++ b/include/framework/RecordInterface.h
@@ -14,6 +14,7 @@
 #include <cmath>
 
 #include "util/base.h"
+#include "util/hash.h"
 
 namespace de {
 
@@ -117,4 +118,12 @@ struct Point{
         return sqrt(pow(x - other.x, 2) + pow(y - other.y, 2));
     }
 };
+
+template<RecordInterface R>
+struct RecordHash {
+    size_t operator()(R const &rec) const {
+        return hash_bytes((char *) &rec, sizeof(R));
+    }
+};
+
 }
diff --git a/include/shard/VPTree.h b/include/shard/VPTree.h
index 5364537..6a976f7 100644
--- a/include/shard/VPTree.h
+++ b/include/shard/VPTree.h
@@ -13,6 +13,7 @@
 #include <queue>
 #include <memory>
 #include <concepts>
+#include <map>
 
 #include "ds/PriorityQueue.h"
 #include "util/Cursor.h"
@@ -104,6 +105,7 @@ public:
 
         if (m_reccnt > 0) {
             m_root = build_vptree();
+            build_map();
         }
     }
 
@@ -136,6 +138,7 @@ public:
 
         if (m_reccnt > 0) {
             m_root = build_vptree();
+            build_map();
         }
    }
 
@@ -145,17 +148,13 @@ public:
     }
 
     Wrapped<R> *point_lookup(const R &rec, bool filter=false) {
-        auto node = m_root;
+        auto idx = m_lookup_map.find(rec);
 
-        while (node && m_data[node->idx].rec != rec) {
-            if (rec.calc_distance(m_data[node->idx].rec) >= node->radius) {
-                node = node->outside;
-            } else {
-                node = node->inside;
-            }
+        if (idx == m_lookup_map.end()) {
+            return nullptr;
         }
 
-        return (node) ? m_data + node->idx : nullptr;
+        return m_data + idx->second;
     }
 
     Wrapped<R>* get_data() const {
@@ -194,6 +193,13 @@ private:
         return n;
     }
 
+    void build_map() {
+
+        for (size_t i=0; i<m_reccnt; i++) {
+            m_lookup_map.insert({m_data[i].rec, i});
+        }
+    }
+
     vpnode *build_subtree(size_t start, size_t stop, gsl_rng *rng) {
         if (start >= stop) {
             return nullptr;
@@ -268,6 +274,7 @@ private:
     }
 
     Wrapped<R>* m_data;
+    std::unordered_map<R, size_t, RecordHash<R>> m_lookup_map;
     size_t m_reccnt;
     size_t m_tombstone_cnt;
     size_t m_node_cnt;