Search

The growing number of data privacy breaches and associated financial losses have driven the demand for private database queries. Clients typically submit queries that involve both search and computation operations, such as counting students under a certain age or calculating the BMI of employees above a specific age. Existing protocols often face limitations due to reliance on specific-purpose encryption schemes or multiple communication rounds between clients and servers. In this work, we present a unified framework utilizing fully homomorphic encryption techniques to efficiently and privately process queries with search and computation operations. Our contributions include a homomorphic encryption-based private comparison algorithm, called the layered comparison algorithm, which achieves a 2.6-6.6X performance improvement compared to algorithms from prior work; a fast Fourier transform-based preprocessing method enabling accurate large integer arithmetic operations in the encrypted domain; and a scalable database encoding method. Evaluation results demonstrate the practicality of our system, as it processes an aggregated query for a 1k-row encrypted database in approximately 4.53 seconds. [ABSTRACT FROM AUTHOR]

The ranking pipelines of modern search platforms commonly exploit complex machine-learned models and have a significant impact on the query response time. In this paper, we discuss several techniques to speed up the document scoring process based on large ensembles of decision trees without hindering ranking quality. Specifically, we study the problem of document early exit within the framework of a cascading ranker made of three components: 1) an efficient but sub-optimal ranking stage; 2) a pruner that exploits signals from the previous component to force the early exit of documents classified as not relevant; and 3) a final high-quality component aimed at finely ranking the documents that survived the previous phase. To maximize speedup and preserve effectiveness, we aim to increase the accuracy of the pruner in identifying non-relevant documents without early exiting documents that are likely to be ranked among the final top- $k$ results. We propose an in-depth study of heuristic and machine-learning techniques for designing the pruner. While the heuristic technique only exploits the score/ranking information supplied by the first sub-optimal ranker, the machine-learned solution named LEAR uses these signals as additional features along with those representing query-document pairs. Moreover, we study alternative solutions to implement the first ranker, either a small prefix of the original forest or an auxiliary machine-learned ranker explicitly trained for this purpose. We evaluated our techniques through reproducible experiments using publicly available datasets and state-of-the-art competitors. The experiments confirm that our early-exit strategies achieve speedups ranging from $3\times $ to $10\times $ without statistically significant differences in effectiveness.

Increasingly, individuals and companies adopt a cloud service provider as a primary data and IT infrastructure platform. The remote access of the data inevitably brings the issue of trust. Data encryption is necessary to keep sensitive information secure and private on the cloud. Yet adversaries can still learn valuable information regarding encrypted data by observing data access patterns. To solve such problem, Oblivious RAMs (ORAMs) are proposed to completely hide access patterns. However, most ORAM constructions are expensive and not suitable to deploy in a database for supporting query processing over large data. Furthermore, an ORAM processes queries synchronously, hence, does not provide high throughput for concurrent query processing. In this article, we design a practical oblivious query processing framework to enable efficient query processing over a cloud database. In particular, we focus on processing multiple range and $k$ k NN queries asynchronously and concurrently with high throughput. The key idea is to integrate indices into ORAM which leverages a suite of optimization techniques (e.g., oblivious batch processing and caching). The effectiveness and efficiency of our oblivious query processing framework is demonstrated through extensive evaluations over large datasets. Our construction shows an order of magnitude speedup in comparison with other baselines. [ABSTRACT FROM AUTHOR]

From a set of existing tuples, a skyline operator retrieves only a subset, superior tuples that are of a person’s interest and are non-dominant. Processing of queries using the skyline operator is an expensive and exhaustive task. It gets more complicated when skyline queries are applied on partially complete data and databases are distributed over different data centers. Incompleteness in data raises many issues such as compromise on transitivity property and the threat of cyclic dominance to occur within database. To overcome such issues this paper proposes an efficient algorithm called Cloud-based Incomplete Data Skyline algorithm (CIDS) for processing skyline queries over partially complete databases in cloud environment. The algorithm retrieves superior tuples with the aim of reducing domination tests between the tuples, decreasing processing time and reducing the huge amount of data flow from one data center to another. Several experiments have been conducted over different types of datasets, and results have proven that the proposed algorithm outplays the existing algorithms in terms of processing time, domination tests as well as the amount of data flow.

The purpose of this paper is to show concisely how we can promote chatbots in the medical sector and cure infectious diseases. We can create awareness through the users and the users can get proper medical solutions to prevent disease. We created a preliminary training model and a study report to improve human interaction in databases in 2021. Through natural language processing, we describe the human behaviors and characteristics of the chatbot. In this paper, we propose an AI Chatbot interaction and prediction model using a deep feedforward multilayer perceptron. Our analysis discovered a gap in knowledge about theoretical guidelines and practical recommendations for creating AI chatbots for lifestyle improvement programs. A brief comparison of our proposed model concerning the time complexity and accuracy of testing is also discussed in this paper. In our work, the loss is a minimum of 0.1232 and the highest accuracy is 94.32%. This study describes the functionalities and possible applications of medical chatbots and explores the accompanying challenges posed by the use of these emerging technologies during such health crises mainly posed by pandemics. We believe that our findings will help researchers get a better understanding of the layout and applications of these revolutionary technologies, which will be required for continuous improvement in medical chatbot functionality and will be useful in avoiding COVID-19.

So-called spatial web queries retrieve web content representing points of interest, such that the points of interest have descriptions that are relevant to query keywords and are located close to a query location. Two broad categories of such queries exist. The first encompasses queries that retrieve single spatial web objects that each satisfy the query arguments. Most proposals belong to this category. The second category, to which this paper's proposal belongs, encompasses queries that support exploratory user behavior and retrieve sets of objects that represent regions of space that may be of interest to the user. Specifically, the paper proposes a new type of query, the top- $k$ k spatial textual cluster retrieval ($k$ k -STC) query that returns the top- $k$ k clusters that (i) are located close to a query location, (ii) contain objects that are relevant with regard to given query keywords, and (iii) have an object density that exceeds a given threshold. To compute this query, we propose a DBSCAN-based approach and an OPTICS-based approach that rely on on-line density-based clustering and that exploit early stop conditions. Empirical studies on real data sets offer evidence that the paper's proposals can find good quality clusters and are capable of excellent performance. [ABSTRACT FROM AUTHOR]

The reachability problem on directed graphs, asking whether two vertices are connected via a directed path, is an elementary problem that has been well-studied. In this paper, we study a variation of the elementary reachability problem, called the sink-reachability problem, which can be found in many applications such as static program analysis, social network analysis, large scale web graph analysis, XML document link path analysis, and the study of gene regulation relationships. To scale sink-reachablity analysis to large graphs, we develop a highly scalable sink-reachability preserving graph reduction strategy for input sink graphs, by using a composition framework. That is, individual sink-reachability preserving condensation operators, each running in linear time, are pipelined together to produce graph reduction algorithms that result in close to maximum reduction, while keeping the computation efficient. Experiments on large real-world sink graphs demonstrate the efficiency and effectiveness of our compositional approach to sink-reachability preserving graph reduction with a reduction rate of up to 99.74 percent for vertices and a rate of up to 99.46 percent for edges. [ABSTRACT FROM AUTHOR]

