دانلود مقاله ترجمه شده تست کولموگروف اسمیرنوف و الگوریتم جریان داده – مجله IEEE

مشخصات مقاله انگلیسی (PDF)
سال انتشار	۲۰۱۵
تعداد صفحات مقاله انگلیسی	۱۰ صفحه با فرمت pdf
رشته های مرتبط با این مقاله	آمار و مهندسی کامپیوتر
گرایش های مرتبط با این مقاله	مهندسی الگوریتم ها و محاسبات و آمار ریاضی
مجله	کنفرانس بین المللی بزرگ داده (داده بزرگ)
دانشگاه	گروه ریاضی و علوم کامپیوتر، دانشگاه دنیسون گرانویل، ایالات متحده آمریکا
شناسه شاپا یا ISSN	ISSN ۹۷۸-۱-۴۷۹۹-۹۹۲۵-۵
رفرنس	دارد
لینک مقاله در سایت مرجع	لینک این مقاله در سایت IEEE
نشریه آی تریپل ای

• فهرست مطالب:

چکیده
مقدمه
A.کاربردها
نجوم
شبکه های حس گر بی سیم
اندازه گیری ترافیک اینترنت
B.همکاری
تشکیلات
کارمرتبط
پیش مقدمه
۱-تعریف مسئله
B. طرح های چندک
آزمون یک نمونه ای
A.آزمون دونمونه ای
آزمون دونمونه ای
A. تحلیل محاسباتی
A. الگوریتم دونمونه ای
B. تحلیل محاسباتی
انتخاب ϵ
ارزیابی تجربی
تک نمونه
دو نمونه
نتایج
تک نمونه
دو نمونه

• بخشی از ترجمه:

  نتایج
دراین مقاله مسئله عملکرد آزمون KS برروی جریان داده را درنظرگرفتیم. ما الگوریتم هایی برای هردو نسخه یک نمونه ای و دونمونه ای همراه با تضمین عملکرد آنها ارائه کردیم. الگوریتم های ما ازتکنیک هایی برای محاسبه چندک ها درجریان استفاده می کنند و ازاین رو، ممکن است نتایج بهتری وقتی پیشرفت بیشتری برروی این مسئله رخ دهد، داشته باشند. علاوه برآن، ما با آزمایش برروی داده واقعی و ترکیبی نشان می دهیم که الگوریتم های پیشنهادشده قادرند آزمون را با کاهش دودرجه بزرگی در اندازه داده انجام دهند. همچنین آزمایشات ما نشان می-دهد که طرح GK بهترین تطبیق را برای الگوریتم ما دارد و به طور چشمگیری نسبت به دیگر تکنیک ها نظیر نمونه سازی برتری دارد.
چندین مسئله بازدیگر هنوز باقی مانده است. الگوریتم های پیشنهادشده دراین مقاله نیازبه نمونه های O(√n log⁡n) دارد وباز باقی می ماند تا وقتی این مورد بیشتر کاهش یابد. اگرچه الگوریتم پیشنهادشده در این مقاله ازطرح های چندک استفاده می کند، وازاین رو فضای استفاده یکسانی همچون آنها دارد، اما وجود الگوریتم تست شده که ازفضای کمتر مجانبی نسبت به دیگرطرح های چندک استفاده کند، نامعلوم است. پیداکردن چنین الگوریتمی یا متعاقبا اثبات اینکه هرطرح چندک باید از فضای بیشتری همچون تست الگوریتم استفاده کند، جالب خواهدبود. باتوجه به آزمایشات، طراحی دیگر الگوریتم های چندک که به سمت بهبود دقت نتایج الگوریتم آزمون KS در این مقاله هدف گیری کنند، نیز جالب خواهد بود.
همچنین بسیاری ازآزمون های عددی دیگر، هم پارامتری و هم غیرپارامتری، وجود دارد که الگوریتم های جریانی مشخصی ندارند. شناسایی اینکه کدام یک الگوریتم های فضای زیرخطی دارند و توسعه این الگوریتم ها زمینه دیگری برای تحقیقات آینده می باشد.

• بخشی از مقاله انگلیسی:

VIII. CONCLUSIONS

In this paper, we considered the problem of performing the Kolmogorov-Smirnov test on streaming data. We gave algorithms for both the one-sample and the two-sample versions of the test, along with guarantees of their performance. Our algorithms make use of the techniques for computing quantiles on a stream and hence may have improved results when further progress is made on this problem. Moreover, we show via experiments on real and synthetic data that the proposed algorithms are capable of performing the test with a two order magnitude reduction in the size of the data. Our experiments also showed that the Greenwald-Khanna sketch is best suited for our algorithm, and that it is considerably 104 superior to other simple techniques such as sampling.

There are several open problems that still remain. The algorithms proposed in this paper need O( √n log n) samples, and it remains open whether this can be further reduced. While the algorithm proposed in this paper makes use of quantile sketches, and hence has the same space usage as them, it is unclear whether a testing algorithm exists that uses asymptotically less space than any quantile sketch. It would be interesting to find such an algorithm, or alternatively to prove that any quantile sketch must use as much space as any testing algorithm. From the experimental side, it would be interesting to design other quantile algorithms that are targeted towards improving the accuracy of the result of the KS test algorithm in this paper.

There are also many other statistical tests, both parametric and non-parametric, that do not have known streaming algorithms. Identifying which ones have sublinear space algorithms and developing these algorithms is another avenue for future work.

دانلود رایگان مقاله انگلیسی

خرید ترجمه فارسی مقاله