The term Big Data is defined as the amount of data that goes beyond the ability of the technology to efficiently store, manage, and process it. These actions are only revealed by a robust analysis of its own data, which requires multiple amounts of data processing and the use of tools, whether hardware, software, or methods, that would allow the complete analysis of its own information. As it often happens when one faces a problem, the process of figuring out how to proceed can lead to the creation of new tools to perform new tasks [1].

One of the types of data that benefit from the Big Data area is spatial data, which represents all types of data objects present in a geographic space. Their classification depends on the analysis of spatial objects associated with their spatial characteristics, i.e., areas of the region, roads, lakes, or rivers [2]. Spatial objects are characterized by a geometric representation and relative positioning that implicitly define both spatial relations and properties. In addition, these types of information are organized into a set of spatially linked thematic layers, which represent discrete or continuous features [3]. Furthermore, spatial data mining is the process of extracting knowledge and relations that are stored in spatial databases. Extracting valuable patterns from spatial datasets is more difficult due to the complexity of data types, relations, and autocorrelation [2].

However, such a type of mining is largely derived from conventional data mining techniques for spatial classification, which can be used to explain or predict a phenomenon based on the analysis of the properties of the geographic environment, for example, the occurrence of accidents according to road conditions or the urban environment [3].

Bearing in mind the importance of spatial data and the search for more efficient extraction methods, the objective of this work is to use techniques for prospecting spatial data in a parallelization concept to propose a new algorithm capable of offering performance compatible with the analysis challenges in the Big Data universe.

With that said, the goal intended for this paper was to find the following scientific contribution: the application of parallelization resources in data collection for the creation of a solution with superior performance for the extraction of behaviors and patterns in spatial data, while possessing Big Data characteristics. Since more complex data is being dealt with, these require more computational processing resources.

For the experiments, a bibliographic survey was carried out initially on the theme of Big Data, knowledge extraction in spatial data and MapReduce. Afterwards, a new algorithm was developed that uses parallel processing techniques derived from CHSMST+, a spatial data mining algorithm published by [4]. For this, Apache Spark was used, for the application of MapReduce techniques, in the data collection stage so that the collected records that have the same location and non-spatial characteristics could be counted as only one point, while still maintaining their number of occurrences.

Then, a comparison was made with existing papers based on issues such as input parameter needs, noise detection, and the presence of discrepant points, among others.

Finally, after the development stage, performance tests were run to compare the execution time in relation to the base algorithm and scalability tests when applying them to large amounts of data.

Related Work

A set of papers on the subject in question was researched and studied within the main means of scientific dissemination. These papers have in common the implementation of parallelization resources, such as the MapReduce method for performance optimization in spatial data mining algorithms. [5] Presents a new clustering algorithm that uses K-Medoids instead of K-Means, which makes the algorithm less sensitive to The K-Medoids clustering algorithm has a high running time when processing massive two-dimensional spatial points, although it is robust in relation to external ones. For this reason, it became necessary to use a strategy to improve the performance of the algorithm on large amounts of data. The experimental results confirm that the use of MapReduce has effectively contributed to improving the performance of the algorithm. [6] Proposes an effective process for soil classification n that uses input data from a soil database called the Harmonized World Soil Database. Pre-processing helps to generate an improved representation and uses the least amount of time possible. Then the MapReduce framework divides the input dataset into complementary in the map task, the main component analysis is used to reduce the data, and the outputs contribute to reducing the tasks. Finally, the proposed process is employed to categorize soil types using an optimal neural network classifier. The conventional network uses the optimization process for its customization. Derived from the classifier, the soil type is categorized. The performance of the procedure is evaluated using various metrics, such as sensitivity, specificity, accuracy, precision, recall, and F-measure. The results of the analysis illustrate that the process has high accuracy, which validates the purpose of meeting the objective of soil classification. [7] Presents two algorithms, called VDBSCAN-MR and OVDBSCAN-MR, whose goal is to obtain performance and scalability superior to the base algorithms when analyzed in large databases, without any loss in the results’ quality. VDBSCAN-MR is a density-based spatial data clustering algorithm that implements the MapReduce programming model over the Hadoop framework to allow the analysis of large databases. This algorithm has a single input parameter, which is the value of k, that is, the minimum number of points to form a cluster. In its execution, the VDBSCAN-MR goes through two stages of distributed processing in MapReduce, and the remaining ones are performed sequentially on the master machine of the Hadoop cluster. In OVDBSCAN-MR, on the other hand, the input parameter is the initial domain for the possible values of k, which is inherited from the OVDBSCAN algorithm. This will be the search domain to find the best value of k for the cluster search. As in VDBSCAN-MR, it also has two processing steps distributed in MapReduce, with the others executed sequentially. However, it has some differences since it has one more step at the time of processing, which is finding the best value for k changes in other steps. [2] A new solution for the classification of spatial data is proposed here, which uses an assorted linear method based on Pareto exponentiation. The algorithm applies the Pareto exponentiated technique to find recurrence relations between properties of spatial data, so that spatial association rules are generated and the data are passed to the linear sorted method. After applying the methods, an efficient classification of spatial data is generated. Such classification was analyzed through experimental works, which are based on metrics of precision, classification, time complexity, and space complexity. Experimental results show that the proposed technique is able to increase classification accuracy and reduce time complexity.

