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.

Natural Language Interfaces for Databases em-power non-technical users to interact with data using natural language (NL). Advanced approaches, utilizing either neural sequence-to-sequence or more recent sophisticated large-scale language models, typically implement NL to SQL (NL2SQL) translation in an end-to-end fashion. However, like humans, these end-to-end translation models may not always generate the best SQL output on their first try. In this paper, we propose Cyclesql, an iterative framework designed for end-to-end translation models to autonomously generate the best output through self-evaluation. The main idea of CyClesqlis to introduce data-grounded NL explanations of query results as self-provided feedback, and use the feedback to validate the correctness of the translation iteratively, hence improving the overall translation accuracy. Extensive experiments, including quantitative and qualitative evaluations, are conducted to study Cyclesql by applying it to seven existing translation models on five widely used benchmarks. The results show that 1) the feedback loop introduced in Cyclesql can consistently improve the performance of existing models, and in particular, by applying Cyclesql to Resdsql, obtains a translation accuracy of 82.0% (+2.6 %) on the validation set, and 81.6 % (+3.2 %) on the test set of Spider benchmark; 2) the generated NL explanations can also provide insightful information for users, aiding in the comprehension of translation results and consequently enhancing the interpretability of NL2SQL translation11Our code is available at https://github.com/Kaimary/CycleSQL..

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.

Dirty data are prevalent in time series, such as energy consumption or stock data. Existing data cleaning algorithms present shortcomings in dirty data identification and unsatisfactory cleaning decisions. To handle these drawbacks, we leverage inherent recurrent patterns in time series, analogize them as fixed combinations in textual data, and incorporate the concept of perplexity. The cleaning problem is thus transformed to minimize the perplexity of the time series under a given cleaning cost, and we design a four-phase algorithmic framework to tackle this problem. To ensure the framework's feasibility, we also conduct a brief analysis of the impact of dirty data and devise an automatic budget selection strategy. Moreover, to make it more generic, we additionally introduce advanced solutions, including an ameliorative probability calculation method grounded in the homomorphic pattern aggregation and a greedy-based heuristic algorithm for resource savings. Experiments on 12 real-world datasets demonstrate the superiority of our methods.

As one of the most primitive operators in graph algorithms, such as the triangle counting, maximal clique enumeration, and subgraph listing, a set intersection operator returns common vertices between any two given sets of vertices in data graphs. It is therefore very important to accelerate the set intersection, which will benefit a bunch of tasks that take it as a built-in block. Existing works on the set intersection usually followed the merge intersection or galloping-search framework, and most optimization research focused on how to leverage the SIMD hardware instructions. In this paper, we propose a novel multi-level set intersection framework, namely hierarchical set partitioning and join (HERO), by using our well-designed set intersection bitmap tree (SIB-tree) index, which is independent of SIMD instructions and completely orthogonal to the merge intersection framework. We recursively decompose the set intersection task into small-sized subtasks and solve each subtask using bitmap and boolean AND operations. To sufficiently achieve the acceleration brought by our proposed intersection approach, we formulate a graph reordering problem, prove its NP-hardness, and then develop a heuristic algorithm to tackle this problem. Extensive experiments on real-world graphs have been conducted to confirm the efficiency and effectiveness of our HERO approach. The speedup over classic merge intersection achieves up to 188x and 176x for triangle counting and maximal clique enumeration, respectively.

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×.

Nowadays the demands for managing and analyzing substantially increasing collections of time series are becoming more challenging. Subsequence matching, as a core subroutine in time series analysis, has drawn significant research attention. Most of the previous works only focus on matching the subsequences with equal length to the query. However, many scenarios require support for efficient variable-length subsequence matching. In this paper, we propose a new representation, Uniform Piecewise Aggregate Approximation (UPAA) with the capability of aligning features for variable-length time series while remaining the lower bounding property. Based on UPAA, we present a compact index structure by grouping adjacent subsequences and similar subsequences respectively. Moreover, we propose an index pruning algorithm and a data filtering strategy to efficiently support variable-length subsequence matching without false dismissals. The experiments conducted on both real and synthetic datasets demonstrate that our approach achieves considerably better efficiency, scalability, and effectiveness than existing approaches.

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.

Towards building online analytical services on big heterogeneous graphs, we study the problem of the multithreading graph aggregation. The purpose is to exploit the thread-level parallelism for accelerating the graph aggregation process, which is both data and computation intensive. We identify the sources of parallelization latency caused by multifarious factors, including data distributions and contentions, uneven workload assignments, logical aggregation plan obstructions, etc. To cope with these problems, we investigate a parallelization solution for graph aggregation with a number of threads packaged as threadblocks, categorize the parallelization latency as the thread-level and threadblock-level latency, and propose a series of optimization techniques for alleviating or eliminating the latency on different levels. The solution supports different aggregate functions, scales up to large number of threads, and scales out to big heterogeneous graphs. Experiments on real datasets show that our solution achieves up to 60x acceleration with 256 threads compared to the non-parallelized solution.

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.

