Non-zero probability of nearest neighbor searching | ||
| Journal of AI and Data Mining | ||
| مقاله 10، دوره 5، شماره 1، خرداد 2017، صفحه 101-109 اصل مقاله (1.55 M) | ||
| نوع مقاله: Original/Review Paper | ||
| شناسه دیجیتال (DOI): 10.22044/jadm.2016.733 | ||
| نویسندگان | ||
| A. Mesrikhani* ؛ M. Davoodi | ||
| Department of Computer Science & Information Technology, Institute for Advanced Studies in Basic Sciences (IASBS), Zanjan, Iran. | ||
| چکیده | ||
| Nearest Neighbor (NN) searching is a challenging problem in data management and has been widely studied in data mining, pattern recognition and computational geometry. The goal of NN searching is efficiently reporting the nearest data to a given object as a query. In most of the studies both the data and query are assumed to be precise, however, due to the real applications of NN searching, such as tracking and locating services, GIS and data mining, it is possible both of them are imprecise. So, in this situation, a natural way to handle the issue is to report the data have a nonzero probability —called nonzero nearest neighbor— to be the nearest neighbor of a given query. Formally, let P be a set of n uncertain points modeled by some regions. We first consider the following variation of NN searching problem under uncertainty. If both the query and the data are uncertain points modeled by distinct unit segments parallel to the x-axis, we propose an efficient algorithm that reports nonzero nearest neighbors under Manhattan metric in O(n^2 α(n^2 )) preprocessing and O(logn+k) query time, where α(.) is the extremely slowly growing functional inverse of Ackermann’s function. Finally, for the arbitrarily length segments parallel to the x-axis, we propose an approximation algorithm that reports nonzero nearest neighbor with maximum error L in O(n^2 α(n^2 )) preprocessing and O(logn+k) query time, where L is the length of the query. | ||
| کلیدواژهها | ||
| Nearest neighbor searching؛ Uncertainty؛ Imprecision؛ Nonzero probability | ||
|
آمار تعداد مشاهده مقاله: 2,584 تعداد دریافت فایل اصل مقاله: 2,381 |
||