Every time-series has its own linear trend, the directionality of a time-series, and removing the linear trend is crucial to get more intuitive matching results. Supporting the linear detrending in subsequence matching is a challenging problem due to the huge number of all possible subsequences. In this paper we define this problem as the linear detrending subsequence matching and propose its efficient index-based solution. To this end, we first present a notion of LD-windows (LD means linear detrending). Using the LD-windows we then present a lower bounding theorem for the index-based matching solution and show its correctness. We next propose the index building and subsequence matching algorithms. We finally show the superiority of the index-based solution.

Flash SSDs are being incorporated in many enterprise storage platforms recently and expected to play a notable role for IO-intensive applications. However, the IO characteristics of flash SSDs are very different from those of hard disks. Since existent storage subsystems are designed on the basis of characteristics of hard disks, the IO performance of flash SSDs may not be obtained as expected. This paper provides an evaluation of flash SSDs in transaction processing systems with TPC-C benchmark. We present performance results with various configurations and describe our observations of the IO behaviors at different levels along the IO path, which helps to understand the performance of flash-based transaction processing systems and provides certain references to build flash-based systems for IO-intensive applications.

The turn of the century is witnessing radical changes in the way information services are spreading due to the progress of IT and the constantly increase in the number of users of the WWW. Therefore, the business market is changing its strategy for a modern online business environment. Autonomous Decentralized Database System (ADDS), based on autonomous coordinating subsystems, has been proposed as a system architecture in order to meet the innovative e-business requirements for consistency and high response among distributed database systems. Autonomy and decentralization of subsystems help achieving high response time in highly competitive situation and autonomous Mobile Agent based coordination has been proposed to achieve flexibility in a highly dynamic environment. In this paper, it is analyzed the case in which the system size increases; and a multi agent coordination, the same number of mobile agents and sites coexist in the system, is proposed for achieving the timeliness property. The response time in the system is conformed by those transactions that require coordination and those that can be satisfied immediately. In accordance, the distribution of the data in the system for coordination is a medullar issue for the improvement of the response time. A trade-off exits between these two kind of transactions depending on the coordination of the Mobile Agents, the capacity of allocating data among the sites, and as well as the distribution of the data and user requests in the system. In this sense, since the system requires high response time, a data allocation technology in which each mobile agent autonomously determine its own capacity for adjusting data among the sites is proposed. Thus, the system will adapt itself to the dynamic environment. The effectiveness of the proposed architecture and technologies are evaluated by simulation.

Web APIs are offered in many Web sites for Ajax and mashup, but they have been developed independently since no reusable database component has been specifically created for Web applications. In this paper, we propose WAPDB, a distributed database management system for the rapid development of Web applications. WAPDB is designed on Atom, a set of Web API standards, and provides several of the key features required for Web applications, including efficient access control, an easy extension mechanism, and search and statistics capabilities. By introducing WAPDB, developers are freed from the need to implement these features as well as Web API processing. In addition, its design totally follows the REST architectural style, which gives uniformity and scalability to applications. We develop a proof-of-concept application with WAPDB, and find that it offers great cost effectiveness with no significant impact on performance; in our experiments, the development cost is reduced to less than half with the overhead (in use) of response times of just a few msec.

In this paper, we emphasize the need for data cleansing when clustering large-scale transaction databases and propose a new data cleansing method that improves clustering quality and performance. We evaluate our data cleansing method through a series of experiments. As a result, the clustering quality and performance were significantly improved by up to 165% and 330%, respectively.

Encryption can provide strong security for sensitive data against inside and outside attacks. This is especially true in the "Database as Service" model, where confidentiality and privacy are important issues for the client. In fact, existing encryption approaches are vulnerable to a statistical attack because each value is encrypted to another fixed value. This paper presents a novel database encryption scheme called MV-OPES (Multivalued--Order Preserving Encryption Scheme), which allows privacy-preserving queries over encrypted databases with an improved security level. Our idea is to encrypt a value to different multiple values to prevent statistical attacks. At the same time, MV-OPES preserves the order of the integer values to allow comparison operations to be directly applied on encrypted data. Using calculated distance (range), we propose a novel method that allows a join query between relations based on inequality over encrypted values. We also present techniques to offload query execution load to a database server as much as possible, thereby making a better use of server resources in a database outsourcing environment. Our scheme can easily be integrated with current database systems as it is designed to work with existing indexing structures. It is robust against statistical attack and the estimation of true values. MV-OPES experiments show that security for sensitive data can be achieved with reasonable overhead, establishing the practicability of the scheme.

