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

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 gen...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on knowledge and data engineering 2013-11, Vol.25 (11), p.2629-2643
Main Authors: Changqing Chen, Watve, Alok, Pramanik, Sakti, Qiang Zhu
Format: Article
Language:English
Subjects:
Bioinformatics
Box query
categorical data
Filtering
Genomics
Indexing
nonordered discrete data
Vectors
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1041-4347
1558-2191
DOI:10.1109/TKDE.2012.132