To make databases more accessible to a much broader audience of non-technical users, many applications, such as chatbots and search engines, have developed a natural language (NL) interface for the underlying databases (NLIDB). With the advances in machine learning techniques, most recent research employs language translation models to build NLIDB systems. In this demonstration, we introduce GenSql, a generative NLIDB system that enables users to query databases using NL. Unlike most existing NLIDB systems that attempt to leverage a generalized language translation model to convert NL to SQL queries (NL2SQL) for any database, GenSql utilizes a set of sample queries to capture the specific structure and semantics of a given database and thus to provide more accurate translation results. The underlying NL2SQL model in GenSql is a novel generate-and-rank model named Gar designed by the authors, which first generates a set of generalized SQL queries with corresponding NL expressions from the given sample queries, and ranks the NL expressions to get the best matching one, and hence the SQL query. This demonstration shows the effectiveness of GenSql, especially in answering complex queries, which proves its utility in practice.

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.

In the paper, we study the problem of computing a maximum quasi-independent set that admits$k$conflict edges at most but contains the set of query vertices$S$. It generalizes the task of finding a maximum independent set (shorted as MIS) for a given graph. Due to the intractable hardness of computing an exact solution, delivering a high-quality approximate solution within a time budget can be accepted. The existing algorithms for the maximum quasi-independent set are organized in two phases, namely near-MIS initialization and edge expansion (i.e., deleting edges). As both of the two phases adopt greedy strategies, error propagation degrades the quality of delivered answer sets. In contrast, we develop a novel pay-and-recycle approach interleaving the above two phases. Instead of making greedy peelings when no reduction rules can be applied, we delete an edge (i.e., edge expansion) to create opportunities for applying reduction rules. To enhance the performance, the wasted edges are detected and recycled for further expansion. Moreover, we propose an effective method to guide edge expansion based on offline samples. Extensive empirical studies show that our proposed method outperforms the state-of-the-art algorithm in finding larger quasi-independent sets.

We will demonstrate a prototype query-processing engine, which utilizes correlations among predicates to accelerate machine learning (ML) inference queries on unstructured data. Expensive operators such as feature extractors and classifiers are deployed as user-defined functions (UDFs), which are not penetrable by classic query optimization techniques such as predicate push-down. Recent optimization schemes (e.g., Probabilistic Predicates or PP) build a cheap proxy model for each predicate offline, and inject proxy models in the front of expensive ML UDFs under the independence assumption in queries. Input records that do not satisfy query predicates are filtered early by proxy models to bypass ML UDFs. But enforcing the independence assumption may result in sub-optimal plans. We use correlative proxy models to better exploit predicate correlations and accelerate ML queries. We will demonstrate our query optimizer called CORE, which builds proxy models online, allocates parameters to each model, and reorders them. We will also show end-to-end query processing with or without proxy models.

We consider accelerating machine learning (ML) inference queries on unstructured datasets. Expensive operators such as feature extractors and classifiers are deployed as user-defined functions (UDFs), which are not penetrable with classic query optimization techniques such as predicate push-down. Recent optimization schemes (e.g., Probabilistic Predicates or PP) assume independence among the query predicates, build a proxy model for each predicate offline, and rewrite a new query by injecting these cheap proxy models in the front of the expensive ML UDFs. In such a manner, unlikely inputs that do not satisfy query predicates are filtered early to bypass the ML UDFs. We show that enforcing the independence assumption in this context may result in sub-optimal plans. In this paper, we propose CORE, a query optimizer that better exploits the predicate correlations and accelerates ML inference queries. Our solution builds the proxy models online for a new query and leverages a branch-and-bound search process to reduce the building costs. Results on three real-world text, image and video datasets show that CORE improves the query throughput by up to 63% compared to PP and up to 80% compared to running the queries as it is.

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.

Urban traffic gridlock is a familiar scene. At the same time, the mean occupancy rate of personal vehicle trips in the United States is only 1.6 persons per vehicle mile. Ridesharing has the potential to solve many environmental, congestion, pollution, and energy problems. In this paper, we introduce the problem of large scale real-time ridesharing with service guarantee on road networks. Trip requests are dynamically matched to vehicles while trip waiting and service time constraints are satisfied. We first propose two scheduling algorithms: a branch-and-bound algorithm and an integer programing algorithm. However, these algorithms do not adapt well to the dynamic nature of the ridesharing problem. Thus, we propose kinetic tree algorithms which are better suited to efficient scheduling of dynamic requests and adjust routes on-the-fly. We perform experiments on a large Shanghai taxi dataset. Results show that the kinetic tree algorithms outperform other algorithms significantly.