The need for data encryption that protects sensitive data in a database has increased rapidly. However, encrypted data can no longer be efficiently queried because nearly all of the data should be decrypted. Several order-preserving encryption schemes that enable indexes to be built over encrypted data have been suggested to solve this problem. They allow any comparison operation to be directly applied to encrypted data. However, one of the main disadvantages of these schemes is that they expose sensitive data to inference attacks with order information, especially when the data are used together with unencrypted columns in the database. In this study, a new order-preserving encryption scheme that provides secure queries by hiding the order is introduced. Moreover, it provides efficient queries because any user who has the encryption key knows the order. The proposed scheme is designed to be efficient and secure in such an environment. Thus, it is possible to encrypt only sensitive data while leaving other data unencrypted. The encryption is not only robust against order exposure, but also shows high performance for any query over encrypted data. In addition, the proposed scheme provides strong updates without assumptions of the distribution of plaintext. This allows it to be integrated easily with the existing database system.

Quantum computations have so far proved to be more powerful than classical computations, but quantum computers still have not been put into practical use due to several technical issues. One of the most serious problems for realizing quantum computers is decoherence that occurs inevitably since our apparatus are surrounded with environment and open systems. In this paper, we give some surveys on a variety of effects of decoherence in quantum algorithms such as Grover's database search and quantum walks, and we show how quantum algorithms work under decoherence, how sensitive they are against decoherence, and how to implement a robust quantum circuit.

This paper discusses verification of the security against inference attacks on XML databases. First, a security definition called k-secrecy against inference attacks on XML databases is proposed. k-secrecy with an integer k > 1 (or k = ∞) means that attackers cannot narrow down the candidates for the value of the sensitive information to k - 1 (or finite), using the results of given authorized queries and schema information. Secondly, an XML query model such that verification can be performed straightforwardly according to the security definition is presented. The query model can represent practical queries which extract some nodes according to any of their neighboring nodes such as ancestors, descendants, and siblings. Thirdly, another refinement of the verification method is presented, which produces much smaller intermediate results if a schema contains no arbitrarily recursive element. The correctness of the refinement is proved, and the effect of the refinement in time and space efficiency has been confirmed by experiment.

Lower-dimensional transformations in similar sequence matching show different performance characteristics depending on the type of time-series data. In this paper we propose a hybrid approach that exploits multiple transformations at a time in a single hybrid index. This hybrid approach has advantages of exploiting the similar effect of using multiple transformations and reducing the index maintenance overhead. For this, we first propose a new notion of hybrid lower-dimensional transformation that extracts various features using different transformations. We next define the hybrid distance to compute the distance between the hybrid transformed points. We then formally prove that the hybrid approach performs similar sequence matching correctly. We also present the index building and similar sequence matching algorithms based on the hybrid transformation and distance. Experimental results show that our hybrid approach outperforms the single transformation-based approach.

An expectation for more intelligent Web is recently being reflected through the new research field called Semantic Web. In this paper, related with Semantic Web security, we introduce an RDF triple based access control model having explicit authorization propagation by inheritance and implicit authorization propagation by inference. Especially, we explain an authorization conflict problem between the explicit and the implicit authorization propagation, which is an important concept in access control for Semantic Web. We also propose a novel conflict detection algorithm using graph labeling techniques in order to efficiently find authorization conflicts. Some experimental results show that the proposed detection algorithm has much better performance than the existing detection algorithm when data size and number of specified authorizations become larger.

In this paper, we propose a continuous range query processing method over moving objects. To efficiently process continuous range queries, we design a main-memory-based query index that uses smaller storage and significantly reduces the query processing time. We show through performance evaluation that the proposed method outperforms the existing methods.

In this paper, we propose an image completion algorithm which takes advantage of the countless number of images available on Internet photo sharing sites to replace occlusions in an input image. The algorithm 1) automatically selects the most suitable images from a database of downloaded images and 2) seamlessly completes the input image using the selected images with minimal user intervention. Experimental results on input images captured at various locations and scene conditions demonstrate the effectiveness of the proposed technique in seamlessly reconstructing user-defined occlusions.

