Depression and bipolar disorder (BD) are mental disorders that are often misdiagnosed as each other because their symptoms often overlap. Depression is characterized by prolonged negative emotion, which is persistent feelings of sadness. In contrast, BD is characterized by repeated extreme changes of emotions, consisting of manic (very happy) and depression (very sad) episodes. Because of overlapping symptoms, changes of emotions indicating depression or BD are difficult to recognize from individual posts. We propose two deep learning models to detect depression and BD from user posts, considering individual posts and multiple posts. A novel method to extract emotion features is designed by fine-tuning a transformer model to extract the intensity of emotions of the posts. Text features are extracted using word embedding models that have been fine tuned on mental health data, and we further consider topic features by using a topic modeling method. Multiple posts are considered by grouping them based on a time interval between the posts. The features of each group are concatenated, input into a convolution neural network (CNN), and go through a long short-term memory (LSTM). The attention mechanism is used to pay attention to important groups. The most important groups can be observed further to explain why the model classified depression and BD users. Our proposed model outperforms other models, achieving an F1-Score of 0.9589. Based on our experiment, the changes of emotions within four days are necessary for distinguishing depression and BD, which aligns with considerations in diagnosing symptoms of depression and BD.

The number of children diagnosed with Autism Spectrum Disorder (ASD) is continually increasing. However, diagnosing autism is not straightforward; the process is lengthy and complex. Previous research has indicated that children with autism exhibit deficits in using language within social contexts, such as storytelling skills. Additionally, children with autism may display distinct patterns in certain acoustic features compared to typically developing (TD) children. With the advancement of computational models, we aim to employ deep neural network models to rapidly analyze the acoustic features of children’s narratives for detecting autism. In this study, we collected narrative data from 12 children with autism and 19 TD children using Module 3 of the standardized tool ADOS-2 (Autism Diagnostic Observation Schedule, Second Edition). We then represented the acoustic features using Mel-Frequency Cepstral Coefficients (MFCCs) and employed computational models for training and classification. Moreover, we identified 10 low-level descriptors (LLDs) in our dataset through t-tests that showed significant differences between ASD and TD children. We combined these 10 LLDs with MFCCs as inputs to the model and achieved an F1 score of 89.4%. Upon further analysis of these 10 LLDs, we found that they indeed represent the speech characteristic differences between ASD and TD children. This further provides interpretability of our model in identifying autistic tendencies based on the speech characteristic differences.

Doctors prescribe drugs for the patient with the objective of curing the patient. Some drugs cannot be consumed together since doing so may cause negative effects. This can be avoided by knowing the effects caused by consuming combinations of drugs. However, for complex cases of a patient, it can be difficult to decide the best combination of drugs. Therefore, automatic drug recommendation method was used to recommend drugs with minimal negative effects. It is performed by using a deep learning model which is trained on drug data. A graph called drug-drug interaction (DDI) is used to represent the drugs and effects of consuming one drug with other drugs. Additionally, information about the combination of drugs prescribed in the past for a patient is also important for drug recommendation. It can also be represented as a graph called drug concurrence relation (DCR). The DDI and DCR graphs can be input to the deep learning model through an encoding process. In this paper, we propose a graph encoding-enhanced transformer (GEET) to recommend drugs. The DDI and DCR graphs are encoded by using Graph Attention Network (GAT). The graph encoding model has multi-head attention, which makes the GEET model aware of the most important DDI and DCR from the graphs. Additionally, the encoding outputs are combined, and activation function and normalization methods are used to improve the performance. The model has been evaluated on the publicly available MIMIC-III dataset and has the best results on F1, Jaccard and PRAUC scores compared to the models proposed by the existing related research papers.

BACKGROUND: Biomedical named entity recognition (BioNER) is a basic and important task for biomedical text mining with the purpose of automatically recognizing and classifying biomedical entities. The performance of BioNER systems directly impacts downstream applications. Recently, deep neural networks, especially pre-trained language models, have made great progress for BioNER. However, because of the lack of high-quality and large-scale annotated data and relevant external knowledge, the capability of the BioNER system remains limited. RESULTS: In this paper, we propose a novel fully-shared multi-task learning model based on the pre-trained language model in biomedical domain, namely BioBERT, with a new attention module to integrate the auto-processed syntactic information for the BioNER task. We have conducted numerous experiments on seven benchmark BioNER datasets. The proposed best multi-task model obtains F1 score improvements of 1.03% on BC2GM, 0.91% on NCBI-disease, 0.81% on Linnaeus, 1.26% on JNLPBA, 0.82% on BC5CDR-Chemical, 0.87% on BC5CDR-Disease, and 1.10% on Species-800 compared to the single-task BioBERT model. CONCLUSION: The results demonstrate our model outperforms previous studies on all datasets. Further analysis and case studies are also provided to prove the importance of the proposed attention module and fully-shared multi-task learning method used in our model.

A skyline query searches the data points that are not dominated by others in the dataset. It is widely adopted for many applications which require multi-criteria decision making. However, skyline query processing is considerably time-consuming for a high-dimensional large scale dataset. Parallel computing techniques are therefore needed to address this challenge, among which$MapReduce$is one of the most popular frameworks to process big data. A great number of efficient$MapReduce$skyline algorithms have been proposed in the literature and most of their designs focus on partitioning and pruning the given dataset. However, there are still opportunities for further parallelism. In this study, we propose two parallel skyline processing algorithms using a novel$LShape$partitioning strategy and an effective$Propagation$$Filtering$method. These two algorithms are$2Phase$$LShape$and$1Phase$$LShape$, used for multiple reducers and single reducer, respectively. By extensive experiments, we verify that our algorithms outperformed the state-of-the-art approaches, especially for high-dimensional large scale datasets.

