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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.>

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.