Efficient k-dominant skyline query over incomplete data using MapReduce

Skyline queries are extensively incorporated in various real-life applications by filtering uninteresting data objects.Sometimes,a skyline query may return so many results because it cannot control the retrieval conditions especially for highdimensional datasets.As an extension of skyline query,the kdominant skyline query reduces the control of the dimension by controlling the value of the parameter k to achieve the purpose of reducing the retrieval objects.In addition,with the continuous promotion of Bigdata applications,the data we acquired may not have the entire content that people wanted for some practically reasons of delivery failure,no power of battery,accidental loss,so that the data might be incomplete with missing values in some attributes.Obviously,the k-dominant skyline query algorithms of incomplete data depend on the user definition in some degree and the results cannot be shared.Meanwhile,the existing algorithms are unsuitable for directly used to the incomplete big data.Based on the above situations,this paper mainly studies k-dominant skyline query problem over incomplete dataset and combines this problem with the distributed structure like MapReduce environment.First,we propose an index structure over incomplete data,named incomplete data index based on dominate hierarchical tree(ID-DHT).Applying the bucket strategy,the incomplete data is divided into different buckets according to the dimensions of missing attributes.Second,we also put forward query algorithm for incomplete data in MapReduce environment,named MapReduce incomplete data based on dominant hierarchical tree algorithm(MR-ID-DHTA).The data in the bucket is allocated to the subspace according to the dominant condition by Map function.Reduce function controls the data according to the key value and returns the k-dominant skyline query result.The effective experiments demonstrate the validity and usability of our index structure and the algorithm.

Dominant Skyline Query Processing over Multiple Time Series

Multiple time series （MTS）, which describes an object in multi-dimensions, is based on single time series and has been proved to be useful. In this paper, a new analytical method called α/β-Dominant-Skyline on MTS and a formal definition of the α/β-dominant skyline MTS are given. Also, three algorithms, called NL, BC and MFB, are proposed to address the α/β-dominant skyline queries over MTS. Finally experimental results on both synthetic and real data verify the correctness and effectiveness of the proposed method and algorithms.

k-dominant Skyline query algorithm for dynamic datasets

At present,most k-dominant Skyline query algorithms are oriented to static datasets,this paper proposes a k-dominant Skyline query algorithm for dynamic datasets.The algorithm is recursive circularly.First,we compute the dominant ability of each object and sort objects in descending order by dominant ability.Then,we maintain an inverted index of the dominant index by k-dominant Skyline point calculation algorithm.When the data changes,it is judged whether the update point will afect the k dominant Skyline point set.So the k-dominant Skyline point of the new data set is obtained by inserting and deleting algorithm.The proposed algorithm resolves maintenance isue of a frequently updated database by dynamically updating the data sets.The experimental results show that the query algorithm can efectively improve query eficiency.

An Energy-Efficient Query Based on Variable Region for Large-Scale Smart Grid

The state-of-the-art query techniques in power grid monitoring systems focus on querying history data, which typically introduces an unwanted lag when the systems try to discover emergency situations. The monitoring data of large-scale smart grids are massive, dynamic and highly dimensional, so global query, the method widely adopted in continuous queries in Wireless Sensor Networks(WSN), is rendered not suitable for its high energy consumption. The situation is even worse with increasing application complexity. We propose an energy-efficient query technique for large-scale smart grids based on variable regions. This method can query an arbitrary region based on variable physical windows, and optimizes data retrieve paths by a key nodes selection strategy. According to the characteristics of sensing data, we introduce an efficient filter into the each query subtree to keep non-skyline data from being retrieved. Experimental results show that our method can efficiently return the overview situation of any query region. Compared to TAG and ESA, the average query efficiency of our approach is improved by 79% and 46%, respectively; the total energy consumption of regional query is decreased by 82% and 50%, respectively.

Multidimensional Data Querying on Tree-Structured Overlay

