Search

Efficiently querying multiple spatial datasets is a challenging task in geoscience. The majority of spatial processing techniques use minimum bounding box (MBB) to approximate neighbouring spatial objects and and place them adjacent in the spatial index. However, due to the existence of redundant space in MBB of these methods, this problem can significantly reduce the query efficiency. In this paper, we propose a novel two-stage adaptive method of clipping the bounding box in spatial query, called IB-CBB (Intersection Based Clipped Bounding Boxes). The first stage employs a clipped bounding box, which records the redundant spatial spaces within the bounding box of the spatial index by calculating the clip points. As a result, the computational complexity of indexed child nodes in the query process is reduced. The second stage optimizes the above query algorithm by judging the intersection of the query box and the MBB of index node, significantly reducing the query time. Experiments demonstrate that IB-CBB outperforms the baseline method in terms of reducing the computational time. [ABSTRACT FROM AUTHOR]

ABSTRACTEfficiently querying multiple spatial datasets is a challenging task in geoscience. The majority of spatial processing techniques use minimum bounding box (MBB) to approximate neighbouring spatial objects and and place them adjacent in the spatial index. However, due to the existence of redundant space in MBB of these methods, this problem can significantly reduce the query efficiency. In this paper, we propose a novel two-stage adaptive method of clipping the bounding box in spatial query, called IB-CBB (Intersection Based Clipped Bounding Boxes). The first stage employs a clipped bounding box, which records the redundant spatial spaces within the bounding box of the spatial index by calculating the clip points. As a result, the computational complexity of indexed child nodes in the query process is reduced. The second stage optimizes the above query algorithm by judging the intersection of the query box and the MBB of index node, significantly reducing the query time. Experiments demonstrate that IB-CBB outperforms the baseline method in terms of reducing the computational time.

Many kinds of spatio-temporal data in our daily lives, such as the trajectory data of moving objects, stream natively. Streaming systems exhibit significant advantages in processing streaming data due to their distributed architecture, high throughput, and real-time performance. The use of streaming processing techniques for spatio-temporal data applications is a promising research direction. However, due to the strong dynamic nature of data in streaming processing systems, traditional spatio-temporal indexing techniques based on relatively static data cannot be used directly in stream-processing environments. It is necessary to study and design new spatio-temporal indexing strategies. Hence, we propose a workload-controllable dynamic spatio-temporal index based on the R-tree. In order to restrict memory usage, we formulate an INSERT and batch-REMOVE (I&BR) method and append a collection mechanism to the traditional R-tree. To improve the updating performance, we propose a time-identified R-tree (TIR). Moreover, we propose a distributed system prototype called a time-identified R-tree farm (TIRF). Experiments show that the TIR could work in a scenario with a controllable usage of memory and a stable response time. The throughput of the TIRF could reach 1 million points per second. The performance of a range search in the TIRF is many times better than in PostgreSQL, which is a widely used database system for spatio-temporal applications. [ABSTRACT FROM AUTHOR]

The proliferation of location-based service applications has led to a substantial surge in the amount of life trajectory data produced by mobile devices. And these data frequently contain confidential personal details. Simultaneously, the corresponding relatively lagging privacy protection technology and the improper trajectory data handling method will make tremendous problems with privacy breach. Therefore, this paper presents a trajectory privacy data publishing scheme, denoted as LORDP, which is based on local optimisation and R-tree. The proposed scheme aims to handle sensitive data while improves trajectory protection effectiveness. Firstly, the scheme combines the LKC-privacy model requirement to filter out the minimum violating sequences set, to reduce data sensitivity and the amount of injected noise. Secondly, R-tree is constructed based on trajectory similarity. Finally, Laplacian noise is added to the R-tree's leaf nodes constrained by differential privacy. The experiments show that the proposed LORDP algorithm significantly enhances the utility of data compared to other algorithms, and reduces the loss rate of about approximately 2% for per trajectory data, which shows that the present algorithm is extremely effective. [ABSTRACT FROM AUTHOR]

Abstract In the pre-big data era, many traditional databases supported spatial queries via spatial indexes. However, modern applications are seeing a rapid increase of the volume and ingestion rate of spatial data. Log-structured Merge (LSM) tree is used by many big data systems as their storage structure in order to support write-intensive large-volume workloads, which are usually only optimized for single-dimensional data. Research has studied how spatial indexes can be supported on LSM systems, but focused mainly on the local index organization, that is, how data is organized inside a single LSM component. This paper studies various aspects of LSM spatial indexing, including spatial merge policies, which determine when and how spatial components are merged. Three stack-based and one leveled merge policies have been studied, which have been implemented on a common big data system Apache AsterixDB. The write and read performance on various workloads is evaluated, and our findings and recommendations are discussed. A key finding is that Leveled policies underperform other stack-based merge policies for most types of spatial workloads.

