• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Symposium on Computer and Information Sciences(ISCIS 2004); 20041027-29; Kemer-Antalya(TR) >Efficient Methods for Database Storage and Retrieval Using Space-Filling Curves
【24h】

Efficient Methods for Database Storage and Retrieval Using Space-Filling Curves

机译：使用空间填充曲线进行数据库存储和检索的有效方法

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

摘要

Efficient storage and retrieval of records involving multiple keys is a difficult and well-studied problem. A popular solution employed is to visualize the records- as points in multidimensional space and use a mapping from this multidimensional space to the one-dimensional space of block addresses in secondary storage. There is significant interest in performing such a mapping using space-filling curves. Unfortunately, space-filling curves are defined for points that lie on a uniform grid of a particular resolution. As a result, both storage and retrieval algorithms based on space-filling curves depend upon the size of the grid. This makes the run time of such algorithms dependent on the distribution of the points and in fact, unbounded for arbitrary distributions. There are two main contributions in this paper: First, we present a distribution-independent algorithm for storing records with multiple keys using space-filling curves. Our algorithm runs in O(kn log n) time for storing n records containing k key fields. We then present an algorithm for answering range queries with a bounded running time independent of the distribution.
机译：涉及多个键的记录的有效存储和检索是一个困难且经过充分研究的问题。一种流行的解决方案是将记录可视化为多维空间中的点，并使用从该多维空间到二级存储中块地址的一维空间的映射。使用空间填充曲线执行这种映射引起了极大的兴趣。不幸的是，为位于特定分辨率的均匀网格上的点定义了空间填充曲线。结果，基于空间填充曲线的存储和检索算法都取决于网格的大小。这使得此类算法的运行时间取决于点的分布，并且实际上不受任意分布的限制。本文有两个主要贡献：首先，我们提出了一种与分布无关的算法，用于使用空间填充曲线存储具有多个键的记录。我们的算法以O（kn log n）时间运行，用于存储包含k个关键字段的n条记录。然后，我们提出一种算法，用于以不受限制的运行时间来响应范围查询，而该运行时间与分布无关。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号