Search

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]

In this paper, a heterogeneous spatial-temporal similarity search framework is proposed, in which the datasets come from multiple different asynchronous data sources. Due to measuring error, data loss, and other factors, the similarity search based on single points along a trajectory usually cannot fulfill the accuracy requirements in our heterogeneous case. To address this issue, we introduce a concept of the spatial-temporal cluster of points, instead of single points, which can be identified for each target query. By following this concept, we further design a spectral clustering algorithm to construct the clusters in the pre-processing phase effectively. And the query processing is improved for the accuracy of the search by unifying multiple search metrics. To validate our idea, we also prototype a clustered online spatial-temporal similarity search system, "Osprey", to calculate in parallel the similarity of spatial-temporal sequences in the heterogeneous search on a distributed database. Our empirical study is conducted based on an open dataset, called "T-Drive", and a billion-scale dataset consisting of WiFi positioning records gathered from the urban metro system in Shenzhen, China. The experimental results show that the latency of our proposed system is less than 4s in most cases, and the accuracy is more than 70% when the similarity exceeds 0.5. [ABSTRACT FROM AUTHOR]

An excellent cardinality estimation can make the query optimiser produce a good execution plan. Although there are some studies on cardinality estimation, the prediction results of existing cardinality estimators are inaccurate and the query efficiency cannot be guaranteed as well. In particular, they are difficult to accurately obtain the complex relationships between multiple tables in complex database systems. When dealing with complex queries, the existing cardinality estimators cannot achieve good results. In this study, a novel cardinality estimator is proposed. It uses the core techniques with the BiLSTM network structure and adds the attention mechanism. First, the columns involved in the query statements in the training set are sampled and compressed into bitmaps. Then, the Word2vec model is used to embed the word vectors about the query statements. Finally, the BiLSTM network and attention mechanism are employed to deal with word vectors. The proposed model takes into consideration not only the correlation between tables but also the processing of complex predicates. Extensive experiments and the evaluation of BiLSTM‐Attention Cardinality Estimator (BACE) on the IMDB datasets are conducted. The results show that the deep learning model can significantly improve the quality of cardinality estimation, which is a vital role in query optimisation for complex databases. [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]

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]

Abstract The existing privacy protection schemes for Location‐Based Service (LBS) only protect users' location privacy or query privacy, which can not adopt both of the privacy protections simultaneously in the LBS system. Moreover, these schemes cannot take into account the spatial‐temporal correlation and background knowledge. In response to the above mentioned questions, the LBS Privacy Protection Scheme Based on Differential Privacy (DPLQ) is proposed. The method contains two kinds of privacy protection algorithms: users' location privacy protection algorithm and users' query privacy protection algorithm. The users' location privacy protection algorithm divides the map using the Voronoi diagram, choosing l fake location points based on the improved k‐means algorithm and l‐diversity idea, and protects users' location privacy with the Laplace mechanism. Based on the k‐anonymous algorithm, the users' query privacy protection algorithm builds a query k‐anonymous set according to the neighbour users' query requests at the same time t in the cluster and the historical query probability of the region’s POI and protects users' query privacy with the exponential mechanism. Through setting the privacy protection intensity of the algorithm by the users, the generated location dataset and query k‐anonymous set can resist a variety of attacks from malicious attackers. Theoretical analysis and experimental results show that the scheme can effectively protect the location privacy and query privacy of users.