In this study, we propose two parallel skyline processing algorithms using a novel LShape partitioning strategy and an effective Propagation Filtering method. By extensive experiments, we verify that our algorithms outperformed the state-of-the-art approaches, especially for high-dimensional large scale datasets.

Having an effective public transport system is one of the most important factors to improve the quality of urban residents' life and to bring a sustainable development in urban areas. In this paper, we detect high demanding region pairs with inconvenient bus route design, such as taking circuitous routes or having too many stops, etc., to improve the utilization efficiency of public transportation services, according to people's real demands. The detected results consist of 1) region pairs with significant bus route design problems, and 2) the linking structure as well as the correlation among these region pairs. We compare these results to some existing and future urban planning, such as MRT lines, and study whether this planning reduces the current problems.

In order to increase the understanding of diseases, research on relationships among diseases becomes popular nowadays. Several previous works focus on finding the relationships between diseases from genomes. However, the relationships between diseases are also affected by many other factors such as gender, age, and even seasons. In this work, we divide patients into several groups, based on their genders and ages. After that, we find the relationships between diseases in the distinct groups from patient records. For example, in a group of middle-aged men, we find a significant percentage of patients getting a disease after a specified disease in a time period. Association rule mining is adopted to find the relationships of diseases. The relationships between diseases found can be applied to many fields, such as health education for people and information for researchers.

Understanding users is a key for many business applications. In this paper, we propose to pursue user preference understanding by their Wi-Fi logs collected from their mobile devices. As shown, Wi-Fi data are essentially of various information types and with noises. The challenges lie in how to refine relevant information from noisy Wi-Fi data. Aiming at the challenges, this paper proposes a data cleaning and information enrichment framework for enabling user preference understanding through Wi-Fi logs, and introduces a series of filters for cleaning, correcting, and refining Wi-Fi logs. A comprehensive experiment with real data collected from users is made to verify the effectiveness of the proposed techniques for cleaning noisy Wi-Fi data for user preference profiling. To the best of our knowledge, this work is the first attempt to study user behavior understanding by mining Wi-Fi logs.

Nowadays, mobile devices have become a ubiquitous medium supporting various forms of functionality and are widely accepted for commons. In this study, we investigate using Wi-Fi logs from a mobile device to discover user preferences. The core ideas are two folds. First, every Wi-Fi access point is with a network name, normally a human-readable string, called SSID (Service Set Identifier). Since SSIDs are often with semantics, from which we can infer the place where the user stayed. Second, a Wi-Fi log is produced when the user is near a Wi-Fi access point. A high frequency of a consecutively observed SSID implies a long stay duration at a place. To the best of our knowledge, our work is the first attempting to understand users from the collected Wi-Fi logs from mobile devices. However, Wi-Fi logs are essentially of various information types and with noises. How to assess the information types, eliminate irrelevant information, and clean up the noises within partial-informative SSIDs are therefore keys for profiling user preferences over Wi-Fi logs. In this paper, we propose a data cleaning and information enrichment framework for enabling the user preference understanding through collected Wi-Fi logs, and introduce a data clean framework for cleaning, correcting, and refining Wi-Fi logs. In addition, a comprehensive experiment with data collected from users is made to verify the effectiveness of the proposed techniques for cleaning noisy Wi-Fi data for user preferences profiling. The experiment results demonstrate the effectiveness of the proposed framework for profiling user preferences through Wi-Fi logs.

Many real-world phenomena such as social networks and biological networks can be modeled as graphs. Discovering dense sub-graphs from these graphs may be able to find interesting facts about the phenomena. Quasi-cliques are a type of dense graphs, which is close to the complete graphs. In this paper, we want to find all maximal quasi-cliques containing a target vertex in the graph for some applications. A quasi-clique is defined as a maximal quasi-clique if it is not contained by any other quasi-cliques. We propose an algorithm to solve this problem and use several pruning techniques to improve the performance. Moreover, we propose another algorithm to solve a special case of this problem, i.e. finding the maximal cliques. The experiment results reveal that our method outperforms the previous work both in real and synthetic datasets in most cases.

Given a set of criteria, an object o is defined to dominate another object o' if o is no worse than o' in each criterion and has better outcomes in at least a specific criterion. A skyline query returns each object that is not dominated by any other objects. Consider a scenario as follows. Given three types of datasets, including residents in a city, existing restaurants in the city, and candidate places for opening new restaurants in the city, where each restaurant and candidate place has its respective rank on a set of criteria, e.g., convenience of parking, we want to find the top-k candidate places that have the most potential customers. The potential customers of a candidate place is defined as the number of residents whose distance to this candidate is no larger than a given distance r and also regard this candidate as their skyline restaurants. In this paper, we propose an efficient method based on the quad-tree index and use four pruning strategies to solve this problem. A series of experiments are performed to compare the proposed method with a straightforward method using the R-tree index. The experiment results demonstrate that the proposed method is very efficient, and the pruning strategies very powerful.

The coverage problem is one of the fundamental problems in sensor networks, which reflects the degree of a region being monitored by sensors. In this paper, we make the first attempt to address the k-coverage verification problem regarding a given query line segment, which returns all sub-segments from the line segment that are covered by at least k sensors. To deal with the problem, we propose three methods based on the R-tree index. The first method is the most primitive one, which identifies all intersection points of the query line segment and the circumferences of the covering regions of the sensors and then checks each sub-segment to see whether it is k-coverage. Improving from the first method, the second method calculates the lower bound of the number of sensors covering a specific sub-segment to reduce the computation costs. The third method partitions the query line segment into sub-segments with equal length and then verifies each of them. A series of experiments on a real dataset and two synthetic datasets are performed to evaluate these methods. The experiment results demonstrate that the third method has the best performance among all three methods.

