Vi undersöker problemet med att generera snabbt ungefärliga svar på frågor som ställs till stora glesa binära datamängder. Vi fokuserar särskilt på probabilistiska modellbaserade tillvägagångssätt för detta problem och utvecklar ett antal tekniker som är betydligt mer exakta än en grundmodell för oberoende. I synnerhet introducerar vi två tekniker för att bygga probabilistiska modeller från frekventa objekt: objektet maximal entropi metod, och objektet inkludering-exklusion modell. I den maximala entropimetoden behandlar vi objekten som begränsningar av fördelningen av frågevariablerna och använder den maximala entropiprincipen för att bygga en gemensam sannolikhetsmodell för frågeattributen online. I inclusion-exklusion modell objektet och deras frekvenser lagras i en datastruktur som kallas en ADtree som stöder ett effektivt genomförande av inclusion-exklusion princip för att svara på frågan. Vi jämför empiriskt dessa två itemset-baserade modeller med direkt förfrågan av de ursprungliga data, förfrågan av prover av de ursprungliga data, liksom andra probabilistiska modeller såsom självständighetsmodellen, Chow-Liu trädmodellen, och Bernoulli blandningsmodell. Dessa modeller kan hantera högdimensionellitet (hundratals eller tusentals attribut), medan de flesta andra arbeten inom detta ämne har fokuserat på relativt lågdimensionella OLAP-problem. Experimentella resultat på både simulerade och verkliga transaktionsdata visar olika grundläggande avvägningar mellan approximativa fel, modell komplexitet och den online-tid som krävs för att beräkna ett frågesvar.
Vi kan anta att göra en uppskattning av de selektiva frågor genom att använda den maximala entropimetoden är mer exakt än andra modeller REF.
Beyond Independence: Probabilistic Models for Query Approximation on Binary Transaction Data
{'venue': 'IEEE Transactions on Knowledge and Data Engineering', 'journal': None, 'mag_field_of_study': ['Computer Science']}