Abstract Resource Description Framework (RDF) is commonly used as a standard for data interchange on the web. The collection of RDF data sets can form a large graph which consumes time to query. It is known that modern Graphic Processing Units (GPUs) can be employed to execute parallel programs in order to speedup the running time. In this paper, we propose a novel RDF data representation along with the query processing algorithm that is suitable for GPU processing. Since the main challenges of GPU architecture are the limited memory sizes, the memory transfer latency, and the vast number of GPU cores. Our system is designed to strengthen the use of GPU cores and reduce the effect of memory transfer. We propose a representation consists of indices and column-based RDF ID data that can reduce the GPU memory requirement. The indexing and pre-upload filtering techniques are then applied to reduce the data transfer between the host and GPU memory. We add the index swapping process to facilitate the sorting and joining data process based on the given variable and add the pre-upload step to reduce the size of results’ storage, and the data transfer time. The experimental results show that our representation is about 35% smaller than the traditional NT format and 40% less compared to that of gStore. The query processing time can be speedup ranging from 1.95 to 397.03 when compared with RDF3X and gStore processing time with WatDiv test suite. It achieves speedup 578.57 and 62.97 for LUBM benchmark when compared to RDF-3X and gStore. The analysis shows the query cases which can gain benefits from our approach.

Molecular Dynamics (MD) simulation is often used to study properties of various chemical interactions in domains such as drug discovery and development, particularly when executing real experimental studies is costly and/or unsafe. Studying the motion of trajectories of molecules/atoms generated from MD simulations provides a detailed atomic level spatial location of every atom for every time frame in the experiment. The analysis of this data leads to an atomic and molecular level understanding of interactions among the constituents of the system of interest. However, the data is extremely large and poses storage and processing challenges in the querying and analysis of associated atom level motion trajectories. We take a first step towards applying domain-specific generalization techniques for the data representation, subsequently used for applying trajectory compression algorithms towards reducing the storage requirements and speeding up the processing of within-distance queries over MD simulation data. We demonstrate that this generalization-aware compression, when applied to the dataset used in this case study, yields significant improvements in terms of data reduction and processing time without sacrificing the effectiveness of within-distance queries for threshold-based detection of molecular events of interest, such as the formation of Hydrogen Bonds (H-Bonds). • Molecular Dynamics outputs big trajectory data, studied to find chemical interactions. • Trajectory compression yields storage savings and speeds up query processing. • Context-aware generalization used to pre-process data while keeping semantic features. • Comparing generalization and compression to extant trajectory compression algorithms. [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]

Since the power of transmitting one-bit data is higher than that of computing one thousand lines of code in IoT (Internet of Things) applications, it is very important to reduce communication costs to save battery power and prolong system lifetime. In IoT sensors, the transformation of physical phenomena to data is usually with distortion (bounded-error tolerance). It introduces bounded-error data in IoT applications according to their required QoS2 (quality-of-sensor service) or QoD (quality-of-decision making). In our previous work, we proposed a bounded-error data compression scheme called BESDC (Bounded-Error-pruned Sensor Data Compression) to reduce the point-to-point communication cost of WSNs (wireless sensor networks). Based on BESDC, this paper proposes an online bounded-error query (OBEQ) scheme with edge computing to handle the entire online query process. We propose a query filter scheme to reduce the query commands, which will inform WSN to return unnecessary queried data. It not only satisfies the QoS2/QoD requirements, but also reduces the communication cost to request sensing data. Our experiments use real data of WSN to demonstrate the query performance. Results show that an OBEQ with a query filter can reduce up to 88% of the communication cost when compared with the traditional online query process. [ABSTRACT FROM AUTHOR]

Cloud computing is rapidly expanding because it allows users to save the development and implementation time on their work. It also reduces the maintenance and operational costs of the used systems. Furthermore, it enables the elastic use of any resource rather than estimating workload, which may be inaccurate, as database systems can benefit from such a trend. In this paper, we propose an algorithm that allocates the materialized view over cloudbased replica sets to enhance the database system's performance in stock market using a Peer-to-Peer architecture. The results show that the proposed model (MVCRS) improves the query processing time and network transfer cost by distributing the materialized views over cloudbased replica sets. Also, it has a significant effect on decision-making and achieving economic returns. [ABSTRACT FROM AUTHOR]

