Answers.Body: <p>It sounds like you may be looking for the <a href="https://en.wikipedia.org/wiki/A*_search_algorithm" rel="nofollow noreferrer">A* search algorithm</a>. It is a search algorithm, like DFS and BFS, but it will explore only the most promising branches based on a heuristic function you supply. The difficult part of implementing this is deciding on a low-cost, admissible heuristic.</p>
  <p>Excited to reflect nbro's suggestion from comments.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-04T21:57:32.850Z
Answers.Text: A* does not really prune branches, but it explores branches according to the admissible heuristic, so, more intuitively, we could say that it explores branches based on how promising they are, but it doesn't really discard any branch. I'm not sure if A* is really the solution the problem.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-05T16:17:43.537Z
Answers.Text: I would say that within the search space branches are "pruned" if they are never explored. Is there other terminology for that you would look for?
Answers.UserDisplayName: Alina Barnett
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-05T16:22:37.187Z
Answers.Text: The reason why I think "prune" may not be the most appropriate term here is that, if there's no goal and the graph is finite, for instance, A* should explore all nodes, so, in that case, it doesn't prune anything. However, you're right that it may not visit certain parts of the search space if all paths that lead to the goal from a start node have already been explored, so, in those cases, we can think of certain parts of the search space being pruned. So, I was a bit imprecise in my previous comment, so your description was right (but not applicable in all cases).
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-05T16:27:50.947Z
Answers.Text: In any case, I'm still not sure whether A* is the right tool to solve OP's problem. Maybe you should try to explain more in detail how A* should be applied in the OP's case.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-06T05:31:54.133Z
Answers.Text: Thank you guys for answering my question! I didn't know that kind of search algorithm was called the A* search algorithm. But nbro has a point since it seems like the A* algorithm requires a destination to work towards. This problem is a real head-scratcher because the data isn't discrete; it's like drawing lines in the sand to mark how far the waves reach into the beach. Using a heuristic has it's merits but it breaks down when that heuristic comes down to a razor's margin at a fork in the road.
Answers.UserDisplayName: JungleBird
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-06T05:57:19.353Z
Answers.Text: I also edited my post to include a better picture of a graph I'd be dealing with. Each branch represents a cluster/sub-cluster. And it would reduce my search time exponentially if I could just "prune" the first few major branches and contain my DFS/BFS in a sub-cluster. The best way to do that would be keep some memory about where previous nodes ended up. At first the associations would be weak but grow stronger with more nodes being placed, and stronger associations would translate to greater confidence in which path a node should take.
Answers.UserDisplayName: JungleBird
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-04T20:19:51.457Z
Answers.LastActivityDate: 2021-01-05T16:16:10.200Z
Answers.LastEditDate: 2021-01-05T16:16:10.200Z
Answers.UserDisplayName: Alina Barnett
Body: <p>I'm not very knowledgeable in this field but I'm wondering if any research or information already exists for the following situation:</p>
  <p>I have some data that may or may not look similar to each other. Each represents a node that represents a vector of size 128.</p>
  <p><a href="https://i.sstatic.net/9XT1o.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/9XT1o.png" alt="similar vectors" /></a></p>
  <p>And they are inserted into a tree graph according to similarity.</p>
  <p><a href="https://i.sstatic.net/Vsy4C.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Vsy4C.png" alt="better graph" /></a></p>
  <p>and a new node is created with an edge connecting the most similar vertex node found in the entire tree graph.</p>
  <p>Except I'm wasting a lot of time searching through the entire graph to insert each new node when I could narrow down my search according to previous information. Imagine a trunk node saying &quot;Oh, I saw a node like you before, it went down this branch. And don't bother going down that other branch.&quot; I could reduce the cost of searching the entire tree structure if there was a clever way to remember if a similar node went down a certain path.</p>
  <p>I've thought about some ways to use caching or creating a look-up table but these are very memory intensive methods and will become slower the longer the program runs on. I have some other ideas I am playing around with but I was hoping someone could point me in the right direction before I started trying out weird ideas.</p>
  <p>Edit: added a better (more realistic) graph picture</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-05T05:40:27.820Z
