کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951302 | 1441209 | 2017 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Range selection and predecessor queries in data aware space and time
ترجمه فارسی عنوان
محدوده انتخاب و پیش نمایش داده ها در فضای زمان و اطلاعات آگاه است
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
ساختارهای داده، محدوده جستجو، جستجوی پیشین، متراکم سازی داده ها،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
On a given vector X=ãx1,x2,â¦,xnã of integers, the range selection (i,j,k) query is finding the k-th smallest integer in ãxi,xi+1,â¦,xjã for any (i,j,k) such that 1â¤iâ¤jâ¤n, and 1â¤kâ¤jâi+1. Previous studies on the problem proposed data structures that occupied additional O(nâ
logâ¡n) bits of space over the X itself that answer the queries in logarithmic time. In this study, we replace X and encode all integers in it via a single wavelet tree by using S=nâ
logâ¡u+âlogâ¡xi+o(nâ
logâ¡u+âlogâ¡xi) bits, where u is the number of distinct âlogâ¡xiâ values observed in X. Notice that u is at most 32 (64) for 32-bit (64-bit) integers and when xi>u, the space used for xi in the proposed data structure is less than the Elias-δ coding of xi. Besides data-aware coding of X, the range selection is performed in O(logâ¡u+logâ¡xâ²) time where xâ² is the k-th smallest integer in the queried range. This result is adaptive and achieves the range selection regardless of the size of X, and the time-complexity depends on the answer itself. Additionally, we can answer range predecessor queries (i,j,xâ²): return the largest element yâ¤xâ² in ãxi,xi+1,â¦,xjã, in O(logâ¡u+logâ¡xâ²) time. In summary, to the best of our knowledge, we present the first algorithms using data-aware space and time for the general range selection and predecessor problems.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 43, March 2017, Pages 18-25
Journal: Journal of Discrete Algorithms - Volume 43, March 2017, Pages 18-25
نویسندگان
M. OÄuzhan Külekci, Sharma V. Thankachan,