当前位置:首页 >> 其它课程 >> 搜索技术2015-期末作业-2150230509-文成

搜索技术2015-期末作业-2150230509-文成


深圳大学研究生课程论文

题目 VP 树的实现和性能分析

成绩

专业

软件工程

课程名称、代码 技术与应用

20151-161023040018/161023050022 : 通用搜索

年级

2015

/>
姓名

文 成





2150230509

时间

2016



1



任课教师

毛睿

题目:

VP 树的实现和性能分析
(100 分)在课程中已实验的通用相似性索引基本框架上,实现一个 VP 树,并进行性能分析。 (40 分)用清晰明了的方式给出主要的代码。 (10 分)用清晰明了的方式给出主要的注释。 (10 分)程序运行测试过程(构建,搜索)的截屏。 (30 分)设计性能分析试验方案,对 VP 树进行性能分析,如时间复 杂度,可扩展性,不同维度数据的差别,不同搜索半径的差别等。欢 迎使用 UMAD 数据集。 5. (10 分)请在 BlackBoard 系统提交一个压缩文件,文件名格式(不 要括号) : 搜索技术 2015-期末作业-(学号)-(姓名).zip 其中应包括实验报告(必须是 pdf 格式) 、源程序和格式清晰的实验数 据。 1. 2. 3. 4.

一、什么是 VP 树 VP 树的全称是 Vantage Point tree。 VP 树是由 Peter N. Yianilos 在 1993 年的论文 《Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces 》中 提出的一种搜索度量空间(Metric Space)的二叉搜索树。 在维基百科上的说明是: The way a VP tree stores data can be represented by a circle. First, understand that each node of this tree contains an input point and a radius. All the left children of a given node are the points inside the circle and all the right children of a given node are outside of the circle. The tree itself does not need to know any other information about what is being stored. All it needs is the distance function that satisfies the properties of the metric space.[4] Just imagine a circle with a radius. The left children are all located inside the circle and the right children are located outside the circle. 用途:最邻近搜索。任何在度量空间的数据都可以生成 VP 树进行搜索。 度量空间定义: 1. d(x, y) ≥ 0 (非负性) 2. d(x, y) = 0 当且仅当 x = y (不可区分者的同一性) 3. d(x, y) = d(y, x) (对称性) 4. d(x, z) ≤ d(x, y) + d(y, z) (三角不等式)。 二、有利点(Vantage Point)划分
有利点树(Vantange Point Tree, VPT):有利点划分的基本形式

选择有利点 VP1,以 VP1 为圆心、R1 为半径画圆; 数据按位于圆内、外划分之; 再从圆内、外分别选择有利点 VP21、VP22,分别以 R21 和 R22 为圆心画圆