In this paper, a problem of production plans, named k-most demanding products (k-MDP) discovering, is formulated. Given a set of customers demanding a certain type of products with multiple attributes, a set of existing products of the type, a set of candidate products that can be offered by a company, and a positive integer k, we want to help the company to select k products from the candidate products such that the expected number of the total customers for the k products is maximized. We show the problem is NP-hard when the number of attributes for a product is 3 or more. One greedy algorithm is proposed to find approximate solution for the problem. We also attempt to find the optimal solution of the problem by estimating the upper bound of the expected number of the total customers for a set of k candidate products for reducing the search space of the optimal solution. An exact algorithm is then provided to find the optimal solution of the problem by using this pruning strategy. The experiment results demonstrate that both the efficiency and memory requirement of the exact algorithm are comparable to those for the greedy algorithm, and the greedy algorithm is well scalable with respect to k.

Sensor networks have received considerable attention in recent years, and are employed in many applications. In these applications, statistical aggregates such as Sum over the readings of a group of sensor nodes are often needed. One challenge for computing sensor data aggregates comes from the communication failures, which are common in sensor networks. To enhance the robustness of the aggregate computation, multipath-based aggregation is often used. However, the multipath-based aggregation suffers from the problem of overcounting sensor readings. The approaches using the multipath-based aggregation therefore need to incorporate techniques that avoid overcounting sensor readings. In this paper, we present a novel technique named scalable counting for efficiently avoiding the overcounting problem. We focus on having an (ε, δ) accuracy guarantee for computing an aggregate, which ensures that the error in computing the aggregate is within a factor of ε with probability (1 - δ). Our schemes using the scalable counting technique efficiently compute the aggregates under a given accuracy guarantee. We provide theoretical analyses that show the advantages of the scalable counting technique over previously proposed techniques. Furthermore, extensive experiments are made to validate the theoretical results and manifest the advantages of using the scalable counting technique for sensor data aggregation.

To investigate the most efficient way to represent text in reading Chinese on computer displays, three typographic variables, character size (41′ arc/24 pixels and 60′ arc/32 pixels), character spacing (1/4 and 1/8 character width) and font type (Kai and Ming), were manipulated. Results showed that the reading speed for Chinese characters of Kai type in 24 pixels with 1/8 character spacing was the shortest. Character size significantly affected overall reading speed; in specific, text in 24-pixel characters was read faster than text in 32-pixel characters. Further eye-movement analyses revealed that text in smaller-sized characters had longer fixation duration, fewer fixations and fewer regressions than text in larger-sized characters. The interaction between character spacing and font type was observed on overall reading efficiency and on some eye-movement measures, which suggests that different character spacings should be considered in different font types for more efficient reading. Generally, characters in Kai font were easier to read with 1/8 character spacing than with 1/4 character spacing. The relationship between eye-movement measures and overall reading efficiency was further discussed.

Sensor networks have received considerable attention in recent years, and are often employed in the applications where data are difficult or expensive to collect. In these applications, in addition to individual sensor readings, statistical aggregates such as Min and Count over the readings of a group of sensor nodes are often needed. To conserve resources for sensor nodes, in-network strategies are adopted to process the aggregates. One primitive in-network aggregation strategy is the tree-based aggregation, where the aggregates are computed from leaves to the root of a spanning tree over a sensor network. However, a shortcoming with the tree-based aggregation is that it is not robust against communication failures, which are common in sensor networks. One of the solutions to overcome this shortcoming is to enable multipath routing, by which each node broadcasts its reading or a partial aggregate to multiple neighbors. However, multipath routing-based aggregation typically suffers from the problem of overcounting sensor readings. In this study, we propose two schemes based on the linear counting technique to deal with the overcounting problem. These two schemes process aggregates by statically and dynamically, respectively, allocating space for the use of the linear counting technique. Both schemes provide the same accuracy guarantee but involve different communication costs. Through extensive experiments with real-world and synthetic data, we demonstrate the efficiency and effectiveness of using these two schemes as solutions for processing aggregates in a sensor network. The experiments also show that the scheme that dynamically allocates the space often outperforms the other one in terms of energy conservation since it requires less space to satisfy an accuracy constraint.

Range queries for querying the current and future positions of the moving objects have received growing interests in the research community. Existing methods, however, assume that an object only moves along an anticipated path. In this paper, we study the problem of answering probabilistic range queries on moving objects based on an uncertainty model, which captures the possible movements of objects with probabilities. Evaluation of probabilistic queries is challenging due to large objects volume and costly computation. We map the uncertain movements of all objects to a dual space for indexing. By querying the index, we quickly eliminate unqualified objects and employ an approximate approach to examine the remaining candidates for final answer. We conduct a comprehensive performance study, which shows our proposal significantly reduces the number of object examinations and the overall cost of the query evaluation.

Wireless sensor networks have received considerable attention in recent years and played an important role in data collection applications. Sensor nodes usually have limited supply of energy. Therefore, a major consideration for developing sensor network applications is to conserve the energy for sensor nodes. In this paper, we propose a novel energy-efficient data acquisition algorithm based on the periodic patterns derived from past sensor readings. Our key observation is that sensor readings often exhibit periodic patterns, e.g., the daily cycle of temperature readings, and the patterns provide opportunities for reducing energy consumption for sensor data acquisition. We exploit the patterns and use the patterns to build a statistic model for predicting sensor readings. In our approach, sensor data acquisition is needed only when acquired readings are unpredictable. Therefore the energy for sensor data acquisition and the associated radio communications can be conserved. The experiments performed with real data validate the effectiveness and efficiency of our approach.

