Spatial range queries play a crucial role in spatial information retrieval. Existing Z-order curve based algorithms suffer from accessing a large number of invalid points outside the query region. To address this challenge, we design a simple yet efficient Z-order curve based learned index, ZPI. Building upon ZPI, we propose a novel spatial range query algorithm, ZPI-RQ. ZPI-RQ leverages efficient decomposition mechanism to address the invalid points issue. To avoid decomposing the query region into a large number of overly small blocks, a query region expansion strategy is further introduced to align each query border with a m-order dividing lines. Experimental results show that ZPI-RQ significantly outperforms state-of-the-art algorithms in query efficiency, achieving a 3.6× improvement over traditional Z-order curve-based algorithms while accessing only 1% invalid points.

Connected and Autonomous Vehicles (CAVs) equipped with diverse sensors can enhance environmental perception through cooperative sensing, overcoming individual sensor limitations such as restricted range and occlusion. However, privacy concerns regarding location exposure and data leakage significantly hinder widespread adoption. This paper presents a comprehensive privacy-preserving cooperative sensing framework that enables secure data sharing among CAVs without compromising performance. We introduce two key innovations: the Vehicular Spatial Index Tree (VSITree), which provides efficient spatial indexing while preventing location leakage through cryptographic encoding, and the Vehicular Attribute Matching Protocol (VAMP), which enables oblivious membership testing between encrypted sensing data and queries. Our framework leverages arithmetic secret sharing and predicate encryption to protect both sensing providers and requesters throughout the data lifecycle. The system is designed to operate through roadside units (RSUs) that facilitate secure matching and aggregation without learning sensitive information. Theoretical analysis and extensive simulations demonstrate the security and efficiency properties of our approach, confirming its resilience against various attack vectors while maintaining real-time performance suitable for safety-critical vehicular applications.

Vehicular crowdsensing enables Connected and Autonomous Vehicles (CAVs) to jointly contribute driving-related data to support applications such as traffic management and accident analysis. Ensuring the reliability of such data requires identifying observations that have been corroborated by multiple vehicles. However, achieving this corroboration typically necessitates comparing each vehicle’s private set of observations, which can inadvertently reveal sensitive trajectory information. To address this privacy challenge, we introduce Edge-Assisted Private Set Intersection (EA-PSI), a scheme that enables secure computation of the intersection among CAV observation sets without disclosing individual data elements. Our design begins with a protocol that leverages polynomial-based set encoding and additive secret sharing, in which each vehicle encodes its observation set as a polynomial and divides it into two shares, delegating one share to a roadside unit (RSU) while retaining the other locally. The RSU then performs intersection computation on the collected shares using randomized encoding techniques, without learning any private observations or intersection results. To support necessary polynomial operations over secret-shared data, we develop a secure multiplication mechanism based on Beaver triples, enabling the RSU and vehicles to jointly compute polynomial products without reconstructing underlying values. In addition, we design a key-distribution protocol that facilitates secure communication among vehicles through the RSU, eliminating the need for direct vehicle-to-vehicle exchange. We analyze the security of EA-PSI under the simulation-based paradigm and formally prove privacy against semi-honest adversaries. Experimental evaluation of computational and communication costs demonstrates the efficiency and practicality of the proposed EA-PSI scheme.

Database query processing and optimization are critical components of modern database management systems (DBMS) that efficiently process user queries. In big data application scenarios, the movement of large volumes of data influences performance, power efficiency, and reliability, which are the three essential aspects of a computing system. Large-scale data centers require an exceptionally efficient server and storage infrastructure. The systems currently employed for managing and processing big data are increasingly showing inefficiency, both in terms of energy usage and scalability, primarily due to the constraints imposed by existing CPU architectures. A significant challenge in Database Management Systems (DBMS) is the growing disparity between the speeds of processors and memory access, which results in notable performance bottlenecks. This paper presents a comprehensive survey of reconfigurable acceleration in database systems, offering a structured taxonomy that categorizes existing work based on query types, integration models, and hardware/software co-design strategies. We examine key acceleration techniques across relational operators, indexing, join algorithms, and compression, highlighting their trade-offs in performance, scalability, and adaptability. Furthermore, we identify current limitations in programmability, data movement, and workload variability, and outline open research challenges including dynamic reconfiguration, hybrid architectures, and compiler support. This taxonomy-driven perspective aims to guide both researchers and practitioners in navigating the design space and pushing the boundaries of FPGA-accelerated data processing.

Industrial Internet of Things (IIoT) systems in sectors like manufacturing, energy, and healthcare are increasingly deployed in cloud-assisted operational environments, where network telemetry and security analytics are routinely processed in the cloud. However, these systems remain highly vulnerable to cyber threats from shared threat actors. Among these, low-rate Denial of Service (LDoS) attacks, marked by subtle periodic traffic patterns, are particularly challenging to detect when analyzed in isolation. Cross-organization collaborative detection across cloud platforms can improve identification accuracy, but sharing threat intelligence risks exposing sensitive operational information. To tackle this challenge, we propose Labelled-Threshold Private Set Intersection (LT-PSI), a cryptographic framework that allows two organizational clouds to securely identify common elements whose associated label vectors satisfy a similarity threshold, without revealing any additional data. Our LT-PSI protocol introduces an innovative combination of position encoding, Diffie-Hellman Oblivious Pseudorandom Functions (DH-OPRF), and Bloom filters, effectively transforming threshold-based label similarity matching into efficient and privacy-preserving set membership tests. Particularly, our protocol achieves sublinear online complexity and is well-suited for cloud execution, integrating an adaptive early termination strategy that significantly reduces the number of OPRF invocations. We provide formal security proofs under the semi-honest model and validate the protocol through extensive experiments across diverse similarity thresholds and dataset sizes. Results show that LT-PSI is significantly more efficient than brute-force threshold matching while preserving privacy. The framework naturally supports cloud-to-cloud collaborative security analytics and generalizes to broader cloud and edge threat intelligence scenarios requiring private, threshold-based feature matching.

This paper introduces HQT-TI, a novel indexing method designed to improve the efficiency of spatial keyword queries. HQT-TI consists of two main components: a Hilbert QuadTree (HQT) based spatial index and a Trie-Inverted index (TI) combined textual index. HQT integrates the Hilbert curve with a Quadtree, establishing a direct relationship between the two. TI combines a trie and inverted index to minimize the intersection cost associated with long lists, thus improving the speed of keyword queries. The HQT based Spatial Query algorithm (HQT-SQ) reduces overlap checks and limits irrelevant object retrieval by employing query drill-down and depth first search with limited breadth expansion in spatial queries. Meanwhile, the Segment List Intersection based Keyword Query algorithm (SLI-KQ), built on TI, efficiently handles segment list intersections for keyword queries. The combination of HQT-SQ and SLI-KQ results in HS-SK, a highly efficient spatial keyword query algorithm. Extensive experimental results demonstrate that HS-SKQ outperforms SFC-Quad by up to two orders of magnitude, achieving up to a 5.46× speedup over the best existing competitors, making it a promising solution for large-scale spatial keyword query processing.