Subgraph queries are routinely used to search for entities in richly attributed graphs e.g., social networks and knowledge graphs. With little knowledge of underlying data, users often need to rewrite queries multiple times to reach desirable answers. Why-questions are studied to clarify missing or unexpected query results. This paper makes a first step to answer Why-questions for entity search in attributed graphs. We consider three common types of Why-questions: Why-not, Why, and Why-rank, which suggest query manipulations that are responsible for user-specified missing, unexpected, and undesirably ranked entities, respectively. (1) We approach a general query rewriting paradigm that suggests to identify desired entities that are specified by Why-questions. We introduce measures that characterize good query rewrites by incorporating both query editing cost and answer closeness. (2) While computing optimal query rewrites is intractable, we develop feasible algorithms, from approximation to fast heuristics, and provide query rewrites with (near) optimality guarantees whenever possible, for Why, Why-not and Why-rank questions. We further show that our results remain intact for Why questions that (1) request a single query rewrite to clarify multiple types of entities, and (2) variants such as Why-empty and Why-so-many, by providing the matching algorithms. Using real-world graphs, we experimentally verify that our algorithms are effective and feasible for large graphs. Our case study also verifies their application in e.g., knowledge exploration. [ABSTRACT FROM AUTHOR]

Given a dataset $\mathcal S$ S composed of $g$ g subsets with each data item belonging to one of them, multiset membership lookup takes an item $e$ e as input and outputs a binary answer whether $e\in {\mathcal S}$ e ∈ S and, in case of yes, the ID of the subset to which $e$ e belongs. Overlaid upon while more sophisticated than the canonical membership lookup, multiset membership lookup emerges as a pivotal functionality in many computing and networking paradigms. The quest to achieve high-speed, high-accuracy lookup with limited memory cost makes lookup algorithm design a challenging task, particularly when the data items arrive as a stream. In this paper, we devise compact data structures and lookup algorithms that are amendable for hardware implementation, while guaranteeing high lookup accuracy and supporting interactive query processing. We first propose multi-hash color table, a variant of Bloom filter, to encode subset IDs compactly and map the ID of an item to its subset ID. We further construct a more balanced data structure called balanced multi-hash color table to improve the compactness by integrating the state-of-the-art load balancing technique. We complete our work by addressing the case of batch arrivals and design a batched recording algorithm optimizing the memory efficiency. We give both theoretical and empirical analysis to characterize and evaluate the performance of the proposed algorithms in terms of lookup accuracy, memory and access efficiency. [ABSTRACT FROM AUTHOR]

Recent advances in video processing utilizing deep learning primitives achieved breakthroughs in fundamental problems in video analysis such as frame classification and object detection enabling an array of new applications. In this paper we study the problem of interactive declarative query processing on video streams. In particular we introduce a set of approximate filters to speed up queries that involve objects of specific type (e.g., cars, trucks, etc.) on video frames with associated spatial relationships among them (e.g., car left of truck). The resulting filters are able to assess quickly if the query predicates are true to proceed with further analysis of the frame or otherwise not consider the frame further avoiding costly object detection operations. We propose two classes of filters $IC$ I C and $OD$ O D , that adapt principles from deep image classification and object detection. The filters utilize extensible deep neural architectures and are easy to deploy and utilize. In addition, we propose statistical query processing techniques to process aggregate queries involving objects with spatial constraints on video streams and demonstrate experimentally the resulting increased accuracy on the resulting aggregate estimation. Finally, we introduce a framework based on extreme value theory to detect unexpected objects on video streams and experimentally demonstrate its utility. Combined these techniques constitute a robust set of video monitoring query processing techniques. We demonstrate that the application of the techniques proposed in conjunction with declarative queries on video streams can dramatically increase the frame processing rate and speed up query processing by at least two orders of magnitude. We present the results of a thorough experimental study utilizing benchmark video data sets at scale demonstrating the performance benefits and the practical relevance of our proposals. [ABSTRACT FROM AUTHOR]

In this paper, we study a new variant of trajectory similarity search from the context of continuous query processing. Given a moving object from $s$ s to $d$ d , following a reference route $T_r$ T r , we monitor the trajectory similarity between the reference route and the current partial route at each timestamp for online detour detection. Since existing trajectory distance measures fail to adequately capture the deviation between a partial route and a complete route, we propose a partial trajectory similarity measure to bridge the gap. In particular, we enumerate all the possible routes extended from the partial route to reach the destination $d$ d and calculate their minimum distance to $T_r$ T r . We consider deviation calculation in both euclidean space and road networks. In euclidean space, we can directly infer the optimal future path with the minimum trajectory distance. In road networks, we propose an efficient expansion algorithm with a suite of pruning rules. Furthermore, we propose efficient incremental processing strategies to facilitate continuous query processing for moving objects. Our experiments are conducted on multiple real datasets and the experimental results verify the efficiency of our query processing algorithms. [ABSTRACT FROM AUTHOR]

Current spatial-keyword publish/subscribe systems need to handle spatial-keyword skyline queries over geo-textual streams to continuously obtain good results. The skyline queries in such systems face two main problems: (1) query problems, because the powerful query capability is required for the strict limit of the response time and the large number of items concerned by the users, and (2) scalability issue, because millions of active users are maintained simultaneously with many network-connected machines. Unfortunately, the current approach is towards static data. Thus, this paper first proposes a distributed skyline query processing framework. Then, we optimize the skyline computing by introducing MF-R $^t$ t -tree, which is an update-efficient and space-saving indexing structure and a fast approach for processing a continuous spatial-keyword skyline query called $eager^*$ e a g e r * . Finally, a spatial and textual signature-based communication optimization method is proposed to support scalability. The experimental results indicate that (1) MF-R $^t$ t -tree can significantly reduce update costs, while maintaining a low storage cost, and a query performance comparable to IL-Quadtree, (2) $eager^*$ e a g e r * can averagely accelerate 79.72 × faster than the method based on BNL, (3) the communication optimization method significantly reduces the communication cost, and (4) the distributed framework can efficiently support large-scale skyline queries. [ABSTRACT FROM AUTHOR]

Finding top- $k$ k frequent items has been a hot issue in databases. Finding top- $k$ k persistent items is a new issue, and has attracted increasing attention in recent years. In practice, users often want to know which items are significant, i.e., not only frequent but also persistent. No prior art can address both of the above two issues at the same time. Also, for high-speed data streams, prior art cannot achieve high accuracy when the memory is tight. In this paper, we define a new issue, named finding significant items, and propose a novel algorithm namely LTC to address this issue. It includes two key techniques, Long-tail Restoring and CLOCK, as well as three optimizations. In addition, LTC is extended to support finding significant items with thresholds. We theoretically derive the correct rate and error bound, and conduct extensive experiments on three real datasets to test the performance of LTC. Our experimental results show that LTC can achieve $10^5$ 10 5 times higher accuracy in terms of average relative error than other related algorithms. Lastly, LTC is applied to a DDoS detection task and it shows that finding significant items is more powerful than finding frequent items. [ABSTRACT FROM AUTHOR]