Multidimensional data query has been gaining much interest in database research communities in recent years, yet many of the existing studies focus mainly on ten tralized systems. A solution to querying in Peer-to-Peer（P2P） environment was proposed to achieve both low processing cost in terms of the number of peers accessed and search messages and balanced query loads among peers. The system is based on a balanced tree structured P2P network. By partitioning the query space intelligently, the amount of query forwarding is effectively controlled, and the number of peers involved and search messages are also limited. Dynamic load balancing can be achieved during space partitioning and query resolving. Extensive experiments confirm the effectiveness and scalability of our algorithms on P2P networks.

Efficient Optimization of Multiple Subspace Skyline Queries

We present the first efficient sound and complete algorithm （i.e., AOMSSQ） for optimizing multiple subspace skyline queries simultaneously in this paper. We first identify three performance problems of the na/ve approach （i.e., SUBSKY） which can be used in processing arbitrary single-subspace skyline query. Then we propose a cell-dominance computation algorithm （i.e., CDCA） to efficiently overcome the drawbacks of SUBSKY. Specially, a novel pruning technique is used in CDCA to dramatically decrease the query time. Finally, based on the CDCA algorithm and the share mechanism between subspaces, we present and discuss the AOMSSQ algorithm and prove it sound and complete. We also present detailed theoretical analyses and extensive experiments that demonstrate our algorithms are both efficient and effective.

Efficient Processing of Skyline Group Queries over a Data Stream

In this paper, we study the skyline group problem over a data stream. An object can dominate another object if it is not worse than the other object on all attributes and is better than the other object on at least one attribute. If an object cannot be dominated by any other object, it is a skyline object. The skyline group problem involves finding k-item groups that cannot be dominated by any other k-item group. Existing algorithms designed to find skyline groups can only process static data. However, data changes as a stream with time in many applications,and algorithms should be designed to support skyline group queries on dynamic data. In this paper, we propose new algorithms to find skyline groups over a data stream. We use data structures, namely a hash table, dominance graph, and matrix, to store dominance information and update results incrementally. We conduct experiments on synthetic datasets to evaluate the performance of the proposed algorithms. The experimental results show that our algorithms can efficiently find skyline groups over a data stream.

Skyline refinement exploiting fuzzy formal concept analysis

Purpose-The study of the skyline queries has received considerable attention from several database researchers since the end of 2000’s.Skyline queries are an appropriate tool that can help users to make intelligent decisions in the presence of multidimensional data when different,and often contradictory criteria are to be taken into account.Based on the concept of Pareto dominance,the skyline process extracts the most interesting(not dominated in the sense of Pareto)objects from a set of data.Skyline computation methods often lead to a set with a large size which is less informative for the end users and not easy to be exploited.The purpose of this paper is to tackle this problem,known as the large size skyline problem,and propose a solution to deal with it by applying an appropriate refining process.Design/methodology/approach-The problem of the skyline refinement is formalized in the fuzzy formal concept analysis setting.Then,an ideal fuzzy formal concept is computed in the sense of some particular defined criteria.By leveraging the elements of this ideal concept,one can reduce the size of the computed Skyline.Findings-An appropriate and rational solution is discussed for the problem of interest.Then,a tool,named SkyRef,is developed.Rich experiments are done using this tool on both synthetic and real datasets.Research limitations/implications-The authors have conducted experiments on synthetic and some real datasets to show the effectiveness of the proposed approaches.However,thorough experiments on large-scale real datasets are highly desirable to show the behavior of the tool with respect to the performance and time execution criteria.Practical implications-The tool developed SkyRef can have many domains applications that require decision-making,personalized recommendation and where the size of skyline has to be reduced.In particular,SkyRef can be used in several real-world applications such as economic,security,medicine and services.Social implications-This work can be expected in all domains that require decision-making like hotel finder,restaurant recommender,recruitment of candidates,etc.Originality/value-This study mixes two research fields artificial intelligence(i.e.formal concept analysis)and databases(i.e.skyline queries).The key elements of the solution proposed for the skyline refinement problem are borrowed from the fuzzy formal concept analysis which makes it clearer and rational,semantically speaking.On the other hand,this study opens the door for using the formal concept analysis and its extensions in solving other issues related to skyline queries,such as relaxation.