Aging in Place (AiP) programs enable elderly individuals to live independently and comfortably within their homes and communities by utilizing technological innovations such as smart homes and remote healthcare monitoring. In practical AiP scenarios, data necessary for accurate health predictions are typically vertically partitioned across multiple medical institutions, raising significant privacy concerns during data integration and analysis. To address this challenge, we propose an efficient and privacy-preserving logistic regression (LR) prediction scheme tailored explicitly for vertically partitioned AiP data. Our scheme effectively combines the computational efficiency of Trusted Execution Environments (TEE) under the honest-but-curious model with cryptographic security based on the Matrix Diffie-Hellman (MDDH) assumption. Security analysis confirms that our approach provides privacy protections against honest-but-curious adversaries. Extensive experimental evaluations demonstrate that our proposed scheme achieves computational efficiency, privacy protection, and practical scalability for real-world AiP implementations.

Set Similarity Query (SSQ) is widely applied in various fields. The existing B+-tree-based SSQ approaches fail to fully exploit length filtering and require calculating similarity bounds in a node-wise manner, leading to low efficiency. To address these issues, we propose LeB, a novel length-enhanced B+-tree index, whose keys integrate set lengths and bucket mapping, enabling the direct pruning of sets that do not meet the length requirements. Building upon LeB, we present an efficient algorithm, LeBQ, which leverages length filtering and symmetric difference allocation to determine the key bounds for a query, enabling the key bounds computation only once for each query$Q$and avoiding costly similarity bounds computation in a node-wise manner. Efficient key filtering strategies are proposed to prune sets that cannot be similar, significantly reducing the number of candidates. Based on LeBQ, LeBQ+ further reduces the number of candidates by introducing length-independent key bounds. Experimental results on four real datasets demonstrate that LeBQ+ has a higher node access efficiency and accesses only 3.08% to 27.47% nodes compared to the existing B+-tree-based SSQ algorithm. LeBQ+is up to 99.8 × faster than the state-of-the-art algorithms.

As the global population continues to age rapidly, Aging in Place (AiP) solutions have become increasingly vital for enabling elderly individuals to maintain their independence and continue living comfortably in their own homes. These solutions leverage advanced technologies such as smart homes and remote health monitoring. However, in real-world AiP applications, the health data needed for accurate predictions is often spread across multiple medical institutions, which raises signficant privacy concerns when integrating and analyzing the data. To address this challenge, we propose an efficient and privacy-preserving AdaBoost learning framework for vertically partitioned AiP data by utilizing Symmetric Homomorphic Encryption (SHE) technique. To ensure compatibility with the integer-based constraints of SHE, we adopt a straightforward weight quantization strategy by representing AdaBoost sample weights as integers. This design simplifies encrypted computation and maintains the boosting mechanism’s effectiveness. Our theoretical and experimental evaluations validate both the accuracy and security of the proposed framework, highlighting its practical viability for deployment in real-world AiP systems.

The rapid rise in spatial data volumes from diverse sources necessitate efficient spatial data processing capability. Although most relational databases support spatial extensions of SQL query features, they offer limited scalability. Traditional relational database query processing follows a pull-based (or tuple-at-a-time) model of query processing. This is not efficient for processing large volumes of data. A number of specialized spatial data processing systems were developed that extend cluster computing frameworks, such as Spark and Hadoop. However, these systems are characterized by limited or no support for spatial SQL query execution. The few systems that support SQL querying, suffer from the overheads of the pull-based model.We present a compilation-based distributed SQL query processing system. It follows a data-centric query compilation approach that takes a SQL query and generates distributed C++ (UPC++) based physical query plans. The generated code is compiled and executed on a distributed in-memory high performance framework based on the Partitioned Global Address Space (PGAS) paradigm. We also introduce morsel-driven parallelism for scalable spatial query execution in a distributed runtime. We conduct experimental evaluation of our system with two real-world datasets on a number of spatial query workloads. Experimental results demonstrate that our system performs significantly better than a leading spatial big data system Apache Sedona and distributed parallel relational database Citus.

With the technological advances in creation and capture of 3D spatial data, new emerging applications are being developed. Digital Twins, metaverse and extended reality (XR) based immersive environments can be enriched by leveraging geocoded 3D spatial data. Unlike 2D spatial queries, queries involving 3D immersive environments need to take the query user’s viewpoint into account. Spatio-visual queries return objects that are visible from the user’s perspective.In this paper, we propose enhancing 3D spatio-visual queries with large language models (LLM). These kinds of queries allow a user to interact with the visible objects using a natural language interface. We have implemented a proof-of-concept prototype and conducted preliminary evaluation. Our results demonstrate the potential of truly interactive immersive environments.

Indexes in database systems such as B+trees and hash tables retrieve data quickly. Much research has been conducted on the faster index lookup in recent years. A learned index is one such area of study. Learned index approaches, such as radix spline (RS) [1] can achieve significant performance improvement over traditional indexing techniques. However, query performance with learned indexes is limited by the constraints imposed by CPU architecture. This paper introduces a novel methodology that leverages the benefits of learned indexes and FPGAs. We term this approach as the Selective Mathematical operation AcceleRaTion (SMART) with an FPGA for an end-to-end acceleration of learned indexes. As a hybrid of CPU and FPGA approaches, the SMART model of index acceleration surpasses the throughput of CPU-based implementations while preserving the data structure storage on the CPU. Our proposed FPGA-based RS learned index architecture (Figure 1) consists of two major stages: Build and Lookup. The Build model$(SMART-RS_{Build})$accelerates the build stage on an FPGA, while the Lookup model$(SMART-RS_{Lookup})$executes the FPGA-based lookup acceleration. The build stage is accelerated by offloading the computationally intensive interpolation operation onto an FPGA. In this stage, the index data is stored on a CPU while the interpolation operation is executed on an FPGA. As shown in Figure 1, input to the FPGA-based$SMART-RS_{Build}$are key, max spline error, and previously stored CDF point. Here, the$X$and$Y$coordinates are the bounding box of a spline. The FPGA-based build-stage accelerator will output the orientation type: clockwise (CW), counter-clockwise (CCW), or collinear. Based on the orientation obtained, upper and lower limits are set and the previous CDF point is stored as the next spline point. RadixSpline is constructed over a sorted data set. The module AddKeyToSpline iterates over the input sorted data set and will create the array of resultant splines. The decision-making in deciding the orientation type is offloaded to the module SMART-@$RS_{Build-Interp}$on the FPGA. The output from the FPGA is the type of orientation that will make the following decision during spline construction: Store the input key and its position in the dataset in the spline points array (SplinePoints). • Store the spline index in the radix table (Radix TABLE). • Update the upper and lower error bounds. In the lookup stage acceleration, the radix table and set of spline points are offloaded to our lookup-stage accelerator (SMART@$RS_{Lookup}$), where they are stored in BRAMs/SRLs as partitioned arrays. With our approach, Speedup of 5.5× as compared to a CPU -based RS index. • Specific compute-intensive operations were identified, thereby avoiding the need for a full-scale FPGA implementation. • Complexities associated with debugging RTL-related issues were reduced. • Controlled on-chip and off-chip memory resource usage. • More accurate comparison between CPU and FPGA implementations.

