An asymptotically optimal multiversion B-tree

In a variety of applications, we need to keep track of the development of a data set over time. For maintaining and querying these multiversion data efficiently, external storage structures are an absolute necessity. We propose a multiversion B-tree that supports insertions and deletions of data items at the current version and range queries and exact match queries for any version, current or past. Our multiversion B-tree is asymptotically optimal in the sense that the time and space bounds are asymptotically the same as those of the (single-version) B-tree in the worst case. The technique we present for transforming a (single-version) B-tree into a multiversion B-tree is quite general: it applies to a number of hierarchical external access structures with certain properties directly, and it can be modified for others.     

An efficient buffer memory system for subarray access

Many current graphical display systems utilize a buffer memory system to contain a two-dimensional image array to be modified and displayed. In order to speed up the update of the buffer memory system, it is required that the buffer memory system accesses many image points within an image subarray in parallel. This paper proposes an efficient buffer memory system for a fast and high-resolution graphical display system. The memory system provides parallel accesses to pq image points within a block(p×q), a horizontal (1×pq), a vertical (pq×1), a forward-diagonal, or a backward-diagonal subarray in a two-dimensional image array, M×N, where the design parameters p and q are all powers of two. In the address calculation and routing circuit of the proposed buffer memory system, the address differences of the five subarrays are prearranged according to the index numbers of memory modules and stored in two static random access memories (SRAMs), so that the address differences are simply added to the base address to obtain the addresses according to the index numbers of memory modules. In addition, for the fast address calculation, one single multiplication operation in the base address calculation is replaced by a SRAM access, so that the multiplication operation can be performed during the SRAM access for the address differences for the case when N is not a power of two. The address calculation and routing circuit proposed in this paper is improved in the hardware cost, the complexity of control, and the speed over the previous circuits     

An efficient cache conscious multi-dimensional index structure

Recently, to relieve the performance degradation caused by the bottleneck between CPU and main memory, cache conscious multi-dimensional index structures have been proposed. The ultimate goal of them is to reduce the space for entries so as to widen index trees and minimize the number of cache misses. The existing index structures can be classified into two approaches according to their entry reduction methods. One approach is to compress MBR keys by quantizing coordinate values to the fixed number of bits. The other approach is to store only the sides of minimum bounding regions (MBRs) that are different from their parents partially. The second approach works well when the size of a node is small and the number of entries is small. In this paper, we investigate the existing multi-dimensional index structures for main memory database systems through experiments under the various work loads. Then, we propose a new index structure that exploits the properties of the both techniques. We implement existing multi-dimensional index structures and the proposed index structure. We perform various experiments to show that our approach outperforms others.     

FHIN: an efficient storage structure and access method for object-oriented databases

While relational database technology has dominated the database field for more than a decade, object-oriented database (OODB) technology has recently gained a lot of attention in the database community. Many researchers are concerned about the performance of OODBs. This paper proposes an OODB design methodology called fragmented hash-indexed (FHIN) that is aimed at improving the operating performance of OODBs. The FHIN model's storage structure contains an Instances–Classes Table (ICT) with a two-segment data design. Query processing is done by accessing data segments through ICT with an algorithm introduced here. The FHIN model uses three access methods: hashing, indexing, or hash-indexing. The database performance of FHIN is compared to two previous access methods using 1050 simulation runs. Results indicate that the FHIN model is 43% better than either of the other models in smaller databases, 65% better in larger databases, 50% better under conditions of high updating, and 72% better under conditions of low updating. These results suggest that FHIN methodology has promise and is worthy of exploration and OODB software development.     

On-line multiversion database concurrency control

This paper presents a new model for studying the concurrency vs. computation time tradeoffs involved in on-line multiversion database concurrency control. The basic problem that is studied in our model is the following: Given:a current database system state which includes information such as which transaction previously read a version from which other transaction; which transaction has written which versions into the database; and the ordering of versions previously written; anda set of read and write requests of requesting transactions. Question: Does there exist a new database system state in which the requesting transactions can be immediately put into execution (their read and write requests satisfied, or in the case of predeclared writeset transactions, write requests are guaranteed to be satisfied) while preserving consistency under a given set of additional constraints? (The amount of concurrency achieved is defined by the set of additional constraints). In this paper we derive “limits” of performance achievable by polynomial time concurrency control algorithms. Each limit is characterized by a minimal set of constraints that allow the on-line scheduling problem to be solved in polynomial time. If any one constraint in that minimal set is omitted, although it could increase the amount of concurrency, it would also have the dramatic negative effect of making the scheduling problem NP-complete; whereas if we do not omit any constraint in the minimal set, then the scheduling problem can be solved in polynomial time. With each of these limits, one can construct an efficient scheduling algorithm that achieves an optimal level of concurrency in polynomial computation time according to the constraints defined in the minimal set.     

An efficient spatial access method for spatial images containing multiple non-overlapping features

