High-utility itemset mining (HUIM) is an advanced problem of frequent itemset mining, considering the frequency of occurrence and quantitative criteria such as unit profit. Because HUIM can be applied to a broad spectrum of knowledge discovery work, various algorithmic improvements have been studied over the past two decades. On the other hand, limited efforts have been made to take advantage of hardware performance despite significant changes in hardware trends. This paper presents a novel parallelization method called DPHIM (Dynamic Parallelization for High-utility Itemset Mining). DPHIM dynamically decomposes a high-utility itemset mining task into subtasks to utilize logical parallelism and carefully assigns the subtasks and their related data to physical resources such as processing cores and nearby memory in a NUMA-aware manner. Through rigorous and diverse experiments, we found that DPHIM achieved speeds up to 72.7 times faster than the fully tuned serial execution, up to 23.5 times faster than static partitioning, and up to 2.5 times faster than the best case of alternative dynamic parallel executions for a variety of datasets and configurations on DRAM. We also demonstrated that DPHIM effectively worked on persistent memory; it offered similar thread scalability trends and was 1.1 to 2.4 times slower on persistent memory.

This paper introduces LakeHarbor, a new data management paradigm that makes structures (e.g., indexes) first-class citizens in data lakes. The LakeHarbor paradigm enables a data lake system to flexibly construct structures based on registered access method functions and execute data processing jobs efficiently with the potential parallelism that the structures inherently hold by exploiting the functions while not sacrificing flexible data processing such as schema-on-read. This paper also presents ReDe, a prototype data processing engine that implements LakeHarbor, and a motivating evaluation and a case study of ReDe to explore the potential of LakeHarbor.

High-utility itemset mining is a generalized problem of well-known frequent itemset mining, which considers not only the frequency of occurrence but also quantitative criteria such as unit profit. Because it can be applied to a wider spectrum of knowledge discovery work, various algorithmic improvements have been studied over the past two decades. On the other hand, limited efforts have been made to take advantage of hardware performance despite significant changes in hardware trends. This paper presents a novel parallelization method called DPHIM (Dynamic Parallelization for High-utility Itemset Mining). DPHIM dynamically decomposes the execution of high-utility itemset mining into subtasks in order to leverage logical data parallelism, and carefully assigns the subtasks and their related data to physical resources such as processing cores and nearby memory in the NUMA-aware manner. Our intensive and extensive experiments have confirmed that DPHIM performs up to 65.23 times faster than the fully-tuned serial execution, up to 23.54 times faster than static partitioning, and up to 2.51 times faster than the best case of alternative dynamic parallel executions for a variety of datasets and configurations on DRAM. As well, we have demonstrated that DPHIM effectively worked on persistent memory; it offered similar thread scalability trends and was 1.07 to 2.43 times slower on persistent memory.

High-utility itemset mining is a generalized problem of well-known frequent itemset mining, which considers not only the frequency of occurrence but also quantitative criteria such as unit profit. Because it can be applied to a wider spectrum of knowledge discovery work, various algorithmic improvements have been studied over the past two decades. On the other hand, limited efforts have been made to take advantage of hardware performance despite significant changes in hardware trends. This paper presents a novel parallelization method called DPHIM (Dynamic Parallelization for High-utility Itemset Mining). DPHIM dynamically decomposes the execution of high-utility itemset mining into subtasks in order to leverage logical data parallelism, and carefully assigns the subtasks and their related data to physical resources such as processing cores and nearby memory in the NUMA-aware manner. Our intensive and extensive experiments have confirmed that DPHIM performs up to 65.23 times faster than the fully-tuned serial execution, up to 23.54 times faster than static partitioning, and up to 2.51 times faster than the best case of alternative dynamic parallel executions for a variety of datasets and configurations on DRAM. As well, we have demonstrated that DPHIM effectively worked on persistent memory; it offered similar thread scalability trends and was 1.07 to 2.43 times slower on persistent memory.

Hash joins and sort-merge joins have been considered the algorithms of choice for analytical relational queries in most parallel database systems because of their performance robustness and ease of parallelization. On the other hand, nested loop joins have been considered less attractive and are conservatively used. In this paper, we revisit the potential of nested loop joins in a cluster environment. We focus on exploring the parallelism aspect of nested loop joins because there could still be space for improvement by fully exploiting the parallelism of current commodity hardware, which could handle more than thousands of concurrent IOs. We also introduce scalable massively-parallel execution as one of the approaches for achieving massive parallelism in nested loop joins to explore how it widens the potential benefit of nested loop joins. Finally, we discuss future research directions based on our exploration.

This panel considers the role of the database research community in addressing humanity's greatest challenges. Are we an innovation engine, tool providers, or are we standing on the side while other research communities take the lead?

Twitter is currently one of the most influential microblogging services on which users interact with messages. It is imperative to grasp the big picture of Twitter through analyzing its huge stream data. In this study, we develop a two-stage clustering method that automatically discovers coarse-grained topics from Twitter data. In the first stage, we use graph clustering to extract micro-clusters from the word co-occurrence graph. All the tweets in a micro-cluster share a fine-grained topic. We then obtain the time series of each micro-cluster by counting the number of tweets posted in a time window. In the second stage, we use time series clustering to identify the clusters corresponding to coarse-grained topics. We evaluate the computational efficacy of the proposed method and demonstrate its systematic improvement in scalability as the data volume increases. Next, we apply the proposed method to large-scale Twitter data (26 million tweets) about the COVID-19 Vaccination in Japan. The proposed method separately identifies the reactions to news and the reactions to tweets.

Periodic-frequent pattern mining (PFPM) is an important data mining model having many real-world applications. However, the successful industrial application of this model has been hindered by the problem of combinatorial explosion of patterns, that is the generation of too many redundant patterns, most of which may be useless to the user. To address this problem, this paper proposes a novel model of maximal periodic- frequent pattern that may exist in a temporal database. A new pattern-growth algorithm, called Maximum Periodic-Frequent Pattern-growth (maxPFP-growth), has also been introduced to efficiently find all desired patterns in the data. Experimental results demonstrate that maxPFP-growth is not only memory and runtime efficient, but also highly scalable as well. The usefulness of our model has also been demonstrated with a case study on traffic congestion analytics.

Frequent pattern mining is an important model in data mining. It involves finding all patterns in a transactional database that satisfy the user-specified minimum support (minSup) constraint. The minSup controls the minimum number of transactions that a pattern must cover in a transactional database. Since only minSup is used to evaluate a pattern's interestingness, the frequent pattern model implicitly assumes that spatial information of the items will not impact the interestingness of a pattern in the database. This assumption limits the applicability of the frequent pattern model in many real-world applications. It is because patterns whose items are close to each other are typically more attractive to the user than the patterns whose items are far from each other in a coordinate system. With this motivation, this paper proposes a novel model of frequent spatial pattern that may exist in a spatiotemporal database. An efficient pattern-growth algorithm, called Frequent Spatial Pattern-growth (FSP-growth), has also been presented to mine all desired patterns in a database. Experimental results demonstrate that our algorithm is efficient. The usefulness of the proposed patterns has also been shown with a real-world application.

