Research on Efficient Algorithms for Intelligent Computing in Big Data Analytics

GFS is Google File System, which is a massive data file storage system used by Google for its cloud computing services. And is tightly integrated with Google’s MapReduce, Bigtable, and other technologies, making it one of Google’s core technologies. Like other distributed file systems, a GFS cluster has a Master node and a large number of Chunk service nodes that can be accessed by multiple users simultaneously. The nodes of the cluster are all running a system environment is generally a Linux operating system. The Master node is responsible for maintaining file system metadata, including namespaces, file-to-block mappings, block locations, and so on. GFS users communicate with Master nodes and Chunk service nodes through clients to perform data read and write operations. Among them, the user and the Master node only communicate about metadata operations, while the client and the Chunk service node directly communicate and interact with specific data reading and writing operations.

Compared with previous file systems, GFS has the following characteristics: 1)

Massive data storage in chunks.

GFS is now one of the best distributed file system in the operational environment to achieve performance, reliability and cost balance.

HDFS, as an open source implementation of GFS, can be easily and quickly deployed on many common hardware devices and can dynamically expand the cluster size according to the need to increase the storage space for large data sets. The multi-copy technology effectively guarantees the reliability of user data storage. At the same time, due to its open-source nature, researchers can customize the file system according to their own needs, with a high degree of autonomy.

For the storage architecture of HDFS, researchers have conducted extensive research and proposed corresponding optimization solutions for different application scenarios. The article suggests a method for distributing data in HDFS. This strategy is constructed on the basis of a consistent hash algorithm for data storage. In HDFS, node failure is common. The consistent hash algorithm ensures that when a new node is added or removed from the cluster, it does not significantly change the mapping of data on the nodes. When data needs to be stored, the policy determines where to store the data based on the hash value attribute of the data as a way to increase the percentage number of map jobs localised when subsequent jobs are run and ultimately increase the speed of data processing.

Indexing is a data structure with certain regularity designed according to the attributes, location and shape of spatial objects, which is located between the user query and the data in the spatial database, and improves the efficiency and speed of the query by filtering out a large amount of spatial data unrelated to the query area. Traditional indexing methods for faceted elements include R-trees, quadtrees, and their variants. For small-scale data, this indexing method has better indexing efficiency in relational databases. With the explosive growth of data volume, distributed storage of massive data is required. This paper combines HBase (Hadoop Database) storage characteristics and data query characteristics to design the indexing method for big data under the cloud storage model: secondary multi-column index table design based on attribute query.

HBase provides exact query (get) and full table scan query (scan) operations based on row keys, while a single row key index is overwhelming in the face of multi-dimensional queries, and full table scan is inefficient for massive data queries [27]. In this paper, we designed a non-row key index based on the Coprocessor of RegionObserver under HBase, by listening to the client’s write operation when the data in MemStore is refreshed to the StoreFile before calling the Coprocessor’s built-in Hook function to build an index on the data in it, and when the index is constructed, it is added to the index map. The index file is added to the index map for data query. Based on the above ideas, a secondary multi-column indexing scheme under HBase is proposed, which can effectively avoid a series of problems brought by splicing non-row key values into RowKey, and by constructing the mapping relationship between non-row key query fields and RowKey values, the target data can be retrieved quickly and accurately in order to achieve efficient indexing when querying for non-row keys. When querying a non-row key value, it will first go to the secondary index table to query the RowKey value corresponding to the current non-row key value and then go to the HBase source data table to query the record corresponding to the RowKey value.

The secondary multi-column index is a “key-value” data established for a certain column or certain columns of the target record, and its index structure adopts the inverted index, with the column value of the original table in HBase as the key and the RowKey value of the original table columns as the value, when querying with these column values as the conditions, it will be possible to retrieve the corresponding “key-value” data by searching the corresponding When a query is made based on these column values, the target record can be found quickly by retrieving the corresponding “key-value”data. Among them, the construction of the secondary multi-column index table mainly includes the design of the index table row key and the design of the column value. The design of the row key is determined by the value of the target field to be indexed. If multiple non-row keys need to be indexed, the row key value of the index table is a combination of these several column values.

