The problem of Approximate Nearest Neighbor (ANN) search is fundamental in computer science and has benefited from significant progress in the past couple of decades. However, most work has been devoted to pointsets whereas complex shapes have not been sufficiently treated. Here, we focus on distance functions between discretized curves in Euclidean space: they appear in a wide range of applications, from road segments to time-series in general dimension. For $\ell_p$-products of Euclidean metrics, for any $p$, we design simple and efficient data structures for ANN, based on randomized projections, which are of independent interest. They serve to solve proximity problems under a notion of distance between discretized curves, which generalizes both discrete Fr\'echet and Dynamic Time Warping distances. These are the most popular and practical approaches to comparing such curves. We offer the first data structures and query algorithms for ANN with arbitrarily good approximation factor, at the expense of increasing space usage and preprocessing time over existing methods. Query time complexity is comparable or significantly improved by our algorithms, our algorithm is especially efficient when the length of the curves is bounded.


翻译:近邻近距离搜索(ANN)问题在计算机科学中具有根本意义,并受益于过去几十年的显著进展。然而,大部分工作都用于点点子,而复杂的形状没有得到充分处理。在这里,我们集中关注在Euclidean空间的离散曲线之间的距离功能:它们出现在从路段到一般时间序列的广泛应用中。对于Euclidean 度量的产物,对于任何美元,我们根据随机化的预测为ANN设计简单而有效的数据结构,这是独立感兴趣的。它们有助于在离散曲线之间的距离概念下解决近距离问题,该概念将离散的Fr\'echet和动态时间旋转距离都加以概括。这是比较这些曲线最受欢迎和最实用的方法。我们为ANN提供了第一种数据结构和查询算法,其任意的近似系数,而牺牲了空间使用的增加和现有方法的预处理时间。根据我们的算法,时间复杂性是可比较或大大改进的,当我们算法的曲线长度是特别有效的。

3
下载
关闭预览

相关内容

因果图,Causal Graphs,52页ppt
专知会员服务
241+阅读 · 2020年4月19日
专知会员服务
53+阅读 · 2020年3月16日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
91+阅读 · 2019年10月10日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【论文】图上的表示学习综述
机器学习研究会
12+阅读 · 2017年9月24日
【推荐】深度学习目标检测全面综述
机器学习研究会
21+阅读 · 2017年9月13日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Arxiv
24+阅读 · 2020年3月11日
Arxiv
6+阅读 · 2018年11月29日
Arxiv
3+阅读 · 2018年6月18日
Arxiv
9+阅读 · 2018年3月28日
Arxiv
7+阅读 · 2018年3月21日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关资讯
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
【论文】图上的表示学习综述
机器学习研究会
12+阅读 · 2017年9月24日
【推荐】深度学习目标检测全面综述
机器学习研究会
21+阅读 · 2017年9月13日
【推荐】SVM实例教程
机器学习研究会
17+阅读 · 2017年8月26日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
相关论文
Top
微信扫码咨询专知VIP会员