This section presents the essential concepts for understanding this work. Such concepts are: spatial data and knowledge extraction, the base algorithm for CHSMST+MR, and MapReduce.

Spatial Data and Knowledge Extraction

Spatial objects are characterized by a geometric representation and relative positioning that implicitly define both spatial relations and properties. Furthermore, these data are organized into a set of spatially linked thematic layers, which represent discrete or continuous features. Its classification depends on the analysis of objects associated with their spatial characteristics, that is, areas of the region such as roads, lakes, or rivers [2,3].

Spatial data contains spatial and attribute data in formation. Thus, while typical datasets only contain measures of variables or attributes, spatial datasets are characterized by having a location associated with each measurement, i.e., the geographic location within the basic three-dimensional structure of the physical world where the measurement was done. In contrast to non-spatial data, data space can therefore be separated into two distinct components: geographic space and attribute space. Occasionally, if temporal information is also present, then time forms a third component, temporal space [8].

The classification and mining of spatial data are more complex than classical data. This is due to the fact that, in order to extract useful patterns, spatial data mining algorithms represent data as a stack of thematic layers available. Therefore, in addition to the object of interest itself, it envisages dealing with its neighbours linked by implicit spatial relationships [2,3].

CHSMST+

Upon taking into consideration the restrictions of the CHSMST algorithm, such as the need for input parameters and not considering non-spatial attributes in the formation of clusters, CHSMST+ was proposed. A performance improvement strategy with multithreading was also applied. Such a strategy was possible because the construction of hyper surfaces by the CHS algorithm facilitates the incorporation of such a technique. Once the space is divided into units, all processing in each unit is performed independently. Furthermore, as the units can also be subdivided into smaller regions, the subdivision itself could be carried out in parallel [4].

In order to eliminate the input parameters, the calculation of local and global distances was introduced, in which the average distance of the objects in each unit is calculated, and then the average of these distances is obtained for all units. Thus, the algorithm will subdivide a unit if the local distance is greater than the global distance, which reduces the spatiality of the data within the units [4]. With the changes made, the algorithm now requires only the data set and no parameter defined by the user to run the algorithm. The CHS algorithm performs both the stages of distributing the points in the initial rectangle and subdividing it into smaller units in CHSMST+. The division of the units into smaller regions is performed asynchronously through threads, while the number of subdivisions is defined automatically by calculating the local and global distances [4].

By the end of the thread’s execution, the initial units are obtained, and then the process of attaching the adjacent units is carried out in order to contemplate the respective samples in a single unit. After this step, any samples belonging to adjacent units are grouped, and a new unit is generated considering the borders of the previous units [4].

MapReduce

This framework can be highlighted as the main paradigm related to such large-scale data processing tools. It is primarily identified by distributed execution to provide a high degree of scalability along with a fault-tolerant scheme. The MapReduce framework comprises two stages: the mapping stage and the reduction stage. [6,9].

In each MapReduce (MR) algorithm, the first local models are run with a subset of the original data within the Map tasks. Then, the Reduce task is dedicated to merging the partial outputs generated by each Map. The ways of designing this fusion of information and models can have a strong impact on the quality of the final system [9].

Furthermore, the MR model is defined with respect to an essential data structure: the (key, value) pair. Processed data and both intermediate and final results work in terms of pairs (key, value) [9].

