Search

For the best results in quantitative polymerase chain reaction (qPCR) experiments, it is essential to design high-quality primers considering a multitude of constraints and the purpose of experiments. The constraints include many filtering constraints, homology test on a huge number of off-target sequences, the same constraints for batch design of primers, exon spanning, and avoiding single nucleotide polymorphism (SNP) sites. The target sequences are either in database or given as FASTA sequences, and the experiment is for amplifying either each target sequence with each corresponding primer pairs designed under the same constraints or all target sequences with a single pair of primers. Many websites have been proposed, but none of them including our previous MRPrimerW fulfilled all the above features. Here, we describe the MRPrimerW2, the update version of MRPrimerW, which fulfils all the features by maintaining the advantages of MRPrimerW in terms of the kinds and sizes of databases for valid primers and the number of search modes. To achieve it, we exploited GPU computation and a disk-based key-value store using PCIe SSD. The complete set of 3 509 244 680 valid primers of MRPrimerW2 covers 99% of nine important organisms in an exhaustive manner. Free access: http://MRPrimerW2.com

With advances in base technologies for moving objects, many studies have been conducted on the construction of databases of the trajectories of moving objects, including the diverse applications related to the trajectories. Most previous studies deal with whole trajectory matching, which finds the trajectories T in the database similar to a given query trajectory Q ‘as a whole.’ However, we often want to find those T containing the sub-trajectories $$T_{\mathrm{sub}} \, (\subseteq T)$$ that are similar to Q. This problem is known as sub-trajectory matching and is more complicated than whole trajectory matching since the query trajectory Q can be of any length and the matching sub-trajectories $$T_{\mathrm{sub}}$$ can be at any position in the data trajectories T. In this paper, we present a novel indexing-based sub-trajectory matching algorithm using multi-segment approximation. Our algorithm partitions a data trajectory into multiple component segments and then stores the individual segments in an index. The query trajectory is also partitioned into its component segments, and the search for similar segments for each query segment is efficiently performed using the index. The sub-trajectories similar to the query trajectory are reconstructed by our ‘stitching’ algorithm using the individual segments retrieved from the index. Our stitching algorithm is novel and innovative in the sense that it facilitates segment-wise partitioning and indexing of data trajectories. Without stitching, only trajectory-wise operations would be affordable, which causes severe storage space overhead and degradation in search performance. Our study is the first that uses indexing in sub-trajectory matching. We define a (multi-segment) trajectory similarity measure that extends a widely used single-segment similarity measure proposed by Lee et al. (in: Proceedings of ACM SIGMOD international conference on management of data (SIGMOD), 2007; in: Proceedings of IEEE international conference on data engineering (ICDE), 2008; Proc VLDB Endow (PVLDB) 1(1):1081–1094, 2008) by using the Hausdorff distance. We perform extensive experiments to compare our method with EDS (Xie, in: Proceedings of ACM SIGMOD international conference on management of data (SIGMOD), 2014), which has been proved to outperform all representative point-based measures in terms of accuracy and performance. The accuracy of our similarity measure is better than EDS by up to 52.0%, and our algorithm significantly outperforms that using EDS by up to 22,543 times. The performance of our algorithm is linearly scalable in the size of the database, which is an essential property for handling large-scale databases.

As a representative large-scale data management technology, Apache Hadoop is an open-source framework for processing a variety of data such as SNS, medical, weather, and IoT data. Hadoop largely consists of HDFS, MapReduce, and YARN. Among them, we focus on improving the HDFS metadata management scheme responsible for storing and managing big data. We note that the current HDFS incurs many problems in system utilization due to its file-based metadata management. To solve these problems, we propose a novel metadata management scheme based on RDBMS for improving the functional aspects of HDFS. Through analysis of the latest HDFS, we first present five problems caused by its metadata management and derive three requirements of robustness, availability, and scalability for resolving these problems. We then design an overall architecture of the advanced HDFS, A-HDFS, which satisfies these requirements. In particular, we define functional modules according to HDFS operations and also present the detailed design strategy for adding or modifying the individual components in the corresponding modules. Finally, through implementation of the proposed A-HDFS, we validate its correctness by experimental evaluation and also show that A-HDFS satisfies all the requirements. The proposed A-HDFS significantly enhances the HDFS metadata management scheme and, as a result, ensures that the entire system improves its stability, availability, and scalability. Thus, we can exploit the improved distributed file system based on A-HDFS for various fields and, in addition, we can expect more applications to be actively developed.

We propose two-dimensional indexing—a novel in-memory indexing architecture that operates over distributed memory of a massively-parallel search engine. The goal of two-dimensional indexing is to provide a one-integrated-memory view as in a single node system using one large integrated memory. In two-dimensional indexing, we partition the entire index into n× m fragments and distribute them over the memories of multiple nodes in such a way that each fragment is entirely stored in main memory of one node. The proposed architecture is not only scalable as it uses a scaled-out shared-nothing architecture but also is capable of achieving low query response time as it processes queries in main memory. We also propose the concept of the one-memory point, which is the amount of the memory space required to completely store the entire index in main memory providing a one-integrated-memory view. We first prove the effectiveness of two-dimensional indexing with single-keyword queries, and then, extend the notion so as to be able to handle multiple-keyword queries. To handle multiple-keyword queries, we adopt pre-join that materializes a multiple-keyword query a priori as well as a new notion of semi-memory join that obviates extensive communication overhead to perform join across multiple nodes. In experiments using the real-life search query set over a database consisting of 100 million Web documents crawled, we show that two-dimensional indexing can effectively provide a one-integrated-memory view without too much of additional memory compared with the single node system using one large integrated memory. We also show that, with a six-node prototype, in an ideal case, it significantly improves the query processing performance over a disk-based search engine with an equivalent amount of in-memory buffer but without two-dimensional indexing — by up to 535.54 times. This improvement is expected to get larger as the system is scaled-out with a larger number of machines.

