Abstract This study proposes a stack framework of light gradient boosting machine (LGBM) for Taiwan stock market index prediction. Stock market predictions have been regarded as a challenging task, as the market is affected by several factors such as political events, general economic conditions, institutional investors' choices, movement of the global market, psychology of investors. We construct a rich feature set to capture the impacts of global markets, institutional investors' choices, and the psychology of investors. A feature selection algorithm is proposed to choose important feature subset and enhance the training performance. To further improve the prediction accuracy, we employ stacking strategy to combine multiple classifiers together. A 10‐year period of the Taiwan stock exchange capitalization weighted stock index (TAIEX) is used to verify the performance of the proposed model. The experimental results suggest that our prediction model as well as the feature selection method can achieve good prediction performance.

Recently, the research community has introduced various methods for processing the location-based queries on a single type of objects in road networks. However, in real-life applications user may be interested in obtaining information about different types of objects, in terms of their neighboring relationship. The sets of different types of objects closer to each other are termed the heterogeneous neighboring object sets (HNOSs for short). In this paper, we present a novel type of location-based queries, the shortest average distance query (SADQ for short), on the HNOSs in road networks. Given a query object q and a distance d, the SADQ retrieves a HNOS, such that the road distances between any two objects in this set are less than or equal to d and its average road distance to q is the shortest among all HNOSs. As the SADQ provides object information by preserving both the spatial closeness of objects to the query object and the neighboring relationship between objects, it is useful in many fields and application domains. A grid index is first designed to manage information of data objects and road networks, and then the SADQ algorithm is developed, which is combined with the grid index to efficiently process the SADQ. Extensive experiments using real road network datasets demonstrate the efficiency of the proposed SADQ algorithm.

Currently, most of the processing techniques for the conventional location-based queries focus only on a single type of objects. However, in real-life applications the user may be interested in obtaining information about different types of objects, in terms of their neighboring relationship. We term the different types of objects closer to each other the heterogeneous neighboring objects (HNOs for short). Efficient processing of the location-based queries on the HNOs is more complicated than that on a single data source, because the neighboring relationship between the HNOs inevitably affects the query result. In this paper, we present a novel and important query on the HNOs, namely the shortest average-distance query (SAvgDQ for short), which can provide useful object information by considering both the spatial closeness of objects to the query object and the neighboring relationship between objects. Given a query object q and a distance d, the SAvgDQ retrieves a set of HNOs, such that the distances between any two objects in this set are less than or equal to d and its average distance to q is the smallest among all HNOs sets. To efficiently process the SAvgDQ, we develop an algorithm, the SAvgDQ processing algorithm, which operates based on three devised heuristics, the HNOs-qualifying heuristic, the HNOs-pruning heuristic, and the SAvgD-pruning heuristic, to reduce the number of distance computations required for query processing. Comprehensive experiments are conducted to demonstrate the effectiveness of the heuristics and the efficiency of the proposed algorithm.

Abstract The skyline search problem has been identified as one of the key problems in database research. None of the developed skyline search algorithms include the use of a filter to facilitate the search process. This paper proposes a novel modification involving the use of skyline filters to reduce the search space of a skyline problem by removing data points that cannot provide a viable skyline result. Three filters based on the concept of neural networks are proposed in this paper. The result is a reduction in execution time achieved through the reduction of the input tuples. The proposed filters may be used in conjunction with any existing skyline search algorithm. This is the first study to apply neural network technology to the skyline problem. Comprehensive simulation results demonstrate the effectiveness of the proposed skyline filtering system.

Continuous K-nearest skyline query (CKNSQ) is an important type of the spatio-temporal queries. Given a query time interval [ts, te] and a moving query object q, a CKNSQ is to retrieve the K-nearest skyline points of q at each time instant within [ts, te]. Different from the previous works, our work devotes to overcoming the past assumption that each object is static with certain dimensional values and located in road networks. In this paper, we focus on processing the CKNSQ over moving objects with uncertain dimensional values in Euclidean space and the velocity of each object (including the query object) varies within a known range. Such a query is called the continuous possible K-nearest skyline query (CPKNSQ). We first discuss the difficulties raised by the uncertainty of object and then propose the CPKNSQ algorithm operated with a data partitioning index, called the uncertain TPR-tree (UTPR-tree), to efficiently answer the CPKNSQ.

MOTIVATION: In current databases, there are many genes with inconsistent mapping positions between their cytogenetic annotations and sequence map positions. However, not all inconsistencies are the same. Some of them may be problematic which should be corrected in the future; while others may result from the imprecise nature of chromosomal banding which may be tolerable. It is important to stratify the cytogenetic position information into different confidence groups with the recognition of the impreciseness of cytogenetic banding. RESULTS: When plotting their cytogenetic annotations against sequence map positions on a 2D plane, the consistent genes tend to have a compact linear distribution; while genes with inconsistent positions are more scattered. The overlapping areas between these two groups are defined as the tolerable imprecision zones by linear regression and distance analysis. The system was implemented using sequence information from NCBI Map Viewer Build 36.3 and cytogenetic annotations from NCBI Entrez Gene. The genes' position information is classified into five confidence groups: inconsistent-intolerable, inconsistent-tolerable, consistent-imprecise, consistent-precise and consistent-rough. Using information from NCBI Map Viewer Build 36.3 and NCBI Entrez Gene, the percentages of these confidence groups are 1.4%, 7.0%, 54.0%, 35.4% and 2.2%, respectively. Using information from NCBI Map Viewer Build 36.3 and NCBI online Mendelian inheritance in man (OMIM), the percentages are 3.7%, 16.9%, 49.0%, 19.0% and 11.4%, respectively. Combining these two results, a confidence table of genes' position information was constructed. AVAILABILITY: The detailed results are accessible over the Internet at http://centrallab.hosp.ncku.edu.tw/imz.

More and more users or applications showed high interest in obtaining moving object locations from a wireless sensor network. However, a moving object usually updates its location very frequently, and thus, a great number of messages for updating the locations in the wireless sensor networks are incurred. In this paper, we propose an index structure, called the {\em Gossip-enabled Spatial Index Tree (GSI-tree)}, to support efficient communication for location updates. Our idea is to utilize the gossip property of the sensor communication to let the neighboring paths of the GSI-tree share the transmitted message. In this way, the nodes managing a past location can deregister the object location independently by hearing the registration messages from the neighboring nodes.

Spatio-temporal databases aim at combining the spatial and temporal characteristics of data. The continuous K-Nearest Neighbor (CKNN) query is an important type of spatio-temporal query that finds the K-Nearest Neighbors (KNNs) of a moving query object at each time instant within a given time interval [ts, te]. In this paper, we investigate how to process a CKNN query efficiently under the situation that each object moves with an uncertain velocity. This uncertainty on the velocity of each object inevitably results in high complexity of the CKNN problem. We propose a cost-effective PKNN algorithm to tackle the complicated problem incurred by this uncertainty.

This paper presents the design of Pool, an efficient and scalable data storage scheme for supporting multidimensional queries. The foundation of the work that makes the Pool approach superior in executing multi-dimensional queries is that it provides a novel and elegant higher dimension to two-dimensional data mapping mechanism. Our performance study proves the efficiency of the design.

Location dependent data (LDD) are those closedly related to specific locations. Services involving LDD are becoming more and more popular in recent years. To provide a high quality of service for these applications, prefetching LDD before a mobile client reaches the LDD site is an important factor to consider. In this paper, we analyze this problem and propose a benefit-oriented method for cost-effective prefetch of LDD. Our performance study shows that the method is superior to other traditional methods.

We refer "time-constrained services” to those requests that have to be replied to within a certain client-expected time duration. If the answer cannot reach the client within this expected time, the value of the information may seriously degrade or even become useless. On-demand channels may not be able to handle all time-constrained services without degrading the performance. How to handle these services in broadcast channels becomes crucial to balance the load of wireless systems. In this paper, we study this problem and find the minimum number of broadcast channels required for such a task. Also, we propose solutions for this problem when the available channels are insufficient. Our performance result reveals that only a moderate number of channels is required to promote these time-constrained services.

Data broadcasting is an efficient and highly scalable technique for delivering data to mobile clients in wireless environments. In this paper, we study the problem of scheduling broadcast data that are with an expected time within which the client is expecting to receive the data item. We analyze the problem and derive the minimum number of broadcast channels required for such a task. Also, we discuss the problems when the number of available channels is not enough. We propose novel solutions for both of the cases and the performance study indicates that our method is much better than the previous ones and performs very close to optimal.

