ShakeAlert is an earthquake early warning (EEW) system that detects significant earthquakes so quickly that alerts can reach many people before shaking arrives. The current ShakeAlert system has been developed incrementally over the past decade, following an old-fashioned system design. The system's tight coupling between physical sensors and data processing modules has made it difficult to expand new sensors, adopt novel networking technology advances, or change the system's behavior at runtime, thus hindering the system's extensibility, scalability, and reliability. To address these limitations, this paper proposes to expand the existing system design by adding a "digital twin" middleware layer as virtual representations of physical sensor stations, which provides a standardized software interface for running distributed data processing applications and conceals the hardware/software differences in physical sensors. These virtual stations are placed at the edge of the network near physical stations, acting as a middleware layer between sensors and the ShakeAlert system. By incorporating digital twins, we can leverage cutting-edge networking technologies (such as edge/fog computing) to improve scalability, accept trustworthy sensor data from diverse sources to enhance extensibility, and move data processing functions closer to the sensor stations to reduce response time during large earthquakes when network throughput is impacted. Ultimately, this will enhance the reliability of the ShakeAlert system and help keep communities safe during earthquakes.

Project-based learning (PjBL) has been increasingly adopted in computer science courses to improve students’ engagement and learning outcomes. Although a computer networks course is in great need of a PjBL course module, no such module is available due to the huge gap between PjBL’s design requirements and the current structure and content of the course. This paper introduces a novel PjBL module for a computer networks course, which challenges the students with a real world problem of developing the communication system for a smart lock. Following the PjBL design principles, we devise several scaffolding activities and assignments, which can be integrated into a semester-long computer networks course. We test ran the PjBL module in both undergraduate- and graduate-level computer networks courses. Our preliminary evaluation results show that the proposed PjBL module is well received by the students and helps improve their learning outcomes.

In recent years, we have witnessed an increasing demand to process big data in numerous applications. It is observed that there often exist substantial amounts of repetitive data in different portions of a big data repository/dataset for applications such as genome sequence analyses. In this paper, we present a novel method, called the VA-Store, to reduce the large space requirement for repetitive data in prevailing genome sequence analysis tasks using k-mers (i.e., subsequences of length k) with multiple k values. The VA-Store maintains a physical store for one portion of the input dataset (i.e., k0-mers) and supports multiple virtual stores for other portions of the dataset (i.e., k-mers with k ≠ k0). Utilizing important relationships among repetitive data, the VA-Store transforms a given query on a virtual store into one or more queries on the physical store for execution. Both precise and approximate transformations are considered. Accuracy estimation models for approximate solutions are derived. Query optimization strategies are suggested to improve query performance. Our experiments using real and synthetic datasets demonstrate that the VA-Store is quite promising in providing effective storage and efficient query processing for solving a kernel database problem on repetitive big data for genome sequence analysis applications.

Box queries on a dataset in a multidimensional data space are a type of query which specifies a set of allowed values for each dimension. Indexing a dataset in a multidimensional Non-ordered Discrete Data Space (NDDS) for supporting efficient box queries is becoming increasingly important in many application domains such as genome sequence analysis. The BoND-tree was recently introduced as an index structure specifically designed for box queries in an NDDS. Earlier work focused on developing strategies for building an effective BoND-tree to achieve high query performance. Developing efficient and effective techniques for deleting indexed vectors from the BoND-tree remains an open issue. In this paper, we present three deletion algorithms based on different underflow handling strategies in an NDDS. Our study shows that incorporating a new BoND-tree inspired heuristic can provide improved performance compared to the traditional underflow handling heuristics in NDDSs.

In the past, genome sequence databases had used main memory indexing, such as the suffix tree, for fast sequence searches. With next generation sequencing technologies, the amount of sequence data being generated is huge and main memory indexing is limited by the amount of memory available. K-mer based techniques are being more used for various genome sequence database applications such as local alignment. K-mer can also provide an excellent basis for creating efficient disk based indexing. In this paper, we have proposed a k-mer based database searching and local alignment tool using box queries on BoND-SD-tree indexing. BoND-tree is quite efficient for indexing and searching in Non-Ordered Discrete Data Space (NDDS). We have conducted experiments on searching DNA sequence databases using back translated protein query sequences and have compared with existing methods. We have also implemented local alignment of back translated protein query sequences with large DNA sequence databases using this index based k-mer search. Performances of this local alignment approach has been compared with that of Tblastn of NCBI. The results are quite promising and justify significance of the proposed approach.

