高级检索

    一种处理Skyline查询的有效方法

    An Efficient Method for Processing Skyline Queries

    • 摘要: skyline查询是近年来数据库领域的一个研究重点和热点.当系统中存在多个不同维空间上的skyline查询时,现有的工作均直接从底层关系表中获取这些skyline查询的结果集.显然,当底层关系表的基数较大且skyline查询的个数较多时,现有方法的处理效率极其低下.基于此,提出一种使用预存储的n个skyline集合PR\-1,…,PR\-n来回答用户提交的m个不同维空间上的skyline查询SQ\-1,…,SQ\-m的有效方法EAPSQ(efficient algorithm for processing skyline queries).算法充分考虑预存储的skyline集合的编码机制,采用经济学中边际贡献(contribution margin)的概念,使得m个用户提交的skyline查询在n个预存储的skyline集合间的分配达到最佳状态,从而显著提高了处理用户m个skyline查询的效率.实验评估表明,EAPSQ算法具有有效性和实用性.

       

      Abstract: Skyline query processing has recently received a lot of attention in database community. This is mainly due to the importance of skyline results in many applications, such as multi-criteria decision making, data mining, and user-preference queries. Given a set of k-dimensional objects, the skyline query finds the objects that are not dominated by others. When users issue multiple different dimensional-space skyline quereis simultaneously, all the existing works obtain the results of these skyline queries from the original relational table from scratch. Clearly, the existing approaches are extremely inefficient as the cardinality of the original relational table and the number of skyline queries increase. Motivated by the above fact, an efficient method, called EAPSQ (efficient algorithm for processing skyline queries), is proposed to return m issued different dimensional-space skyline quereis SQ\-1,…,SQ\-m using n prestoring skyline sets PR\-1,…,PR\-n. The PAPSQ algorithm adequately considers the characteristics of the storage mechanism of prestoring skyline sets, and adopts the concept of contribution margin in economics. Thus it can efficiently achieve the optimal state for distribution of m skyline queries between n prestoring skyline sets, which can markedly improve the performance for processing skyline queries. Moreover, detailed theoretical analyses and extensive experiments demonstrate that our algorithm is both efficient and effective.

       

    /

    返回文章
    返回