基于LSH的轨迹相似度搜索开题报告

 2020-02-10 11:02
1.目的及意义(含国内外的研究现状分析)

1 目的及意义

在数据压缩,数据挖掘和数据库等领域中,一个值得人们研究的问题是相似性搜索,即在 d 维欧氏空间中,给定一个查询点q,找到距离点q最近的点p,这一问题在低维空间中是容易被解决的。比如使用各种常用的搜索算法。但是当数据维度变大达到几百或更高时,会出现“维数灾难”的象。搜索时间和空间占用都可能以指数式上升。不幸的是,在数据挖掘等领域,高维数据是经常使用的,因此在高维空间中,进行相似度搜索的研是十分重要的。轨迹相似度目前是一个十分重要的问题,通过对人们出行轨迹,车辆运行轨迹等轨迹的分析检测,从而可以获得相似轨迹,进而帮助应用开发人员开发出相应功能来帮助人们方便生活。很显然,每一条轨迹很有可能是一个高维的数据,因此可以通过使用相似度搜索算法进行查找相似轨迹,从而获得需要的结果。在过去几十年的研究中,人们产生了许多相似性搜索的算法,比如提出了许多基于树的KNN搜索索引方法,如R-tree、K-Dtree、SR-tree、navigating-nets和cover-tree等,这些方法返回的结果是准确的,但是对于高维数据,这些方法的时间效率不高。研究已经表明,当维度超过10左右时,现有的基于空间划分的索引数据结构比蛮力线性扫描的索引数据结构要慢。因此目前的方法仍然不能令人满意。事实上,对于一个足够大的维度d,无论在理论分析上,或是实际研究中,人们几乎不能提出一个比暴力线性搜索算法有效的多的算法,最多只能产生些许作用。因此,研究人员提出近似搜索的概念来突破运行时间的瓶颈。

您需要先支付 5元 才能查看全部内容!立即支付

该课题毕业论文、开题报告、外文翻译、程序设计、图纸设计等资料可联系客服协助查找,微信号:bysjorg 、QQ号:3236353895;