With the rapid evolution of GPU architectures, the heterogeneity of model training infrastructures is steadily increasing. In such environments, effectively utilizing all available heterogeneous accelerators becomes critical for distributed model training. However, existing frameworks, which are primarily designed for homogeneous clusters, often exhibit significant resource underutilization when deployed on heterogeneous accelerators and networks. In this paper, we present Harp, an automated parallel training framework designed specifically for heterogeneous clusters. Harp introduces a fine-grained planner that efficiently searches a wide space for the inter-operator parallel strategy, enabling Harp to alleviate communication overheads while maintaining balanced loads across heterogeneous accelerators. In addition, Harp implements a heterogeneity-aware 1F1B scheduler that adaptively adjusts the execution timing and ordering of microbatches based on network characteristics, maximizing computation-communication overlap under cross-cluster interconnects while incurring only minimal memory overhead. Our evaluation results show that Harp can deliver 1.3×–1.6× higher performance on heterogeneous clusters than state-of-the-art training frameworks.

There have been a flurry of recent proposals on learned benefit estimators for index tuning. Although these learned estimators show promising improvement over what-if query optimizer calls in terms of the accuracy of estimated index benefit, they face significant limitations when applied to online index tuning, an arguably more common and more challenging scenario in real-world applications. There are two major challenges for learned index benefit estimators in online tuning: (1) limited amount of query execution feedback that can be used to train the models, and (2) constant coming of new unseen queries due to workload drifts. The combination of the two hinders the generalization capability of existing learned index benefit estimators. To overcome these challenges, we present UTune, an uncertainty-aware online index tuning framework that employs operator-level learned models with improved generalization over unseen queries. At the core of UTune is an uncertainty quantification mechanism that characterizes the inherent uncertainty of the operator-level learned models given limited online execution feedback. We further integrate uncertainty information into index selection and configuration enumeration, the key component of any index tuner, by developing a new variant of the classic $ε$-greedy search strategy with uncertainty-weighted index benefits. Experimental evaluation shows that UTune not only significantly improves the workload execution time compared to state-of-the-art online index tuners but also reduces the index exploration overhead, resulting in faster convergence when the workload is relatively stable.

In database systems, cost estimation for query plans has a variety of uses, including query optimization, resource management, load balancing, query scheduling, performance monitoring, and automated maintenance. Existing methods mainly targeted B-tree-based systems, where costs and cardinality are highly correlated. However, LSM-Trees, due to their unique storage structure, violate the assumptions of existing learning methods, causing cardinality to be irrelevant to cost estimation. In addition, the constantly changing data layout leads to severe data drifts when updating data, preventing current learning based models from accurately estimating costs in an agile way. To address these challenges, we propose a dual-layer end-to end cost estimation model for LSM-Tree-based database systems. This model treats cost estimation as a regression problem and comprises two layers: the storage layer and the query plan layer. The storage layer employs lightweight neural networks to leverage data distribution, provide information to the query plan layer, and address the challenges posed by data drift in LSM Trees. The query plan layer uses the Transformer framework and incorporates structural information to learn the representation of plans. This dual-layer architecture allows our model to effectively embed storage information and query plan tree details. The results show that our proposed model achieves state-of-the art cost estimation accuracy for database systems based on LSM-Trees. Additionally, our architecture significantly reduces the model's updating costs, ensuring robust performance amid frequent data drifts.

Efficient processing of k-nearest neighbor (kNN) join operations on streaming data is critical for applications in location-aware services, recommendation systems, and spatial analytics. To serve users in real time, these applications generally require a high-performance kNN join on continuously changing streaming data. This paper introduces StreamingRT, a framework that leverages ray tracing (RT) cores in GPUs to accelerate stream kNN joins in 3D space. By modeling stream data into large primitives and transferring queries into short rays, StreamingRT transforms the kNN join problem into an efficient ray tracing task. To address the ray tracing index updating overhead on stream data, we propose two key techniques, i.e., boundary-extended point partitioning and query-driven BVH lazy updating. Moreover, we also adopt multi-BVH coprocessing and CPU-GPU pipelining to improve performance. These techniques enable efficient stream kNN join on ray tracing cores, delivering unprecedented performance improvement. Experimental evaluations show that StreamingRT can achieve up to 2.2× and 5.8× speedup over the state-of-the-art approach on RT cores and CUDA cores, respectively.

