The traditional MapReduce frameworks were originally designed for processing data within a single cluster and are not suitable for handling geo-distributed data. Consequently, alternative approaches such as Hierarchical and Geo-Hadoop have been proposed to address this limitation. However, these approaches still face challenges in efficiently managing inter-cluster data transfer, particularly considering the heterogeneity of clusters and varying bandwidth among them. Moreover, the need to transmit results to a central global reducer for geo-distributed MapReduce operations adds unnecessary complexity. To tackle these issues, we introduce Extended Cross-MapReduce (ECMR), a framework that integrates resource heterogeneity and network links in geo-distributed MapReduce workflows. ECMR optimizes data management and determines the necessary data volume for generating final results. To enhance performance, ECMR leverages the overlap between data transfer and execution time by utilizing multiple global reducers and grouping temporary results that require data transfer over the Internet. In ECMR, we propose a bipartite graph and extend the Gale-Shapley algorithm to determine the optimal number of clusters and select the most suitable locations for global reducers. Through extensive experimental evaluations conducted on a real testbed, we demonstrate the effectiveness of our proposed ECMR method. The results exhibit significant improvements over traditional Hierarchical and Geo-Hadoop approaches, achieving reductions of up to 81% and 85% in overall makespan, respectively.

The theme and variation music form is a hierarchical structure in music. It has a theme segment at the beginning, followed by a series of variation segments imitating the theme segment. Hence, the primary features of the theme and variation form are repetition and variation at different levels. However, due to the lack of available datasets, the theme and variation form analysis method has not been explored much. Therefore, in this work, we curate and contribute a dataset named Performance of Theme and Variation Form (PTV) and propose a theme and variation form segmentation framework to analyze the theme and variation form. Experiment results show that our method achieves an F1 score of 92.8% on our dataset with some constraints. In addition, we conduct analysis to support and encourage future studies of the theme and variation form.

Reverse Approximate Nearest Neighbor (RANN) query relaxes the RkNN definition of influence, where a user u can be influenced by not only its closest facility but also by every other facility that is almost as close to u as its closest facility is. In this paper, we study the continuous monitoring of RANN queries on road network. Existing continuous RANN algorithms on Euclidean space cannot be extended to continuously monitor RANN queries on road network. We propose two different methods to efficiently monitor RANN queries. We conduct an extensive experiment on different real data sets and demonstrate that our both proposed algorithms are significantly better than the competitor

Abstract As an essential part of music, main melody is the cornerstone of music information retrieval. In the MIR’s sub-field of main melody extraction, the mainstream methods assume that the main melody is unique. However, the assumption cannot be established, especially for music with multiple main melodies such as symphony or music with many harmonies. Hence, the conventional methods ignore some main melodies in the music. To solve this problem, we propose a deep learning-based Multiple Main Melodies Generator (Multi-MMLG) framework that can automatically predict potential main melodies from a MIDI file. This framework consists of two stages: (1) main melody classification using a proposed MIDIXLNet model and (2) conditional prediction using a modified MuseBERT model. Experiment results suggest that the proposed MIDIXLNet model increases the accuracy of main melody classification from 89.62 to 97.37%. In addition, this model requires fewer parameters (71.8 million) than the previous state-of-art approaches. We also conduct ablation experiments on the Multi-MMLG framework. In the best-case scenario, predicting meaningful multiple main melodies for the music are achieved.

Classifying music pieces based on their instrument sounds is pivotal for analysis and application purposes. Given its importance, techniques using machine learning have been proposed to classify violin and viola music pieces. The violin and viola are two different instruments with three overlapping strings of the same notes, and it is challenging for ordinary people or even musicians to distinguish the sound produced by these instruments. However, the classification of musical instrument pieces was barely performed by prior research. To solve this problem, we propose a technique using descriptive statistics to reliably distinguish between violin and viola music pieces. Likewise, a similar technique on the basis of histogram is introduced alongside the main descriptive statistics approach. These approaches are derived based on the nature of the instruments’ strings and the range of their pieces. We also solve the problem in the current literature which divide the audio into segments for processing instead of managing the whole song. Thereby, we compile a dataset of recordings that comprises of violin and viola solo pieces from the Baroque, Classical, Romantic, and Modern eras. Experiment results suggest that our approach achieves high accuracy on solo pieces as compared to other methods with 0.97 accuracy on Baroque pieces.

Botnets are a frequent threat to information systems on the Internet, capable of launching denial-of-service attacks, spreading spam and malware on a large scale. Detecting and preventing botnets is very important in cybersecurity. Previous studies have suggested anomaly-based, signature-based, or HoneyNet-based botnet detection solutions. This paper presents new solutions for detecting and classifying families of Domain Generation Algorithm (DGA) botnets. Our solution can be applied in practice to disable botnets even if they have infected the computer. Our works help solve two problems, including binary classification and multiclass classification, specifically: (1) Determining whether a domain name is malicious or benign; (2) For malicious domains, identify their DGA botnet family. We proposed two deep learning models called LA_Bin07 and LA_Mul07 by combining the LSTM network and Attention layer. Our evaluation used the UMUDGA dataset recently published in 2020, with 50 DGA botnet families. The experimental results show that the LA_Bin07 and LA_Mul07 models solve the DGA botnets problem for binary and multiclass classification problems with very high accuracy.

This article presents a new holistic and efficient approach to big data analysis. We introduce a new parallel algorithm, known asATrie Group Join (ATGJ), that integrates join, grouping and aggregation operations to accelerate big data analytical workloads in in-memory column-stores. ATGJ performs a single scan of the fact columns and uses a mixture of data and task parallelism for the optimal use of computing resources. It uses a novel technique to perform group-by and aggregation realising the grouping attributes as a tree shaped deterministic finite automation known asAggregate TrieorATrie. ATrie facilitates grouping of attributes and processing of data in tight loops that significantly improves the performance on modern hardware. Unlike other competing algorithms, use of ATrie avoids the creation of multiple data structures with the increasing number of dimension tables and grouping attributes. Also, we demonstrate that ATGJ performs efficiently even when the ATrie becomes bushy. We evaluated the algorithm using Star Schema Benchmark (SSBM) to show that it is significantly faster and scales better than other algorithms for the number of concurrent threads, the number of group-by attributes, the data set size and the query complexity.