In many applications, such as homeland security, image processing, social network, and bioinformatics, it is often required to support an approximate membership query (AMQ) to answer a question like “is an (query) object q near to at least one of the objects in the given data set Ω?” However, existing techniques for processing AMQs require a key parameter, i.e., the distance value, to be defined in advance for the query processing. In this paper, we propose a novel filter, called multi-granularity locality-sensitive Bloom filter (MLBF), which can process AMQs with multiple distance granularities. Specifically, the MLBF is composed of two Bloom filters (BF), one is called basic multi-granularity locality-sensitive BF (BMLBF), and the other is called multi-granularity verification BF (MVBF). The BMLBF is used to store the data objects. It adopts an alignable locality-sensitive hashing (LSH) function family to support multiple granularities. The MVBF is used to reduce the false positive rate of the MLBF. The false negative rate of the MLBF is reduced by applying AND-constructions followed by an OR-construction. In addition, based on the MLBF structure, we suggest a more spaceeffective variant, called the MLBF , to further reduce space cost. Theoretical analyses for estimating false positive/negative rates of the MLBF/MLBF are given. Experiments using synthetic and real data show that the theoretical estimates are quite accurate, and the MLBF/MLBF technique can handle AMQs with low false positive and negative rates for multiple distance granularities.

There is an increasing demand to efficiently process emerging types of queries, such as progressive queries (PQs), from contemporary database applications including telematics, e-commerce and social media. Unlike conventional queries, a PQ consists of a set of step-queries (SQ). A user formulates a new SQ on the fly based on the result(s) from the previous SQ(s). Existing database management systems were not designed to efficiently process such queries. In this paper, we present a novel technique to efficiently process a special type of PQ, called monotonic linear PQs, based on dynamically materialized views. The key idea is to create a superior relationship graph for SQs from historical PQs that can be used to estimate the benefit of keeping the current SQ result as a materialized view. The materialized views are used to improve the performance of future SQs. A new storage structure for the materialized views set is designed to facilitate efficient search for a usable view to answer a given SQ. Algorithms/strategies to efficiently construct a superior relationship graph, dynamically select materialized views, effectively manage the materialized views set and efficiently search for usable views are discussed. Experiment results demonstrate that our proposed technique is quite promising.

Bloom filters are widely-used powerful tools for processing set membership queries. However, they are not entirely suitable for many new applications, such as deleting one attribute value according to another attribute value for a set of data objects/items with two correlated attributes. In this paper, we introduce a concept for such an operation, called the associative deletion. To realize this operation, we propose a new Bloom filter data structure, named IABF (Improved Associative deletion Bloom Filter), which keeps the association information on the two correlated attributes of items in the given data set. Based on IABF, we present an algorithm to perform associative deletions, which can be applied to both normal data and streaming data. To further accelerate the operation, we also illustrate a hardware coprocessor implementation for a crucial component of the algorithm. Detailed theoretical analysis and experimental results demonstrate that the presented IABF technique can accurately process associative deletions with controlled false positive and negative rates.

Box queries (or window queries) are a type of query which specifies a set of allowed values in each dimension. Indexing feature vectors in the multidimensional Nonordered Discrete Data Spaces (NDDS) for efficient box queries are becoming increasingly important in many application domains such as genome sequence databases. Most of the existing work in this field targets the similarity queries (range queries and k-NN queries). Box queries, however, are fundamentally different from similarity queries. Hence, the same indexing schemes designed for similarity queries may not be efficient for box queries. In this paper, we present a new indexing structure specifically designed for box queries in the NDDS. Unique characteristics of the NDDS are exploited to develop new node splitting heuristics. For the BoND-tree, we also provide theoretical analysis to show the optimality of the proposed heuristics. Extensive experiments with synthetic data demonstrate that the proposed scheme is significantly more efficient than the existing ones when applied to support box queries in NDDSs. We also show effectiveness of the proposed scheme in a real-world application of primer design for genome sequence databases.