MOTIVATION: Staining the human metaphase chromosomes reveals characteristic banding patterns known as cytogenetic bands or cytobands. Using technologies based on metaphase chromosomes, researchers have accumulated much knowledge about the correlations between human diseases and specific cytoband aberrations, indicating the presence of disease-associated genes in those bands. With the progress of human genome project and techniques such as fluorescent in situ hybridization, many genes have been assigned to the cytobands and annotated in public databases, making it possible to find all genes in the disease-related cytobands through database queries. However, finding genes in cytobands remains an imprecise process, partly due to the insufficiency of current methods for cytoband queries, especially for those based on cytogenetic annotations. RESULTS: By transforming the cytoband annotations into numerical segments, a new query method is developed that is able to accurately define any cytogenetic ranges in human chromosomes. A query system (designated cytoband query sys CQS) is implemented using cytogenetic annotations in the public domain. Judged by a performance test, CQS executed as accurately as expected using cytogenetic annotations from NCBI Map Viewer. The new method is scalable and can be applied to genomes from other species. AVAILABILITY: The CQS is freely accessible over the Internet at http://moris.csie.ncku.edu.tw/cqs/ CONTACT: [email protected] SUPPLEMENTARY INFORMATION: http://moris.csie.ncku.edu.tw/cqs/

Data delivery is through broadcast in wireless information systems due to the asymmetric communication property. However, broadcasting data easily wastes large access time because the large amount of data pages needs to be broadcast. In this paper we propose three compression-based strategies considering access order to reduce access time. Then, the expected access time of three proposed strategies is also derived by using the probability model. Our analytic and experimental results show that the compression-based broadcast strategies can dramatically reduce the access time for mobile users (MU).