Range queries for querying the current and future positions of the moving objects have received growing interests in the research community. Existing methods, however, assume that an object only moves along an anticipated path. In this paper, we study the problem of answering probabilistic range queries on moving objects based on an uncertainty model, which captures the possible movements of objects with probabilities. We conduct a performance study, which shows our proposal significantly reduces the number of object examinations and the overall cost of the query evaluation.

Presents the introductory welcome message from the conference proceedings.

Sensor networks have received considerable attention in recent years, and are often employed in the applications where data are difficult or expensive to collect. In these applications, in addition to individual sensor readings, statistical aggregates such as Min and Count over the readings of a group of sensor nodes are often needed. To conserve resources for sensor nodes, in-network strategies are adopted to process the aggregates. One primitive in-network aggregation strategy is the tree-based aggregation, where the aggregates are computed along a spanning tree over a sensor network. However, a shortcoming with the tree-based aggregation is that it is not robust against communication failures, which are common in sensor networks. One of the solutions to overcome this shortcoming is to enable multi-path routing, by which each node broadcasts its reading or a partial aggregate to multiple neighbors. However, multi-path routing based aggregation typically suffers from the problem of overcounting sensor readings. In this study, we propose using the linear counting sketches for multi-path routing based in-network aggregation. We claim that the use of the linear counting sketches makes our approach considerably more accurate than previous approaches using the same sketch space. Our approach also enjoys low variances in term of the aggregate accuracy, and low overheads either in computations or sketch space. Through extensive experiments with real-world and synthetic data, we demonstrate the efficiency and effectiveness of using the linear counting sketches as a solution for the in-network aggregation.

Data mining techniques have been widely used in various applications. However, the misuse of these techniques may lead to the disclosure of sensitive information. Researchers have recently made efforts at hiding sensitive association rules. Nevertheless, undesired side effects, e.g., nonsensitive rules falsely hidden and spurious rules falsely generated, may be produced in the rule hiding process. In this paper, we present a novel approach that strategically modifies a few transactions in the transaction database to decrease the supports or confidences of sensitive rules without producing the side effects. Since the correlation among rules can make it impossible to achieve this goal, in this paper, we propose heuristic methods for increasing the number of hidden sensitive rules and reducing the number of modified entries. The experimental results show the effectiveness of our approach, i.e., undesired side effects are avoided in the rule hiding process. The results also report that in most cases, all the sensitive rules are hidden without spurious rules falsely generated. Moreover, the good scalability of our approach in terms of database size and the influence of the correlation among rules on rule hiding are observed

Since tree-structured data such as XML files are widely used for data representation and exchange on the Internet, discovering frequent tree patterns over tree-structured data streams becomes an interesting issue. In this paper, we propose an online algorithm to continuously discover the current set of frequent tree patterns from the data stream. A novel and efficient technique is introduced to incrementally generate all candidate tree patterns without duplicates. Moreover, a framework for counting the approximate frequencies of the candidate tree patterns is presented. Combining these techniques, the proposed approach is able to compute frequent tree patterns with guarantees of completeness and accuracy.

Multimedia data can be represented as a multiple-attribute string of feature values corresponding to multiple features of the data. Therefore, the retrieval problem can be transformed into the q-attribute string matching problem if q features are considered in a query. A general solution is proposed in this paper. It includes an index structure and the matching methodologies, which can be applied on different values of q. The experiment results show the efficiency of the proposed approach.

Mining frequent itemsets has been widely studied over the last decade. Past research focuses on mining frequent itemsets from static databases. In many of the new applications, data flow through the Internet or sensor networks. It is challenging to extend the mining techniques to such a dynamic environment. The main challenges include a quick response to the continuous request, a compact summary of the data stream, and a mechanism that adapts to the limited resources. In this paper, we develop a novel approach for mining frequent itemsets from data streams based on a time-sensitive sliding window model. Our approach consists of a storage structure that captures all possible frequent itemsets and a table providing approximate counts of the expired data items, whose size can be adjusted by the available storage space. Experiment results show that in our approach both the execution time and the storage space remain small under various parameter settings. In addition, our approach guarantees no false alarm or no false dismissal to the results yielded.

Data mining techniques have been developed in many applications. However it also causes a threat to privacy. We investigate to find an appropriate balance between a need for privacy and information discovery on association patterns. We propose an innovative technique for hiding sensitive patterns. In our approach, a sanitization matrix is defined. By multiplying the original transaction database and the sanitization matrix, a new database, which is sanitized for privacy concern, is described. Moreover a set of experiments is performed to show the effectiveness of our approach.

Mining sequential patterns in large databases is an important research topic. The main challenge of mining sequential patterns is the high processing cost due to the large amount of data. We propose a new strategy called direct sequence comparison (abbreviated as DISC), which can find frequent sequences without having to compute the support counts of nonfrequent sequences. The main difference between the DISC strategy and the previous works is the way to prune nonfrequent sequences. The previous works are based on the antimonotone property, which prune the nonfrequent sequences according to the frequent sequences with shorter lengths. On the contrary, the DISC strategy prunes the nonfrequent sequences according to the other sequences with the same length. Moreover, we summarize three strategies used in the previous works and design an efficient algorithm called DISC-all to take advantages of all the four strategies. The experimental results show that the DISC-all algorithm outperforms the PrefixSpan algorithm on mining frequent sequences in large databases. In addition, we analyze these strategies to design the dynamic version of our algorithm, which achieves a much better performance.

According to musicology, musical content and musical structure are both major components of a music work. Most approaches of music retrieval, classification, and analysis use the information of the musical content, but not the information of the musical structure. The main reason is that the musical structure usually needs to be analyzed manually by experts, which is time-consuming and impractical. We propose an approach for automatic music segmentation to extract the phrases and sentences of the musical structure. In addition to the rhythmic features, the melodic shape is also used to improve the effectiveness of the music segmentation. Experiments are performed to show that our approach is practical.