Linked Data Fragments (LDFs) refer to interfaces that allow for publishing and querying Knowledge Graphs on the Web. These interfaces primarily differ in their expressivity and allow for exploring different trade-offs when balancing the workload between clients and servers in decentralized SPARQL query processing. To devise efficient query plans, clients typically rely on heuristics that leverage the metadata provided by the LDF interface, since obtaining fine-grained statistics from remote sources is a challenging task. However, these heuristics are prone to potential estimation errors based on the metadata which can lead to inefficient query executions with a high number of requests, large amounts of data transferred, and, consequently, excessive execution times. In this work, we investigate robust query processing techniques for Linked Data Fragment clients to address these challenges. We first focus on robust plan selection by proposing CROP, a query plan optimizer that explores the cost and robustness of alternative query plans. Then, we address robust query execution by proposing a new class of adaptive operators: Polymorphic Join Operators. These operators adapt their join strategy in response to possible cardinality estimation errors. The results of our first experimental study show that CROP outperforms state-of-the-art clients by exploring alternative plans based on their cost and robustness. In our second experimental study, we investigate how different planning approaches can benefit from polymorphic join operators and find that they enable more efficient query execution in the majority of cases. [ABSTRACT FROM AUTHOR]

Abstract This article focusses on the problems associated with or unavailability of service in the Indian transportation system. Nowadays, web portal pages and Internet require most frequent search capability. In applying queries for data searches, this work procedure expressly demonstrates intriguing aspects of the query that utilize gathering terms. These gatherings are semantically correlated but separate from search results. The query is fired for the best travel route to make the travel system more intelligent. Such gatherings can be applied to real‐time applications such as those for airlines, trains, buses, and diverse and distinct flight travel classes to determine the lowest cost and shortest route. In this work, the gatherings are called query aspects. This work investigates a method for web applications that searches for data from a user search and generates a list of the shortest and lowest cost travel routes. A proposed intelligent algorithm is developed and analysed for searching data effectively. The user selects from a list of the low‐cost, shortest routes by the preferred mode of travel (flight/train/bus). The proposed method reduces customer dependency on solely vehicle (cab/bus/train) services, where prices may be too high and travel time too long. The proposed method demonstrates suitable performance by visualization of data against considered peer methods.

Abstract Background Graphs are mathematical structures widely used for expressing relationships among elements when representing biomedical and biological information. On top of these representations, several analyses are performed. A common task is the search of one substructure within one graph, called target. The problem is referred to as one-to-one subgraph search, and it is known to be NP-complete. Heuristics and indexing techniques can be applied to facilitate the search. Indexing techniques are also exploited in the context of searching in a collection of target graphs, referred to as one-to-many subgraph problem. Filter-and-verification methods that use indexing approaches provide a fast pruning of target graphs or parts of them that do not contain the query. The expensive verification phase is then performed only on the subset of promising targets. Indexing strategies extract graph features at a sufficient granularity level for performing a powerful filtering step. Features are memorized in data structures allowing an efficient access. Indexing size, querying time and filtering power are key points for the development of efficient subgraph searching solutions. Results An existing approach, GRAPES, has been shown to have good performance in terms of speed-up for both one-to-one and one-to-many cases. However, it suffers in the size of the built index. For this reason, we propose GRAPES-DD, a modified version of GRAPES in which the indexing structure has been replaced with a Decision Diagram. Decision Diagrams are a broad class of data structures widely used to encode and manipulate functions efficiently. Experiments on biomedical structures and synthetic graphs have confirmed our expectation showing that GRAPES-DD has substantially reduced the memory utilization compared to GRAPES without worsening the searching time. Conclusion The use of Decision Diagrams for searching in biochemical and biological graphs is completely new and potentially promising thanks to their ability to encode compactly sets by exploiting their structure and regularity, and to manipulate entire sets of elements at once, instead of exploring each single element explicitly. Search strategies based on Decision Diagram makes the indexing for biochemical graphs, and not only, more affordable allowing us to potentially deal with huge and ever growing collections of biochemical and biological structures.