Abstract Medical images play a fundamental role in disease screening, and automated evaluation of these images is widely preferred in hospitals. Recently, Convolutional Neural Network (CNN) supported medical data assessment is widely adopted to inspect a set of medical imaging modalities. Extraction of the leukocyte section from a thin blood smear image is one of the essential procedures during the preliminary disease screening process. The conventional segmentation needs complex/hybrid procedures to extract the necessary section and the results achieved with conventional methods sometime tender poor results. Hence, this research aims to implement the CNN-assisted image segmentation scheme to extract the leukocyte section from the RGB scaled hematological images. The proposed work employs various CNN-based segmentation schemes, such as SegNet, U-Net, and VGG-UNet. We used the images from the Leukocyte Images for Segmentation and Classification (LISC) database. In this work, five classes of the leukocytes are considered, and each CNN segmentation scheme is separately implemented and evaluated with the ground-truth image. The experimental outcome of the proposed work confirms that the overall results accomplished with the VGG-UNet are better (Jaccard-Index = 91.5124%, Dice-Coefficient = 94.4080%, and Accuracy = 97.7316%) than those of the SegNet and U-Net schemes Finally, the merit of the proposed scheme is also confirmed using other similar image datasets, such as Blood Cell Count and Detection (BCCD) database and ALL-IDB2. The attained result confirms that the proposed scheme works well on hematological images and offers better performance measure values.

Summary As a crowdsourcing map platform, OpenStreetMap (OSM) relies on public contributions to enhance its dataset where the contributors can create, modify or remove features from the maps or share their trajectory trips in the repository. The majority of the data provided in a crowdsourcing platform are manually created and reviewed to suit real‐world conditions, hence human perception is the key indicator to consider the correctness of the data. One of the data that is provided by crowdsourcing platform is public trajectory. Public trajectory data contains details of historical trips obtained from contributors' GPS logger devices that are embedded in mobile devices, wearable devices, satnavs, or vehicle GPS trackers to record the user's trajectory path. While public trajectory data can be used as an alternate data source for human movement analysis, this crowdsourced dataset is also prone to noise and inaccuracy which makes the preprocessing step an important phase prior of any processing step. In this article, we discuss the characteristics and the most common noise from crowdsourcing GPS trajectories and utilize a non‐map‐matching approach convex hull‐based reduction method to minimize spike noise, followed by granularity reduction to reduce the number of trajectory points while maintaining the nature of the trajectories.

Summary Column‐stores perform significantly better than row‐stores on analytical workloads such as those found in data warehouses, decision support, and business intelligence applications. As mainstream data warehouses are growing into multi‐terabyte range, decision support queries should be processed in parallel to achieve adequate performance. Researchers of the column‐oriented join queries assume an unlimited reserve of main memory and focus on minimising execution time. However, some analytics require a large amount of memory to calculate intermediate results, and some interactive analytics require a fast initial response time even though queries need to process a large amount of data. Motivated by these requirements, we present a new progressive parallel star algorithm for main memory column‐stores known as “Nimble Join.” Equipped with multi‐attribute array table and a novel progressive materialisation technique, Nimble Join requires half the memory space and has two times faster initial response whilst having comparable execution time to the existing algorithm.

Due to the growing popularity of indoor location-based services, indoor data management has received significant research attention in the past few years. However, we observe that the existing indexing and query processing techniques for the indoor space do not fully exploit the properties of the indoor space. Consequently, they provide below par performance which makes them unsuitable for large indoor venues with high query workloads. In this paper, we first propose two novel indexes called Indoor Partitioning Tree (IP-Tree) and Vivid IP-Tree (VIP-Tree) that are carefully designed by utilizing the properties of indoor venues. The proposed indexes are lightweight, have small pre-processing cost and provide near-optimal performance for shortest distance and shortest path queries. We are also the first to study spatial keyword queries in indoor venues. We propose a novel data structure called Keyword Partitioning Tree (KP-Tree) that indexes objects in an indoor partition. We propose an efficient algorithm based on VIP-Tree and KP-Trees to efficiently answer spatial keyword queries. Our extensive experimental study on real and synthetic data sets demonstrates that our proposed indexes outperform the existing solutions by several orders of magnitude.

Abstract Retrieval of arbitrary-shaped surrounding data objects has many potential applications in spatial databases including nearby arbitrary-shaped object-of-interests retrieval surrounding a user. In this paper, we propose directional zone concept to determine directional similarity among spatial data objects. Then, we propose a novel query, called direction-based spatial skyline (DSS), which retrieves non-dominated arbitrary-shaped surrounding data objects in spatial databases for a user. The proposed DSS query is rotationally invariant as well as fair. We develop efficient algorithms for processing DSS queries in spatial databases by designing novel data pruning techniques using R-Tree data indexing scheme. Finally, we demonstrate the effectiveness and efficiency of our approach by conducting extensive experiments with real datasets.

Trajectory is the path that is formed because of the moving object positioning history. Based on where it happened, trajectory can be formed in indoor or outdoor environment. While outdoor trajectory can be reconstructed by GPS technology, this technology is not sufficient to be used in indoor environment. However, there are some embedded sensors in mobile devices that can be utilized to track and reconstruct trajectory in indoor environment without utilizing GPS technology. In this paper, we propose the method to track and reconstruct trajectory for indoor environment using embedded mobiles sensors. Our experiment shows that these sensors are capable in tracking and reconstructing indoor trajectories without using any GPS technologies.

A route planning query has many real-world applications and has been studied extensively in outdoor spaces such as road networks or Euclidean space. Despite its many applications in indoor venues (e.g., shopping centres, airports), almost all existing studies are specifically designed for outdoor spaces and do not take into account unique properties of the indoor spaces such as hallways, stairs, escalators, rooms etc. We identify this research gap and formally define the problem of category aware multi-criteria route planning query, denoted by CAM, which returns the optimal route from an indoor source point to an indoor target point that passes through at least one indoor point from each given category while minimizing the total cost of the route in terms of travel distance and other relevant attributes. We show that CAM query is NP-hard. We propose an efficient approximation algorithm which generates high-quality results. We provide an extensive experimental study conducted on the largest shopping centre in Australia and compare our algorithms with alternative approaches. The experiments demonstrate that our algorithm is highly efficient and produces quality results.

In the age of smartphones, finding the nearest points of interest (POIs) is a highly relevant problem. A popular way to solve this is to use a k Nearest Neighbor (kNN) query to retrieve POIs by their road network distances from a query location. However, we find that existing kNN methods have not been carefully compared. We present a detailed and fair experimental study of the state-of-the-art, documenting the many insights gleaned along the way. Notably, a long overlooked Euclidean distance heuristic is often the best performing method by a wide margin. We have also released all code as open-source for readers to reproduce experiments and easily add methods or queries to the testbed for new studies.