The exponential growth of video data highlights the necessity of exploring large-scale video repositories to extract valuable insights. Querying video clips based on content and temporal attributes is a critical task. However, existing solutions face two major challenges: insufficient flexibility in handling complex query conditions involving statistical reasoning and temporal constraints, and low efficiency under high query quality requirements and resource constraints.

For interactive data exploration, approximate query processing (AQP) is a useful approach that provides a timely response by trading query accuracy. To reduce query latency, existing AQP methods use samples or models rather than the underlying data to answer queries. However, it is difficult to achieve satisfactory results in terms of query accuracy and query latency simultaneously with these methods. For the sample-based methods, this is because the more accurate the query results are, the more samples are needed and the more time cost is required for processing. The model-based methods have lower query latency, but they cannot return the approximate results with high accuracy because the existing models cannot capture the complex data distribution accurately. In this paper, we propose a fast and accurate AQP method FAAQP . In FAAQP, we propose a novel unsupervised model bitmap-augmented sum-product network (BSPN) that combines the advantages of the sum-product network with bitmaps to capture the characteristics of data distribution more accurately. Then, we propose a budget-aware BSPN construction method that builds BSPN models with the maximum query accuracy for the given storage budget. Furthermore, to reduce the query latency of FAAQP, we propose a bitmap merging strategy that makes a trade-off between query accuracy and query latency. Experimental results on real-world and synthetic datasets show that FAAQP outperforms the state-of-the-art AQP methods and achieves 1.3×-9.0× improvements in query accuracy with a low query latency.

Persistent Regular Path Query (RPQ) on streaming graphs is widely applicable to many online analysis applications. Existing research primarily focuses on the single-worker scenario, while scaling out to distributed RPQ processing on multiple workers is desirable when facing a high workload. Existing distributed solutions are designed for general streaming queries, and various bottlenecks exist that significantly limit the performance when performing streaming RPQ evaluation. The challenge is how to execute queries with multiple workers while introducing limited overhead and ensuring sufficient speedup as the number of workers increases. This paper introduces a distributed processing strategy called DRPQ by carefully dividing a query into multiple partially matched query tasks. The idea is to form query tasks based on initial matches of the graph against the given regular expression, and to dynamically distribute these tasks to workers to balance their workloads. To reduce redundant evaluation across different workers, a grouping method is proposed to find query tasks that are likely to share evaluation processes, and send them to the same workers. Extensive experiments on two real-world graph datasets demonstrate that DRPQ is significantly more efficient and scalable than existing distributed solutions. Furthermore, the proposed grouping method proves to be particularly effective, nearly doubling the throughput in most cases.

Current large language model (LLM)-based Natural Language to SQL (NL2SQL) approaches typically rely on the database schema and partial data values for the translation. These approaches are unable to use sufficient data for accurate database understanding due to limitations in data selection methods, and they cannot input the entire database due to the limited context window sizes of LLMs. This insufficient data integration may result in an incomplete understanding of the database, leading to semantically incorrect SQL generation. In this paper, we introduce REDSQL, a novel plug-and-play framework that refines the predicted SQL by utilizing the entire database in the refinement process. The core idea of REDSQL is to enhance SQL refinement by identifying potential errors based on the database content, which is achieved by applying constraints on the input relations of query operations. LLMs can refine the SQL using SQL-related information extracted by REDSQL, which provides concise and informative insights into the database. Additionally, REDSQL enhances schema semantics by integrating data profiling for more effective database utilization. Our experiments demonstrate that REDSQL consistently improves the performance of existing NL2SQL approaches across five benchmarks. Specifically, REDSQL elevates the accuracy of CODES to 67.3% (+8.8%) and PURPLE to 67.7% (+11.1%) on the Bird benchmark.

