کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428971 | 686978 | 2013 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Top-k document retrieval in optimal space
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
• We present an index for top-k most frequent document retrieval whose space is |CSA|+o(n)+DlognD+O(D) bits.
• The space complexity is better than previous results for the problem.
• The index is based on an index of Belazzougui and Navarro.
We present an index for top-k most frequent document retrieval whose space is |CSA|+o(n)+DlognD+O(D) bits, and its query time is O(logklog2+ϵn) per reported document, where D is the number of documents, n is the sum of lengths of the documents, and |CSA||CSA| is the space of the compressed suffix array for the documents. This improves over previous results for this problem, whose space complexities are |CSA|+ω(n)|CSA|+ω(n) or 2|CSA|+ω(1)2|CSA|+ω(1).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 113, Issue 12, 30 June 2013, Pages 440–443
Journal: Information Processing Letters - Volume 113, Issue 12, 30 June 2013, Pages 440–443
نویسندگان
Dekel Tsur,