A method, system and computer program product for providing privacy protection to data streams in a distributed computing environment. The method includes concurrently processing, by a plurality of computer machines, data streams of attributes containing data values received by each of the plurality of local computer machines; indexing the data values for each attribute of the plurality of data streams received by each of the plurality of local computer machines; providing the indexed data values to a main computer machine; integrating, by the main computer machine, the local computer machine indexed data values into a global index data structure for the plurality of data streams; and identifying privacy vulnerabilities of the attributes that are direct identifiers and quasi-identifiers based on the global index.