• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
Advanced Search
Zhang Bin, Jiang Tao, Gao Yunjun, Yue Guangxue. Top-k Query Processing of Reverse Skyline in Metric Space[J]. Journal of Computer Research and Development, 2014, 51(3): 627-636.
Citation: Zhang Bin, Jiang Tao, Gao Yunjun, Yue Guangxue. Top-k Query Processing of Reverse Skyline in Metric Space[J]. Journal of Computer Research and Development, 2014, 51(3): 627-636.

Top-k Query Processing of Reverse Skyline in Metric Space

More Information
  • Published Date: March 14, 2014
  • Unlike the traditional metric skyline query, this paper studies a novel skyline query in metric space, called metric top-k reverse skyline (MkRS), which executes the skyline computation from a reverse perspective. Given a query object q and a monotonic preference function f, MkRS returns k subsets which contain exactly m objects of the input dataset P such that each subset G has q in its metric skyline. When evaluating the query, we need to perform exhaustive search of selecting m objects from n objects of dataset P and metric skylines for each combination. These computations are costly due to the extremely large search space. We first present STS (sort and threshold skyline) algorithm to speed-up the computation, which exploits the sorting machinery so that only a part of subsets needs examining and STS can early stop the computation. Then, we reuse the information produced during index accessing which reduces more than 80% I/O accesses of STS and propose the customized algorithm rSTS based on STS. The experimental results show that our proposed algorithms are effective and efficient.

Catalog

    Article views (914) PDF downloads (554) Cited by()
    Turn off MathJax
    Article Contents

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return