An increasing number of web applications require cloud in-memory key-value stores to minimize latency and achieve higher throughput. They generally have diverse characteristics and constantly changing traffic volumes, which require different computational and memory resources. A serverless in-memory key-value store characterized by elastic resource allocation and pay-as-you-go billing could satisfy the requirements of diverse and dynamic workloads. However, we find current serverless IMKVs fail to achieve fine-grained and prompt resource elasticity due to the limitations of their infrastructures. This paper proposes Genie, a lightweight serverless infrastructure for in-memory key-value caching with fine-grained and immediate elasticity. In Genie, a novel approach is adopted to enable dynamic and independent resource allocation to multiple tenants. It processes all arrived requests and estimates the vCPU consumption with a lightweight machine-learning approach for fine-grained billing. Moreover, Genie estimates the working set and dynamically resizes the allocated memory for hit ratio requirements. Evaluation results show that CPU estimation could be achieved every 100 microseconds without impacting system performance, and memory capacity could be adjusted by megabytes within seconds. The holistic design incurs 1%-2% performance degradation compared to our baseline. Moreover, Genie achieves an average of 58.3% CPU and 49.9% memory savings compared to AsparaDB for Memcache.

The Natural Language Interface to Databases (NLIDB) empowers non-technical users with database access through intuitive natural language (NL) interactions. Advanced approaches, utilizing neural sequence-to-sequence models or large-scale language models, typically employ auto-regressive decoding to generate unique SQL queries sequentially. While these translation models have greatly improved the overall translation accuracy, surpassing 70% on NLIDB benchmarks, the use of auto-regressive decoding to generate single SQL queries may result in sub-optimal outputs, potentially leading to erroneous translations. In this paper, we propose Metasql, a unified generate-then-rank framework that can be flexibly incorporated with existing NLIDBs to consistently improve their translation accuracy. Metasql introduces query metadata to control the generation of better SQL query candidates and uses learning-to-rank algorithms to retrieve globally optimized queries. Specifically, Metasql first breaks down the meaning of the given NL query into a set of possible query metadata, representing the basic concepts of the semantics. These metadata are then used as language constraints to steer the underlying translation model toward generating a set of candidate SQL queries. Finally, Metasql ranks the candidates to identify the best matching one for the given NL query. Extensive experiments are performed to study Metasql on two public NLIDB benchmarks. The results show that the performance of the translation models can be effectively improved using Metasql. In particular, applying Metasql to the published Lgesql model obtains a translation accuracy of 77.4 % on the validation set and 72.3 % on the test set of the Spider benchmark, outperforming the baseline by 2.3% and 0.3%, respectively. Moreover, applying Metasql to GpT-4 achieves translation accuracies of 68.6%, 42.0%, and 17.6 % on the three real-world complex scientific databases of Sciencebenchmark, respectively. The code for Metasql is available at https://github.com/Kaimary/MetaSQL.

Large Language Model (LLM) techniques play an increasingly important role in Natural Language to SQL (NL2SQL) translation. LLMs trained by extensive corpora have strong natural language understanding and basic SQL generation abilities without additional tuning specific to NL2SQL tasks. Existing LLMs-based NL2SQL approaches try to improve the translation by enhancing the LLMs with an emphasis on user intention understanding. However, LLMs sometimes fail to generate appropriate SQL due to their lack of knowledge in organizing complex logical operator composition. A promising method is to input the LLMs with demonstrations, which include known NL2SQL translations from various databases. LLMs can learn to organize operator compositions from the input demonstrations for the given task. In this paper, we propose PURPLE (Pre-trained models Utilized to Retrieve Prompts for Logical Enhancement), which improves accuracy by retrieving demonstrations containing the requisite logical operator composition for the NL2SQL task on hand, thereby guiding LLMs to produce better SQL translation. PURPLE achieves a new state-of-the-art performance of 80.5% exact-set match accuracy and 87.8% execution match accuracy on the validation set of the popular NL2SQL benchmark Spider. PURPLE maintains high accuracy across diverse benchmarks, budgetary constraints, and various LLMs, showing robustness and cost-effectiveness.