We consider the k-Nearest Neighbour problem in a two-dimensional Euclidean plane with obstacles (OkNN). Existing and state of the art algorithms for OkNN are based on incremental visibility graphs and as such suffer from a well known disadvantage: costly and online visibility checking with quadratic worst-case running times. In this work we develop a new OkNN algorithm which avoids these disadvantages by representing the traversable space as a collection of convex polygons; i.e. a Navigation Mesh. We then adapt an recent and optimal navigation mesh algorithm, Polyanya, from the single-source single-target setting to the the multi-target case. We also give two new heuristics for OkNN. In a range of empirical comparisons we show that our approach can be orders of magnitude faster than competing methods that rely on visibility graphs.

In this paper, we study a new type of indoor queries, called the indoor trip planning query (iTPQ). We have observed that the existing methods for outdoor spaces cannot be applied directly to indoor spaces, due to the difference in the underlying networks. Outdoor spaces, which are normally represented as spatial road networks, are commonly modelled as a graph. In contrast, indoor spaces have distinct features (e.g. rooms, doors, hallways) that do not exist in road networks. So far, no specific solutions have been proposed for iTPQ. Even if outdoor techniques are revised for iTPQ, they fail to process iTPQ efficiently. In this paper, we propose an indoor-specific technique, based on the indoor VIP-Tree, called the VIP-Tree neighbor expansion (VNE) method, that also includes new pruning techniques in both pre-processing and query processing phases. Our experimental results show that our proposed method VNE outperforms other indoor and outdoor algorithms by several orders of magnitude in terms of processing time with low indexing cost.

The widespread proliferation of location-acquisition techniques and GPS-embedded mobile devices have resulted in the generation of geo-tagged data at unprecedented scale and have essentially enhanced the user experience in location-based services associated with social networks. Such location-based social networks allow people to record and share their location and are a rich source of information which can be exploited to study people’s various attributes and characteristics to provide various Geo-Social (GS) services. In this paper, we propose two new types of queries called Top-k famous placesTkFP and Socio-Spatial Skyline QuerySSSQ query, which enrich the semantics of the conventional spatial queries by introducing a social relevance component. In addition, three approaches namely, (1) Social-First, (2) Spatial-First and (3) Hybrid are proposed to efficiently process TkFP and SSSQ queries. Finally, we conduct an extensive evaluation of the proposed schemes using real and synthetic datasets and demonstrate the effectiveness of the proposed approaches.

Summary Sensors are widely used in the field of manufacturing, railways, aerospace, cars, medicines, robotics, and many other aspects of our everyday life. There is an increasing need to capture, store, and analyse the dynamic semi‐structured data from those sensors. A similar growth of semi‐structured data in the modern web has led to the creation of NoSQL data stores for scalability, availability, and performance, whereas large‐scale data processing frameworks for parallel analysis. NoSQL data store such as MongoDB and data processing framework such as Apache Hadoop has been studied for scientific data analysis. However, there has been no study on MongoDB with Apache Spark, and there is a limited understanding of how sensor data management can benefit from these technologies, specifically for ingesting high‐velocity sensor data and parallel retrieval of high volume data. In this paper, we evaluate the performance of MongoDB sharding and no‐sharding databases with Apache Spark, to identify the right software environment for sensor data management.

Given a set of facilities and a set of users, a reverse nearest neighbors (RNN) query retrieves every user$u$for which the query facility$q$is its closest facility. Since$q$is the closest facility to$u$, the user$u$is said to be influenced by$q$. In this paper, we propose arelaxeddefinition of influence where a user$u$is said to be influenced by not only its closest facility but also every other facility that isalmostas close to$u$as its closest facility is. Based on this definition of influence, we propose reverse approximate nearest neighbors (RANN) queries. Formally, given a value$x>1$, an RANN query$q$returns every user$u$for which$dist(u,q) \leq x\times NNDist(u)$where$NNDist(u)$denotes the distance between a user$u$and its nearest facility, i.e.,$q$is an approximate nearest neighbor of$u$. In this paper, we study bothsnapshotandcontinuousversions of RANN queries. In a snapshot RANN query, the underlying data sets do not change and the results of a query are to be computed only once. In the continuous version, the users continuously change their locations and the results of RANN queries are to be continuously monitored. Based on effective pruning techniques and several non-trivial observations, we propose efficient RANN query processing algorithms for both the snapshot and continuous RANN queries. We conduct extensive experiments on both real and synthetic data sets and demonstrate that our algorithm for both snapshot and continuous queries are significantly better than the competitors.

Every database systems needs to employ searching algorithms to locate and retrieve data. With the proliferation of NoSQL databases, there is a need to design search algorithms that are optimised for the non-relational files and record structures. We propose several search algorithms for documentbased databases. The algorithms were designed with parallelism in mind, considering many of the NoSQL databases have very large volume of data. The algorithms were implemented and extensively tested on MongoDB and Apache Spark environment. The test results shows a promising performance of our proposed algorithms.

In a mobile Peer-to-Peer (P2P) environment, where inherent resource constraints (e.g. battery, bandwidth and computing power) exist, the notion of reliability and efficiency especially around communication of messages between peers is a crucial factor. In this paper, we introduce a trustworthy token-passing multi-point relays (TOP) data dissemination scheme for moving objects in wireless ad-hoc networks. The proposed scheme encompasses the trustworthy model and location-based scheduling technique capable of determining the most optimal schedule for the target peers to receive messages based on the location and mobility parameter. The performance of the proposed approach is compared against the existing state of techniques namely pure flooding and Trustworthiness-based Broadcast (TBB) scheme. The experimental evaluation includes a number of metrics, such as transmission cost, computational cost and message deliverability, of which the results showed promising performance of the proposed scheme.

A k nearest neighbor ( k NN) query on road networks retrieves the k closest points of interest (POIs) by their network distances from a given location. Today, in the era of ubiquitous mobile computing, this is a highly pertinent query. While Euclidean distance has been used as a heuristic to search for the closest POIs by their road network distance, its efficacy has not been thoroughly investigated. The most recent methods have shown significant improvement in query performance. Earlier studies, which proposed disk-based indexes, were compared to the current state-of-the-art in main memory. However, recent studies have shown that main memory comparisons can be challenging and require careful adaptation. This paper presents an extensive experimental investigation in main memory to settle these and several other issues. We use efficient and fair memory-resident implementations of each method to reproduce past experiments and conduct additional comparisons for several overlooked evaluations. Notably we revisit a previously discarded technique (IER) showing that, through a simple improvement, it is often the best performing technique.

