Computer Science – Data Structures and Algorithms
Scientific paper
2010-10-12
Computer Science
Data Structures and Algorithms
Appears in proceedings of the IEEE International Workshop on Knowledge Discovery Using Cloud and Distributed Computing Platfor
Scientific paper
While there has been a lot of work on finding frequent itemsets in transaction data streams, none of these solve the problem of finding similar pairs according to standard similarity measures. This paper is a first attempt at dealing with this, arguably more important, problem. We start out with a negative result that also explains the lack of theoretical upper bounds on the space usage of data mining algorithms for finding frequent itemsets: Any algorithm that (even only approximately and with a chance of error) finds the most frequent k-itemset must use space Omega(min{mb,n^k,(mb/phi)^k}) bits, where mb is the number of items in the stream so far, n is the number of distinct items and phi is a support threshold. To achieve any non-trivial space upper bound we must thus abandon a worst-case assumption on the data stream. We work under the model that the transactions come in random order, and show that surprisingly, not only is small-space similarity mining possible for the most common similarity measures, but the mining accuracy improves with the length of the stream for any fixed support threshold.
Campagna Andrea
Pagh Rasmus
No associations
LandOfFree
On Finding Similar Items in a Stream of Transactions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Finding Similar Items in a Stream of Transactions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Finding Similar Items in a Stream of Transactions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-608442