Abstrakt. Ett klassiskt problem i frågeoptimering är att hitta den optimala beställningen av en uppsättning eventuellt korrelerade urval. Vi ger en abstraktion av detta problem som en generalisering av set cover som kallas pipeled set cover, där uppsättningarna tillämpas sekventiellt på de element som ska täckas och de element som omfattas i varje steg kastas. Vi visar att flera naturliga heuristiker för detta NP-hårda problem, såsom den giriga set-cover heuristic och en lokal-search heuristic, kan analyseras med hjälp av en linjär-programmering ram. Dessa heuristik leder till effektiva algoritmer för pipeled set täcker som kan tillämpas på ordning eventuellt korrelerade val i konventionella databassystem samt dataström bearbetningssystem. Vi använder vårt linjära programramverk för att visa att de giriga och lokala sök algoritmerna är 4 approximationer för piped set cover. Vi utökar vår analys för att minimera lp-normen för de kostnader som betalas av uppsättningarna, där p ≥ 2 är ett heltal, för att undersöka förbättringen av prestanda när den totala kostnaden har ökat bidraget från inledande uppsättningar i rörledningen. Slutligen anser vi att online-versionen av piped set cover och presentera en konkurrenskraftig algoritm med en logaritmisk prestandagaranti. Vårt analysramverk kan vara tillämpligt på andra problem i frågeoptimering där det är viktigt att redovisa korrelationer. En vanlig åtgärd i databas frågebehandling är att hitta delmängd poster i ett förhållande som uppfyller en viss uppsättning av urvalskriterier. För att utföra denna operation effektivt, föredrar en frågeprocessor att bestämma den optimala ordningen för att utvärdera de enskilda urvalsvillkoren, så vi kallar denna operation rörledningsfilter [2, 4, 12, 18]. Optimalitet i rörledningar filter är vanligtvis med avseende på att minimera den totala bearbetningstiden [4, 12]. Till exempel, överväga ett relationspaket, där varje post innehåller huvudet och en inledande del av nyttolasten för nätverkspaket som loggas av ett nätverk
Munagalas arbete m.fl. REF överväger att beställa urvalsgrunder genom att anta approximationsalgoritmer som den set cover problemalgoritmen, myntad piped set cover.
The pipelined set cover problem
{'venue': None, 'journal': None, 'mag_field_of_study': ['Computer Science']}