三、主要的代码 ( 因 为 我 对 VP 树 的 了 解 有 限 , 主 要 的 代 码 有 参 考 了 维 基 百 科 的 https://en.wikipedia.org/wiki/Vantage-point_tree 但要成功运行并测试也是有难度 的, 需要理解代码的结构并对代码进行整理, 也需要对 Linux 系统有一定的了解。 后面给出解释和测试结果。 )

主要的数据结构
typedef struct { int int nPoints; dimension; // size : numPoints * dimension

double *points; } DataSet;

typedef struct VPNodeStru { int isLeaf; // _TRUE or _FALSE

struct VPNodeStru **child; // children (array of numBranch pointers) double *medians; // array of (numBranch-1) distances // separating each group such that the // (i)th group is bounded by medians[i] int nPoints; double *points; // // // // else this is the vantage Point(s) (note that vp is also data point) // number of data points // if (isLeaf) this is the data points

int *dataID;

// dataIDs' keep track of where the // points goes in the VP tree

} VPNode;

typedef struct { int numBranch; int dimension; VPNode *root; } VPTree;

VP 树的建立
/* * buildvptree.c * * VP-tree Program - Building VPTree * * By Philip Fu * * Fri Jan 12 22:58:44 EST 2001 * */ #include <stdio.h> #include <stdlib.h> #include <math.h> #include <sys/resource.h> #include <sys/times.h> #include "vptree.h" #include "standard.h" int { DataSet *ds; VPTree int n; float userTime, sysTime; struct rusage startTime, stopTime; ///////////////////////////////////////////////////////// getrusage(RUSAGE_SELF,&startTime); ///////////////////////////////////////////////////////// *vpTree; main(int argc, char **argv)

// (1) Sanity check printf("\n"); if (argc != 5) { printf("Usage : %s <n> <dim> <data file> <vptree file>\n\n",argv[0]); return; } n = atoi(argv[1]); ///////////////////////////////////////////////////////// // (2) Read dataset printf("Reading the dataset ........ "); fflush(stdout); ds = readDataSet(n, atoi(argv[2]), argv[3]); if (ds == NULL) { printf("Oh! No memory left for me...\n\n"); return; } // testing //ds->nPoints = 15; //n = ds->nPoints; printf("done [%d points, %d dimension]\n",n,ds->dimension); ///////////////////////////////////////////////////////// // (3) Build the VP-tree printf("Building the VP-tree ....... "); fflush(stdout); vpTree = buildVPTree(ds,2); printf("done\n"); ///////////////////////////////////////////////////////// // (4) Output the vpTree to file printf("Output VP-Tree to file ..... "); fflush(stdout); n = writeVPTree(argv[4],vpTree); printf("done [%d points written]\n",n); /* for testing { VPTree *vpTree2 = readVPTree(argv[4],&n); printf("done [%d points read]\n",n); n = writeVPTree("data.vptree2",vpTree2); printf("done [%d points written]\n",n); freeVPTree(vpTree2); } */ ///////////////////////////////////////////////////////// getrusage(RUSAGE_SELF,&stopTime); /////////////////////////////////////////////////////////

// (5) Report execution time for building tree userTime = ((float) (stopTime.ru_utime.tv_sec 1e-6; sysTime = ((float) (stopTime.ru_stime.tv_sec 1e-6; printf("\n"); printf("User time : %f seconds\n",userTime); printf("System time : %f seconds\n\n",sysTime); ///////////////////////////////////////////////////////// // (6) Done freeVPTree(vpTree); freeDataSet(ds); printf("\n"); } - startTime.ru_stime.tv_sec)) + ((float) (stopTime.ru_stime.tv_usec - startTime.ru_stime.tv_usec)) * - startTime.ru_utime.tv_sec)) + ((float) (stopTime.ru_utime.tv_usec - startTime.ru_utime.tv_usec)) *

VP 树的搜索:
/*h.c * * VP-tree Program - K-Near-neighbor search * * By Philip Fu * * Mon Jan 15 03:02:36 EST 2001 * */ #include <stdio.h> #include <stdlib.h> #include <math.h> #include <sys/resource.h> #include <sys/times.h> #include "vptree.h" #include "standard.h" void readQuery(char *queryFile, double **queryPt, int dimension) { FILE *fp; int k,i;

double f; char buf[255]; ///////////////////////////////////////// // 1) Open file fp = fopen(queryFile,"r"); if (!fp) errexit2("Err : cannot read file [%s]\n\n",queryFile); ///////////////////////////////////////// // 2) Read queryPt // read k //fgets(buf,255,fp); //sscanf(buf,"%d",&k); // allocate memory for queryPt *queryPt = (double *) malloc(sizeof(double)*dimension); if (!(*queryPt)) errexit("Err : Not enough memory for allocation!\n\n"); // read queryPt for (i=0; i<dimension; i++) { fscanf(fp,"%lf",&f); (*queryPt)[i] = f; } ///////////////////////////////////////// // 3) Done fclose(fp); return; } int main(int argc, char **argv) { VPTree *vpTree; int i,j,k,n; double *queryPt; double *resultPt; int *resultID; FILE *resultFp; int dim,nodeCount; float userTime, sysTime; struct rusage startTime, stopTime; ///////////////////////////////////////////////////////// getrusage(RUSAGE_SELF,&startTime); ///////////////////////////////////////////////////////// // (1) Sanity check printf("\n"); if (argc != 6) {

printf("Usage : %s <dim> <k> <vptree file> <query file> <result file>\n\n",argv[0]); return; } dim = atoi(argv[1]); k = atoi(argv[2]); ///////////////////////////////////////////////////////// // (2) Read VP-tree printf("Reading the VP-Tree ........ "); fflush(stdout); vpTree = readVPTree(argv[3],&n); if (vpTree == NULL) { printf("Oh! No memory left for me...\n\n"); return; } if (dim != vpTree->dimension) { printf("Dimension not match\n"); exit(1); } printf("done [%d points, %d dimension]\n",n,vpTree->dimension); ///////////////////////////////////////////////////////// // (3) Read Query File printf("Reading Query File ......... "); fflush(stdout); readQuery(argv[4],&queryPt,vpTree->dimension); printf("done [k = %d]\n",k); ///////////////////////////////////////////////////////// // (4) Process the Query printf("Processing the Query ....... "); fflush(stdout); // 4a) allocate memory for resultPt and resultID resultPt = (double *) malloc(sizeof(double)*k*vpTree->dimension); resultID = (int *) malloc(sizeof(int)*k);

if (!resultID || !resultPt) errexit("Err : Not enough memory for allocation!\n\n"); // 4b) call knnsearch in vptree.c nodeCount = knnsearch(vpTree,queryPt,k,resultPt,resultID); printf("done\n"); ///////////////////////////////////////////////////////// getrusage(RUSAGE_SELF,&stopTime);

///////////////////////////////////////////////////////// // (5) Report result and Release resource // 5a) Report result /* printf("\n"); printf("Query Pt : "); printPt(stdout,queryPt,vpTree->dimension); printf("\n"); printf("\n"); printf("Result Pt : "); printPt(stdout,resultPt,vpTree->dimension); printf(" (%d)\n",resultID[0]); */ if ((resultFp = fopen(argv[5], "w")) == NULL) { printf("Can't write to file, %s\n", argv[4]); exit(1); } // fprintf(resultFp, "%d", resultID[0]);

