Group-by och top-k är grundläggande konstruktioner i databasfrågor. Men de kriterier som används för att gruppera och beställa vissa typer av data - såsom omärkta bilder som grupperas av samma person efter ålder - är svåra att utvärdera med hjälp av maskiner. Däremot är dessa uppgifter lätta för människor att utvärdera och är därför naturliga kandidater för att vara crowd-sourced. Vi studerar problemet med att utvärdera top-k och grupp-by-frågor med hjälp av publiken för att svara på antingen typ eller värdefrågor. Med tanke på två dataelement är svaret på en typfråga "ja" om elementen har samma typ och därför tillhör samma grupp eller kluster; svaret på en värdefråga beställer de två dataelementen. Antagandet här är att det finns en underliggande sanning, men att de svar som publiken ger ibland kan vara felaktiga. Vi formaliserar problemen med top-k och group-by i crowd-sourced-inställningen, och ger effektiva algoritmer som garanterat uppnår goda resultat med hög sannolikhet. Vi analyserar den crowd-sourced kostnaden för dessa algoritmer i termer av det totala antalet typ- och värdefrågor, och visar att de är i huvudsak den bästa möjliga. Vi visar också att färre frågor behövs när värden och typer korreleras, eller när felmodellen är en där felet minskar när avståndet mellan de två elementen i den sorterade ordningen ökar.
Davidson et al REF ger teoretiska garantier för aggregering (GROUP BY) frågor, där arbetstagare uppmanas att svara på frågor av formen "är a och b av samma typ".
Using the crowd for top-k and group-by queries
{'venue': "ICDT '13", 'journal': None, 'mag_field_of_study': ['Computer Science']}