How can recommender systems help people improve their skills? As a first step toward recommendation for the upskilling of users, this paper addresses the problems of modeling the improvement of user skills and the difficulty of items in action sequences where users select items at different times. We propose a progression model that uses latent variables to learn the monotonically non-decreasing progression of user skills. Once this model is trained with the given sequence data, we leverage it to find a statistical solution to the item difficulty estimation problem, where we assume that users usually select items within their skill capacity. Experiments on five datasets (four from real domains, and one generated synthetically) revealed that (1) our model successfully captured the progression of domain-dependent skills; (2) multi-faceted item features helped to learn better models that aligned well with the ground-truth skill and difficulty levels in the synthetic dataset; (3) the learned models were practically useful to predict items and ratings in action sequences; and (4) exploiting the dependency structure of our skill model for parallel computation made the training process more efficient.

Intra-query parallelism is a key for database software to offer acceptable responsiveness for data-intensive queries. Many researchers have studied how to achieve greater execution parallelism for database queries. Partitioning is a representative approach, which divides a query into multiple sub-tasks and executes them in parallel. However, given a new query, optimal division is not necessarily obvious. Database software utilizes heuristic rules or statistical information to decide how to divide the query before execution. As yet another approach to achieve execution parallelism, this paper presents out-of-order database execution (OoODE), a massively-parallel query execution method to offer significant speedup for database queries consistently. OoODE dynamically decomposes query work by making the best use of the exact knowledge of the potential execution parallelism for each operation ready to be performed during query execution. With OoODE, the database software is allowed to automatically squeeze out the execution parallelism that the query inherently holds. Hence, for a wide spectrum of queries, OoODE performs significantly faster than the serial (non-parallelized) execution, while it performs better than or comparably with alternative parallelizing methods without the need for dividing the query before execution. This paper presents the experiments that we conducted using the prototyped database software and demonstrates that OoODE is two to three orders of magnitude faster than the serial execution, whereas it is substantially (up to 2.07 times) faster than the best achievable case of partitioning. Besides, OoODE performs two to four orders of magnitude faster than major DBMSs.

Finding partial periodic patterns in very large databases is a challenging problem of great importance in many real-world applications. Most previous work focused on finding these patterns in temporal (or transactional) databases and did not recognize the spatial characteristics of items. In this paper, we propose a more flexible model of partial periodic spatial pattern that may be present in spatiotemporal database. Three constraints, maximum inter-arrival time(maxIAT), minimum period-support(minPS) and maximum distance(maxDist), have been employed to determine the interestingness of a pattern in a spatiotemporal database. The maxIAT controls the maximum duration in which a pattern must reappear to consider its occurrence as periodic within the data. The minPS controls the minimum number of periodic occurrences of a pattern within the data. The maxDist controls the maximum distance between the items in a pattern. All patterns satisfying these three constraints are returned. An efficient algorithm, called SpatioTemporal-Equivalence CLAss Transformation (ST-ECLAT), has also been described to discover all partial periodic spatial patterns in a spatiotemporal database. This algorithm employs a novel smart depth-first search technique to discover desired patterns effectively. Experimental results demonstrate that the proposed algorithm is efficient. We also present a case study in which we apply our model to find useful information in the air pollution database.

Understanding the spread of diseases and the use of medicines is of practical importance for various organizations, such as medical providers, medical payers, and national governments. This study aims to detect the change in the prescription trends and to identify its cause through an analysis of Medical Insurance Claims (MICs), which comprise the specifications of medical fees charged to health insurers. Our approach is two-fold. (1) We propose a latent variable model that simulates the medication behavior of physicians to accurately reproduce monthly prescription time series from the MIC data, where prescription links between the diseases and medicines are missing. (2) We apply a state space model with intervention variables to decompose the monthly prescription time series into different components including seasonality and structural changes. Using a large dataset consisting of 3.5-year MIC records, we conduct experiments to evaluate our approach in terms of accuracy, usefulness, and efficiency. We also demonstrate three applications for our medical analysis.

In real-world databases, high utility itemset (HUI) is an important class of regularities. Most previous studies have focused on mining HUIs in transactional databases and did not consider the spatiotemporal characteristics of items. In this study, a more flexible model of spatial HUIs (SHUIs) that exist in spatiotemporal databases is proposed. In a spatiotemporal database (STD), an itemset is said to be an SHUI if its utility is not less than a user-specified minimum utility and the distance between any two of its items is not more than a user-specified maximum distance. Identifying SHUIs is very challenging because the generated itemsets do not satisfy the anti-monotonic property. In this study, we present two novel pruning techniques for reducing computational costs. Moreover, a fast single scan algorithm is presented for effectively evaluating all SHUIs in a STD. Furthermore, two case studies are presented, in which the proposed model is used to identify useful information in traffic congestion data and air pollution data.

Weighted Frequent Itemset (WFI) mining is an important model in data mining. The popular adoption and successful industrial application of this model has been hindered by the following two obstacles: (i) finding WFIs is a computationally expensiveness process as these itemsets do not satisfy the downward closure property and (ii) lack of parallel algorithms to find WFIs in very large databases (e.g. astronomical data and twitter data). This paper makes an effort to address these two obstacles. Two pattern-growth algorithms, Sequential Weighted Frequent Pattern-growth and Parallel Weighted Frequent Pattern-growth, have been introduced to discover WFIs efficiently. Both algorithms employ three novel pruning techniques to reduce the computational cost effectively. The first pruning technique prunes some of the uninteresting items by employing a criterion known as cutoff weight. The second pruning technique, called conditional pattern base elimination, eliminates the construction of conditional pattern bases if a suffix item is an uninteresting item. The third pruning technique, called pattern-growth termination, defines a new terminating condition for the pattern-growth technique. Experimental results demonstrate that the proposed algorithms are memory and runtime efficient, and highly scalable as well.