Numerous applications such as wireless communication and telematics need to keep track of evolution of spatio-temporal data for a limited past. Limited retention may even be required by regulations. In general, each data entry can have its own user specified lifetime. It is desired that expired entries are automatically removed by the system through some garbage collection mechanism. This kind of limited retention can be achieved by using a sliding window semantics similar to that from stream data processing. However, due to the large volume and relatively long lifetime of data in the aforementioned applications (in contrast to the real-time transient streaming data), the sliding window here needs to be maintained for data on disk rather than in memory. It is a new challenge to provide fast access to the information from the recent past and, at the same time, facilitate efficient deletion of the expired entries. In this paper, we propose a disk based, two-layered, sliding window indexing scheme for discretely moving spatio-temporal data. Our index can support efficient processing of standard time slice and interval queries and delete expired entries with almost no overhead. In existing historical spatio-temporal indexing techniques, deletion is either infeasible or very inefficient. Our sliding window based processing model can support both current and past entries, while many existing historical spatio-temporal indexing techniques cannot keep these two types of data together in the same index. Our experimental comparison with the best known historical index (i.e., the MV3R tree) for discretely moving spatio-temporal data shows that our index is about five times faster in terms of insertion time and comparable in terms of search performance. MV3R follows a partial persistency model, whereas our index can support very efficient deletion and update.

The increasing capabilities and decreasing cost of information and communication technologies (ICTs) are enabling new categories of vehicular telematics applications, such as wireless drive-through (WDT) services, in which an external service provider provides services to in-vehicle occupants via a wireless connection. Most telematics systems rely on proprietary protocols for data exchange between an in-vehicle client and its external counterpart in individual applications, making it difficult to share data-exchange methods among applications. Sharing data-exchange methods is important because it allows a rapid return on ICT investments. In this paper, we study the data-modeling issues for data exchange between an in-vehicle client and its service provider for WDT services. We present a novel data model that captures the main characteristics of data exchange for the WDT application family, using a formal mathematical representation and an intuitive graphical representation. We show that the proposed data model provides generality for such data exchange. In addition, we propose several optimization techniques based on the data model to minimize user interaction so that a good usability can be achieved. Our simulations and analysis demonstrate that the proposed data model and relevant optimization techniques are promising in supporting efficient WDT applications.

Recent legislation has increased the requirements of organizations to report data breaches, or unauthorized access to data. While access control policies are used to restrict access to a database, these policies are complex and difficult to configure. As a result, misconfigurations sometimes allow users access to unauthorized data. In this paper, we consider the problem of reporting data breaches after such a misconfiguration is detected. To locate past SQL queries that may have revealed unauthorized information, we introduce the novel idea of a misconfiguration response (MR) query . The MR-query cleanly addresses the challenges of information propagation within the database by replaying the log of operations and returning all logged queries for which the result has changed due to the misconfiguration. A strawman implementation of the MR-query would go back in time and replay all the operations that occurred in the interim, with the correct policy. However, re-executing all operations is inefficient. Instead, we develop techniques to improve reporting efficiency by reducing the number of operations that must be re-executed and reducing the cost of replaying the operations. An extensive evaluation shows that our method can reduce the total runtime by up to an order of magnitude.

Numerous techniques have been proposed in the past for supporting efficient k -nearest neighbor ( k -NN) queries in continuous data spaces. Limited work has been reported in the literature for k -NN queries in a nonordered discrete data space (NDDS). Performing k -NN queries in an NDDS raises new challenges. The Hamming distance is usually used to measure the distance between two vectors (objects) in an NDDS. Due to the coarse granularity of the Hamming distance, a k -NN query in an NDDS may lead to a high degree of nondeterminism for the query result. We propose a new distance measure, called Granularity-Enhanced Hamming (GEH) distance, which effectively reduces the number of candidate solutions for a query. We have also implemented k -NN queries using multidimensional database indexing in NDDSs. Further, we use the properties of our multidimensional NDDS index to derive the probability of encountering valid neighbors within specific regions of the index. This probability is used to develop a new search ordering heuristic. Our experiments on synthetic and genomic data sets demonstrate that our index-based k -NN algorithm is efficient in finding k -NNs in both uniform and nonuniform data sets in NDDSs and that our heuristics are effective in improving the performance of such queries.

