« Stuff The Internet Says On Scalability For February 23rd, 2018 | Main | Stuff The Internet Says On Scalability For February 16th, 2018 »

How fast can a bird search a tree?


I was wondering if you could help me figure something out: what is the algorithmic complexity of a bird searching a tree for food?

Over the years I've had the pleasure of watching a lot of cute little birds feed in our oak trees. I've noticed they have a search pattern.

A bird will hop from branch to branch looking for insects. They don't hop on a branch and explore every square inch of it, so it's not an exhaustive search. They'll take a couple hops, peck at a branch a few times, and hop to a nearby branch. Birds also search the underside of branches, so the whole surface area of a tree is game. 

I've often marveled in wonder at how efficient this whole process is. They scour huge trees in no time. Then they'll move on to the next tree and repeat the process until they fly away to a completely different area.

My dog when searching for a ball seems to follow a similar Lévy flight sort of pattern. Search a local area by bouncing around for bit and then take a bee-line for a completely different area and repeat the process. 

Often a flock will search a single tree at the same time, so there's parallelism at work here. A bird being on a branch doesn't lock the branch, but a new bird will jump to a different part of a branch if a branch has another bird on it already.

I haven't been able to determine if there's some signal, like a certain threshold number of birds flying away that tells the flock this tree has played out, or if each bird makes their own decisions locally. I don't know how they select trees either. They, it seems to me, enter a tree at random, not always starting at the top or bottom, and not performing on obvious depth or breadth first search. They don't seem to want to visit every branch of a tree either. They spend a limited amount of time in each tree before moving on.

An analogy to computing I've noticed is that it's the shape of thee tree itself that contributes to the efficiency of the search. A tree efficiently fills a certain volume of space with leaves and branches, optimizing for sunlight exposure. It's because branches are located on a trunk, relatively close together, often almost touching, with a fractal branching pattern that means branches lead to more branches which lead to more branches, that birds can make quick work if searching a tree for food.

When I see a bird jump from branch to branch, tree to tree, I see some sort of search algorithm. What I don't see is good way to describe it. Any ideas?

Reader Comments (11)

They are not really opt for efficiency I think? It might be just for fun and major part of their life.

February 21, 2018 | Unregistered CommenterFrank

They might use other senses like smell or hearing... you have to be good at those to not being eaten by bigger animals.

February 21, 2018 | Unregistered Commenterkarl

I don't think they get any rewards for recall, only precision (sorry if I got that backwards). If a short search finds a goody, they probably keep searching locally. But if the short search doesn't find anything, it is probably more valuable to search elsewhere rather than embark on a local exhaustive search.

There are higher-order effects, too, because perhaps some other bird recently searched this tree, and there are probably also benefits to letting the smaller and harder to find morsels grow.

It would be interesting to see how hunger factors in. A well-fed bird has more energy and less need, while a hungry bird has less energy and more need. Being hungry implies low availability, which might encourage longer searches since there's less chance of easy pickings elsewhere.