The steps of the parallel region query algorithm can be summarised in two steps: filtering and refining. Specifically, first calculate the MBR of the query region, construct the HBase index filter based on the MBR, get the grid code (Hilbert code) intersecting with the MBR, then scan the index table based on the grid code, save the hit index records in the to-be-searched dataset, and then transform the to-be-searched dataset to the RDD operator through Spark, and then parallelly query the corresponding dataset with the HBase storage table by the RDD operator. The corresponding dataset is queried in parallel in the HBase storage table, and finally, the obtained dataset is refined with the query region to return the dataset that meets the query region’s conditions.

The experiments tested the performance (query execution time) of ▯ Hadoop HDFS against the above comparison systems on three datasets, LUBM-5, LUBM-50 and LUBM-500, respectively. All results in the experiments are averaged over 10 runs. In addition, the values were recorded for both coldstart and hot-run states. The specific experimental results are shown in Table 1.

The 10 queries of LUBM were divided into two groups with different categories. The first group includes queries 1, 3, 4, 5, 7, 8, and 10. These queries are highly selective and return fewer result data, and thus are labelled as fast queries. Correspondingly, the second group of queries includes queries 2, 6, and 9, which return more results or have more complex queries, are slower to execute and are labelled as slow queries.

In the experiments, some systems failed to return results within a reasonable timeframe (1000 seconds) on some datasets, and the results were labelled as NA. Jena-Hbase failed to return results within a reasonable timeframe on two large-scale datasets, LUBM-50 and LUBM-500.

Hadoop HDFS outperforms Jena-Hbase in executing all the queries. Even for fast queries, the execution time of Jena-Hbase increases as the dataset grows. On the contrary, the execution time of Hadoop HDFS is fixed for fast queries, which is mainly due to the efficient indexing schema and query optimisation strategy of Hadoop HDFS. In addition, Hadoop HDFS achieves a three-order-of-magnitude performance improvement over SHARD for most query use cases. This is mainly due to the fact that SHARD needs to transform each query into a series of MapReduce job executions. This imposes a significant time overhead for job startup and network disk reads and writes.

The memory usage of indexes in Hadoop HDFS is shown in Table 2. As can be seen from Table 2, the memory usage of indexes in Hadoop HDFS is very low. This allows the indexes to fit into memory using very few nodes. Therefore, all the queries mentioned above can actually be performed using Hadoop HDFS. In addition, Hadoop HDFS has good load-balancing properties due to the use of a consistent hash to divide index data in memory.

This section evaluates the scalability of the Hadoop HDFS system. First, the data set size is adjusted by fixing the number of machines to evaluate the data scalability of the system. Then, the number of machines is adjusted by fixing the data size to evaluate the system’s scalability. 1)

Data scalability

Hadoop HDFS is tested on a cluster of 17 nodes, and five datasets whose sizes are scaled up from 5 universities to 500 universities are used. The experimental results are shown in Fig. 3. For fast queries, e.g., Q1, the query time of Hadoop HDFS is fixed because of the highly selective index structure of Hadoop HDFS as well as the fact that there is not much change in the number of result entries returned by the query. For slow queries, e.g., Q6, Hadoop HDFS achieves near-linear scalability as the data size grows.

Figure 3.

Query time change with adjusted data

Figure 4.

Query time change with adjusted storage node

Partitioning phase is an important phase, partitioning of data consists of two sub phases, data slicing and slice extension phase. The data slicing stage is to divide the dataset X into M sets S_i without intersection according to the specified rules, i.e., X=∪i=oi=MSi and S_i ∩ S_j = ∅, where i ≠ j and i ≤ M, j ≤ M. The partition extension stage is to extend the range of the partition outward by a certain distance, which should be larger than the radius of the DBSCAN clustering ε in order to ensure the correctness of the final merging result. In order to reduce the partition size and improve the computational efficiency, this paper extends the partition by a ε distance. In this paper, the dataset is divided into multiple partitions using Bisection Space Partitioning (BSP).BSP was proposed by M. Berger and S. Bokhari in that it can recursively partition the desired space into roughly equal regions.

