کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435554 689915 2016 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Range queries on uncertain data
ترجمه فارسی عنوان
محدوده پرس و جو بر روی داده های نامشخص
کلمات کلیدی
محدوده پرس و جو، داده های نامعلوم، پرس و جوهای بالا نمایش آستانه، ساختارهای داده، الگوریتم ها
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

Given a set P of n uncertain points on the real line, each represented by its one-dimensional probability density function, we consider the problem of building data structures on P to answer range queries of the following three types for any query interval I: (1) top-1 query: find a point in P that lies in I with the highest probability, (2) top-k   query: given any integer k≤nk≤n as part of the query, return the k points in P that lie in I with the highest probabilities, and (3) threshold query: given any threshold τ as part of the query, return all points of P that lie in I with probabilities at least τ. We present data structures for these range queries with linear or nearly linear space and efficient query time.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 609, Part 1, 4 January 2016, Pages 32–48
نویسندگان
, ,