A well-studied query type on moving objects is the continuous range query. An interesting and practical situation is that instead of being continuously evaluated, the query may be evaluated at different degrees of continuity, e.g. every 2 seconds (close to continuous), every 10 minutes or at irregular time intervals (close to snapshot). Furthermore, the range query may be stacked under predicates applied to the returned objects. An example is the count predicate that requires the number of objects in the range to be at least Y. The conjecture is that these two practical considerations can help reduce communication costs. We propose a safe region-based solution that exploits these two practical considerations. An extensive experimental study shows that our solution can reduce communication costs by a factor of 9.5 compared to an existing state-of-the-art system.

The term "indoor" here refers generally to enclosed space partitioned into subspaces with connecting doors or gates. Examples include the inside of office buildings, amusement parks, and indoor shopping malls. In many applications, it is desirable to keep track of the distribution of people within the enclosed space. These applications range from smart house with automatically controlled air-conditioning and lighting, shopping assistance allocation, to business intelligence. Contact sensors are accurate but obstructive. Non-contact sensors such as automated visual recognition and RFID tags can be expensive in calibration or cost in order to obtain accurate readings. An interesting cost optimization problem is to understand how to obtain relatively accurate dynamic distribution of people from inaccurate point sensors using correlations among the point sensor readings. The paper formalizes a framework that uses a flow model and a particle-filter learning algorithm for this optimization problem based on the hypotheses that (1) there is an underlying stochastic "flow model" of people moving within the space, and (2) with the help of this flow model, counting of people can be made more accurate by taking advantage of the continuous, albeit inaccurate, point sensor readings. The main challenge is that the performance of particle filters deteriorates rapidly with the number of doors in the indoor space. We propose a divide and conquer method that uses relatively more accurate sensors at a few strategically chosen locations to achieve overall good accuracy. Experimental results given herein show that the algorithm is effective.

Location information is necessarily uncertain when objects are constantly moving. The cost can be high to maintain precise locations at the application server for all the objects while many applications may not need all the costly precision that is technically possible. An interesting question is how to reduce the cost associated with obtaining precise locations while satisfying user requirements. A general technique of maintaining uncertain location information is using a “safe-region” for each object, a region in which the object must be in but it is not known where it exactly is. Location updates are only needed when the object moves out of its safe region, or a user query needs more precise information to answer. This paper uses the same idea for finding an object that is likely to be the nearest neighbor of a query location, a query type termed herein Probabilistic one-of Nearest Neighbor (PoNN) query. An algorithm is described that first tries to answer a given PoNN query with the known safe regions. If this fails, the algorithm selects some objects to ask for their precise locations (called location exposures). An innovative method is used by the algorithm in deciding which objects to expose in order to reduce the total number of exposures. The innovation includes an information gain formulation of the problem and careful probability calculations. The paper details the algorithm and shows an experimental study of the algorithm against more straightforward solutions in a simulated environment.

Spatial cloaking has been proposed and studied to protect mobile user privacy when using location based services (LBS). Traditional spatial cloaking methods are carried out by a trusted proxy known as location trusted server (LTS) to generate a region that contains at least k users for every request. The LTS is assumed to know the location of all users at all times, and perform the cloaking for all user requests. There are a number of disadvantages of relying on a single service for privacy preservation, including the scalability concern and the appropriate worry that this service “knows too much”. To ameliorate this single-service problem, in-device spatial cloaking may be more desirable. However, the sticky problem is that the device does not know, at the time of the request, the locations of all other users, which are necessary to obtain an appropriate cloaked region. With cloud services, it may be appropriate to assume that user-density information is available from cloud servers. These servers may collect user location information for different regions, or may use sophisticated method to estimate user densities for different places. When a request needs to be anonymized, the device goes to the cloud to acquire appropriate user density information to perform spatial cloaking. In this operating environment, traditional spatial cloaking methods such as Casper [9] need to be modified in order to guarantee safety. This paper proposes and studies a new algorithm and reports performance evaluation of the new algorithm and its optimized version, aiming at provably safe cloaking with minimized communication cost. Experimental results show that the new algorithms work well in the realistic evaluation environment.

Proximity based services are location based services (LBS) in which the service adaptation depends on the comparison between a given threshold value and the distance between a user and other (possibly moving) entities. While privacy preservation in LBS has lately received much attention, very limited work has been done on privacy-aware proximity based services. This paper describes the main privacy threats that the usage of these services can lead to, and proposes original privacy preservation techniques offering different trade-offs between quality of service and privacy preservation. The properties of the proposed algorithms are formally proved, and an extensive experimental work illustrates the practicality of the approach.

One of the privacy threats recognized in the use of LBS is represented by an adversary having information about the presence of individuals in certain locations, and using this information together with an (anonymous) LBS request to re-identify the issuer of the request associating her to the requested service. Several papers have proposed techniques to prevent this, assuming that the use of the service is considered sensitive. In this paper we investigate the more general case in which the adversary is also able to recognize traces of LBS requests by the same anonymous user, so that the identification of the issuer of one request can lead to the disclosure of the same user being in other possibly sensitive locations at different times or using sensitive services.Using the notion of "historical k-anonymity", this paper provides the first formalization of this class of privacy threats. Through extensive experiments based on realistic simulations, and runs of an optimal algorithm, we show some negative results for the defenses based on spatial generalization against these attacks under very conservative assumptions. Under more realistic location knowledge assumptions, we propose two defense algorithms, based on a strategy of changing and reusing of pseudo-identifiers, whose correctness is formally proved. Our experiments show that, among all the proposed algorithms, the ProvidentHider algorithm is particularly effective in protecting privacy for reasonably long sequences of requests.