In this paper, we define a new class of queries, the top-k multiple-type integrated query (simply, top-k MULTI query). It deals with multiple data types and finds the information in the order of relevance between the query and the object. Various data types such as spatial, textual, and relational data types can be used for the top-k MULTI query. The top-k MULTI query distinguishes itself from the traditional top-k query in that the component scores to calculate final scores are determined dependent of the query. Hence, each component score is calculated only when the query is given for each data type rather than being calculated apriori as in the top-k query. As a representative instance, the traditional top-k spatial keyword query is an instance of the top-k MULTI query. It deals with the spatial data type and text data type and finds the information based on spatial proximity and textual relevance between the query and the object, which is determined only when the query is given. In this paper, we first define the top-k MULTI query formally and define a new specific instance for the top-k MULTI query, the top-k spatial-keyword-relational(SKR) query, by integrating the relational data type into the traditional top-k spatial keyword query. Then, we investigate the processing approaches for the top-k MULTI query. We discuss the scalability of those approaches as new data types are integrated. We also devise the processing methods for the top-k SKR query. Finally, through extensive experiments on the top-k SKR query using real and synthetic data sets, we compare efficiency of the methods in terms of the query performance and storage.

After our paper was published on-line, the authors have learned existence of the paper by Feuerstein et al. [Feuerstein 2009].

There has been a lot of research on MapReduce for big data analytics. This new class of systems sacrifices DBMS functionality such as query languages, schemas, or indexes in order to maximize scalability and parallelism. However, as high functionality of the DBMS is considered important for big data analytics as well, there have been a lot of efforts to support DBMS functionality in MapReduce. HadoopDB is the only work that directly utilizes the DBMS for big data analytics in the MapReduce framework, taking advantage of both the DBMS and MapReduce. However, HadoopDB does not support sharability for the entire data since it stores the data into multiple nodes in a shared-nothing manner--i.e., it partitions a job into multiple tasks where each task is assigned to a fragment of data. Due to this limitation, HadoopDB cannot effectively process queries that require internode communication. That is, HadoopDB needs to re-load the entire data to process some queries (e.g., 2-way joins) or cannot support some complex queries (e.g., 3-way joins). In this paper, we propose a new notion of the DFS-integrated DBMS where a DBMS is tightly integrated with the distributed file system (DFS). By using the DFS-integrated DBMS, we can obtain sharability of the entire data. That is, a DBMS process in the system can access any data since multiple DBMSs are run on an integrated storage system in the DFS. To process big data analytics in parallel, our approach use the MapReduce framework on top of a DFS-integrated DBMS. We call this framework PARADISE. In PARADISE, we employ a job splitting method that logically splits a job based on the predicate in the integrated storage system. This contrasts with physical splitting in HadoopDB. We also propose the notion of locality mapping for further optimization of logical splitting. We show that PARADISE effectively overcomes the drawbacks of HadoopDB by identifying the following strengths. (1) It has a significantly faster (by up to 6.41 times) amortized query processing performance since it obviates the need to re-load data required in HadoopDB. (2) It supports query types more complex than the ones supported by HadoopDB.

A top-k spatial-keyword query returns the k best spatio-textual objects ranked based on their proximity to the query location and relevance to the query keywords. Various index schemes have been proposed for top-k spatial-keyword queries; however, a unified framework covering all these schemes has not been proposed. In this paper, we present a generic model of index schemes for top-k spatial-keyword queries, which we call G-Index Model. First, G-Index Model is a unified framework that exhaustively investigates all the possible index schemes for top-k spatial-keyword queries. For this, we conjecture that data clustering is the key element in composing various index schemes and generate index schemes as combinations of clustering. The result shows that all the existing methods map to those generated by G-Index Model. Using G-Index Model, we also discover two new methods that have not been reported before. Second, we show that G-Index Model is generic, i.e., it can generate index schemes for a class of queries integrating arbitrary multiple data types. For this, we show that G-Index Model can enumerate index schemes for two classes of queries: the spatial-keyword query (without the top-k constraint) and the top-k spatial-keyword-relational query, which adds the relational data type to the top-k spatial-keyword query. Third, we propose a cost model of the generated methods for the top-k spatial-keyword query. Consequently, the cost model allows us to do physical database design so as to find an optimal index scheme for a given usage pattern (i.e., a set of query loads and frequencies). We validate the cost model through extensive experiments.

As many recent applications require integration of structured data and text data, unifying database (DB) and information retrieval (IR) technologies has become one of major challenges in our field. There have been active discussions on the system architecture for DB-IR integration, but a clear agreement has not been reached yet. Along this direction, we have advocated the use of the tight-coupling architecture and developed a novel structure of the IR index as well as tightly-coupled query processing algorithms. In tight-coupling, the text data type is supported from the storage system just like a built-in data type so that the query processor can efficiently handle queries involving both structured data and text data. In this paper, for archival purposes, we consolidate our achievements reported at non-regular publications over the last ten years or so, extending them by adding greater details on the IR index and the query processing algorithms. All the features in this paper are fully implemented in the Odysseus DBMS that has been under development at KAIST for over 23 years. We show that Odysseus significantly outperforms two open-source DBMSs and one open-source search engine (with some exceptional cases) in processing DB-IR integration queries. These results indeed demonstrate superiority of the tight-coupling architecture for DB-IR integration.

