目录
【摘要】 1
第一章 skyline查询背景简介 2
1.1 简介（问题1：描述skyline的应用范围） 2
1.2 相关工作 2
第二章 穷举法查询计算 2
2.1 BFS计算语义距离&分块剪枝处理 2
（1）算法描述 2
（2）算法步骤 2
（3）算法实现伪代码 3
（4）算法评价与分析 4
2.2 BNL算法（块嵌套环算法） 4
（1）算法描述 4
（2）算法步骤 5
（3）算法实现伪代码 5
（4）算法复杂度分析评价 5
2.3穷举检索 6
第三章 高效检索算法设计 6
3.1 B-Tree结构存储关键词 6
（1）结构背景简介 6
（2）基本结构介绍 6
（3）结构改进用于语义地点查询 6
（4）基于语义地点B-Tree的相关操作实现 7
3.2 基于B-Tree的初阶检索算法 8
（1）算法描述 8
（2）算法步骤 9
（3）算法伪代码 9
（4）算法复杂度分析评价 10
3.3 核心算法：基于B-Tree的高阶检索算法 10
（1）有助于理解算法的相关定义 10
（2）算法描述 11
（3）算法步骤 12
（4）算法伪代码 12
（5）算法复杂度分析评价 13
3.4 针对单个关键词查找的最终优化 13
3.5 高效检索算法的确定 13
第四章 实验分析算法性能 14
实验环境&配置：普通的PC； 14
算法实现语言：C/C++； 14
编译运行软件：DEV 5.11。 14
4.1 对检索结果的正确性进行验证 14
4.2 yago_small小数据集下算法性能测量 15
4.3 yago数据集下 15
第五章 问题解答 16
5.1 问题1 16
5.2 问题2 17
5.3 问题3 17
第六章 结论&进一步工作 17
6.1 实验总结 17
6.2 进一步工作 18
第三章高效检索算法设计
3.1 B-Tree结构存储关键词
（1）结构背景简介
当需要检索的文件较大，并且存放在磁盘等直接存储设备中时，为了减少检索过程中对磁盘进行读写操作的次数，提高检索效率，基于直接存取设备的读写操作以"页"为单位的特征，1972年R.Bayer和E.M.McCreight提出了一种称之为B-Tree的多路平衡查找树，它适合在磁盘等直接存储设备上组织动态的关键词查找表，并能极大提高检索效率，常被适用于做文件的索引，在文件系统中被广泛使用。
（2）基本结构介绍
定义：B-Tree本质是一种多路平衡查找树，是B树（二叉排序树）一种改进。
结构/特点：
一棵m阶的B-树，或为空树，或为满足下列特性的叉树：
1)树中每个结点至多有棵子树；
2)根结点要么是叶子结点，要么它至少有两棵子树；
3)除根之外的所有非终端结点至少有[m/2]棵子树；
4)所有的非终端结点中包含下列信息数据：
5) ：表示关键词个数， 为关键词数组（按关键词的大小升序排序） ，为指向子树根结点的指针数组；
6)所有的叶子结点都出现在同一层次上，并且不带信息（实际上不存在，指向这些结点的指针为空）。
（3）结构改进用于语义地点查询
B-Tree主要用于关键词查找，而我们的目的在于通过关键词查找语义地点。因此，我创建了如下伪代码所示的关键词类使得B-Tree在创建时就将与每个关键词有关的语义地点编号保留在树中了，这样一来对B-Tree进行查找时，返回的关键词类既有关键词的信息，又有与该关键词有关的所有地点编号的链表。
如下伪代码是查询操作返回的结构体定义（下文常用表示）
（4）基于语义地点B-Tree的相关操作实现
一颗完整的B-Tree应该具有初始化、查找、插入、删除、打印输出、销毁六个操作。其中，查找和插入是最主要操作。由于除查找和插入操作的另外的四个操作采用了较为常见实现方法，对于语义地点查询问题来说其实并没有作用，因此，这里只介绍在语义地点查询背景下，基于如上类实现B-Tree查找和插入操作的具体步骤。
B-Tree查找接口的实现步骤
Step0：初始化查询变量为0，从树的根节点出发，即指针指向；
Step1：在中找到需要检索的关键词的一个上确界，返回这个上确界在中的序号。
Step2：判断中的上确界是否与相等
Stituation1：
将foundFlag置为1
Stituation2：
令,重复Step1直至出现Stituation1或者。
Step3：根据返回结果
Stituation1：
返回查询结果，是含有的树结点，是关键词，是标志变量，置为1，表面中确实含有关键词。查询结束。
Stituation2：
返回查询结果，是含有的树结点，是关键词，是标志变量，置为0，表面中不含有关键词，是关键词的一个插入位置，用于后面的插入操作。查询结束。
B-Tree插入步骤
Step0：遍历每个结点的所有关键词，假设当前读取读取到了结点的关键词,创建关键词类，进行如下操作：
Step1：利用上文描述的在树中查找要插入的关键词，得到返回结果r；
Step2：判断的标志变量是否为1
Stituation1：为1，本文转载自http://www.biyezuopin.vip/onews.asp?id=14169表明树中已经有了这个关键词，那么将插入到的列表中，也就是上文提到的关键词存储语义地点的列表中，回到Step0读取结点的下一个关键词或者下一个结点的第一个关键词。
Stituation2：为0，表明树中并没有该关键词，需要把关键词类插入到这个指针所指的树结点中，进入Step3；
Step3：判断树是否为空；
Situation1：如果树为空，直接插入新结点，并将其作为树的根结点；
Situation2：如果树不为空，进入Step4；
Step4：令指向结点，并将关键词类插入，判断会有如下两种情况：
Situation1：(树的阶数)，则插入成功，回到Step0读取结点no的下一个关键词或者下一个结点的第一个关键词。
Situation2：，由于每个树所含有的关键词和孩子结点都是不能超过B树的阶数的，所以此处要对进行结点分裂的操作，进入Step5；
Step5：将结点的关键前一半依然保留在中，后一半保留在分裂出的结点中（前一半和后一半均不包含中间那个关键词），以中间的关键词，为孩子结点创建新根结点。
Step6：回到Step0读取结点的下一个关键词或者下一个结点的第一个关键词，直到所有结点的每个关键词都进行了一次查询和插入（插入或者B-Tree插入）的操作即可。
#include <iostream>
#include <cstdio>
#include <malloc.h>
#include <cstdlib>
#include<fstream>
#include<vector>
#include<string>
#include<cstring>
#include<queue>
#include<map>
#include<sstream>
#include<time.h>
#include "BTree.h"
#define MAX_DNUM 5
using namespace std;
static int pnum = 8091179;//8091179,24; //点的数目
static vector<int> *key; //关键词信息存储
static vector<int> *graph; //邻接表存储
static vector<int> site; //地点序号存储
static map<int,int> pmap; //地点坐标检索使用
static int dnum = 0; //查询关键词数目
static int sitenum = 0;
static int **gap; //记录距离
static int maxlayer = 0x3f3f3f3f; //记录支配情况下的最高层
static BTNode *Bt = NULL;
static int *visited;
#pragma region 读取数据
void PreSet()
{
key = new vector<int>[pnum];
graph = new vector<int>[pnum];
visited = new int[pnum];
}
void ReadKey(string filename)
{
FILE *file;
file = fopen(filename.c_str(), "r");
if (!file)
{
cout << "key文件打开失败" << endl;
exit(-1);
}
while (1)
{
char tempstr[10000] = { '\0' };
if (fgets(tempstr, 10000, file) == NULL)
{
break;
}
char seps[] = ": ,\n";
char *token;
char *next_token;
token = strtok(tempstr, seps);
if (token == NULL)
{
continue;
}
//cout << token << ":" << endl;
int index = atoi(token), temp;
token = strtok(NULL, seps);
while (token != NULL)
{
//cout << token << ",";
temp = atoi(token);
key[index].push_back(temp);
token = strtok(NULL, seps);
}
//cout << endl;
}
fclose(file);
}
void ReadGraph(string filename)
{
FILE *file;
file = fopen(filename.c_str(), "r");
if (!file)
{
cout << "graph文件打开失败" << endl;
exit(-1);
}
int u, v;
while (1)
{
char tempstr[10000] = { '\0' };
if (fgets(tempstr, 10000, file) == NULL)
{
break;
}
char seps[] = ": ,\n";
char *token;
char *next_token;
token = strtok(tempstr, seps);
if (token == NULL)
{
continue;
}
u = atoi(token);
token = strtok(NULL, seps);
while (token != NULL)
{
v = atoi(token);
graph[v].push_back(u);
token = strtok(NULL, seps);
}
}
fclose(file);
}
void ReadSite(string filename)
{
FILE *file;
file = fopen(filename.c_str(), "r");
if (!file)
{
cout << "site文件打开失败" << endl;
exit(-1);
}
fscanf(file, "%d#\n", &sitenum);
//cout << sitenum << endl;
int u;
int no = 0;
while (1)
{
char tempstr[10000] = { '\0' };
if (fgets(tempstr, 10000, file) == NULL)
{
break;
}
//cout << tempstr << endl;
char seps[] = ": ,\n";
char *token;
char *next_token;
token = strtok(tempstr, seps);
if (token == NULL)
{
continue;
}
//cout << token << ":" << endl;
u = atoi(token);
pmap.insert(pair<int,int>(u,no++));
site.push_back(u);
}
sitenum = site.size();
fclose(file);
}
void Show()
{
for (int i = 0; i < pnum; i++)
{
cout << i << ": ";
for (int j = 0; j < (int)graph[i].size(); j++)
{
cout << graph[i][j] << ",";
}
cout << endl;
}
}
#pragma endregion
void CreateBTree()
{
Findres r;
cout<<"创建一颗"<<m<<"阶B树"<<endl;
for(int i = 0; i < pnum; i++)
{
int len = key[i].size();
for(int j = 0; j < len; j++)
{
pkey k(key[i][j]);
k.insert_no(i);
//cout<<"第"<<j+1<<"步，"<<"插入元素"<<key[i][j]<<endl;
r = SearchBTree(Bt,k);
if(r.flag == 0)
{
InsertBTree(Bt,r.i,k,r.pt);
}
else
{
r.pt->key[r.i].insert_no(i);
}
}
}
//PrintBTree(Bt);
}
//***************************************************************
void BFS_CalculateMinDistance(int start,int d)
{
// int count = 0;
int u, v;
queue<int> que;
int layer = 0, nodeNum = 1, nextnodeNum = 0;
que.push(start);
visited[start] = 1;
while (!que.empty())
{
u = que.front();
//cout << "u = " << u << endl;
que.pop();
if(pmap.find(u)!=pmap.end())
{
int g = pmap[u];
if(gap[g][d]==-1||gap[g][d]>layer)
{
gap[g][d] = layer;
}
}
for (int j = 0; j < (int)graph[u].size(); j++)
{
v = graph[u][j];
if (!visited[v]) //未访问过
{
que.push(v);
//cout << "v = " << v << endl;
visited[v] = 1;
nextnodeNum++;
}
}
nodeNum--; //每次循环输出一个点，即遍历当前层结点数-1
if (nodeNum == 0)
{
layer++;
nodeNum = nextnodeNum;
nextnodeNum = 0;
}
}
queue<int> empty;
swap(empty, que);
}
//返回值说明：1表示a<b，-1表示b<a，0表示两者没有支配关系
int isGovern(int *a, int *b)
{
int ag = 0, bg = 0;
for (int i = 0; i < dnum; i++)
{
if (a[i] < b[i])
{
ag++;
}
else if(b[i] < a[i])
{
bg++;
}
}
if (ag&&bg)
{
return 0;
}
else if(bg)
{
return 1;
}
else if(ag)
{
return -1;
}
return 0;
}
bool isAssessible(int *temp)
{
for(int i = 0; i < dnum; i++)
{
if(temp[i] == -1)
{
return false;
}
}
return true;
}
static vector<int> BNLresult;
void BNL()
{
BNLresult.clear();
for(int i = 0; i<sitenum; i++)
{
if(isAssessible(gap[i]))
{
BNLresult.push_back(i);
break;
}
}
if(BNLresult.size()==0)
{
return;
}
//cout << sitenum << endl;
for (int i = BNLresult[0] + 1; i < sitenum; i++)
{
bool isSP = true;
//新引入节点与窗口节点之间的对比
if(!isAssessible(gap[i]))
{
continue;
}
for (vector<int>::iterator it = BNLresult.begin(); it != BNLresult.end();)
{
int flag = isGovern(gap[i], gap[*it]);
// cout << flag << endl;
if (flag == -1)
{
// cout << *it << endl;
it = BNLresult.erase(it);
}
else if(flag == 1)
{
isSP = false;
break;
}
else
{
it++;
}
}
if (isSP)
{
BNLresult.push_back(i);
}
}
}
//***************************************************************
void ShowList(noPoint *head)
{
noPoint* p = head;
while(p!=NULL)
{
cout << " " << p->no;
p=p->next;
}
cout << endl;
}
void SearchInBTree(int key, Findres &r)
{
r = SearchBTree(Bt,key);
cout << "Flag = " << r.flag << endl;
cout << "sum of point = " << r.pt->key[r.i].sum << endl;
//cout << "no：" << endl;
//ShowList(r.pt->key[r.i].nolist);
}
void ShowBNLResult()
{
//输出检索结果
for (int i = 0; i < (int)BNLresult.size(); i++)
{
int sp = site[BNLresult[i]];
cout << "第" << i + 1 << "个SP点是" << sp << endl;
cout << "关键词" << endl;
for (int j = 0; j < (int)key[sp].size(); j++)
{
cout << key[sp][j] << " ";
}
cout << endl;
cout << "距离" << endl;
for (int j = 0; j < dnum; j++)
{
cout << gap[BNLresult[i]][j] << " ";
}
cout << endl;
}
}
void GetRunTime(FILE *file, int knum)
{
double starttime, endtime, deltatime;
vector<int> des;
dnum = knum;
int times = 10;
while(times--)
{
cout << "检索目标是(用空格隔开，回车表示开始进行检索)：" << endl;
for(int i = 0; i < knum; i++)
{
int temp1 = rand()%pnum;
int temp2 = rand()%key[temp1].size();
des.push_back(key[temp1][temp2]);
cout << des[i] << ",";
}
cout << endl;
Findres r;
starttime = clock();
cout << "****************正在检索****************" << endl;
for(int i = 0; i < dnum; i++)
{
SearchInBTree(des[i], r);
noPoint *p = r.pt->key[r.i].nolist;
while(p!=NULL)
{
memset(visited, 0, sizeof(int)*pnum);
BFS_CalculateMinDistance(p->no,i);
//cout<<p->no<<endl;
p=p->next;
}
}
//只有一个搜索词，找出其中是p点的即为skyline，若无p点则要反向遍历
if(dnum == 1)
{
SearchInBTree(des[0], r);
noPoint *p = r.pt->key[r.i].nolist;
int no;
pkey res(r.pt->key[r.i].key);
while(p!=NULL)
{
no = p->no;
if(pmap.find(no) != pmap.end())
{
res.insert_no(no);
}
p=p->next;
}
cout << "sum of P in res = " << res.sum << endl;
if(res.sum == 0)
{
p = r.pt->key[r.i].nolist;
while(p!=NULL)
{
BFS_CalculateMinDistance(p->no,0);
//cout<<p->no<<endl;
p=p->next;
}
BNL();
cout << "BNL result's size = " << BNLresult.size() << endl;
//ShowBNLResult();
}
}
if(dnum>1)
{
BNL();
cout << "BNL result's size = " << BNLresult.size() << endl;
//ShowBNLResult();
}
endtime = clock();
deltatime = endtime - starttime;
fprintf(file,"%f\n",deltatime);
cout << "*********检索所花时间：" << deltatime << endl;
BNLresult.clear();
des.clear();
}
fclose(file);
}
int main(){
string timefile = "B:\\算法大作业\\rumtime.txt";
FILE *file;
file = fopen(timefile.c_str(), "a+");
if (!file)
{
cout << "timefile文件打开失败" << endl;
exit(-1);
}
string keyfile = "B:\\算法大作业\\Yago\\node_keywords.txt";
string graphfile = "B:\\算法大作业\\Yago\\edge.txt";
string sitefile = "B:\\算法大作业\\数据\\placeid2coordYagoVB.txt";
/*
string keyfile = "B:\\算法大作业\\Yago_small\\node_keywords.txt";
string graphfile = "B:\\算法大作业\\Yago_small\\edge.txt";
string sitefile = "B:\\算法大作业\\数据\\placeid2coordYagoVB.txt";
*/
/*
string keyfile = "B:\\算法大作业\\question1\\node_kewords.txt";
string graphfile = "B:\\算法大作业\\question1\\edge.txt";
string sitefile = "B:\\算法大作业\\question1\\position.txt";
*/
PreSet();
ReadKey(keyfile);
ReadGraph(graphfile);
ReadSite(sitefile);
gap = new int*[sitenum];
for (int i = 0; i < sitenum; i++)
{
gap[i] = new int[MAX_DNUM];
for (int j = 0; j < MAX_DNUM; j++)
{
gap[i][j] = -1;
}
//cout << gap[i][0] << endl;
}
cout <<"顶点数目是："<< pnum << endl;
cout << "**********************************" << endl;
double s1 = clock();
CreateBTree();
double s2 = clock();
double d1 = s2 - s1;
cout << "*********建立B树所花时间：" << d1 << endl;
GetRunTime(file, 3);
/*
double starttime, endtime, deltatime;
PreSet();
ReadKey(keyfile);
ReadGraph(graphfile);
ReadSite(sitefile);
gap = new int*[sitenum];
for (int i = 0; i < sitenum; i++)
{
gap[i] = new int[MAX_DNUM];
for (int j = 0; j < MAX_DNUM; j++)
{
gap[i][j] = -1;
}
//cout << gap[i][0] << endl;
}
vector<int> des;
cout <<"顶点数目是："<< pnum << endl;
cout << "**********************************" << endl;
starttime = clock();
CreateBTree();
endtime = clock();
deltatime = endtime - starttime;
cout << "*********建立B树所花时间：" << deltatime << endl;
//BFS_CreateBTree();
//Show();
while(1)
{
cout << "是否继续检索：是请输入1，否请输入0" <<endl;
int flag;
cin>>flag;
getchar();
if(!flag)
{
break;
}
cout << "请告诉你的检索目标是(用空格隔开，回车表示开始进行检索)：" << endl;
char tempstr[2048];
cin.getline(tempstr, 2048);
char seps[] = " ,";
char *token;
char *next_token;
token = strtok(tempstr, seps);
while (token != NULL)
{
int temp = atoi(token);
des.push_back(temp);
token = strtok(NULL, seps);
}
dnum = des.size();
//cout<<des[0]<<endl;
Findres r;
starttime = clock();
cout << "****************正在检索****************" << endl;
for(int i = 0; i < dnum; i++)
{
SearchInBTree(des[i], r);
noPoint *p = r.pt->key[r.i].nolist;
while(p!=NULL)
{
//此步可做优化，反向遍历的特点
memset(visited, 0, sizeof(int)*pnum);
BFS_CalculateMinDistance(p->no,i);
//cout<<p->no<<endl;
p=p->next;
}
}
//只有一个搜索词，找出其中是p点的即为skyline，若无p点则要反向遍历
if(dnum == 1)
{
SearchInBTree(des[0], r);
noPoint *p = r.pt->key[r.i].nolist;
int no;
pkey res(r.pt->key[r.i].key);
while(p!=NULL)
{
no = p->no;
if(pmap.find(no) != pmap.end())
{
res.insert_no(no);
}
p=p->next;
}
cout << "sum of P in res = " << res.sum << endl;
if(res.sum == 0)
{
p = r.pt->key[r.i].nolist;
while(p!=NULL)
{
BFS_CalculateMinDistance(p->no,0);
//cout<<p->no<<endl;
p=p->next;
}
BNL();
cout << "BNL result's size = " << BNLresult.size() << endl;
ShowBNLResult();
}
}
if(dnum>1)
{
BNL();
cout << "BNL result's size = " << BNLresult.size() << endl;
ShowBNLResult();
}
endtime = clock();
deltatime = endtime - starttime;
fprintf(file,"%f",deltatime);
cout << "*********检索所花时间：" << deltatime << endl;
BNLresult.clear();
des.clear();
}
fclose(file);
*/
//Test1();
return 0;
}