Recent advancements in TableQA leverage sequence-to-sequence (Seq2seq) deep learning models to accurately respond to natural language queries. These models achieve this by converting the queries into SQL queries, using information drawn from one or more tables. However, Seq2seq models often produce uncertain (low-confidence) predictions when distributing probability mass across multiple outputs during a decoding step, frequently yielding translation errors. To tackle this problem, we present Ckif , a confidence-based knowledge integration framework that uses a two-stage deep-learning-based ranking technique to mitigate the low-confidence problem commonly associated with Seq2seq models for TableQA. The core idea of Ckif is to introduce a flexible framework that seamlessly integrates with any existing Seq2seq translation models to enhance their performance. Specifically, by inspecting the probability values in each decoding step, Ckif first masks out each low-confidence prediction from the predicted outcome of an underlying Seq2seq model. Subsequently, Ckif integrates prior knowledge of query language to generalize masked-out queries, enabling the generation of all possible queries and their corresponding NL expressions. Finally, a two-stage deep-learning ranking approach is developed to evaluate the semantic similarity of NL expressions to a given NL question, hence determining the best-matching result. Extensive experiments are conducted to investigate Ckif by applying it to five state-of-the-art Seq2seq models using a widely used public benchmark. The experimental results indicate that Ckif consistently enhances the performance of all the Seq2seq models, demonstrating its effectiveness for better supporting TableQA.

A persistent Regular Path Query (RPQ) on a streaming graph is to continuously find every pair of vertices that are connected by a path in the graph within a sliding window, such that the edge label sequence of this path matches a given regular expression. The existing RPQ evaluation algorithm in the literature incrementally maintains a set of spanning-tree-like data structures to quickly form query results and to avoid reprocessing edges that are shared by multiple sliding windows. This approach allows parallel processing of the graph edges within a sliding window but requires a blocking expiration phase between sliding windows to remove the old edges. This blocking phase can significantly degrade the query performance, especially when the edges arrive quickly and the sliding windows overlap significantly. This paper presents a new RPQ evaluation strategy called Multi-Window Parallel (MWP) method leveraging a new data structure called Timestamped Rooted Digraph (TRD). The novel idea is to incrementally maintain TRDs for the quick formulation of query results, like the aforementioned spanning trees, but simultaneously contain needed information for multiple sliding windows. MWP eliminates the forced blocking expiration phase. Only when memory runs low, a quick "dirty garbage collection" (DGC) process is done to remove some unneeded edges and nodes on TRDs, without incurring large costs. Extensive experiments on real graph datasets show that MWP significantly outperforms the existing algorithm in terms of throughput, tail latency, and scalability, and that DGC provides an effective solution for releasing memory with minimum impact.

Approximate Nearest Neighbor Search (ANNS) is a fundamental and critical component in many applications, including recommendation systems and large language model-based applications. With the advancement of multimodal neural models, which transform data from different modalities into a shared high-dimensional space as feature vectors, cross-modal ANNS aims to use the data vector from one modality (e.g., texts) as the query to retrieve the most similar items from another (e.g., images or videos). However, there is an inherent distribution gap between embeddings from different modalities, and cross-modal queries become Out-of-Distribution (OOD) to the base data. Consequently, state-of-the-art ANNS approaches suffer poor performance for OOD workloads. In this paper, we quantitatively analyze the properties of the OOD workloads to gain an understanding of their ANNS efficiency. Unlike single-modal workloads, we reveal OOD queries spatially deviate from base data, and the k-nearest neighbors of an OOD query are distant from each other in the embedding space. The property breaks the assumptions of existing ANNS approaches and mismatches their design for efficient search. With the insights from the OOD workloads, we propose p Ro jected bipartite Graph ( RoarGraph ), an efficient ANNS graph index that is built under the guidance of query distribution. Extensive experiments show that RoarGraph significantly outperforms state-of-the-art approaches on modern cross-modal datasets, achieving up to 3.56× faster search speed at a 90% recall rate for OOD queries.

Indexing is a core technique for accelerating predicate evaluation in databases. After many years of effort, the indexing performance has reached its peak on the existing hardware infrastructure. We propose to use ray tracing (RT) cores to move the indexing performance and efficiency to another level by addressing the following technical challenges: (1) the lack of an efficient mapping of predicate evaluation to a ray tracing job and (2) the poor performance by the heavy and imbalanced ray load when processing skewed datasets. These challenges set obstacles to effectively exploiting RT cores for predicate evaluation. In this paper, we propose RTScan, an approach that leverages RT cores to accelerate index scans. RTScan transforms the evaluation of conjunctive predicates into an efficient ray tracing job in a three-dimensional space. A set of techniques are designed in RTScan, i.e., Uniform Encoding, Data Sieving, and Matrix RT Refine, which significantly enhances the parallelism of scans on RT cores while lightening and balancing the ray load. With the proposed techniques, RTScan achieves high performance for datasets with either uniform or skewed distributions and queries with different selectivities. Extensive evaluations demonstrate that RTScan enhances the scan performance on RT cores by five orders of magnitude and outperforms the state-of-the-art approach on CPU by up to 4.6×.

