Efficient Distributed Skyline Queries for Mobile Applications

In this paper, we consider skyline queries in a mobile and distributed environment, where data objects are distributed in some sites (database servers) which are interconnected through a high-speed wired network, and queries are issued by mobile units (laptop, cell phone, etc.) which access the data objects of database servers by wireless channels. The inherent properties of mobile computing environment such as mobility, limited wireless bandwidth, frequent disconnection, make skyline queries more complicated. We show how to efficiently perform distributed skyline queries in a mobile environment and propose a skyline query processing approach, called efficient distributed skyline based on mobile computing (EDS-MC). In EDS-MC, a distributed skyline query is decomposed into five processing phases and each phase is elaborately designed in order to reduce the network communication, network delay and query response time. We conduct extensive experiments in a simulated mobile database system, and the experimental results demonstrate the superiority of EDS-MC over other skyline query processing techniques on mobile computing.     

一种并行处理Skyline查询的有效方法

Skyline查询是近年来数据库领域的一个研究重点和热点, 这主要是因为Skyline查询在许多领域有着广泛的应用. 现有的工作大都集中于单处理机环境, 然而, 由于Skyline查询是CPU敏感的, 因此,在实际应用中, 现有的方法具有很大的局限性. 基于此, 提出一种有效降低处理Skyline查询时间开销的并行算法PAPSQ (Parallel algorithm for processing skyline queries). 算法有机结合多维数据对象的自身特性和通用多处理机系统的实施优点, 以Skyline查询搜索偏序格为底层结构, 利用多维数据对象的同胚评估值和偏序格加权技术来有效提高并行处理Skyline查询的效率. 实验评估表明, PAPSQ算法具有有效性和实用性.     

Efficient Processing of Metric Skyline Queries

Skyline query is of great importance in many applications, such as multi-criteria decision making and business planning. In particular, a skyline point is a data object in the database whose attribute vector is not dominated by that of any other objects. Previous methods to retrieve skyline points usually assume static data objects in the database (i.e. their attribute vectors are fixed), whereas several recent work focus on skyline queries with dynamic attributes. In this paper, we propose a novel variant of skyline queries, namely metric skyline, whose dynamic attributes are defined in the metric space (i.e. not limited to the Euclidean space). We illustrate an efficient and effective pruning mechanism to answer metric skyline queries through a metric index. Most importantly, we formalize the query performance of the metric skyline query in terms of the pruning power, by a cost model, in light of which we construct an optimized metric index aiming to maximize the pruning power of metric skyline queries. Extensive experiments have demonstrated the efficiency and effectiveness of our proposed pruning techniques as well as the constructed index in answering metric skyline queries.     

Efficient monitoring of skyline queries over distributed data streams

Data management and data mining over distributed data streams have received considerable attention within the database community recently. This paper is the first work to address skyline queries over distributed data streams, where streams derive from multiple horizontally split data sources. Skyline query returns a set of interesting objects which are not dominated by any other objects within the base dataset. Previous work is concentrated on skyline computations over static data or centralized data streams. We present an efficient and an effective algorithm called BOCS to handle this issue under a more challenging environment of distributed streams. BOCS consists of an efficient centralized algorithm GridSky and an associated communication protocol. Based on the strategy of progressive refinement in BOCS, the skyline is incrementally computed by two phases. In the first phase, local skylines on remote sites are maintained by GridSky. At each time, only skyline increments on remote sites are sent to the coordinator. In the second phase, a global skyline is obtained by integrating remote increments with the latest global skyline. A theoretical analysis shows that BOCS is communication-optimal among all algorithms which use a share-nothing strategy. Extensive experiments demonstrate that our proposals are efficient, scalable, and stable.     

Distributed top-k query processing by exploiting skyline summaries

Recently, a trend has been observed towards supporting rank-aware query operators, such as top-k, that enable users to retrieve only a limited set of the most interesting data objects. As data nowadays is commonly stored distributed over multiple servers, a challenging problem is to support rank-aware queries in distributed environments. In this paper, we propose a novel approach, called DiTo, for efficient top-k processing over multiple servers, where each server stores autonomously a fraction of the data. Towards this goal, we exploit the inherent relationship of top-k and skyline objects, and we employ the skyline objects of servers as a data summarization mechanism for efficiently identifying the servers that store top-k results. Relying on a thresholding scheme, DiTo retrieves the top-k result set progressively, while the number of queried servers and transferred data is minimized. Furthermore, we extend DiTo to support data summarizations of bounded size, thus restricting the cost of summary distribution and maintenance. To this end, we study the challenging problem of finding an abstraction of the skyline set of fixed size that influences the performance of DiTo only slightly. Our experimental evaluation shows that DiTo performs efficiently and provides a viable solution when a high degree of distribution is required.     

