در این پایان نامه در زمینه الگوریتم های تجزیه و تحلیل داده ها (Analytics) بر روی داده های بزرگ یا داده های حجیم و یا کلان داده ها (Big Data) صحبت شده است. به علت حجم زیاد این داده ها پردازش آنها در حافظه اصلی ممکن نیست و یا زمان زیادی نیاز دارد. برای حل این مشکل از داده ها نمونه برداری (Sampling) انجام میشود. تئوری ها و الگوریتم های مختلف در این پایان نامه بررسی و مورد تجزیه و تحلیل قرار گرفته است.
این پایان نامه در سال 2014 برای اخذ مدرک دکترای کامپیوتر از دانشگاه براون (Brown) در رود آیلند (Rhode Island) آمریکا ارائه شده است.
تعداد صفحات: 189
فهرست مطالب:
1 Introduction 1
1.1 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Overview of contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 The Vapnik-Chervonenkis Dimension 6
2.1 Use of VC-Dimension in computer science . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Range spaces, VC-dimension, and sampling . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Computational considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3 Mining Association Rules and Frequent Itemsets 14
3.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3 The dataset’s range space and its VC-dimension . . . . . . . . . . . . . . . . . . . . 22
3.3.1 Computing the d-index of a dataset . . . . . . . . . . . . . . . . . . . . . . . 27
3.3.2 Speeding up the VC-dimension approximation task . . . . . . . . . . . . . . . 30
3.3.3 Connection with monotone monomials . . . . . . . . . . . . . . . . . . . . . . 31
3.4 Mining (top-K) Frequent Itemsets and Association Rules . . . . . . . . . . . . . . . 32
3.4.1 Mining Frequent Itemsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4.2 Mining top-K Frequent Itemsets . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.4.3 Mining Association Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4.4 Other interestingness measures . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4.5 Closed Frequent Itemsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.5 Experimental evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4 PARMA: Mining Frequent Itemsets and Association Rules in MapReduce 50
4.1 Previous work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2.1 MapReduce . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3 Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.3.1 Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.3.2 Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.3.3 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.3.4 Top-K Frequent Itemsets and Association Rules . . . . . . . . . . . . . . . . . 62
4.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.5 Experimental evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.5.1 Performance analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.5.2 Speedup and scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.5.3 Accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
4.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5 Finding the True Frequent Itemsets 74
5.1 Previous work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.3 The range space of a collection of itemsets . . . . . . . . . . . . . . . . . . . . . . . . 81
5.3.1 Computing the VC-Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . 82
5.4 Finding the True Frequent Itemsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.5 Experimental evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
6 Approximating Betweenness Centrality 92
6.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
6.2 Graphs and betweenness centrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
6.3 A range space of shortest paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.3.1 Tightness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
6.4 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
6.4.1 Approximation for all the vertices . . . . . . . . . . . . . . . . . . . . . . . . 103
6.4.2 High-quality approximation of the top-K betweenness vertices . . . . . . . . 109
6.4.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
6.5 Variants of betweenness centrality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.5.1 k-bounded-distance betweenness . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.5.2 -weighted betweenness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
6.5.3 k-path betweenness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
6.5.4 Edge betweenness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.6 Experimental evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
6.6.1 Accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
6.6.2 Runtime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
6.6.3 Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
6.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
7 Estimating the Selectivity of SQL Queries 126
7.1 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
7.2 Database queries and selectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
7.3 The VC-dimension of classes of queries . . . . . . . . . . . . . . . . . . . . . . . . . . 133
7.3.1 Select queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
7.3.2 Join queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
7.3.3 Generic queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
7.4 Estimating query selectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
7.4.1 The general scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
7.4.2 Building and using the sample representation . . . . . . . . . . . . . . . . . . 140
7.5 Experimental evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
7.5.1 Selectivity estimation with histograms . . . . . . . . . . . . . . . . . . . . . . 143
7.5.2 Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
7.5.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
7.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
8 Conclusions and Future Directions 150
پس از خرید از درگاه امن بانکی لینک دانلود در اختیار شما قرار میگیرد و همچنین به آدرس ایمیل شما فرستاده میشود.
تماس با ما برای راهنمایی، درخواست مقالات و پایان نامه ها و یا ترجمه با آدرس ایمیل:
ArticleEbookFinder@gmail.com
شماره تماس ما در نرم افزار واتس آپ:
+98 921 764 6825
شماره تماس ما در نرم افزار تلگرام:
+98 921 764 6825
توجه: اگر کارت بانکی شما رمز دوم ندارد، در خرید الکترونیکی به مشکل برخورد کردید و یا به هر دلیلی تمایل به پرداخت الکترونیکی ندارید با ما تماس بگیرید تا راههای دیگری برای پرداخت به شما پیشنهاد کنیم.
دانلود پایان نامه انگلیسی دکترای کامپیوتر: الگوریتم های تجزیه و تحلیل داده های بزرگ یا کلان داده ها (Big Data)