CHSMST+MR is a spatial data clustering algorithm that implements the MapReduce programming technique on the Apache Spark framework, which is intended to allow efficient execution of large amounts of data. The algorithm uses CHSMST+ techniques, which use techniques from the CHS and MST algorithms already mentioned above. This algorithm, in its execution, goes through the data collection stage, with its processing distributed on MapReduce. The flowchart of the algorithm can be seen in Figure 1, in which the highlighted steps are explained in the next subsection.

Figure 1: CHSMST+MR Flowchart.

Implementing Apache Spark

During the MapReduce step, the occurrences of each record that have the same coordinates and characteristics are calculated, which will be reduced to a single point; however, the value of occurrences is maintained.

As shown in Figure 1, this stage is performed on the Spark cluster and therefore contains the MapReduce functions. At the beginning of processing, a text file with all selected records is sent so that the framework can execute its functions. The Map function then reads the points and, after going through the list of points, creates pairs containing their coordinates and characteristics. Then, the Reduce function reads the pairs, calculates occurrences of points with the same coordinates and characteristics, and associates these values to each pair. The output file has the tuples generated with the coordinates, characteristics, and number of occurrences of these points.

In the Map function, the collected data is divided into small datasets, where it will be transformed into a key-value pair in parallel. This pair is composed of a key, which in turn is defined by the X and Y coordinates, and the values are the non-spatial attributes.

In the Reduce function, these pairs generated in the Map function are merged, where a tuple is created with the pairs that have the same values and their total number of occurrences during the data collection.

Moreover, the number of points that would be generated in the group creation stage is reduced, so that the number of points to be processed is reduced, but the total number of points that exist is maintained because the number of occurrences is stored.

Figure 2 shows what the data looks like before applying MapReduce. It is possible to observe that records 1, 2 and 3 have the same coordinates; however, only records 1 and 3 have the same non-spatial characteristics. In the same way, records 5 and 6 also have the same coordinates but different non-spatial characteristics.

Figure 2: Example of Collected Data.

In this context, when applying Apache Spark to this dataset, it is possible to obtain the following data, shown in Figure 3. In reference to this figure, it is possible to observe the decrease in the records to be treated and that the number of occurrences of them still remains.

Figure 3: Data after applying Apache Spark.

Technologies

For the development of the application, due to its use in the base work and its connection capabilities with the DBMS used [10] and other Web services, the Java language was used. The development environment was Net Beans 13. The database management system used was PostgreSQL, a powerful open-source object relational database system that uses the SQL language [11]. For the treatment of spatial data, the PostGIS extension of PostgreSQL was used, where it offers many resources for the treatment of georeferenced data, rarely found in other competing spatial databases [12].

This section presents the test methods, the database used, and the results obtained after the implementation of Apache Spark in the data collection of the CHSMST+ algorithm.

Methodology

In order to demonstrate the efficiency of the new algorithm, the database of the Academy of Natural Sciences was used, which includes records of animal species [13]. Additionally, the tests were performed on a computer system running an Intel Core i5-10400F CPU at 2.90 GHz, 12 threads, 16GB of RAM, and the operating system Windows 10.

For the performance tests, three sets of tests were performed, and the average between these times was calculated. Each set of tests considered the application of the algorithm with the use of 1, 2, and 3 non-spatial features in addition to the spatial attribute, considering that non-spatial attributes are important to consider the similarity of objects in addition to their proximity. Furthermore, a time comparison was made between the use of MapReduce in conjunction with multithreading and the base algorithm that only contemplates multithreading.

Obtained Results

In the first test stage, the characteristic order was considered in a dataset with 50,000 records. Table 1 shows the execution times for each test, and Figure 4 shows the graph with the values.

Table 1: Execution Times with Characteristic Order.

Figure 4: Graph with execution times with a non-spatial characteristic.

It can be seen from the graph shown in Figure 4, that the application of MapReduce together with multithreading, presented a lower time than the other applications, with an average reduction of approximately 79.96% in relation to the execution without MapReduce. For the second stage of testing, the same structure as the first was maintained, but the gender attribute was added. Table 2 shows the execution times for each case, and Figure 5 shows the respective graph.

Table 2: Execution time with order and genre characteristics.

Figure 5: Graph with execution times with two characteristics.

From figure 5, it can be seen that, for the second test stage, the proposed algorithm also presented a lower time compared to the other tests, with an average reduction of approximately 52.09%.