Browsing Web pages through wireless devices will become more and more popular in the near future. However, accessing a large chunk of Web data incurs a great amount of access latency while a mobile user migrates across cells. This paper investigates this problem and proposes an effective way of delivering such data to a mobile user in a ubiquitous computing system. Our data delivery (/spl Dscr//sup 2/) strategy is based on the dynamic programming skill needed to pre-assign the user-requested data on the possible cells to be visited in order to reduce the access latency. We first design an encoding method for the cells and then derive the properties of the encoding scheme. These properties are then used in our algorithm to deliver the data. Finally, experiments are conducted to demonstrate the feasibility and efficiency of the proposed method.

The rapid advances and popularity of the Internet encourages the wide dissemination of electronic commerce. Various applications of electronic commerce, e.g., querying supermarket catalogs, purchasing products, booking a hotel room of a trip, etc., are rapidly increasing. Moreover, the emergence of mobile computing makes it possible for users to access information anywhere and at anytime. With the merging of these two technologies, millions of users in the near future could carry a mobile device requesting services through electronic commerce applications. While serving such a mobile user, the server should consider how to minimize the response time of the request. However, conventional strategies for query processing are no longer adequate in the mobile environment. This is mainly because the user may not be at the same site as where he/she issued the request when the result of the request is ready to be delivered to the user. The issue becomes more complicated when the user’s request involves data residing in multiple data sources. This paper proposes some strategies for query processing in a mobile commerce environment. All the strategies are presented, along with a cost analysis as the theoretical basis for the support of our design. Through the analysis of each strategy, we find the weakness of the strategy and improve it by a new design. Finally, the performances of all strategies are studied and compared to find the performance difference of the strategies.

Although many query tree optimization strategies have been proposed in the literature, there still is a lack of a formal and complete representation of all possible permutations of query operations (i.e., execution plans) in a uniform manner. A graph-theoretic approach presented in the paper provides a sound mathematical basis for representing a query and searching for an execution plan. In this graph model, a node represents an operation and a directed edge between two nodes indicates the older of executing these two operations in an execution plan. Each node is associated with a weight and so is an edge. The weight is an expression containing optimization required parameters, such as relation size, tuple size, join selectivity factors. All possible execution plans are representable in this graph and each spanning tree of the graph becomes an execution plan. It is a general model which can be used in the optimizer of a DBMS for internal query representation. On the basis of this model, we devise an algorithm that finds a near optimal execution plan using only polynomial time. The algorithm is compared with a few other popular optimization methods. Experiments show that the proposed algorithm is superior to the others under most circumstances.

Due to the autonomy of individual databases, a multidatabase system (MDBS) has no control over the task execution within each database system. This complicates the issue of query optimization in a MDBS. Past researchers tackled this problem mainly by regenerating the cost model of each participating database systems. However a completely autonomous participating database system does nor own the information (data) as well as the mechanism (software) for converting data of one database to another to resolve the data type conflict problems that can occur in any MDBS environment. In addition, unpredictable factors that can drastically deviate the accuracy of a regenerated cost model (in the past research) come into play at unknown time. This confines the processing of an intersite operation (such as a join over two relations of different databases) to the MDBS only. The participating database systems will not be able to share the workload of the MDBS under this circumstance. Hence, minimizing the consumption of system resources of the MDBS is an urgent problem. The authors propose three scheduling algorithms that are used in the MDBS to reduce the processing cost of a multidatabase query. A major difference between the strategies and the past methods is that ours do not require the knowledge of the cost models of the participating databases.

A major issue with location management in mobile wireless networks is the high cost associated with location updates and searches. A search occurs when a caller needs to connect to a mobile user whose location is unknown to the caller and the network must locate the callee. An update occurs when a mobile user moves into a new registration area and the network is informed of the location change. We propose and analyze a class of new agent-based forwarding strategies with the objective to reduce the location management cost in mobile wireless networks. We develop analytical Markov models to compare the performance of the proposed strategies with existing location management schemes to demonstrate their feasibility and also to reveal conditions under which the proposed schemes are superior to existing ones.

This paper presents a methodology for evaluating the performance of forwarding strategies for location management in a personal communication services (PCS) mobile network. A forwarding strategy in the PCS network can be implemented by two mechanisms: a forwarding operation which follows a chain of databases to locate a mobile user and a resetting operation which updates the databases in the chain so that the current location of a mobile user can be known directly without having to follow a chain of databases. In this paper, we consider the PCS network as a server whose function is to provide services to the mobile user for ‘updating the location of the user as the user moves across a database boundary’ and ‘locating the mobile user’. We use a Markov chain to describe the behavior of the mobile user and analyze the best time when forwarding and resetting should be performed in order to optimize the service rate of the PCS network. We demonstrate the applicability of our approach with hexagonal and mesh coverage models for the PCS network and provide a physical interpretation of the result.

The paper presents a framework for modeling and evaluating the performance of forwarding strategies in a personal communication services (PCS) mobile network. A forwarding strategy in the PCS network can be implemented by two mechanisms: a forwarding operation which follows a chain of databases to locate a mobile user, and a resetting operation which updates the databases in the chain so that the current location of a mobile user can be known directly without having to follow a chain of databases. We consider the PCS network as a server whose function is to provide services to the mobile user for "updating the location of the user as the user moves across a database boundary" and "locating the mobile user". We use a Markov chain to describe the behavior of the mobile user and analyze the best time when forwarding and resetting should be performed in order to optimize the service rate of the PCS network. We demonstrate the applicability of our approach with hexagonal coverage models for the PCS network and provide a physical interpretation of the result.

In a multidatabase system, the participating databases are autonomous. The schemas of these databases may be different in various ways, while the same information is represented. A global query issued against the global database needs to be translated to a proper form before it can be executed in a local database. Since data requested by a query (or a part of a query) is sometimes available in multiple sites, the site (database) that processes the query with the least cost is the desired query processing site. The authors study the effect of differences in schemas on the cost of query processing in a multidatabase environment. They first classify schema conflicts to different types. For each type of conflict, they show how much more or less complex a translated query can become in comparison with the originally user-issued global query. Based on this observation, they propose an analytical method that considers the conflicts between local databases and finds the database(s) that renders the least execution cost in processing a global query. This research introduces a new level of query optimization (termed the schema-level optimization) in multidatabase environments. The results provide a new dimension of enhancement for the capability of a query optimizer in multidatabase systems.

The issue of interoperability among multiple autonomous databases has attracted a lot of attention from researchers in these years. The past research on this issue can be roughly divided into two main categories: the tightly-integrated approach that integrate databases by building an integrated schema and the loosely-integrated approach that achieves interoperability by using a multidatabase language. Most of the past efforts focused on the issues in the first approach. The problem with the first approach is, however, that it lacks a convenient representation of the integrated schema at the system level and a sound mathematical basis for data manipulation in a multidatabase system. In this paper, we propose to use hyperrelations as a powerful and succinct model for the global level representation of heterogeneous database schemas. A hyperrelation has the structure of a relation, but its contents are the schemas of the semantically equivalent local relations in the databases. With this representation, the metadata of the global database, local databases and the data of these databases are all representable by using the structure of a relation. The impact of such a representation is that all the elegant features of relational systems can be easily extended to multidatabase systems. A hyperrelational algebra is designed accordingly. This algebra is performed at the multidatabase systems (MDBS) level such that query transformation and optimization is supported on a sound mathematical basis. The major contributions of this paper include: (1) Local relations of various schemas (even though they retain information of the same semantics) can be systematically mapped to hyperrelations. As the structure of a hyperrelation is similar to that of a relation, data manipulation and management tasks (such as design of the global query language and the view mechanism) are greatly facilitated. (2) The hyperrelational algebra provides a sound basis for query transformation and optimization in a MDBS.

Shared nothing multiprocessor architecture is known to be more scalable to support very large databases. Compared to other join strategies, a hash-based join algorithm is particularly efficient and easily parallelized for this computation model. However, this hardware structure is very sensitive to the skew in tuple distribution. Unless the parallel hash join algorithm includes some dynamic load balancing mechanism, the skew effect can severely deteriorate the system performance. In this paper, we investigate this issue. In particular, three parallel hash join algorithms are presented. We implement a simulator to study the effectiveness of these schemes. The simulation model is validated by comparing the simulation results to those produced by the actual implementation of the algorithms running on a multiprocessor system. Our performance study indicates that a naive approach is not able to provide tangible savings. However, the carefully designed strategies can offer substantial improvement over conventional techniques for a wide range of skew conditions.

This paper presents a methodology for the optimization of parallel join execution. Past research on parallel join methods mostly focused on the design of algorithms for partitioning (e.g. hash) relations and distributing data buckets as evenly as possible to the processors. Once data is distributed to the processors, it assumes that all processors will complete their tasks at about the same time. We stress that this is true if no further information such as page-level join index is available. Otherwise, the join execution can be further optimized and the workload in the processors may still be unbalanced. We study such problems that may incur in a shared-nothing architecture environment and propose algorithms for the problems. Also, a simulation study is performed to understand the characteristics of the proposed method.

A multidatabase system is a system that supports data access to a collection of preexisting autonomous database systems. Concurrency control in such an environment is much more difficult in nature than that in centralized or distributed (homogeneous) database systems. Many factors, especially the autonomies, bring difficulties to it. We classify the multidatabase environment into value independent and value dependent ones, and discuss concurrency control mechanisms in these environments. We show that in the value independent environment, the task of concurrency control is resolvable by utilizing conventional concurrency control schemes. As for value dependent environment, we propose a general protocol which is deadlock free and preserves the local autonomy to solve the problems.>

Looks at how to effectively exploit pipelining for multi-join queries in shared-nothing systems. A multi-join query can be processed using an iterative approach. In each iteration, several relations are selected and are joined in a pipelined fashion. However, algorithms that are based on this approach have traditionally assumed that the relations are uniformly distributed or only slightly skewed. When this assumption is relaxed, i.e. when the data is skewed, some nodes may be assigned a larger amount of data than can fit into their memories. As such, pipelining cannot be effectively exploited, and performance may degenerate drastically. We propose four skew handling techniques to deal with data skew for multi-join queries. The results of a performance study show that a hybrid technique is superior in most cases.

A methodology to resolve balancing and scheduling issues for parallel join execution in a shared-nothing multiprocessor environment are presented. In the past, research on parallel join methods focused on the design of algorithms for partitioning relations and distributing data buckets as evenly as possible to the processors. Once data are uniformly distributed to the processors, it is assumed that all processors will complete their tasks at about the same time. The authors stress that this is true if no further information, such as page-level join index, is available. Otherwise, the join execution can be further optimized and the workload in the processors may still be unbalanced. The authors study these problems in a shared-nothing environment.>

The design and analysis of a special function unit for database operations (SFU-DB) that uses a novel hardware sorting module, the automatic retrieval memory (ARM), are described. The SFU-DB is a functionally independent unit that efficiently performs certain nonnumeric operations. It can function as a coprocessor for a host CPU or as a special processing unit in a highly parallel processing system. The ARM implements in hardware a true distribution-based sort algorithm that requires no comparison operations. Without performing any comparison, the SFU-DB avoids the lower bound constraint on comparison-based sorting algorithms and achieves, for the worst case, a complexity of O(n) for both execution time and main memory size. Using the fundamental sort algorithm with slight modifications. the SFU-DB also uses the ARM as an engine for other primitive database operations such as relational join, elimination of duplicates, set union, set intersection, and set difference, also with complexity of O(n). The SFU-DB/ARM architecture is rather simple and requires only a modest amount of specialized hardware. The specialized hardware has been designed and simulated for fabrication using CMOS gate arrays, and the remainder of the SFU-DB has been simulated in software using Turbo Pascal running on an IBM-PC.>