Abstract SQL injection attack (SQLIA) is a code injection technique, used to attack data‐driven applications by executing malicious SQL statements. Techniques like pattern matching, software testing and grammar analysis etc. are frequently used to prevent such attack. However, major bottlenecks still remain in detecting SQLIA with bypassing techniques, getting access to source code and requiring an additional manual operation to extract features. The authors propose a novel detection approach based on long short‐term memory and abstract syntax tree, which could detect SQLIAs from the raw query strings and work under SQL detection bypassing scenario. Our deep learning technique explicitly uses both context and syntax information that previous methods failed to fully grasp. Experimental results clearly illustrate the superior performance of our method compared to other existing works when detecting with complete SQL raw queries.

Abstract Searching relevant papers is a fundamental task for the elaboration of secondary studies. This task is known to be tedious and time‐consuming when it is made manually, especially with the presence of several academic repositories. Recently, Semantic Scholar has emerged as a new artificial intelligence‐based search engine enabling a set of valuable features. The present study investigates the role of Semantic Scholar in retrieving relevant papers for performing secondary studies in software engineering. For this sake, an examination is performed to check the ability of Semantic Scholar to locate included papers in recent and well‐established secondary studies. Afterwards, a hybrid and automatic search strategy is introduced making use of Semantic Scholar as a sole search engine and it incorporates: automatic search, snowballing, and use of Computer Science Ontology (CSO) and Software Engineering Body of Knowledge (SWEBOK) for refining queries. The proposed strategy is validated by replicating the search of high‐quality secondary studies in the software engineering field. To guarantee objectivity, a systematic search is conducted of recent secondary studies published in the field since 2015. For the coverage test, Semantic Scholar is examined to locate primary papers of selected secondary studies and identify missing venues. The proposed search strategy is used to check the ability to retrieve primary papers of each secondary study. The systematic search yielded 20 high‐quality secondary studies with 1337 distinct primary papers. The coverage test revealed that Semantic Scholar covers 98.88% of the papers. The proposed search strategy enabled the full replication of 13 studies and more than 90% for the 7 remaining studies.

Abstract Knowledge graphs are a powerful concept for querying large amounts of data. These knowledge graphs are typically enormous and are often not easily accessible to end-users because they require specialized knowledge in query languages such as SPARQL. Moreover, end-users need a deep understanding of the structure of the underlying data models often based on the Resource Description Framework (RDF). This drawback has led to the development of Question-Answering (QA) systems that enable end-users to express their information needs in natural language. While existing systems simplify user access, there is still room for improvement in the accuracy of these systems. In this paper we propose a new QA system for translating natural language questions into SPARQL queries. The key idea is to break up the translation process into 5 smaller, more manageable sub-tasks and use ensemble machine learning methods as well as Tree-LSTM-based neural network models to automatically learn and translate a natural language question into a SPARQL query. The performance of our proposed QA system is empirically evaluated using the two renowned benchmarks-the 7th Question Answering over Linked Data Challenge (QALD-7) and the Large-Scale Complex Question Answering Dataset (LC-QuAD). Experimental results show that our QA system outperforms the state-of-art systems by 15% on the QALD-7 dataset and by 48% on the LC-QuAD dataset, respectively. In addition, we make our source code available.

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.

Abstract A time‐specific encrypted range query scheme that has the following properties is proposed. (1) The proposed scheme has trapdoor privacy and data privacy so that a semi‐honest cloud is not able to get any useful information from given ciphertexts and given tokens that are used for searching ranges. (2) Unlike most of the other studies which report that the cloud server stores single encrypted keyword/element in the database, in our solution, the cloud server stores encrypted multi‐keywords/ranges in the database. Therefore, the semi‐honest cloud compares ciphertexts to tokens as ranges based on a predefined threshold ϕ value. This approach decreases the cloud search time since the cloud compares ranges to ranges (multi‐keywords with multi‐keywords) not points to points (not a keyword with a keyword). Thus, the proposed scheme is efficient based on searching ranges on ciphertexts. (3) Moreover, the communication cost between users and the cloud is decreased from O(n) to O(log n), where n is the size of a range. Users send logarithmic size information to the cloud server instead of sending linear size information.

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]

