+Advanced Search

PSP:An Efficient Skyline Computation Method for Partially Ordered Domains
Author:
Affiliation:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
    Abstract:

    In order to solve the skyline query problem in partial order domain, this paper proposes an efficient query processing method for the skyline query in the partial order domain to meet people's increasing demand for query efficiency. Firstly, in order to improve the query efficiency of skyline on partially ordered domains, this paper introduces the inverted index into the skyline query and proposes an index structure based on the inverted index. Secondly, the basic algorithm PSP_B (Basic Partially-ordered Skyline Processing based on inverted index, PSP_B) is proposed. The PSP_B consists of two phases: in the first step, each partially ordered domain is converted into two fully ordered domains through mapping function, and then each fully ordered dimension is managed through the inverted index; in the second step, the scan end point is found through scanning the inverted index and the result set is obtained. Thirdly, based on the PSP_B, this paper further proposes an optimization algorithm PSP_I (Improved Partially-ordered Skyline Processing based on inverted index, PSP_I). The PSP_I can further improve the computational efficiency by grouping the data in advance and then indexing them. Finally, a large number of experiments prove the correctness and efficiency of the proposed algorithm.

    Reference
    Related
    Cited by
Article Metrics
  • PDF:
  • HTML:
  • Abstract:
  • Cited by:
Get Citation
History
  • Received:
  • Revised:
  • Adopted:
  • Online: August 28,2020
  • Published: