CAJ | 학술논문

Skyline计算是要发现数据集中不被其他点支配的所有点的集合.近来,它在实时在线服务方面的良好应用前景,使其成为数据库研究领域的一个热点.实际应用中,用户通常期望快速、渐进地返回Skyline计算结果,因此文中主要讨论了高维空间子空间Skyline渐进查询问题.据我们所知,现有的Skyline计算方法都不能直接或者通过简单修改来高效解决该种查询问题.BNL(Blocked Nested Loop)算法是一个可用来进行子空间Skyline计算的算法,但是,该方法低效且非渐进.基于此,文中提出了在线高效子空间Skyline算法--CSky(Count the Skyline).该算法充分利用了一个新颖数据结构--InvertS的特征,即通过对目标数据集进行排序,存放最可能为Skyline点的数据于算法优先扫描的位置,这使得CSky算法能高效计算出任意子空间上的Skyline;同时,CSky每次计算子空间Skyline查询时,至多访问一遍数据库;再有,算法扫描一个点时,只需和当前已发现的Skyline点进行比较即能判断该点是否为Skyline点,保证了算法的渐进性.这样,相比BNL,CSky大大减少了计算开销,具有其他基于索引的Skyline算法计算Skyline时的高效,且这种高效适用于所有子空间.理论分析和实验表明,在解决高维空间子空间Skyline查询问题方面,CSky性能大大优于BNL.
Skyline계산시요발현수거집중불피기타점지배적소유점적집합.근래,타재실시재선복무방면적량호응용전경,사기성위수거고연구영역적일개열점.실제응용중,용호통상기망쾌속、점진지반회Skyline계산결과,인차문중주요토론료고유공간자공간Skyline점진사순문제.거아문소지,현유적Skyline계산방법도불능직접혹자통과간단수개래고효해결해충사순문제.BNL(Blocked Nested Loop)산법시일개가용래진행자공간Skyline계산적산법,단시,해방법저효차비점진.기우차,문중제출료재선고효자공간Skyline산법--CSky(Count the Skyline).해산법충분이용료일개신영수거결구--InvertS적특정,즉통과대목표수거집진행배서,존방최가능위Skyline점적수거우산법우선소묘적위치,저사득CSky산법능고효계산출임의자공간상적Skyline;동시,CSky매차계산자공간Skyline사순시,지다방문일편수거고;재유,산법소묘일개점시,지수화당전이발현적Skyline점진행비교즉능판단해점시부위Skyline점,보증료산법적점진성.저양,상비BNL,CSky대대감소료계산개소,구유기타기우색인적Skyline산법계산Skyline시적고효,차저충고효괄용우소유자공간.이론분석화실험표명,재해결고유공간자공간Skyline사순문제방면,CSky성능대대우우BNL.