De flesta databashanteringssystem upprätthåller statistik över det underliggande förhållandet. En av de viktigaste statistikerna är den om de "heta posterna" i relationen: de som förekommer många gånger (oftast, eller mer än någon tröskel). End-biased histograms behåller till exempel de heta objekten som en del av histogrammet och används i selektivitetsbedömning. Varma föremål används som enkla avvikelser i datautvinning, och i anomali upptäckt i många tillämpningar. Vi presenterar nya metoder för dynamisk bestämning av heta objekt när som helst i ett förhållande som genomgår raderingsåtgärder samt infogar. Våra metoder upprätthåller små rymddatastrukturer som övervakar transaktionerna i relationen och, vid behov, snabbt matar ut alla heta objekt utan att ändra relationen i databasen. Med användarspecificerad sannolikhet rapporteras alla heta objekt korrekt. Våra metoder bygger på idéer från "grupptester". De är enkla att genomföra och har bevisbar kvalitet, utrymme och tidsgarantier. Tidigare kända algoritmer för detta problem som gör liknande kvalitet och prestanda garantier kan inte hantera raderingar, och de som hanterar raderingar kan inte göra liknande garantier utan att skanna databasen. Våra experiment med verkliga och syntetiska data visar att våra algoritmer är korrekta i dynamisk spårning av de heta objekten oberoende av graden av insättningar och raderingar.
I REF föreslås GroupTest-algoritmen, som upprätthåller en liten rymddatastruktur som övervakar transaktionerna i relationen, och vid behov snabbt matar ut alla heta objekt, utan att återscanna relationen i databasen.
What's hot and what's not: tracking most frequent items dynamically
{'venue': 'TODS', 'journal': None, 'mag_field_of_study': ['Computer Science']}