2011/08/02 by Wing-Kai Hon, Rahul Shah, Hon, Wing-Kai +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Image and Video Retrieval Techniques #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1108.0554
openalex publication_date 2011/08/02 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
Let \D = \d1,d2,...dD\ be a given set of D string documents of total length n, our task is to index \D, such that the k most relevant documents for an online query pattern P of length p can be retrieved efficiently. We propose an index of size |CSA|+nlog D(2+o(1)) bits and O(ts(p)+kloglog n+polyloglog n) query time for the basic relevance metric term-frequency, where |CSA| is the size (in bits) of a compressed full text index of \D, with O(ts(p)) time for searching a pattern of length p . We further reduce the space to |CSA|+nlog D(1+o(1)) bits, however the query time will be O(ts(p)+k(log σloglog n)1+ε+polyloglog n), where σ is the alphabet size and ε>0 is any constant.