In this paper we propose and analyze a new spatial access method, namely the S*-tree, for the efficient secondary memory encoding and manipulation of images containing multiple non-overlapping features (i.e., coloured images). The S*-tree is based on a non-straightforward and space efficient extension to coloured images of its precursor, namely the S⁺-tree, which was explicitly designed for binary images. To assess experimentally the qualities of the S*-tree, we test it against the HL-quadtree, a previous spatial access method for coloured images, which is known to be space and time efficient. Our experiments show that the S*-tree reaches up to a 75% of space saving, and performs constantly less I/O accesses than the HL-quadtree in solving classical window queries.     

An efficient key management scheme for user access control in outsourced databases

Recently, researches on key management scheme for user access control in outsourced databases have been actively done. Because outsourced databases require dealing with a lot of users and data resources, an efficient key management scheme for reducing the number of authentication keys is required. However, the existing schemes have a critical problem that the cost of key management is rapidly increasing as the number of keys becomes larger. To solve the problem, we propose an efficient key management scheme for user access control in outsourced databases. For this, we propose an Resource Set Tree(RST)-based key generation algorithm to reduce key generation cost by merging duplicated data resources. In addition, we propose a hierarchical Chinese Remainder Theorem(CRT)-based key assignment algorithm which can verify a user permission to gain accesses to outsourced databases. Our algorithm can reduce key update cost because the redistribution of authentication keys is not required. We also provide the analytic cost models of our algorithms and verify the correctness of the theoretical analysis by comparing them with experiment results. Finally, we show from the performance analysis that the proposed scheme outperforms the existing schemes in terms of both key generation cost and update cost.     

A Conservative Multiversion Locking-Graph Scheduler Algorithm

In order to improve the concurrency of multiversion database systems,a conservative MV locking-graph scheduler algorithm is proposed,which takes the power of MVS as a target.The algorithm combines the advantages of locking and graph,and does optimizing processes on read-only and write-only operations to reduce the blocks of transactions.The correctness and complexity of the algorithm are also provided.     

一种基于多相结构的高效数字下变频设计

基于带通采样结构的数字下变频技术是软件无线电收发机的关键技术之一。介绍了一种基于多相结构的带通采样数字下变频设计。首先,采用带通采样,使得ADC更靠近天线,数字化更为充分;其次,通过对采样频率和中频的选取,使得正交混频无需使用查找表,避免了截位处理,改善了混频后的无杂散动态范围;最后,根据并行混频的结构,选择多相抽取滤波器结构进行处理,在确保达到系统要求的同时,提高了硬件资源利用率。该系统具有高度的灵活性和充分的数字化特点,有较高的实用价值。     

An efficient controller structure with minimum roundoff noise gain

Based on a polynomial operator approach, a new sparse controller structure is derived, which is actually an improved version of the recently proposed structure [Li, G. (2004). A polynomial-operator-based DFIIt structure for IIR filters. IEEE Transactions on Circuits and Systems II, 51, 147-151]. The performance of the proposed structure is analyzed by deriving the corresponding expression of roundoff noise gain and the problem of finding optimized sparse structures is solved efficiently with a genetic algorithm (GA). A numerical example is given, which shows that the newly developed structure can achieve much better performance than some well-known structures and particularly outperforms the traditional optimal fully parametrized realization greatly in terms of reducing roundoff noise and implementation complexity.     

An efficient peer-to-peer indexing tree structure for multidimensional data

As one of the most important technologies for implementing large-scale distributed systems, peer-to-peer (P2P) computing has attracted much attention in both research and industrial communities, for its advantages such as high availability, high performance, and high flexibility to the dynamics of networks. However, multidimensional data indexing remains as a big challenge to P2P computing, because of the inefficiency in search and network maintenance caused by the complicated existing index structures, which greatly limits the scalability of applications and dimensionality of the data to be indexed.We propose SDI (Swift tree structure for multidimensional Data Indexing), a swift index scheme with a simple tree structure for multidimensional data indexing in large-scale distributed systems. While keeping the query efficiency in O(logN) in terms of routing hops, SDI has extremely low maintenance costs which is proved through theoretical analysis. Furthermore, SDI overcomes the root-bottleneck problem existing in most other tree-based distributed indexing systems. Extensive empirical study verifies the superiority of SDI in both query and maintenance performance.     

An efficient PHR service system supporting fuzzy keyword search and fine-grained access control

Outsourcing of personal health record (PHR) has attracted considerable interest recently. It can not only bring much convenience to patients, it also allows efficient sharing of medical information among researchers. As the medical data in PHR is sensitive, it has to be encrypted before outsourcing. To achieve fine-grained access control over the encrypted PHR data becomes a challenging problem. In this paper, we provide an affirmative solution to this problem. We propose a novel PHR service system which supports efficient searching and fine-grained access control for PHR data in a hybrid cloud environment, where a private cloud is used to assist the user to interact with the public cloud for processing PHR data. In our proposed solution, we make use of attribute-based encryption (ABE) technique to obtain fine-grained access control for PHR data. In order to protect the privacy of PHR owners, our ABE is anonymous. That is, it can hide the access policy information in ciphertexts. Meanwhile, our solution can also allow efficient fuzzy search over PHR data, which can greatly improve the system usability. We also provide security analysis to show that the proposed solution is secure and privacy-preserving. The experimental results demonstrate the efficiency of the proposed scheme.     