Protecting privacy of mobile users of location-based services is a currently interesting research problem. Most protection techniques can be categorized into either those providing location privacy or those guaranteeing k-anonymity. A mobile user (i) has location privacy if, when he makes an LBS request, adversaries cannot tell his location precise enough to cause privacy concerns, and (ii) has k-anonymity if adversaries cannot distinguish him, among a group of k users, as the definite request issuer. SpaceTwist proposed recently is in the former category, but makes no attempt to provide k-anonymity. The purpose of this paper is to study a method that makes SpaceTwist provide k-anonymity in addition to location privacy. The extended algorithm is called AnonTwist. The major challenge is the ability to make sure that at least k users are in the privacy area given in the SpaceTwist algorithm, i.e., in the so-called "twisted space". AnonTwist contains two technical contributions. The first is a user density map in the form of a Quadtree so that we have an estimate of the number of users in each spatial area. The second is a nontrivial counting mechanism, over the density map, to keep track of the number of users in the twisted space. Comparison of AnonTwist and SpaceTwist is performed via an experimental evaluation. The results show that the performance of AnonTwist is comparable to that of SpaceTwist. With the additional advantage of providing k-anonymity, AnonTwist should be the more favorable algorithm to use in practice.

The demonstrated, high-level decisions query language DQL combines the decision optimization capability of mathematical programming and the data manipulation capability of traditional database query languages. DQL benefits application developers in two aspects. First, it avoids a conceptual impedance mismatch between mathematical programming and data access and makes decision optimization functionality readily accessible to database programmers with no prior experience in operations research. Second, a tight integration provides unique opportunities for more efficient evaluation as compared to a loosely coupled system. This demonstration uses an emergency response scenario to illustrate the power of the language and its implementation.

A general consensus is that the proliferation of location- aware devices will result in a diffusion of location-based services. Privacy preservation is a challenging research issue for this kind of service. A possible solution consists of ensuring users' anonymity, i.e., ensuring that the user issuing a request is indistinguishable, among a group of users, by any attacker who has access to the service requests. In this paper we propose a formal framework to model the problem of guaranteeing anonymity when requiring location-based services. The proposed framework extends existing approaches by allowing to model different kinds of knowledge that may be available to the attacker. We show application examples of our framework, modeling both known scenarios and new ones. From a practical point of view, the framework makes it possible to define anonymity-preserving techniques that best suite the system assumptions as derived from the applicative context, and the level of privacy protection defined by the user.

Reservoir sampling is a well-known technique for sequential random sampling over data streams. Conventional reservoir sampling assumes a fixed-size reservoir. There are situations, however, in which it is necessary and/or advantageous to adaptively adjust the size of a reservoir in the middle of sampling due to changes in data characteristics and/or application behavior. This paper studies adaptive size reservoir sampling over data streams considering two main factors: reservoir size and sample uniformity. First, the paper conducts a theoretical study on the effects of adjusting the size of a reservoir while sampling is in progress. The theoretical results show that such an adjustment may bring a negative impact on the probability of the sample being uniform (called uniformity confidence herein). Second, the paper presents a novel algorithm for maintaining the reservoir sample after the reservoir size is adjusted such that the resulting uniformity confidence exceeds a given threshold. Third, the paper extends the proposed algorithm to an adaptive multi-reservoir sampling algorithm for a practical application in which samples are collected from memory-limited wireless sensor networks using a mobile sink. Finally, the paper empirically examines the adaptivity of the multi-reservoir sampling algorithm with regard to reservoir size and sample uniformity using real sensor networks data sets.

In stream join processing with limited memory, uniform random sampling is useful for approximate query evaluation. In this paper, we address the problem of reservoir sampling over memory-limited stream joins. We present two sampling algorithms, reservoir join-sampling (RJS) and progressive reservoir join-sampling (PRJS). RJS is designed straightforwardly by using a fixed-size reservoir sampling on a join-sample (i.e., random sample of a join output stream). Anytime the sample in the reservoir is used, RJS always gives a uniform random sample of the original join output stream. With limited memory, however, the available memory may not be large enough even for the join buffer, thereby severely limiting the reservoir size. PRJS alleviates this problem by increasing the reservoir size during the join-sampling. This increasing is possible since the memory requirement by the join-sampling algorithm decreases over time. A larger reservoir provides a closer representation of the original join output stream. However, it comes with a negative impact on the probability of the sample being uniform. Through experiments we examine the tradeoffs and compare the two algorithms in terms of the aggregation error on the reservoir sample.

