Patent Document ID: 9977806
Application ID: 14529915

Base Claim:
1. A skyline query apparatus for performing a skyline query, the apparatus comprising a processor configured to: determine a type of the skyline query, the type including a normal skyline query, a dynamic skyline query, or a reverse skyline query; generate a quad tree from data, the quad tree including plural tuples in plural leaf nodes; determine whether a first tuple p dominates other tuples of the plural tuples, the plural tuples including the first tuple p, based on the determined type of the skyline query, wherein, in response to the type of the skyline query being determined to be the normal skyline query, the processor is further configured to determine that the first tuple p dominates a second tuple r of the other tuples when p(k)≤r(k) holds for every dimension k and p(j)<r(j) holds for at least one dimension j, and wherein the tuple p and the tuple r, respectively included in the data and having a d-dimensional value, are represented by <p(1), p(2), . . . , p(d)>, and <r(1), r(2), . . . , r(d)>, respectively; determine which leaf node, from among the plural leaf nodes, includes the tuple p that is determined to dominate the other tuples, and mark a corresponding leaf node, which cannot comprise a local skyline, as being dominated, based on a result of the determining which leaf node includes the tuple p that is determined to dominate the tuple r; identify a local skyline of each leaf node, which is not marked as being dominated, from among the plural leaf nodes in the sky quad tree, and identify a global skyline by using the local skyline by excluding tuples, from among the plural tuples, which are dominated by the other tuples, wherein the global skyline corresponds to a set of all tuples which are not dominated by any other tuples; perform the skyline query, according to the determined type of the skyline query, based on the identified local skyline and global skyline, in parallel using a MapReduce framework.

---

Claim 13:
13. The skyline query apparatus for performing a skyline query of claim 1 , wherein the processor is further configured to compute: a virtual max point, which is virtual data constructed by using maximum values extracted in the data contained in the local skyline when compared with other data by attributes, and a skyfilter, which is a set of data where at least one attribute is a minimum value when compared with other data among the data contained in the local skyline.