Abstract-Ges en uppsättning D = {d1, d2,..., dD} av D strängar av total längd n, är vår uppgift att rapportera de "mest relevanta" strängar för en given frågemönster P. Detta innebär något mer avancerad frågefunktionalitet än den vanliga mönster matchning, eftersom vissa begrepp om " mest relevanta" är inblandade. I litteraturen för informationssökning uppnås denna uppgift bäst genom att använda omvända index. Inverterade index fungerar dock endast för vissa fördefinierade uppsättningar mönster. I den mönstermatchande gemenskapen är de mest populära mönstermatchande datastrukturerna suffixträd och suffixmatriser. Men en typisk suffix trädsökning innebär att gå igenom alla förekomster av mönstret över hela strängsamlingen, vilket kan vara mycket mer än de nödvändiga relevanta dokumenten. Den första formella ramen för att studera sådana problem gavs av Muthukrishnan [25]. Han övervägde två mått för relevans: frekvens och närhet. Han tog en tröskelbaserad metod på dessa mätvärden och gav datastrukturer med O(n log n) ord i rymden. Vi studerar detta problem i en något annorlunda ram för att rapportera de högsta k mest relevanta dokumenten (i sorterad ordning) under liknande och mer allmänna relevansmått. Vårt ramverk ger linjär rymddatastruktur med optimala frågetider för godtyckliga poängfunktioner. Som en följd av detta förbättrar det utnyttjandet av utrymme för problemen i [25] samtidigt som optimal frågeprestanda upprätthålls. Vi utvecklar även komprimerade varianter av dessa datastrukturer för flera specifika relevansmått.
I samma anda, datastrukturer för det mer allmänna problemet med substring matchning för top-k hämtning har beaktats i REF.
Space-Efficient Framework for Top-k String Retrieval Problems
{'venue': '2009 50th Annual IEEE Symposium on Foundations of Computer Science', 'journal': '2009 50th Annual IEEE Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Computer Science']}