The DOI matches its Crossref record; 19 of the 19 references it cites were found in a registry or an index.
Dimensionality reduction for similarity searching in dynamic databases
Open accessAbstract
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%.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
Multidimensional binary search trees used for associative searching
Bentley, J. L. (1975) · Communications of the ACM · doi:10.1145/361002.361007 · Cited by 7,520
R-trees: a dynamic index structure for spatial searching
Guttman, A. (1984) · Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84 · doi:10.1145/602259.602266 · Cited by 6,580
The R*-tree: an efficient and robust access method for points and rectangles
Beckmann, N., Kriegel, H.-P., Schneider, R., & Seeger, B. (1990) · Proceedings of the 1990 ACM SIGMOD international conference on Management of data · doi:10.1145/93597.98741 · Cited by 4,161
An Algorithm for Finding Best Matches in Logarithmic Expected Time
Friedman, J. H., Bentley, J. L., & Finkel, R. A. (1977) · ACM Transactions on Mathematical Software · doi:10.1145/355744.355745 · Cited by 2,813
QBIC project: querying images by content, using color, texture, and shape:
Niblack, C. W., Barber, R., Equitz, W., Flickner, M. D., Glasman, E. H., Petkovic, D., Yanker, P., Faloutsos, C., & Taubin, G. (1993) · SPIE Proceedings · doi:10.1117/12.143648 · Cited by 1,747
Fast subsequence matching in time-series databases
Faloutsos, C., Ranganathan, M., & Manolopoulos, Y. (1994) · Proceedings of the 1994 ACM SIGMOD international conference on Management of data · doi:10.1145/191839.191925 · Cited by 1,709
Salton, G. (1988) · Cited by 1,587
Berchtold, S., Keim, D. A., & Kriegel, H.-P. (2002) · Readings in Multimedia Computing and Networking · doi:10.1016/b978-155860651-7/50124-8 · Cited by 1,118
Faloutsos, C., & Lin, K.-I. (1995) · Proceedings of the 1995 ACM SIGMOD international conference on Management of data - SIGMOD '95 · doi:10.1145/223784.223812 · Cited by 897
The SR-tree: an index structure for high-dimensional nearest neighbor queries
Katayama, N., & Satoh, S. (1997) · Proceedings of the 1997 ACM SIGMOD international conference on Management of data - SIGMOD '97 · doi:10.1145/253260.253347 · Cited by 817
Bookstein, A. (1990) · Information Processing & Management · doi:10.1016/0306-4573(90)90016-u · Cited by 699
Similarity indexing with the SS-tree
White, D. A., & Jain, R. (2002) · Proceedings of the Twelfth International Conference on Data Engineering · doi:10.1109/icde.1996.492202 · Cited by 635
The TV-tree: An index structure for high-dimensional data
Lin, K.-I., Jagadish, H. V., & Faloutsos, C. (1994) · The VLDB Journal · doi:10.1007/bf01231606 · Cited by 494
The X Tree: An Index Structure for High Dimensional Data
Berchtold, S., Keim, D. A., & Kriegel, H.-P. (1996) · KOPS (University of Konstanz) · Cited by 414
An Eigenspace Update Algorithm for Image Analysis
Chandrasekaran, S., Manjunath, B. S., Wang, Y. F., Winkeler, J., & Zhang, H. (1997) · Graphical Models and Image Processing · doi:10.1006/gmip.1997.0425 · Cited by 233
Improving text retrieval for the routing problem using latent semantic indexing
Hull, D. A. (1994) · doi:10.5555/188490.188585 · Cited by 155
Efficient retrieval for browsing large image databases
Wu, D. D., Singh, A. K., Agrawal, D., Abbadi, A. E., & Smith, T. R. (1996) · ACM International Conference on Information and Knowledge Management (CIKM) · doi:10.1145/238355.238365 · Cited by 71
Self-citationIp, L., JagadishH., V., & FaloutsosChristos (1994) · Very Large Data Bases · doi:10.5555/615204.615210 · Cited by 53
Cited by
(1999) · Cited by 3,186
Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases
Keogh, E., Chakrabarti, K., Pazzani, M., & Mehrotra, S. (2001) · Knowledge and Information Systems · doi:10.1007/pl00011669 · Cited by 1,573
Esling, P., & Agon, C. (2012) · ACM Computing Surveys · doi:10.1145/2379776.2379788 · Cited by 997
Locally adaptive dimensionality reduction for indexing large time series databases
Keogh, E., Chakrabarti, K., Pazzani, M., & Mehrotra, S. (2001) · Proceedings of the 2001 ACM SIGMOD international conference on Management of data · doi:10.1145/375663.375680 · Cited by 866
Finding generalized projected clusters in high dimensional spaces
Aggarwal, C. C., & Yu, P. S. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335383 · Cited by 530
Metadata
- Authors
- Ravi Kanth, K. V., Agrawal, D., & Singh, A.
- Venue
- Proceedings of the 1998 ACM SIGMOD international conference on Management of data
- Publisher
- ACM
- Published
- 1998-06
- Pages
- 166-176
- ISSN
- 0730-8078 (ISSN-L)
- OpenAlex
- W2084481683
- Cited by
- 256
- References
- 19
- FWCI
- 19.10
- Type
- conference paper
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.