首页> 外文期刊>IEEE Transactions on Knowledge and Data Engineering >The BoND-Tree: An Efficient Indexing Method for Box Queries in Nonordered Discrete Data Spaces
【24h】

The BoND-Tree: An Efficient Indexing Method for Box Queries in Nonordered Discrete Data Spaces

机译:BoND树:一种无序离散数据空间中的框查询的有效索引方法

获取原文
获取原文并翻译 | 示例

摘要

Box queries (or window queries) are a type of query which specifies a set of allowed values in each dimension. Indexing feature vectors in the multidimensional Nonordered Discrete Data Spaces (NDDS) for efficient box queries are becoming increasingly important in many application domains such as genome sequence databases. Most of the existing work in this field targets the similarity queries (range queries and k-NN queries). Box queries, however, are fundamentally different from similarity queries. Hence, the same indexing schemes designed for similarity queries may not be efficient for box queries. In this paper, we present a new indexing structure specifically designed for box queries in the NDDS. Unique characteristics of the NDDS are exploited to develop new node splitting heuristics. For the BoND-tree, we also provide theoretical analysis to show the optimality of the proposed heuristics. Extensive experiments with synthetic data demonstrate that the proposed scheme is significantly more efficient than the existing ones when applied to support box queries in NDDSs. We also show effectiveness of the proposed scheme in a real-world application of primer design for genome sequence databases.
机译:框式查询(或窗口查询)是一种查询类型,它在每个维度中指定一组允许的值。在多维无序离散数据空间(NDDS)中进行有效框查询的索引特征向量在许多应用领域(如基因组序列数据库)中变得越来越重要。该领域中的大多数现有工作都针对相似性查询(范围查询和k-NN查询)。但是,框式查询与相似性查询从根本上是不同的。因此,为相似性查询设计的相同索引方案对于框式查询可能无效。在本文中,我们提出了一种新的索引结构,该结构专门为NDDS中的框查询设计。利用NDDS的独特特性来开发新的节点拆分启发式算法。对于BoND树,我们还提供了理论分析,以证明所提出的启发式算法的最优性。使用合成数据进行的大量实验表明,该方案在应用于NDDS中的框查询时,其效率明显高于现有方案。我们还显示了该方案在基因组序列数据库引物设计的实际应用中的有效性。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号