A top-k spatial keyword query returns k objects having the highest (or lowest) scores with regard to spatial proximity as well as text relevancy. Approaches for answering top-k spatial keyword queries can be classified into two categories: the separate index approach and the hybrid index approach. The separate index approach maintains the spatial index and the text index independently and can accommodate new data types. However, it is difficult to support top-k pruning and merging efficiently at the same time since it requires two different orders for clustering the objects: the first based on scores for top-k pruning and the second based on object IDs for efficient merging. In this paper, we propose a new separate index method called Rank-Aware Separate Index Method (RASIM) for top-k spatial keyword queries. RASIM supports both top-k pruning and efficient merging at the same time by clustering each separate index in two different orders through the partitioning technique. Specifically, RASIM partitions the set of objects in each index into rank-aware (RA) groups that contain the objects with similar scores and applies the first order to these groups according to their scores and the second order to the objects within each group according to their object IDs. Based on the RA groups, we propose two query processing algorithms: (i) External Threshold Algorithm (External TA) that supports top-k pruning in the unit of RA groups and (ii) Generalized External TA that enhances the performance of External TA by exploiting special properties of the RA groups. RASIM is the first research work that supports top-k pruning based on the separate index approach. Naturally, it keeps the advantages of the separate index approach. In addition, in terms of storage and query processing time, RASIM is more efficient than the IR-tree method, which is the prevailing method to support top-k pruning to date and is based on the hybrid index approach. Experimental results show that, compared with the IR-tree method, the index size of RASIM is reduced by up to 1.85 times, and the query performance is improved by up to 3.22 times.

Since recent applications such as XML applications, Geographical Information Systems (GIS), and CAD/CAM systems require highly efficient data management, they are built on Object-Relational DBMS (ORDBMS). The applications are called navigational applications, and they navigate the composite objects connected via the reference and the collection attributes in the ORDBMS. When a navigational application accesses an object, it first checks whether the object is stored in the object cache. If not, the object must be fetched from the database in the server, which is a costly operation. Prefetching identifies the objects that are most likely to be accessed in the near future by the navigational applications and stores them in the object cache in advance. Since prefetching reduces the number of object fetches, it is crucial for improving the application performance. However, the experimental result by Han et al. [16] showed that the improvement ratio of application performance is much lower than the reduction ratio of the number of object fetches. In this paper, we claim that the number of disk accesses in the server also considerably affects the application performance, and we propose a technique for minimizing disk accesses to improve the performance of the prefetch method by Han et al. [16] and hence the navigational application. The contributions of this paper are summarized as follows. (1) For the iterative and the recursive patterns, we propose methods for creating materialized views based on the type-level path access logs proposed in [15]. We refer to the materialized views as the type-level access pattern views. (2) We then present the algorithms for minimizing the number of disk accesses using the type-level access pattern views when prefetching the objects from the database in the server. (3) We present an implementation technique that, given a prefetch request from the client, quickly finds the most efficient type-level access pattern view. (4) We perform a series of experiments using a variety of databases to show that the proposed technique significantly improves the overall performance of the navigational application. Experimental result shows that we reduce the number of disk accesses by up to 33.0 times and improve the performance by up to 21.4 times.

Advancement in mobile computing technologies has prompted strong needs for database systems that can be used in small devices such as sensors, cellular phones, PDAs, car navigators, and Ultra Mobile PCs (UMPCs). We term the database systems that are customizable for small computing devices as Ubiquitous Database Management Systems (UDBMSs). In this paper, we first review the requirements of the UDBMS. The requirements identified include lightweight DBMSs, selective convergence, flash-optimized storage systems, data synchronization, support of unstructured/semistructured data, complex database operations, selfmanagement, and security. Next, we review existing systems and research prototypes. We review the functionality of UDBMSs including the footprint size, support of standard SQL, transaction management, concurrency control, recovery, indexing, and access control. We then review the supportability of the requirements by those UDBMSs surveyed. We finally present research issues related to the UDBMS.

Due to wide use of XPath, the problem of efficiently processing XPath queries has recently received a lot of attention. In particular, a considerable effort has been devoted to minimizing XPath queries since the efficiency of query processing greatly depends on the size of the query. Research work in this area can be classified into two categories: constraint-independent minimization and constraint-dependent minimization. The former minimizes queries in the absence of integrity constraints while the latter in the presence of them. For a linear path query, which is an XPath query without branching predicates, existing constraint-independent minimization methods are generally known to be unable to minimize the query without processing the query itself. Most recently, however, by using the DataGuide, a representative structural summary of XML data, a constraint-independent method that minimizes linear path queries in a top-down fashion has been proposed. Nevertheless, this method can fail to find a minimal query since it minimizes a query by merely erasing labels from the original query whereas a minimal query could include labels that are not present in the original query. In this paper, we propose a bottom-up approach called XMin that guarantees finding a minimal query for a given tree pattern query by using the DataGuide without processing the query itself. For the linear path query, we first show that the sequence of labels occurring in the minimal query is a subsequence of every schema label sequence that matches the original query. Here, the schema label sequence for a node is the sequence of labels from the root of XML data to the node. We then propose iterative subsequence generation that iteratively generates subsequences from the shortest schema label sequence matching the original query in a bottom-up fashion and tests query equivalence. Using iterative subsequence generation, we can always find a minimal query and we formally prove this guarantee. We also propose an extended algorithm that guarantees the minimality for the tree pattern query, which is a linear path query with branching predicates. These methods have been prototyped in a full-fledged object-relational DBMS. The experimental results using real and synthetic data sets show the practicality of our method.

