skyline查詢——bitmap算法

位圖（Bitmap）算法最先由Kian-Lee Tan在2002年提出，相比于之前該算法的一個創新之處在于只需要把數據點的為所有維度值轉化為一個位串，把所有的數據點轉化位向量合起來即形成位圖。然后進行與運算就判斷是否為SP點。
為了更加形象的展示這個算法的流程，筆者簡單的演示這個算法流程：
如下表所示的10個數據點

數據點坐標位向量
p1 （2，5）（11111110,111110000）
p2 （3，6）（11111100,111100000）
p3 （5，8）（11110000,111000000）
p4 （4，4）（11111000,111111000）
p5 （2，10）（11111110,100000000）
p6 （9，2）（10000000,111111110）
p7 （1，9）（11111111,110000000）
p8 （7，3）（11100000,111111100）
p9 （8，1）（11000000,111111111）
p10 （5，5）（11110000,111110000）
其轉換規則如下：
待測數據集是由d維數據點組成的數據集，任意一個數據點p（p1,p2…pd），假設在某i維（1≤i≤d）上有ki個不同屬性值，數據集在i維上有ki個不同的值。將他們從大到小排列pi1> pi2>…> piki，沒個數據點中第i維的值轉化ki個位串，將其投影在[0…1]中，其轉化規則是：數據點p在第i維的值為pi，用value（pi）代表pi在上面排第value（pi）位，則根據算法中的規則，從最高位到value（pi）位賦值1，從value（pi）-1位開始的賦值0形成一個位串，將d個位串合起來就形成一個位向量，將所有數據點轉換成位向量即可變成一張位圖。
把上表的數據的兩個維度轉化成位圖即如下

   d1                   d2

9 8 7 5 4 3 2 1 10 9 8 6 5 4 3 2 1
1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0
1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0
1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0
1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0
1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0
1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0
1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1
1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0

接下來就可以來尋找每個點的列位串并進行算法流程演示。
如p1點的坐標值（2,5），把A定義為p1點第一維度坐標值的列位串，把B定義為p1點第二維度坐標值的列位串，首先確定p1點在一維上的值為2，在bitmap中找到第一維度上的“2”，然后按列取串即可得A。同理在第二維度“5”中按列取串即可得到B。如圖所示取第一個數據點的列串。
第一個數據點的列位串

可以采用MATLAB編寫了這個算法，這個算法中有比較多的按列取串等，在矩陣中可以比較容易的實現。而且MATLAB中有較多的函數可以直接進行排序等。

close all;
clear;
clc;
tic
m=500;
n=2;
flag=0;
a=1;
flag_bitmap=0;
%point=[2,5;3,6;5,8;4,4;2,10;9,2;1,9;7,3;8,1;5,5];
point=100*rand(m,n);%生成30行2列的位于（0，1）的數據點在乘100
point_1=point(:,1);
point_2=point(:,2);
point_1_sort=unique(point_1);
point_2_sort=unique(point_2);
point_1_sort=sort(point_1_sort,'descend');
point_2_sort=sort(point_2_sort,'descend');
len_point1=length(point_1_sort);
len_point2=length(point_2_sort);
for i=1:m
        for j=1:len_point1
            if((point_1(i)~=point_1_sort(j)) && (flag==0))
                bitmap_1(i,j)=1;
            else
                    if(point_1(i)==point_1_sort(j))
                        bitmap_1(i,j)=1;
                        flag=1;
                    else
                        if((point_1(i)~=point_1_sort(j)) && (flag==1))
                                bitmap_1(i,j)=0;
                        end
                    end
            end
        end
        flag=0;
end
flag=0;
for i=1:m
        for j=1:len_point2
            if((point_2(i)~=point_2_sort(j)) && (flag==0))
                bitmap_2(i,j)=1;
            else
                    if(point_2(i)==point_2_sort(j))
                        bitmap_2(i,j)=1;
                        flag=1;
                    else
                        if((point_2(i)~=point_2_sort(j)) && (flag==1))
                                bitmap_2(i,j)=0;
                        end
                    end
            end
        end
        flag=0;
