• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文学位 >Proximity problems for point sets with low doubling dimension.
【24h】

Proximity problems for point sets with low doubling dimension.

机译：低倍尺寸点集的邻近问题。

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In this thesis we consider proximity problems on point sets. Proximity problems arise in many fields of computer science, with broad application to computational geometry, machine learning, computational biology, data mining, and the like. In particular, we consider the problems of approximate nearest neighbor search and dynamic maintenance of a spanner for a point set.;It has been conjectured that all algorithms for these two problems suffer from the "curse of dimensionality," which means that their run times grow exponentially with the dimension of the point set. To avoid this undesirable growth, we consider point sets that possess a doubling dimension lambda. We first present a dynamic data structure that uses linear space and supports a (1+epsilon)-approximate nearest neighbor search of the point set. We then extend this data structure to allow the dynamic maintenance of a low degree (1+epsilon)- spanner for the point set. The query and update time of these structures are logarithmic in the size of the point set and exponential in lambda (as opposed to exponential in the dimension); when lambda is small, this provides a significant speed-up over known algorithms, and when lambda and epsilon are constant these run times are optimal up to a constant. The spanner degree is optimal, while the spanner update times improve on all previously known algorithms.
机译：在本文中，我们考虑了点集上的邻近问题。邻近性问题出现在计算机科学的许多领域中，广泛应用于计算几何，机器学习，计算生物学，数据挖掘等。特别是，我们考虑了点集的近似最近邻搜索和扳手动态维护的问题。；据推测，这两个问题的所有算法都遭受“维数诅咒”，这意味着它们的运行时间随着点集的尺寸呈指数增长。为了避免这种不希望的增长，我们考虑具有两倍维度lambda的点集。我们首先介绍一种动态数据结构，该结构使用线性空间并支持点集的（1 +ε）近似最近邻搜索。然后，我们扩展此数据结构，以允许动态维护该点集的低度（1 +ε）-扳手。这些结构的查询和更新时间在点集的大小上是对数的，在lambda中是指数（相对于维数是指数）。当lambda较小时，与已知算法相比，速度显着提高；当lambda和epsilon恒定时，这些运行时间最优化为一个常数。扳手的程度是最佳的，而扳手的更新时间在所有先前已知的算法上都有所改善。

著录项

  • 作者

    Gottlieb, Lee-Ad.;

  • 作者单位

    New York University.;

  • 授予单位 New York University.;
  • 学科 Computer Science.
  • 学位 Ph.D.
  • 年度 2009
  • 页码 108 p.
  • 总页数 108
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类 自动化技术、计算机技术;
  • 关键词

  • 入库时间 2022-08-17 11:38:30

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号