Many kinds of spatio-temporal data in our daily lives, such as the trajectory data of moving objects, stream natively. Streaming systems exhibit significant advantages in processing streaming data due to their distributed architecture, high throughput, and real-time performance. The use of streaming processing techniques for spatio-temporal data applications is a promising research direction. However, due to the strong dynamic nature of data in streaming processing systems, traditional spatio-temporal indexing techniques based on relatively static data cannot be used directly in stream-processing environments. It is necessary to study and design new spatio-temporal indexing strategies. Hence, we propose a workload-controllable dynamic spatio-temporal index based on the R-tree. In order to restrict memory usage, we formulate an INSERT and batch-REMOVE (I&BR) method and append a collection mechanism to the traditional R-tree. To improve the updating performance, we propose a time-identified R-tree (TIR). Moreover, we propose a distributed system prototype called a time-identified R-tree farm (TIRF). Experiments show that the TIR could work in a scenario with a controllable usage of memory and a stable response time. The throughput of the TIRF could reach 1 million points per second. The performance of a range search in the TIRF is many times better than in PostgreSQL, which is a widely used database system for spatio-temporal applications.

In the pre-big data era, many traditional databases supported spatial queries via spatial indexes. However, modern applications are seeing a rapid increase of the volume and ingestion rate of spatial data. Log-structured Merge (LSM) tree is used by many big data systems as their storage structure in order to support write-intensive large-volume workloads, which are usually only optimized for single-dimensional data. Research has studied how spatial indexes can be supported on LSM systems, but focused mainly on the local index organization, that is, how data is organized inside a single LSM component. This paper studies various aspects of LSM spatial indexing, including spatial merge policies, which determine when and how spatial components are merged. Three stack-based and one leveled merge policies have been studied, which have been implemented on a common big data system Apache AsterixDB. The write and read performance on various workloads is evaluated, and our findings and recommendations are discussed. A key finding is that Leveled policies underperform other stack-based merge policies for most types of spatial workloads. [ABSTRACT FROM AUTHOR]

Flash-based SSDs have become well established in the storage market, replacing magnetic disks in both enterprise and consumer computer systems. The performance characteristics of these new devices have prompted a considerable amount of research that aims at developing efficient data access methods. Early works attempted to reduce the expensive random writes, exploiting logging and batch write techniques, while more recent ones addressed query processing, taking advantage of the high internal parallelism of SSDs. 3D XPoint is a new nonvolatile memory technology that has emerged recently, featuring smaller access times and higher durability compared with flash. It is available both as block addressable secondary storage and as byte addressable persistent main memory. However, the high cost of 3D XPoint prevents, for the moment, its adoption in large scales. This renders hybrid storage systems utilizing NAND flash and 3D XPoint a sufficient alternative. In this work, we propose HyR-tree, a hybrid variant of R-tree that persists a part of the tree in the high performing 3D XPoint storage. HyR-tree identifies repeated access pattern to the data and uses these patterns to locate the most important nodes. The importance of a node is determined by the performance gain that derives from its placement within a 3D XPoint-based device. We experimentally evaluated HyR-tree using real devices and four different datasets. The acquired results show that our proposal achieves significant performance gains up to 40% in tree construction and up to 56% in range queries. [ABSTRACT FROM AUTHOR]

