Transforming range queries to equivalent box queries to optimize page access

Range queries based on L 1 distance are a common type of queries in multimedia databases containing feature vectors. We propose a novel approach that transforms the feature space into a new feature space such that range queries in the original space are mapped into equivalent box queries in the tran...

Full description

Saved in:
Bibliographic Details
Published in:Proceedings of the VLDB Endowment 2010-09, Vol.3 (1-2), p.409-416
Main Authors: Pramanik, Sakti, Watve, Alok, Meiners, Chad R., Liu, Alex
Format: Article
Language:English
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:Range queries based on L 1 distance are a common type of queries in multimedia databases containing feature vectors. We propose a novel approach that transforms the feature space into a new feature space such that range queries in the original space are mapped into equivalent box queries in the transformed space. Since box queries are axes aligned, there are several implementational advantages that can be exploited to speed up the retrieval of query results. For two dimensional data the transformation is precise. For greater than two dimensions we propose a space transformation scheme based on disjoint planer rotation, and along with pruning query box the results are precise. Experimental results with large synthetic databases and some real databases show the effectiveness of the proposed transformation scheme. These experimental results have been corroborated with appropriate mathematical models.
ISSN:2150-8097
2150-8097
DOI:10.14778/1920841.1920895