Driven by the need to support spatial data applications, most relational databases offer spatial SQL query features. However, traditional relational databases are not scalable, and their query processing follows a pull-based tuple-at-a-time model, which is not efficient for large data volumes. Although several specialized spatial data processing systems were developed by extending frameworks, such as Spark and Hadoop, these systems offer limited or no support for spatial SQL query execution. The few systems that support SQL querying, suffer from the overheads of the pull-based model.

With growing adoption of blockchain in established and emerging applications, there is an increasing need to support efficient ad hoc querying of authenticated historical data. This is especially true in fields such as healthcare to meet the rigorous security and regulatory requirements of ever-expanding digital health platforms. Existing blockchain systems, however, offer little or no support for querying capabilities over historical data. Although a full blockchain archive node can be used to maintain historical records of all executed transactions on the chain, it is not scalable when dealing with large volumes of data. Moreover, such ‘offline’ historical data lack tamper evidence support. To address these issues, we introduce an authenticated index structure called Authenticated Multi-Version Skip List (AMVSL), designed to support a rich set of query features over historical blockchain data. We further present three range queries: SVRK, MVRK, and MVAK, which offer querying over a range of keys and a range of versions. Our experimental evaluation of two healthcare-inspired examples demonstrates that AMVSL efficiently supports these queries and can achieve performance that is several orders of magnitude faster than existing authenticated data structures.

Worker selection that is often outsourced to a cloud server is crucial for the success of the Mobile Crowdsensing (MCS) system, in which the spatial constraint plays a fundamental role in selecting workers. To protect the location information involved in the spatial constraint, several privacy-preserving worker selection schemes were proposed. However, they either only support a specific spatial range or cannot trace the workers who leak secret keys. In this paper, we propose a traceable and privacy-preserving worker selection scheme that can support arbitrary spatial ranges when selecting workers and trace the worker when his/her secret key is leaked to the cloud server for inferring location information. Security analysis demonstrates the privacy preservation and traceability of our proposed scheme, and the evaluation results illustrate its efficiency.

Vast amounts of data are stored in raw data files. Data scientists and practitioners typically use data science frameworks for data analysis on raw data. Among them, Python Pandas library is one of the most popular language-based frameworks. On the other hand, relational databases (RDBMSs) are still widely used for SQL query execution. Before querying, raw data must be loaded into RDBMSs through an ETL process. Conversely, data stored in RDBMSs may need to be exported out or moved into a suitable format to perform complex data analysis. This movement of data adversely affects the time-to-insight.

Recently, researchers have demonstrated that learned index can improve query performance while reducing the storage overhead. It potentially offers an opportunity to address the spatial query processing challenges caused by the surge in location-based services. Although several learned indexes have been proposed to process spatial data, the main idea behind these approaches is to utilize the existing one-dimensional learned models, which requires either converting the spatial data into one-dimensional data or applying the learned model on individual dimensions separately. As a result, these approaches cannot fully leverage or take advantage of the information regarding the spatial distribution of the original spatial data. To this end, in our previous work, we proposed a spatial (multi-dimensional) interpolation function based learned model to develop a spatial learned index and designed efficient range and $k$ NN query strategies over it. However, there are some limitations in the proposed learned model, such as the prediction accuracy and index building time. In this paper, we address the limitations of our previous work and propose a new spatial learned model by employing the characteristics of the spatial interpolation functions and a novel dynamic encoding technique. Detailed experiments are conducted with real-world datasets. The results indicate that our new proposed learned model is better than our previous one in terms of building time, prediction accuracy, and storage overhead simultaneously, and the new learned spatial index is better than the existing learned spatial indexes in query execution time and index building time.

As a popular and practical query type in location-based services, the spatial keyword query has been extensively studied in both academia and industry. Meanwhile, with the growing demand for data privacy, many privacy-preserving spatial keyword query schemes have been proposed to deal with queries over encrypted data. However, none of the existing schemes preserve access pattern privacy, and the recent research illustrates that leaking such privacy may incur inference attacks and thus disclose sensitive information. In addition, most existing schemes only consider the boolean keyword search, which is not quite practical and flexible in real-world applications. To address the above issues, in this paper, we propose two privacy-preserving spatial keyword similarity query schemes that can preserve full and partial access pattern privacy, respectively. First, we present a basic privacy-preserving spatial keyword similarity query scheme (PPSKS) by integrating a secure set membership test (SSMT) technique with secure circuits. After that, to improve performance, we propose a tree-based scheme (PPSKS+) by employing a new index called FR-tree together with a predicate encryption technique that can encrypt FR-tree. Formal security analysis shows that: i) our proposed schemes can protect outsourced data, query requests, and query results; ii) our PPSKS scheme can hide full access patterns, while the PPSKS+ scheme preserves$m$-access pattern privacy. Extensive experiments are also conducted, and the results indicate that our tree-based PPSKS+ scheme is much more efficient, almost two orders of magnitude better than our linear search PPSKS scheme in performing queries.

Skyline queries, especially those variants that allow users to define their own query criteria, are very promising and practical techniques in multi-criteria decision making applications. Meanwhile, the growing data volume drives the service providers to outsource their data to the cloud for reaping economic benefits. However, privacy concerns compel the outsourced data to be encrypted and require to perform the skyline queries over encrypted data. To achieve the privacy-preserving skyline queries, many schemes were proposed in the literature. However, those existing solutions cannot fully support the user-defined query criteria in skyline queries, and most of them employ a two-server model to support skyline queries over ciphertexts, which needs multi-round communications between the deployed two servers. In this article, we propose a privacy-preserving user-defined skyline query scheme in a single-server model, which eliminates extra communications. Specifically, we first formally define the user-defined skyline query. Then, based on the idea of converting order relations into computing the inner products of two multi-dimensional points, we design three predicate encryption schemes. Finally, we adopt these predicate encryption schemes to construct our proposed scheme. Detailed security analysis shows that these predicate encryption schemes are selectively secure, and the proposed user-defined skyline query scheme is privacy-preserving. In addition, extensive experiments are conducted, and the results show that our proposed scheme outperforms the alternative scheme by up to an order of magnitude in terms of computational costs when performing user-defined skyline queries.