For the third and final testing stage, the previous structures were maintained, and the location attribute was added. The execution times for each case are presented in Table 3 and in Figure 6 the respective graph.

Table 3: Execution time with order, genre, and location characteristics.

Figure 6: Execution time with three characteristics.

Upon following the same model, it can be seen in Figure 6 that the execution of the algorithm with MapReduce and Multithreading with 3 non-spatial characteristics maintained a lower execution time than the other applications, with an average reduction of approximately 22.03% in comparison to the algorithm without MapReduce.

Results Analysis

From the results obtained, it was possible to observe a decrease of about 79.96% of the processing time when using 1 non-spatial attribute for the detection of patterns and formation of clusters, but when using 2 attributes, the reduction decreased to 52.09%, and consequently, adding a third attribute decreased the reduction a bit more, down to 22.03%. As a consequence, it was possible to detect that as the number of non-spatial features increases, the time reduction through parallelization is reduced. This is due to the fact that the more attributes selected, the smaller the chance that they are equal, so the number of points to be treated is not reduced as it would be with fewer non-spatial features. The algorithm's time reduction curve can be seen in Figure 7. The average execution times are used for each test.

Figure 7: Graph with average execution times.

In the developed work, the MapReduce method was implemented from the Apache Spark framework in the CHSMST+ algorithm during the data collection stage. This implementation allowed a reduction of points to be treated, which generated a decrease in the execution time of the algorithm in relation to the base work according to the number of selected non-spatial attributes. Performance and scalability tests were performed for the algorithm, where it was possible to observe that the parallelization allowed the algorithm to perform better compared to the old one. For this reason, it was found that the more non-spatial attributes are selected, the longer the algorithm's execution time. Also, despite the use of MapReduce as an optimization method, the use of multithreading remains important. Taking it all in account, it can be stated that the new algorithm is efficient in mining spatial data, and it can be scaled to large amounts of data. This work addresses concepts of spatial databases along with the area of parallel processing. With the implementation made for the base algorithm, data collection for knowledge extraction could be optimized, which reduced the computational cost and execution time for the algorithm. The scientific contribution of this particular paper was the use of parallelization methods for the creation of a solution with better performance for the extraction of behaviors and patterns in spatial data and with Big Data characteristics, which resulted in a time optimization for the execution of the algorithm. As the MapReduce methods were made in the data collection stage, the implementation of these methods is proposed as future work in the creation of clusters as well. This will allow further optimization of the algorithm. In addition, it is proposed to measure efforts to support more characteristics in data collection, which allows a better extraction of knowledge from these data.

1. Kaisler S, Armour F, Espinosa JA, Money W. Big data: Issues and challenges moving forward. In 2013 46th Hawaii international conference on system sciences. IEEE. 2013; 995-1004.
2. Smart PDS, Thanammal KK, Sujatha SS. A novel linear assorted classification method based association rule mining with spatial data. Sadhana. 2021; 46: 1-12.
3. Oujdi S, Belbachir B, Boufares F. C4.5 Decision tree algorithm for spatial data, alternatives and performances. Journal of computing and information technology. 2019; 27: 29-43.
4. Medeiros CA. Extracao de conhecimento em bases de dados espaciais: algoritmo CHSMST+. 2014.
5. Yue X, Man W, Yue J, Liu G. Parallel k-medoids++ spatial clustering algorithm based on mapreduce. arXiv. 2016.
6. Aakunuri M, Narsimha G. Using an efficient optimal classifier for soil classification in spatial data mining over big data. Journal of Intelligent Systems. 2020; 29: 172-188.
7. Daniel GP. Otimizacao de algoritmos de agrupamento espacial baseado em densidade aplicados em grandes conjuntos de dados. 2016.
8. Demsar U, Harris P, Brunsdon C, Fotheringham AS, McLoone S. Principal component analysis on spatial data: an overview. Annals of the Association of American Geographers. 2013; 103: 106-128.
9. Ramiez-Gallego S, Fernandez A, Garcia S, Chen M, Herrera F. Big Data: Tutorial and guidelines on information and process fusion for analytics algorithms with MapReduce. Information Fusion. 2018; 42, 51-61.
10. What is Java? 2022.
11. What is PostgreSQL? 2022.
12. About PostGIS. 2022.
13. Academy of Natural Sciences: MAL. 2022.