Understanding the reasons behind differences between aggregated sequences derived from SQL queries is crucial for data scientists. However, existing methods often suffer from being labor-intensive, lacking scalability, providing only approximate solutions, and inadequately supporting sequence difference explanations. In response, we introduce SDEcho, a novel framework designed to automate the explanation searching for sequence differences in high-dimensional and high-volume datasets. SDEcho utilizes advanced pruning techniques, considering pattern, order, and dimension perspectives, as well as their interactions, to prune the entire explanation space while maintaining explanations accurate and concise. This hybrid pruning approach significantly accelerates the explanation searching process, making SDEcho a valuable tool for data analysis tasks. Extensive experiments on synthetic and real-world datasets, along with a case study, demonstrate that SDEcho outperforms existing methods in terms of both effectiveness and efficiency.

In the interactive data exploration, approximate query processing (AQP) can be used to quickly return query results at the cost of accuracy. For online AQP, the sampler can be treated as an operator in the query plan. During the query optimization for AQP, heuristic rules are usually used to guide the sampler push-down. However, due to the complexity and changes of data distribution, the heuristic rule-based optimization methods cannot meet the users’ query accuracy requirements. In this article, we propose a learning-based query optimization method for online AQP. We first introduce the weak equivalence concept and propose a series of push-down rules to guide the sampler push-down during the query optimization. Then, to enable more queries to meet the users’ query accuracy requirements, we propose a deep learning model to further optimize the query plan. By using this model during each push-down process of the sampler, we try to avoid the negative effect of inappropriate sampler push-down on query accuracy, especially when there is an inconsistency between the underlying and intermediate data distribution. Extensive experiments show that the method proposed in this paper can outperform the state-of-the-art online sampling-based AQP method by 1.2×−7.9× in query accuracy.

Outlier detection in data streams is a critical component in numerous applications, such as network intrusion detection, financial fraud detection, and public health. To detect abnormal behaviors in real-time, these applications generally have stringent requirements for the performance of outlier detection. This paper proposes RTOD, a high-performance outlier detection approach that utilizes RT cores in modern GPUs for acceleration. RTOD transforms distance-based outlier detection in data streams into an efficient ray tracing job. By creating spheres centered at points within a window and casting rays from each point, RTOD identifies the outlier points according to the number of intersections between rays and spheres. Besides, we propose two optimization techniques, namely Grid Filtering and Ray-BVH Inversion, to further accelerate the detection efficiency of RT cores. Experimental results show that RTOD achieves up to 9.9× speedups over existing start-of-the-art outlier detection algorithms.

For interactive data exploration, approximate query processing (AQP) is a useful approach that usually uses samples to provide a timely response for queries by trading query accuracy. Existing AQP systems often materialize samples in the memory for reuse to speed up query processing. How to tune the samples according to the workload is one of the key problems in AQP. However, since the data exploration workload is so complex that it cannot be accurately predicted, existing sample tuning approaches cannot adapt to the changing workload very well. To address this problem, this paper proposes a deep reinforcement learning-based sample tuner,RL-STuner. When tuning samples,RL-STunerconsiders the workload changes from a global perspective and uses a Deep Q-learning Network (DQN) model to select an optimal sample set that has the maximum utility for the current workload. In addition, this paper proposes a set of optimization mechanisms to reduce the sample tuning cost. Experimental results on both real-world and synthetic datasets show thatRL-STuneroutperforms the existing sample tuning approaches and achieves 1.6×-5.2× improvements on query accuracy with a low tuning cost.

