Sammanfattning Att hitta typiska fall är ett effektivt sätt att förstå och analysera stora datamängder. I den här artikeln tillämpar vi idén om typiska analyser från psykologi och kognitiv vetenskap för att svara på databasfrågor, och studerar det nya problemet med att svara på top-k-typiska frågor. Vi modellerar typiskt i stora datamängder systematiskt. Tre typer Detta dokument är en betydande förlängning av konferensversionen [32]. Forskningen av Ming Hua och Jian Pei stöds delvis av ett NSERC Discovery-bidrag och ett NSERC Discovery Accelerator Tilläggsbidrag. Forskningen av Xuemin Lin stöds delvis av Australian Research Council Discovery Grants DP0987557, DP0881035 och DP0666428 och ett Google forskningspris. Alla synpunkter, resultat, slutsatser och rekommendationer i detta dokument är upphovsmännens och återspeglar inte nödvändigtvis finansiärernas åsikter. Vi är tacksamma mot de anonyma recensenterna och dr Peter Haas, den biträdande redaktören, för deras konstruktiva kommentarer som bidrar till att förbättra papperets kvalitet avsevärt. Vi tackar dem särskilt för deras råd när det gäller att förbättra den matematiska utställningen och deras förslag om ett viktigt relaterat arbete. av top-k typiska frågor är formulerade. För att svara på frågor som "Vilka är top-k mest typiska NBA-spelare?", är måttet på enkel typiskhet utvecklas. För att svara på frågor som "Vilka är top-k mest typiska vakter som skiljer vakter från andra spelare?"föreslås begreppet diskriminerande typiskhet. Dessutom, för att svara på frågor som "Vilka är de bästa k typiska vakter i hela representerar olika typer av vakter?", används begreppet representativ typiskhet. Att beräkna det exakta svaret på en top-k-typisk fråga kräver kvadratisk tid som ofta är för kostsamt för online-fråga svar på stora databaser. Vi utvecklar en serie approximativa metoder för olika situationer: (1) den randomiserade turneringsalgoritmen har linjär komplexitet även om den inte ger en teoretisk garanti på kvaliteten på svaren; (2) den direkta lokala typiska approximationen med hjälp av VP-träd ger en approximativ kvalitetsgaranti; (3) en lokal typisk träddatastruktur kan utnyttjas för att indexera en stor uppsättning objekt. Då kan typiska frågor besvaras effektivt med kvalitetsgarantier genom en turneringsmetod baserad på en lokal typitet Tree. En omfattande prestandastudie med hjälp av två verkliga dataset och en serie syntetiska dataset visar tydligt att top-k typiska frågor är meningsfulla och våra metoder är praktiska. M. Hua (B)·
Hua m.fl. REF införde en ny top-k-typisk fråga, som rankar objekt efter deras typiska egenskaper i en datauppsättning eller en klass av objekt.
Top-k typicality queries and efficient query answering methods on large databases
{'venue': 'The VLDB Journal', 'journal': 'The VLDB Journal', 'mag_field_of_study': ['Computer Science']}