کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4951313 | 1441208 | 2017 | 36 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On the arrangement of stochastic lines in R2
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Consider a set of n stochastic lines in R2, where the existence probability of each line is determined by a fixed probability distribution. For a fixed x-coordinate q, the n lines from top to bottom can be represented by an ordered n-element sequence. Consider all the (nk)k-element sub-sequences of that n-element sequence. Each k-element sub-sequence has an associated likelihood to be the true k-topmost lines at x-coordinate q, and the one with the largest probability is defined as the most likely k-topmost lines at q. This paper studies the most likely k-topmost lines of the arrangement of n lines taken over all the x-coordinates. Let cnt be the total number of distinct sequences of the most likely k-topmost lines over all x-coordinates. The main result established is that the expected value of cnt is O(kn), which implies that it is possible to store all the distinct most likely k-topmost lines in O(k2n) expected space. An example is given showing that cnt, in the worst case, can be Î(n2) even when k=1. This highlights the value of the expected bound. An algorithm is also given to compute the most likely k-topmost lines of the arrangement. Applications of this result to the stochastic Voronoi Diagram in R1 and to the stochastic preference top-k query in R2 are discussed.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 44, May 2017, Pages 1-20
Journal: Journal of Discrete Algorithms - Volume 44, May 2017, Pages 1-20
نویسندگان
Yuan Li, Jie Xue, Akash Agrawal, Ravi Janardan,