You, must, must, take inflation and percentage of GDP into account.
Of course spending increases with population, because there's more people to look after and more taxes to do it.
Spending per person adjusted for inflationhttp://oregonstate.edu/Dept/pol_sci/fac/sahr/percap92.htm
You can see that Clinton is slightly higher.
And by percentage of GDP:http://carriedaway.blogs.com/carried_away/images/economics/u.S.%20Spending%20And%20Revenue%20In%20Relation%20To%20GDP.GIF
Note that Government spending drops under Bush, federal spending goes down, states go up.