Outsourcing encrypted time series data and query services to a cloud has been widely adopted by data owners for economic considerations. However, it inevitably lowers data utility and query efficiency. Existing secure skyline query schemes either leak critical information or are inefficient. In this paper, we propose an efficient and privacy-preserving interval skyline query scheme by employing symmetric homomorphic encryption (SHE). Specifically, we first devise a secure sort protocol to sort the encrypted dataset and a secure high-dimensional dominance check protocol to securely determine dominance relations of time series data, in which a dominance check tree is presented. With these secure protocols, we propose our secure skyline computation protocol that can ensure both security and efficiency. Furthermore, to deal with the characteristics of time series data, we design a look-up table to index time series for quick query response. The security analysis shows that our proposed scheme can protect outsourced data, query results, and single-dimensional privacy and hide access patterns. In addition, we evaluate our proposed scheme and compare the core component of our scheme with the state-of-the-art solution, and the results indicate that our protocol outperforms the compared solution by two orders of magnitude in the computational cost and at least 23× in the communication cost.

Secure queries are fundamental to data security, particularly in cloud databases. In data analytics, one of the common and practical queries is the iceberg query that can find aggregate values above a specified threshold. However, existing secure aggregate query schemes: 1) are unable to support secure iceberg queries equipped with the HAVING clause; 2) only consider additive aggregate functions; and 3) suffer from performance issues due to the use of homomorphic encryption to encrypt databases. In this article, we present a secure iceberg query scheme, SecBerg, to support both addition-based and comparison-based aggregate functions and ensure high efficiency and security simultaneously. To make it possible, we propose a secure bitmap index system to encode database values and pioneer the use of the arithmetic secret sharing technique to protect databases in the cloud environment. Furthermore, we carefully design efficient and secure protocols over arithmetic secret sharing to construct our SecBerg. Extensive evaluations are conducted, and the results indicate that SecBerg is significantly more efficient than the state-of-the-art relevant scheme in computational overhead and can attain orders of magnitude performance improvement at best.

Exploratory data analysis, which is at the heart of data science workflows, is becoming important due to the rapid rise in spatio-temporal data volume, and popularity of Web and mobile mapping applications. Such exploratory data analysis often involves the user selecting an arbitrary polygon region to perform a statistical computation on the selected region. Existing approaches for spatio-temporal data aggregation support rectangular query regions only, and not arbitrary polygons. A recently proposed system called GeoBlocks supports polygonal queries, but GeoBlocks was designed for spatial data, not spatio-temporal data. Another aspect of exploratory data analysis is that the users often repeatedly perform similar statistical analyses over the same selected query region. Although the reuse of already computed answers can improve the response time, existing approaches do not support this reuse for advanced statistical analysis. Data Canopy is a recently proposed approach that supports statistics synthesis by reusing basic aggregates, however, it does not support spatial or spatio-temporal analysis.To address the mentioned challenges, we introduce ScanCube, an exploratory statistical analysis system over any arbitrary polygonal query region for any time interval. ScanCube also supports statistics synthesis by reusing a small set of basic aggregates that are computed and stored a priori. We introduce two techniques, ScanX1 and ScanX2, for providing a grid-based polygonal approximation, which offers distance-based bounded error. Experimental evaluation suggests that ScanCube significantly outperforms GeoBlocks.

Applying skyline queries to medical data can considerably benefit medical analysis in eHealthcare. However, as medical data often involves sensitive personal data, privacy concerns have become a significant impediment to the development of eHealthcare. Although several privacy-preserving skyline query schemes in eHealthcare have been put forth, they need a trusted platform to generate and assign secret keys for the multi-source scenario. In addition, those schemes incur non-trivial computational costs on resource-limited entities. To address these limitations, we propose a novel privacy-preserving skyline query scheme, named PPsky, based on arithmetic secret sharing, in which a series of secure protocols are designed to handle the basic operations in skyline queries. Security analysis illustrates that our PPsky scheme is privacy-preserving, and the evaluation results also validate the efficiency of our PPsky scheme.

Worker selection is one of the most fundamental problems in Mobile Crowdsensing (MCS) applications. In this paper, we formulate a practical worker selection scenario in MCS services where the selected workers should meet both the spatial and temporal constraints. To protect participants’ (both the task requestor and the workers) personal information from being disclosed, we design a privacy-preserving worker selection scheme based on the Symmetric Homomorphic Encryption (SHE) technique. Besides, we devise a pre-filtering process to further increase the efficiency of the worker assignment process. Security analysis shows that our proposed scheme can achieve the desirable security properties. In addition, extensive experiments are conducted to validate the effectiveness of the proposed scheme.

Mobile Crowdsourcing (MCS) is a newly-emerged sensing paradigm where a group of workers is selected to collect and share real-time data for a particular task. With the recent advances of Internet of Things (IoTs), cloud computing, and 5G network, MCS has drawn great attention in recent years. Worker selection is one of the most fundamental problems in MCS, as the selected workers’ qualifications play a significant role in the service quality. In this paper, by extending the research scope of previous literature, we formulate a novel worker selection problem in MCS that incorporates spatial-temporal constraints over workers’ tentative future trajectories. Specifically, each worker is required to submit a tentative future trajectory in advance and the MCS platform only selects qualified workers who meet both the spatial and temporal constraints. To increase the efficiency of worker selection, we propose a hybrid indexing approach to efficiently index workers’ spatial-temporal information by combining MX-CIF quadtree and Interval tree. Besides, we design a greedy algorithm, which considers both the reliability of the selected workers and the overall budget at the same time. Furthermore, to protect workers’ sensitive spatial-temporal information from being disclosed to untrusted parties, we design a privacy-preserving technique by transferring workers’ real spatial-temporal information to the approximate data with restricted information. Security analysis shows that the proposed solution is privacy-preserving. Extensive experiments are conducted, and the results demonstrate that our scheme outperforms the baseline methods.