Nowadays recording and sharing personal lives using mobile devices on the Internet is becoming increasingly popular, and successive POI recommendation is gaining growing attention from academia and industry. In mobile scenarios, multiple influencing factors including the diversity of user preferences, the changeability of user behavior and the dynamic of spatiotemporal context bring great challenges to the POI recommender system. In order to accurately capture both the stable and the contextual preferences of mobile users in dynamic contexts, we propose a fusion framework JANICP (Joint Attention Networks with Inherent and Contextual Preferences) for successive POI recommendation by jointly training an offline/nearline user inherent interest perception model and an online user contextual interest prediction model. The offline model is trained based on the global historical behavior data to achieve stable interest representation, while the online model is trained based on the instantly selected context-sensitive data to achieve dynamic interest perception. An attention aggregation and matching module is used to fully connect the two kinds of preference representations and generate the final POI recommendation. Extensive experiments were conducted on three real datasets and experimental results show that the proposed JANICP outperforms existing state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Nearest close friend query (kℓNCF) in geo-social networks, aims to find the k nearest user objects from among the ℓ-hop friends of the query user. Existing efforts on kℓ-NCF find the user objects in the Euclidean space. In this paper, we study the problem of nearest close friend query in road-social networks. We propose two methods. One is based on Dijkstra algorithm, and the other is based on ISLabel. For the Dijkstra-based method, Dijkstra algorithm is used to traverse the user objects needed. For the label-based method, we make use of IS-Label to calculate the distance between two vertices to avoid traversing the edges that do not contain the desired user object. For each method, we propose effective termination conditon to terminate the query process early. Finally, we conduct a variety of experiments on real and synthetic datasets to verify the efficiency of the proposed methods. [ABSTRACT FROM AUTHOR]

Summary: Uncertain data is widely used in many practical applications, such as data cleaning, location‐based services, privacy protection, and so on. With the development of technology, data has a tendency to high‐dimensionality. The most common indexes for nearest neighbor search on uncertain data are the R‐Tree and the KD‐Tree. These indexes will inevitably bring about "curse of dimension." Focus on this problem, article proposes a new hash algorithm, called the LSR‐forest, which based on locality sensitive hashing and R‐Tree, to solve the high‐dimensional uncertain data approximate neighbor search problem. The LSR‐forest can hash similar high‐dimensional uncertain data into a same bucket with a high probability, and then constructs multiple R‐Tree‐based indexes for hashed buckets. When querying, it is possible to judge neighbors by checking the data in the hypercube which the query point is in. One can also adjust the query range automatically by different parameter of k. Many experiments on different datasets are presented in this article. The results show that LSR‐forest has better effectiveness and efficiency than R‐Tree on high‐dimensional datasets. [ABSTRACT FROM AUTHOR]

• Position information and velocity direction are used for trajectory segmentation. • A new similarity matrix is construct for clustering. • The spatial R-tree index is used to improve the efficiency of neighborhood query. • The real Atlantic hurricane and elk datasets verify that the proposed algorithm. The existing trajectory clustering algorithms only use the position information in trajectory segmentation, which makes the selection of segment points unreliable. Meanwhile, the adopted distance metrics are originally designed to compare the whole trajectory, leads to the inaccuracy similarity of trajectory segments, and hence causes subsequent clustering risks. Moreover, the execution time of clustering significantly increases with the amount of data. To address these issues, the direction of velocity is introduced for improving the discrimination of segment points. Next, the shared nearest neighbor (S N N) similarity and Trajectory-Hausdorff distance are combined to construct the similarity matrix for overcoming the limitations of existing distance measures. Then, based on the R-tree index strategy, the neighbored trajectory segments are extracted and stored for fastening segment indexing. Finally, the Atlantic hurricane and elk datasets verify that the proposed algorithm can not only improve the clustering efficiency but also extract the trajectory model accurately. [ABSTRACT FROM AUTHOR]

Outlier detection is an important task in the field of big data analysis. The technology has been extensively used in network security, sensor data analysis, public health and so on. In an outlier detection system, with the continuous expansion of upper-layer applications, a system needs to process a large number of query requests in a very short time, which places high requirements on the timeliness of outlier detection algorithms. To solve this problem, in this paper, an efficient algorithm, R-tree based Outlier Detection Algorithm (RODA), is proposed, which can effectively support single query and multiple query processing. For single query processing, we first extended the R-tree index and proposed a new outlier estimation method. Using the techniques above, the algorithm greatly reduces the retrieval space by preferentially scanning data points with high outlier-degrees. For multiple query processing, the algorithm deeply analyzes the sharing mechanism between multiple queries in order to handle multiple detection tasks within one processing. Finally, experiment results show that the RODA proposed in this paper has improved operating efficiency, and has good applicability and practical significance.