An attribute-based lightweight cloud data access control using hypergraph structure

The Journal of Supercomputing - Cloud file storage systems are the current trend of enterprises and also of individual users. Due to the malicious or unauthorized users, file sharing among the...     

Exploiting SSDs in operational multiversion databases

Multiversion databases store both current and historical data. Rows are typically annotated with timestamps representing the period when the row is/was valid. We develop novel techniques to reduce index maintenance in multiversion databases, so that indexes can be used effectively for analytical queries over current data without being a heavy burden on transaction throughput. To achieve this end, we re-design persistent index data structures in the storage hierarchy to employ an extra level of indirection. The indirection level is stored on solid-state disks that can support very fast random I/Os, so that traversing the extra level of indirection incurs a relatively small overhead. The extra level of indirection dramatically reduces the number of magnetic disk I/Os that are needed for index updates and localizes maintenance to indexes on updated attributes. Additionally, we batch insertions within the indirection layer in order to reduce physical disk I/Os for indexing new records. In this work, we further exploit SSDs by introducing novel DeltaBlock techniques for storing the recent changes to data on SSDs. Using our DeltaBlock, we propose an efficient method to periodically flush the recently changed data from SSDs to HDDs such that, on the one hand, we keep track of every change (or delta) for every record, and, on the other hand, we avoid redundantly storing the unchanged portion of updated records. By reducing the index maintenance overhead on transactions, we enable operational data stores to create more indexes to support queries. We have developed a prototype of our indirection proposal by extending the widely used generalized search tree open-source project, which is also employed in PostgreSQL. Our working implementation demonstrates that we can significantly reduce index maintenance and/or query processing cost by a factor of 3. For the insertion of new records, our novel batching technique can save up to 90 % of the insertion time. For updates, our prototype demonstrates that we can significantly reduce the database size by up to 80 % even with a modest space allocated for DeltaBlocks on SSDs.     

Multiversion join index for multiversion data warehouse

The data warehouse (DW) technology is developed in order to support the integration of external data sources (EDSs) for the purpose of advanced data analysis by On-Line Analytical Processing (OLAP) applications. Since contents and structures of integrated EDSs may evolve in time, the content and schema of a DW must evolve too in order to correctly reflect the evolution of EDSs. In order to manage a DW evolution, we developed the multiversion data warehouse (MVDW) approach. In this approach, different states of a DW are represented by the sequence of persistent DW versions that correspond either to the real world state or to a simulation scenario. Typically, OLAP applications execute star queries that join multiple fact and dimension tables. An important optimization technique for this kind of queries is based on join indexes. Since in the MVDW fact and dimension data are physically distributed among multiple DW versions, standard join indexes need extensions. In this paper we present the concept of a multiversion join index (MVJI) applicable to indexing dimension and fact tables in the MVDW. The MVJI has a two-level structure, where an upper level is used for indexing attributes and a lower level is used for indexing DW versions. The paper also presents the theoretical upper bound (pessimistic) analysis of the MVJI performance characteristic with respect to I/O operations. The analysis is followed by experimental evaluation. It shows that the MVJI increases a system performance for queries addressing multiple DW versions with exact match and range predicates.     

An efficient key assignment scheme for access control in a large leaf class hierarchy

The employees of an organization are usually divided into different security classes to authorize the information retrieval, and the number of leaf classes is substantially larger than the number of non-leaf classes. Additionally, the alternations in leaf classes are more frequent than in non-leaf classes. We proposed a new key assignment scheme for controlling the access right in a large POSET (partially ordered set) hierarchy to reduce the required computation for key generation and derivation with the storage amount of data decreased.     

DiffNodesets: An efficient structure for fast mining frequent itemsets

Mining frequent itemsets is an essential problem in data mining and plays an important role in many data mining applications. In recent years, some itemset representations based on node sets have been proposed, which have shown to be very efficient for mining frequent itemsets. In this paper, we propose DiffNodeset, a novel and more efficient itemset representation, for mining frequent itemsets. Based on the DiffNodeset structure, we present an efficient algorithm, named dFIN, to mining frequent itemsets. To achieve high efficiency, dFIN finds frequent itemsets using a set-enumeration tree with a hybrid search strategy and directly enumerates frequent itemsets without candidate generation under some case. For evaluating the performance of dFIN, we have conduct extensive experiments to compare it against with existing leading algorithms on a variety of real and synthetic datasets. The experimental results show that dFIN is significantly faster than these leading algorithms.