Wireless body area network (WBAN) and big data techniques indubitably enable the online medical diagnosis system to be more practical. In the system, to make a more accurate diagnosis, doctors wish to obtain some archived medical data records, which are similar to the sensed patient data, to learn from the prior diagnoses. As a practically useful similarity search, the dynamic skyline query can provide doctors with similar data records having all possible relative weights of attributes. Driven by the powerful cloud, the data owner often outsources encrypted data and the corresponding services, e.g., dynamic skyline query services here, to a third-party cloud. As a result, it is required to perform the dynamic skyline query over encrypted data. However, existing schemes are either insecure or inefficient. To address the issue, in this article, we propose an efficient and privacy-preserving dynamic skyline query scheme and use it in an online medical diagnosis system. Specifically, based on symmetric homomorphic encryption (SHE), we present a set of efficient and secure protocols to achieve various operations, such as less than comparison, equality test, and dominance determination, without leaking any sensitive information to the cloud. With these secure protocols, we carefully design our dynamic skyline query scheme to attain full security and high efficiency at the same time. Detailed security analysis shows that our proposed scheme is indeed privacy-preserving. With extensive experimental evaluations, we show that our proposed scheme outperforms the alternative scheme by two orders of magnitude in the computational cost and at least$8.1\times $in the communication cost.

Aggregate nearest neighbor (ANN) query, which can find an optimal location with the smallest aggregate distance to a group of query users’ locations, has received considerable attention and been practically useful in many real-world location-based applications. Nevertheless, query users still hesitate to use these applications due to privacy concerns, as there is a worrisome that the location-based service (LBS) providers may abuse their locations after collecting them. In this article, to tackle this issue, we propose a novel privacy-preserving aggregate query (PPAQ) scheme to select an optimal location for query users in road networks. Specifically, we first analyze the problem of the ANN query in road networks and identify two basic operations, i.e., addition and comparison, in the query. Then, we carefully design efficient addition and comparison circuits to securely add and compare two bit-based inputs, respectively. With these two secure circuits, we propose our PPAQ scheme, which can simultaneously protect the users’ locations, query results, and access patterns from leaking. Detailed security analysis shows that our proposed scheme is indeed privacy-preserving. In addition, extensive performance evaluations are conducted, and the results indicate that our proposed scheme has an acceptable efficiency for non-real-time applications.

Outsourcing data to the cloud has become popular due to the big data challenges. However, security concerns compel the outsourced data to be encrypted before sending them to the cloud, which lowers their utility and efficiency. The range query plays a significant role in common queries. Consequently, how to efficiently support the range query over encrypted data has become an important challenge. Previously reported schemes either achieve efficiency only in a specific operation or have severe defects in scalability. To address these limitations, we propose a framework, called SOREL, which simultaneously considers security, efficiency and scalability. Specifically, we first propose a new efficient and Secure Order Revealing Encryption (SORE) scheme, which is more secure than bit-based ORE schemes. Then, by employing the proposed SORE scheme, we design a novel index within our framework SOREL to support efficient updating and query operations over encrypted data. Detailed security analysis shows that our SOREL achieves the desirable security requirements. Additionally, results from extensive evaluations indicate that i) SORE outperforms other alternative schemes by at least 8; and ii) SOREL is at least 3faster than the comparative schemes with range query operation in the best case while ensuring the competitiveness with insertion operation.

It has been witnessed that Aggregate Reverse Skyline (ARS) query has recently received a wide range of practical applications due to its marvelous property of identifying the influence of query requests. Nevertheless, the query users may hesitate to participate in such query services as the query requests and query results may leak sensitive personal data or valuable business data assets to the service providers. To tackle the concerns, a promising solution is to encrypt the query requests, conduct the ARS queries over encrypted query requests without decrypting, and return the encrypted query results. Unfortunately, many existing solutions are either deployed over a two-server model or unable to fully preserve query privacy. In this paper, we propose a novel privacy-preserving aggregate reverse skyline query (PPARS) scheme on a single server model while ensuring full query privacy. Specifically, we first transform the problem of ARS query into a combination of set membership test and logical expressions. Then, by employing the prefix encoding technique, bloom filter technique, and fully homomorphic encryption, we run the transformed logical expressions to obtain the encrypted aggregate values without leaking query requests, query results, and access patterns. Furthermore, we propose an interpolation-based packing technique to improve the communication efficiency of PPARS. Detailed and formal security analysis demonstrates that our proposed schemes can guarantee strong security. In addition, extensive experiments are conducted, and the results validate the efficiency of our proposed schemes.

In recent years, with the increased usage of the Internet of Things (IoT) devices, cyber-attacks have become a serious threat over the Internet. These devices have low memory capacity and processing power, which makes them easy targets for attackers. The research community has proposed different approaches to deal with emerging variants of attacks on IoT devices using various machine learning techniques. However, these approaches rely heavily on the classifier’s categorization of a given record while ignoring its confidence. This paper proposes a verification-based scheme to reject IoT attacks by utilizing the classifier’s confidence. At the same time, existing studies are evaluated using traditional cross-validation approaches (e.g., k-fold), thus, not tested against unknown attacks. We propose using the leave-one-attack-out (LOAO) cross-validation scheme to evaluate the generalizability of the application to unknown attacks. The experiments are performed on Med BIoT, a publicly available dataset consisting of three IoT attacks. The system’s robustness is evaluated in terms of Receiver Operating Curves (ROC) and Equal Error rates (EERs). The results indicate a lower false-positive rate of 12.6% using the proposed verification-based approach in comparison to k-fold cross-validation.

Due to the rapidly rising data volume, there is a need to analyze this data efficiently and produce results quickly. However, data scientists today need to use different systems, since presently relational databases are primarily used for SQL querying and data science frameworks for complex data analysis. This may incur significant movement of data across multiple systems, which is expensive. Furthermore, with relational databases, the data must be completely loaded into the database before performing any analysis. We believe that data scientists would prefer to use a single system to perform both data analysis tasks and SQL querying, without requiring data movement between different systems. Ideally, this system would offer adequate performance, scalability, built-in data analysis functionalities, and usability. We present DaskDB, a scalable data science system with support for unified data analytics and in situ SQL query processing on heterogeneous data sources. DaskDB supports invoking Python APIs as User-Defined Functions (UDF). So, it can be easily integrated with most existing Python data science applications. Moreover, we introduce a distributed index join algorithm and a novel distributed learned index to improve join performance. Our experimental evaluation involve the TPC-H benchmark and a custom UDF benchmark, which we developed, for data analytics. And, we demonstrate that DaskDB significantly outperforms PySpark and Hive/Hivemall.

As one of the most fundamental problems in mobile crowdsensing (MCS), worker selection has drawn significant attention in recent years. However, very few studies consider the workers' spatio- and temporal-coverage for the sensing task. In this paper, we propose a novel top-k worker selection scheme such that the MCS platform can select qualified workers in terms of spatio-temporal similarity. Besides, we design a novel privacy-preserving approach for protecting participants' spatio-temporal information based on the modified Paillier encryption technique. Detailed security analysis showed that the task re-questor's temporal information and the workers' spatio-temporal information are preserved and will not be revealed to any other parties. Extensive experiments are conducted, and the results demonstrate that our scheme outperforms the baseline methods regarding the selection of reliable workers.

