Maximera submodulära funktioner under kardinalitet begränsningar ligger i kärnan av många data mining och maskininlärning applikationer, inklusive datadiversifiering, datasammanfattning, och täckningsproblem. I detta arbete studerar vi denna fråga i samband med dataströmmar, där element anländer en i taget, och vi vill designa lågminnes- och snabbuppdateringsalgoritmer som upprätthåller en bra lösning. Vi fokuserar specifikt på skjutfönstermodellen, där vi uppmanas att upprätthålla en lösning som endast tar hänsyn till de sista W-objekten. I detta sammanhang tillhandahåller vi den första icke-triviala algoritmen som upprätthåller en påvisbar approximation av den optimala användningen av utrymme sublinear i storleken på fönstret. I synnerhet ger vi en 1 /3 − approximationsalgoritm som använder utrymme polylogaritmisk i spridningen av värdena för elementen, 0, och linjär i lösningen storlek k för alla konstant > 0. Samtidigt kräver bearbetningen av varje element endast ett polylogaritmiskt antal utvärderingar av själva funktionen. När en bättre approximation önskas, visar vi en annan algoritm som, till priset av att använda mer minne, ger en 1 /2 - approximation och tillåter en tonfiskble kompromiss mellan genomsnittlig uppdateringstid och utrymme. Denna algoritm matchar de mest kända approximationsgarantier för submodulära optimering i inför-bara strömmar, en mindre allmän formulering av problemet. Vi demonstrerar algoritmernas effektivitet på ett antal verkliga datauppsättningar, vilket visar att deras praktiska prestanda vida överstiger de teoretiska gränserna. Algoritmerna bevarar högkvalitativa lösningar i strömmar med miljontals objekt, samtidigt som de lagrar en försumbar del av dem.
Epasto m.fl. I REF föreslås (1/3 – ε) och (1/2 – ε) approximationsalgoritmer för SM med kardinalitetsbegränsningar för skjutbara fönster.
Submodular Optimization over Sliding Windows
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}