In a Network Function Virtualization (NFV) system, network functions (NFs) are implemented on general-purpose hardware, including CPU, GPU, and FPGA. Studies have shown that there is no one-size-fits-all processor, as each processor demonstrates performance advantages to implement certain types of NFs. With more general-purpose processors such as GPUs being deployed in data center servers, the best practice to build a high-performance NFV service chain should employ available heterogeneous processors. However, current NFV systems fail to utilize these processors for acceleration. This is because, due to separate memory spaces, data synchronization is demanded to guarantee correctness, which can incur non-trivial overhead and result in low performance. This paper proposes AdaptChain, a data management facility that enables adaptive data sharing and synchronization for hybrid NFV systems on heterogeneous architectures. AdaptChain shares the host and device memory among NFs in a service chain. With adaptive synchronization plan generation and NF code adaptation, AdaptChain exploits three classes of opportunities to reduce the amount of synchronized data while guaranteeing correctness. Experimental results show that AdaptChain improves the overall throughput by up to 3.2× and reduces the latency by up to 52%.

A Natural Language (NL) Interface to Databases (NLIDB) aims to help end-users access databases. State-of-the-art approaches primarily construct language translation models to convert NL queries to SQL queries. While these models exhibit good performance on NLIDB benchmarks, the translation accuracy seems to have stalled at between 70%-75%, and most erroneous translations happen with complex queries that require an understanding of the structure and semantics specific to a database. This paper proposes a Generate-And-Rank approach called Gar. Gar assumes that a set of sample SQL queries is given to represent the possible user-intended queries to the database. In order to provide a broad coverage, akin to avoiding over-fitting, Gar extracts the basic components from the sample set to form the basic building blocks to generate a set of generalized SQL queries. By leveraging a simple rule-based SQL to NL technique, a less natural NL expression called a dialect expression for each sample and generalized SQL query is obtained. Finally, a learning-to-rank method is used for a given NL query to retrieve the best dialect expression and hence the resulting SQL query. Extensive experiments are performed to study Gar in comparison with other approaches. The results show that Gar achieves better performance on the NLIDB benchmarks, including in particular a 78.5% translation accuracy on the popular Spider benchmark, outperforming the best reported accuracy in the literature. An extension to Gar, called Gar-j, is further introduced to aid the translation by annotating join semantics in the sample queries. The experimental results show that Gar-j can further improve translation accuracy on queries with joins. Code for Gar can be found at https://github.com/Kaimary/GAR.

Web-based online interactive visual analytics enjoys popularity in recent years. Traditionally, visualizations are produced directly from querying the underlying data. However, for a very large dataset, this way is so time-consuming that it cannot meet the low-latency requirements of interactive visual analytics. In this paper, we propose a learning-based visualization approach called BlinkViz, which uses a learned model to produce approximate visualizations by leveraging mixed sum-product networks to learn the distribution of the original data. In such a way, it makes visualization faster and more scalable by decoupling visualization and data. In addition, to improve the accuracy of approximate visualizations, we propose an enhanced model by incorporating a neural network with residual structures, which can refine prediction results, especially for visual requests with low selectivity. Extensive experiments show that BlinkViz is extremely fast even on a large dataset with hundreds of millions of data records (over 30GB), responding in sub-seconds (from 2ms to less than 500ms for different requests) while keeping a low error rate. Furthermore, our approach remains scalable on latency and memory footprint size regardless of data size.

Abstract The size of textual data continues to grow along with the need for timely and cost-effective analysis, while the growth of computation power cannot keep up with the growth of data. The delays when processing huge textual data can negatively impact user activity and insight. This calls for a paradigm shift from blocking fashion to progressive processing. In this paper, we propose a sample-based progressive processing model that focuses on term frequency calculation on text. The model is based on an incremental execution engine and will calculate a series of approximate results for a single query in a progressive way to provide a smooth trade-off between accuracy and latency. As a part, we proposed a new variant of the bootstrap technique to quantify result error progressively. We implemented this method in our system called Parrot on top of Apache Spark and used real-world data to test its performance. Experiments demonstrate that our method is 2.4×–19.7× faster to get a result within 1% error while the confidence interval always covers the accurate results very well.