A stream classifier is a decision model that assigns a class label to a data stream, based on its arriving data. Various features of the stream can be used in the classifier, each of which may have different relevance to the classification task and different cost in obtaining its value. As time passes by, some less costly features may become more relevant, but the time needed for decision may be considered as a cost. A challenge is how to balance the different costs when building a cost-effective classifier. This paper proposes a new feature selection strategy that extends the traditional relief algorithm in two aspects: (1) estimate the classification cost associated with each feature, and (2) order all the features with a score that combines both cost estimation and classification relevance. A classifier is then built with the selected features using a traditional classification method. Experimental results show that classifiers constructed with this strategy are indeed cost effective.

In many applications, local or remote sensors send in streams of data, and the system needs to monitor the streams to discover relevant events/patterns and deliver instant reaction correspondingly. An important scenario is that the incoming stream is a continually appended time series, and the patterns are time series in a database. At each time when a new value arrives (called a time position), the system needs to find, from the database, the nearest or near neighbors of the incoming time series up to the time position. This paper attacks the problem by using fast Fourier transform (FFT) to efficiently find the cross correlations of time series, which yields, in a batch mode, the nearest and near neighbors of the incoming time series at many time positions. To take advantage of this batch processing in achieving fast response time, this paper uses prediction methods to predict future values. When the prediction length is long, FFT is used to compute the cross correlations of the predicted series (with the values that have already arrived) and the database patterns, and to obtain predicted distances between the incoming time series at many future time positions and the database patterns. If the prediction length is short, the direct computation method is used to obtain these predicted distances to avoid the overhead of using FFT. When the actual data value arrives, the prediction error together with the predicted distances is used to filter out patterns that are not possible to be the nearest or near neighbors, which provides fast responses. Experiments show that with reasonable prediction errors, the performance gain is significant. Especially, when the long term predictions are available, the proposed method can handle incoming data at a very fast streaming rate.

In many applications, it is important to quickly find, from a database of patterns, the nearest neighbors of high-dimensional query points that come into the system in a streaming form. Treating each query point as a separate one is inefficient. Consecutive query points are often neighbors in the high-dimensional space, and intermediate results in the processing of one query should help the processing of the next. This paper extends the KD tree with triangle inequality to deal with high-dimensional streaming time series. More specifically, the distances calculated for earlier query points (to patterns) are used to filter out patterns that are not possible to be the nearest neighbor of the current one. Experiments show that this extension works well.

An important investigation of moving objects involves searching for objects with specific movement patterns, such as "going up," "going towards southwest," or a combination of these. Movement patterns can be in various scales, and larger-scale patterns usually span over longer time periods with greater disturbances ignored. Movement pattern queries ask for moving objects which show a given movement pattern in a specific scale. This paper studies database techniques to support fast evaluation of movement pattern queries in user-specified scales. The database is assumed to contain position information of moving objects sampled at a certain time interval. A movement pattern is defined as a regular expression of movement letters where each letter describes a set of movement directions. For each series of positions, movement directions of all scales are precomputed and results are mapped into points on a plane. Points on this plane usually cluster well and can be readily bounded by trapezoids. These bounding trapezoids are then stored in a relational database and the query language SQL can be used to help evaluate movement pattern queries. This paper also reports some experiments conducted on a real data set as well as a synthesized data set. Results show that both the precomputation algorithm and the bounding strategy are efficient and scalable.

For many applications, it is important to quickly locate the nearest neighbor of a given time series. When the given time series is a streaming one, nearest neighbors may need to be found continuously at all time positions. Such a standing request is called a continuous nearest neighbor query. This paper seeks fast evaluation of continuous queries on large databases. The initial strategy is to use the result of one evaluation to restrict the search space for the next. A more fundamental idea is to extend the existing indexing methods, used in many traditional nearest neighbor algorithms, with pre-fetching. Specifically, pre-fetching is to predict the next value of the stream before it arrives, and to process the query as if the predicted value were the real one in order to load the needed index pages and time series into the allocated cache memory. Furthermore, if the pre-fetched candidates cannot fit into the cache memory, they are stored in a sequential file to facilitate fast access to them. Experiments show that pre-fetching improves the response time greatly over the direct use of traditional algorithms, even if the caching provided by the operating system is taken into consideration.

In many applications, local or remote sensors send in streams of data, and the system needs to monitor the streams to discover relevant events/patterns and deliver instant reaction correspondingly. An important scenario is that the incoming stream is a continually appended time series, and the patterns are time series in a database. At each time when a new value arrives (called a time position), the system needs to find, from the database, the nearest or near neighbors of the incoming time series up to the time position. This paper attacks the problem by using Fast Fourier Transform (FFT) to efficiently find the cross correlations of time series, which yields, in a batch mode, the nearest and near neighbors of the incoming time series at many time positions. To take advantage of this batch processing in achieving fast response time, this paper uses prediction methods to predict future values. FFT is used to compute the cross correlations of the predicted series (with the values that have already arrived) and the database patterns, and to obtain predicted distances between the incoming time series at many future time positions and the database patterns. When the actual data value arrives, the prediction error together with the predicted distances is used to filter out patterns that are not possible to be the nearest or near neighbors, which provides fast responses. Experiments show that with reasonable prediction errors, the performance gain is significant.

