کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10321312 | 659322 | 2005 | 19 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An approximate algorithm for top-k closest pairs join query in large high dimensional data
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: An approximate algorithm for top-k closest pairs join query in large high dimensional data An approximate algorithm for top-k closest pairs join query in large high dimensional data](/preview/png/10321312.png)
چکیده انگلیسی
In this paper we present a novel approximate algorithm to calculate the top-k closest pairs join query of two large and high dimensional data sets. The algorithm has worst case time complexity O(d2nk) and space complexity O(nd) and guarantees a solution within a O(d1+1t) factor of the exact one, where t â {1, 2, â¦Â , â} denotes the Minkowski metrics Lt of interest and d the dimensionality. It makes use of the concept of space filling curve to establish an order between the points of the space and performs at most d + 1 sorts and scans of the two data sets. During a scan, each point from one data set is compared with its closest points, according to the space filling curve order, in the other data set and points whose contribution to the solution has already been analyzed are detected and eliminated. Experimental results on real and synthetic data sets show that our algorithm behaves as an exact algorithm in low dimensional spaces; it is able to prune the entire (or a considerable fraction of the) data set even for high dimensions if certain separation conditions are satisfied; in any case it returns a solution within a small error to the exact one.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Data & Knowledge Engineering - Volume 53, Issue 3, June 2005, Pages 263-281
Journal: Data & Knowledge Engineering - Volume 53, Issue 3, June 2005, Pages 263-281
نویسندگان
Fabrizio Angiulli, Clara Pizzuti,