1 目的及意义

在数据压缩,数据挖掘和数据库等领域中,一个值得人们研究的问题是相似性搜索,即在 d 维欧氏空间中，给定一个查询点q，找到距离点q最近的点p，这一问题在低维空间中是容易被解决的。比如使用各种常用的搜索算法。但是当数据维度变大达到几百或更高时，会出现“维数灾难”的象。搜索时间和空间占用都可能以指数式上升。不幸的是，在数据挖掘等领域，高维数据是经常使用的，因此在高维空间中，进行相似度搜索的研是十分重要的。轨迹相似度目前是一个十分重要的问题，通过对人们出行轨迹，车辆运行轨迹等轨迹的分析检测，从而可以获得相似轨迹，进而帮助应用开发人员开发出相应功能来帮助人们方便生活。很显然，每一条轨迹很有可能是一个高维的数据，因此可以通过使用相似度搜索算法进行查找相似轨迹，从而获得需要的结果。在过去几十年的研究中，人们产生了许多相似性搜索的算法，比如提出了许多基于树的KNN搜索索引方法，如R-tree、K-Dtree、SR-tree、navigating-nets和cover-tree等，这些方法返回的结果是准确的，但是对于高维数据，这些方法的时间效率不高。研究已经表明，当维度超过10左右时，现有的基于空间划分的索引数据结构比蛮力线性扫描的索引数据结构要慢。因此目前的方法仍然不能令人满意。事实上，对于一个足够大的维度d，无论在理论分析上，或是实际研究中，人们几乎不能提出一个比暴力线性搜索算法有效的多的算法，最多只能产生些许作用。因此，研究人员提出近似搜索的概念来突破运行时间的瓶颈。这是由于在许多情况下，近似邻近搜索的结果几乎和精确搜索的结果差不多。实际上，如果距离测量的方法能够精确测出对象的相应性质，那么近似邻近搜索的小误差应该不是问题。正如使用近似邻近搜索在轨迹相似度中进行搜索一样，由于目前位置测定的工具存在误差，在存在误差的数据下使用精确近似搜索可能并没有特别大的意义，使用近似邻近搜索却能减少查询时间和空间占用率。
目前有许多的近似邻近搜索方法被提出，如VA-file、A-tree和AV-tree。这些技术使用向量近似或边界矩形近似来修剪搜索空间。在求解近似最近邻(ANN)问题上取得了很大的进展。目标是找到距离查询点的距离不超过1 真实最近邻距离的点。由Indyk和Motwani引入的局部性敏感哈希(Localitysensitive hashing,LSH)是ANN搜索中最著名的索引方法。其通过构建多个哈希表，每个表中存在多个buckets，将原始数据哈希到不同的buckets中，然后对查询点进行相同哈希，对buckets中碰撞的点进行查找，得到近似邻近解。该方法能够有效的减少查询时间和空间的占用，因此广泛被使用。Bawa等人提出了LSH森林索引方法，它用前缀树表示每个哈
希表，这样每个表的哈希函数的数量就可以适应不同的近似距离。Panigrahy提出了一种基于熵的LSH方案，该方案试图通过使用多个受扰动的查询来减少哈希表的数量

2. 研究的基本内容与方案

2 研究的基本内容、拟采用的技术方案及措施
2.1 研究内容
对于由GPS或各类传感器比如手机得到的位置信息，其在不同地点的位置可以连成相应的轨迹。使用相似度搜索算法对轨迹数据进行搜索比较，得到近似的最相似轨迹。并保证查询时间短，占用空间少。
2.2 拟采用的技术方案及措施
使用由Indyk和Motwani引入的局部性敏感哈希LSH算法，该算法是近似邻近搜索中最著名的索引方法。对了方便和线性搜索算法进行比较，选择使用基本LSH方法进行研究。其通过构建多个哈希表，每个表中存在多个buckets，将原始数据哈希到不同的buckets中，然后对查询点进行相同哈希，对buckets中碰撞的点进行查找，得到近似邻近解。该方法能够有效的减少查询时间和空间的占用，因此广泛被使用。
算法流程:
#8226; 构造l个hash tables T1; T2;:::TL 每个表Tl由众多buckets组成。
#8226; 对于数据点p使用g(p) = (h1(p);:::hk(p))将其映射到buckets中。
#8226; 对于查询点q使用同样方法将其映射到buckets中。然后找出所有(或3l个) q映射的buckets中存在的p，将其按真实距离排序，并返回前K个值。

