Exploratory data analysis problems have recently grown in importance due to the large magnitudes of data being collected by everything from satellites to supermarket scanners. This so-called "data glut" often precludes the effective processing of information for decision-making. These problems can be seen as search problems over massive unstructured spaces. A prototypical problem of this type involves the search, by Department of Defense medical agencies, for a so-called "Desert Storm Syndrome" which involves large amounts of medical data obtained over several years following the Persian Gulf conflict. This data ranges over more than 170 attributes, making the search problem over the attribute space a hard one. We propose the use of genetic algorithms for the attribute search problem, and intertwine it with search algorithms at the detailed data level. Computational results so far strongly suggest that our system has succeeded at the given tasks, requiring relatively few resources. They also have found no indication that a single syndrome or other medical entity is responsible for wide-spread adverse health ramifications among a significant cross-section of Persian Gulf War participants in the CCEP program. There are, however, numerous correlations of exposure/demographic information and associated symptoms/diagnoses which suggest that smaller groups may share common health conditions based on shared exposure to common health risk factors.