With explosively increasing volumes of remote sensing, modelling and other Earth science data available, and the popularity of the Internet, scientists are now facing challenges to publish and to find interesting data sets effectively and efficiently. Metadata has been recognized as a key technology to ease the searching and retrieval of Earth science data. In this paper, we discuss the DIMES (DIstributed MEtadata Server) prototype system. Designed to be flexible yet simple, DIMES uses XML to represent, store, retrieve and interoperate metadata in a distributed environment. DIMES accepts metadata in any well-formed XML format and thus assumes the "tree" semantics of metadata entries. Additional domain knowledge can be represented as specific links through XML's ID/IDREF mechanism. DIMES provides a number of mechanisms, including the "nearest-neighbor search", to navigate and to search metadata. Though started for the Earth science community, DIMES can be easily extended to serve scientific communities in other disciplines.

1. INTRODUCTION Searching for nearest neighbors among a large number of time series is an important data mining task in many application domains varying from economics to physics to experimental science in general. Time series are usually modeled as high-dimensional points and proximity of time series is often measured by some metric distance function on their corresponding points [12, 10, 4]. Depending on application needs, time series nearest neighbor searches may be classified into three categories: Whole series query Given a query series and a positive

Fast retrieval of time series in terms of their contents is important in many application domains. This paper studies database techniques supporting fast searches for time series whose contents are similar to what users specify. The content types studied include shapes, trends, cyclic components, autocorrelation functions and partial autocorrelation functions. Due to the complex nature of the similarity searches involving such contents, traditional database techniques usually cannot provide a fast response when the involved data volume is high. This paper proposes to answer such content-based queries using appropriate approximation techniques. The paper then introduces two specific approximation methods, one is wavelet based and the other line-fitting based. Finally, the paper reports some experiments conducted on a stock price data set as well as a synthesized random walk data set, and shows that both approximation methods significantly reduce the query processing time without introducing intolerable errors.

Illustrates a distributed system that provides online searching, analysis and ordering capabilities for distributed Earth science data. The system is under development by a consortium led by George Mason University in a project called Seasonal-to-Interannual Earth Science Information Partners (SIESIP) as a part of a federation of information partners funded by NASA. The integrated system is composed of data, a database management system (DBMS), communication protocols, data analysis tools and a user interface. Through a Web-based Java GUI, users can search the DBMS for metadata information, conduct content-based searches, perform some initial analyses and issue an order for the selected data.

An important investigation of time series involves searching for "movement" patterns, such as "going up" or "going down" or some combinations of them. Movement patterns can be in various scales: a large scale pattern may cover a long time period, while a small scale pattern usually covers a short time period. This paper considers such scale requirement. More specifically, a pattern is defined as a regular expression of letters, where each letter describes a movement direction and covers a specified length of time (called pattern unit length). To find if a time series (or a part of it) matches a pattern, the time series is first partitioned into consecutive sub-series of the unit length, and for each subseries, the direction of its best fitting line is taken as the movement direction of the sub-series if the distance between the best fitting line and the sub-series is within a specified tolerance (tolerance requirement). A direct implementation of pattern search will undoubtedly yield poor performance if the number of time series or the length of them is large. This paper introduces a pre-computation and indexing method to facilitate fast evaluation of pattern queries in user-specified scales. An efficient pre-computation algorithm is given to find the movement directions for all the sub-series that satisfy the tolerance requirement. Bounding triangles are used to represent clusters of sub-series. Relational database is then used to store these bounding triangles and relational operations are employed to facilitate the evaluation of pattern queries. The paper also reports some experiments performed on a real-life data set to show the efficiency and the scalability of the algorithms.

We address the implementation of a distributed data system designed to serve Earth system scientists. A consortium led by George Mason University has been funded by NASA's Working Prototype Earth Science Information Partner (WP-ESIP) program to develop, implement, and operate a distributed data and information system. The system will address the research needs of seasonal to interannual scientists whose research focus includes phenomena such as El Nino, monsoons and associated climate studies. The system implementation involves several institutions using a multitiered client-server architecture. Specifically the consortium involves an information system of three physical sites, GMU, the Center for Ocean-Land-Atmosphere Studies (COLA) and the Goddard Distributed Active Archive Center, distributing tasks in the areas of user services, access to data, archiving, and other aspects enabled by a low-cost, scalable information technology implementation. The project can serve as a model for a larger WP-ESIP Federation to assist in the overall data information system associated with future large Earth Observing System data sets and their distribution. The consortium has developed innovative information technology techniques such as content based browsing, data mining and associated component working prototypes; analysis tools particularly GrADS developed by COLA, the preferred analysis tool of the working seasonal to interannual communities; and a Java front-end query engine working prototype.