通过使用Hausdoff distance或DTW距离将轨迹数据映射成高维数据向量，并将原始数据向量哈希到哈希表中，在给定查询轨迹后，将查询轨迹向量化后进行哈希，然后对碰撞的轨迹向量进行距离比较，从而得到近似的最近轨迹。

4 参考文献
[1] A. Gionis, P. Indyk, and R. Motwani. Similarity search in highdimensions via hashing. Proceedings of the 25thInternational Conference on VeryLarge Data Bases (VLDB), 1999.
[2] P. Indyk and R. Motwani. Approximate nearest neighbor: towards removing thecurse of dimensionality. Proceedings of the Symposium on Theory of Computing,1998.
[3] M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni. Locality-sensitivehashing scheme based on p-stable distributions. In Proc. of the 20th Symposiumon Computational Geometry(SCG), pages 253–262, 2004.
[4]Gao J , Jagadish H V , Lu W , et al. DSH: data sensitive hashing forhigh-dimensional k-nnsearch.[C]// Acm Sigmod International Conference onManagement of Data. ACM, 2014.
[5]Jia Pan , Dinesh Manocha, Fast GPU-based locality sensitivehashing for k-nearest neighbor computation, Proceedings of the 19th ACMSIGSPATIAL International Conference on Advances in Geographic InformationSystems, November01-04, 2011, Chicago, Illinois
[6]Astefanoaei M, Cesaretti P, Katsikouli P, et al. Multi-resolution sketchesand locality sensitive hashing for fast trajectory processing[C]//Proceedingsof the 26th ACM SIGSPATIAL International Conference on Advances in Geographic InformationSystems. ACM, 2018: 279-288.
[7]Tao Y, Yi K, Sheng C, et al. Quality and efficiency in high dimensionalnearest neighbor search[C]//Proceedings of the 2009 ACM SIGMOD InternationalConference on Management of data. ACM, 2009: 563-576.
[8]Sun Y , Wang W , Qin J , et al. SRS : Solving c -Approximate NearestNeighbor Queries in High Dimensional Euclidean Space with a Tiny Index[J].Proceedings of the Vldb Endowment, 2014, 8(1):1-12.
[9]Lv Q, Josephson W, Wang Z, et al. Multi-probe LSH: efficient indexing forhigh-dimensional similarity search[C]//Proceedings of the 33rd internationalconference on Very large data bases. VLDB Endowment, 2007: 950-961.
[10]J. Alman and R. Williams. Probabilistic polynomials and hamming nearestneighbors. In Foundations of Computer Science (FOCS), 2015 IEEE 56th AnnualSymposium on, pages 136–150. IEEE, 2015.
[11] P. Katsikouli, M. Astefanoaei, and R. Sarkar. Distributed mining ofpopular paths in road networks. In DCOSS 2018-International Conference onDistributed Computing in Sensor Systems, pages 1–8. IEEE, 2018
[12]D. Xie, F. Li, and J. M. Phillips. Distributed trajectory similaritysearch. Proceedings of the VLDB Endowment, 10(11):1478–1489, 2017.
[13]A. Driemel and F. Silvestri. Locality-Sensitive Hashing of Curves. In 33rdInternational Symposium on Computational Geometry (SoCG 2017), volume 77, pages37:1–37:16, 2017.
[14]B. Mirzasoleiman, A. Karbasi, R. Sarkar, and A. Krause. Distributedsubmodular maximization. The Journal of Machine Learning Research,17(1):8330–8373, 2016.
[15]R. Panigrahy. Entropy based nearest neighbor search in high dimensions. InProceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm,pages 1186–1195. Society for Industrial and Applied Mathematics, 2006.
[16]J. Zeng, G. Telang, M. P. Johnson, R. Sarkar, J. Gao, E. M. Arkin, and J.S. Mitchell. Mobile r-gather: Distributed and geographic clustering forlocation anonymity. In Proceedings of the 18th ACM International Symposium onMobile
Ad Hoc Networking and Computing. ACM, 2017.