Vi introducerar och studerar problemet med att beräkna likheten själv-join i ett strömmande sammanhang (ssj), där indata är en obegränsad ström av objekt som anländer kontinuerligt. Målet är att hitta alla par av objekt i strömmen vars likhet är större än en given tröskel. Den enklaste formuleringen av problemet kräver obegränsat minne, och därför är det oåtkomligt. För att göra problemet genomförbart introducerar vi begreppet tidsberoende likhet: likheten mellan två punkter minskar med skillnaden i ankomsttid. Genom att utnyttja egenskaperna hos denna tidsberoende likhetsfunktion utformar vi två algoritmiska ramar för att lösa sssj-problemet. Den första, MiniBatch (MB), använder befintliga indexbaserade filtreringstekniker för den statiska versionen av problemet, och kombinerar dem i en pipeline. Den andra ramen, Streaming (STR), lägger till tidsfiltrering till befintliga index, och integrerar nya tidsbaserade gränser djupt i arbetet med algoritmerna. Vi introducerar också en ny indexeringsteknik (L2), som bygger på en befintlig toppmodern indexeringsteknik (L2AP), men är optimerad för streamingfallet. Omfattande experiment visar att STR-algoritmen, när den instanteras med L2-indexet, är det mest skalbara alternativet över ett brett spektrum av datauppsättningar och parametrar.
Morales m.fl. REF-studie en likhet ansluter där uppsättningarna anländer i en ström.
Streaming Similarity Self-Join
{'venue': 'PVLDB', 'journal': 'PVLDB', 'mag_field_of_study': ['Computer Science']}