Contemporary database applications often perform queries in hybrid data spaces (HDS) where vectors can have a mix of continuous valued and non-ordered discrete valued dimensions. To support efficient query processing for an HDS, a robust indexing method is required. Existing indexing techniques to process queries efficiently either apply to continuous data spaces (e.g., the R-tree) or non-ordered discrete data spaces (e.g., the ND-tree). No techniques directly indexing vectors in HDSs have been reported in the literature. In this paper, we propose a new multidimensional indexing technique, called the C-ND tree, to directly index vectors in an HDS. To build such an index, we first introduce some essential geometric concepts (e.g., hybrid bounding rectangle) in HDSs. The C-ND tree structure and the relevant tree building and query processing algorithms based on these geometric concepts in HDSs are then presented. Strategies have been suggested to make the values in continuous dimensions and non-ordered discrete dimensions comparable and controllable. Novel node splitting heuristics which exploit characteristics of both continuous and discrete dimensions are proposed. Performance of the C-ND tree is compared with that of linear scan, R*-tree and ND-tree using range queries on hybrid data. Experimental results demonstrate that the C-ND tree is quite promising in supporting range queries in HDSs.

As the Extensible Markup Language (XML) rapidly establishes itself as the de facto standard for presenting, storing, and exchanging data on the Internet, large volume of XML data and their supporting facilities start to surface. A fast and accurate selectivity estimation mechanism is of practical importance because selectivity estimation plays a fundamental role in XML query optimization. Recently proposed techniques are all based on some forms of structure synopses that could be time-consuming to build and not effective for summarizing complex structure relationships. In this research, we propose an innovative sampling method that can capture the tree structures and intricate relationships among nodes in a simple and effective way. The derived sample tree is stored as a synopsis for selectivity estimation. Extensive experimental results show that, in comparison with the state-of-the-art structure synopses, specifically the TreeSketch and Xseed synopses, our sample tree synopsis applies to a broader range of query types, requires several orders of magnitude less construction time, and generates estimates with considerably better precision for complex datasets.

The emergence of modern data-intensive applications requires sophisticated database techniques for processing advanced types of user queries on massive data. In this paper, we study such a new type of query, called progressive queries. A progressive query is defined as a set of inter-related and incrementally formulated step-queries. A step-query in a progressive query PQ is specified on the fly based on the results of previously-executed step-queries in PQ. Hence, a progressive query cannot be formulated in advance before its execution, which raises challenges for its processing and optimization. We introduce a query model to characterize different types of progressive queries. We then present a new index structure, called the collective index, to efficiently process progressive queries. The collective index technique incrementally evaluates step-queries via dynamically maintained member indexes. Utilizing the special structure of a collective index, the (member) indexes on the input relation(s) of a step-query are efficiently transformed into indexes on the result relation. Algorithms to efficiently process single-input (unary) linear and multiple-input (join) linear progressive queries based on the collective index are presented. Our experiment results show that the proposed collective index technique outperforms the conventional query processing methods in processing progressive queries.

A k-nearest neighbor (k-NN) query retrieves k objects from a database that are considered to be the closest to a given query point. Numerous techniques have been proposed in the past for supporting efficient k-NN searches in continuous data spaces. No such work has been reported in the literature for k-NN searches in a non-ordered discrete data space (NDDS). Performing k-NN searches in an NDDS raises new challenges. The Hamming distance is usually used to measure the distance between two vectors (objects) in an NDDS. Due to the coarse granularity of the Hamming distance, a k-NN query in an NDDS may lead to a large set of candidate solutions, creating a high degree of non-determinism for the query result. We propose a new distance measure, called granularity-enhanced Hamming (GEH) distance, that effectively reduces the number of candidate solutions for a query. We have also considered using multidimensional database indexing for implementing k-NN searches in NDDSs. Our experiments on synthetic and genomic data sets demonstrate that our index-based k-NN algorithm is effective and efficient in finding k-NNs in NDDSs.

