Dimensionality Reduction for Similarity Searching in Dynamic Databases.
Kothuri Venkata Ravi Kanth, Divyakant Agrawal, Ambuj K. Singh:
Dimensionality Reduction for Similarity Searching in Dynamic Databases.
SIGMOD Conference 1998: 166-176@inproceedings{DBLP:conf/sigmod/KanthAS98,
author = {Kothuri Venkata Ravi Kanth and
Divyakant Agrawal and
Ambuj K. Singh},
editor = {Laura M. Haas and
Ashutosh Tiwary},
title = {Dimensionality Reduction for Similarity Searching in Dynamic
Databases},
booktitle = {SIGMOD 1998, Proceedings ACM SIGMOD International Conference
on Management of Data, June 2-4, 1998, Seattle, Washington, USA},
publisher = {ACM Press},
year = {1998},
isbn = {0-89791-995-5},
pages = {166-176},
ee = {http://doi.acm.org/10.1145/276304.276320, db/conf/sigmod/KanthAS98.html},
crossref = {DBLP:conf/sigmod/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
Abstract
Databases are increasingly being used to store multi-media objects
such as maps, images, audio and video. Storage and retrieval
of these objects is accomplished using multi-dimensional index
structures such as R*-trees and SS-trees.
As dimensionality increases,
query performance in these index structures degrades. This phenomenon,
generally referred to as the dimensionality curse, can be circumvented by
reducing the dimensionality of the data.
Such a reduction is however accompanied
by a loss of precision of query results.
Current techniques such as QBIC use SVD
transform-based dimensionality reduction to ensure high query precision.
The drawback of this approach is that SVD is expensive to compute,
and therefore not readily applicable to dynamic databases.
In this paper, we propose novel techniques
for performing SVD-based dimensionality reduction in dynamic databases.
When the data distribution changes considerably so as to degrade query
precision, we recompute the SVD transform and incorporate it in the
existing index structure.
For recomputing the SVD-transform, we propose a novel technique that uses
aggregate data from the existing index rather than the entire data.
This technique reduces the SVD-computation time without compromising
query precision. We then explore efficient ways to incorporate the
recomputed SVD-transform in the existing
index structure without degrading subsequent query response times.
These techniques reduce the computation time by a factor of 20 in
experiments on color and texture image vectors.
The error due to approximate computation of SVD is less than 10%.
Copyright © 1998 by the ACM,
Inc., used by permission. Permission to make
digital or hard copies is granted provided that
copies are not made or distributed for profit or
direct commercial advantage, and that copies show
this notice on the first page or initial screen of
a display along with the full citation.
CDROM Version: Load the CDROM "DiSC, Volume 1 Number 1" and ...
Online Version (ACM WWW Account required): Full Text in PDF Format
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
Printed Edition
Laura M. Haas, Ashutosh Tiwary (Eds.):
SIGMOD 1998, Proceedings ACM SIGMOD International Conference on Management of Data, June 2-4, 1998, Seattle, Washington, USA.
ACM Press 1998, ISBN 0-89791-995-5 
,
SIGMOD Record 27(2),
June 1998
Contents
[Abstract]
[Full Text (Postscript)]
References
- [1]
- Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger:
The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles.
SIGMOD Conference 1990: 322-331
- [2]
- Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel:
The X-tree : An Index Structure for High-Dimensional Data.
VLDB 1996: 28-39
- [3]
- ...
- [4]
- ...
- [5]
- ...
- [6]
- Christos Faloutsos, M. Ranganathan, Yannis Manolopoulos:
Fast Subsequence Matching in Time-Series Databases.
SIGMOD Conference 1994: 419-429
- [7]
- Michael Freeston:
The BANG File: A New Kind of Grid File.
SIGMOD Conference 1987: 260-269
- [8]
- Michael Freeston:
A General Solution of the n-dimensional B-tree Problem.
SIGMOD Conference 1995: 80-91
- [9]
- ...
- [10]
- Jerome H. Friedman, Jon Louis Bentley, Raphael A. Finkel:
An Algorithm for Finding Best Matches in Logarithmic Expected Time.
ACM Trans. Math. Softw. 3(3): 209-226(1977)
- [11]
- ...
- [12]
- ...
- [13]
- Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57
- [14]
- David A. Hull:
Improving Text Retrieval for the Routing Problem using Latent Semantic Indexing.
SIGIR 1994: 282-291
- [15]
- Jon Louis Bentley:
Multidimensional Binary Search Trees Used for Associative Searching.
Commun. ACM 18(9): 509-517(1975)
- [16]
- Norio Katayama, Shin'ichi Satoh:
The SR-tree: An Index Structure for High-Dimensional Nearest Neighbor Queries.
SIGMOD Conference 1997: 369-380
- [17]
- King-Ip Lin, H. V. Jagadish, Christos Faloutsos:
The TV-Tree: An Index Structure for High-Dimensional Data.
VLDB J. 3(4): 517-542(1994)
- [18]
- David B. Lomet, Betty Salzberg:
The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance.
ACM Trans. Database Syst. 15(4): 625-658(1990)
- [19]
- ...
- [20]
- ...
- [21]
- Wayne Niblack, Ron Barber, William Equitz, Myron Flickner, Eduardo H. Glasman, Dragutin Petkovic, Peter Yanker, Christos Faloutsos, Gabriel Taubin:
The QBIC Project: Querying Images by Content, Using Color, Texture, and Shape.
Storage and Retrieval for Image and Video Databases (SPIE) 1993: 173-187
- [22]
- ...
- [23]
- Gerard Salton:
Automatic Text Processing: The Transformation, Analysis, and Retrieval of Information by Computer.
Addison-Wesley 1989, ISBN 0-201-12227-8
- [24]
- ...
- [25]
- David A. White, Ramesh Jain:
Similarity Indexing with the SS-tree.
ICDE 1996: 516-523
- [26]
- Daniel Wu, Divyakant Agrawal, Amr El Abbadi, Ambuj K. Singh, Terence R. Smith:
Efficient Retrieval for Browsing Large Image Databases.
CIKM 1996: 11-18
Referenced by
- Kaushik Chakrabarti, Sharad Mehrotra:
Local Dimensionality Reduction: A New Approach to Indexing High Dimensional Spaces.
VLDB 2000: 89-100
- Charu C. Aggarwal, Philip S. Yu:
Finding Generalized Projected Clusters In High Dimensional Spaces.
SIGMOD Conference 2000: 70-81
- Roger Weber, Klemens Böhm:
Trading Quality for Time with Nearest Neighbor Search.
EDBT 2000: 21-35
- Gísli R. Hjaltason, Hanan Samet:
Distance Browsing in Spatial Databases.
ACM Trans. Database Syst. 24(2): 265-318(1999)
- Aristides Gionis, Piotr Indyk, Rajeev Motwani:
Similarity Search in High Dimensions via Hashing.
VLDB 1999: 518-529
- Kelvin Kam Wing Chu, Man Hon Wong:
Fast Time-Series Searching with Scaling and Shifting.
PODS 1999: 237-248
Copyright © Mon Nov 2 21:12:25 2009
by Michael Ley (ley@uni-trier.de)