Progressive visualization is fast becoming a technique in the visualization community to help users interact with large amounts of data. With progressive visualization, users can examine intermediate results of complex or long running computations, without waiting for the computation to complete. While this has shown to be beneficial to users, recent research has identified potential risks. For example, users may misjudge the uncertainty in the intermediate results and draw incorrect conclusions or see patterns that are not present in the final results. In this article, we conduct a comprehensive set of studies to quantify the advantages and limitations of progressive visualization. Based on a recent report by Micallef et al., we examine four types of cognitive biases that can occur with progressive visualization: uncertainty bias, illusion bias, control bias, and anchoring bias. The results of the studies suggest a cautious but promising use of progressive visualization – while there can be significant savings in task completion time, accuracy can be negatively affected in certain conditions. These findings confirm earlier reports of the benefits and drawbacks of progressive visualization and that continued research into mitigating the effects of cognitive biases is necessary. [ABSTRACT FROM AUTHOR]

Numerous research efforts have been proposed for efficient processing of range queries in high-dimensional space by either redesigning R-tree access structure for exploring massive parallelism on single GPU or exploring distributed framework of R-tree. However, none of the existing efforts explores the integration of the parallelization of the R-tree on a single GPU with a distributed framework for the R-tree. The problem of designing an efficient multi-GPU indexing method, which can effectively combine the parallelism maximization with distributed processing of the R-tree, remains an open challenge. In this article, we present a novel multi-GPU efficient parallel and distributed indexing method, called LBPG-tree. The rationale of the LBPG-tree is to combine the advantages of an instruction pipeline in CPU with the massive parallel processing potential of multiple GPUs by introducing two new optimization strategies: First, we exploit the GPU L2 cache for accelerating both index search and index node access on GPUs. Second, we further improve utilization of L2 cache on GPUs by compacting and sorting candidate nodes called Compact-and-Sort. Our experimental results show that the LBPG-tree outperforms G-tree, the previous representative GPU index method and effectively support multiple GPUs for providing efficient high dimensional range query service. [ABSTRACT FROM AUTHOR]

With the enormous growth of wireless technology, and location acquisition techniques, a huge amount of spatio-temporal traces are being accumulated. This dataset facilitates varied location-aware services and helps to take real-life decisions. Efficiently handling and processing spatio-temporal queries are necessary to respond in real-time. Processing the vast spatio-temporal data requires scalable computing infrastructure. In this regard, an efficient query resolution system can be deployed if we predict the infrastructure requirement of the user query apriori along with the identification of the geospatial service chain. In this work, we propose a framework, namely LYRIC (deadLine and budget aware spatio-temporal querY pRocessing In Cloud), where the spatio-temporal queries are resolved efficiently considering user-defined deadline and budget constraint. Our framework shows high deadline completion accuracy in the range of 1.0 - 0.937, which is more accurate than SparkGIS, GeoSpark, GeoMesa and JUST. This also reduces the resource prediction error by 11 percent, considering the geospatial service chain than without it. The cost of the spatio-temporal query is reduced by $\approx$ ≈ 23% in LYRIC, further, the simulation study (using CloudSim) illustrates the efficacy and scalability of LYRIC in terms of optimal budget usage and execution time compared to four baseline approaches. [ABSTRACT FROM AUTHOR]

Uncertain graph management and analysis have attracted many research attentions. Among them, computing $k$ k -cores in uncertain graphs (aka, $(k,\eta)$ (k , η) -cores) is an important problem and has emerged in many applications such as community detection, protein-protein interaction network analysis and influence maximization. Given an uncertain graph, the $(k,\eta)$ (k , η) -cores can be derived by iteratively removing the vertex with an $\eta$ η -degree of less than $k$ k . However, the results heavily depend on the two input parameters $k$ k and $\eta$ η . The settings for these parameters are unique to the specific graph structure and the user's subjective requirements. In addition, computing and updating the $\eta$ η -degree for each vertex is the most costly component in the algorithm, and the cost is high. To overcome these drawbacks, we propose an index-based solution for computing $(k,\eta)$ (k , η) -cores. The size of the index is well bounded by $O(m)$ O (m) , where $m$ m is the number of edges in the graph. Based on the index, queries for any $k$ k and $\eta$ η can be answered in optimal time. We propose an algorithm for index construction with several different optimizations. We also propose a new algorithm for index construction in external memory. We conduct extensive experiments on eight real-world datasets to practically evaluate the performance of all proposed algorithms. [ABSTRACT FROM AUTHOR]

A skyline query searches the data points that are not dominated by others in the dataset. It is widely adopted for many applications which require multi-criteria decision making. However, skyline query processing is considerably time-consuming for a high-dimensional large scale dataset. Parallel computing techniques are therefore needed to address this challenge, among which $MapReduce$ M a p R e d u c e is one of the most popular frameworks to process big data. A great number of efficient $MapReduce$ M a p R e d u c e skyline algorithms have been proposed in the literature and most of their designs focus on partitioning and pruning the given dataset. However, there are still opportunities for further parallelism. In this study, we propose two parallel skyline processing algorithms using a novel $LShape$ L S h a p e partitioning strategy and an effective $Propagation$ P r o p a g a t i o n $Filtering$ F i l t e r i n g method. These two algorithms are $2Phase$ 2 P h a s e $LShape$ L S h a p e and $1Phase$ 1 P h a s e $LShape$ L S h a p e , used for multiple reducers and single reducer, respectively. By extensive experiments, we verify that our algorithms outperformed the state-of-the-art approaches, especially for high-dimensional large scale datasets. [ABSTRACT FROM AUTHOR]

RDF graph has been increasingly used to store and represent information shared over the Web, including social graphs and knowledge bases. With the increasing scale of RDF graphs and the concurrency level of SPARQL queries, current RDF systems are confronted with inefficient concurrent query processing on massive data parallelism. The situation becomes more severe in the face of data-intensive queries (aka heavy query), which usually lead to suboptimal response time (latency) as well as throughput collapse. In this article, we present Wukong+G, the first graph-based distributed RDF query processing system that efficiently exploits the hybrid parallelism of CPU and GPU. Wukong+G is made fast and concurrent with four key designs. First, Wukong+G tames massive random memory accesses in graph exploration by efficiently mapping data between CPU and GPU for latency hiding, including a set of techniques like query-aware prefetching, pattern-aware pipelining and fine-grained swapping. Second, Wukong+G scales up by introducing a GPU-friendly RDF store to support RDF graphs exceeding GPU memory size, by using techniques like predicate-based grouping, pairwise caching and look-ahead replacing to narrow the gap between host and device memory scale. Third, Wukong+G scales out through a communication layer that decouples the transferring process for query metadata and intermediate results, and further leverages both native and GPUDirect RDMA to enable efficient communication on a CPU/GPU cluster. Finally, Wukong+G simultaneously runs multiple queries on a single GPU to improve overall throughput and fully exploits hardware heterogeneity (CPU/GPU) by scheduling a single query on CPU and GPU adaptively. We have implemented Wukong+G by extending a state-of-the-art distributed RDF store (i.e., Wukong) with distributed GPU support. Evaluation on a heterogeneous CPU/GPU cluster with RDMA-capable network shows that Wukong+G outperforms Wukong by up to 9.0× (from 2.3×) and scales well on 10 GPU cards for heavy queries. Wukong+G can also improve both latency and throughput by more than one order of magnitude when facing hybrid workloads. [ABSTRACT FROM AUTHOR]

