Sakti Pramanik
Chad R. Meiners
Abstract
Range queries based on L1 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.
- C. C. Aggarwal. On the effects of dimensionality reduction on high dimensional similarity search. In PODS '01: Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 256--266, New York, NY, USA, 2001. ACM. Google Scholar
Digital Library
- N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree: an efficient and robust access method for points and rectangles. Proceedings of ACM SIGMOD, pages 322--331, 1990. Google ScholarDigital Library
- S. Berchtold, D. Keim, and H.-P. Kriegel. The X-tree: an index structure for high-dimensional data. Proceedings of the 22nd International Conference on VLDB, pages 28--39, 1996. Google ScholarDigital Library
- K. Chakrabarti, E. Keogh, S. Mehrotra, and M. Pazzani. Locally adaptive dimensionality reduction for indexing large time series databases. ACM Trans. Database Syst., 27(2):188--228, 2002. Google ScholarDigital Library
- P. Ciaccia, M. Patella, and P. Zezula. M-tree: An efficient access method for similarity search in metric spaces. In VLDB '97: Proceedings of the 23rd International Conference on Very Large Data Bases, pages 426--435, San Francisco, CA, USA, 1997. Morgan Kaufmann Publishers Inc. Google ScholarDigital Library
- A. Guttman. R-trees: a dynamic index structure for spatial searching. Proceedings of ACM SIGMOD, pages 47--57, 1984. Google ScholarDigital Library
- G. R. Hjaltason and H. Samet. Index-driven similarity search in metric spaces (survey article). ACM Trans. Database Syst., 28(4):517--580, 2003. Google ScholarDigital Library
- I. F. Ilyas, G. Beskales, and M. A. Soliman. A survey of top-k query processing techniques in relational database systems. ACM Comput. Surv., 40(4):1--58, 2008. Google ScholarDigital Library
- N. Katayama and S. Satoh. The SR-tree: an index structure for high-dimensional nearest neighbor queries. In SIGMOD '97: Proceedings of the 1997 ACM SIGMOD international conference on Management of data, pages 369--380, New York, NY, USA, 1997. ACM. Google ScholarDigital Library
- A. Kumar. G-tree: A new data structure for organizing multidimensional data. IEEE Trans. on Knowl. and Data Eng., 6(2):341--347, 1994. Google ScholarDigital Library
- S. Lang. Linear Algebra. New York: Springer-Verlag, 1987.Google Scholar
- K. V. Ravi Kanth, D. Agrawal, and A. Singh. Dimensionality reduction for similarity searching in dynamic databases. SIGMOD Rec., 27(2):166--176, 1998. Google ScholarDigital Library
- J. Robinson. The K-D-B-tree: a search structure for large multidimensional dynamic indexes. Proceedings of ACM SIGMOD, pages 10--18, 1981. Google ScholarDigital Library
- J. K. Uhlmann. Satisfying general proximity/similarity queries with metric trees. Inf. Process. Lett., 40(4):175--179, 1991.Google ScholarCross Ref
- http://download.oracle.com/docs/html/B10829\_01/toc.htm. Oracle intermedia reference - 10g release 1(10.1).Google Scholar
- http://www.cse.msu.edu/~watvealo/mysoftware.html. Web url for source code.Google Scholar
- V. Vapnik. The Nature of Statistical Learning Theory. Springer, New York, 1995. Google ScholarDigital Library
- K. Vu, K. A. Hua, H. Cheng, and S.-D. Lang. A non-linear dimensionality-reduction technique for fast similarity search in large databases. In SIGMOD '06: Proceedings of the 2006 ACM SIGMOD international conference on Management of data, pages 527--538, New York, NY, USA, 2006. ACM. Google ScholarDigital Library
- R. Weber, H.-J. Schek, and S. Blott. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In Proceedings of the 24rd International Conference on Very Large Data Bases, pages 194--205, San Francisco, CA, USA, 1998. Morgan Kaufmann Publishers Inc. Google ScholarDigital Library
- D. A. White and R. Jain. Similarity indexing with the ss-tree. In Proceedings of the 12th International Conference on Data Engineering, pages 516--523, Washington, DC, USA, 1996. IEEE Computer Society. Google ScholarDigital Library
Index Terms
- Transforming range queries to equivalent box queries to optimize page access
Recommendations
Range queries on uncertain data
Given a set P of n uncertain points on the real line, each represented by its one-dimensional probability density function, we consider the problem of building data structures on P to answer range queries of the following three types for any query ...
Decidable containment of recursive queries
Database theoryOne of the most important reasoning tasks on queries is checking containment, i.e., verifying whether one query yields necessarily a subset of the result of another one. Query containment is crucial in several contexts, such as query optimization, query ...
Approximating expressive queries on graph-modeled data
We present GeX for the approximate matching of complex queries on graph-modeled data.GeX generalizes existing approaches and allows for querying any graph-based datasets.GeX query language supports queries ranging from keyword-based to complex ones.GeX ...
Comments