In this paper, we describe the Ultima project which aims to construct a platform for evaluating various approaches of music information retrieval. Two kinds of approaches are adopted in this project. These approaches differ in various aspects, such as representations of music objects, index structures, and approximate query processing strategies. For a fair comparison, we propose a measurement of the retrieval effectiveness by recall-precision curves with a scaling factor adjustment. Finally, the performance study of the retrieval effectiveness based on various factors of these approaches is presented.

The problem of transmitting data items with timing constraint in the multiple broadcast channels where clients equipped with multiple receivers is studied. In our approach, the data items are divided into two sets, the broadcast data set and the on-demand data set. The data items in the broadcast data set is periodically broadcast on the broadcast channels while the data items in the on-demand data set are transmitted when they are requested. The server offline allocates the data items in the broadcast data set to the multiple broadcast channels. The clients retrieved data items from the broadcast channels are guaranteed to receive them within the timing constraint. Once the desired data item is not included in the broadcast channels, clients make requests associated with deadlines to the server. By using the bandwidth remaining for the on-demand mode, the server broadcasts the requested data items in an online fashion. The intention of our work is to serve as many requests as possible.

In a wireless environment, the bandwidth of the channels and the energy of the portable devices are limited. Data broadcast has become an excellent method for efficient data dissemination. In this paper the problem for generating a broadcast program of a set of data items with the associated access frequencies on multiple channels is explored. In our approach, we consider allocating index information and data items on multiple broadcast channels by extending the distributed indexing approach. Moreover global data replication and local data allocation are performed to improve the average access time of all data items. Simulation is performed to compare the performance of our approach with an existing approach. The result of the experiments shows that our approach outperforms the existing approach.

Many approaches have been proposed to schedule data items for broadcasting in a mobile environment. However, the issues of accessing multiple data items on the broadcast channel are less discussed. In this paper, an efficient strategy for accessing multiple data items in mobile environments is proposed. Two issues are investigated in this paper, that is, deciding the content of the broadcast channel based on the queries from the clients, and scheduling the data items to be broadcast. Experiments are performed to compare our proposed methods for deciding the content and to show that our data scheduling methods can reduce the average access time without considerable increase on processing time.

Data broadcast is an excellent method for efficient data dissemination in the mobile computing environment. The application domain of data broadcast will be widely expanded in the near future, where the client is expected to perform complex queries or transactions on the broadcast data. To reduce the access latency for processing the complex query, it is beneficial to place the data accessed in a query close to each other on the broadcast channel. In this paper, we propose an efficient algorithm to determine the allocation of the data on the broadcast channel such that frequently co-accessed data are not only allocated close to each other, but also in a particular order which optimizes the performance of query processing. Our mechanism is based on the well-known problem named optimal linear ordering. Experiments are performed to justify the benefit of our approach.

Within integrated multiple object databases, missing data occurs due to the missing attribute conflict as well as the existence of null values. A set of algorithms is provided in this paper to process the predicates of global queries with missing data. To provide more informative answers to users, the "maybe" results due to missing data are presented in addition to the "certain" results. The local "maybe" results may become "certain" results via the concept of object isomerism. One algorithm is designed based on the centralized approach in which data are forwarded to the same site for integration and processing. Furthermore, to reduce the response time, localized approaches evaluate the predicates within distinct component databases in parallel. The object signature is also applied in the design to further reduce the data transfer. These algorithms are compared and discussed according to the simulation results of both the total execution and response times. Alternately, the global schema may contain multi-valued attributes with values derived from attribute values in different component databases. Hence, the proposed approaches are also extended to process the global queries involving this kind of multi-valued attribute.

A video query model based on the content of video and iconic indexing is proposed. We extend the notion of two-dimensional strings to three-dimensional strings (3D-Strings) for representing the spatial and temporal relationships among the symbols in both a video and a video query. The problem of video query processing is then transformed into a problem of three-dimensional pattern matching. To efficiently match the 3D-Strings, a data structure, called 3D-List, and its related algorithms are proposed. In this approach, the symbols of a video in the video database are retrieved from the video index and organized as a 3D-List according to the 3D-String of the video query. The related algorithms are then applied on the 3D-List to determine whether this video is an answer to the video query. Based on this approach, we have started a project called Vega. In this project, we have implemented a user friendly interface for specifying video queries, a video index tool for constructing the video index, and a video query processor based on the notion of 3D-List. Some experiments are also performed to show the efficiency and effectiveness of the proposed algorithms.

Foreign functions have been considered in the advanced database systems to support complex applications. We consider optimizing queries with foreign functions in a distributed environment. In traditional distributed query processing, selection operations are locally processed before joins as much as possible so that the size of relations being transmitted and joined can be reduced. However, if selection predicates involve foreign functions, the cost of evaluating selections cannot be ignored. As a result, the execution order of selections and joins becomes significant, and the trade-off for reducing the costs of data transmission, join processing, and selection predicate evaluation needs to be carefully considered in query optimization. A response time model is developed for estimating the cost of distributed query processing involving foreign functions. We explore the property of the problem and find an optimal algorithm with polynomial complexity for a special case of it. However, finding the optimal execution plan for the general case is NP-hard. We propose an efficient heuristic algorithm for solving the problem and the simulation result shows its good quality. The research result can also be applied to the advanced database systems and the multidatabase systems where the conversion function defined for the need of schema integration can be considered a type of foreign functions.

With the growth of the World Wide Web, a large amount of music data is available on the Internet. In addition to searching expected music objects for users, it becomes necessary to develop a recommendation service. In this paper, we design the Music Recommendation System (MRS) to provide a personalized service of music recommendation. The music objects of MIDI format are first analyzed. For each polyphonic music object, the representative track is first determined, and then six features are extracted from this track. According to the features, the music objects are properly grouped. For users, the access histories are analyzed to derive user interests. The content-based, collaborative and statistics-based recommendation methods are proposed, which are based on the favorite degrees of the users to the music groups. A series of experiments are carried out to show that our approach is feasible.