Due to the growing popularity of indoor location-based services, indoor data management has received significant research attention in the past few years. However, we observe that the existing indexing and query processing techniques for the indoor space do not fully exploit the properties of the indoor space. Consequently, they provide below par performance which makes them unsuitable for large indoor venues with high query workloads. In this paper, we propose two novel indexes called Indoor Partitioning Tree (IP-Tree) and Vivid IP-Tree (VIP-Tree) that are carefully designed by utilizing the properties of indoor venues. The proposed indexes are lightweight, have small pre-processing cost and provide near-optimal performance for shortest distance and shortest path queries. We also present efficient algorithms for other spatial queries such as k nearest neighbors queries and range queries. Our extensive experimental study on real and synthetic data sets demonstrates that our proposed indexes outperform the existing algorithms by several orders of magnitude.

In Reverse Nearest Neighbour (RNN) Query, every single object in the space has a certain region where all objects inside this region will think of the query object as their nearest neighbour. Other objects that are outside the region will not consider the query object as their nearest neighbour. In many cases, we might encounter a situation where we want to find this kind of region for several objects altogether, instead of a single object. Current RNN region approach cannot be used for this problem. Therefore we propose Group Reverse kNN as a solution, which we will find a specific region based on multiple query objects. So any objects located inside this region will always consider all of the query objects as the nearest compare to the non-query objects. Our experiments demonstrate the performance efficiency of the proposed Group Reverse kNN algorithm.

Summary With the increasing popularity of Global Positioning System (GPS) technologies, many applications have been developed that are able to browse and monitor their GPS tracks on mobile objects. However, a large number of applications focus only on the region (not the exact coordinate location) where mobile objects are located. Not only the exact coordinate locations of moving objects are not needed but also the exact coordinate locations may sometime be distorted because of the inaccuracy of tracking systems. Therefore, in this paper, we propose an efficient data structure index for the moving objects based on their regional location. The topographical outdoor‐tree (TO‐tree) is based on the connectivity (adjacency) between outdoor cells space. The proposed index can support and enable efficient query processing and efficient updates of moving objects in outdoor space cells. The TO‐tree can serve spatial, topological, and adjacency queries. Experiments suggest that the TO‐tree performs efficiently and incurs less update cost while maintaining satisfactory performance. Copyright © 2013 John Wiley & Sons, Ltd.

Summary In this paper, we introduce a new notion of Ontology as a Service, in which the ontology tailoring process serves as a service in the cloud. To illustrate Ontology as a Service, we propose sub‐ontology extraction and extension, whereby a sub‐ontology is extracted from the main ontology and is then extended to cover new concepts and relationships. We use a maximum extraction method to facilitate this. Unified Medical Language System meta‐thesaurus ontology is used as a walk‐through case study to illustrate our proposed methods. Copyright © 2014 John Wiley & Sons, Ltd.

Summary Ontology as a formal representation of a domain knowledge has played an important role in a distributed environment whereby semantic interoperability is a major factor. In this paper, we particularly focus on a distributed ontology framework that utilizes Semantic Grid resources. The semantic representation in a machine‐understandable format (i.e., an ontology) is the backbone that enables interoperability between different user nodes in a semantic grid environment. However, the domain knowledge represented within an ontology is not static. From time to time, its concepts, properties and relationships need to be replaced or updated. Although many existing work have been focusing on how to utilize an ontology to support interoperability within a distributed environment, they often assume a rather static ontology. This paper focuses on formalizing and validating the process of ontology update, whereby sections of one ontologyO2are replaced by a subset extracted from another ontologyO1. In the first phase, a subsetS1is extracted from ontologyO1. Then in the second phase, the concepts in ontologyO2are replaced byS1. At the end of the process, the resulting ontologyO2must still be a valid ontology. A semantic completeness checking also needs to be conducted so that the updated ontologyO2is complete. A case study based on the Unified Medical Language System ontology from the medical informatics domain is presented. We use a semantic grid environment to build a framework for reusing, extracting and updating an ontology using a SOA. These allow the subset extracted from one ontology, to replace sections of another ontology, using shared resources in the semantic grid environment. A prototype of the framework is built using Web Services and a complexity evaluation measure is presented. The results of several simulations show ontology update in the semantic grid is a viable solution and can be further optimized. Copyright © 2012 John Wiley & Sons, Ltd.

Reverse Nearest Neighbour queries is known for the heavyweight algorithm that makes it difficult to be implemented in mobile devices due to high computations needed to verify the objects. Since the rapid development of mobile devices' hardware and also the new lightweight approach in solving the Reverse Nearest Neighbour problem, this problem can be solved in mobile devices. In this paper, we implemented the Contact Zone algorithm to create bichromatic reverse nearest neighbour region for a specific query point on mobile devices. The model is developed in a closed wireless network and various types of mobile devices with different hardware specifications are used. Our experiments show that RNN queries by region can be solved in mobile devices and different mobile CPUs do not give significant performance in processing the queries.

In a mobile environment, data broadcast paradigm has been recognised as an effective and scalable mechanism to disseminate frequently requested information to a large number of mobile users. This paper presents the design and implementation of a power preserving mobile broadcast system. The broadcast system is designed to serve transitive queries or queries that access related data items belonging to different tables in the relational databases. The focus of this paper is revolved around the implementation of three specific data broadcast schemes, namely: (i) a filtering technique for mobile device to perform transitive queries and display the desired data from incoming multiple entity types broadcast data items, (ii) the index broadcast scheme to predict the arrival of the desired data so that power utilization can be minimized, and (iii) multiple channel environments to allow mobile device to tune into multiple broadcast channels to receive the desired data. We showcase the efficacy of these data broadcast schemes through the development of the prototype system with a share indices price application.

With the popularity of mobile devices, such as mobile phones and tablets, mobile users are taking more advantages of mobile computing. Through the applications in mobile devices, mobile users are able to search for the nearby spatial objects like restaurants and hotels. Hence, in this paper, we propose a range-based nearest neighbour search algorithm, which is named as Range-kNN[17]. Our algorithm focuses on expanding the query point to a query range, according to this query range, the interesting objects both inside and outside the query range are retrieved based on a Voronoi-based search algorithm. In the experiment part, our proposed algorithm is proved to be quite efficient and scalable.

SUMMARY Common reverse nearest neighbor queries in spatial database run in an inefficient way because they need to check a query result with almost every nearest neighbor. This wastes many time and resources, making this approach unsuitable for mobile computation. Instead of using the neighbors as candidates for the query result, a region approach can be used to answer the query. By using this approach, any objects located in the region will be considered candidate results for the query. To reduce the cost of creating the region, we introduce the concept of a contact zone, a method that can identify the right region generator points without having to process the whole points in the space, hence make reverse nearest neighbor queries by region possible to be run in mobile devices. Copyright © 2013 John Wiley & Sons, Ltd.

