Big Data Quality: A systematic literature review and future research directions <s> Distance-based techniques <s> In this article we consider the problem of detecting unusual values or outliers from time series data where the process by which the data are created is difficult to model. The main consideration is the fact that data closer in time are more correlated to each other than those farther apart. We propose two variations of a method that uses the median from a neighborhood of a data point and a threshold value to compare the difference between the median and the observed data value. Both variations of the method are fast and can be used for data streams that occur in quick succession such as sensor data on an airplane. <s> BIB001 </s> Big Data Quality: A systematic literature review and future research directions <s> Distance-based techniques <s> Outlier detection is a well established area of statistics but most of the existing outlier detection techniques are designed for applications where the entire dataset is available for random access. A typical outlier detection technique constructs a standard data distribution or model and identifies the deviated data points from the model as outliers. Evidently these techniques are not suitable for online data streams where the entire dataset, due to its unbounded volume, is not available for random access. Moreover, the data distribution in data streams change over time which challenges the existing outlier detection techniques that assume a constant standard data distribution for the entire dataset. In addition, data streams are characterized by uncertainty which imposes further complexity. In this paper we propose an adaptive, online outlier detection technique addressing the aforementioned characteristics of data streams, called Adaptive Outlier Detection for Data Streams (A-ODDS), which identifies outliers with respect to all the received data points as well as temporally close data points. The temporally close data points are selected based on time and change of data distribution. We also present an efficient and online implementation of the technique and a performance study showing the superiority of A-ODDS over existing techniques in terms of accuracy and execution time on a real-life dataset collected from meteorological applications. <s> BIB002 </s> Big Data Quality: A systematic literature review and future research directions <s> Distance-based techniques <s> The main aim of data stream outlier detection is to find the data stream outliers in rational time accurately. The existing outlier detection algorithms can find outliers in static data sets efficiently, but they are inapplicable for the dynamic data stream, and cannot find the abnormal data effectively. Due to the requirements of real-time detection, dynamic adjustment and the inapplicability of existing algorithms on data stream outlier detection, we propose a new data stream outlier detection algorithm, ODGrid, which can find the abnormal data in data stream in real time and adjust the detection results dynamically. According to the experiments on real datasets and synthetic datasets, ODGrid is superior to the existing data stream outlier detection algorithms, and it has good scalability to the dimensionality of data space. <s> BIB003 </s> Big Data Quality: A systematic literature review and future research directions <s> Distance-based techniques <s> To effectively clean the large-scale, mixed and inaccurate monitoring or collective data, reduce the cost of data cache and ensure the consistent deviation detection on timing data of each cycle, a big data online cleaning algorithm based on dynamic outlier detection has been proposed. The data cleaning method is improved by local outliner detection upon density, sampling cluster uniformly dilution Euclidean distance matrix retaining some corrections into next cycle of cleaning, which avoids a sampling causing overall cleaning deviation and reduces amount of calculation within data cleaning stable time, enhancing the speed greatly. Finally, the distributed solutions on online cleaning algorithm based on Hadoop platform. <s> BIB004 </s> Big Data Quality: A systematic literature review and future research directions <s> Distance-based techniques <s> Although most NoSQL Data Stores are schema-less, information on the structural properties of the persisted data is nevertheless essential during application development. Otherwise, accessing the data becomes simply impractical. In this paper, we introduce an algorithm for schema extraction that is operating outside of the NoSQL data store. Our method is specifically targeted at semi-structured data persisted in NoSQL stores, e.g., in JSON format. Rather than designing the schema up front, extracting a schema in hindsight can be seen as a reverse-engineering step. Based on the extracted schema information, we propose set of similarity measures that capture the degree of heterogeneity of JSON data and which reveal structural outliers in the data. We evaluate our implementation on two real-life datasets: a database from the Wendelstein 7-X project and Web Performance Data. <s> BIB005 </s> Big Data Quality: A systematic literature review and future research directions <s> Distance-based techniques <s> Among many Big Data applications are those that deal with data streams. A data stream is a sequence of data points with timestamps that possesses the properties of transiency, infiniteness, uncertainty, concept drift, and multi-dimensionality. In this paper we propose an outlier detection technique called Orion that addresses all the characteristics of data streams. Orion looks for a projected dimension of multi-dimensional data points with the help of an evolutionary algorithm, and identifies a data point as an outlier if it resides in a low-density region in that dimension. Experiments comparing Orion with existing techniques using both real and synthetic datasets show that Orion achieves an average of 7X the precision, 5X the recall, and a competitive execution time compared to existing techniques. <s> BIB006 </s> Big Data Quality: A systematic literature review and future research directions <s> Distance-based techniques <s> The outlier detection is a popular issue in the area of data management and multimedia analysis, and it can be used in many applications such as detection of noisy images, credit card fraud detection, network intrusion detection. The density-based outlier is an important definition of outlier, whose target is to compute a Local Outlier Factor (LOF) for each tuple in a data set to represent the degree of this tuple to be an outlier. It shows several significant advantages comparing with other existing definitions. This paper focuses on the problem of distributed density-based outlier detection for large-scale data. First, we propose a Gird-Based Partition algorithm (GBP) as a data preparation method. GBP first splits the data set into several grids, and then allocates these grids to the datanodes in a distributed environment. Second, we propose a Distributed LOF Computing method (DLC) for detecting density-based outliers in parallel, which only needs a small amount of network communications. At last, the efficiency and effectiveness of the proposed approaches are verified through a series of simulation experiments. <s> BIB007 </s> Big Data Quality: A systematic literature review and future research directions <s> Distance-based techniques <s> The concept of Top-N local outlier that focuses on the detection of the N points with the largest Local Outlier Factor (LOF) score has been shown to be very effective for identifying outliers in big datasets. However, detecting Top-N local outliers is computationally expensive, since the computation of LOF scores for all data points requires a huge number of high complexity k-nearest neighbor (kNN) searches. In this work, we thus present the first distributed solution to tackle this problem of Top-N local outlier detection (DTOLF). First, DTOLF features an innovative safe elimination strategy that efficiently identifies dually-safe points, namely those that are guaranteed to (1) not be classified as Top-N outliers and (2) not be needed as neighbors of points residing on other machines. Therefore, it effectively minimizes both the processing and communication costs of the Top-N outlier detection process. Further, based on the well-accepted observation that strong correlations among attributes are prevalent in real world datasets, we propose correlation-aware optimization strategies that ensure the effectiveness of grid-based partitioning and of the safe elimination strategy in multi-dimensional datasets. Our extensive experimental evaluation on OpenStreetMap, SDSS, and TIGER datasets demonstrates the effectiveness of DTOLF — up to 10 times faster than the alternative methods and scaling to terabyte level datasets. <s> BIB008
There are seven papers that the first three papers are distance-based and the last four one is densitybased. As previously mentioned, density based methods are also considered as distance-based methods because density-based methods use distance measures to determine the density and LOF. In BIB001 , a distance-based approach is presented in which the median of the data is calculated, and the new data is compared with the median. If it is higher than a threshold value, then new data is considered as an outlier. In this paper, two types of median are defined: one side and two sides. In two side, the 2k data is considered from the past data, and the median is selected, and in the one side, the median is calculated separately of each k data, and finally, the two medians are summed up, and the sum is considered as the final median. The reason for this is dealing with k outliers in a row. The experiments are conducted for one side, and two side methods and the results show that one side method is better for detecting outliers in a row, but the complete improvement has not yet been achieved. Another distance-based method is proposed in BIB002 . In this paper, there are two concepts of local deviation and global deviation. The purpose of the local deviation is to check the new data value with the average of the recent data. On the other hand, for global deviation, the new data value is compared with the average of the total data stored. If the new data value with local or global deviation exceeds more than three times the variance, then that data is an outlier. In this method, the concept of drift has also been solved with the help of global deviation. The run-time and predictive accuracy of the proposed method is evaluated by three other methods, which the results show that, at a reasonable time, the accuracy of predictions was far more than the other methods. In this dissertation  , authors also propose a distance-based method to determine the outliers. Thus, By Euclidean distance, the number of nodes close to each data is determined. If this number is less than a certain threshold, then that data is known as an outlier. The proposed method is compared with several similar methods, and the results of the experiments show that the proposed method can efficiently detect and clean the outliers and free the data set of noise. In another work of the authors of BIB002 , a density-based method is proposed BIB006 . An algorithm called Orion, which is first, calculates the similarity between new data and other data, then the stream density and k-distance criteria for each data are obtained. The stream density is the number of stream neighbors and the k-distance of a point is the shortest distance that includes k closest neighbors of that point. Then Orion uses a clustering algorithm to cluster the data. The clusters are divided into three groups: small, average, and large. Data that belongs to the small density and large k-distance clusters are considered as an outlier. The same method is presented in  . Also, this dissertation contains more details on the method and the proof of the lemmas. Several datasets have been used for evaluation. Precision, recall and the effect of the concept drift on the proposed method and other methods have been evaluated. The results show that in most of the datasets, the proposed method has a higher precision/recall and the concept drift does not affect the accuracy of Orion. In BIB003 , a density-based approach is presented in which the data space is split into several grids and according to the data entry, the information of each grid, including the number of data, the mean, the variance, and the time, is updated. After the updating process, the density of each grid is evaluated, and if the density is less than a threshold, then the grid is said to be an abnormal grid, and finally, the data that is contained in an abnormal grid is an outlier. The method is compared with the two algorithms STORM and LOF. The KDD-CUP99 dataset is considered as the actual dataset, and a synthetic data set of 400,000 records is also selected. The precision of the prediction and run-time has been compared, and the results indicate that the proposed method has been able to have lower execution time and more accurate prediction. Another density-based method is presented in BIB004 . In this paper, after the data stored in the buffer, the Euclidean distance of the data is computed. Then, if the distance is greater than the desired threshold, it was checked as an outlier and went to the density calculation stage. At this stage, the data density is computed with the LOF formulas, and if it exceeds the threshold, it will be deleted from the buffer. The runtime of the algorithm is compared with another one, which the results indicate that the proposed method performed less time in processing and, thanks to the distributed platform, has approximately linear time complexity. There are three papers in this category. Apart from the first method that uses the distance criterion, two other methods, after calculating the distance, use the density to detect the outliers. The explanation of each work is given below. An important characteristic of a NoSQL data model, which is frequently used for storing big, is the lack of a fixed and predefined data schema. On the other hand, in order to evaluate data quality and identify quality issues, it is needed to analyze the schema. As a result, some researchers have worked on techniques for extracting schema from data instances. In BIB005 a method to extract the JSON files schema is presented in which, after selecting each JSON document, its structure is extracted, and a graph is made of the properties of each document. Then, by evaluating the new document and its properties, if the property is a duplicate, its count will be increased in the corresponding path, and if it is not, it will be added to the graph. After the graph is made, all properties are identified, but are all necessary? To understand, the count of repetitions of each property must be checked with the count of parent repeats. If this number is equal, then the property is necessary. Otherwise, it is optional. To determine duplicate properties, similarity and distance measures are used. After creating the graph and specifying a threshold for each property, it is possible to create a list of properties that are less than the threshold in the relevant document. This approach is useful for determining optional properties. The algorithm is provided on the Wendelstein project database. The database has been recording plasma experiments for several years. There are now over 120 different documents. Until today, this data set has no explicit schema. The execution time of the algorithm is evaluated with documents of varying size, which is almost linear and the algorithm can generate a JSON document schema at the right time. Paper BIB007 , which is a density-based approach, data is first mapped to a grid space. Then, in each grid, density (LOF) is calculated in parallel. If the density is less than the threshold, then the grid data is considered as an outlier. When splitting data, it may be placed on the boundary of the two grids. In this case, the proposed method calculates the distance of that data with two grids, and if it is closer to the second grid, it will be transferred to that grid. The runtime and the number of transmissions are evaluated in the proposed method and in another method, and the experiments have shown that the proposed method has a better performance. Another distributed density-based approach is presented in BIB008 . To reduce computations, after partitioning data, partitions whose data count exceeds the threshold value are removed from the next calculation. Then, in partitions with less data, the LOF is calculated, and the outlier is detected. The proposed method is evaluated in terms of execution cost, and the results have demonstrated that it has a higher speed in comparison to related works.