Due to the rapid growth in the use of location based services (LBS), abundant spatially referenced text data is being generated. Hence, spatio-textual queries and in particular, spatio-textual join have gained prominence in recent times. Spatio-textual similarity join (STSJ) is an expensive operation, which is used to retrieve documents that are both textually relevant and spatially nearby. NUMA architectures are becoming increasingly prevalent in modern multi-core machines. Applications that are agnostic of the underlying NUMA topology may not be able to fully exploit the hardware. Due to the compute intensive nature of STSJ, efficient processing of STSJ is important, particularly in the context of NUMA architectures. Previous work on spatio-textual similarity join has not addressed this challenge. To remedy this, we explore several approaches to parallelize spatio-textual similarity join on modern NUMA architecture machines. Specifically, we propose three NUMA-aware algorithms. Our best-performing NUMA-aware algorithm exploits topology-aware work-stealing with adaptive data placement. Experimental evaluation involving four real-world datasets (on two different hardware architectures) demonstrates that our NUMA-aware algorithms perform significantly better than existing approaches that do not consider NUMA-awareness.

A corpus of recent work has revealed that the learned index can improve query performance while reducing the storage overhead. It potentially offers an opportunity to address the spatial query processing challenges caused by the surge in location-based services. Although several learned indexes have been proposed to process spatial data, the main idea behind these approaches is to utilize the existing one-dimensional learned models, which requires either converting the spatial data into one-dimensional data or applying the learned model on individual dimensions separately. As a result, these approaches cannot fully utilize or take advantage of the information regarding the spatial distribution of the original spatial data. To this end, in this paper, we exploit it by using the spatial (multi-dimensional) interpolation function as the learned model, which can be directly employed on the spatial data. Specifically, we design an efficient SPatial inteRpolation functIon based Grid index (SPRIG) to process the range and kNN queries. Detailed experiments are conducted on real-world datasets. The results indicate that, compared to the traditional spatial indexes, our proposed learned index can significantly improve the index building and query processing performance with less storage overhead. Moreover, in the best case, our index achieves up to an order of magnitude better performance than ZM-index in range queries and is about 2.7 × , 3 × , and 9 × faster than the multi-dimensional learned index Flood in terms of index building, range queries, and kNN queries, respectively.

The emergence of mobile crowdsensing (MCS) has provided us with unprecedented opportunities for both sensing coverage and data transmission. However, in many MCS applications, the MCS workers are usually required to report the location information of the assigned tasks, which inevitably reveals the workers' location information, even trajectories, and severely impedes the popularization of the MCS system. It is believed that the query on the most-frequent location, e.g., querying the most congested location over a period in a city, is one of the most popular statistics queries in the MCS system, but it may disclose workers' location information. To address the issue, in this article, we propose a location privacy-preserving scheme for outsourced most-frequent item query in the MCS system, where two noncollusive semi-trusted cloud servers cooperatively handle the most-frequent item query. Specifically, by employing our pseudonymization mechanism, transposition cipher, ciphertext packing technique, and order-preserving merge function, our proposed scheme can efficiently answer the most-frequent item query while ensuring the privacy of both workers' personal information and query results. Detailed security analysis shows that our proposed scheme is privacy-preserving. In addition, extensive experiments are conducted, and the results show that our proposed scheme outperforms alternative schemes in terms of computational costs and communication overhead.

With the emergence of wearable technology, IoT, and Edge computing, the nature of healthcare is rapidly shifting towards digital health aided by these ICT technologies. At the same time, consumer devices, such as smart, wearable fitness watches are gaining market share as a way to monitor physical activity and wellness. Despite these advances, and their ability to capture longitudinal behavioural patterns, these devices have yet to be fully leveraged within the healthcare system. If the user-generated data from such devices could be collected without com-promising an individual’s privacy, these insights could comprise part of a more holistic and preventative healthcare solution. In this article, we propose an Edge-assisted data analytics frame-work that uses Federated Learning to re-train local machine learning models using user-generated data. This framework could leverage pre-trained models to extract user-customized insights while preserving privacy and Cloud resources. We also identify some potential application scenarios and discuss research challenges to be explored within the proposed framework.

Spatio-textual similarity join is an operation for finding documents, which are both spatially close and textually relevant. Joins in databases are considered to be the most expensive operation; similarly spatio-textual similarity join is a resource intensive operation. Therefore, it is natural to consider approaches to parallelize this operation.

Data analytics systems commonly utilize in-memory query processing techniques to achieve better throughput and lower latency. Modern computers increasingly rely on Non-Uniform Memory Access (NUMA) architectures to achieve scalability. A key drawback of NUMA architectures is that many existing software solutions are not aware of the underlying NUMA topology and thus do not take full advantage of the hardware. Modern operating systems are designed to provide basic support for NUMA systems. However, default system configurations are typically sub-optimal for large data analytics applications. Additionally, rewriting the application from the ground up is not always feasible.In this work, we evaluate a variety of strategies that aim to accelerate memory-intensive data analytics workloads on NUMA systems. Our findings indicate that the operating system default configurations can be detrimental to query performance. We analyze the impact of different memory allocators, memory placement strategies, thread placement, and kernel-level load balancing and memory management mechanisms. With extensive experimental evaluation, we demonstrate that the methodical application of these techniques can be used to obtain significant speedups in four commonplace in-memory query processing tasks, on three different hardware architectures. Furthermore, we show that these strategies can improve the performance of five popular database systems running a TPC-H workload. Lastly, we summarize our findings in a decision flowchart for practitioners.

The proliferation of location-enabled sensors, smart phones, and the power of digital messaging combined with social media platforms is producing a deluge of multi-dimensional data. Novel index structures are needed to efficiently process massive amounts of geo-tagged data, and to promptly answer queries with textual, spatial, and temporal components. Existing approaches to spatio-temporal text indexing lack a unified index supporting efficient range and top-k search on any combination of location, time, or text.

Location-based services (LBS) are a widely adopted technology that produces large volumes of spatio-temporal data at high velocity. Spatial data is also being generated from many other geo-spatial applications. To address the challenge of data volume, a number of big spatial data management systems have emerged that are based on the MapReduce paradigm. Recent projects have developed spatial data systems using Spark's distributed in-memory architecture. These projects, which include GeoSpark, SpatialSpark, and LocationSpark, do not support the high update rates required by LBS applications. Alternatively, systems such as MD-HBase support data updates, but are hindered by the performance characteristics of HBase, which is a disk-oriented framework. We present DISTIL+, a distributed spatio-temporal data processing system designed for high velocity location data. Our system achieves high update throughput and low query latency by leveraging the APGAS (Asynchronous Partitioned Global Address Space) architecture to build a multi-level distributed in-memory index. We present extensive experimental evaluation of our system, comparing several indexing and data placement schemes, as well as competing systems. Our results show that DISTIL+ excels at supporting high throughput location updates, and low latency spatio-temporal range queries and kNN queries, while offering better performance than existing approaches.

