Adaptive convex skyline: a threshold-based project partitioned layer-based index for efficient-processing top-k queries in entrepreneurship applications

作者：Son Yunsik; Ihm Sun Young; Nasridinov Aziz; Park Young Ho^*

来源：Journal of Supercomputing, 2016, 72(11): 4262-4275.

DOI：10.1007/s11227-016-1826-4

• Bigdata
• Healthcare
• Top-k queries
• Adaptive convex skyline
• Entrepreneurship

Many entrepreneurship applications use data as the core concept of their business to better understand the needs of their customers. However, as the size of databases used by these entrepreneurship applications grows and as more users access data through various interactive interfaces, obtaining the result for a top-k query may take long time if the query matches millions of the tuples in the database. Traditionally, layer-based indexing methods are representative for processing top-k queries efficiently. These methods form tuples into a list of layers where the ith layer holds the tuples that can be the top-i answer. Layer-based indexing methods enable us to obtain top-k answers by accessing at most k layers. Most of these methods achieve high accuracy of query answer at the expense of enlarged index construction time. However, we can adjust between accuracy and index construction time to achieve an optimal performance. Thus in this paper, we propose a method, called the adaptive convex skyline (AdaptCS) for efficient-processing top-k queries in entrepreneurship applications. AdaptCS first prunes the data with a virtual threshold point and finds skyline points over the pruned data. Here, by adjusting virtual threshold we are able to achieve optimal performance. Then, AdaptCS divides the skyline into m subregions with projection partitioning method and constructs the convex hull m times for each subregion with virtual objects. Lastly, AdaptCS combines the objects obtained by computing the convex hull. The experimental results show that the proposed method outperforms the existing methods.

• 出版日期2016-11