This story from the Electronic Frontier Foundation highlights research that indicates that some ones true identity can often be determined with just the person’s gender, ZIP code, and birth date. According to the CMU study there is a %87 chance that your gender, ZIP code, and birth date are unique.
What is interesting about this is that this kind of data is routinely included in medical records that have been stripped of other personally identifying information (PII) to comply with HIPAA.