The convergence of technologies like Cloud computing, mobile, and smart phone technologies has led to the rapid development of location-based services (LBS) in smart cities. For flexibility and cost savings, there is a recent trend to migrate LBS to the Cloud, however it poses a serious threat to the user privacy. In this paper, we present a new privacy preserving top-k spatio-textual keyword (TkSK) query scheme, called privacy-preserving spatio-textual index (Pystin), which is performed over outsourced Cloud and can enable secure LBS in smart cities. In Pystin, a query user's accurate location is protected by the combination of Boneh-Goh-Nissim homomorphic encryption and hash bucket techniques, and the privacy of textual information are persevered by a one-way hash function. In addition, a quad-tree-based spatio-textual indexing is integrated into Pystin to further reduce the query latency. Detailed security analyzes show that the proposed Pystin scheme is indeed a privacy-preserving TkSK query scheme. Furthermore, extensive experiments are conducted, and results confirm the scalability, efficiency properties of our proposed Pystin scheme.

Location-based services (LBS) have become an ubiquitous technology and spatio-temporal data generated by LBS is characterized by high volume and velocity. In recent times several projects, such as GeoSpark, SpatialSpark and LocationSpark, have focused on developing spatial data systems that take advantage of the distributed in-memory data processing capability of Spark. However, most of these systems assume immutable spatial data, and they do not support high throughput location data updates that are common in LBS. On the other hand, a few HBase-based systems, such as MD-HBase, have been proposed that support data updates. However, these systems do not take advantage of any distributed in-memory query processing frameworks.

Main memory hash joins are an important category of in-memory joins. However, the performance of these joins can be hindered by dataset skew, shuffling, and load balancing. We conducted a comprehensive study on the effects of dataset skew on four hash join algorithms. We show that hash joins are acutely affected by dataset skew, and the performance gets worse with shuffled data. To address these issues, we propose non-partitioning hash joins using two different hash tables. First, we use a separate chaining hash table that is based on an existing implementation that we have modified. This version outperforms the original implementation on skewed datasets by up to three orders of magnitude. Second, we propose a novel hash table for hash joins, called Maple hash table. We demonstrate that this hash table is better suited to skewed and/or shuffled datasets. Moreover, this approach further improves performance by up to 17.3×.

With the growing number of Open Data initiatives and the increased volume of related data, new forms of civic engagement are emerging. This engagement leads to novel applications and problem solving approaches. Useful insights derived from exploiting publicly available data and open source tools ultimately result in the enhancement of daily life in our communities. In this paper, we analyze publicly available road accident data for the cities of Fredericton and Laval. A traffic accident data processing and analysis pipeline is built using big data systems and big data spatial frameworks. We present a comparative analysis of traffic accidents in these two cities. Random forest classification models are trained to predict if an accident has casualties. The predictive models are used to provide insights into important factors affecting accidents with fatalities or injuries. Results of the study can be used to establish meaningful safe driving policy suggestions, aid in making emergency dispatch decisions, inform accident management procedures or even assist with urban planning.

The volume of data that is generated each day is rising rapidly. There is a need to analyze this data efficiently and produce results quickly. Data science offers a formal methodology for processing and analyzing data. It involves a work-flow with multiple stages, such as, data collection, data wrangling, statistical analysis and machine learning. In this paper, we look at data analytics systems that support the data science work-flow. The variety of current commercial and open-source data analytics systems differ significantly in terms of available features, functionality, and scalability. A benchmark can be used to evaluate the functionality and performance of a system. However, there is no standard benchmark for evaluating or comparing these data systems for doing data science. In this paper, we introduce a data science benchmark, Sanzu, to evaluate systems with data processing and analytics tasks. Our benchmark includes a micro and macro benchmark. The micro benchmark tests basic operations in isolation. It consists of task suites for reading and writing, data wrangling, statistical analysis, machine learning and time series analysis. Each macro workload evaluates an analytics application where a series of analysis or functions are based on a real world application. The macro benchmark focuses on sports and smart grid analytics. We evaluate these tasks on five different popular data science frameworks and systems: R, Anaconda Python, Dask, PostgreSQL (MADlib) and PySpark. For micro benchmark we generate synthetic datasets with 3 scale factors: 1, 10 and 100 (scale factor 1=1 million). The macro benchmark uses data generated from real-world data sources.

The pervasiveness and growing complexity of software systems are challenging software engineering to design systems that can adapt their behavior to withstand unpredictable, uncertain, and continuously changing execution environments. Control theoretical adaptation mechanisms have received growing interest from the software engineering community in the last few years for their mathematical grounding, allowing formal guarantees on the behavior of the controlled systems. However, most of these mechanisms are tailored to specific applications and can hardly be generalized into broadly applicable software design and development processes. This article discusses a reference control design process, from goal identification to the verification and validation of the controlled system. A taxonomy of the main control strategies is introduced, analyzing their applicability to software adaptation for both functional and nonfunctional goals. A brief extract on how to deal with uncertainty complements the discussion. Finally, the article highlights a set of open challenges, both for the software engineering and the control theory research communities.

Every year research institutions produce petabytes of data. Yet, only a small percent of the data is readily accessible for analysis. Terra Populus acts as the bridge between big data sources and researchers. Researchers are provided convenient web applications that allow them to access, analyze, and tabulate different datasets under a common platform. Terra Populus is developing three unique applications. The first application, Paragon, is a prototype parallel spatial database, which aims to extend the functionality of PostgreSQL and PostGIS onto multinode systems. Terra Populus' Tabulator application employs Parquet on Spark to build dynamic queries for analyzing large population survey data. The last application, Terra Explorer, is an exploratory analysis tool for visualizing the spatial datasets within the repository.

The rapid growth of spatiotemporal Big Data is fueling the emergence and growth of many applications. Many of these applications are characterized by complex spatiotemporal queries. An important category of such queries is the trajectory-based spatiotemporal topological join queries, which combine a trajectory dataset and a spatial objects dataset based on spatiotemporal predicates. Although these queries have many important use-cases, they have not received much attention from the research community. We systematically evaluate several feasible in-memory spatiotemporal topological join algorithms, using existing trajectory index (TB-tree) and spatial index (STR). We show that even the best among these algorithms is long running and not scalable. To address the performance problems of these algorithms we introduce PISTON, a parallel in-memory indexing system targeted for spatiotemporal topological join. With extensive evaluations, we demonstrate that even the single-threaded performance of PISTON is significantly better than the feasible approaches that use existing trajectory and spatial indexes. Moreover, the parallel performance of PISTON is orders of magnitude better than these approaches.