Agile analytics can help organizations to gain and sustain a competitive advantage by making timely decisions. Approximate query processing (AQP) is one of the useful approaches in agile analytics, which facilitates fast queries on big data by leveraging a pre-computed sample. One problem such a sample faces is that when new data is being imported, re-sampling is most likely needed to keep the sample fresh and AQP results accurate enough. Re-sampling from scratch for every batch of new data, called the full re-sampling method and adopted by many existing AQP works, is obviously a very costly process, and a much quicker incremental sampling process, such as reservoir sampling, may be used to cover the newly arrived data. However, incremental update methods suffer from the fact that the sample size cannot be increased, which is a problem when the underlying data distribution dramatically changes and the sample needs to be enlarged to maintain the AQP accuracy. This paper proposes an adaptive sample update (ASU) approach that avoids re-sampling from scratch as much as possible by monitoring the data distribution, and uses instead an incremental update method before a re-sampling becomes necessary. The paper also proposes an enhanced approach (T-ASU), which tries to enlarge the sample size without re-sampling from scratch when a bit of query inaccuracy is tolerable to further reduce the sample update cost. These two approaches are integrated into a state-of-the-art AQP engine for an extensive experimental study. Experimental results on both real-world and synthetic datasets show that the two approaches are faster than the full re-sampling method while achieving almost the same AQP accuracy when the underlying data distribution continuously changes.

In modern analytical database systems, the performance of the data scan operation is of key importance to the performance of query execution. Existing approaches may be categorized into index scan and sequential scan. However, both approaches have inherent inefficiencies. Indeed, sequential scan may need to access a large amount of unneeded data, especially for queries with low selectivity. Instead, index scan may involve a large number of expensive random memory accesses when the query selectivity is high. Moreover, with the growing complexities in database query workloads, it has become hard to predict which approach is better for a particular query. In order to obtain fast and robust scans under all selectivities, this paper proposes BinDex, a two-layered index structure based on binned bitmaps that can be used to significantly accelerate the scan operations for in-memory column stores. The first layer of BinDex consists of a set of binned bitmaps which filter out most unneeded values in a column. The second layer provides some auxiliary information to correct the bits that have incorrect values. By varying the number of bit vectors in the first layer, BinDex can make a tradeoff between memory space and performance. Experimental results show that BinDex outperforms the state-of-the-art approaches with less memory than a B+-tree would use. And by enlarging the memory space, BinDex can achieve up to 2.9 times higher performance, eliminating the need for making a choice between sequential or index scans.

Text clustering is a widely studied problem in the text mining domain. The Dirichlet Multinomial Mixture (DMM) model based clustering algorithms have shown good performance to cope with high dimensional sparse text data, obtaining reasonable results in both clustering accuracy and computational efficiency. However, the time complexity of DMM model training is proportional to the average document length and the number of clusters, making it inefficient for scaling up to long text and large corpora, which is common in realworld applications such as documents organization, retrieval and recommendation. In this paper, we leverage a symmetric prior setting for Dirichlet distribution, and build indices to decrease the time complexity of the sampling-based training for DMM from O(K∗L) to O(K∗U), where K is the number of clusters, L the average length of document, and U the average number of unique words in each document. We introduce a Metropolis-Hastings sampling algorithm, which further reduces the sampling time complexity from O(K∗U) to O(U) in the nearly-to-convergence training stages. Moreover, we also parallelize the DMM model training to obtain a further acceleration by using an uncollapsed Gibbs sampler. We combine all these optimizations into a highly efficient implementation, called X-DMM, which enables the DMM model to scale up for long and large-scale text clustering. We evaluate the performance of X-DMM on several real world datasets, and the experimental results show that XDMM achieves substantial speed up compared with existing state-of-the-art algorithms without clustering accuracy degradation.

Outsourcing spatial databases to the cloud provides an economical and flexible way for data owners to deliver spatial data to users of location-based services. However, in the database outsourcing paradigm, the third-party service provider is not always trustworthy, therefore, ensuring spatial query integrity is critical. In this paper, we propose an efficient road network k-nearest-neighbor query verification technique which utilizes the network Voronoi diagram and neighbors to prove the integrity of query results. Unlike previous work that verifies k-nearest-neighbor results in the Euclidean space, our approach needs to verify both the distances and the shortest paths from the query point to its kNN results on the road network. We evaluate our approach on real-world road networks together with both real and synthetic points of interest datasets. Our experiments run on Google Android mobile devices which communicate with the service provider through wireless connections. The experiment results show that our approach leads to compact verification objects (VO) and the verification algorithm on mobile devices is efficient, especially for queries with low selectivity.

