The government's ability to obtain and analyze recorded information about its citizens through the process known as data mining has expanded enormously over the past decade. Although the best-known government data mining operation (Total Information Awareness, more recently dubbed Terrorism Information Awareness) supposedly no longer exists, large-scale data mining by federal agencies devoted to enforcing criminal and counter-terrorism laws has continued unabated. This paper addresses three puzzles about data mining. First, when data mining is undertaken by the government, does it implicate the Fourth Amendment? Second, does the analysis change when data mining is undertaken by private entities which then make the data or data analysis available to the government? Third, if the Fourth Amendment does impose some restrictions on government data mining, what might they look like? Current Fourth Amendment jurisprudence appears to leave data mining completely unregulated, while most commentators have called for stringent regulation or a prohibition on large-scale operations such as TIA. This paper takes an intermediate position on these issues. The proposed framework requires attention to the type of records obtained via the data mining, the extent to which they can be connected to particular individuals, and the government's goal in obtaining them. Based on proportionality reasoning that I have applied in other contexts, the highest degree of justification for data mining should be required when the data is private in nature and sought in connection with investigation of a particular target. In contrast, data mining that relies on impersonal or anonymized records, or that is sought in an effort to identify a perpetrator of a past or future event, need not as strictly regulated. In aid of this project, I describe a study that investigated lay views on data mining.