[I bet there's an exhaustive literature on this ... somewhere.]

February 21, 2018 | Unregistered CommenterScott Hess

Birds probably recognize trees by their leaves/twigs and recall the part of the tree that had the likelyhood of finding food. They probably also recall the season of the year and the ecosystem around the tree that gave them food on a particular type of tree.

February 22, 2018 | Unregistered CommenterMilind

The complexity of the algorithm is probably infinite, we could spend hours and hours discussing about that. Wasn't there a famous scientist who declared the time and space for infinite?

Sure is that nature made not only the tree as efficient as possible, but also the bird and his extreme senses. A lot of the story behind that fact is written in the genetic code of the bird.

What about the things we can't see, for example how does the world looks like from a bird's eye? Even when find a way to build an artificial birdorganism to therefore project a picture onto a screen: How can we be sure that this is analog to the bird's reality?

We need a way to transform ourselves into birds!

February 22, 2018 | Unregistered CommenterCaio

If the tree is optimized for sunlight, the bird could see the tree from an optimal vantage point, or a set of optimal vantage points.

If you climb a tree and look down you see a radiating fan of branches. With good eyesight you could pretty much see all of the tree from just a few spots. That assumes the bugs you are looking for are on the sunny side.

February 22, 2018 | Unregistered CommenterChris

Birds are amazingly well made:

In terms of the birthday paradox, only a few random branch perches actually need to be searched for the bird to have a 50% chance of finding food, if the tree has food.

For example, if the tree has 365 possible branch perches at which to look for food, then the bird only needs to inspect around 23 random branch perches to have a 50% chance of hitting the jackpot.

If the bird searches enough branch perches without finding anything, then there's a good chance that the tree does not have the kind of food the bird is looking for, and the bird is better off moving on.

In terms of probability theory, every tree searched doubles the chances of finding food, so the bird might even consider inspecting slightly fewer branch perches per tree, to eliminate large clusters of unfruitful trees quickly.

Moving quickly also has the nice fringe benefit of making the bird less vulnerable to creeping things like snakes, by not staying too long in any one tree, unless there is food of course.


February 23, 2018 | Unregistered CommenterJoran

We need more data to determine the pattern and thereby the algorithm. Else it will be just speculations.

February 23, 2018 | Unregistered Commenteranonymous

Question for you: When you go in the forest looking for mushrooms ... what's your search algorithm? I'd bet that most people do it exactly like the birds described. Now if I ask myself, what the pattern is, I would probably end up with something along of this:

while there are any unsearched forests within reach {
enter forest

while there are any promising search areas nearby {

enter search area, defined by the area that I can overlook easily within not to many footsteps.

if there are any "low hanging fruits", i.e. if I can find a mushroom in under 1 minute {
// if I found something, I decide to dig deeper. Experience tells, where there is one, there are often more.

while( collect-next-mushroom && (! enough-mushrooms-found)) {

if( no-sunlight || search-timed-out) {
exit search

// At some point it gets boring, because I did not find
// any more mushroom in a certain time frame (say 3 minutes)
if( no-mushroom-within-3-minutes) {
break // we're done with that area

exit area

if( no-sunlight || search-timed-out) {
exit search
exit forest

if( no-sunlight || search-timed-out) {
exit search

February 24, 2018 | Unregistered CommenterJensG

It's been mentioned a couple times already, but I'll repeat it anyway in my own words. I'm sure there's some heuristics involved based on instincts and experience. I saw a documentary once explaining how crows are able to pass on learned experience to younger generations (IIRC). I believe this ties into understanding the specific problem at hand based on what is being searched for. Is the algorithm you're trying to achieve looking for something specific? Then probably not a good fit for this algorithm. But if you're searching for a classification or possible matches for further review then based on the comments regarding probability above I think this could be a good experiment to try out.

February 24, 2018 | Unregistered CommenterMark Miller

Actually, I don't think a bird really tries does on the fly calculations (pun intended) about the probability of finding something on a tree-like graph and which number of edges have to be visited to reach that percentage goal. I never saw a crow carrying a laptop around or do statistics.

Instead, my guess would be some simple effort-success ratio (the "low hanging fruits" again), and it bwas not an accident I came up with the mushroom example - I see a lot of similarities. The rest, the decision about move on or continue search is based on learned behaviour.

And the big question here is, whether the algorithm is really that excellent as we might assume it is, or if it is just "good enough". I personally prefer to think it is the latter (and I have a slight feeling that Mr. Ockham would probably agree), and that essentially renders the whole debate into something less spectacular or exotic. Some birds just learned some sort of a decision balance (not necessarily the optimum) that finally lead them to find enough food, and some died trying during the evolution.

A good existing example for "good enough" is skip lists

February 24, 2018 | Unregistered CommenterJensG

PostPost a New Comment

Enter your information below to add a new comment.
Author Email (optional):
Author URL (optional):
Some HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>