计算机学报
計算機學報
계산궤학보
CHINESE JOURNAL OF COMPUTERS
2010年
7期
1236-1245
,共10页
印鉴%姚树宇%薛少锷%杨文新%刘玉葆
印鑒%姚樹宇%薛少鍔%楊文新%劉玉葆
인감%요수우%설소악%양문신%류옥보
skyline%决策支持%k-支配skyline%基于索引
skyline%決策支持%k-支配skyline%基于索引
skyline%결책지지%k-지배skyline%기우색인
由于在多标准决策支持等应用上具有重要的意义,skyline查询成为近年来数据库和数据挖掘领域的一个研究热点.然而随着数据集维数的增加,数据点之间形成支配关系的可能性越来越小,导致了skyline点数目过多而无法提供任何有效信息.为了在高维数据集中找到更重要和更有意义的skyline点,人们提出了k-支配skyline的定义.但现有的用于k-支配skyline的算法在时间效率、空间复杂度和渐进输出性上都有待提高.该文提出了一种基于索引的高效k-支配skyline算法,通过为数据集建立两个索引,算法可以高效地进行计算,在时间、空间和渐进性上均优于现有的算法.
由于在多標準決策支持等應用上具有重要的意義,skyline查詢成為近年來數據庫和數據挖掘領域的一箇研究熱點.然而隨著數據集維數的增加,數據點之間形成支配關繫的可能性越來越小,導緻瞭skyline點數目過多而無法提供任何有效信息.為瞭在高維數據集中找到更重要和更有意義的skyline點,人們提齣瞭k-支配skyline的定義.但現有的用于k-支配skyline的算法在時間效率、空間複雜度和漸進輸齣性上都有待提高.該文提齣瞭一種基于索引的高效k-支配skyline算法,通過為數據集建立兩箇索引,算法可以高效地進行計算,在時間、空間和漸進性上均優于現有的算法.
유우재다표준결책지지등응용상구유중요적의의,skyline사순성위근년래수거고화수거알굴영역적일개연구열점.연이수착수거집유수적증가,수거점지간형성지배관계적가능성월래월소,도치료skyline점수목과다이무법제공임하유효신식.위료재고유수거집중조도경중요화경유의의적skyline점,인문제출료k-지배skyline적정의.단현유적용우k-지배skyline적산법재시간효솔、공간복잡도화점진수출성상도유대제고.해문제출료일충기우색인적고효k-지배skyline산법,통과위수거집건립량개색인,산법가이고효지진행계산,재시간、공간화점진성상균우우현유적산법.