As Vehicular Networks rely increasingly on sensed data to enhance functionality and safety, efficient and distributed data analysis is needed to effectively leverage new technologies in real-world applications. Considering the tens of GBs per hour sensed by modern connected vehicles, traditional analysis, based on global data accumulation, can rapidly exhaust the capacity of the underlying network, becoming increasingly costly, slow, or even infeasible. Employing the edge processing paradigm, which aims at alleviating this drawback by leveraging vehicles’ computational power, we are the first to study how to localize, efficiently and distributively, relevant data in a vehicular fleet for analysis applications. This is achieved by appropriate methods to spread requests across the fleet, while efficiently balancing the time needed to identify relevant vehicles, and the computational overhead induced on the Vehicular Network. We evaluate our techniques using two large sets of real-world data in a realistic environment where vehicles join or leave the fleet during the distributed data localization process. As we show, our algorithms are both efficient and configurable, outperforming the baseline algorithms by up to a $40\times $ speedup while reducing computational overhead by up to $3\times $ , while providing good estimates for the fraction of vehicles with relevant data and fairly spreading the workload over the fleet. All code as well as detailed instructions are available at https://github.com/dcs-chalmers/dataloc_vn.

Recently there has been a new emerging trend in using the technology of Named Data Networking (NDN) on wireless sensor networks (WSNs) to improve data-centric communications over WSNs. The usage of the NDN notion in WSN for such communications can be advantageous in many respects ranging from ensuring secure data collection without using the nodes’ location and several nodes to possible delivery of sensory data by utilizing the cached data in intermediate components of the network. On the other hand, WSN being a resource-constrained, energy-starved network, the data communication mechanism must be low-overhead in terms of computation and communication overheads. Thus, we propose integrity preserving low overhead query handling over NDN-based WSN. We make the scheme low overhead by judicious use of the NDN data structure Content Store (CS), Pending Interest Table (PIT), Forwarding Information Base (FIB) in a few strategically placed nodes. We also make the data collection secure by applying an existing Light-weight One-way Cryptographic Hash Algorithm (LOCHA) on the collected data. The performance of the scheme is analyzed theoretically in terms of communication, computation, storage overheads. We also simulate the entire query processing scheme including request and response forwarding in Cooja, the Contiki network simulator. Simulation results show that our scheme does not compromise with network performance such as packet loss rate, network lifetime, end-to-end delay, etc. while achieving the design goal of making the scheme energy saving which establishes that the scheme is readily implementable in real life mote e.g., Tmote Sky. Finally, all the results are compared with three competing schemes and the results confirm our scheme’s supremacy in terms of both design performance as well as network performance.

Skyline queries identify skyline points, the minimal set of data points that dominate all other data points in a large dataset. The main challenge with skyline queries is executing the skyline query in the shortest possible time. To address and solve skyline query performance issues, we propose a decision tree-based method known as the decision tree-based comparator (DC). This method minimizes unnecessary dominance tests (i.e., pairwise comparisons) by constructing a decision tree based on the dominance testing. DC uses dominance relations that can be obtained from the decision rules of the decision tree to determine incomparability between data points. DC can also be easily applied to improve the performance of various existing skyline query methods. After describing the theoretical background of DC and applying it to existing skyline queries, we present the results of various experiments showing that DC can improve skyline query performance by up to 23.15 times.

Analytic queries enable sophisticated large-scale data analysis within many commercial, scientific and medical domains today. Data skew is a ubiquitous feature of these real-world domains. In a retail database, some products are typically much more popular than others. In a text database, word frequencies follow a Zipf distribution with a small number of very common words, and a long tail of infrequent words. In a geographic database, some regions have much higher populations (and therefore data measurements) than others. Current systems do not make the most of caches for exploiting skew. In particular, a whole cache line may remain cache resident even though only a small part of the cache line corresponds to a popular data item. In this article, we propose a novel index structure for repositioning data items to concentrate popular items into the same cache lines. The net result is better spatial locality, and better utilization of limited cache resources. We develop a theoretical model for analyzing the cache utilization, and implement database operators that are efficient in the presence of skew. Our experimental evaluation on real and synthetic data shows that exploiting skew can significantly improve in-memory query performance. In some cases, our techniques can speed up queries by over an order of magnitude. [ABSTRACT FROM AUTHOR]

Recently, location-based social networks, that involve both social and spatial information, have received much attention in many real-world applications such as location-based services (LBS), map utilities, business planning, and so on. In this paper, we seamlessly integrate both social networks and spatial road networks, resulting in a so-called spatial-social network, and study an important and novel query type, named group planning query over spatial-social networks (GP-SSN), which is very useful for applications such as trip recommendations. In particular, a GP-SSN query retrieves a group of friends with common interests on social networks and a number of spatially close points of interest (POIs) on spatial road networks that best match group’s preferences and have the smallest traveling distances to the group. In order to tackle the GP-SSN problem, we design effective pruning methods, matching score pruning, user pruning, and distance pruning, to rule out false alarms of GP-SSN query answers and reduce the problem search space. We also propose effective indexing mechanisms to facilitate the GP-SSN query processing, and develop efficient GP-SSN query answering algorithms via index traversals. Extensive experiments have been conducted to evaluate the efficiency and effectiveness of our proposed GP-SSN query processing approaches. [ABSTRACT FROM AUTHOR]

Range query processing is a common edge computing and service in the Internet of things, which can extract user-interest information from distributed edge devices. How to design lightweight privacy-preserving range query processing methods remains a challenging task. Existing secure range query approaches suffer from both high communication cost and long response time, which makes them unsuitable for edge computing over resource-constrained edge devices. In this article, we propose two privacy-aware fuzzy query processing schemes based on fuzzy theory. Linguistic range variables, fuzzy overlap information, and its recovery mechanism are introduced. In addition, two distributed privacy-aware fuzzy range query processing algorithms are devised. Our approaches not only serve for privacy protection, but also aim to provide other optimal performances in terms of reliability, energy efficiency, and real-time response. Theoretical analysis and experimental evaluations based on real-world datasets validated our motivation. [ABSTRACT FROM AUTHOR]