In a wireless environment, the bandwidth of the channels and the energy of the portable devices are limited. Data broadcast has become an excellent method for efficient data dissemination. In this paper, the problem for generating a broadcast program of a set of data items with the associated access frequencies on multiple channels is explored. In our approach, an expected average access time of the broadcast data items is first derived. The broadcast program is then generated, which minimizes the expected average access time. Simulation is performed to compare the performance of our approach with two existing approaches. The result of the experiments shows that our approach outperforms others and is in fact close to the optimal.

This paper proposes an indexing and query processing approach for content-based video retrieval The concept hierarchy is used to provide high-level concepts for users to specify queries. The index buckets and suffix trees are proposed to index the static attributes and motions of video objects A flexible query processing strategy is designed based on the index structure. Also, strategies for processing approximate queries and queries involving object motions are considered.

Mining association rules is an important task for knowledge discovery. We can analyze past transaction data to discover customer behaviors such that the quality of business decisions can be improved. Various types of association rules may exist in a large database of customer transactions. The strategy of mining association rules focuses on discovering large item sets, which are groups of items which appear together in a sufficient number of transactions. We propose a graph-based approach to generate various types of association rules from a large database of customer transactions. This approach scans the database once to construct an association graph and then traverses the graph to generate all large item sets. Empirical evaluations show that our algorithms outperform other algorithms which need to make multiple passes over the database.

A repeating pattern in music data is defined as a sequence of notes which appears more than once in a music object. The themes are a typical kind of repeating patterns. The themes and other nontrivial repeating patterns are important music features which can be used for both content-based retrieval of music data and music data analysis. In this paper, we propose two approaches for fast discovering nontrivial repeating patterns in music objects. In the first approach, we develop a data structure called correlative matrix and its associated algorithms for extracting the repeating patterns. In the second approach, we introduce a string-join operation and a data structure called RP-tree for the same purpose. Experiments are performed to compare these two approaches with others. The results are further analyzed to show the efficiency and the effectiveness of our approaches.

Searching information from the WWW efficiently and effectively has become a very important issue. We apply the information filtering concept to finding good matches of Web pages to what the user needs. Furthermore, we propose four new methods for indexing user information needs and show their efficiency in comparison with two well-known approaches.

The issue of data broadcast has received much attention in mobile computing. A periodic broadcast of frequently requested data can reduce the workload of the up-link channel and facilitate data access for the mobile user. Since the mobile units usually have limited battery capacity, the minimization of the access latency for the broadcast data is an important problem. The indexing and scheduling techniques on the broadcast data should be considered. We propose a solution to find the optimal index and data allocation, which minimizes the access latency for any number of broadcast channels. We represent all the possible allocations as a tree in which the optimal one is searched, and propose a pruning strategy based on some properties to greatly reduce the search space. Experiments are performed to show the effectiveness of the pruning strategy. Moreover, we propose two heuristics to solve the same problem when the size of the broadcast data is large.

A ubiquitous information environment can be achieved by the mobile computing technologies. In this environment, users carrying their portable computers can retrieve local or remote information anywhere and at anytime. Data broadcast, with its advantages, has become a powerful means to disseminate data in wireless communications. Indexing methods for the broadcast data have been proposed to speedup access time and reduce power consumption. However, the influence of access failures has not been discussed. For the error-prone mobile environment, the occurrence of access failures is often due to disconnections, handoffs, and communication noises. Based on the distributed indexing scheme, we propose an adaptive access method which tolerates the access failures. The basic idea is to use index replication to recover from the access failures. One mechanism, named search range, is provided to dynamically record the range where the desired data item may exist. According to the search range, an unfinished search can be efficiently resumed by finding an available index replicate. A performance analysis is given to show the benefits of the method. Also, the concept of version bits is applied to deal with the updates of the broadcast data.

This paper presents a query processing strategy for the content-based video query language named CVQL. By CVQL, users can flexibly specify query predicates by the spatial and temporal relationships of the content objects. The query processing strategy evaluates the predicates and returns qualified videos or frames as results. Before the evaluation of the predicates, a preprocessing is performed to avoid unnecessary accessing of videos which are impossible to be the answers. The preprocessing checks the existence of the content objects specified in the predicates to eliminate unqualified videos. For the evaluation of the predicates, an M-index is designed based on the analysis of the behaviors of the content objects. The M-index is employed to avoid frame-by-frame evaluation of the predicates. Experimental results are presented to illustrate the performance of this approach.

Proposes an approach for the fast discovery of all non-trivial repeating patterns in music objects. A repeating pattern is a sequence of notes which appears more than once in a music object. The longest repeating patterns in music objects are typically their themes. The themes and other non-trivial repeating patterns are important musical features which can be used both for content-based retrieval of music data and for music data analysis. We present a data structure called an RP-tree (repeating pattern tree) and its associated algorithms for the fast extraction of all non-trivial repeating patterns in a music object. Experiments are performed to compare this method with related approaches. The results are further analysed to show the efficiency and effectiveness of our approach.

In this paper, we propose an approach for the extraction of the repeating patterns in music objects. A repeating pattern is a sequence of notes which appears more than once in a music object. It is one of the most important music features which can be used for both content-based retrieval of music data and music data analysis. We propose a data structure called correlative matrix and its associated algorithms for extracting all repeating patterns in a music object. Experiments are also performed and the results are analyzed to show the efficiency and the effectiveness of our approach.

