Vi beskriver en datastruktur som använder O(n)-word mellanslag och rapporterar k mest relevanta dokument som innehåller ett frågemönster P i optimal O( och P + k) tid. Vår konstruktion stöder en mängd viktiga relevanta åtgärder, såsom frekvensen av P i ett dokument och det minimala avståndet mellan två förekomster av P i ett dokument. Vi visar hur man minskar utrymmet för datastrukturen från O(n log n) till O(n(log σ+log D+log log n)) bitar, där σ är alfabetet storlek och D är det totala antalet dokument.
Det tidsoptimala resultatet av Navarro och Nekrich REF, O(p + k) tid, kräver O(n(lg D + lg σ)) bitar.
Top-k document retrieval in optimal time and linear space
{'venue': 'In Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}