This paper concerns the fundamental problem of processing conjunctive queries that contain both keyword and range conditions on public clouds in a privacy preserving manner. No prior Searchable Symmetric Encryption (SSE) based privacy preserving conjunctive query processing scheme satisfies the three requirements of adaptive security, efficient query processing, and scalable index size. In this paper, we propose the first privacy preserving conjunctive query processing scheme that satisfies all the above three requirements. To achieve adaptive security, we propose an Indistinguishable Bloom Filter (IBF) data structure for indexing. To achieve efficient query processing and structural indistinguishability, we propose a highly balanced binary tree data structure called Indistinguishable Binary Tree (IBtree). To achieve scalable and compact index size, we propose an IBtree space compression algorithm to remove redundant information in IBFs. To optimize search efficiency, we propose a traversal minimization algorithm. To make our scheme dynamic, we propose update algorithms. We prove that our scheme is adaptive secure under the IND-CKA secure model. The key contribution of this paper is on achieving conjunctive query processing with both strong privacy guarantee and practical efficiency in terms of both speed and space. We implemented our scheme in C++, evaluated and compared its performance with the prior KRB scheme for keyword queries and the prior PBtree scheme for range queries on two real-world data sets. Experimental results show that our scheme is both fast and scalable. For example, processing a query only takes a few milliseconds for millions of records. [ABSTRACT FROM AUTHOR]

Support for efficient spatial data storage and retrieval has become a vital component in almost all spatial database systems. While GPUs have become a mainstream platform for high-throughput data processing in recent years, exploiting the massively parallel processing power of GPUs is non-trivial. Current approaches that parallelize one query at a time have low work efficiency and cannot make good use of GPU resources. On the other hand, many spatial database systems could receive a large number of queries simultaneously. In this paper, we present a comprehensive framework named G-PICS for parallel processing of concurrent spatial queries on GPUs. G-PICS encapsulates efficient parallel algorithms for constructing a variety of spatial trees with different space partitioning methods. G-PICS also provides highly optimized programs for processing major spatial query types, and such programs can be accessed via an API that could be further extended to implement user-defined algorithms. While support for dynamic data inputs is missing in existing work, G-PICS implements efficient parallel algorithms for bulk updates of data. Furthermore, G-PICS is designed to work in a Multi-GPU environment to support datasets beyond the size of a single GPU’s global memory. Empirical evaluation of G-PICS shows significant performance improvement over the state-of-the-art GPU and parallel CPU-based spatial query processing systems. In particular, G-PICS achieves double-digit speedup over such systems in tree construction (up to 53X) and query processing (up to 80X). [ABSTRACT FROM AUTHOR]

Many real world data can be modeled by a graph with a set of nodes interconnected to each other by multiple relationships. Such a rich graph is called multilayer graph or network. Providing useful visualization tools to support the query process for such graphs is challenging. Although many approaches have addressed the visual query construction, few efforts have been done to provide a contextualized exploration of query results and suggestion strategies to refine the original query. This is due to several issues such as i) the size of the graphs ii) the large number of retrieved results and iii) the way they can be organized to facilitate their exploration. In this article, we present VERTIGo, a novel visual platform to query, explore and support the analysis of large multilayer graphs. VERTIGo provides coordinated views to navigate and explore the large set of retrieved results at different granularity levels. In addition, the proposed system supports the refinement of the query by visual suggestions to guide the user through the exploration process. Two examples and a user study demonstrate how VERTIGo can be used to perform visual analysis (query, exploration, and suggestion) on real world multilayer networks. [ABSTRACT FROM AUTHOR]

Finding the fastest path in the time-dependent road network is time consuming because its problem complexity is $\Omega (T(|V|\log |V|+|E|))$ Ω (T (| V | log | V | + | E |)) , where $T$ T is the size of the result's time-dependent function, $|V|$ | V | and $|E|$ | E | are the number of vertices and edges. There are three kinds of fastest path problems: SSFP (Single-Staring Time Fastest Path) that has a fixed departure time, ISFP (Interval-Staring Time Fastest Path) that selects the best departure time from an interval, and FPP (Fastest Path Profile) that returns the travel time of the entire time domain. In this paper, we aim to answer these three queries in time-dependent road network faster by extending the 2-hop labeling approach, which is fast in answering shortest distance query in the static graph. However, it is hard to construct index for SSFP and ISFP because there are $|\mathcal {T}|$ | T | and $|\mathcal {T}|^2$ | T | 2 possible time points and intervals, where $\mathcal {T}$ T is the time domain. Therefore, we first propose the time-dependent hop-labeling for FPP, then provide the specific optimizations for SSFP and ISFP query answering. Moreover, it is both time and space consuming to build an index in a large time-dependent graph, so we partition road network into smaller sub-graphs and build indexes within and between the partitions. Furthermore, we propose an online approximation technique AT-Dijkstra and a bottom-up compression method to further reduce the label size, save construction time and speedup query answering. Experiments on real world road network show that our approach outperforms the state-of-art fastest path index approaches and can speed up the query answering by hundreds of times. [ABSTRACT FROM AUTHOR]

With the popularization of the geo-positioning technologies and Location Based Service (LBS), the spatial range query has gained increasing attention in VANET. To eliminate local data storage and computation burden, the data owner outsources his/her spatial data and the processing of range query tasks to location based service providers. However, outsourcing tasks may bring the risk of privacy leakage as location based service providers and clients, including data owner and data users are not in the same trusted domain. Besides, malicious service providers may forge or tamper retrieval results due to interest incentives such as saving storage or computational capacity. Therefore, we first propose and construct the Verifiable Spatial Range Query (VSRQ) scheme in VANET by using the hierarchical cell based encoding method, G-tree and the accumulator. To guarantee the correctness and completeness of search results, we leverage an accumulator-based technology. Then, we develop an improved G-tree to accelerate query processing and extend it to support multi-dimensional range queries. Security analysis shows that basic VSRQ and extension of VSRQ schemes are secure in terms of the privacy of index and confidentiality of spatial data. Extensive experiments further show that, basic (or extension of) VSRQ scheme can achieve result integrity while supporting spatial range query and lower computational and storage burden compared with existing schemes. [ABSTRACT FROM AUTHOR]

In the era of big data, parallel $Top_{k}$ query processing under information retrieval has received increasing attention from both the industry and academia. This query handling allows users to retrieve the most useful data objects in a set of choices. This problem is compounded by the use of $Top_{k}$ in cases of multiple dimensions and extensive data analytics. In this article, we provide a novel parallel algorithm in a distributed recommender system based on the Apache Spark platform. The purpose of this approach was to implement the multicriteria decision aiding support and dominating query approach run by using matrix factorization and singular value decomposition (SVD)-based model as a sophisticated machine learning technique. Simultaneously, applying the resilient distributed datasets paradigm in cloud computing, which presents a favorable environment for big data management. Extensive experimental results in terms of accuracy, and scalability indicated the new algorithm’s advantage compared to other $Top_{k}$ algorithms. Accordingly, our recommender system based on the conceived algorithm achieved high precision (62%–82%, depending on the data) to verify the profoundly positive effect of the use of the Spark framework and the SVD-based model while applying the commonly used evaluation metrics in the recommendation systems. [ABSTRACT FROM AUTHOR]