Load shedding techniques generate approximate sliding window join results when memory constraints prevent exact computation. The previously proposed random load shedding method drops input tuples without consideration for the number of outputs created, while the recently proposed semantic load shedding technique aims to produce the largest possible result set. We consider a new model in which data stream tuples contain numerical importance values relevant to the query source and seek to maximize the importance of the approximate join result. We show that both random load shedding and semantic load shedding are sub-optimal in this situation, while the techniques presented in this paper satisfy the objective function by considering both tuple importance and join attribute distributions. We extend the existing offline semantic approximation technique to make it compatible with our objective function and show that it is less space and time efficient than our new optimal offline algorithm for small and large join memory allotments. We also introduce four efficient online algorithms, which are quite promising in maximizing the importance of the approximate join result without foreknowledge of input streams.

Similarity searches in multidimensional Non-ordered Discrete Data Spaces (NDDS) are becoming increasingly important for application areas such as bioinformatics, biometrics, data mining and E-commerce. Efficient similarity searches require robust indexing techniques. Unfortunately, existing indexing methods developed for multidimensional (ordered) Continuous Data Spaces (CDS) such as the R-tree cannot be directly applied to an NDDS. This is because some essential geometric concepts/properties such as the minimum bounding region and the area of a region in a CDS are no longer valid in an NDDS. Other indexing methods based on metric spaces such as the M-tree and the Slim-trees are too general to effectively utilize the special characteristics of NDDSs, resulting in nonoptimized performance. In this article, we propose a new dynamic data-partitioning-based indexing technique, called the ND-tree, to support efficient similarity searches in an NDDS. The key idea is to extend the relevant geometric concepts as well as some indexing strategies used in CDSs to NDDSs. Efficient algorithms for ND-tree construction and techniques to solve relevant issues such as handling dimensions with different alphabets in an NDDS are presented. Our experimental results on synthetic data and real genome sequence data demonstrate that the ND-tree outperforms the linear scan, the M-tree and the Slim-trees for similarity searches in multidimensional NDDSs. A theoretical model is also developed to predict the performance of the ND-tree for random data.

There is an increasing demand for similarity searches in a multidimensional non-ordered discrete data space (NDDS) from application areas such as bioinformatics and data mining. The non-ordered and discrete nature of an NDDS raises new challenges for developing efficient indexing methods for similarity searches. In this article, we propose a new indexing technique, called the NSP-tree , to support efficient similarity searches in an NDDS. As we know, overlap causes a performance degradation for indexing methods (e.g., the R-tree) for a continuous data space. In an NDDS, this problem is even worse due to the limited number of elements available on each dimension of an NDDS. The key idea of the NSP-tree is to use a novel discrete space-partitioning (SP) scheme to ensure no overlap at each level in the tree. A number of heuristics and strategies are incorporated into the tree construction algorithms to deal with the challenges for developing an SP-based index tree for an NDDS. Our experiments demonstrate that the NSP-tree is quite promising in supporting efficient similarity searches in NDDSs. We have compared the NSP-tree with the ND-tree, a data-partitioning-based indexing technique for NDDSs that was proposed recently, and the linear scan using different NDDSs. It was found that the search performance of the NSP-tree was better than those of both methods.

A database management system (DBMS) performs query optimization based on statistical information about data in the underlying database. Out-of-date statistics may lead to inefficient query processing in the system. The existing utility method, which collects statistics in batch mode, suffers from drawbacks such as heavy administrative burden, high system load and tardy updates. In this paper, we study approaches to performing statistical analysis on the fly during query execution, taking advantage of data already resident in main memory. We propose a framework for on-the-fly statistics collection, which we term piggybacking, and analyze the tradeoffs of piggybacking various statistics collection techniques on top of query execution plans. We present a multiple-granularity interleaving algorithm to integrate a set of piggyback operations with an execution plan, and show how the algorithm can be incorporated into an existing query optimizer. Our experiments demonstrate that useful statistics can be obtained via the piggyback method with a small overhead.

