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.

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.

Remarks on the Complexity of Signed k-Domination on Graphs

This paper is motivated by the concept of the signed k-domination problem and dedicated to the complexity of the problem on graphs. For any fixed nonnegative integer k, we show that the signed k-domination problem is NP-complete for doubly chordal graphs. For strongly chordal graphs and distance-hereditary graphs, we show that the signed k-domination problem can be solved in polynomial time. We also show that the problem is linear-time solvable for trees, interval graphs, and chordal comparability graphs.

On the 2-Domination Number of Complete Grid Graphs

A set D of vertices of a graph G = (V, E) is called k-dominating if every vertex v ∈V-D is adjacent to some k vertices of D. The k-domination number of a graph G, γk (G), is the order of a smallest k-dominating set of G. In this paper we calculate the k-domination number (for k = 2) of the product of two paths Pm × Pn for m = 1, 2, 3, 4, 5 and arbitrary n. These results were shown an error in the paper [1].

The Roman k-domatic Number of a Graph

Let k be a positive integer. A Roman k-dominating function on a graph G is a labeling f ： V（G） → {0, 1, 2} such that every vertex with label 0 has at least k neighbors with label 2. A set {f1, f2,..., fd} of distinct Roman k-dominating functions on G with the property that ∑di=1 fi（v） ≤ 2 for each v C V（G）, is called a Roman k-dominating family （of functions） on G. The maximum number of functions in a Roman k-dominating family on G is the Roman k-domatic number of G, denoted by dkR（G）. Note that the Roman 1-domatic number dlR（G） is the usual Roman domatic number dR（G）. In this paper we initiate the study of the Roman k-domatic number in graphs and we present sharp bounds for dkR（G）. In addition, we determine the Roman k-domatic number of some graphs. Some of our results extend those given by Sheikholeslami and Volkmann in 2010 for the Roman domatic number.