The group nearest neighbor (GNN) search on a road network $G_r$ G r , i.e., finding the spatial objects as activity assembly points with the smallest sum of distances to query users on $G_r$ G r , has been extensively studied; however, previous works neglected the fact that social relationships among query users, which ensure the maximally favorable atmosphere in the activity, can play an important role in GNN queries. Meanwhile, the ratings of spatial objects can also be used as recommended guidelines. Many real-world applications, such as location-based social networking services, require such queries. In this paper, we study two new problems: (1) a GNN search on a road network that incorporates cohesive social relationships (CGNN) and (2) a CGNN query under multi-criteria (MCGNN). Specifically, both the query users of highest closeness and the corresponding top- $j$ j objects are retrieved. To address critical challenges on the effectiveness of results and the efficiency of computation over large road-social networks: (1) for CGNN, we propose a filtering-and-verification framework. During filtering, we prune substantial unpromising users and objects using social and geospatial constraints. During verification, we obtain the object candidates, among which the top $j$ j are selected, with respect to the qualified users; (2) for MCGNN, we propose threshold-based selection and expansion strategies, where different strict boundaries are proposed to ensure that correct top- $j$ j objects are found early. Moreover, we further optimize search strategies to improve query performance. Finally, experimental results on real social and road networks significantly demonstrate the efficiency and efficacy of our solutions. [ABSTRACT FROM AUTHOR]

The log structured merge (LSM) tree has been widely adopted by database systems owing to its superior write performance. However, LSM-tree based databases face vulnerabilities when processing analytical queries due to the read amplification caused by its architecture and the limited use of storage devices with high bandwidth. To flexibly handle transactional and analytical workloads, we proposed and implemented OurRocks taking full advantage of NVMe SSD and GPU devices, which improves scan performance. Although the NVMe SSD serves multi GB/s I/O rates, it is necessary to solve the data transfer overhead which limits the benefits of the GPU processing. The primary idea is to offload the scan operation to the GPU with filtering predicate pushdown and resolve the bottleneck from the data transfer between devices with direct memory access (DMA). OurRocks benefits from all the features of write-optimized database systems, in addition to accelerating the analytic queries using the aforementioned idea. Experimental results indicate that OurRocks effectively leverages resources of the NVMe SSD and GPU and significantly improves the execution of queries in the YCSB and TPC-H benchmarks, compared to the conventional write-optimized database. Our research demonstrates that the proposed approach can speed up the handling of the data-intensive workloads. [ABSTRACT FROM AUTHOR]

Given a geo-textual dataset $\mathbb {O}$ O , a set $\varphi$ φ of keywords, a query object $q \in \mathbb {O}$ q ∈ O , and an integer $k$ k , a reverse top- $k$ k keyword-based location query returns the influence zone $\mathcal {R}$ R of $q$ q such that $q$ q belongs to the result of a top- $k$ k spatial keyword query with query keywords $\varphi$ φ and any location in $\mathcal {R}$ R as arguments. For a query object $q$ q , the influence zone of $q$ q varies for different keywords $\varphi$ φ . Users may be interested in identifying the maximum influence zone of the query object. To this end, in this paper, we study the problem called MaxiZone that finds the keyword set maximizing the influence zone of a specified query object. The MaxiZone problem has many real-life applications, e.g., a business owner would like to identify the maximum influence zone so as to attract as many customers as possible. A straightforward way to tackle the MaxiZone problem is to compute the influence zone for every candidate keyword set. Obviously, this is infeasible if there are a large number of candidate keyword sets. We propose a more efficient index-centric algorithm together with a series of optimizations as well as a sampling-based algorithm, to facilitate the query processing. Moreover, we extend the proposed algorithms to address a variant of MaxiZone problem called $\tau$ τ -MaxiZone problem, which finds top- $\tau$ τ keyword sets having the maximum influence zones. Extensive empirical study using real-world datasets demonstrates the effectiveness and efficiency of our proposed algorithms. [ABSTRACT FROM AUTHOR]

Social data outsourcing is an emerging paradigm for effective and efficient access to the social data. In such a system, a third-party Social Data Provider (SDP) purchases social network datasets from Online Social Network (OSN) operators and then resells them to data consumers who can be any individuals or entities desiring social data through query interfaces. The SDP cannot be fully trusted and may return forged or incomplete query results to data consumers for various reasons, e.g., in favor of the businesses willing to pay. In this paper, we initiate the study on verifiable query processing over outsourced social graph whereby a data consumer can verify both the integrity and completeness of any query result returned by an untrusted SDP. We propose three schemes for single-attribute queries and another scheme for multi-attribute queries over outsourced social data. The four schemes all require the OSN provider to generate some cryptographic auxiliary information, based on which the SDP can construct a verification object to allow the data consumer to verify the integrity and completeness of the query result. They, however, differ in how the auxiliary information is generated and how the verification object is constructed and verified. Detailed analysis and extensive experiments using a real Twitter dataset confirm the efficacy and efficiency of the proposed schemes. [ABSTRACT FROM AUTHOR]

Internet of Things (IoT) is flourishing and has penetrated deeply into people’s daily life. With the seamless connection to the physical world, IoT provides tremendous opportunities to a wide range of applications. However, potential risks exist when the IoT system collects sensor data and uploads it to the Cloud. The leakage of private data can be severe with curious database administrator or malicious hackers who compromise the Cloud. In this work, we propose Kryptein, a compressive-sensing-based lightweight encryption scheme for Cloud-enabled IoT systems to secure the interaction between the IoT devices and the Cloud. Kryptein supports random compressed encryption, statistical computation over cipher, and accurate raw data decryption. According to our evaluation based on two real datasets, Kryptein provides strong protection to the data. It is 250 times faster than other state-of-the-art systems and incurs 120 times less energy consumption. The performance of Kryptein is also measured on off-the-shelf IoT devices, and the result shows Kryptein can run efficiently on IoT devices. After comparing with other state-of-the-art lightweight ciphers on IoT (Simon and Speck), IoT system with Kryptein is expected to have a much more longevity with about 35 percent extended lifetime. Further, experiments illustrated IoT data variance will not affect Kryptein’s accuracy in a long term usage, and Krpytein is also able to support basic analytics tasks like machine learning (e.g., classification). [ABSTRACT FROM AUTHOR]

