Även om det har varit en hel del arbete på att hitta frekventa artiklar i transaktionsdata strömmar, ingen av dessa löser problemet med att hitta liknande par enligt standard liknande åtgärder. Detta dokument är ett första försök att ta itu med detta, tveklöst viktigare, problem. Vi börjar med ett negativt resultat som också förklarar bristen på teoretiska övre gränser för rymdanvändning av data mining algoritmer för att hitta frekventa objekt: Alla algoritmer som (även om det bara är ungefär och med en risk för fel) finner den mest frekventa k-objektet måste använda utrymme  och (min {mb, n k, (mb) k }) bitar, där mb är antalet objekt i strömmen hittills, n är antalet distinkta objekt och ∂ är en stödtröskel. För att uppnå en icke-trivial rymd övre gräns måste vi därför överge ett värsta-fall antagande på dataströmmen. Vi arbetar under modellen att transaktionerna kommer i slumpmässig ordning, och visar att överraskande, inte bara är små utrymme likhet gruvdrift möjligt för de vanligaste likhetsåtgärder, men gruvnoggrannheten förbättras med längden på strömmen för varje fast stöd tröskel.
Campagna och Pagh REF gör utan tvekan svagare, men fortfarande tveksamt, antagandet att ordningen för transaktionerna i strömmen är slumpmässig.
On Finding Similar Items in a Stream of Transactions
{'venue': '2010 IEEE International Conference on Data Mining Workshops', 'journal': '2010 IEEE International Conference on Data Mining Workshops', 'mag_field_of_study': ['Computer Science', 'Mathematics']}