With rapid developments in indoor positioning technologies such as wireless communications, RFID and Bluetooth, the tracking of indoor moving objects has become easier. The indexing of moving objects in indoor spaces is different from outdoor spaces in many respects such as positioning technologies and measurements. Therefore, in this paper, we propose a new adjacency index structure for moving objects in indoor spaces that take into account both spatial and temporal properties. The index is based on the idea of connectivity (adjacency)between the indoor space cells. Furthermore, we use a non-leaf node time stamping method to store temporal data, which can enable and support the temporal queries in an indoor space. An empirical performance study suggests that the developed data structure is effective and robust.

Data broadcast with its scalability feature provides a strong backbone for the digital information delivery. Such a feature is especially significant for mobile users with inherent power limitations in asymmetric communication environments. This paper presents a specific broadcast ordering scheme supported by advanced structure and access mechanism for ad-hoc queries in mobile data broadcast environments. The proposed scheme aims to minimize both query-access and tuning times by specifying a new message and ordering structure. As a proof of concept, we carry out experimentation of the proposed scheme in comparison with the conventional models. The result of the experiments are presented and discussed in the paper.

The increasing use of location-based services has raised many issues of decision support and resource allocation. A crucial problem is how to solve queries of Group k-Nearest Neighbour (GkNN). A typical example of a GkNN query is finding one or many nearest meeting places for a group of people. Existing methods mostly rely on a centralised base station. However, mobile P2P systems offer many benefits, including self-organization, fault-tolerance and load-balancing. In this study, we propose and evaluate a novel P2P algorithm focusing on GkNN queries, in which mobile query objects and static objects of interest are of two different categories. The algorithm is evaluated in the MiXiM simulation framework with both real and synthetic datasets. The results show the practical feasibility of the P2P approach for solving GkNN queries for mobile networks.

As the number of mobile devices is experiencing an explosive growth, mobile query processing has become an important application of mobile devices. One of the most frequently used mobile queries is range queries - retrieving surrounding objects of interest. As mobile devices are moving, these range queries are literally moving range queries. The main problem of processing mobile moving range queries is how to know when the surrounding objects of interest are no longer relevant (and the previously distant objects of interest have become relevant) since the mobile device has already moved to a new location. Past researches have proposed the use of safe region - an area where the set of objects of interest to the mobile device does not change. However, when the query leaves the safe region, the mobile device has to reprocess the query. Knowing when and where the mobile device will leave a safe region is widely known as a difficult problem. To solve this problem, we propose two novel methods: (i) efficient construction of the safe region by using only two objects closest to the border of the moving mobile device, and (ii) periodic monitoring the position of the mobile device. Our evaluation shows that our method enlarges the safe region compared with previous methods, giving the mobile device a wider range to roam, and therefore, reducing computation and communication costs.

The increasing use of mobile communications has raised many issues of decision support and resource allocation. A crucial problem is how to solve queries of Reverse Nearest Neighbor (RNN). An RNN query returns all objects that consider the query object as their nearest neighbor. Existing methods mostly rely on a centralized base station. However, mobile P2P systems offer many benefits, including self-organization, fault-tolerance and load-balancing. In this study, we propose two P2P algorithms focusing on bichromatic RNN queries, in which mobile query objects and static objects of interest are of two different categories, based on a boundary polygon around the mobile query object. The Exhaustive Search Algorithm makes use of all information from the peers to aim at high accuracy rate while the Optimized Search Algorithm reduces the number of queried peers. The algorithms are evaluated in MiXiM simulation framework with a real dataset. The results show the practical feasibility of the P2P approach in solving bichromatic RNN queries for mobile networks.

A participatory mobile sensing system is designed to enable clients to voluntarily collect environmental data using embedded sensors and a mobile device while going about their daily activities. Due to the spatio-temporal nature of the data, and the significant benefits of the data to the general public, it is necessary to employ an efficient and effective query processing model for the mobile clients to access the data that can be visualized via an interactive multimedia interface. This article introduces a unified on-demand and data broadcast model to serve queries in the context of a mobile sensing system. The contributions of this article include the following: (i) it presents a novel data structure and indexing method to support the system; (ii) it provides flexibility for the client to issue query using on-demand or broadcast channel according to the server load and broadcast schedule; (iii) it enables new data access and processing for the mobile client; and (iv) it is designed for a multiple channels/receivers environment in a 4G wireless network. The proposed model uses a holistic query processing approach for the mobile sensing system that offers substantial efficiency and autonomy for mobile clients when retrieving data. The results of the experiments undertaken affirm the effectiveness of its performance.

This paper introduces a novel clustering-based broadcast scheduling technique for mobile nearest-neighbor (NN) query processing in cyber physical systems. An efficient index structure is presented to guide mobile clients to the NN-objects. The proposed broadcast scheduling and indexing is aimed at minimizing query access time and energy consumption of the clients when retrieving NN-objects through wireless channels. We have experimentally studied the proposed scheme and its comparison with the state-of-the-art methods. The results suggest the efficacy of our proposed approach in offering minimum latency and energy consumption, which is critically important especially for resource-constrained wireless environments.

The sizes of databases have seen exponential growth in the past, and such growth is expected to accelerate in the future, with the steady drop in storage cost accompanied by a rapid increase in storage capacity. Many years ago, a terabyte database was considered to be large, but nowadays they are sometimes regarded as small, and the daily volumes of data being added to some databases are measured in terabytes. In the future, petabyte and exabyte databases will be common. With such volumes of data, it is evident that the sequential processing paradigm will be unable to cope, for example, even assuming a data rate of 1 terabyte per second, reading through a petabyte database will take over 10 days. To effectively manage such volumes of data, it is necessary to allocate multiple resources to it, very often massively so. The processing of databases of such astronomical proportions requires an understanding of how high-performance systems and parallelism work. Besides the massive volume of data in the database to be processed, some data has been distributed across the globe in a Grid environment. These massive data centres are also a part of the emergence of Cloud computing, where data access has shifted from local machines to powerful servers hosting web applications and services, making data access across the Internet using standard web browsers pervasive. This adds another dimension to such systems. This talk, based on our recent published book [1], discusses fundamental understanding of parallelism in data-intensive applications, and demonstrates how to develop faster capabilities to support them. This includes the importance of indexing in parallel systems [2-4], specialized algorithms to support various query processing [5-9], as well as objectoriented scheme [10-12]. Parallelism in databases has been around since the early 1980s, when many researchers in this area aspired to build large special-purpose database machines -- databases employing dedicated specialized parallel hardware. Some projects were born, including Bubba, Gamma, etc. These came and went. However, commercial DBMS vendors quickly realized the importance of supporting high performance for large databases, and many of them have incorporated parallelism and grid features into their products. Their commitment to high-performance systems and parallelism, as well as grid configurations, shows the importance and inevitability of parallelism. There have been an increase number of researches in high performance parallel database processing in the last five years (2008-12). Data partitioning is still the fundamental issue in high performance database processing [13, 14]. The data itself is getting more complex, including XML-based data [15, 16], bio-informatics data [17, 18], and data streams [19, 20]. These new data types require new approaches to parallel processing. In addition, database transactions [21, 22] are still a major focus in many high performance database systems, such as grid transactions. We also see an increasing growth of new application domains, broadly categorized as data-intensive applications, including data warehousing and online analytic processing (OLAP) [23-25]. Therefore, it is critical to understand the underlying principle of data parallelism, before specialized and new application domains can be properly addressed.

