From c4a1b596483b494ead45755dca1805cae6b5615c Mon Sep 17 00:00:00 2001
From: Douglas Rumbaugh <dbr4@psu.edu>
Date: Mon, 17 Jul 2023 09:24:19 -0400
Subject: VPTree: use a secondary hash-table for point lookups

---
 include/shard/VPTree.h | 23 +++++++++++++++--------
 1 file changed, 15 insertions(+), 8 deletions(-)

(limited to 'include/shard')

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;
-- 
cgit v1.2.3