Comments.Text: might be late, but if your similarity metric abide the triangle inequality $d(a,c) \leq d(a,b) + d(b,c)$, you can use M-Tree (metric tree) to store/retrieve the node more efficiently. You can also query K-closest node by using M-Tree.
Comments.UserDisplayName: Sanyou
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-06T22:58:21.500Z
Comments.Text: Thank you for answering! That's a great idea to explore, as I haven't seen a good solution to tackle this problem yet
Comments.UserDisplayName: JungleBird
Tags: <machine-learning><deep-learning><breadth-first-search><depth-first-search>
Title: A way to leverage machine learning to reduce DFS/BFS search time on a tree graph?
UserDisplayName: JungleBird
ThreadText: # A way to leverage machine learning to reduce DFS/BFS search time on a tree graph?
  
  (Asked by: username_0 on 2021-01-02)
  
  I'm not very knowledgeable in this field but I'm wondering if any research or information already exists for the following situation:
  
  I have some data that may or may not look similar to each other. Each represents a node that represents a vector of size 128.
  
  [![similar vectors](https://i.sstatic.net/9XT1o.png)](https://i.sstatic.net/9XT1o.png)
  
  And they are inserted into a tree graph according to similarity.
  
  [![better graph](https://i.sstatic.net/Vsy4C.png)](https://i.sstatic.net/Vsy4C.png)
  
  and a new node is created with an edge connecting the most similar vertex node found in the entire tree graph.
  
  Except I'm wasting a lot of time searching through the entire graph to insert each new node when I could narrow down my search according to previous information. Imagine a trunk node saying "Oh, I saw a node like you before, it went down this branch. And don't bother going down that other branch." I could reduce the cost of searching the entire tree structure if there was a clever way to remember if a similar node went down a certain path.
  
  I've thought about some ways to use caching or creating a look-up table but these are very memory intensive methods and will become slower the longer the program runs on. I have some other ideas I am playing around with but I was hoping someone could point me in the right direction before I started trying out weird ideas.
  
  Edit: added a better (more realistic) graph picture
  
  **Tags:** machine-learning, deep-learning, breadth-first-search, depth-first-search
  > **Comments:**
  > **username_1**: might be late, but if your similarity metric abide the triangle inequality $d(a,c) \leq d(a,b) + d(b,c)$, you can use M-Tree (metric tree) to store/retrieve the node more efficiently. You can also query K-closest node by using M-Tree.  
  > **username_0**: Thank you for answering! That's a great idea to explore, as I haven't seen a good solution to tackle this problem yet  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-01-04. Score: 0
  
  It sounds like you may be looking for the [A\* search algorithm](https://en.wikipedia.org/wiki/A*_search_algorithm). It is a search algorithm, like DFS and BFS, but it will explore only the most promising branches based on a heuristic function you supply. The difficult part of implementing this is deciding on a low-cost, admissible heuristic.
  
  Excited to reflect nbro's suggestion from comments.
  
  > **Comments:**
  > **username_3**: A* does not really prune branches, but it explores branches according to the admissible heuristic, so, more intuitively, we could say that it explores branches based on how promising they are, but it doesn't really discard any branch. I'm not sure if A* is really the solution the problem.  
  > **username_2**: I would say that within the search space branches are "pruned" if they are never explored. Is there other terminology for that you would look for?  
  > **username_3**: The reason why I think "prune" may not be the most appropriate term here is that, if there's no goal and the graph is finite, for instance, A* should explore all nodes, so, in that case, it doesn't prune anything. However, you're right that it may not visit certain parts of the search space if all paths that lead to the goal from a start node have already been explored, so, in those cases, we can think of certain parts of the search space being pruned. So, I was a bit imprecise in my previous comment, so your description was right (but not applicable in all cases).  
  > **username_3**: In any case, I'm still not sure whether A* is the right tool to solve OP's problem. Maybe you should try to explain more in detail how A* should be applied in the OP's case.  
  > **username_0**: Thank you guys for answering my question! I didn't know that kind of search algorithm was called the A* search algorithm. But nbro has a point since it seems like the A* algorithm requires a destination to work towards. This problem is a real head-scratcher because the data isn't discrete; it's like drawing lines in the sand to mark how far the waves reach into the beach. Using a heuristic has it's merits but it breaks down when that heuristic comes down to a razor's margin at a fork in the road.  
  > **username_0**: I also edited my post to include a better picture of a graph I'd be dealing with. Each branch represents a cluster/sub-cluster. And it would reduce my search time exponentially if I could just "prune" the first few major branches and contain my DFS/BFS in a sub-cluster. The best way to do that would be keep some memory about where previous nodes ended up. At first the associations would be weak but grow stronger with more nodes being placed, and stronger associations would translate to greater confidence in which path a node should take.  
  
  ---
  
  