Search

The set of closed high-utility itemsets (CHUIs) concisely represents the exact utility of all itemsets. Yet, it can be several orders of magnitude smaller than the set of all high-utility itemsets. Existing CHUI mining algorithms assume that databases are static, making them very expensive in the case of incremental data, since the whole dataset has to be processed for each batch of new transactions. To address this challenge, this paper presents the first approach, called IncCHUI, that mines CHUIs efficiently from incremental databases. In order to achieve this, we propose an incremental utility-list structure, which is built and updated with only one database scan. Further, we apply effective pruning strategies to fast construct incremental utility-lists and eliminate candidates that are not updated. Finally, we suggest an efficient hash-based approach to update or insert new closed sets that are found. Our extensive experimental evaluation on both real-life and synthetic databases shows the efficiency, as well as the feasibility of our approach. It significantly outperforms previously proposed methods that are mainly run in batch mode in terms of speed, and it is scalable with respect to the number of transactions.

With rapidly decreasing storage costs, temporal document databases are now a viable solution in many contexts. However, storing an ever-growing database can still be too costly, and as a consequence it is desirable to be able to physically delete old versions of data. Traditionally, this has been performed by an operation called vacuuming, where the oldest versions are physically deleted or migrated from secondary storage to less costly tertiary storage. In temporal document databases on the other hand, it is often more appropriate to remove intermediate versions instead of removing the oldest versions. We call this operation granularity reduction. In this paper we describe the concept of granularity reduction, and present six strategies for selecting the document versions to eliminate. Three of the strategies have been implemented in the V2 temporal document database system, and in this context we discuss the cost of applying the strategies.

It is now feasible to store previous versions of documents, and not only the most recent version which has been the traditional approach. This is of interest in a number of application, both temporal document databases as well as web archiving systems and temporal XML warehouses. In this paper, we describe the architecture and the implementation of V2, a temporal document database system that supports storage, retrieval, and querying of temporal documents. We also give some performance results from a mini-benchmark run on the V2 prototype.

In most current database systems, data is updated in-place. In order to support recovery and increase performance, write-ahead logging is used. This logging defers the in-place updates. However, sooner or later, the updates have to be applied to the database. Even if this is done as a batch operation, it can result in many nonsequential writes. In order to avoid this, another approach is to eliminate the database completely and use a log-only approach. In this case, the log is written contiguously to the disk, in a no-overwrite way using large blocks. When using the log-only approach keeping previous versions comes almost for free, and this approach is therefore particularly interesting for transaction-time temporal object database systems. Although the log-only approach in its basic form is relatively straightforward, it is not trivial to support features such as steal/no-force buffer management, fuzzy checkpointing, and fast commit. We describe, in detail, algorithms and strategies for object and log management that make support for these features possible.

In temporal document databases, and temporal XML databases, temporal text-containment queries are a potential performance bottleneck. In this paper we describe how to manage documents and index structures in such databases in a way that makes, temporal text-containment querying feasible. We describe and discuss different index structures that can improve such queries. Three of the alternatives have been implemented in the V2 temporal document database system, and the performance of the index structures is studied using temporal web data. The results show that even a very simple time-indexing approach can reduce query cost by up to three orders of magnitude.

In a transaction-time temporal object database management system (TODBMS), updating an object creates a new version of the object, but the old version is still accessible. A TODBMS will store large amounts of data, and in order to provide the necessary computing power and data bandwidth, a parallel system based on a shared-nothing architecture is necessary. In order to benefit from a parallel architecture, a suitable declustering of the objects over the nodes in the system is important. In this paper, we study three low-cost declustering algorithms: (1) declustering based on the hash value of the OID of the objects, (2) range partitioning based on the timestamp of the objects, and (3) a new hybrid algorithm, where current object versions are declustered according to the hash value of the OID, and the historical versions are range partitioned based on timestamp. In contrast to many similar studies, we study the performance with a workload including both read and update operations. We show that strategies 1 and 3 are the most scalable strategies, and that the new hybrid declustering strategy is especially suitable for low update rates, for example in geographical information systems and decision support systems with support for temporal data. However, in general declustering based on the hash value of the OID of the objects has the most stable and predictable performance.

In many application areas, the access pattern is navigational and a large fraction of the accesses are perfect match accesses/queries on one or more words in text strings in the objects. One example of such an application area is XML data stored in object database systems. Such systems will frequently store large amounts of data, and in order to provide the necessary computing power and data bandwidth, a parallel system based on a shared-nothing architecture can be necessary. In this paper, we describe how the signature cache approach can significantly reduce the average object access cost in parallel object database systems.

Object database systems (ODBs) are an attractive alternative to relational database systems, especially in application areas where the modeling power or performance of relational database systems is insufficient. These applications typically maintain large amounts of data. Frequently, some of the data is temporal data. For the temporal data, the whole history of the individual objects is kept, and data is never deleted. The area of temporal ODBs is still immature, and there are many design issues that need to be solved in order to be able to achieve the desired performance. In this paper, we discuss some temporal ODB research issues and possible solutions related to object storage, object management, main memory buffering, and language bindings.

In this paper, we present the SigCache approach. In contrast to traditional signature files where signatures are stored in separate files, signatures are in our approach stored together with their objects. In addition, the most frequently accessed signatures are stored in a main memory signature cache (SigCache). When using the signatures stored in the SigCache as a filter during perfect match queries, the number of objects that actually have to be retrieved during perfect match queries can be reduced. The increase in update cost is insignificant, because the signatures are much smaller than the objects.

Computational science applications performing distributed computations using grid networks are now emerging. These applications have new and demanding requirements for efficient query processing. To meet these requirements, we have developed the DASCOSA-DB distributed database system. In this chapter, a detailed overview of the architecture and implementation of DASCOSA-DB is given, as well as a description of novel features developed to better support typical data-intensive applications running on a grid system: fault-tolerant query processing, dynamic refragmentation, allocation and replication of data fragments, and distributed semantic caching.

Requirements from new types of applications call for new database system solutions. Computational science applications performing distributed computations on Grid networks with requirements for efficient storage and query solutions are now emerging. For this purpose we have developed DASCOSA-DB, a P2P-based distributed database system, which in addition to providing location-transparent storage and querying, also includes novel features like efficient partial restartof queries and redistribution of query operators in the context of failure, dynamic refragmentation and allocation, and distributed semantic caching. In this demo, the novel features will be demonstrated, combined with a more general description of the architecture and demonstration of the distributed query processing capabilities.

XML is emerging as the de-facto standard for semistructured contents and metadata. Searching this content in mobile environments is challenging, since centralized approaches are not appropriate in a very dynamic environment with limited resources available for keeping a centralized index up-to-date. A more appropriate solution is to organize the mobile devices in an unstructured peer-to-peer (P2P) network. The main challenge in the context of unstructured P2P is to determine the peers that might store documents matching a query, i.e., peer selection. In this paper, we propose a summary caching method for increasing the efficiency and recall of peer selection during XML querying. Our approach is based on caching parts of XML schemas along the query path, to enable subsequent jumps to remote peers storing content relevant to the query. We evaluate the performance improvements of our search strategy in terms of completeness of the search and reduced latency. The results show that our approach can significantly enhance a naive query mechanism such as flooding, and consistently outperform a baseline path caching technique similar to techniques used in related work.

Peer-to-peer database systems (P2PDBs) aim at providing database services with node autonomy, high availability and loose coupling between participating nodes by building the DBMS on top of a peer-to-peer network. A key feature of current peer-to-peer systems is resilience to churn in the overlay network layer. A major challenge in P2PDBs is to provide similar robustness in the data and query processing layer. In this paper we in particular describe how aggregation queries in P2PDBs can be handled in order to reduce the impact of churn on accuracy of results. We perform a formal study of data loss and accuracy of such queries, and describe new approaches that increase the accuracy of aggregation queries in P2PDBs under churn.

The peer-to-peer (P2P) paradigm is emerging as a possible solution to some of the problems in distributed data processing, including scalability, availability, and administrative cost. P2P has already proved to be suitable in contexts like file sharing, distributed computations, and distributed search. In our research we are aiming at using P2P to solve some problems in the domain of distributed databases. In this paper we 1) present PORDaS, a distributed DBMS based on P2P techniques, 2) describe query processing and query planning in PORDaS, and 3) present results from an experimental evaluation of different query planning variants.

Computational science is a rapidly growing multidisciplinary field that uses advanced computing capabilities to understand and solve complex problems. So far, grid computing has gained some maturity with respect to the actual computation. However, the management of data in grid networks is still a very immature area. In this paper, we present DASCOSA (database support for computational science applications), which consists of a) a grid database management system based on the peer-to-peer paradigm (POR-DaS), and b) a semantic layer that provides seamless access to the heterogeneous sources in the data grid. We present the architecture of PORDaS, and the design of the semantic layer that is under development

The advent of digital libraries along with the tremendous growth of digital content call for distributed and scalable approaches for managing vast data collections. Peer-to-peer (P2P) networks emerge as a promising solution to delve with these challenges. However, the lack of global content/topology knowledge in an unstructured P2P system demands unsupervised methods for content organization and necessitates efficient and high quality search mechanisms. Towards this end, Semantic Overlay Networks (SONs) have been proposed in the literature, and in this paper, an unsupervised method for decentralized and distributed generation of SONs, called DESENT, is proposed. We prove the feasibility of our approach through analytical cost models and we show through simulations that, when compared to flooding, our approach improves recall by more than 3-10 times, depending on the network topology.