Traditional relational database engines have been losing ground to specialized data processing engines in virtually every market segment, from data warehousing, OLTP, and stream processing, to scientific applications. Although relational database engines are evolving to leverage new technologies and more efficient processing paradigms, the generality of a large monolithic engine often makes this a significant effort. Our aim is to delimit and decouple database engine components to design a more lightweight and flexible data processing engine that can support any application domain efficiently and without the effort of a complete redesign. We introduce Slingshot, a new data processing engine, where modularity and implementation flexibility are the top priority. Its core database engine is minimal and mainly handles inter-operation of the database components. Each component, abstracted by an interface, can be externally implemented and plugged into the framework as a module that handles the component's functionality. As a result, this allows designers the liberty to choose suitable features for their target applications, to drop excess functionality, and to optimize code independent of the rest of the engine. We compare Slingshot to a traditional RDBMS and to custom solutions on queries that are representative of three application types (spatial, OLAP, and OLTP). We show that Slingshot outperforms the RDBMS in most cases, while performing comparably in others. Furthermore, Slingshot performs better or comparable to custom solutions on most tests. Finally, Slingshot's flexibility allows us to efficiently leverage computer architectures such as GPUs for speeding up complex computational tasks.

The volume of spatio-temporal data is growing at a rapid pace. This is driven by several factors, including the widespread adoption of GPS-enabled mobile devices and the proliferation of RFID-tagged objects in sensor networks. Besides the volume, such spatio-temporal data is characterized by high "velocity", with its high rate of time-stamped location updates. The rise of spatio-temporal "Big data" has led to the emergence of many novel location-oriented applications. These applications often have complex use-cases and service-level requirements. Efficient management of the spatio-temporal data is critical to meet these requirements. This poses some challenges and unique research questions, for instance: i) how to support the high rate of location updates, while at the same time supporting many concurrent historical, present and predictive queries, ii) what kind of database storage organization is suitable for such workload, iii) what are the implications for the spatio-temporal index, and iv) what kind of novel spatio-temporal queries are to be supported. Technological trends involving increasingly large main memory sizes and core counts offer opportunities to address some of these issues. We have addressed a few issues pertinent to high performance commercial Location-Based Services (LBS) by exploiting in-memory database techniques. We propose an in-memory storage organization for high insert performance and introduce a novel spatio-temporal index. With extensive evaluation, we demonstrate that our system supports high insert and query throughputs and it outperforms the leading LBS system by a significant margin. As part our future research we are building a spatio-temporal data management system in the context of a cluster of machines in the Cloud. We are also investigating the possibility of supporting trajectory-based join queries.

With the proliferation of mobile devices and explosive growth of spatio-temporal data, Location-Based Services (LBS) have become an indispensable technology in our daily lives. The key characteristics of the LBS applications include a high rate of time-stamped location updates, and many concurrent historical, present and predictive queries. The commercial providers of LBS must support all three kinds of queries and address the high update rates. While they employ relational databases for this purpose, traditional databases are unable to cope with the growing demands of many LBS systems. Support for spatio-temporal indexes within these databases are limited to R-tree based approaches. Although a number of advanced spatio-temporal indexes have been proposed by the research community, only a few of them support historical queries. These indexing techniques, with support for historical queries, are unable to sustain high update and query throughput typical in LBS. Technological trends involving increasingly large main memory and core footprints offer opportunities to address some of these issues. We present several key ideas to support high performance commercial LBS by exploiting in-memory database techniques. Taking advantage of very large memory available in modern machines, our system maintains the location data and index for the past N days in memory. Older data and index are kept in disk. We propose an in-memory storage organization for high insert performance. We also introduce a novel spatio-temporal index that maintains partial temporal indexes in a versioned-grid structure. The partial temporal indexes are organized as compressed bitmaps. With extensive evaluation, we demonstrate that our system supports high insert and query throughputs and it outperforms the leading LBS system by a significant margin.

Spatial join is a crucial operation in many spatial analysis applications in scientific and geographical information systems. Due to the compute-intensive nature of spatial predicate evaluation, spatial join queries can be slow even with a moderate sized dataset. Efficient parallelization of spatial join is therefore essential to achieve acceptable performance for many spatial applications. Technological trends, including the rising core count and increasingly large main memory, hold great promise in this regard. Previous parallel spatial join approaches tried to partition the dataset so that the number of spatial objects in each partition was as equal as possible. They also focused only on the filter step. However, when the more compute-intensive refinement step is included, significant processing skew may arise due to the uneven size of the objects. This processing skew significantly limits the achievable parallel performance of the spatial join queries, as the longest-running spatial partition determines the overall query execution time.

Spatial data analysis applications are emerging from a wide range of domains such as building information management, environmental assessments and medical imaging. Time-consuming computational geometry algorithms make these applications slow, even for medium-sized datasets. At the same time, there is a rapid expansion in available processing cores, through multicore machines and Cloud computing. The confluence of these trends demands effective parallelization of spatial query processing. Unfortunately, traditional parallel spatial databases are ill-equipped to deal with the performance heterogeneity that is common in the Cloud.

Spatial databases are increasingly important for a wide variety of real-world applications, such as land surveying, urban planning, cartography and location-based services. However, spatial database workload properties are not well-understood. For example, it is unknown to what degree one spatial application resembles another in terms of resource demand, or how the demand will change as more concurrent queries (i.e., more users) are added. We show that spatial workloads have a different CPU execution profile than well-studied decision support workloads, as represented by TPC-H.

The volume of spatial data generated and consumed is rising exponentially and new applications are emerging as the costs of storage, processing power and network bandwidth continue to decline. Database support for spatial operations is fast becoming a necessity rather than a niche feature provided by a few products. However, the spatial functionality offered by current commercial and open-source relational databases differs significantly in terms of available features, true geodetic support, spatial functions and indexing. Benchmarks play a crucial role in evaluating the functionality and performance of a particular database, both for application users and developers, and for the database developers themselves. In contrast to transaction processing, however, there is no standard, widely used benchmark for spatial database operations. In this paper, we present a spatial database benchmark called Jackpine. Our benchmark is portable (it can support any database with a JDBC driver implementation) and includes both micro benchmarks and macro workload scenarios. The micro benchmark component tests basic spatial operations in isolation; it consists of queries based on the Dimensionally Extended 9-intersection model of topological relations and queries based on spatial analysis functions. Each macro workload includes a series of queries that are based on a common spatial data application. These macro scenarios include map search and browsing, geocoding, reverse geocoding, flood risk analysis, land information management and toxic spill analysis. We use Jackpine to evaluate the spatial features in 2 open source databases and 1 commercial offering.