After dividing the dataset X into numerous partitions, DBSCAN clustering, called local clustering, can be executed on each partitioned data. The input of local clustering is only for partitioned data, because the massive data has been divided into multiple partitions with less data in the first stage, and local clustering is executed in parallel, so the time required for clustering massive data can be greatly reduced. Local clustering is the core of the whole distributed DBSCAN algorithm, and the clustering output of this phase is an important input for the merging phase. At the end of local clustering, each point in the data set will be assigned at least one cluster ID and a point type (core, boundary or noise). Most points will only be assigned a single cluster ID, but points in the partitioned overlap region will be labeled with multiple cluster IDs, and likewise with a point type.

After all the local clustering phases are completed, the global merging phase performs the global merging of clusters based on the clustering results of the points that are in the overlapping region of the partitions. The global merging of clusters phase can be completed in three steps: 1) Remove the points that are in the overlapping region and have multiple local clusters. 2) Determine which local cluster IDs belong to the same global cluster to be merged in more than one partition based on these points and record this information. 3) Regenerate the unique global cluster IDs.

This subsection of the text experiments built three nodes (1 management node, two computing nodes) of the Hadoop cluster, and in the Hadoop cluster built on the Spark cluster, the entire Spark cluster using Hadoop’s HDFS for data storage to facilitate the storage of datasets and can improve the speed of the entire experimental environment. The hardware configuration of the three nodes used for the experiment is an Ubuntu Server system, the CPU is Intel 12th generation i9-12900H processor, memory is 16G, and hard disk storage is 60G. The software configuration is Hadoop-3.2.3, Spark-3.2.2, and Python-3.9.13. The Spark cluster built in this paper uses Yarn for resource management during the running state. The experiments utilize Yarn-Client mode to enhance the flexibility of resource allocation for the entire Spark cluster.

In this paper, in order to explore the accuracy of the proposed Spark DBSCAN algorithm with its DBSCAN algorithm on different datasets, this paper compares the clustering result metrics of the traditional parallel DBSCAN algorithm (Naive DBSCAN) and the proposed Spark DBSCAN algorithm on different datasets as shown in Table 3.

As shown in Table 3, compared to the stand-alone DBSCAN algorithm, the Spark DBSCAN algorithm, in most cases, shows a decrease in the metrics such as contour coefficient, purity and Rand coefficient. This is mainly due to the fact that in the parallel DBSCAN algorithm, multiple computing nodes process different data slices in parallel, and then merge the local clustering results into the final clustering results, and the process may lead to conflicts or overlaps between the clustering results of different partitions, which affects the accuracy of the final clustering results. The accuracy of the Spark DBSCAN algorithm is not much different from that of traditional parallel DBSCAN algorithms in different data sets. The Spark DBSCAN algorithm’s accuracy is not significantly different. The clustering results of the Spark DBSCAN algorithm are shown in Figure 6. The clustering results of the Spark DBSCAN algorithm and traditional parallel DBSCAN algorithm on Jain and Pathbased datasets are the same because the datasets have the same amount of data and similar data characteristics.

Figure 6.

Spark DBSCAN algorithm clustering result graph

Subsequently, in this paper, in order to show the performance of the Spark DBSCAN algorithm in terms of runtime efficiency, the runtime comparison between the traditional parallel DBSCAN algorithm and the Spark DBSCAN algorithm on different datasets is shown in Table 4, where the number of partitions of Naive DBSCAN algorithm and Spark DBSCAN algorithm is 4.

As shown in Table 4, the Spark DBSCAN algorithm runs faster on different datasets compared to the Naive DBSCAN algorithm, and the cost of the runtime on the Aggregation dataset is only 30.57% of the Naive DBSCAN parallel algorithm, and on the D31 dataset, it is only 46.50 per cent.