Similarity search in time-series databases finds such data sequences whose changing patterns are similar to that of a query sequence. For efficient processing, it normally employs a multi-dimensional index. In order to alleviate the well-known dimensionality curse, the previous methods for similarity search apply the Discrete Fourier Transform (DFT) to data sequences, and take only the first two or three DFT coefficients as organizing attributes. Other than this ad-hoc approach, there have been no research efforts on devising a systematic guideline for choosing the best organizing attributes. This paper first points out the problems occurring in the previous methods, and proposes a novel solution to construct optimal multi-dimensional indexes. The proposed method analyzes the characteristics of a target time-series database, and identifies the organizing attributes having the best discrimination power. It also determines the optimal number of organizing attributes for efficient similarity search by using a cost model. Through a series of experiments, we show that the proposed method outperforms the previous ones significantly.

In this paper, the development, long-term operation and portability of a practical ASR application in a real environment is investigated. The target application is a speech-oriented guidance system installed at the local community center. The system has been exposed to ordinary people since November 2002. More than 300 hours or more than 700,000 inputs have been collected during four years. The outcome is a rare example of a large scale real-environment speech database. A simulation experiment is carried out with this database to investigate how the system's performance improves during the first two years of operation. The purpose is to determine empirically the amount of real-environment data which has to be prepared to build a system with reasonable speech recognition performance and response accuracy. Furthermore, the relative importance of developing the main system components, i.e. speech recognizer and the response generation module, is assessed. Although depending on the system's modeling capacities and domain complexity, experimental results show that overall performance stagnates after employing about 10-15 k utterances for training the acoustic model, 40-50 k utterances for training the language model and 40 k-50 k utterances for compiling the question and answer database. The Q&A database was most important for improving the system's response accuracy. Finally, the portability of the well-trained first system prototype for a different environment, a local subway station, is investigated. Since collection and preparation of large amounts of real data is impractical in general, only one month of data from the new environment is employed for system adaptation. While the speech recognition component of the first prototype has a high degree of portability, the response accuracy is lower than in the first environment. The main reason is a domain difference between the two systems, since they are installed in different environments. This implicates that it is imperative to take the behavior of users under real conditions into account to build a system with high user satisfaction.

Energy-efficiency is one of the main concerns in the wireless information dissemination system. This paper presents a wireless broadcast stream organization scheme which enables complex queries (e.g., aggregation queries) to be processed in an energy-efficient way. For efficient processing of complex queries, we propose an approach of broadcasting their pre-computed results with the data stream, wherein the way of replication of index and pre-computation results are investigated. Through analysis and experiments, we show that the new approach can achieve significant performance enhancement for complex queries with respect to the access time and tuning time.

Normalization transform is known to be very useful for finding the overall trend of time-series data since it enables finding sequences with similar fluctuation patterns. Previous subsequence matching methods with normalization transform, however, would incur index overhead both in storage space and in update maintenance since they should build multiple indexes for supporting query sequences of arbitrary length. To solve this problem, we adopt a single-index approach in the normalization-transformed subsequence matching that supports query sequences of arbitrary length. For the single-index approach, we first provide the notion of inclusion-normalization transform by generalizing the original definition of normalization transform. To normalize a window, the inclusion-normalization transform uses the mean and the standard deviation of a subsequence that includes the window while the original transform uses those of the window itself. Next, we formally prove the correctness of the proposed normalization-transformed subsequence matching method that uses the inclusion-normalization transform. We then propose subsequence matching and index-building algorithms to implement the proposed method. Experimental results for real stock data show that our method improves performance by up to 2.52.8 times compared with the previous method.

In this paper, we present a novel method to incorporate metadata into data mining. The method has many advantages. It can be completed automatically and is independent of a specific database. Firstly, we convert metadata into ontology. Then input a rule set to a reasoner, which supports rule-based inference over the ontology model. The outputs of the reasoner describe the prior knowledge in metadata. Finally, incorporate the prior knowledge into data mining.

This paper proposes a Mel-Wiener filter to enhance Mel-LPC spectra in the presence of additive noise. The transfer function of the proposed filter is defined by using a first-order all-pass filter instead of unit delay. The filter coefficients are estimated based on minimization of the sum of the square error on the linear frequency scale without applying the bilinear transformation and efficiently implemented in the autocorrelation domain. The proposed filter does not require any time-frequency conversion, which saves a large amount of computational load. The performance of the proposed system is comparable to that of ETSI AFE. The optimum filter order is found to be 3, and thus filtering is computationally inexpensive. The computational cost of the proposed system except VAD is 53% of ETSI AFE.

One of the system greatly affecting the performance of a database server is the size-division of buffer pools. This letter proposes an adaptive control method of the buffer pool sizes. This method obtains the nearly optimal division using only observed response times in a comparatively short duration.