A method estimates similarities in data streams. A data source receives input vectors from users. A sketch feature generator converts the input vectors into sketch feature vectors corresponding to the users, wherein each sketch feature vector represents data and meta-information from each user received in a most recent sample period. A similarity comparator compares each sketch feature vector against other sketch feature vectors to calculate similarity probabilities between the users. A processor running a decision loop determines a prediction result for at least one user based on the similarity probabilities.