This paper proposes a novel data indexing scheme, the distributed access pattern R-tree (DAPR-tree), for spatial data retrieval in a distributed computing environment. As compared to traditional distributed indexing schemes, the DAPR-tree introduces the data access patterns during the indexing utilization stage so that a more balanced indexing structure can be provided for spatial applications (e.g. Digital Earth data warehouse). In this new indexing scheme, (a) an indexing penalty matrix is proposed by considering the balance of data number, topology and access load between different indexing nodes; (b) an ‘access possibility’ element is integrated to a classic ‘Master-Client’ structure for a distributed indexing environment; and (c) indexing algorithm for the DAPR-tree is provided for index implementations. By using a duplication of official GEOSS Clearinghouse system as a case study, the DAPR-tree was evaluated in a number of scenarios. The results show that our indexing schemes generally outperform (around 9%) traditional distributed indices with the utilization of data access patterns. Finally, we discuss the applicability of the DARP-tree and document DARP-tree shortcomings to encourage researchers pursuing related topics in Big Data indexing for Digital Earth and other geospatial initiatives.

Currently, fuzzy data, linguistic variables, etc. are used. However, modern DBMS lacks support for operations on odd data and means of indexing this data. A solution to the problem of indexing a set of fuzzy values of a linguistic alternative is proposed. Fuzzy variables are represented as closed planar polylines or polygons. To optimize processing, a polygon projection is built, which will be stored in a hierarchical index. A modified R-tree structure is proposed, which is optimized for storing fuzzy values. Internal tree nodes store the minimum bounding spacing for all child nodes, leaf nodes, in addition, store the fuzzy value polygon itself and the polygons corresponding to the specified alpha levels. Leaf nodes have links to neighboring leaf nodes to perform more, less, unequal operations. Modified algorithms for insertion and search in a modified R-tree are proposed. Testing of the proposed algorithms was carried out, which showed not the worst execution time compared to standard R-tree algorithms.

Cloud computing is motivating data owners to outsource their databases to the cloud. However, for privacy concerns, the sensitive data has to be encrypted before outsourcing, which inevitably posts a challenging task for effective data utilization. Existing work either focuses on keyword searches, or suffers from inadequate security guarantees or inefficiency. In this paper, we concentrate on multi-dimensional range queries over dynamic encrypted cloud data. We first propose a tree-based private range query scheme over dynamic encrypted cloud data (TRQED), which supports faster-than-linear range queries and protects single-dimensional privacy. Then, we discuss the defects of TRQED in terms of privacy-preservation. We modify the framework of the system by adopting a two-server model and put forward a safer range query scheme, called TRQED $^{+}$ + . By newly designed secure node query (SNQ) and secure point query (SPQ), we propose the perturbation-based oblivious R-tree traversal (ORT) operation to preserve both path pattern and stronger single-dimensional privacy. Finally, we conduct comprehensive experiments on real-world datasets and perform comparisons with existing works to evaluate the performance of the proposed schemes. Experimental results show that our TRQED and TRQED $^+$ + surpass the state-of-the-art methods in privacy-preservation level and efficiency. [ABSTRACT FROM AUTHOR]

Next-generation enterprise management systems are beginning to be developed based on the Systems of Engagement (SOE) model. We visualize an SOE as a set of entities. Each entity is modeled by a single parent document with dynamic embedded links (i.e., child documents) that contain multi-modal information about the entity from various networks. Since entities in an SOE are generally queried using keywords, our goal is to efficiently retrieve the top-k entities related to a given keyword-based query by considering the relevance scores of both their parent and child documents. Furthermore, we extend the afore-mentioned problem to incorporate the case where the entities are geo-tagged. The main contributions of this work are three-fold. First, it proposes an efficient bitmap-based approach for quickly identifying the candidate set of entities, whose parent documents contain all queried keywords. A variant of this approach is also proposed to reduce memory consumption by exploiting skews in keyword popularity. Second, it proposes the two-tier HI-tree index, which uses both hashing and inverted indexes, for efficient document relevance score lookups. Third, it proposes an R-tree-based approach to extend the afore-mentioned approaches for the case where the entities are geo-tagged. Fourth, it performs comprehensive experiments with both real and synthetic datasets to demonstrate that our proposed schemes are indeed effective in providing good top-k result recall performance within acceptable query response times. [ABSTRACT FROM AUTHOR]

The spatial index structure is one of the most important research topics for organizing and managing massive 3D Point Cloud. As a point in Point Cloud consists of Cartesian coordinates (x , y , z) , the common method to explore geometric information and features is nearest neighbor searching. An efficient spatial indexing structure directly affects the speed of the nearest neighbor search. Octree and kd-tree are the most used for Point Cloud data. However, octree or KD-tree do not perform best in nearest neighbor searching. A highly balanced tree, 3D R*-tree is considered the most effective method so far. So, a hybrid spatial indexing structure is proposed based on octree and 3D R*-tree. In this paper, we discussed how thresholds influence the performance of nearest neighbor searching and constructing the tree. Finally, an adaptive way method adopted to set thresholds. Furthermore, we obtained a better performance in tree construction and nearest neighbor searching than octree and 3D R*-tree. [ABSTRACT FROM AUTHOR]