Geographical information systems (GIS) and applications assist us in commuting, traveling and locating our points of interests. The efficient implementation and support of spatial queries in those systems is of particular interest and importance. The use of a Voronoi diagram has traditionally been applied to computational geometry. In this paper, we will show how a Voronoi diagram can be applied to support spatial queries in GIS systems, and in particular to reverse nearest neighbor (RNN) queries. An RNN query retrieves the set of interest objects having the query object as the nearest neighbor among other objects. Two cases of RNN queries are: monochromatic (MRNN) and bichromatic (BRNN). In the MRNN, the interest objects and the query object are of the same type, whereas in the BRNN they are of two different types. Due to the shortcomings of solutions for BRNN in the literature, we develop a new approach and algorithm, named the ‘2Vor BRNN algorithm’, for processing this query type in the context of the spatial network database (SNDB). Our novel approach extends the previous work and uses the ‘order-2 network Voronoi diagram’ to provide a more efficient solution for the BRNN. In addition, we experimentally confirm that the proposed algorithm outperforms the previous one in terms of memory used and response time.

This issue features a special issue on ‘Computational Science and Its Applications’. Computational Science is the main pillar of most of the present research, industrial and commercial activities and plays a unique role in exploiting ICT innovative technologies. Owing to the latest development and the availability of high-performance computing, including parallel computing, grid computing, and cloud computing, there is a critical need to employ efficient and effective computational methods and algorithms in various applications, including computational biology, computational geometry, computational physics, computation chemistry, computational finance, graphics and visualization, scientific data management, data mining, etc. This issue features selected papers from the International Conference on Computational Science and Its Applications (ICCSA2009) held in 29 June–1 July, 2009, Kyung Hee University, Suwon, South Korea. In addition to extended papers from ICCSA2009, a special issue CFP has been distributed to a wider community through various mailing lists. Finally, we selected five papers to be included in this issue. The first paper discusses data and knowledge grids. It basically combines grid computing and real-time service management and execution paradigms, which makes use of the service-oriented architecture and paradigm suited for the grid platform. The second focuses on grid and P2P systems, especially in the context of sharing paradigm. It discusses middleware and libraries for grid and P2P systems. The third paper also focuses on P2P, whereby it describes scalable group communication protocols. The fourth paper focuses on road network query processing, which can be adopted in a mobile environment. It particularly concentrates on range search in a continuous mobile dynamic. Finally, the fifth paper introduces context-aware semantic network similarity model, using an ontological approach. As general co-chairs and program co-chairs of ICCSA2009, as well as the guest editors of the special issue on Computational Science in the Concurrency and Computation journal, we would like to congratulate the authors whose papers appeared in this special issue. We would also like to thank the PC members of ICCSA2009 who conducted the initial reviewing process for the conference and external reviewers who conducted further reviews of extended papers submitted to this special issue.

Abstract Range search is one of the most common queries in the spatial databases and geographic information systems (GIS). Most range search processing depends on the length of the distance that expresses the relative position of the objects of interest in the Euclidean space or road networks. But, in reality, the expected result is normally constrained by other factors (e.g. number of spatial objects, pre‐defined area, and so forth.) rather than the distance alone; hence, range search should be comprehensively discussed in various scenarios. In this paper, we propose two constrained range search approaches based on network Voronoi diagram, namely Region Constrained Range (RCR) and k nearest neighbor Constrained Range (kCR), which make the range search query processing more flexible to satisfy different requirements in a complex environment. The performance of these approaches is analyzed and evaluated to illustrate that both of them can process constrained range search queries very efficiently. Copyright © 2010 John Wiley & Sons, Ltd.

A data warehouse is built as a layer on top of existing operational database systems. Once built, it has to be regularly updated (refreshed). Currently, most data warehouse approaches employ static refresh mechanisms whereby updates are based on a static timestamp, eg. once every day/week/quarter only. Whilst for some systems this might be adequate, others require a more rigorous approach ensuring that analysis is always 'up-to-date'. Static time interval for refreshing data warehouse is not adequate enough for systems with high update frequency. A real-time data warehouse incorporates operational data changes in real time. However, sometimes, it is often unnecessary or even inefficient to immediately refresh and send updates from the operational database into a data warehouse. In this paper, we propose a near real-time refresh mechanism that takes into consideration a number of measures: (i) Impact from record, (ii) Number of records affected, and (iii) Frequency Request Measure. The combination of these measures can accurately identify when the data warehouse needs to be strictly real-time, or near real-time (ie. right-time). Our experimentation shows that the proposed approach offers a significant benefit in terms of refresh operation cost in comparison to real-time warehousing, while at the same time still maintaining a high freshness level of the data warehouse.

This paper proposes a new global index structure and processing for location-dependent queries in mobile broadcast environments. The proposed scheme consists of two essential elements for addressing spatial queries in broadcast databases. These two elements are: (i) determine the client's location in relevant to the spatial model adopted by the broadcast scheme, and (ii) obtain the required object, which corresponds to the location of the client as determined by the model. The global index's concept will enhance the efficiency of the model. We explore the effectiveness of the proposed index scheme in single and multi channel environments. Performance comparisons with the earlier work through simulated-experiments have also been carried out and the results found have been promising.

The development of mobile devices and mobile databases boost many spatial queries over moving objects, most of existing mobile applications concentrate on processing mobile queries based on distance metric in Cartesian space. In reality, traveling time is another important metric for spatial queries rather than Euclidean distance or network distance. On the other hand, the spatial queries of moving object monitoring is also restricted by frequent updates, as a result, processing spatial queries over moving objects becomes a tough job, especially in road networks. In this paper, we proposes a time constrained range search query and applies this query over a set of objects moving on the road networks to get a continuous result. By experimental studies, we show that our proposed approach can solve time constrained range search queries properly and the approach for moving objects monitoring outperform its competitors.

