I saw this via Lobsters yesterday and enjoyed reading it. The animations helped me understand bidiBFS.
But I'm confused by the example showing the buggy version of the algorithm fail. This is in the section "Finding the Wrong Path".
Consider the state of the algorithm after the first step. We've explored S and added its neighbors to the queue, Q = [T, a1, b1].
In the next step we explore T, the first node in the queue. We add its neighbors , a3 and b2, to the queue.
Now, I would expect the new value of Q to be something like [a1, b1, a3, b2] (depending on the order we add T's neighbors). In this case we would process a1, and b1 next, notice that b1 is adjacent to b2, and correctly find the shortest path S-b1-b2-T.
But the animation actually shows that after step 2, Q = [a1, a3, b1, b3]. In other words, a3 didn't join the back of the queue but jumped in front of b1. This is what leads to the buggy behavior that is shown.
So as I understand the example, this would have worked fine if Q were actually a queue. But as shown it is not.
> But the animation actually shows that after step 2, Q = [a1, a3, b1, b3]. In other words, a3 didn't join the back of the queue but jumped in front of b1. This is what leads to the buggy behavior that is shown.
This is my fault. The animation doesn't really point that out, but these are two separate queues: the forwards BFS and the backwards BFS each have their own queue. What the diagram shows is the order in which the nodes will be visited, according to the queues. So it's interleaved, in a way, since each step alternates the BFS that is executed.
However, suppose that Q actually be a "normal" queue. We'd then need to track, in the queue, which "way" the node should be visited (forwards or backwards). We'd be visiting more nodes at once per side but we'd still not visit levels at once before moving on to the other side, so it could still give the bad path sometimes. Also, since we'd only have one queue, we would be unable to efficiently detect a missing path: right now we check at each step if either of the queues is empty (and stop if that's the case). With a single queue, it would be slow to check if one side doesn't have any queued nodes, and without that check, for cases where no path exists, we'd waste time expanding a search on one side when it could never reach the destination anyway.
I've found it to be quite accurate here in upstate NY, with a few recognizable exceptions. In particular, sometimes it seems to think it's hearing a blue-headed vireo when a red-eyed vireo is singing. Also, it sometimes misreports yellow-rumped warblers.
There is an email address to send errors and such. A secretary prints them and he marks up the hard copy (if necessary) which is returned with a reward check (when appropriate).
Agreed. I posted a lot in the 90s, especially to groups like sci.math and rec.arts.books.tolkien, and there is almost no trace of any of it in Google groups.
When Google bought the Dejanews archives I thought it was good, because Google was good at search and I naively still believed that the company actually wanted to make all information accessible. It's a real shame that all of the old Usenet stuff is gone.
Years ago I had one of these. It slowly stopped working and my wife got sick of it. Without any way to fix it I got rid of it, which I now regret. The toaster we have now browns unevenly and is wildly inconsistent from run to run.
BirdNet has been around for several years now, while Merlin just got sound-id recently. Merlin has coverage for about 450 birds of North America, while BirdNet can id around 1000 birds of N Am. and Europe.
With BirdNet you make a recording, highlight the interesting section of the sonogram, and upload that section to the BirdNet servers. With Merlin you start recording and the software ids birds in real time, popping up species as it goes.
My assumption is that, because it runs locally on the device, Merlin is going to be less accurate than whatever BirdNet is able to do on its beefy servers. But it is has the advantage of working without a data connection. Merlin can also id from photos and descriptions.
So the one isn't a replacement for the other. It's great to have options.
The apps run two different models, and mobile phones are plenty powerful now to run some pretty complicated algorithms, so the offline accuracy of Merlin is pretty good.
BirdNET and Merlin Sound ID are such different use cases (real-time classification of a rolling window of audio vs classification of a user selection) that we don't have any comparison metrics between the two, and they are really geared for different purposes (BirdNET’s goals align more with research in bioacoustics, while Merlin’s goals align more with outreach and education.)