A document retrieval system mainly consists of three components: document representation, user queries, and document evaluation. Each component may involve some uncertainties. Fuzzy set theory is a natural approach to coping with the representation of documents, queries, and the relevance of documents to a given query. The authors propose a fuzzy document retrieval model on the World Wide Web (WWW) environment to support conceptual queries. A flexible query expression is proposed to support different semantics of the queries. A concept network is adopted as the knowledge base to represent the relevance of the concepts. The concept network is explored from the WWW. Moreover, they also support neighborhood queries, which retrieve documents relevant to a document specified by a user. A system is currently being implemented to achieve these functions.

Motion is the major feature that differentiates a video from a still image. In content-based retrieval, the motion track of a symbol object can be used as an index of video databases. Query processing based on such index can be treated as a curve matching problem. Two important criteria for solving the problem are sub-matching and approximate-matching. In this paper, two query processing approaches are proposed. The first approach expands the motion track index to a region and allows a user to query against this region. In the second approach, both the motion track index and the query curve are modeled as a combination of peaks and each peak is coded according to its orientation, angle and temporal information. The curve matching problem is then converted into a string matching problem, which is solved efficiently by a new finite automata based method. The proposed string matching algorithm is also shown to be scalable to the growth of the size of the database. 1.

The problem of missing data arises in the distributed heterogeneous object databases because of the missing attribute conflict and the existence of null values. A set of algorithms are provided in this paper for query processing when the predicates in global queries involve missing data. For providing more informative answers to the users, the maybe results due to missing data are presented in addition to the certain results. One algorithm is designed based on the centralized approach in which the data are sent to the same site for integration and then processing. On the other hand, for reducing the response time, the localized approaches evaluate the predicates in different component databases in parallel. The proposed algorithms are compared and discussed by the simulation result on the total execution time and response time.

Imprecise data in databases were originally denoted as null values, which represent the meaning of "values unknown at present." More generally, a partial value corresponds to a finite set of possible values for an attribute in which exactly one of the values is the "true" value. We define a set of extended aggregate operations, namely sum, average, count, maximum, and minimum, which can be applied to an attribute containing partial values. Two types of aggregate operators are considered: scalar aggregates and aggregate functions. We study the properties of the aggregate operations and develop efficient algorithms for count, maximum and minimum. However, for sum and average, we point out that in general it takes exponential time complexity to do the computations.

For original paper, see A. Ola and G. Ozsoyoglu, ibid., vol. 5, no. 2, pp. 293-308 (1993). In that paper, a family of relational database models (M-1 to M-5) were proposed to represent unknown values by intervals. Relational operators were extended for evaluating queries on these models. In this paper, we stultify the theorems, claiming that query evaluation in models M-2, M-3 and M-5 is sound.

We elaborate on how to interpret the query answer on exclusive disjunctive databases and how to reduce the query answer into a more concise form. Exclusive disjunctive data are represented as a pair of value set and variable set in Pv-table which is an extension of the relational model. A value set corresponds to a finite set of possible values in which exactly one value is the true value. By variable sets, tuples may be related with certain relationships, namely disjunctive relationship and join relationship. Three kinds of tuple sets are classified according to these relationships, each possesses an important property, namely co-exist, co-nonempty, or co-instance. Based on these properties, the interpretation of Pv-tables can be formalized in a semantically meaningful way, Also, the redundant and mergeable tuples can be identified. After removing and merging tuples accordingly, a more concise Pv-table can thus provide a better understanding of the query result.

We propose an approach for building an object front-end on top of a relational database. The object front-end can be used as the interface for integration with other object databases. The users are allowed to access data stored in the relational database using an object query language. A set of derivation rules is provided to construct an object view from the relational schema. Transformation strategies from object queries to corresponding relational queries are also presented. This object front-end has been implemented in a heterogeneous database project.>

The paper presents an approach for processing long-duration database transactions with high concurrency degree. The basic idea is based on the use of a repository which stores the data items that can be exposed before the associated transaction commits. The management of the repository is described. Since we allow a transaction to read and update the early exposed data items, if the data items are invalidated we have to rollback the transactions that have read these data items. In order to reduce the cost of rollback, a partial rollback mechanism is proposed. Further, transactions that have read the early exposed data may commit earlier than the corresponding uncommitted transactions. We describe the commit decision rule to determine whether earlier commitment can be allowed, by which the system throughput can be increased.>

We consider processing entity join queries in a wide area multidatabase environment where the query processing cost is dominated by the cost of data transmission. An entity join operation "integrates" tuples representing the same entities from different relations in which inconsistent data may exist. The semijoin technique has been successfully used in a distributed database system to reduce the cost of data transmission. However, it cannot be directly applied to process the entity join query. An extension of the traditional semijoin, named extended semijoin is proposed to reduce the cost of data transmission for entity join query processing in a wide area multidatabase environment.

Performance studies show that traditional semi-join processing methods are sometimes inefficient because of the storage and processing overhead. To remedy this problem, a new semi-join processing method, called one-shot semi-join execution is proposed. This method allows parallel generation of all the semi-join projections, parallel transmission of all the semi-join projections, and parallel execution of all the semi-joins. The authors apply this method to optimize the response time for processing distributed queries. A response time model is established, which considers both data transmission time and local processing time. Based on this model, an efficient query processing algorithm is developed and analyzed.>

Entity-relationship (E-R) concepts are extended to capture natural language semantics and develop a logical form to represent natural language queries. The logical form can be efficiently transformed into relational algebra for query execution. The whole process provides a clear and natural framework for processing natural language queries to retrieve data from database systems.>

