De flesta tekniker för datareduktion för ungefärlig frågebehandling (t.ex. wavelets, histograms, kärnor och så vidare) är vanligtvis inte tillämpliga på kategoriska data. Det har varit något av en koppling mellan forskning inom detta område och verkligheten av databasdata; mycket färsk forskning har fokuserat på ungefärlig frågebehandling över beställda eller numeriska attribut, men utan tvekan majoriteten av databasattribut är kategoriska: land, stat, job_title, färg, sex, avdelning, och så vidare. I detta dokument behandlas problemet med tillnärmning av aggregerade funktioner över kategoriska uppgifter eller blandade kategoriska/numeriska uppgifter. Vi föreslår en metod baserad på slumpmässig provtagning, kallad ungefärlig pre-aggregation (APA). Den största nackdelen med provtagning för beräkning av aggregerad funktion är provtagningens känslighet för att tillskriva värdeskala, och APA använder flera tekniker för att övervinna denna känslighet. Den ökade noggrannheten med APA jämfört med "vanlig vanilj" provtagning är dramatisk. För SUM- och AVG-frågor är det relativa felet för enbart slumpmässig provtagning mer än 700 % större än för provtagning med APA. Även om stratifierade provtagningsmetoder används är felet fortfarande mellan 28 % och 175 % större än för APA. Ungefärlig frågesvar har fått mycket ny forskning uppmärksamhet från datahantering gemenskapen. Betydelsen av tillnärmning som ett område för databasforskning har ökat avsevärt genom uppkomsten av beslutsstödsystem (DSS) som ett grundläggande tillämpningsområde för databasteknik. Två egenskaper som är specifika för sådana system gör DSS till ett potentiellt område där approximeringsmetoder kan användas. •För det första, DSS arkiv många gigabyte eller terabyte av data (ofta på beställning av miljarder poster), och så exakta frågesvar kan vara mycket dyrt. •För det andra, frågor över DSS är vanligtvis aggregerade frågor, och därmed låna sig till numerisk approximation. En stor del av arbetet inom detta område har kretsat kring den ungefärliga utvärderingen av aggregerade frågor av formuläret: SELECT AGG_FUNC (TBL.MEAS_ATT) från den_TABELL TBL där TBL.SEL_ATT_1 MELLAN (N1_LOW OCH N1_HI) OCH TBL.SEL_ATT_2 MELLAN (N2_LOW OCH N2_HI) OCH... I de flesta arbeten har man antagit att den datamodell som ställs över är något liknande en multidimensionell datakub. I denna modell finns D- markeringsattribut, av vilka någon kan visas i Where-klausulen i frågan. Dessa attribut partitionerar datautrymmet till en D-dimensionell kub. Utöver markeringsattributen finns det en uppsättning mätattribut på vilka olika aggregerade funktioner kan tillämpas i SELECT-klausulen i frågan. Varje tuple i databasen avbildas till en cell i datakuben baserat på värdena för den tuples markeringsattribut, och värdena för den tuples olika måttattribut skrivs in i cellen. Frågar sedan beräkna aggregerade funktioner (såsom SUM, AVG, COUNT, etc.) över olika lågdimensionella projektioner av de mätattribut som lagras i kuben. Ett nyckelantagande i en stor del av arbetet inom detta område är att de attribut som visas i Where-klausulen antingen är numeriska eller har diskretiserats till en uppsättning hinkar som har en meningsfull beställning. I detta fall kan man välja mellan många föreslagna approximeringsmetoder. Exempel är multidimensionella histogram [18], wavelets [20], och kärnskattningar [13], bland annat. Ett problem med dessa approximeringsmetoder är att data ofta har attribut som verkligen är kategoriska. Ett exempel på detta är attributet land (med möjliga värden USA, Kanada, Frankrike, etc.). Dessa värden är inte numeriska, och det är svårt att införa en beställning på dem som möjliggör en meningsfull nedbrytning av data I detta fall kan vi ha ökat vår data dimensionalitet från tre till 500 attribut, vilket sannolikt är långt mer än någon av de nämnda approximativa metoder kan hantera. Enligt Gunopulos et al. är det tveksamt om någon av dessa metoder konsekvent kan fungera i mer än tio dimensioner [13].
Ungefärlig pre-aggregation REF (APA) använder ett slumpmässigt urval kombinerat med en liten uppsättning statistik om data för att öka noggrannheten.
Robust Estimation With Sampling and Approximate Pre-Aggregation
{'venue': 'VLDB', 'journal': None, 'mag_field_of_study': ['Computer Science']}