end
for i=1:m
    for j=1:len_point1
        if(point_1(i)==point_1_sort(j))
            temp_1=j;
        end
    end
    for j=1:len_point2
        if(point_2(i)==point_2_sort(j))
            temp_2=j;
        end
    end
    for k=1:m
        temp_A=bitmap_1(k,temp_1);
        temp_B=bitmap_2(k,temp_2);
        temp_C=temp_A & temp_B;
        if(temp_C==1)
            flag_bitmap=flag_bitmap+1;
        end
    end
    if(flag_bitmap==1)
            final(a,1)=point(i,1);
            final(a,2)=point(i,2);
            a=a+1;
    end
    flag_bitmap=0;
end
final
plot(point(:,1),point(:,2),'*');
hold on
plot(final(:,1),final(:,2),'ro');
legend('all point','skyline point');
toc

下面是仿真結果：
這里寫圖片描述

[1] Borzsony S, Kossmann D, Stocker K. The Skyline operator[C]// International Conference on Data Engineering, 2001. Proceedings. IEEE Xplore, 2001:421-430.
[2] Kossmann D, Ramsak F, Rost S. Shooting stars in the sky: an online algorithm for skyline queries[C]// VLDB 2002, Proceedings of, International Conference on Very Large Data Bases, August 20-23, 2002, Hong Kong, China. DBLP, 2002:275-286.
[3] 朱琳, 關佶紅, 周水庚. Skyline計算研究綜述[J]. 計算機工程與應用, 2008, 44(6):160-165.
[4] 魏小娟, 楊婧, 李翠平,等. Skyline查詢處理[J]. 軟件學報, 2008, 19(6):1386-1400.

本文鏈接：https://blog.csdn.net/huangboy123/article/details/78757046

智能推薦

BitMap

轉載于http://blog.51cto.com/zengzhaozheng/1404108 https://blog.csdn.net/hguisu/article/details/7880288 https://blog.csdn.net/v_july_v/article/details/6685962 一、概述本文將講述Bit-Map算法的相關原理,Bit-Map算法的一些利用場景，例如B...

【性能優化】BitMap的使用:(1)創建BitMap (2)插入key到BitMap (3)刪除key到BitMap (4)查詢key是否存在于BitMap中

位圖操作宏定義先列出來正文： BitMap就是位圖, BitMap是個好數據結構, 尤其對大數據行業，搞清楚其原理后，會發現位圖很easy. 先給出兩個假設 (1)--->假設要處理的都是正整數，(負整數也可以搞定，做下特殊處理就可以，此文章忽略) (2)--->假設申請位圖內存類型為unsigned int 1.BitMap的bit總數有什么決定 bit總數由最大數N確定，而和數隊...

BitMap算法及實現點贊功能

BitMap簡介 bitmap聽起來是位圖的意思，其實就一種基于位的映射，bitmap是一個十分有用的結構。所謂的Bit-map就是用一個bit位來標記某個元素對應的Value，而Key即是該元素。由于采用了Bit為單位來存儲數據，因此可以大大節省存儲空間。為什么要使用bitmap？舉個例子，有一個無序有界int數組{1,2,5,7},初步估計占用內存44=16字節，這倒是沒什么奇怪的；但是...

理解BitMap算法的原理及應用

BitMap簡介：什么是 BitMap 算法所謂 BitMap 就是用一個 bit 位來標記某個元素對應的 value，而 key 即是這個元素。由于采用bit為單位來存儲數據，因此在可以大大的節省存儲空間。算法思想 32位機器上，一個整形，比如 int a; 在內存中占32bit，可以用對應的32個bit位來表示十進制的0-31個數，bitmap算法利用這種思想處理大量數據的排序與查詢。 ...

bitmap 算法的實現與作用

問題引入有一個無序有界int數組{1,2,5,7},初步估計占用內存44=16字節，因為只有4個數，很容易，可以很快找到需要的數。但是假如有10億個這樣的數呢，10億個不重復并且沒有排過序的無符號的int整數，給出一個整數，找出給定的某個數，你該如何操作？需求分析：Int類型在Java中的存儲占用4個Byte,32Bit。10億4/(102410241024)=3.72G左右。如果這樣的一個大...

skyline查詢——bitmap算法

智能推薦

猜你喜歡