Most query searches on road networks are either to find objects within a certain range (range search) or to find k nearest neighbors (kNN) on the actual road network map. In this paper, we propose a novel query, that is, path branch point (PBP). PBP can be defined as given a set of candidate interest objects and a pre-defined path starts from S and end at E, find a path which starts from S, via an interest point P and ends at E. This path should overlap with the user's ad hoc (pre-defined) path as much as possible with an acceptable distance increment. This is a novel query which is motivated by users' common requirements because most users have an ad hoc path in their daily travel and can tolerate a longer driving distance to some extent if they can drive on a familiar path. In this proposed approach, an Adjust Score is calculated for each path which is determined by overlapping distance and increased distance cost. Our experiment verifies the applicability of the proposed approach to solve the queries, which involves finding the optimal path branch points.

One of the most frequent queries in spatial and mobile databases is range search, which is originated from the construction of R-tree that limits the spatial database application to Euclidean distance. Nowadays, Geographic Information System (GIS) demands the applications to be practicable for factual distance, normally identified as network distance. Even though some algorithms are engaged in this area, network distance range search is still a time consuming and storage space occupation task. In this paper, we propose a novel approach which is based on Network Voronoi Diagram that is diffusely used in geometrical analysis. We are looking into how to improve the performance of range search query processing using Network Voronoi Diagram.

The semantic grid as the uniting concept of semantic web and grid computing, and its ontology technology provide an efficient data retrieval methodology in widely distributed semantic grid resources over the Internet. As the number of semantic grid resources increase, e.g., ontology servers, the amount of data increases and managing job workflows is becoming increasingly complex. This paper proposed a validation framework for sub-ontology extraction workflows in our proposed semantic grid computing environment. We considered two ontology optimization schemes and design its workflow models using Petri Net. The workflow for each model is described and validated. The results justify the feasibilities of our proposed validation framework of the aforementioned models which can be used as building blocks to model large and efficient sub-ontology extraction workflows in a semantic grid.

This tutorial will be based on the recently published book, High-Performance Parallel Database Processing and Grid Databases (John Wiley & Sons, 2008). The sizes of databases have seen exponential growth in the past and such growth is expected to accelerate in the future, with the steady drop in storage cost accompanied by a rapid increase in storage capacity. To effectively manage such volumes of data, it is necessary to allocate multiple resources to it, very often massively so. The processing of databases of such astronomical proportions requires an understanding of how high performance systems and parallelism work. Besides the massive volume of data in the database to be processed, some data has been distributed across the globe in a Grid environment. This important new book provides readers with a fundamental understanding of parallelism in data-intensive applications, and demonstrates how to develop faster capabilities to support them. It features not only the algorithms for database operations, but also quantitative analytical models, so that performance can be analyzed and evaluated more effectively.

Clustering as an intelligent technique for mining XML documents has been utilised as an excellent way of grouping the documents by their content or structure. A main step in many distance based XML clustering algorithms is to calculate pair-wise distances between documents; naturally, a time-efficient technique requests the pair-wise distances to be determined in a timely manner. In case of dynamic XML documents, the amount of changes between versions cannot be predicted. Therefore, in case of clustered dynamic XML documents, if changes were little or if they affected only some of the clustered documents, recalculating pair-wise distances every time would be highly redundant. In this paper we propose a time-efficient technique to reassess pair- wise distances between clustered dynamic XML documents which change in time, without performing redundant calculations but considering the previously known distances and the set of changes which might have affected the documents versions.

Range search query processing has become one of the most important technologies in spatial and mobile databases. Most literature focuses on static range search extended from one point on both Euclidean distance and actual network distance, but there are only a few methods which can properly solve the problem for moving users, such as searching objects of interest on a road within a certain range. Although there are some techniques, which address continuous search, most approaches are absorbed in the KNN (k nearest neighbour) queries which are a different research area. In this paper, we propose two new methods to process continuous range search query in mobile computing. One is constructed using R-tree index based on Euclidean distance, and the other addresses the requirement on actual network distance.

The need to extract knowledge from web data warehousing just 'in-time' for decision making has increased significantly. An efficient system that can generate up-to-date analysis and decision making of the ever changing web-based information will play a very important role in the current global market and society. The new era of business intelligence and web databases brings in new research and development issues whereby the efficient integration of various web data is needed and timely analysis of data resources are vital. Web Data Warehousing is a growing area that addresses the need for an efficient web data summary to support decision making and ensure the quality of web data analysis.

This paper presents a novel schema mediation approach, called XMiner, for mining mediated schemas from a set of XML schemas. XMiner addresses three main problems resulting from the heterogeneous source schemas: nesting discrepancy, backward paths and schema discrepancy. XMiner discovers frequent substructures using frequent subtree mining algorithms, and then constructs a mediated schemas. XMiner aims to preserve the hierarchical structure as the best as possible while avoiding information loss. XMiner exploits structural context, forward/backward paths, and label semantics for matching, mapping and merging frequent substructures. Experiments on real and synthetic datasets are reported to show that XMiner offers acceptable performance and quality for large-scale application scenarios.

This paper presents a service oriented architecture (SOA) approach to a distributed framework for reusing, extracting and extending (tailoring) large domain ontologies in the semantic grid environment. The conceptual level of the framework describes how sub-ontologies are tailored while the architectural level of the framework describes the components of the framework that allows the tailoring process happen in the semantic grid environment. A prototype of the framework and a complexity evaluation measure are also provided.

In a wireless environment, data broadcast paradigm has been recognized as an effective and scalable mechanism to disseminate frequently requested information to a large number of clients. This paper presents the development of a multiple entity types wireless broadcast database system. The broadcast system is designed to serve transitive queries or queries that access related data items belonging to different entity types. The broadcast data are retrieved from a central database server. We apply three different data broadcast schemes including: (i), filtering technique for mobile device to perform transitive queries and display the desired data from incoming multiple entity types broadcast data items; (ii), the index broadcasting scheme designed to predict the arrival of the desired data to appropriately execute power conserving mode; (iii), incorporate multiple channel environments to allow mobile device to tune into multiple broadcast channels to receive the desired data. The proposed model uses a share indices price context to demonstrate the effective use of these data broadcast schemes.

An area of knowledge extraction is mobile user data mining. It is concerned with methods and algorithms on extracting interesting knowledge from mobile users through the data they have generated. These data are such as their user movement database and communication history. In group pattern mining, group patterns from a given user movement database is found based on spatio-temporal distances. Static objects are such as walls are present in the mobile environment. In this paper, we propose a method of group pattern mining through a user movement database with static objects defined to ensure the accuracy of result when static object exist. Our performance evaluation witnessed a reduction of group pattern found after static objects are defined in user movement databases compared to without. It proves that mobile users that are separated by static object can be detected and prevented from returning them as a valid group pattern.