Remote sensing from space can provide global and continuous observations. The associated measurement data need to be stored and studied to understand the Earth system processes. The ability of interactive content-based browsing, i.e., browsing or searching the content to narrow-down the interesting portions of data sets prior to actually accessing or ordering full data sets, is highly desirable for any Earth science data information system. However the large volumes of archived and future Earth science remote sensing data are clearly a serious challenge for an interactive browsing process. In this paper a pyramid data model is introduced to support interactive content-based browsing and knowledge discovery for a wide variety of Earth science remote sensing data sets. By using multi-level precomputation and robust nonparametric approximation procedures, the interactive browsing performance can be enhanced greatly. An initial implementation and testing of this data model has been carried out through our research prototype system, Virtual Domain Application Data Center (VDADC). Future implementations are planned for our Seasonal to Interannual Earth Science Information Partner (SIESIP) project.

Data explicitly stored in a temporal database are often associated with certain semantic assumptions. Each assumption can be viewed as a way of deriving implicit information from explicitly stored data. Rather than leaving the task of deriving (possibly infinite) implicit data to application programs, as is the case currently, it is desirable that this be handled by the database management system. To achieve this, the paper formalizes and studies two types of semantic assumptions: point based and interval based. The point based assumptions include those assumptions that use interpolation methods over values at different time instants, while the interval based assumptions include those that involve the conversion of values across different time granularities. The paper presents techniques on: (1) how assumptions on specific sets of attributes can be automatically derived from the specification of interpolation and conversion functions; and (2) given the representation of assumptions, how a user query can be converted into a system query such that the answer of this system query over the explicit data is the same as that of the user query over the explicit and the implicit data. To precisely illustrate concepts and algorithms, the paper uses a logic based abstract query language. The paper also shows how the same concepts can be applied to concrete temporal query languages.

An important usage of time sequences is to discover temporal patterns. The discovery process usually starts with a user specified skeleton, called an event structure, which consists of a number of variables representing events and temporal constraints among these variables; the goal of the discovery is to find temporal patterns, i.e., instantiations of the variables in the structure that appear frequently in the time sequence. The paper introduces event structures that have temporal constraints with multiple granularities, defines the pattern discovery problem with these structures, and studies effective algorithms to solve it. The basic components of the algorithms include timed automata with granularities (TAGs) and a number of heuristics. The TAGs are for testing whether a specific temporal pattern, called a candidate complex event type, appears frequently in a time sequence. Since there are often a huge number of candidate event types for a usual event structure, heuristics are presented aiming at reducing the number of candidate event types and reducing the time spent by the TAGs testing whether a candidate type does appear frequently in the sequence. These heuristics exploit the information provided by explicit and implicit temporal constraints with granularity in the given event structure. The paper also gives the results of an experiment to show the effectiveness of the heuristics on a real data set.

The authors address the data access and analysis issues faced by interdisciplinary Earth scientists and graduate students as a prototypical domain community which will be accessing large data sets in Earth system science in the following decades. They present a working prototype developed at George Mason University to serve wide user needs termed Virtual Domain Application Data Center (VDADC). The VDADC prototype provides tools, data products and services tailored to users and can be extended to other domain communities. The VDADC operates in a distributed environment, the World Wide Web, and in close association with federated data centers. Moreover, the information technology implementation is driven by science scenarios and can apply to a variety of domain users, thus reducing network traffic the data centers by implementing intelligent data searching or "content-based browsing" prior to data ordering thus more effectively addressing user needs.

The purpose of good database logical design is to eliminate data redundancy and isertion and deletion anomalies. In order to achieve this objective for temporal databases, the notions of temporal types , which formalize time granularities, and temporal functional dependencies (TFDs) are intrduced. A temporal type is a monotonic mapping from ticks of time (represented by positive integers) to time sets (represented by subsets of reals) and is used to capture various standard and user-defined calendars. A TFD is a proper extension of the traditional functional dependency and takes the form X → μ Y, meaning that there is a unique value for Y during one tick of the temporal type μ for one particular X value. An axiomatization for TFDs is given. Because a finite set TFDs usually implies an infinite number of TFDs, we introduce the notion of and give an axiomatization for a finite closure to effectively capture a finite set of implied TFDs that are essential of the logical design. Temporal normalization procedures with respect to TFDs are given. Specifically, temporal Boyce-Codd normal form (TBCNF) that avoids all data redundancies due to TFDs, and temporal third normal form (T3NF) that allows dependency preservation, are defined. Both normal forms are proper extensions of their traditional counterparts, BCNF and 3NF. Decompositition algorithms are presented that give lossless TBCNF decompositions and lossless, dependency-preserving, T3NF decompositions.