Efficient distributed skyline computation using dependency-based data partitioning

Skyline queries, together with other advanced query operators, are essential in order to help identify sets of interesting data points buried within huge amount of data readily available these days. A skyline query retrieves sets of non-dominated data points in a multi-dimensional dataset. As computing infrastructures become increasingly pervasive, connected by readily available network services, data storage and management have become inevitably more distributed. Under these distributed environments, designing efficient skyline querying with desirable quick response time and progressive returning of answers faces new challenges. To address this, in this paper, we propose a novel skyline query scheme termed MpSky. MpSky is based on a novel space partitioning scheme, employing the dependency relationships among data points on different servers. By grouping points of each server using dependencies, we are able to qualify a skyline point by only comparing it with data on dependent servers, and parallelize the skyline computation among non-dependent partitions that are from different servers or individual servers. By controlling the query propagation among partitions, we are able to generate skyline results progressively and prune partitions and points efficiently. Analytical and extensive simulation results show the effectiveness of the proposed scheme.     

基于层次组织位置数据库的连续位置相关查询处理

1 引言现有的数据库系统一般假设数据在未被显式修改前是不变的,例如:如果字段salary的值是30.000,那么只有通过事务更新才会改变该字段的值。但对连续变化的对象,如移动对象的位置,应用传统的数据库管理系统来管理会造成两种结果:或者移动对象位置的频繁更新占用大量的系统资源;或者使用移动对象过时的位置信息而导致错误的决策。     

Processing skyline queries in incomplete distributed databases

Due to its great benefits over many database applications, skyline queries have received formidable concern in the last decades. Skyline queries attempt to assist users by identifying the set of data items which represents the best results that meet the conditions of a given query. Most of the existing skyline techniques concentrate on identifying skylines over a single relation. However, in distributed databases, the process of skyline queries required accessing multiple relations which might be located at different sites. Consequently, data items from these multiple relations need to be joined and thus transferring these data items from one site to another is unavoidable. Moreover, the previous techniques also assume that the values of dimensions for every data item are presented (complete) which is not always true as some values may be missing. In this paper, we proposed an approach for processing skyline queries in incomplete distributed databases. The approach derives skylines from multiple relations where dominated data items are removed before joining the relations to reduce the processing time and the network cost. The experimental results illustrate that our proposed approach outperforms the previous approaches in terms of processing time and network cost.     

A Probe-Based Technique to Optimize Join Queries in Distributed Internet Databases

An adaptive probe-based optimization technique is developed and demonstrated in the context of an Internet-based distributed database environment. More and more common are database systems which are distributed across servers communicating via the Internet where a query at a given site might require data from remote sites. Optimizing the response time of such queries is a challenging task due to the unpredictability of server performance and network traffic at the time of data shipment; this may result in the selection of an expensive query plan using a static query optimizer. We constructed an experimental setup consisting of two servers running the same database management system connected via the Internet. Concentrating on join queries, we demonstrate how a static query optimizer might choose an expensive plan by mistake. This is due to the lack of a priori knowledge of the run-time environment, inaccurate statistical assumptions in size estimation, and neglecting the cost of remote method invocation. These shortcomings are addressed collectively by proposing a probing mechanism. An implementation of our run-time optimization technique for join queries was constructed in the Java language and incorporated into an experimental setup. The results demonstrate the superiority of our probe-based optimization over a static optimization. Received 6 February 1999 / Revised 15 February 2000 / Accepted 10 May 2000     

基于高斯模型的不确定数据流Skyline查询方法

由于数据的动态性及不确定性等特征,使得不确定数据流上Skyline查询研究面临挑战.不确定对象一般采用多元概率密度函数(PDF)表示,现有的不确定数据流Skyline查询方法均采用离散型随机变量建模.然而不确定数据流中的对象可能是连续变化的,离散模型对连续性随机变量难以适用.针对连续PDF建模的不确定数据流Skyline查询进行了研究,提出了基于高斯模型的不确定数据流Skyline查询方法(SGMU),该方法包含2个过程:1)动态高斯建模算法(DGM):对滑动窗口采样并建立高斯模型,将原始的数据流转化为不确定对象PDF的参数流;2)提出了基于高斯树的查询算法(GTS)以建立空间索引结构和执行Skyline查询.实验结果表明,SGMU算法不仅能够对连续型不确定对象进行有效建模以辅助Skyline查询,而且能够有效地减少查询对象个数,提高Skyline查询效率.