With increasing demands for a proper and efficient XML data storage, XML-enabled database (XEnDB) has emerged as one of the popular answers. It claims to combine the strengths and limit the shortcomings of the traditional database management systems and native XML database. The implication is more research need to be done for this database family. This paper focuses on the XML update management in XEnDB. Our aim is to preserve the conceptual semantic constraints in XML data during update operations. The constraints are classified and represented in SQL/XML schema. Then, we propose the update methodology that utilizes the proposed schema and implement the method in one of the current XEnDB products

GroupBy-Join queries in SQL are queries involving the group by clause joining several tables. In this paper, we describe three parallelization techniques for GroupBby-Join queries, particularly the queries where the group-by clause can be performed before the join operation. We subsequently call this query "GroupBy-Before-Join" queries. Performance evaluation of the three parallel processing methods is also carried out

This paper explores a distributed ontology framework for tailoring ontologies in the semantic grid environment. The framework is divided into five main categories: ontology processing, ontology location, ontology connection, users' connection and algorithm location. A number of possible scenarios are discussed following two case studies that indicate how the framework can be manipulated and used in various situations. This framework helps developers design tools for tailoring ontologies in the semantic grid environment.

XML data can be stored in different types of databases including object-relational databases (ORDB). Using ORDB, we get the benefit of relational maturity and the richness of object-oriented modeling. One modeling concept that can be captured is composition hierarchy, which is a special type of relationship that shows an exclusive existence-dependent "part-of" relationship. This type of relationship frequently occurs in XML data, yet very often when the data is stored in a database repository, the "part-of" relationship is either flattened or split into an entirely separate table. In this paper we propose a model to preserve composition type in XML data into ORDB using the concept of row types. We use the Semantic Network diagram to represent the composition hierarchy in XML data. The composition hierarchy is divided into three types, namely single row composition, multi rows composition, and multi level composition. Each of these composition types will then be transformed into storage in an ORDB environment.

Data broadcasting is a scalable mechanism to disseminate information to a large number of mobile clients in a wireless environment. Our paper concerns with developing a data broadcasting system in a mobile environment, which involves data and index dissemination. The broadcasted data is retrieved from a database server. Subsequently, these data may be broadcasted periodically or aperiodically. As wireless environment inherent resource limitations, the use of indexing scheme will provide efficient data retrieval. We use share indices price context to demonstrate our proposed models. The models are developed using wireless ad-hoc network infrastructure.

Broadcast indexing is necessary to be applied in a wireless broadcast environment as such the scheme helps mobile clients to find the desired data instances efficiently. This is particularly important considering the inherent limitations in mobile environment. In this paper, we present a global indexing scheme for location dependent queries. The proposed scheme is designed to serve queries in which the query result is relevant to client's location. Global indexing scheme aims to minimise index access time while having all the advantages of index broadcasting. We develop a simulation model to find out the access time performance of global indexing scheme as compared to non-global indexing scheme. Additionally, we analyse the efficiency of valid scope used in the global index scheme as compared with an existing valid scope. It is found that global index performs substantially better than the existing indexing concept.

The new era of semantic Web has enabled users to extract semantically relevant data from the Web. The backbone of the semantic Web is a shared uniform structure which defines how Web information is split up regardless of the implementation language or the syntax used to represent the data. This structure is known as an ontology. As information on the Web increases significantly in size, Web ontologies also tend to grow bigger, to such an extent that they become too large to be used in their entirety by any single application. This has stimulated our work in the area of sub-ontology extraction where each user may extract optimized sub-ontologies from an existing base ontology. Sub-ontologies are valid independent ontologies, known as materialized ontologies, that are specifically extracted to meet certain needs. Because of the size of the original ontology, the process of repeatedly iterating the millions of nodes and relationships to form an optimized sub-ontology can be very extensive. Therefore we have identified the need for a distributed approach to the extraction process. As ontologies are currently widely used, our proposed approach for distributed ontology extraction will play an important role in improving the efficiency of information retrieval.

Data broadcasting strategy is known as a scalable way to disseminate information to mobile users. However, with a very large set of broadcast items, the query access time of mobile clients raise accordingly, due to high waiting time for mobile clients to find their data of interest. One possible solution is to split the database information into several broadcast channels. In this paper, we introduce taxonomy of index dissemination for multibroadcast channel based on B* tree structure. We consider three indexing schemes namely: (i) nonreplicated indexing scheme (NRI), (ii) partially-replicated indexing scheme (PRI), and (iii) fully-replicated indexing scheme (FRI). Simulation model is developed to find out the access time performance of each scheme.

SQL queries in the real world are replete with group-by and join operations. This type of queries is often known as "GroupBy-Join" queries. In some GroupBy-Join queries, it is desirable to perform group-by before join in order to achieve better performance. This subset of GroupBy-Join queries is called "GroupBy-Before-Join" queries. In this paper, we present a study on the parallelization of GroupBy-Before-Join queries, particularly by exploiting cluster architectures. From our study, we have learned that, in parallel query optimization, processing group-by operations as early as possible is not always desirable. On many occasions, performing data distribution first, before group-by, offers performance advantages. In this study, we also describe our cluster-based scheme.

The widespread use of the World Wide Web in recent years has opened up universal access to a vast number of information sources. An obstacle that affects the access to Web data is the lack of an information structure among and within Web pages. This raises a need for structured Web page management for efficient Web information searching. Our proposed structured Web page management is built in two stages: (i) HTML transformation to XML, and (ii) a navigation hierarchy. Also, we study how querying Web data can be accomplished in our structured Web page management, by which users may follow a navigation hierarchy to browse both inter-page and intra-page structures of the Web database and can specify queries for desired information.

One of the differences between relational and object-oriented databases (OODB) is that attributes in OODB can be of a collection type (e.g. sets, lists, arrays, bags) as well as a simple type (e.g., integer, string). Consequently, explicit join queries in OODB may be based on collection attributes. One form of collection join queries in OODB is "collection-equi join queries", where the joins are based on collection attributes and the queries check for an equality of both collection operands. Our previous work (1997) describes "Parallel Double Sort-Merge" algorithm for collection-equi join queries, Since the publication, we realize that we have overlooked the complexity of collection merging in the algorithm. In this paper, we not only present alternative solutions relating to the collection merging problem, but also introduce a new algorithm called "Parallel Sort-Hash" algorithm. The two algorithms play an important role in parallel object-oriented query processing, due to their superiority over the conventional join methods through relational division and intersection operators.