for (i=0; i<k; i++) { /* printf(" printPt(stdout, resultPt+i*vpTree->dimension, vpTree->dimension); printf(" (%d)\n",resultID[i]); */ fprintf(resultFp, "%d:", resultID[i]); for(j=0;j<dim;j++) { fprintf(resultFp,"\t%lf",resultPt[i*dim+j]); } fprintf(resultFp,"\n"); } fclose(resultFp); // Report execution time userTime = ((float) (stopTime.ru_utime.tv_sec - startTime.ru_utime.tv_sec)) + ((float) (stopTime.ru_utime.tv_usec - startTime.ru_utime.tv_usec)) * ");

1e-6; sysTime = ((float) (stopTime.ru_stime.tv_sec 1e-6; printf("\n"); printf("number of nodes visited : %d\n",nodeCount); printf("User time : %f seconds\n",userTime); printf("System time : %f seconds\n\n",sysTime); // 5e) Release resource freeVPTree(vpTree); free(resultPt); free(resultID); free(queryPt); printf("\n"); } - startTime.ru_stime.tv_sec)) + ((float) (stopTime.ru_stime.tv_usec - startTime.ru_stime.tv_usec)) *

四、主要的解释 Unify existing methods

其实《 Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces 》 一文中提出的一种搜索度量空间(Metric Space)的二叉搜索树,文中提出的算法 与这里的实现大同小异 下面是 Peter N. Yianilos 在论文中对于建 Vp 树的算法说明:

下面是 Peter N. Yianilos 在论文中对于搜索的算法说明:

实现完 VP 树可以进行最邻近搜索。任何在度量空间的数据都可以生成 VP 树 进行搜索。 五、程序运行测试过程(构建,搜索)
测试是在 Ubuntu 系统下完成的, 将 vpt 文件夹放到某个目录下 (我将其放到 home 目录 下) 。

其中包含两个文件夹。

(截图中 wcventure 是我的用户名,我是自己测试过的) 先 cd 到相应的目录,make。 结果如下:

现在可以使用./buildvptree 命令了 格式和参数如 Usage 展示的那样。

我们先建一个 10 维的。输出结果如下。

这就完成了一个 VP 树的构建 下面是搜索的过程:

使用./knnsearch 搜索,注意参数要一致,建的树是 10 维的此处的参数也应该是 10 维。

这就完成了程序的测试。 六、VP 树的性能分析
Vp 树有很多优点: 搜索复杂度:O(log(N)),当然随着搜索半径的增加,复杂度会增加。 可扩展性也很好,各种语言都有实现的例子。

当然随着搜索半径的增加,耗时会增加。 随着维度的增加,耗时也会增加。
例如你有一本 10 万字的词典,给你一个词,搜索所有只差一个字母的词,全部词遍历 一次的话要访问 10 万个词, 用 VP 树最优化的情况下只需要访问(log(100000)/log(2)约等于 17)个词。 缺点: 由于 VP 树是静态的,无法在其身上实现插入和删除操作。 大量距离查询操作,所以最好能缓存距离查询。

七、实验心得与体会 一开始我根本不明白什么是 VP 树,这几天在网上查阅了不少资料,相关的 资料也相当的少。与这相关的还有一篇论文,名为: 《Data Structures and Algorithms for Nearest Neighbor Search in General Metric Spaces》 我简单地读了一下,但是还是对它的树最终构造结构还是不太了解。最终我 参考了一些资料完成了这次实验,但其测试过程依旧遇到了不少困难。总之,学 习了这门课,虽然对这个领域依旧陌生,但我感觉还是收获很大。


更多相关文档:

搜索技术2015-期末作业-2150230509-文成

搜索技术2015-期末作业-2150230509-文成_其它课程_高中教育_教育专区。深圳大学研究生课程论文 题目 VP 树的实现和性能分析 成绩 专业 软件工程 课程名称、代码 技术...

通用搜索技术试验报告一(文成2150230509)

深 圳 大 学 实 验 报 告 课程名称:通用搜索技术 实验名称:熟悉 UMAD 并...文成 学 号:2150230509 班 级:15 级软件工程 实验日期:2015-10-29 一.实验...

实验报告(实验二)-文成

文成 学号: 2150230509 班级: 软工学硕 实验时间: 2015-10-15 至 2016-01-...因为不熟悉,大作业并没有 boost 库,我是使用自己的方法做的,可能误差 也比较...

Type Inference on Executables-文成-2150230509

搜试试 3 帮助 全部 DOC PPT TXT PDF XLS ...年级 2015 级 姓名 文成 学 号 2150230509 时间 2016...-2150230509 深圳大学研究生期末考试试卷开卷 专业英文...

手写数字识别-文成-2150230509

搜试试 3 帮助 全部 DOC PPT TXT PDF XLS ...年级 2015 级 姓名 文成 学 号 2150230509 时间 2016...4. 手写数字识别技术展望 随着国家信息化进程的加快...
更多相关标签:
电大作业答案搜索系统 | flash期末作业 | 网页设计期末作业 | android期末大作业 | 经济法期末大作业答案 | ps期末作业 | 交大经济法期末大作业 | 3dmax期末作业 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com