Space-Filling Curves (SFCs) map a multi-dimensional cellular space into one dimension. Although several algorithms have been introduced that can generate different SFCs, they barely consider deploying SFCs for non-cellular spaces. This article presents a new higher-order functional approach that enables a new level of abstraction which separates the SFC representation (i.e. a set of functions that define the SFC) from the algorithms that use it (e.g. SFC generator, point ordering, etc.). We describe the proposed approach and, as example cases, show how different SFCs can be used as the ordering mechanism for generating the K-d trees and R-trees for a set of arbitrarily distributed points using the proposed higher-order representation of the SFCs. [ABSTRACT FROM AUTHOR]

Complex 3D objects with microstructures can be modelled using the function representation (FRep) approach and then manufactured. The task of modelling a geometric object with a sophisticated microstructure based on unit cell repetition is often too computationally expensive for CAD systems. FRep provides efficient tools to solve this problem. However, even for FRep the slicing step required for manufacturing can take a significant amount of time. An accelerated slicing algorithm for FRep 3D objects is proposed in this paper. This algorithm allows the preparation of FRep models for 3D printing without surface generation stage. The spatial index is employed to accelerate the slicing process. A novel compound adaptive criterion and a novel acceleration criterion are proposed to speed up the evaluation of the defining function of an FRep object. The use of these criteria is significantly reducing the computational time for contour construction during the slicing process. The K-d tree and R-tree data structures are used as spatial indexes. The performance of the accelerated slicing algorithm was tested. The contouring time was reduced 100-fold due to using the novel compound adaptive criterion with the novel acceleration criterion. [ABSTRACT FROM AUTHOR]

Searching and handling geometric data are basic requirements of any Computer Aided Engineering application (CAE). Spatial search and local search has greater importance in CAD and CAE applications for reducing the model preparation time. There are many efficient algorithms being made to search geometrical data. Current neighbour search strategy is limited and not efficient in different CAE platforms. R-tree is tree data structure used for spatial access methods. This paper presents a review of R-tree data structure with its implementation in one of the CAE tool for neighbour search and local search. It satisfies current neighbour search requirements in CAE tools. Results shows considerable amount of time saving compared to the conventional approach. This work concludes that R-tree implementation can be helpful in identifying neighbour part and reducing model preparation time in CAD and CAE tools. [ABSTRACT FROM AUTHOR]

Internet of Things (IoT) has gained significant importance due to its flexibility in integrating communication technologies and smart devices for the ease of service provisioning. IoT services rely on a heterogeneous cloud network for serving user demands ubiquitously. The service data management is a complex task in this heterogeneous environment due to random access and service compositions. In this article, a machine learning aided information management scheme is proposed for handling data to ensure uninterrupted user request service. The neural learning process gains control over service attributes and data response to abruptly assign resources to the incoming requests in the data plane. The learning process operates in the data plane, where requests and responses for service are instantaneous. This facilitates the smoothing of the learning process to decide upon the possible resources and more precise service delivery without duplication. The proposed data management scheme ensures less replication and minimum service response time irrespective of the request and device density. [ABSTRACT FROM AUTHOR]

Searching and handling geometric data are basic requirements of any Computer Aided Engineering application (CAE). Spatial search and local search has greater importance in CAD and CAE applications for reducing the model preparation time. There are many efficient algorithms being made to search geometrical data. Current neighbour search strategy is limited and not efficient in different CAE platforms. R-tree is tree data structure used for spatial access methods. This paper presents a review of R-tree data structure with its implementation in one of the CAE tool for neighbour search and local search. It satisfies current neighbour search requirements in CAE tools. Results shows considerable amount of time saving compared to the conventional approach. This work concludes that R-tree implementation can be helpful in identifying neighbour part and reducing model preparation time in CAD and CAE tools. [ABSTRACT FROM AUTHOR]

