AOL has rightly apologized for its massive disclosure of over 650,000 users' search data. But it has also seemed to downplay the disclosure by saying, "there was no personally identifiable data linked to these accounts," even as it concedes "search queries themselves can sometimes include such information."
And thus these records can all too easily be linked to a user's identity, as this New York Times article clearly demonstrates. Without a doubt, many AOL users could be identified like the woman in this story -- whether vanity searches for your name or MySpace profile, or searches related to your city and neighborhood, your search history may provide clues to your identity.
While AOL's apology is commendable, its users deserve more than that to help rectify the damage done and to improve privacy-protections in the future.