Japan is launching `Society 5.0', the vision for a future smarter society. One of the fundamental pillars of Society 5.0 is to help the society become smarter in a data-driven way. Through the advance of Internet of Things (IoT), the rapidly growing big data is substantially transforming our society, for example, through smarter commercial products and services. In this talk, we will focus on the role of big data in providing smarter services for societal benefits, with special emphases on disaster management and socialized healthcare. In accordance to Sustainable Development Goals (a United Nations initiative), our solution frameworks are being deployed both in Japan and partner developing countries.

In data-parallel computing that uses a graphic processing unit (GPU), processing of large data requires that multiple GPUs be used in the computer to increase its execution performance. Increasing processing performance by using multiple computing resources has been enabled by the development of computing frameworks based on a directed acyclic graph (DAG). However, their performance degrades in out-of-core processing, which often occurs in processing of large data on GPUs with limited memory capacity. The GPU data input/output (I/O) for data swapping between host memory and GPU memory during the execution of a user DAG is usually a performance bottleneck. A computing framework called "Victream" is proposed to overcome this drawback. It uses a novel scheduler that involves two methods to minimize the total amount of GPU data I/O of data swapping. First, it performs locality-aware scheduling. When it schedules a task, it selects one that requires the minimum amount of data swapping and reuses as much of the data residing in GPU memory as possible. Second, it extends the locality-aware scheduling so that GPUs can execute data prefetching. Prefetching data that are swapped out from a GPU enables efficient use of bottleneck GPU I/O resources. To prefetch the input data of future tasks, it is required to determine the schedule of future tasks. Victream's scheduler (hereafter, the Victream scheduler) extends the locality-aware scheduling so that it can schedule future tasks to enable data prefetching that is executed in the way that minimizes the amount of data I/O of data swapping. Evaluation of a Victream prototype showed that the performance of Victream is better than that of conventional frameworks by up to 117%.

Traffic accidents are still troubling our society. The number of drive recorders sold has increased, and therefore we can collect large-scale vehicle recorder data to be used to support traffic safety. We have developed a system for detecting potentially risky crossroads on the basis of vehicle recorder data, road shapes, and weather information. Visualization combining space and time in a single display called a “space time cube (STC)” helps us to understand and analyze spatio-temporal mobility data on caution crossroads. The STC enables us to simultaneously explore not only shapes and positions of vehicle trajectories but also their temporal distributions. However, it is difficult for users to manually find good viewpoints for understanding such characteristics of trajectories. In this paper, we propose an optimal viewpoint selection method for visualizing spatio-temporal characteristics of vehicle trajectories on a large set of crossroads using an STC. Major contributions of this paper are as follows: (1) We provide an algorithm based on viewpoint entropy weighted by angles of trajectories with a horizontal line as a measure of a viewpoint quality on a projected 2D image. (2) We demonstrate our solution can be adapted to crossroads with different trajectory shapes. We also extend the proposed method to find an optimal viewpoint for multiple crossroads. (3) We verify the proposed method through users' evaluations. (4) We construct an overviewing catalog of potentially risky crossroads detected from real vehicle recorder big data to discuss and analyze them with stakeholders.

A temporal database is a collection of transactions, ordered by their timestamps. Discovering partial periodic itemsets in temporal databases has numerous applications. However, to the best of our knowledge, no work has considered finding these itemsets in temporal databases, despite that this type of data is very common in real-life. Discovering partial periodic itemsets in temporal databases is challenging. It requires defining (i) an appropriate measure to assess the periodic interestingness of itemsets, and (ii) an algorithm to efficiently find all partial periodic itemsets. While a pattern-growth algorithm can be employed for the second sub-task, the first sub-task has not been addressed. Moreover, how these two tasks are combined has significant implications. In this paper, we address this challenge. We introduce a model to find partial periodic itemsets in temporal databases. A new measure, called periodic-frequency, has been proposed to determine the periodic interestingness of itemsets by taking into account their number of cyclic repetitions in the entire data. Moreover, the paper introduces a pattern-growth algorithm to discover all partial periodic itemsets. Experimental results demonstrate that our model is efficient.

Rapidly escalating energy and cooling costs of storage systems have become a concern for data centers. In response, a multitude of energy saving approaches that take into account storage-device-level input/output (I/O) behaviors has been proposed. The trouble is that critical applications are in constant operation at data centers, and the conventional approaches do not produce sufficient energy savings. It may be possible to dramatically reduce storage energy consumption without degrading application performance levels by utilizing application level I/O behaviors. However, such behaviors differ from one application to another, and it would be too expensive to tailor methods to individual applications. We propose a universal storage energy management framework for runtime storage energy savings that can be applied to any type of application. The results of evaluations show that the use of this framework results in substantive energy savings compared with the traditional approaches.

It is vital for the transportation industry, which performs most of their work by automobiles, to reduce its number of traffic accidents. Many local governments in Japan have made potential risk maps of traffic accident spots. However, making such maps in wide areas and with the time information had been difficult because most of them are made based on an investigation. Utilizing long-term driving records can extract wide area spatio-temporal caution spots. This paper proposes a visual interaction method for exploring caution spots from large-scale vehicle recorder data. Our method provides (i) a flexible filtering interface for driving operations using various combinations of attribute values such as velocity and acceleration, and (ii) a 3D visual environment for spatio-temporal exploration of caution spots. We demonstrate the usefulness of our novel visual exploration environment using real data given by one of the biggest transportation companies in Japan. Exploration results show our environments can extract caution spots where some accidents have actually occurred or that are on very narrow roads with bad visibility.

The development of cloud storage and computing has facilitated the rise of various big data applications. As a representative high performance computing (HPC) workload, graph processing is becoming a part of cloud computing. However, scalable computing on large graphs is still dominated by HPC solutions, which require high performance all-to-all collective operations over torus (or mesh) networking. Implementing those torus-based algorithms on commodity clusters, e.g., cloud computing infrastructures, can result in great latency due to inefficient communication. Moreover, designing a highly scalable system for large social graphs, is far from being trivial, as intrinsic features of social graphs, e.g., degree skewness and lacking of locality, often profoundly limit the extent of parallelism.

Partial periodic patterns are an important class of regularities that exist in a time series. A key property of these patterns is that they can start, stop, and restart anywhere within a series. We classify partial periodic patterns into two types: (i) regular patterns−patterns exhibiting periodic behavior throughout a series with some exceptions and (ii) recurring patterns−patterns exhibiting periodic behavior only for particular time intervals within a series. Past studies on partial periodic search have been primarily focused on finding regular patterns. One cannot ignore the knowledge pertaining to recurring patterns. This is because they provide useful information pertaining to seasonal or temporal associations between events. Finding recurring patterns is a non-trivial task because of two main reasons. (i) Each recurring pattern is associated with temporal information pertaining to its durations of periodic appearances in a series. Obtaining this information is challenging because the information can vary within and across patterns. (ii) Finding all recurring patterns is a computationally expensive process since they do not satisfy the anti-monotonic property. In this paper, we propose recurring pattern model by addressing the above issues. We also propose Recurring Pattern growth algorithm along with an efficient pruning technique to discover these patterns. Experimental results show that recurring patterns can be useful and that our algorithm is efficient.

Many update queries on a database can eventually degrade the structural efficiency of the database and result in lower performance. This phenomenon is called aging. On aged databases, conventional cost-based query optimizers could choose non-optimal query execution plan because they are not aging-aware and could not accurately estimate query execution cost.

Non-communicable diseases (NCDs) are no longer just a problem for high-income countries, but they are also a problem that affects developing countries. Preventive medicine is definitely the key to combat NCDs; however, the cost of preventive programs is a critical issue affecting the popularization of these medicine programs in developing countries. In this study, we investigate predictive modeling for providing a low-cost preventive medicine program. In our two-year-long field study in Bangladesh, we collected the health checkup results of 15,075 subjects, the data of 6,607 prescriptions, and the follow-up examination results of 2,109 subjects. We address three prediction problems, namely subject risk prediction, drug recommendation, and future risk prediction, by using machine learning techniques; our multiple-classifier approach successfully reduced the costs of health checkups, a multi-task learning method provided accurate recommendation for specific types of drugs, and an active learning method achieved an efficient assignment of healthcare workers for the follow-up care of subjects.

Rapidly escalating energy and cooling costs, especially those related to the energy consumption of storage systems, have become a concern for data centers, primarily because the amount of digital data that needs storage is increasing daily. In response, a multitude of energy saving approaches that take into account storage-device-level input/output (I/O) behaviors have been proposed. The trouble is that numerous critical applications such as database systems or web commerce applications are in constant operation at data centers, and the conventional approaches that only utilize storage-device-level I/O behaviors do not produce sufficient energy savings. It may be possible to dramatically reduce storage-related energy consumption without degrading application performance levels by utilizing application-level I/O behaviors. However, such behaviors differ from one application to another, and it would be too expensive to tailor methods to individual applications. As a way of solving this problem, we propose a universal storage energy management framework for runtime storage energy savings that can be applied to any type of application. The results of evaluations show that the use of this framework results in substantive energy savings compared with the traditional approaches that are used while applications are running.

Transportation systems in mega-cities are often affected by various kinds of events such as natural disasters, accidents, and public gatherings. Highly dense and complicated networks in the transportation systems propagate confusion in the network because they offer various possible transfer routes to passengers. Visualization is one of the most important techniques for examining such cascades of unusual situations in the huge networks. This paper proposes visual integration of traffic analysis and social media analysis using two forms of big data: smart card data on the Tokyo Metro and social media data on Twitter. Our system provides multiple coordinated views to visually, intuitively, and simultaneously explore changes in passengers' behavior and abnormal situations extracted from smart card data and situational explanations from real voices of passengers such as complaints about services extracted from social media data. We demonstrate the possibilities and usefulness of our novel visualization environment using a series of real data case studies about various kinds of events.

Data driven scientific discovery approach has already been agreed to be an important emerging paradigm for computing in areas including social, service, Internet of Things (or sensor networks), and cloud. Under this paradigm, Big Data is the core that drives new researches in many areas, from environmental to social. There are many new scientific challenges when facing this big data phenomenon, ranging from capture, creation, storage, search, sharing, analysis, and visualization. The complication here is not just the storage, I/O, query, and performance, but also the integration across heterogeneous, interdependent complex data resources for real-time decision-making, collaboration, and ultimately value co-creation. Data sciences encompass the larger areas of data analytics, machine learning and managing big data. Advanced data analytics has become essential to glean a deep understanding of large data sets and to convert data into actionable intelligence. With the rapid growth in the volumes of data available to enterprises, Government and on the web, automated techniques for analyzing the data have become essential.

Many recent large-scale data intensive applications are increasingly demanding efficient graph databases. Distributed graph algorithms, as a core part of practical graph databases, have a wide range of important applications, but have been rarely studied in sufficient detail. These problems are challenging as real graphs are usually extremely large and the intrinsic character of graph data, lacking locality, causes unbalanced computation and communication workloads.

Coverage pattern mining is an important model in data mining. It provides useful information pertaining to the sets of items that have coverage interesting to the users in a transactional database. The coverage patterns do not satisfy the anti-monotonic property. This increases the search space in the itemset lattice, which in turn increases the computational cost of mining these patterns. An Apriori-like algorithm known as CMine has been proposed in the literature to discover the patterns. It employs a pruning technique to reduce the search space. We have observed that there exists further scope for reducing the search space effectively. In this paper, we theoretically analyze different measures used in the pattern model, and introduce a novel pruning technique to reduce the search space. An Apriori-like algorithm, called CMine++, has also been proposed to discover the patterns. The performance study shows that mining coverage patterns with CMine++ is efficient.

Finding the skyline in a multi-dimensional space is relevant to a wide range of applications. The skyline operator over a set of d -dimensional points selects the points that are not dominated by any other point on all dimensions. Therefore, it provides a minimal set of candidates for the users to make their personal trade-off among all optimal solutions. The existing algorithms establish both the worst case complexity by discarding distributions and the average case complexity by assuming dimensional independence. However, the data in the real world is more likely to be anti-correlated. The cardinality and complexity analysis on dimensionally independent data is meaningless when dealing with anti-correlated data. Furthermore, the performance of the existing algorithms becomes impractical on anti-correlated data. In this paper, we establish a cardinality model for anti-correlated distributions. We propose an accurate polynomial estimation for the expected value of the skyline cardinality. Because the high skyline cardinality downgrades the performance of most existing algorithms on anti-correlated data, we further develop a determination and elimination framework which extends the well-adopted elimination strategy. It achieves remarkable effectiveness and efficiency. The comprehensive experiments on both real datasets and benchmark synthetic datasets demonstrate that our approach significantly outperforms the state-of-the-art algorithms under a wide range of settings.

Power, especially that consumed for storing data, and cooling costs for data centers have increased rapidly. The main applications running at data centers are data intensive applications such as large file servers or database systems. Recently, power management of the data intensive applications has been emphasized in the literature. Such reports discuss the importance of power savings. However, these reports lack research on power management models for the efficient use of data intensive applications' I/O behaviors. This paper proposes a novel energy efficient storage management system that monitors both application- and device-level I/O patterns at run time, and uses not only the device-level I/O pattern but also application level patterns. First, the design of the proposed model combined with such large data intensive applications will be shown. The key features of the model are i) classifying application-level I/O into four patterns using run-time access behaviors such as the length of idle time and read/write frequency, and ii) adopting an appropriate power-saving method-based on these application level I/O patterns. Next, the proposed method is quantitatively evaluated with typical data intensive applications such as file servers, OLTP, and DSS. It is shown that energy efficient storage management is effective in achieving large power savings compared with traditional approaches while an application is running.

IT program in Japan to build powerful engine for big data was launched. Quite recently the initial version is commercialized. This presentation will give a brief overview of the project. Also some of the potential applications will be introduced.

Despite the extensive number of studies for multimodal information fusion, the issue of determining the optimal modalities has not been adequately addressed yet. In this study, a RELIEF-based multimodal feature selection approach (RELIEF-RDR) is proposed. The original RELIEF algorithm is extended for weaknesses in three major issues; multi-labeled data, noise and class-specific feature selection. To overcome these weaknesses, discrimination based weighting mechanism of RELIEF is supported with two additional concepts; representation and reliability capabilities of features, without an increase in computational complexity. These capabilities of features are exploited by using the statistics on dissimilarities of training instances. The experiments conducted on TRECVID 2007 dataset validated the superiority of RELIEF-RDR over RELIEF.

Graphs are fundamental data structures and have been employed for centuries to model real-world systems and phenomena. Random walk with restart (RWR) provides a good proximity score between two nodes in a graph, and it has been successfully used in many applications such as automatic image captioning, recommender systems, and link prediction. The goal of this work is to find nodes that have top-k highest proximities for a given node. Previous approaches to this problem find nodes efficiently at the expense of exactness. The main motivation of this paper is to answer, in the affirmative, the question, 'Is it possible to improve the search time without sacrificing the exactness?'. Our solution, K-dash , is based on two ideas: (1) It computes the proximity of a selected node efficiently by sparse matrices, and (2) It skips unnecessary proximity computations when searching for the top-k nodes. Theoretical analyses show that K-dash guarantees result exactness. We perform comprehensive experiments to verify the efficiency of K-dash. The results show that K-dash can find top-k nodes significantly faster than the previous approaches while it guarantees exactness.

Duplicates in data streams may often be observed by the projection on a subspace and/or multiple recordings of objects. Without the uniqueness assumption on observed data elements, many conventional aggregates computation problems need to be further investigated due to their duplication-sensitive nature. In this paper, we present novel, space-efficient, one-scan algorithms to continuously maintain duplicate-insensitive order sketches so that rank-based queries can be approximately processed with a relative rank error guarantee \epsilon in the presence of data duplicates. Besides the space efficiency, the proposed algorithms are time-efficient and highly accurate. Moreover, our techniques may be immediately applied to the heavy hitter problem against distinct elements and to the existing fault-tolerant distributed communication techniques. A comprehensive performance study demonstrates that our algorithms can support real-time computation against high-speed data streams.

This work addresses a novel spatial keyword query called the m-closest keywords (mCK) query. Given a database of spatial objects, each tuple is associated with some descriptive information represented in the form of keywords. The mCK query aims to find the spatially closest tuples which match m user-specified keywords. Given a set of keywords from a document, mCK query can be very useful in geotagging the document by comparing the keywords to other geotagged documents in a database. To answer mCK queries efficiently, we introduce a new index called the bR*-tree, which is an extension of the R*-tree. Based on bR*-tree, we exploit a priori-based search strategies to effectively reduce the search space. We also propose two monotone constraints, namely the distance mutex and keyword mutex, as our a priori properties to facilitate effective pruning. Our performance study demonstrates that our search strategy is indeed efficient in reducing query response time and demonstrates remarkable scalability in terms of the number of query keywords which is essential for our main application of searching by document.

Hidden Markov models (HMMs) are receiving considerable attention in various communities and many applications that use HMMs have emerged such as mental task classification, biological analysis, traffic monitoring, and anomaly detection. This article has two goals; The first goal is exact and efficient identification of the model whose state sequence has the highest likelihood for the given query sequence (more precisely, no HMM that actually has a high-probability path for the given sequence is missed by the algorithm), and the second goal is exact and efficient monitoring of streaming data sequences to find the best model. We propose SPIRAL, a fast search method for HMM datasets. SPIRAL is based on three ideas; (1) it clusters states of models to compute approximate likelihood, (2) it uses several granularities and approximates likelihood values in search processing, and (3) it focuses on just the promising likelihood computations by pruning out low-likelihood state sequences. Experiments verify the effectiveness of SPIRAL and show that it is more than 490 times faster than the naive method.

The amount of information available on the Web has increased rapidly, reaching levels that few would ever have imagined possible. We live in what could be called the "information-explosion era," and this situation poses new problems for computer scientists. Users demand useful and reliable information from the Web in the shortest time possible, but the obstacles to fulfilling this demand are many including language barriers and the so-called "long tail." Even worse, users may provide only vague specifications of the information that they actually want, so that a more concrete specification must somehow be inferred by Web access tools. Natural language processing (NLP) is one of the key technologies for solving the above Web usability problems. Almost all the Web page provide with the essential information in the form of natural language texts, and the amount of these text information is huge. In order to offer solutions to these problems we must perform searching and extracting information from the Web texts using NLP technologies. The aim of this workshop: NLP Challenges in the Information Explosion Era (NLPIX 2008) is to bring researchers and practitioners together in order to discuss our most pressing needs with respect to accessing information on the Web, and to discuss new ideas in NLP technologies that might offer viable solutions for those issues.

In this paper, we investigated the problem of approximately processing rank queries against distinct data elements in a data stream with the presence of duplicated data elements. Novel space and time efficient techniques are developed for continuously maintaining order statistics so that rank queries can be answered with a relative error guarantee. This is the first work providing the space and time efficient data stream techniques to process approximate rank queries with relative error guarantees against distinct data elements.

In mobile ad-hoc peer-to-peer (M-P2P) networks, economic models become a necessity for enticing non-cooperative mobile peers to provide service. M-P2P users may issue queries with varying constraints on query response time, data quality of results and trustworthiness of the data source. This work proposes ConQuer, which addresses constraint queries in economy- based M-P2P networks. ConQuer proposes a broker-based incentive M-P2P model for handling user-defined constraint queries. It also provides incentives for MPs to form collaborative peer groups for maximizing data availability and revenues by mutually allocating and deallocating data items using a royalty-based revenue-sharing method. Such reallocations facilitate MPs in providing better data quality, thereby allowing them to further increase their revenues.

In recent years, there has been a prevalence of search engines being employed to find useful information in the Web as they efficiently explore hyperlinks between web pages which define a natural graph structure that yields a good ranking. Unfortunately, current search engines cannot effectively rank those relational data, which exists on dynamic websites supported by online databases. In this study, to rank such structured data (i.e., find the "best" items), we propose an integrated online system consisting of compressed data structure to encode the dominant relationship of the relational data. Efficient querying strategies and updating scheme are devised to facilitate the ranking process. Extensive experiments illustrate the effectiveness and efficiency of our methods. As such, we believe the work in this poster can be complementary to traditional search engines.

This paper proposes CADRE (collaborative allocation and deallocation of replicas with efficiency), a dynamic replication scheme for improving the typically low data availability in mobile ad-hoc peer-to-peer (M-P2P) networks. The main contributions of CADRE are two-fold. First, it collaboratively performs both replica allocation and deallocation in tandem to facilitate optimal replication and to avoid 'thrashing' conditions. Second, it addresses fair replica allocation across the MHs. CADRE deploys a hybrid super-peer architecture in which some of the MHs act as the 'gateway nodes' (GNs) in a given region. GNs facilitate both search and replication. Our performance study indicates that CADRE indeed improves query response times and data availability in M-P2P networks as compared to some recent existing schemes

Sequential pattern mining is very important because it is the basis of many applications. Yet how to efficiently implement the mining is difficult due to the inherent characteristic of the problem - the large size of the dataset. Although there has been a great deal of effort on sequential pattern mining in recent years, its performance is still far from satisfactory. In this paper, we have proposed a new algorithm called passed item deduced sequential pattern mining (abbreviated as PAID), which can efficiently get all the frequent sequential patterns from a large database. The main difference between our strategy and the existing works is that other algorithms accumulate the candidate support in each iteration from scratch, in contrast, PAID makes good use of the temporary results (support value) of k-length frequent patterns on discovering (k+1)-length patterns, which can reduce the search space greatly in mining sequential patterns. Our experimental results and performance studies show that PAID outperforms the previous works by meaningful margins on large datasets

Identifying and tracking new information on the Web is important in sociology, marketing, and survey research, since new trends might be apparent in the new information. Such changes can be observed by crawling the Web periodically. In practice, however, it is impossible to crawl the entire expanding Web repeatedly. This means that the novelty of a page remains unknown, even if that page did not exist in previous snapshots. In this paper, we propose a novelty measure for estimating the certainty that a newly crawled page appeared between the previous and current crawls. Using this novelty measure, new pages can be extracted from a series of unstable snapshots for further analysis and mining to identify new trends on the Web. We evaluated the precision, recall, and miss rate of the novelty measure using our Japanese web archive, and applied it to a Web archive search engine.

Broadcasting in wireless mobile computing environments is an effective technique to disseminate information to a massive number of clients equipped with powerful, battery operated devices. To conserve the usage of energy, which is a scarce resource, the information to be broadcast must be organized so that the client can selectively tune in at the desired portion of the broadcast. In this paper, the efficient, energy conserving transaction processing in mobile broadcast environments is examined with widely accepted approaches to indexed data organizations suited for a single item retrieval. The basic idea is to share the index information on multiple data items based on the predeclaration technique. The analytical and simulation studies have been performed to evaluate the effectiveness of our methodology, showing that predeclaration-based transaction processing with selective tuning ability can provide a significant performance improvement of battery life, while retaining a low access time. Tolerance to access failures during transaction processing is also described.

The ever-increasing popularity of mobile applications coupled with the prevalence of spatial data has created the need for efficient processing of spatial queries in mobile environments. While different types of spatial queries (e.g., spatial select queries, spatial join queries and nearest neighbour queries) need to be addressed in mobile environments, this work specifically addresses the processing of spatial select queries (i.e., window queries) on any k relations among N spatial relations. We designate such window queries on any k relations among N spatial relations as kNW queries. Notably, the processing of kNW queries is much more challenging in mobile environments than in traditional environments primarily due to the mobility of the clients which issue the queries to the respective base stations. The main contribution of this work is the proposal of the kNR-tree, a single integrated novel R-tree-based structure for indexing objects from N different spatial relations. Notably, the kNR-tree facilitates efficient processing of kNW queries. Our performance evaluation demonstrates that our proposed technique, which is based on the kNR-tree, is indeed effective in reducing the response times of kNW queries in mobile environments.

Association rule mining is a well known data mining technique that also applicable to spatial data. Here we systematically elaborate spatial association rule mining which focusing on the geo-word in order to analyze location related preferences of human users. We propose several categories of mining methodologies based on the items in the rule and rule generation process. Novel interestingness metrics are derived out of those mining methodologies to identify location specific characteristics such as local specialties and common words. An experiment on real access logs from a commercial yellowpage site is conducted to examine the effectiveness of those methodologies

We have proposed speculative locking (SL) protocols to improve the performance of distributed database systems (DDBSs) by trading extra processing resources. In SL, a transaction releases the lock on the data object whenever it produces corresponding after-image during its execution. By accessing both before and after-images, the waiting transaction carries out speculative executions and retains one execution based on the termination (commit or abort) mode of the preceding transactions. By carrying out multiple executions for a transaction, SL increases parallelism without violating serializability criteria. Under the naive version of SL, the number of speculative executions of the transaction explodes with data contention. By exploiting the fact that a submitted transaction is more likely to commit than abort, we propose the SL variants that process transactions efficiently by significantly reducing the number of speculative executions. The simulation results indicate that even with manageable extra resources, these variants significantly improve the performance over two-phase locking in the DDBS environments where transactions spend longer time for processing and transaction-aborts occur frequently.

We propose an edge capacity based on hub and authority scores, and examine the effects of using the edge capacity on the method for extracting Web communities using maximum flow algorithm proposed by G. Flake et al. (2000). A Web community is a collection of Web pages in which a common (or related) topic is taken up. In recent years, various methods for finding Web communities have been proposed. G. Flake et al.'s method, which is based on maximum flow algorithm, has a big advantages: "topic drift" does not easily occur. On the other hand, it sets the edge capacity to a fixed value for every edge, which is one of the major cause of failing to obtain a proper Web community. Our approach, which is using HITS score based edge capacity, effectively extracts Web pages retaining well-balanced in both global and local relations to the given seed node. We examined the effects by the experiments for randomly selected 20 topics using Web archives in Japan crawled in 2002. The result confirmed that the average precision rose approximately 20%.

Wireless data broadcast allows a large number of users to retrieve data simultaneously in mobile databases, resulting in an efficient way of using the scarce wireless bandwidth. However, the efficiency of data access methods is limited by an inherent property that data can only be accessed strictly sequentially by users. To properly cope with the inherent property, this paper presents three predeclaration-based transaction processing methods that yield a significant performance improvement in wireless data broadcast.

Clustering is currently one of the most crucial techniques for dealing (e.g. resources locating, information interpreting) with massive amount of heterogeneous information on the web. Unlike clustering in other fields, web page clustering separates unrelated pages and clusters related pages (to a specific topic) into semantically meaningful groups, which is useful for discrimination, summarization, organization and navigation of unstructured web pages. We have proposed a contents-link coupled clustering algorithm that clusters web pages by combining contents and link analysis. In this paper, we particularly study the effects of out-links (from the web pages), in-links (to the web page) and terms on the final clustering results as well as how to effectively combine these three parts to improve the quality of clustering results. We apply it to cluster web search results. Preliminary experiments and evaluations are conducted on various topics. As the experimental results show, the proposed clustering algorithm is effective and promising.

Personal computer/workstation (PC/WS) clusters have come to be studied intensively in the field of parallel and distributed computing. From the viewpoint of applications, data intensive applications including data mining and ad-hoc query processing in databases are considered very important for massively parallel processors, in addition to the conventional scientific calculation. Thus, investigating the feasibility of such applications on a PC cluster is meaningful. A PC cluster connected with a storage area network (SAN) is built and evaluated with a data mining application. In the case of a SAN-connected cluster, each node can access all shared disks directly without using a LAN; thus, SAN-connected clusters achieve much better performance than LAN-connected clusters for disk-to-disk copy operations. However, if a lot of nodes access the same shared disk simultaneously, application performance degrades due to the I/O-bottleneck. A runtime data declustering method, in which data is declustered to several other disks dynamically during the execution of the application, is proposed to resolve this problem.

The rapid growth of Internet access from mobile users has emphasised the importance of location specific information on the Web. A unique Web service called Mobile Info Search (MIS) from NTT Laboratories gathers information and provides location aware search facilities. We performed association rule mining and sequence pattern mining against an access log which was accumulated at the MIS site in order to get insight into the behavior of mobile users regarding spatial information on the Web. Details of the Web log mining process and the rules we derived are reported in this paper.

In recent years, several information retrieval methods using information about Web-links have been developed, such as HITS and trawling. In order to analyze Web-links dividing into links inside each Web site (local-links) and links between Web sites (global-links)for information retrieval, a proper model of the Web site is required. In existing research, a Web server is used as a model of the Web site. This idea works relatively well when a Web site corresponds to a server, as is the case for public Web sites, but works poorly when multiple Web sites correspond to a server, as is the case for private Web sites on rental Web servers. We propose a new model of the Web site, "directory-based site", to handle typical private sites, and a method to identify them using information about the URL and Web-links. We verify the method can approximately identify, at a rate of 66% of over 110,000 servers, whether each server has multiple directory-based sites or not, and extract over 500,000 directory-based sites and 4 million global-links by computational experiments using jp-domain URLs and Web-link data contains over 23 million URLs and 100 million Web-links, collected from July to August 2000, by Toyoda and Kitsuregawa. We also propose a new framework of Web-link based information retrieval that uses directory-based sites and global-links instead of Web pages and whole Web-links respectively, and examine the effectiveness of our framework by comparing a result of trawling on our framework to one on the existing framework.

The need for using spatial vector data for Web-based and mobile applications has been increasing rapidly. Vector spatial data is difficult to generalise (that is, to derive a suitable level of detail, or LoD, of the data for a given application). In a client-server environment, excessive details of spatial data cannot always be appreciated on the client side, but could consume a significant amount of resources on both the server and the client side, not to mention the extra cost of data transfer. Spatial data generalisation has been investigated extensively in the area of cartography. Most cartographical generalisation algorithms, however, are post-query operations where all the data, including unneeded data, is retrieved from the database for simplification. We incorporate spatial data simplification algorithms into query processing within DBMS. This novel approach targets primarily Web-based and mobile spatial applications that stand to benefit from early data reduction. Experiments on real data reveal significant performance improvements for our approach.

Proposes a new strategy called RING that utilizes a ring configuration of the range partition strategy to achieve efficient online data placement reorganization in shared-nothing environments. In the event of reorganization, it has been observed that the range partition strategy in its well-known linear configuration can lead to two main drawbacks: high reorganization costs and performance dependence on hotspot locations in a system. Thus, we modify the configuration into a ring, seeking to minimize the effect of these drawbacks. We also introduce a new standalone heat-balancing algorithm to support the ring configuration, where its migration decisions are deduced by taking into account reorganization costs while balancing a system. RING is based on simple but effective approaches that incur little overhead, so that performance is almost optimized for free. Our simulation results indicate that, under a wide range of requirements, performance can be considerably improved by modifying the underlying structure to support the ring configuration.

We present performance measurement results for a parallel SQL based information retrieval system implemented on a PC cluster system. We used the Web-TREC dataset under a left-deep query execution plan. We achieved satisfactory speed up.

The Web harbors a large number of community structures. Early detection of community structures has many purposes such as reliable searching and selective advertising. In this paper we investigate the problem of extracting and relating the web community structures from a large collection of Web-pages by performing hyper-link analysis. The proposed algorithm extracts the potential community signatures by extracting the corresponding dense bipartite graph (DBG) structures from the given data set of web pages. Further, the proposed algorithm can also be used to relate the extracted community signatures. We report the experimental results conducted on 10 GB TREC (Text REtrieval Conference) data collection that contains 1.7 million pages and 21.5 million links. The results demonstrate that the proposed approach extracts meaningful community signatures and relates them.

While Web search engines can retrieve information on the Web for a specific topic, users have to step a long ordered list in order to locate the needed information, which is often tedious and less efficient. We propose a new link-based clustering approach to cluster search results returned from Web search engines by exploring both co-citation and coupling. Unlike document clustering algorithms in IR that are based on common words/phrases shared among documents, our approach is based on common links shared by pages. We also extend the standard clustering algorithm, K-means, to make it more natural to handle noise and apply it to Web search results. By filtering some irrelevant pages, our approach clusters high quality pages in Web search results into semantically meaningful groups to facilitate users accessing and browsing. Preliminary experiments and evaluations are conducted to investigate its effectiveness. The experimental results show that link-based clustering of Web search results is promising and beneficial.

The authors propose an improved concurrency control protocol based on speculation for nested transactions and explain how it increases both intraand inter-transaction concurrency as compared to J.E.B. Moss's (1985) nested locking protocol. In the proposed speculative nested locking (SNL) protocol, whenever a sub-transaction finishes work with a data object (produces after-image), it's parent inherits the lock. The waiting sub-transaction carries out speculative executions by accessing both before- and after-images of preceding sub-transaction and selects appropriate execution after the termination of the preceding subtransaction. In this way, SNL allows multiple executions to be carried out for a transaction by trading extra processing and main memory resources to increase concurrency.

Parallel database systems are increasingly being deployed to support the performance demands of end-users. While declustering data across multiple nodes facilitates parallelism, initial data placement may not be optimal due to skewed workloads and changing access patterns. To prevent performance degradation, the placement of data must be reorganized, and this must be done on-line to minimize disruption to the system.

In the paper An Approach to Active Spatial Min- ing Based on Statistical Information, authors Wei Wang, Jiong Yang, and Richard Muntz propose data mining algo- rithm to efficiently support user-defined triggers on dy- namically evolving spatial data. It is shown that a new hi- erarchical triggering strategy which introduces subtriggers can improve the performance by three orders of magnitude compared with naive approach. The authors explored the new research area of active spatial mining. The paper A Database Approach for Modeling and Querying Video Data by Mohand-Said Hacid, Cyril De- cleir, and Jacques Kouloumdjian proposes the integrated

In recent years, OLAP technologies have become one of the important applications in the database industry. In particular, the datacube operation proposed in [5] receives strong attention among researchers as a fundamental research topic in the OLAP technologies. The datacube operation requires computation of aggregations on all possible combinations of each dimension attribute. As the number of dimensions increases, it becomes very expensive to compute datacubes, because the required computation cost grows exponentially with the increase of dimensions. Parallelization is very important factor for fast datacube computation. However, we cannot obtain sufficient performance gain in the presence of data skew even if the computation is parallelized. In this paper, we present a dynamic load balancing strategy, which enables us to extract the effectiveness of parallizing datacube computation sufficiently. We perform experiments based on simulations and show that our strategy performs well.

Computing datacubes requires multidimensional aggregations for all possible combinations of each dimension.In thii paper, we present a method to improve main memory utilization efficiency for an array-based algorithm for datacube computation in a MOLAP context.The problem with the array-based algorithm is in its sparsity, where a large pre portion of array cells are empty.,The algorithm proposed in [ZDN97] reduces this space inefficiency by compressing arrays on disk.We improve on this algorithm by performing compression of arrays in main memory as well as on disk using a hashing method, which allocates main memory according to the number of non-empty array cells.We further improve the algorithm using a dynamic main memory allocation strategy.The algorithm by [ZDN97] computes the multiple aggregate views simultaneously, which consumes a lot of main memory space.We propose a main memory allocation method that minimizes the main memory requirement by dynamically allocating main memory only to necessary aggregate views at run time.These savings in main memory resources result in the reduction of disk I/O cost.We evaluate the performance of the proposed method by disk I/O analysis and demonstrate that the improved MOLAP algorithm compares well with a ROLAP algorithm.Permission 10 make digital or hard copies of all or part of this work for personal ur classroom use is granted without fee pro$ided that copies arc not made or distributed for protit or comnwciai advantage and that cop&s bear this notice and the full citation on Ihc firS1 pa!& 'f0 COPY othemzise.to republish.to post on sewers or to redistribute to lists.requires prior specific prrmission an&W a fW.

The distributed shared memory (DSM) architecture is considered to be one of the most likely parallel computing environment candidate for the near future because of its ease of system scalability and facilitation for parallel programming. However, a naive program based on shared memory execution on a DSM machine often deteriorates performance, because of the overhead involved for maintaining cache coherency particularly with frequent remote memory accesses. We show that careful buffer management of parallel join processing on DSM can produce considerable performance improvements in comparison with a naive implementation. We propose four buffer management strategies for parallel hash join processing on the DSM architecture and actually implement them on the HP Exemplar SPP 1600. The basic strategy is to begin with the hash join algorithm for the shared everything architecture and then to consider the memory locality of DSM by distributing the hash table and data pool buffers among the nodes. The results of four buffering strategies are analyzed in detail. Consequently, we can conclude that, in order to achieve high performance on a DSM machine, our buffer management strategy in which the memory access pattern is extracted and buffers are allocated in the local memory of nodes to minimize memory access cost is very efficient.

Association rule mining recently attracted strong attention. Usually, the classification hierarchy over the data items is available. Users are interested in generalized association rules that span different levels of the hierarchy, since some-times more interesting rules can be derived by taking the hierarchy into account. In this paper, we propose the new parallel algorithms for mining association rules with classification hierarchy on a shared-nothing parallel machine to improve its performance. Our algorithms partition the candidate itemsets over the processors, which exploits the aggregate memory of the sys-tem effectively. If the candidate itemsets are partitioned without considering classification hierarchy, both the items and its all the ancestor items have to be transmitted, that causes prohibitively large amount of communications. Our method minimizes interprocessor communication by consid-ering the hierarchy. Moreover, in our algorithm, the avail-able memory space is fully utilized by identifying the fre-quently occurring candidate itemsets and copying them over all the processors, through which frequent itemsets can be processed locally without any communication. Thus it can effectively reduce the load skew among the processors. Sev-eral experiments are done by changing the granule of copying itemsets, from the whole tree, to the small group of the fre-quent itemsets along the hierarchy. The coarser the grain, the easier the control but it is rather difficult to achieve the sufficient load balance. The finer the grain, the more com-plicated the control is required but it can balance the load quite well. We implemented proposed algorithms on IBM SP-2. Per-formance evaluations show that our algorithms are effective for handling skew and attain sufficient speedup ratio. 1

This paper proposes a storage management scheme for disk arrays, named hot mirroring. In this scheme, storage space is partitioned into two regions. One is the mirrored region, which is characterized by high performance and low storage efficiency. The other is the RAID5 region, which is characterized by low performance and high storage efficiency. Hot data blocks are stored in the former area, while cold blocks are stored in the latter. In addition, mirrored pairs and RAID5 stripes are orthogonally laid out, through which the performance degradation during rebuilding is minimized. Hot block clustering in hot mirroring achieves higher performance than conventional RAID5 arrays. The potential of hot mirroring is examined through extensive simulation.

Article Free Access Share on GREO: a commercial database processor based on a pipelined hardware sorter Authors: Shinya Fushimi Information Systems Laboratory, Mitsubishi Electric Co., 5-1-1 Ofuna, Kamakura, Japan Information Systems Laboratory, Mitsubishi Electric Co., 5-1-1 Ofuna, Kamakura, JapanView Profile , Masaru Kitsuregawa Institute of Industrial Science, The University of Tokyo, 7-22-1 Roppongi, Tokyo, Japan Institute of Industrial Science, The University of Tokyo, 7-22-1 Roppongi, Tokyo, JapanView Profile Authors Info & Claims SIGMOD '93: Proceedings of the 1993 ACM SIGMOD international conference on Management of dataJune 1993Pages 449–452https://doi.org/10.1145/170035.170130Published:01 June 1993Publication History 9citation278DownloadsMetricsTotal Citations9Total Downloads278Last 12 Months16Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

The authors implemented a parallel hash join algorithm on a Symmetry S81 shared-everything multiprocessor environment and evaluated the performance. They evaluated the input/output (I/O) performance on a multiple-disk environment, and showed linear performance increase of up to eight disks. The performance of the implemented join operation was examined on each phase, and the effect of parallel processing by the multiprocessor and the multiple disks was clarified. It was concluded from the experimental result that on such a shared-everything multiprocessor system parallelism could be easily exploited for the construction of high-performance relational database systems.>

The performance of the functional disk system with relational database engine (FDS-R2) is evaluated in detail in view of two points. First, the performance evaluation of the combined hash algorithm on FDS-R2 is reported using the projection and aggregation operations in addition to the join operation and they are analyzed in order to verify the effectiveness of the proposed processing method, Second, several measured results of performance evaluations with the expanded version of the Wisconsin Benchmark are given and analyzed. FDS-R2 attained higher performance for very large relations as compared to other large database systems such as Gamma and Teradata. In this evaluation, it is also shown that the performance of the relational operations can be improved largely by using an efficient hashing strategy for large relations on FDS-R2.>

Concurrency-control scheduling of batch transactions on shared-nothing (or loosely-coupled) multiprocessor database machines is discussed. Various schedulers are tested for these batch transactions to examine how well they perform when both intertransaction parallelism and intratransaction parallelism are limited. New schedulers designed for batch transaction processing are outlined which use a new tool called a weighted transaction-precedence graph (WTPG). Simulation results show that two new schedulers (globally and locally optimized WTPG schedulers) are the best performers under various workloads.>

New concurrency control schemes are proposed for bulk access transactions (BATs) on shared-nothing database machines. A BAT is a transaction accessing a large bulk of data, such as a transaction updating a whole file. BATs are used for batch jobs in database services, and many BATs should be finished in a short time. Thus it is necessary to execute BATs concurrently on a database machine. When scheduling BATs, the performance is degraded by very high contention of both data and resources. Therefore, the strategy for scheduling BATs is to reduce the contention as much as possible. A weighted transaction precedence graph (WTPG) and two schedulers using it are proposed. A WTPG is used to estimate the degree of contention in a serializable schedule. Using a WTPG, the proposed schedulers reduced the contention by optimization. In the simulation, both schedulers achieve from 1.2 to 1.8 times higher throughput than atomic static lock and two-phase lock.>

Join algorithms on KD-tree indexed relations are proposed. The join algorithms are based on a concept called wave. The wave is a set of pages that is the object of joining and that propagates over the relation space in the direction of the join attribute axis. Four basic join algorithms that determine the wave from one of the relations and one algorithm that determines the wave from both relations are proposed. The algorithms are described and extensively analyzed with analytical formulas and simulation results. Then a garbage collection mechanism is introduced that discards the unnecessary data loaded in the main memory and extends the previous basic algorithms with an efficient memory management. It is shown that the proposed algorithms perform the join of very large relations with one scan.>

The second version of FDS-R (functional disk system with relational database engine), FDS-RII, which is designed to handle large relations efficiently, is discussed. On FDS-RII, the processing algorithm is selected at run time from two algorithms (nested loop algorithms, grace hash algorithm) by comparing their estimated I/O costs. The processing strategy is discussed in detail. The I/O cost formula is examined by measuring the execution time of a join query on the FDS-RII. With the expanded version of Wisconsin Benchmark, the performance of FDS-RII is measured. FDS-RII attained a high performance level for large relations as compared to other large database systems such as Gamma and Teradata. While FDS uses just one disk and three MC68020s, Teradata uses 40 disks and 20 AMPs and Gamma requires eight disks and 17 VAX 11/750s.>

The major performance bottle neck in the current computer system is in the low-performance secondary system. The performance of the CPU has increased dramatically so far, about several orders of magnitude improvement has been achieved. On the other hand, that of the disk system has shown little advance since nineteen sixties. The von Neumann bottle neck between the CPU and the secondary storage subsystem has been much more enlarged.

Article Free Access Share on Algorithm and performance evaluation of adaptive multidimensional clustering technique Authors: Shinya Fushimi Department of Electrical Engineering, University of Tokyo Department of Electrical Engineering, University of TokyoView Profile , Masaru Kitsuregawa Institute of Industrial Science, University of Tokyo Institute of Industrial Science, University of TokyoView Profile , Masaya Nakayama Department of Electrical Engineering, University of Tokyo Department of Electrical Engineering, University of TokyoView Profile , Hidehiko Tanaka Department of Electrical Engineering, University of Tokyo Department of Electrical Engineering, University of TokyoView Profile , Tohru Moto-oka Department of Electrical Engineering, University of Tokyo Department of Electrical Engineering, University of TokyoView Profile Authors Info & Claims SIGMOD '85: Proceedings of the 1985 ACM SIGMOD international conference on Management of dataMay 1985Pages 308–318https://doi.org/10.1145/318898.318928Published:01 May 1985Publication History 8citation361DownloadsMetricsTotal Citations8Total Downloads361Last 12 Months14Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF