Med explosionen av Internet, LDAP-kataloger och XML, finns det ett allt större behov av att utvärdera frågor som involverar (under)sträng matchning. Effektiv frågeoptimering i detta sammanhang kräver goda selektivitetsbedömningar. I detta papper använder vi beskurna greve-suffix träd som grundram för substring selektivitet uppskattning. Vi presenterar en ny teknik för att få en bra uppskattning för en given substring matchande fråga, kallad MO (för Maximal Overlap), som uppskattar selektiviteten av en fråga baserat på alla maximala substrängar av frågan i den beskurna count-suffix träd. Vi visar att MO är bevisligen bättre än (oberoende-baserad) substring selektivitet estimering teknik föreslås av Krishnan et al. [6], kallad KVI, under det naturliga antagandet att strängar uppvisar den så kallade "korta minnes" egenskapen. Vi kompletterar vår analys med ett experiment, med hjälp av en riktig AT&T datauppsättning, som visar att MO är betydligt bättre än KVI i kvaliteten på uppskattningen. Slutligen utvecklar och analyserar vi två selektivitetsskattningsalgoritmer, MOC och MOLC, baserade på MO och en begränsningsbaserad karakterisering av alla möjliga kompletteringar av ett givet beskurna räkna-suffix träd. Vi visar att KVI, MO, MOC och MOLC illustrerar en intressant avvägning mellan uppskattningsnoggrannhet och beräkningseffektivitet.
Jagadish m.fl. REF presenterade en annan selektivitetsskattningsalgoritm som MO, MOC och MOLC med användning av samma CS-träd.
Substring selectivity estimation
{'venue': "PODS '99", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}