Outsourcing spatial databases, including both road networks and points of interest, to a third party Cloud service provider has attracted much attention from individual and business data owners. With popularity of mobile devices, providing instant and reliable location-based services to smartphones and tablets has been a major means of delivering spatial data to real-world users. Therefore, ensuring spatial query integrity in database outsourcing paradigms is critical. In this paper, we propose a novel road network k-nearest-neighbor query verification technique which utilizes the network Voronoi diagrams and neighbors to prove the integrity of the query result. Unlike previous work that verifies k-nearest-neighbor results in the Euclidean space, our approach verifies both the distances and the shortest paths from the query point to its kNN result on the road network.

In the environment of Mobile Ad-hoc Networks (MANETs), devices can collaborate under the service-oriented architecture (SOA). However, as MANETs are infrastructure-less, devices may move randomly and join and leave the network at any time which leads to a permanently changing topology of the network. What adds to the unpredictability of the network is the limited resource of the nodes, including battery power, processing capacity and memory limit which are common problems for mobile devices. All these features pose a potential risk of failure to the process of service execution. Therefore, service recovery is indispensable to guarantee the success rate when the service execution plan cannot be conducted as the user expects. In this paper, we proposed a novel strategy of service execution and service recovery. By employing additional control messages, the point of fault can be quickly acknowledge by the closest device which will then take the responsibility of service recovery. Using the distributed service cache which is maintained by each node in the network, a back-up service execution plan will be elected promptly. The simulation shows that our strategy can effectively reduce the response time and increase the success rate of service execution.

Wireless broadcast provides a scalable and secure spatial data dissemination approach for geographical applications in wireless mobile environments. Among various location-based services, the shortest path query on road networks is one of the most popular and essential services in our daily life. In this paper, we propose an energy-efficient scheme for on air shortest path query processing on road networks, which leverages an elaborate air index called BagIndex based upon the novel Hilbert-based heuristic tree decomposition for the road networks. Experimental results show that the proposed approach incurs less energy consumption on both communication and computation than the previous schemes.

Traceback technique is useful to identify the source of an attack. Several types of traceback schemes have been proposed for wired networks. But most of them are not suitable for mobile ad hoc networks (MANETs) due to limited resource and dynamically-changing topology. Among all of existing schemes, probabilistic packet marking (PPM) scheme might be the most promising scheme for MANET because it is more lightweight than others. However, it is difficult for PPM scheme to converge quickly in MANET, since it relies on the assumption of static topology that does not hold in MANET due to dynamic topology. In this paper, we propose a traceable overlay network with relative stable topology support for traceback based on identity replacement mechanism. We present the protocol design and experiments. The experiment results show that our approach can get a much more stable topology for traceback and better traceback performance in MANET.

Aggregate nearest neighbor (ANN) query returns a common interesting data object that minimizes an aggregate distance for multiple query points. In this paper, we propose a novel approach to efficiently process ANN queries in road networks. This approach includes two processes: initializing process and pruning process, which are both based on computing kNN of query points in network Voronoi diagram. Experimental results show that our approach outperforms existing approaches on both response time and page accesses.

Distributed denial-of-service attacks have become the major threat to Internet today. IP traceback is one of the most effective techniques to defeat these attacks by identifying attack sources even in the presence of IP spoofing. Because of low marking packet utilization, the convergence time of traditional probabilistic packet marking (PPM) schemes is still too long. In order to shorten the convergence time, a distributed-log-based IP traceback scheme is proposed. Theoretical analysis and simulation results show that this scheme not only can converge more quickly than previous PPM schemes, but also has much less log overhead than other log-based schemes

Distributed denial-of-service attack is one of major threats to Internet today. Rate limit is an effective countermeasure to defeat rate-related attacks on condition that attackers send more traffics than legitimate users. However, sometimes the real case is opposite, because there may be only subtle rate difference between attackers and legitimate users today. We thoroughly investigate such a "meek" DDoS attack case and provide an elaborate IP traceback-based rate limit algorithm. The simulation results show that our method can better mitigate the meek DDoS attack as well as improve the throughput of legitimate traffic.