Due to the growing popularity of indoor location-based services, indoor data management has received significant research attention in the past few years. However, we observe that the existing indexing and query processing techniques for the indoor space do not fully exploit the properties of the indoor space. Consequently, they provide below par performance which makes them unsuitable for large indoor venues with high query workloads. In this paper, we first propose two novel indexes called Indoor Partitioning Tree (IP-Tree) and Vivid IP-Tree (VIP-Tree) that are carefully designed by utilizing the properties of indoor venues. The proposed indexes are lightweight, have small pre-processing cost and provide near-optimal performance for shortest distance and shortest path queries. We are also the first to study spatial keyword queries in indoor venues. We propose a novel data structure called Keyword Partitioning Tree (KP-Tree) that indexes objects in an indoor partition. We propose an efficient algorithm based on VIP-Tree and KP-Trees to efficiently answer spatial keyword queries. Our extensive experimental study on real and synthetic data sets demonstrates that our proposed indexes outperform the existing solutions by several orders of magnitude. [ABSTRACT FROM AUTHOR]

Community search is the task of discovering dense subgraph that satisfy a set of given query parameters. Most community search algorithms consider link structure while ignoring link weight. A recent study proposed the idea of discovering weighted communities which focuses on both link structure and link weight using an online search approach and index-based approach. In this paper two online algorithms are proposed to scale-up the existing online approach efficiency. Performance evaluation of the proposed algorithms against the existing online approach over different datasets shows a great improvement in terms of search and query evaluation time.

The widespread use of GPS smart devices has allowed users to collect location information in real-time, leading to the emergence of ride-sharing services based on users' locations. Ride-sharing services have become effective services that reduce the cost of individual use of vehicles and also reduce the amount of gas that vehicles emit. Many studies have been conducted on ride-sharing services, which have focused on calculating the optimal cost of assigning users to vehicles in consideration of various cases of vehicle-sharing services (e.g., vehicles move to pick passengers, or passengers move to the vehicle's location). However, since the focus was only on improving the performance of queries, it is not easy to apply the proposed queries directly to the actual services. In real-world services, resources are generally finite. So, it happens that service providers are unable to follow that derived from optimal results. This paper focuses on considering limited resources in collective travel planning, a kind of group query available in ride-sharing services. We call this novel query as Resource Capacitated Collective Travel Planning (RCCTP). Unfortunately, the RCCTP query is NP-hard. So, we propose three-level pruning rules to answer the correct result with theoretical proofs and propose a new approximation method that can answer the RCCTP query efficiently. We show that the experimental evaluation demonstrates those improvements in query performance compared with the existing method.

The growing number of connected Internet of Things (IoT) devices has increased the necessity for processing IoT data from multiple heterogeneous data stores. IoT data integration is a challenging problem owing to the heterogeneity of data stores in terms of their query language, data models, and schemas. In this paper, we propose a multi-store query system for IoT data called MusQ, where users can formulate join operation queries for heterogeneous data sources. To reconcile the heterogeneity between source schemas of IoT data stores, we extract a global schema from local source schemas semi-automatically by applying schema-matching and schema-mapping steps. In order to minimize the burden on the user to understand the finer details of various query languages, we define a unified query language called the multi-store query language (MQL), which follows a subset of the Datalog grammar. Thus, users can easily retrieve IoT data from multiple heterogeneous sources with MQL queries. As the three MQL query-processing join algorithms are based on a mediator-wrapper approach, MusQ performs efficient data integration over significant volumes of IoT data from multiple stores. We conduct extensive experiments to evaluate the performance of the MusQ system using a synthetic and large real IoT data set for three different types of data stores (RDBMS, NoSQL, and HDFS). The experimental results demonstrate that MusQ is suitable, scalable, and efficient query processing for multiple heterogeneous IoT data stores. Those advantages of MusQ are important in several areas that involve complex IoT systems, such as smart city, healthcare, and energy management.

Data incompleteness becomes a frequent phenomenon in a large number of contemporary database applications such as web autonomous databases, big data, and crowd-sourced databases. Processing skyline queries over incomplete databases impose a number of challenges that negatively influence processing the skyline queries. Most importantly, the skylines derived from incomplete databases are also incomplete in which some values are missing. Retrieving skylines with missing values is undesirable, particularly, for recommendation and decision-making systems. Furthermore, running skyline queries on a database with incomplete data raises a number of issues influence processing skyline queries such as losing the transitivity property of the skyline technique and cyclic dominance between the tuples. The issue of estimating the missing values of skylines has been discussed and examined in the database literature. Most recently, several studies have suggested exploiting the crowd-sourced databases in order to estimate the missing values by generating plausible values using the crowd. Crowd-sourced databases have proved to be a powerful solution to perform user-given tasks by integrating human intelligence and experience to process the tasks. However, task processing using crowd-sourced incurs additional monetary cost and increases the time latency. Also, it is not always possible to produce a satisfactory result that meets the user's preferences. This paper proposes an approach for estimating the missing values of the skylines by first exploiting the available data and utilizes the implicit relationships between the attributes in order to impute the missing values of the skylines. This process aims at reducing the number of values to be estimated using the crowd when local estimation is inappropriate. Intensive experiments on both synthetic and real datasets have been accomplished. The experimental results have proven that the proposed approach for estimating the missing values of the skylines over crowd-sourced enabled incomplete databases is scalable and outperforms the other existing approaches.

Ridesharing has gained much attention as a solution for mitigating societal, environmental, and economic problems. For example, commuters can reduce traffic jams by sharing their rides with others. Notwithstanding many advantages, the proliferation of ridesharing also brings some crucial issues. One of them is to rideshare with strangers. It makes someone feel uncomfortable or untrustworthy. Another complication is the high-latency of ridesharing group search because users may want to receive the result of their requests in a short time. Despite continuous efforts of academia and industry, the issues still remain. In this paper, for resolving the obstacles, we define a new problem, $\ell $ -cohesive $m$ -ridesharing group ( $\ell m$ -CRG) query, which retrieves a cohesive ridesharing group by considering spatial, social, and temporal information. The problem is based on the three underlying assumptions: people tend to rideshare with socially connected friends, people are willing to walk but not too much, and optimization of finding good groups is essential for both drivers and passengers. In our ridesharing framework, queries are processed by efficiently taking geo-social network data into account. For this purpose, we propose an efficient method for processing the queries using a new concept, exact $n$ -friend set, with its efficient update. Moreover, we further improve our method by utilizing inverted timetable (ITT), which grasps crucial time information. Specifically, we devise time-constrained and incremental personalized-proximity search (TIPS). Finally, the performance of the proposed method is evaluated by extensive experiments on several data sets.

The peer-to-peer (P2P) paradigm has become very popular for storing and sharing information. In most P2P systems, peers are connected by means of a limited range of uniform networks, leading to issues when some connected peers are isolated from the others. In order to address such issues, isolated peers rely on devices with long-range networks to relay their messages. However, since long-range devices can move freely, the set of connected peers may lose their connection. Hence, it is important not only to identify, but also to maximise the area known as the safe region (SR) where a long-range device can move freely while still maintaining connection with its peers. This paper illustrates an innovative and generic monitoring framework that addresses the issues related to frequent query location updating using a systematic approach. In our approach, we propose to apply the Reverse Nearest Neighbourhood (RNNH) concept in a P2P environment to efficiently identify and maximise the irregularly shaped area of the SR up to four times for the potential movement of the long-range devices. It was found that there is no need for costly re- computation when the query is retained within the SR. Monte-Carlo simulation was performed to calculate the area of the SR by weighing in shape irregularity. Experimental results demonstrate the effectiveness and efficiency of our approach.