A database application, called "on-line analytical processing" (or OLAP) and aimed at providing business intelligence through on-line multidimensional data analysis, has become increasingly important due to the existence of huge amounts of on-line data. This paper formalizes a multidimensional data (MDD) model for OLAP, and develops an algebraic query language called grouping algebra. The basic component of the MDD model is a multidimensional cube, consisting of a number of relations (called dimensions) and for each combination of tuples (called a coordinate), one from each dimension, there is an associated data value. Each dimension is viewed as a basic grouping, i.e., each tuple in the dimension corresponds to the group consisting of all the coordinates that contain this tuple. In order to express user queries, relational algebra expressions are then extended to those on basic groupings for obtaining complex groupings, including orderoriented groupings (for expressing, e.g., cumula...

) Claudio Bettini Dept. of Computer Science (DSI) University of Milan via Comelico 39, 20135 Milan, Italy [email protected] X. Sean Wang, Sushil Jajodia Dept. of Info.& Software Systems Eng. George Mason University Fairfax, VA 22030, USA fxywang, [email protected] Abstract An important usage of time sequences is for discovering temporal patterns of events (a special type of data mining). This process usually starts with the specification by the user of an event structure which consists of a number of variables representing events and temporal constraints among these variables. The goal of the data mining is to find temporal patterns, i.e., instantiations of the variables in the structure, which frequently appear in the time sequence. This paper introduces event structures that have temporal constraints with multiple granularities (TCGs). Testing the consistency of such structures is shown to be NP-hard. An approximate algorithm is then presented. The paper also introduces ...

A statistical query first manipulates source category data to build a target category in the form of a grouping relation and then performs statistical functions on the associated measurement data. In this paper, the attributes in a grouping relation are partitioned into pair-wise disjoint sets, each called a dimension. A grouping relation is said to be orthogonal if it is equal to the cross product of the projections of itself on all the dimensions. Orthogonality is useful in searching for and using pre-computed summaries on other categories. However, a grouping relation is sometimes not orthogonal, but rather k-partially orthogonal (i.e., the union of k orthogonal ones). It is shown that it is NP-complete to decide if a grouping relation is k-partially orthogonal. The paper then gives an algorithm to derive partial orthogonality. Also investigated in this paper are interval properties of grouping relations useful for optimizing statistical queries. An algorithm is described to derive interval properties.

This paper investigates algebraic query languages on temporal databases. The data model used is a multidimensional extension of the temporal modules introduced in [WJS95]. In a multidimensional temporal module, every non-temporal fact has a timestamp that is a set ofn-ary tuples of time points. A temporal module has a set of timestamped facts and has an associated temporal granularity (or temporal type), and a temporal database is a set of multidimensional temporal modules with possibly different temporal types. Temporal algebras are proposed on this database model. Example queries and results of the paper show that the algebras are rather expressive. The operations of the algebras are organized into two groups: snapshot-wise operations and timestamp operations. Snapshot-wise operations are extensions of the traditional relational algebra operations, while timestamp operations are extensions of first-order mappings from timestamps to timestamps. Multiple temporal types are only dealt with by these timestamp operations. Hierarchies of algebras are defined in terms of the dimensions of the temporal modules in the is used to denote all the algebra queries whose input, output and intermediate modules are of dimensions at mostm,nandk, respectively. (Most temporal algebras proposed intermediate results. The symbol TALG m;n k in the literature are in TALG 1;1 1.) Equivalent hierarchies TCALCm;n k are defined in a calculus query language that is formulated by using a first-order logic with linear order. The addition of aggregation functions into the algebras is also studied.

When querying a temporal database, a user often makes certain semantic assumptions on stored temporal data. This paper formalizes and studies two types of semantic assumptions: point-based and interval-baaed, The point-based assumptions include those assumptions that use interpolation methods, while the interval-based assumptions include those that involve different temporal types (time granularities). Each assumption is viewed as a way to derive certain implicit data from the explicit data stored in the database. The database system must use all explicit as well as (possibly infinite) implicit data to answer user queries. This paper introduces a new method to facilitate such query evaluations. A user query is translated into a system query such that the answer of this system query over the explicit data is the same as that of the user query over the explicit and the implicit data. The paper gives such a translation procedure and studies the properties (safety in particular) of user queries and system queries. 1

In a federated database environment, different constituents of the federation may use different temporal models or physical representations for temporal information. This paper introduces a new concept, called a temporal module, to resolve these differences, or mismatches, among the constituents. Intuitively, a temporal module hides the implementation details of a temporal relation by exposing its information only through two windowing functions: The first function associates each time point with a set of tuples and the second function links each tuple to a set of time points. A calculus-style language is given to form queries on temporal modules.

A family of sequence operations (rs-operations), based on pattern matching and including most of the “natural” operations on sequences, is introduced. In order to apply rs-operations to calculus-like query languages, a logic about sequences (SL) is defined by converting rs-operations to special predicates. To illustrate the applicability of our concepts to database queries, rs-operations and SL are used in an algebra and a calculus, respectively, over an extended relational data model containing sequences.