Selectivity estimation is an integral part of query optimization. In this paper, we propose a novel approach to approximate data density functions of relations and use them to estimate selectivities. A data density function here is approximated by a partial sum of an orthogonal series. Such approximate density functions can be derived easily, stored efficiently, and maintained dynamically. Experimental results show that our approach yields comparable or better estimation accuracy than the Wavelet and DCT methods, especially in the high dimensional spaces.

A major challenge for global query optimization in a multidatabase system (MDBS) is the lack of local cost information at the global level due to local autonomy. A number of methods to derive local cost models have been suggested recently. However, these methods are only suitable for a static multidatabase environment. In this paper, we propose a new multi-state query sampling method to develop local cost models for a dynamic environment. The system contention level at a dynamic local site is divided into a number of discrete contention states based on the cost of a probing query. To determine an appropriate set of contention states for a dynamic environment, two algorithms based on iterative uniform partitioning and data clustering, respectively, are introduced. A qualitative variable is used to indicate the contention states for the dynamic environment. The techniques from our previous (static) query sampling method, including query sampling, automatic variable selection, regression analysis and model validation, are extended so as to develop a cost model incorporating the qualitative variable for a dynamic environment. Experimental results demonstrate that this new multi-state query sampling method is quite promising in developing useful cost models for a dynamic multidatabase environment.

A multidatabase system (MDBS) integrates information from multiple pre-existing local databases. A major challenge for global query optimization in an MDBS is that some required local information about local database systems such as local cost models may not be available at the global level due to local autonomy. A feasible method to tackle this challenge is to group local queries on a local database system into classes and then use the costs of sample queries from each query class to derive a cost formula for the class via regression analysis. This paper discusses the issues on how to classify local queries so that a good cost formula can be derived for each query class. Two classification approaches, i.e. bottom-up and top-down, are suggested. The relationship between these two approaches is discussed. Classification rules that can be used in the approaches are identified. Problems regarding composition and redundancy of classification rules are studied. Classification algorithms are given. To test the membership of a query in a class, an efficient algorithm based on ranks is introduced. In addition, a hybrid classification approach that combines the bottom-up and top-down ones is also suggested. Experimental results demonstrate that the suggested query classification techniques can be used to derive good local cost formulas for global query optimization in an MDBS.

A crucial challenge for global query optimization in a multidatabase system (MDBS) is that some local optimization information, such as local cost parameters, may not be accurately known at the global level because of local autonomy. Traditional query optimization techniques using a crisp cost model may not be suitable for an MDBS because precise information is required. In this paper we present a new approach that performs global query optimization using a fuzzy cost model that allows fuzzy information. We suggest methods for establishing a fuzzy cost model and introduce a fuzzy optimization criterion that can be used with a fuzzy cost model. We discuss the relationship between the fuzzy optimization approach and the traditional (crisp) optimization approach and show that the former has a better chance to find a good execution strategy for a query in an MDBS environment, but its complexity may grow exponentially compared with the complexity of the later. To reduce the complexity, we suggest to use so-called k-approximate fuzzy values to approximate all fuzzy values during fuzzy query optimization. It is proven that the improved fuzzy approach has the same order of complexity as the crisp approach.

In a multidatabase system (MDBS), some query optimization information related to local database systems may not be available at the global level because of local autonomy. To perform global query optimization, a method is required to derive the necessary local information. This paper presents a new method that employs a query sampling technique to estimate the cost parameters of an autonomous local database system. We introduce a classification for grouping local queries and suggest a cost estimation formula for the queries in each class. We present a procedure to draw a sample of queries from each class and use the observed costs of sample queries to determine the cost parameters by multiple regression. Experimental results indicate that the method is quite promising for estimating the cost of local queries in an MDBS.>