A novel semijoin execution strategy is proposed which allows parallelism and processes multiple semijoins simultaneously. In practice most of the parameters needed for query optimization, such as relation cardinality and selectivity, are of fixed-precision. Imposing this fixed-precision constraint, an efficient distributed query processing algorithm is developed. For situations where the fixed-precision constraint does not apply, a method to truncate the parameters and to use the same algorithm to find near-optimal solutions is proposed. By analyzing the truncation errors, a quantitative comparison between the near-optimal solutions and the optimal ones is provided.>

Mermaid is a testbed system which provides integrated access to multiple databases. Two query optimization algorithms have been developed for Mermaid. The semijoin algorithm tends to reduce the data transmission cost, while the replicate algorithm reduces the processing cost. An algorithm that integrates the features of these two algorithms to optimize the processing cost as well as the transmission cost is presented. A dynamic network environment is considered where processing speeds at each site and transmission speeds at each link can be variable. Moreover, distributed processing of aggregates is considered based on the functional dependency among the fragment attribute, the aggregate attribute, and the group-by attribute. Semantic information is utilized to obtain efficient query processing.>

A partition-and-replicate strategy for processing distributed queries referencing no fragmented relation is sketched. An algorithm is given to determine which relation and which copy of the relation is to be partitioned into fragments, how the relation is to be partitioned, and where the fragments are to be sent for processing. Simulation results show that the partition strategy is useful for processing queries in fast local network environments. The results also show that the number of partitions does not need to be large. The use of semijoins in the partition strategy is discussed. A necessary and sufficient condition for a semijoin to yield an improvement is provided.>

The authors describe a simulation approach to the study of the performance issues of the telephone network operations process. For the initial phase of the study, the customer trouble reporting process was selected. The average receipt-to-close time of a customer trouble as a function of the number of repair techniques and data access time was studied along with the workload distribution. The Bellcore-developed system IC* was used to implement the simulation, to display queuing effects and transaction flows, and to produce a pictorial representation of the simulation model.>

Mermaid is a system that allows the user of multiple databases stored under various relational DBMSs running on different machines to manipulate the data using a common language, either ARIEL or SQL. It makes the complexity of this distributed, heterogeneous data processing transparent to the user. In this paper, we describe the architecture, system control, user interface, language and schema translation, query optimization, and network operation of the Mermaid system. Future research issues are also addressed.

We propose a scheme to make use of semantic information to process distributed queries locally without data transfer with respect to the join clauses of the query. Since not all queries can be processed without data transfer, we give an algorithm to recognize the "locally processable queries." For nonlocally processable queries, a simple "fragment and replicate" algorithm is used. The algorithm chooses a relation to remain fragmented at the sites where they are situated while replicating the other relations at those sites. Our algorithm determines the chosen relation and the chosen copy of every fragment of the chosen relation such that the minimum response time is obtained. The algorithm runs in linear time. If the fragments of the relation are allowed to be processed in other sites, then the problem is NP hard. Two heuristics are given for that situation. They are compared to the optimal situation. Experimental results show that the strategies produced by the heuristics have small errors relative to the optimal strategy.

AIDA is a distributed data management (DDM) front-end system which runs on top of existing databases stored in different data management systems (DBMSs). It appears to the user to be a distributed DBMS, although many of the DBMS functions are actually provided by the underlying DBMS. It currently runs above three relational DBMSs, the IDM database machine connected to a VAX, Ingres on two Suns, and Mistress on a third Sun. One of the key components of the AIDA system is Mermaid which provides query optimization, networking, and system control. Mermaid required research into query optimization where the costs of operations on the different processors and DBMSs is variable, the network cost is variable, and capabilities of the different DBMSs is variable. We extended existing distributed query optimization algorithms to support replicated and fragmented relations. In this paper, we discuss our experiences with the development and testing of the Mermaid system and with the integration of Mermaid with the AIDA translator. We discuss the types of commands, the system controller, and our experiences with distributed debugging. Then we give the results of our initial performance tests.

We propose new adaptive techniques for distributed query optimization. These techniques are divided into two groups: the ones that improve efficiency of query execution (directly) and the ones that improve cost estimations for query execution strategies. Some of the proposed techniques utilize semantic information and knowledge acquisition to adapt to the environment. The latter, in contrast to the former, is not a well-established idea. This is a disturbing fact since knowledge acquisition can give significant improvements in performance of a query optimization algorithm. Performing analysis manually is extrernely time consuming and tedious. Therefore, some learning capacity should be added to the system. Some knowledge acquisition techniques that result in adaptive (dynamic) adjustment to run-time changes are proposed.

The problem of optimal query processing in distributed database systems was shown to be NP-hard. However, for a special type of queries called star queries, we have developed a polynomial optimal algorithm. Semijoin tactics are applied for query processing. An execution graph is introduced to represent the semijoin programs associated with the distributed processing of the queries. We then identify optimality properties of semijoin programs for star queries, and use these properties to derive the optimal semijoin program. We have shown that the optimal semijoin program can be found from serial semijoin strategies, defined as serial semijoin programs which include each semijoin associated with the query exactly once. By making certain assumptions on the file sizes and the semijoin selectivities, we can obtain the optimal semijoin program from these strategies in polynomial time. Our assumption on selectivites is consistent in the sense that we consider the selectivity of a semijoin based on the current database state, i.e., we take into consideration the reduction effects of all prior semijoins.

The problem of optimal query processing in distributed database systems was shown to be NP-hard. This means that heuristic algorithms are necessary to solve the query processing problem. In this paper, we describe algorithms to improve the solutions generated by heuristics. We have identified four properties which optimal semijoin programs for processing tree queries have to satisfy. A semijoin program is represented by an execution graph which specifies the order and the identities of the semijoins to be executed. Given a semijoin program, we can therefore apply these properties to check its optimality. If it does not satisfy these optimality properties, the associated improvement algorithms can be applied to improve this program. No assumptions have been made about the relation size and the selectivity of the semijoins.