This paper proposes a novel data indexing scheme, the distributed access pattern R-tree (DAPR-tree), for spatial data retrieval in a distributed computing environment. As compared to traditional distributed indexing schemes, the DAPR-tree introduces the data access patterns during the indexing utilization stage so that a more balanced indexing structure can be provided for spatial applications (e.g. Digital Earth data warehouse). In this new indexing scheme, (a) an indexing penalty matrix is proposed by considering the balance of data number, topology and access load between different indexing nodes; (b) an 'access possibility' element is integrated to a classic 'Master-Client' structure for a distributed indexing environment; and (c) indexing algorithm for the DAPR-tree is provided for index implementations. By using a duplication of official GEOSS Clearinghouse system as a case study, the DAPR-tree was evaluated in a number of scenarios. The results show that our indexing schemes generally outperform (around 9%) traditional distributed indices with the utilization of data access patterns. Finally, we discuss the applicability of the DARP-tree and document DARP-tree shortcomings to encourage researchers pursuing related topics in Big Data indexing for Digital Earth and other geospatial initiatives. [ABSTRACT FROM AUTHOR]

Time series indexing plays an important role in querying and pattern mining of big data. This paper proposes a novel structure for tightly covering a given set of time series under the dynamic time warping similarity measurement. The structure, referred to as dynamic covering with cross-range constraints (DCRC), enables more efficient and scalable indexing to be developed than current hypercube-based partitioning approaches. In particular, a lower bound of the DTW distance from a given query time series to a DCRC-based cover set is introduced. By virtue of its tightness, which is proven theoretically, the lower bound can be used for pruning when querying on an indexing tree. If the DCRC-based lower bound (LB_DCRC) of an upper node in an index tree is larger than a given threshold, all child nodes can be pruned yielding a significant reduction in computational time. A hierarchical DCRC (HDCRC) structure is proposed to generate the DCRC-tree-based indexing and used to develop time series indexing and insertion algorithms. Experimental results for a selection of benchmark time series datasets are presented to illustrate the tightness of LB_DCRC, as well as the pruning efficiency on the DCRC-tree, especially when the time series have large deformations. [ABSTRACT FROM AUTHOR]

Cloud computing has been one of the critical solutions to reduce heavy storage and computation burden of biometric identification. To protect the privacy of biometric data against untrusted cloud servers, outsourced biometric databases are usually encrypted by users. Performing biometric identification over encrypted data without revealing privacy to cloud servers attracts more and more attention. Several secure biometric identification solutions have been proposed to solve this challenging problem. However, these schemes still suffer from various limitations, such as low search efficiency and heavy computation burden on users. In this paper, we propose a novel cloud-assisted biometric identification scheme based on the asymmetric scalar-product preserving encryption (ASPE) and spatial data structures such as the R-tree index, which simultaneously achieves sub-linear search efficiency and low computation burden on users. Specifically, we construct an R-tree index on the biometric dataset and encrypt the index with ASPE. Then we modify the original search algorithm in the R-tree index and design a secure search algorithm based on ASPE to find the nearest neighbor result over the encrypted R-tree index. Through theoretical analysis and extensive experiments, we demonstrate the effectiveness and efficiency of our proposed approach. [ABSTRACT FROM AUTHOR]

The spatial index is a data structure formed according to the position and shape of the spatial object or the relationship between the spatial objects according to certain rules, and the spatial data is managed by an effective spatial data structure. The quality of a spatial index directly affects the performance of spatial queries. The R-tree index structure is a highly efficient spatial index. According to the R-tree query rule, when performing spatial query, most data that is not related to the query condition can be filtered out, and finally, a few leaf nodes can be accessed to query the data satisfying the condition. Its query performance is affected by factors such as non-leaf node overlap and node space utilisation. This article proposes a lazy splitting method to improve the R-tree construction process. The scheme works as follows: (1) When a node overflows, it creates an overflow node for that node and all overflow nodes are saved in a hash table. (2) If the node continues to insert data, the data are added to its overflow node. (3) When an overflow node is saturated, the node and its overflow node are split into two saturated nodes. We use both simulated and actual data to perform experiments. The experimental results show that an R-tree constructed by the lazy algorithm is superior to an R-tree constructed using the original R-tree PM algorithm or the corner-based splitting (CBS) algorithm based on the number of splits created, the node space used and the efficiency of region queries and k -nearest neighbour (kNN) queries. [ABSTRACT FROM AUTHOR]

Packet classification is a network kernel function that has been widely investigated over the past decade. New networking paradigms, such as software-defined networking and server virtualization, have led to renewed interest in packet classification and its upgrade from classical five-field to many-field classification. With the increasing size of the rule sets and demands for higher throughput, performing many-field packet classification at wire-speed has become challenging. In this paper, we propose an approach to classification by integrating a probabilistic data structure called the Cuckoo filter for approximate membership queries into an R-tree data structure for high-speed, many-field packet classification. Experimental results show that the proposed classifier obtains high throughput of up to 1.5 M packets per second, and requires little memory to support large rule sets (up to 1 million rules). [ABSTRACT FROM AUTHOR]

This paper analyzed the wireless network log data of a university to study the law of crowd aggregation and movement on campus. Firstly, the number of wireless network connections of each building on campus was obtained by distributed statistical algorithms. Secondly, it established the R-tree index of building central latitude-longitude coordinates, and grouped the R-tree leaf nodes to divide the campus into parts. Thirdly, it clustered the building central latitude-longitude coordinates of each part to get the campus area division by the density clustering algorithm. Finally, this paper got the law of crowd aggregation area and movement between areas from clustering results and statistical results. Result of this paper can be used as reference for school bus route planning, shared bicycle deployment and campus function area planning. [ABSTRACT FROM AUTHOR]

Analysts commonly investigate the data distributions derived from statistical aggregations of data that are represented by charts, such as histograms and binned scatterplots, to visualize and analyze a large-scale dataset. Aggregate queries are implicitly executed through such a process. Datasets are constantly extremely large; thus, the response time should be accelerated by calculating predefined data cubes. However, the queries are limited to the predefined binning schema of preprocessed data cubes. Such limitation hinders analysts' flexible adjustment of visual specifications to investigate the implicit patterns in the data effectively. Particularly, RSATree enables arbitrary queries and flexible binning strategies by leveraging three schemes, namely, an R-tree-based space partitioning scheme to catch the data distribution, a locality-sensitive hashing technique to achieve locality-preserving random access to data items, and a summed area table scheme to support interactive query of aggregated values with a linear computational complexity. This study presents and implements a web-based visual query system that supports visual specification, query, and exploration of large-scale tabular data with user-adjustable granularities. We demonstrate the efficiency and utility of our approach by performing various experiments on real-world datasets and analyzing time and space complexity. [ABSTRACT FROM AUTHOR]

Polygon intersection is important for data processing in geographic information systems. For large datasets, spatial indexing methods such as R-tree allow the identification of polygon intersections, but often retrieve inaccurate results. An improved boundary algebra filling (iBAF) method was preliminarily proposed as an alternative to R-tree. However, its applicability, performance, and accuracy require optimization, and its application conditions remain to be unveiled. This study develops version iBAF 2.0 for a more efficient identification and evaluates performance for different computational intensities and applications. Both intersecting polygons and raster zones within intersections can be rapidly grouped in the rasterized cells of input polygons. The resulting polygons can then be generated by configuring the polygon groups or converting the zones into vectors. We use complexity ratio CR, which is defined as the sum of the number of polygons in each actually intersecting group divided by the total number of polygons, to represent the computational intensity. Two land-use datasets containing 4295 and 741,562 polygons are considered, and we establish test cases containing the same polygons with varying CR. Experimental results show that iBAF 2.0 outperforms R-tree when applied to topology verification; however, its performance is conditional for polygon overlay and area calculation between two layers. Specifically, iBAF 2.0 exhibits higher-efficiency grouping of polygons and raster zones when CR exceeds specific thresholds. In addition, better scalability is achieved compared to R-tree when polygons with complex shapes and additional layers are considered. [ABSTRACT FROM AUTHOR]

The spatial index structure is one of the most important research topics for organizing and managing massive 3D Point Cloud. As a point in Point Cloud consists of Cartesian coordinates (x,y,z), the common method to explore geometric information and features is nearest neighbor searching. An efficient spatial indexing structure directly affects the speed of the nearest neighbor search. Octree and kd-tree are the most used for Point Cloud data. However, octree or KD-tree do not perform best in nearest neighbor searching. A highly balanced tree, 3D R*-tree is considered the most effective method so far. So, a hybrid spatial indexing structure is proposed based on octree and 3D R*-tree. In this paper, we discussed how thresholds influence the performance of nearest neighbor searching and constructing the tree. Finally, an adaptive way method adopted to set thresholds. Furthermore, we obtained a better performance in tree construction and nearest neighbor searching than octree and 3D R*-tree.