A top-k query returns k tuples with the highest (or the lowest) scores from a relation. The score is computed by combining the values of one or more attributes. We focus on top-k queries having monotone linear score functions. Layer-based methods are well-known techniques for top-k query processing. These methods construct a database as a single list of layers. Here, the ith layer has the tuples that can be the top-i tuple. Thus, these methods answer top-k queries by reading at most k layers. Query performance, however, is poor when the number of tuples in each layer (simply, the layer size) is large. In this paper, we propose a new layer-ordering method, called the Partitioned-Layer Index (simply, the PL Index), that significantly improves query performance by reducing the layer size. The PL Index uses the notion of partitioning, which constructs a database as multiple sublayer lists instead of a single layer list subsequently reducing the layer size. The PL Index also uses the convex skyline, which is a subset of the skyline, to construct a sublayer to further reduce the layer size. The PL Index has the following desired properties. The query performance of the PL Index is quite insensitive to the weights of attributes (called the preference vector) of the score function and is approximately linear in the value of k. The PL Index is capable of tuning query performance for the most frequently used value of k by controlling the number of sublayer lists. Experimental results using synthetic and real data sets show that the query performance of the PL Index significantly outperforms existing methods except for small values of k (say, k=

We propose a new similar sequence matching method that efficiently supports variable-length and variable-tolerance continuous query sequences on time-series data stream. Earlier methods do not support variable lengths or variable tolerances adequately for continuous query sequences if there are too many query sequences registered to handle in main memory. To support variable-length query sequences, we use the window construction mechanism that divides long sequences into smaller windows for indexing and searching the sequences. To support variable-tolerance query sequences, we present a new notion of intervaled sequences whose individual entries are an interval of real numbers rather than a real number itself. We also propose a new similar sequence matching method based on these notions, and then, formally prove correctness of the method. In addition, we show that our method has the prematching characteristic, which finds future candidates of similar sequences in advance. Experimental results show that our method outperforms the naive one by 2.6-102.1 times and the existing methods in the literature by 1.4-9.8 times over the entire ranges of parameters tested when the query selectivities are low (

We present a new method for computing temporal aggregation that uses a multidimensional index. The novelty of our method lies in mapping the start time and end time of a temporal tuple to a data point in a two-dimensional space, which is stored in a two-dimensional index, and in calculating the temporal aggregates through a temporal join between the data in the index and the base intervals (defined as the intervals delimited by the start times or end times of the tuples). To enhance the performance, this method calculates the aggregates by incrementally modifying the aggregates from that of the previous base interval without re-reading all tuples for the current base interval. We have compared our method with the SB-tree, which is the state-of-the-art method for temporal aggregation. The results show that our method is an order of magnitude more efficient than the SB-tree method in an environment with frequent updates, while comparable in a read-only environment as the number of aggregates calculated in a query increases.

Dissemination of XML data on the internet could breach the privacy of data providers unless access to the disseminated XML data is carefully controlled. Recently, the methods using encryption have been proposed for such access control. However, in these methods, the performance of processing queries has not been addressed. A query processor cannot identify the contents of encrypted XML data unless the data are decrypted. This limitation incurs overhead of decrypting the parts of the XML data that would not contribute to the query result. In this paper, we propose the notion of Query-Aware Decryption for efficient processing of queries against encrypted XML data. Query-Aware Decryption allows us to decrypt only those parts that would contribute to the query result. For this purpose, we disseminate an encrypted XML index along with the encrypted XML data. This index, when decrypted, informs us where the query results are located in the encrypted XML data, thus preventing unnecessary decryption for other parts of the data. Since the size of this index is much smaller than that of the encrypted XML data, the cost of decrypting this index is negligible compared with that for unnecessary decryption of the data itself. The experimental results show that our method improves the performance of query processing by up to six times compared with those of existing methods. Finally, we formally prove that dissemination of the encrypted XML index does not compromise security.

We propose XIR-Linear, a method for efficiently evaluating linear path expressions (LPEs) on large-scale heterogeneous XML documents using information retrieval (IR) techniques. LPEs are the primary form of XPath queries, and their evaluation techniques have been researched actively. XPath queries in their general form are partial match queries, and these queries are particularly useful for searching documents of heterogeneous schemas. Thus, XIR-Linear is geared for partial match queries expressed as LPEs. XIR-Linear has its basis on existing methods using relational tables (e.g., XRel, XParent), and drastically improves their efficiency using the inverted index technique. Specifically, it indexes the labels in label paths (i.e., sequences of node labels) like keywords in texts, and finds the label paths matching the LPE far more efficiently than string match used in the existing methods. We demonstrate the efficiency of XIR-Linear by comparing it with XRel and XParent using XML documents crawled from the Internet. The results show that XIR-Linear outperforms XRel and XParent by an order of magnitude with the performance gap widening as database size grows.

Partial rollback mechanism has been widely supported by many database management systems (DBMSs). It allows a transaction to be rolled back partially, that is, only back to a certain savepoint set by the user. A partial rollback, however, makes the DBMS buffer management complicated because it requires the DBMS to restore the state of not only the database but also the buffers. There are several literatures addressing such a partial rollback in a relational DBMS (RDBMS), which has page buffer only. However, to our knowledge, there exists no literature addressing it in an object-oriented/relational DBMS (OO/ORDBMS). The RDBMS partial rollback scheme cannot be applied to OO/ORDBMSs directly. The reason is that, unlike RDBMSs, many OO/ORDBMSs use dual buffer which consists of object buffer and page buffer. In this paper, we thoroughly study the partial rollback schemes for OO/ORDBMSs with dual buffer. For this, we propose four different partial rollback schemes which are based on (single) page buffer, (single) object buffer, dual buffer using a soft log, and dual buffer using shadows, respectively. The schemes proposed are practical enough to be implemented in a real OO/ORDBMS. The results of performance evaluations show that the dual buffer-based scheme using shadows achieves the best performance.

A transform-space index indexes spatial objects represented as points in the transform space. An advantage of a transform-space index is that optimization of spatial join algorithms using these indexes can be more formal. The authors earlier proposed the Transform-Based Spatial Join algorithm that joins two transform-space indexes. It renders global optimization easy with little overhead by utilizing the characteristics of the transform space. In particular, it allows us to globally determine the order of accessing disk pages, which makes a significant impact on the performance of joins. For this purpose, we use various space filling curves. In this paper, we propose a new space filling curve called the adaptive row major order (ARM order). The ARM order adaptively controls the order of accessing pages and significantly reduces the one-pass buffer size (the minimum buffer size required for guaranteeing one disk access per page) and the number of disk accesses for a given buffer size. Through analysis and experiments, we verify excellence of the ARM order when used with the Transform-Based Spatial Join. The Transform-Based Spatial Join with the ARM order always outperforms those with other conventional space filling curves in terms of both measures used: the one-pass buffer size and the number of disk accesses. Specifically, it reduces the one-pass buffer size by up to 25.9 times and the number of disk accesses by up to 2.11 times. We conclude that we achieve these results mainly due to global optimization of the order of accessing disk pages using an adaptive space filling curve.

Since database management systems(DBMSs) have limited lock resources, transactions requesting locks beyond the limit must be aborted, degrading the performance abruptly. Lock escalation is considered a solution to this problem. However, existing lock escalation methods have been designed in an ad hoc manner. So, they do not provide a complete solution. In this paper, we propose a formal model of lock escalation. Using the model, we analyze the roles of lock escalation formally and solve the problems of the existing methods systematically. In particular, we introduce the concept of the unescalatable lock that cannot be escalated due to conflicts. We identify that the unescalatable lock is the major cause of exhausting lock resources. We then analyze the reasons why unescalatable locks are generated and propose a new lock escalation method, adaptive lock escalation, which controls lock escalation based on the number of unescalatable locks. Through extensive simulation, we show that adaptive lock escalation significantly outperforms existing methods reducing the number of aborts and the average response time and increasing the throughput to a great extent. Adaptive lock escalation drastically reduces (more than 10 fold) the number of lock resources required to maintain the same level of throughput and average response time. At the same time, the throughput and average response time when using adaptive lock escalation are rather insensitive to the number of lock resources. Existing methods rely on users to estimate this number accurately at system initialization time. Adaptive lock escalation greatly alleviates this burden.

Clustering on large databases has been studied actively as an increasing number of applications involve huge amount of data. In this paper, we propose an efficient top-down approach for density-based clustering, which is based on the density information stored in index codes of a multidimensional index. We first provide a formal definition of the cluster based on the concept of region contrast partition. Based on this notion, we propose a novel top-down clustering algorithm, which improves the efficiency through branch-and-bourd pruning. For this pruning, we present a technique for determining the bounds based on sparse and dense internal regions and formally prove the correctness of the bounds. Experimental results show that the proposed method reduces the elapsed time by up to 96 times compared with that of BIRCH, which is a well-known clustering method. The results also show that the performance improvement becomes more marked as the size of the database increases.

In prefetching, the objects that are expected to be accessed in the future are fetched from the server to the client in advance. Prefetching reduces the number of round-trips and increases the system performance. To prefetch object effectively, we need to correctly predict the future navigational patterns. In this paper, we propose the PrefetchGuide , a novel data structure that captures the navigational access patterns. We also formally define the notion of the attribute access log set and analyze the navigational access patterns that can be captured by the PrefetchGuide. We then present an prefetching algorithm using the PrefetchGuide. To show effectiveness of our algorithm, we have conducted extensive experiments in a prototype object-relational database management systems (DBMS). The results show that our method significantly outperforms the state-of-the-art prefetching method. These results indicate that our approach provides a practical method that can be implemented in commercial object-oriented/object-relational DBMSs. We believe our method is practically usable for object-oriented programmers and DBMS implementors.

Aggregation is an operation that plays a key role in multidimensional OLAP (MOLAP). Existing aggregation methods in MOLAP have been proposed for file structures such as multidimensional arrays. These file structures are suitable for data with uniform distributions, but do not work well with skewed distributions. In this paper, we consider an aggregation method that uses dynamic multidimensional files adapting to skewed distributions. In these multidimensional files, the sizes of page regions vary according to the data density in these regions, and the pages that belong to a larger region are accessed multiple times while computing aggregations. To solve this problem, we first present an aggregation computation model that uses the new notions of disjoint-inclusive partition and induced space filling curves . Based on this model, we then present a dynamic aggregation algorithm. Using these notions, the algorithm allows us to maximize the effectiveness of the buffer--we control the page access order in such a way that a page being accessed can reside in the buffer until the next access. We have conducted experiments to show the effectiveness of our approach. Experimental results for a real data set show that the algorithm reduces the number of disk accesses by up to 5.09 times compared with a naive algorithm. The results further show that the algorithm achieves a near optimal performance (i.e., normalized I/O = 1.01) with the total main memory (needed for the buffer and the result table) less than 1.0% of the database size. We believe our work also provides an excellent formal basis for investigating further issues in computing aggregations in MOLAP.

Spatial access methods (SAMs) are often used as clustering indexes in spatial database systems. Therefore, a SAM should have the clustering property both in the index and in the data file. In this paper, we argue that corner transformation preserves the clustering property such that objects having similar sizes and positions in the original space tend to be placed in the same region in the transform space. We then show that SAMs based on corner transformation are able to maintain clustering both in the index and in the data file for storage systems with fixed object positions and propose the MBR-MLGF as an example to implement such an index. In the storage systems with fixed object positions, the inserted objects never move during the operation of the system. Most storage systems currently available adopt this architecture. Extensive experiments comparing with the R∗-tree show that corner transformation indeed preserves the clustering property, and therefore, it can be used as a useful method for spatial query processing. This result reverses the common belief that transformation will adversely affect the clustering and shows that the transformation maintains as good clustering in the transform space as conventional techniques, such as the R∗-tree, do in the original space.

Many object-oriented database systems manage object buffers to provide fast access to objects. Traditional buffer replacement algorithms based on fixed-length pages simply assume that the cost incurred by operating a buffer is proportional to the number of buffer faults. However, this assumption no longer holds in an object buffer where objects are of variable-lengths and the cost of replacing an object varies for each object. In this paper, we propose a cost-based replacement algorithm for object buffers. The proposed algorithm replaces the objects that have minimum costs per unit time and unit space. The cost model extends the previous page-based one to include the replacement costs and the sizes of objects. The performance tests show that the proposed algorithm is almost always superior to the LRU-2 algorithm and, when significant replacement cost is involved, is more than twice as fast.

Interactive multimedia applications require short initial latency. Initial latency increases as the buffer size allocated to each user request increases. Hence, the buffer size must be minimized. This paper proposes a buffer allocation scheme (DyBASe) that dynamically allocates the minimum buffer size to user requests based on the number of user requests in service. Through analysis and simulation, we show that DyBASe reduces the average initial latency by 31–65% compared with the existing static one.

In this paper, we propose a new subsequence matching method, Dual Match. Dual Match exploits duality in constructing windows and significantly improves performance. Dual Match divides data sequences into disjoint windows and the query sequence into sliding windows, and thus, is a dual approach of the one by Faloutsos et al. (Proceedings of the ACM SIGMOD International Conference on Management of Data, Seattle, Washington, 1994, pp. 419–429.) (FRM in short), which divides data sequences into sliding windows and the query sequence into disjoint windows. FRM causes a lot of false alarms (i.e., candidates that do not qualify) by storing minimum bounding rectangles rather than individual points representing windows to save storage space for the index. Dual Match solves this problem by directly storing points without incurring excessive storage overhead. Experimental results show that, in most cases, Dual Match provides large improvement both in false alarms and performance over FRM given the same amount of storage space. In particular, for low selectivities (less than 10−4), Dual Match significantly improves performance up to 430-fold. On the other hand, for high selectivities (more than 10−2), it shows a very minor degradation (less than 29%). For selectivities in between (10−4–10−2), Dual Match shows performance slightly better than that of FRM. Overall, these results indicate that our approach provides a new paradigm in subsequence matching that improves performance significantly in large database applications.

This paper presents a tunable two-dimensional class hierarchy indexing technique (2D-CHI) for object-oriented databases. We use a two-dimensional file organization as the index structure. 2D-CHI deals with the problem of clustering objects in a two-dimensional domain space consisting of the key attribute domain and the class identifier domain. In conventional class indexing techniques using one-dimensional index structures such as the B+-tree, the clustering property is owned exclusively by one attribute. These indexing techniques do not handle the queries that address both the attribute keys and the class identifiers efficiently. 2D-CHI enhances query performance by adjusting the degree of clustering between the key value domain and the class identifier domain based on the precollected usage pattern. For performance evaluation, we first compare 2D-CHI with the conventional class indexing techniques using an analytic cost model based on the assumption of uniform object distribution, and then, verify the cost model through experiments using the multilevel grid file as the two-dimensional index. We further perform experiments with nonuniform object distributions. The experiments show that our proposed method builds optimal class index structures in terms of the total number of page accesses for given the precollected usage pattern regardless of query types and object distributions.

User-interactive undo is a kind of recovery facility that allows users to correct mistakes easily by canceling and reexecuting operations that have already been executed. Supporting user-interactive undo is essential for authoring processes in new database applications such as software engineering, hypermedia, and computer-aided design. A partial rollback using savepoints supported by commercial database management systems (DBMSs), which allows only cancellation of executed operations, is a restricted form of user-interactive undo. Although many applications use DBMSs, they have to provide user-interactive undo by themselves due to lack of support from the DBMSs. Since implementation of user-interactive undo is quite complex, it poses significant burden to application programmers. This paper proposes a new recovery method facilitating user-interactive undo in DBMSs. Such a facility relieves the programmers of implementing user-interactive undo themselves in developing DBMS applications. The method guarantees fast rollback of transactions that contain user-interactive undos. It also provides users with the bulk undo operation that restores the database to a pre-determined point in the past. The bulk undo operation resembles partial rollback, but differs in that it allows redo that cancels the bulk undo. Moreover, the performance of the method is comparable to that of the traditional recovery method in spite of added functionalities.

This paper presents a physical database design methodology for multidimensional file organizations. Physical database design is the process of determining the optimal configuration of physical files and access structures for a given set of queries. Recently, many multidimensional file organizations have been proposed in the literature. However, there has been no effort toward their physical database design. We first show that the performance of query processing is highly affected by the similarity between the shapes of query regions and page regions in the domain space, and then propose a method for finding the optimal configuration of the multidimensional file by controlling the interval ratio of different axes to achieve the similarity. For performance evaluation, we perform extensive experiments with the multilevel grid file, a multidimensional file organization, using various types of queries and record distributions. The results indicate that our proposed method builds optimal multilevel grid files regardless of the query types and record distributions. When the interval ratio of a two-dimensional query region is 1:1024, the performance of the proposed method is enhanced by as much as 7.5 times over that of the conventional method that has an interval ratio of 1:1 employing the cyclic splitting strategy. The performance is further enhanced for query types having higher interval ratios. The result is significant since interval ratios can be far from 1:1 for many practical applications, especially when different axes have different domains.

Conventional fixed point evaluation techniques evaluate recursions by applying all rules repeatedly using an initial set of tuples (i.e., a given extensional database instance) until no new tuples are generated, but there is no specific order in which rules are applied. We can speed up the evaluation by applying rules in an appropriate order. In this paper, we propose a new fixed point evaluation technique, called the dynamically ordered semi-naive evaluation (or simply DYN), in which the next rule to be applied is determined at run time dynamically. DYN consists of a semi-naive algorithm and a set of selection strategies. The semi-naive algorithm allows dynamic ordering of rule applications and makes tuples generated by a rule application immediately available in the subsequent rule applications. After each rule application, the selection strategies determine the next rule by considering the syntactic structure of recursion and some information about the intermediate result up to the present. We develop these selection strategies so that the total number of rule applications and joins can be reduced. Through experimental comparisons, we shows that DYN outperforms the previous evaluation techniques in terms of the total number of rule applications and joins.

The multilevel grid file (MLGF) is a multidimensional dynamic hashed file organization. Asymptotic directory growth, defined as the growth of the directory as the data file expands, is an important factor for evaluating storage overhead of a multidimensional dynamic file organization. In this article we implement the MLGF and examine the growth of its directory. The concepts and the architecture of the MLGF were introduced in refs [1,2]. We argue that the asymptotic directory growth of the MLGF is linearly dependent on the growth of the data file regardless of data distributions, data skew, or correlation among different organizing attributes. To justify this argument, we perform extensive experiments with various distributions of data: uniform, normal, and exponential distributions. We further perform experiments for more complicated cases where the distributions are highly-skewed or highly-correlated. The results show that the directory size of the MLGF increases linearly in the number of records independently of data distributions, data skew, or correlation, and the rates of increase are nearly constant in all cases. The results also show that both of the blocking factor and number of dimensions do not affect the linearity in directory growth of the MLGF. Such characteristics are important advantages of the MLGF in comparison with other multidimensional file organizations in that storage requirement for the directory is minimized, and splitting, merging, and hyperplane search operations are made easier.

The intermediate result cardinality — the number of objects satisfying a condition given in a query — is an important factor for estimating the cost of the query in query optimization. In this paper we show that an object-oriented query often involves partial participation of classes in a relationship. We then present a new technique for estimating the intermediate result cardinality in such a query. Partial participation has not been considered seriously in existing techniques. Since the proposed technique uses detailed statistics to accommodate partial participation, it estimates the intermediate result cardinality more accurately than existing ones. We also show that these statistics are easily obtained by using inherent properties of object-oriented databases.

Ray tracing requires many ray-object intersection tests. A way of reducing the number of ray-object intersection tests is to subdivide the space occupied by objects into many nonoverlapping subregions, called voxels, and to construct an octree for the subdivided space. We propose the Octree-R, an octree-variant data structure for efficient ray tracing. The algorithm for constructing the Octree-R first estimates the number of ray-object intersection tests. Then, it partitions the space along the plane that minimizes the estimated number of ray-object intersection tests. We present the results of experiments for verifying the effectiveness of the Octree-R. In the experiment, the Octree-R provides a 4% to 47% performance gain over the conventional octree. The result shows the more skewed the object distribution (as is typical for real data), the more performance gain the Octree-R achieves.

We present a technique for integrating expert systems and database management systems (DBMSs). Such integration is essential to accommodate new expert system applications that require a large volume of factual information that cannot be stored in main memory. We propose the Extended Disjunctive Normal Form (EDNF) as the basis of our approach and discuss how we can achieve performance in the integrated system using this technique. The EDNF is an extension of the disjunctive normal form of relational algebra expressions so as to include recursion. The EDNF is well suited for loose coupling, where an existing DBMS and optimization can be fully exploited. We first present the basic form of the EDNF and then use it as a building block to process a more general class of queries. We extend valid usage of Clark's negation-as-failure evaluation technique to incorporate negation for most practical situations. We also propose new criteria for safety and termination in the presence of negation. To the extent of the authors' knowledge, optimization in the loose coupling of expert systems and DBMSs has not been seriously addressed in previous research. We believe our technique provides significant progress in this direction.

A technique is proposed for specifying universal quantification and existential quantification (combined with negation) in a two-dimensional (graphical) database query language. Unlike other approaches that provide set operators to simulate universal quantification, this technique allows a direct representation of universal quantification. Syntactic constructs for specifying universal and existential quantifications, two-dimensional translation of universal quantification to existential quantification (with negation), and translation of existentially quantified two-dimensional queries to relational queries are presented. The resulting relational queries can be processed directly by many existing database systems. The authors claim that this technique renders universal quantifications easy to understand. To substantiate this claim, they provide a simple, easy-to-follow guideline for constructing universally quantified queries. >

In this paper, we study the problem of processing continuous range queries in a hierarchical wireless sensor network. Contrasted with the traditional approach of building networks in a "flat" structure using sensor devices of the same capability, the hierarchical approach deploys devices of higher capability in a higher tier, i.e., a tier closer to the server. While query processing in flat sensor networks has been widely studied, the study on query processing in hierarchical sensor networks has been inadequate. In wireless sensor networks, the main costs that should be considered are the energy for sending data and the storage for storing queries. There is a trade-off between these two costs. Based on this, we first propose a progressive processing method that effectively processes a large number of continuous range queries in hierarchical sensor networks. The proposed method uses the query merging technique proposed by Xiang et al. as the basis and additionally considers the trade-off between the two costs. More specifically, it works toward reducing the storage cost at lower-tier nodes by merging more queries, and toward reducing the energy cost at higher-tier nodes by merging fewer queries (thereby reducing "false alarms"). We then present how to build a hierarchical sensor network that is optimal with respect to the weighted sum of the two costs. It allows for a cost-based systematic control of the trade-off based on the relative importance between the storage and energy in a given network environment and application. Experimental results show that the proposed method achieves a near-optimal control between the storage and energy and reduces the cost by 0.989~84.995 times compared with the cost achieved using the flat (i.e., non-hierarchical) setup as in the work by Xiang et al., 41 pages, 20 figures

MEMS storage devices are new non-volatile secondary storages that have outstanding advantages over magnetic disks. MEMS storage devices, however, are much different from magnetic disks in the structure and access characteristics. They have thousands of heads called probe tips and provide the following two major access facilities: (1) flexibility: freely selecting a set of probe tips for accessing data, (2) parallelism: simultaneously reading and writing data with the set of probe tips selected. Due to these characteristics, it is nontrivial to find data placements that fully utilize the capability of MEMS storage devices. In this paper, we propose a simple logical model called the Region-Sector (RS) model that abstracts major characteristics affecting data retrieval performance, such as flexibility and parallelism, from the physical MEMS storage model. We also suggest heuristic data placement strategies based on the RS model and derive new data placements for relational data and two-dimensional spatial data by using those strategies. Experimental results show that the proposed data placements improve the data retrieval performance by up to 4.0 times for relational data and by up to 4.8 times for two-dimensional spatial data of approximately 320 Mbytes compared with those of existing data placements. Further, these improvements are expected to be more marked as the database size grows., Comment: 37 pages

This paper defines a collection of metrics on manuscript reviewing and presents historical data for ACM Transactions on Database Systems and The VLDB Journal.

A theoretical approach to the optimal design of a large multifile physical database is presented. The design algorithm is based on the theory that, given a set of join methods that satisfy a certain property called separability, the problem of optimal assignment of access structures to the whole database can be reduced to the subproblem of optimizing individual relations independently of one another. Coupling factors are defined to represent all the interactions among the relations. This approach not only reduces the complexity of the problem significantly, but also provides a better understanding of underlying mechanisms.

We present a physical design methodology for network model databases based on the theory of separability. In particular, we present a cost model and a usage specification scheme that are suitable for describing the network model database environment. We subsequently prove that, under these usage and cost models, a large subset of practically important access structures that are available in network model database systems satisfies the conditions for separability. The theory of separability was introduced in an earlier work, in the context of relational systems, as a formal basis for partitioning the problem of designing the optimal physical database. The theory proves that, given a certain set of access structures and a usage specification scheme, the problem of optimal assignment of access structures to the entire database can be reduced to the subproblem of optimizing individual record types independently of one another. The approach we present significantly reduces the complexity of the design problem which has the potential of being combinatorially explosive. A heuristic extension of the formal methodology to the access structures not incorporated in the theory is also discussed.

Counts of unique values are frequently needed information in database systems. Especially, they are essential in query optimization and physical database design. Traditionally, exact counts were obtained by sorting, which is an expensive operation. In this paper we present three algorithms for counting unique values by probabilistic methods. These algorithms require only one pass over the data, and produce approximations to the true count with certain standard deviations. For deviations acceptable in practical environments (~10%), the algorithms require only modest amounts of memory space and computation time. We have implemented all three algorithms in System R. We also present the results of the experiments on accuracy and performance of these algorithms.