Storage costs are rapidly decreasing, making it feasible to store larger amounts of data in databases. This also makes it possible to store previous versions of data in the databases, instead of only keeping the last version. Recently, the amount of data available in XML has been rapidly increasing. In this paper, we describe TeXOR, a temporal XML database system built on top of an object-relational database system. We describe the TXSQL query language used in TeXOR for querying temporal XML documents stored in the system, discuss storage alternatives for XML documents in such a system, and some details about the implementation of the current TeXOR prototype.

Temporal document databases are interesting in a number of contexts, in general document databases as well as more specialized applications like temporal XML/Web warehouses. In order to efficiently manage temporal document versions, a temporal document database system should be employed. In this paper, we describe the V2 temporal document database system, which supports storage, retrieval, and querying of temporal documents. We also give some performance results from a mini-benchmark run on the V2 prototype.

In a database system, read operations are much more common than write operations, and consequently, database systems have been read optimized. As the size of main memory increases, more of the database read requests will be satisfied front the buffer system, and the amount of disk write operations relative to disk read operations will increase. This calls for a focus on write optimized database systems. In this paper, we present solutions to this problem. We describe in detail the data structures and algorithms needed to realize a write optimized object-oriented database system in the context of Vagabond, an OODB currently being implemented at our department. In Vagabond, focus has been to provide support for applications which have earlier used file systems because of the limited data bandwidth in current database systems, typical examples are supercomputing applications and geographical information systems.

In an object database system using logical OIDs, an OID index (OIDX) is necessary to map from logical OID to the physical location of an object. In a temporal object database system (TODB), this OIDX also contains the timestamps of the object versions. OIDX maintenance can be very costly, and can easy become the bottleneck of such a system. The main reason for this, is that in a TODB the OIDX needs to be updated every time an object is updated. In order to reduce the access costs, a new index structure, particularly suitable to TODB requirements, is necessary. In this paper, we describe an OIDX for TODBs, the Vagabond Temporal OID Index (VTOIDX). The main goals of the VTOIDX are: 1) support for temporal data, while still having index performance close to a non-temporal (one-version) database system, 2) efficient object-relational operation, and 3) flexible tertiary storage migration of partitions of the index. In this paper, we describe the physical organization and the operations of the VTOIDX.

An alternative to in-place updating of data is to eliminate the database completely, and use a log-only approach. The log is written contiguously to the disk, in a no-overwrite way, in large blocks. The log-only approach is particularly interesting for transaction time object database systems (TODB), because keeping previous versions of objects is a feature that comes for free. One of the objections against log-only databases has been that the read cost will be prohibitively high because of loss of clustering. However in our comparison of the performance of log-only and in-place update TODBs, the analysis shows that with the workload we expect to be typical for future TODBs, the log-only approach is highly competitive with the traditional in-place update approach.

We have previously studied the possible performance gain from using the log-only approach to realize temporal object database systems. Although the log-only approach in its basic form is relatively straightforward, it is not trivial to support features such as steal/no-force buffer management, fuzzy checkpointing, and fast commit. In this paper, we describe in detail algorithms and strategies for object and log management that make support for these features possible.

In a transaction-time temporal object database system (ODB) an object update creates a new object version, but the old versions are still accessible. Each object version has an associated timestamp, and this versioning, related to time, is supported and maintained by the system. The system also provides support for querying the temporal data. The area of temporal ODBs is still immature, and there are many design issues that need to be solved. In this paper, we discuss some issues and possible solutions derived from the design of the Vagabond temporal ODB. This includes physical object storage, clustering of temporal objects, OID indexing, and language bindings in a temporal ODB.

In this paper, we describe main-memory management and the most important buffers in the Vagabond server, a transaction-time temporal object database system currently under development at the Norwegian University of Science and Technology. Special emphasis is given to fine granularity buffering of OID index entries and objects.

In object database systems (ODBs) with logical OIDs, an OID index (OIDX) is needed to map from OID to the physical location of the object. In a transaction-time temporal ODB, the OIDX should also index the object versions. In this case, the index entries, which we call object descriptors (OD), also include the commit timestamp of the transaction that created the object version. In this chapter, we present an analytical model for OIDX access costs and optimal use of the memory for buffering index pages and ODs, with different access patterns.

Simulating distributed database systems is inherently difficult, as there are many factors that may influence the results. This includes architectural options as well as workload and data distribution. In this paper we present the DBsim simulator and some simulation results. The DBsim simulator architecture is extendible, and it is easy to change parameters and configuration. The simulation results in this paper is a comparison of performance and response times for two concurrency control algorithms, timestamp ordering and two-phase locking. The simulations have been run with different number of nodes, network types, data declustering and workloads. The results show that for a mix of small and long transactions, the throughput is significantly higher for a system with a timestamp ordering scheduler than for a system with a two-phase locking scheduler. With only short transactions, the performance of the two schedulers are almost identical. Long transactions are treated more fair by a two-phase locking scheduler, because a timestamp ordering scheduler has a very high abort rate for long transactions.