The new generation of information technology is exchanging a huge data and these data should be process for analytical and visualization purposes. In most of our daily activities we are exchanging the data such as our mobile devices maintains call records, visited location records, exchanging messages etc., and these data are growing drastically and becomes a challenging task to maintain these data. From the starting of human civilization until 2000, humankind produces five Exabyte data but we are producing five Exabyte data every day. These data become useless if some query operation is not performed on it. Data analysis canon these data results any business more responsive and stronger and overcome business challenges. Thus, query-processing system takes place and it plays very decisive part in big data. This paper differentiates betwixt disparate query optimization processes and their algorithms utilized in big data for avoiding issues in query optimization. Utilizing different query processing techniques, the researchers are assisted by this review to find a disparate way for processing the data and how to enhance the query processing as well as optimization in various applications. [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]

RDF has seen increased adoption in recent years, prompting the standardization of the SPARQL query language for RDF, and the development of local and distributed engines for processing SPARQL queries. This survey paper provides a comprehensive review of techniques and systems for querying RDF knowledge graphs. While other reviews on this topic tend to focus on the distributed setting, the main focus of the work is on providing a comprehensive survey of state-of-the-art storage, indexing and query processing techniques for efficiently evaluating SPARQL queries in a local setting (on one machine). To keep the survey self-contained, we also provide a short discussion on graph partitioning techniques used in the distributed setting. We conclude by discussing contemporary research challenges for further improving SPARQL query engines. An extended version also provides a survey of over one hundred SPARQL query engines and the techniques they use, along with twelve benchmarks and their features. [ABSTRACT FROM AUTHOR]

Graphic processing units (GPUs) have been employed as hardware accelerators for online analytics. However, multi-way joins, which are common in analytic workloads, are inefficient on GPUs. Therefore, we propose to accelerate two representative multi-way join algorithms on the GPU: a multi-way hash join (MHJ) and the worst-case optimal Leapfrog Triejoin (LFTJ). Specifically, we design a warp-based parallelization strategy to reduce thread divergence and to facilitate coalesced memory access in parallel searches in a table. We further enhance our implementations with a set of GPU-friendly optimizations, including dynamic workload sharing among threads and elimination of the result counting phase. Additionally, we enable out-of-core multi-way joins with software pipelining. Our experiments show that our optimized MHJ and LFTJ outperform the state-of-the-art GPU algorithms by a factor of up to 67 on an NVIDIA V100 GPU. [ABSTRACT FROM AUTHOR]

Finding the shortest-path distance between an arbitrary pair of vertices is a fundamental problem in graph theory. A tremendous amount of research has explored this problem, most of which is limited to static graphs. Due to the dynamic nature of real-world networks, such as social networks or web graphs in which a link between two entities may fail or become alive at any time, there is a pressing need to address this problem for dynamic networks. Existing work can only accommodate distance queries over moderately large dynamic networks due to high space cost and long pre-processing time required for constructing distance labelling, and even on such moderately large dynamic networks, distance labelling can hardly be updated efficiently. In this article, we propose a fully dynamic labelling method to efficiently update distance labelling so as to answer distance queries over large dynamic graphs. At its core, our proposed method incorporates two building blocks: (i) incremental algorithm for handling incremental update operations, i.e. edge insertions, and (ii) decremental algorithm for handling decremental update operations, i.e. edge deletions. These building blocks are built in a highly scalable framework of distance query answering. We theoretically prove the correctness of our fully dynamic labelling method and its preservation of the minimality of labelling. We have also evaluated on 13 real-world large complex networks to empirically verify the efficiency, scalability and robustness of our method. [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]