A Hierarchical Bloom Filter (HBF)-based biometric framework was recently proposed to provide compact storage, noise tolerance, and fast query processing for resource-constrained environments, e.g., Internet of things (IoT). While security and privacy were also touted as features of the HBF, it was not thoroughly evaluated. Compared to the classical BFs, the HBF uses a threshold parameter to make robust authentication decisions when the HBF encounters noise in the biometric input which one would think might lead to security issues. In this paper, the attack vectors that could compromise the HBF security by increasing the false positive authentication of non-members and by leaking soft information about enrolled members are explored. With quantitative analyses, HBF-based biometric system security under these well-defined attack vectors is evaluated and it is concluded that the framework is more difficult to attack than the classical Bloom Filter. Further, experimental results show that soft biometric information is also kept private. [ABSTRACT FROM AUTHOR]

Spurred by the development of cloud computing, there has been considerable recent interest in the Database-as-a-Service (DaaS) paradigm. Users lacking in expertise or computational resources can outsource their data and database management needs to a third-party service provider. Outsourcing, however, raises an important issue of result integrity: how can the client verify with lightweight overhead that the query results returned by the service provider are correct (i.e., the same as the results of query execution locally)? This survey focuses on categorizing and reviewing the progress on the current approaches for result integrity of SQL query evaluation in the DaaS model. The survey also includes some potential future research directions for result integrity verification of the outsourced computations. [ABSTRACT FROM AUTHOR]

This paper revisits the classical problem of multiple query optimization in federated RDF systems. We propose a heuristic query rewriting-based approach to optimize the evaluation of multiple queries. This approach can take advantage of SPARQL 1.1 to share the common computation of multiple queries while considering the cost of both query evaluation and data shipment. Although we prove that finding the optimal rewriting for multiple queries is NP-complete, we propose a heuristic rewriting algorithm with a bounded approximation ratio. Furthermore, we propose an efficient method to use the interconnection topology between RDF sources to filter out irrelevant sources, and utilize some characteristics of SPARQL 1.1 to optimize multiple joins of intermediate matches. The extensive experimental studies show that the proposed techniques are effective, efficient and scalable. [ABSTRACT FROM AUTHOR]

XML queries can be modeled by twig pattern queries (TPQs) specifying predicates on XML nodes and XPath relationships satisfied between them. A lot of TPQ types have been proposed; this paper takes into account a TPQ model extended by a specification of output and non-output query nodes since it complies with the XQuery semantics and, in many cases, it leads to a more efficient query processing. In general, there are two types of approaches to process a TPQ: holistic joins and binary joins. Whereas the binary join approach builds a query plan as a tree of interconnected binary operators, the holistic join approach evaluates a whole query using one operator (i.e., using one complex algorithm). Surprisingly, a thorough analytical and experimental comparison is still missing despite an enormous research effort in this area. In this paper, we try to fill this gap; we analytically and experimentally show that the binary joins used in a fully-pipelined plan (i.e., the plan where each join operation does not wait for the complete result of the previous operation and no explicit sorting is used) can often outperform the holistic joins, especially for TPQs with a higher ratio of non-output query nodes. The main contributions of this paper can be summarized as follows: (i) we introduce several improvements of existing binary join approaches allowing to build a fully-pipelined plan for a TPQ considering non-output query nodes, (ii) we prove that for a certain class of TPQs such a plan has the linear time complexity with respect to the size of the input and output as well as the linear space complexity with respect to the XML document depth (i.e., the same complexity as the holistic join approaches), (iii) we show that our improved binary join approach outperforms the holistic join approaches in many situations, and (iv) we propose a simple combined approach that utilizes advantages of both types of approaches. [ABSTRACT FROM AUTHOR]

In the past few years ridesharing has largely reshaped the transportation marketplace. It is envisioned as a promising solution to transportation-related problems in metropolitan cities, such as traffic congestion and air pollution. In the current ridesharing research, social ridesharing, which makes use of social relations among drivers and riders to address safety issues, and dynamic pricing are two active directions with important business implications. Simultaneously optimizing social cohesion and revenue is vital to a commercial ridesharing platform's sustainable development, which, however, has not been previously studied. In this paper, we first present a new pricing scheme that better incentivizes drivers and riders to participate in ridesharing, and then propose a novel type of Price-aware Top-k Matching (PTkM) queries which retrieve the top-k vehicles for a rider's request by taking into account both social relations and revenue. We design an efficient algorithm with a set of powerful pruning techniques to tackle this problem. Moreover, we propose a novel index tailored to our problem to further speed up query processing. Extensive experimental results on real datasets show that our proposed algorithms achieve desirable performance for real-world deployment. [ABSTRACT FROM AUTHOR]

In this paper, we consider the SQL Selection-GroupBy-Aggregation (SGA) query evaluation on an untrusted MapReduce system in which mappers and reducers may return incorrect results. We design CorrectMR, a system that supports efficient verification of result correctness for both intermediate and final results of SGA queries. CorrectMR includes the design of Pedersen Merkle R-tree (PMR-tree), a new authenticated data structure (ADS). To enable efficient verification, CorrectMR includes a distributed ADS construction mechanism that allows mappers/reducers to construct PMR-trees in parallel without a centralized party. CorrectMR provides the following verification functionality: (1) correctness verification of PMR-trees by replication; (2) correctness verification of intermediate (final, resp.) query results by constructing local (global, resp.) PMR-trees and verification objects. Our experimental results demonstrate the efficiency and effectiveness of CorrectMR. [ABSTRACT FROM AUTHOR]

The spatio-temporal reachable area that can be reached by driving vehicles from a specific starting location at starting time during a given time period is widely used in urban applications, such as the online ride-hailing service and the charging station seeking by an electric car. Existing studies on this issue usually utilize the static road network, which implies the spatial features, whereas the temporal characteristics of the dynamic urban traffic have not been explored in depth. In this article, we propose a spatio-temporal reachable area calculation scheme, named STRC, based on a tremendous amount of vehicle trajectory data. In STRC, the objective trajectory fragments are extracted according to the starting node and the query time period, and then mapped to reachable nodes to reduce the computational complexity. From those reachable road segments having reachable nodes on, a boundary segment is selected in each sector area by using the arrival-based one segment policy for time-sensitive applications or the arrival-and-distance-based k-segment policy for distance-related applications. The experiments based on large-scale trajectory data from 34 040 taxis in Beijing for one month show that STRC outputs more accurate reachable area, which covers the trajectory points with much smaller area, than compared schemes. [ABSTRACT FROM AUTHOR]