The TV-Tree: An Index Structure for High-Dimensional Data.

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)

@article{DBLP:journals/vldb/LinJF94,
  author    = {King-Ip Lin and
               H. V. Jagadish and
               Christos Faloutsos},
  title     = {The TV-Tree: An Index Structure for High-Dimensional Data},
  journal   = {VLDB J.},
  volume    = {3},
  number    = {4},
  year      = {1994},
  pages     = {517-542},
  ee        = {db/journals/vldb/LinJF94.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We propose a file structure to index high-dimensionality data, which are typically points in some feature space. The idea is to use only a few of the features, using additional features only when the additional discriminatory power is absolutely necessary. We present in detail the design of our tree structure and the associated algorithms that handle such "varying length" feature vectors. Finallly, we report simulation results, comparing the proposed structure with the R*-tree, which is one of the most successful methods for low-dimensionality spaces. The results illustrate the superiority of our method, which saves up to 80% in disk accesses.

Copyright © 1994 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Key Words

Spatial index, similarity retrieval, query by content.

Online Paper

Download PDF file (www.vldb.org, Darmstadt, Germany)
Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/An4-1 or /cdrom

DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD2 or /dvd

References

[Agrawal et al. 1993]: Rakesh Agrawal, Christos Faloutsos, Arun N. Swami: Efficient Similarity Search In Sequence Databases. FODO 1993: 69-84
[Altschul et al. 1990]: ...
[Angell et al. 1983]: ...
[Arya et al. 1993]: Manish Arya, William F. Cody, Christos Faloutsos, Joel E. Richardson, Arthur Toya: QBISM: A Prototype 3-D Medical Image Database System. IEEE Data Eng. Bull. 16(1): 38-42(1993)
[Aurenhammer 1991]: Franz Aurenhammer: Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure. ACM Comput. Surv. 23(3): 345-405(1991)
[Beckmann et al. 1990]: 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
[Bentley et al. 1980]: ...
[Brinkhoff et al. 1993]: Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246
[Chatfield 1984]: ...
[Friedman et al. 1975]: ...
[Fukunaga 1990]: ...
[Fukunaga & Narendra 1975]: Keinosuke Fukunaga, Patrenahalli M. Narendra: A Branch and Bound Algorithms for Computing k-nearest Neighbors. IEEE Trans. Computers 24(7): 750-753(1975)
[Greene 1989]: Diane Greene: An Implementation and Performance Analysis of Spatial Data Access Methods. ICDE 1989: 606-615
[Guttman 1984]: Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57
[Hamming 1977]: ...
[Hartigan 1975]: ...
[Hoel & Samet 1992]: Erik G. Hoel, Hanan Samet: A Qualitative Comparison Study of Data Structures for Large Line Segment Databases. SIGMOD Conference 1992: 205-214
[Hunter & Steiglitz 1979]: ...
[Jagadish 1990]: H. V. Jagadish: Spatial Search with Polyhedra. ICDE 1990: 311-319
[Jagadish 1991]: H. V. Jagadish: A Retrieval Technique for Similar Shapes. SIGMOD Conference 1991: 208-217
[Kamel & Faloutsos 1993]: Ibrahim Kamel, Christos Faloutsos: Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994: 500-509
[Kukich 1992]: Karen Kukich: Techniques for Automatically Correcting Words in Text. ACM Comput. Surv. 24(4): 377-439(1992)
[Mandelbrot 1977]: ...
[Murtagh 1983]: Fionn Murtagh: A Survey of Recent Advances in Hierarchical Clustering Algorithms. Comput. J. 26(4): 354-359(1983)
[Narasimhalu & Christodoulakis 1991]: A. Desai Narasimhalu, Stavros Christodoulakis: Multimedia Information Systems: The Unfolding of a Reality (Guest Editors' Introduction). IEEE Computer 24(10): 6-8(1991)
[Niblack et al. 1993]: 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
[Nievergelt et al. 1984]: Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984)
[Orenstein & Manola 1988]: Jack A. Orenstein, Frank Manola: PROBE Spatial Data Modeling and Query Processing in an Image Database Application. IEEE Trans. Software Eng. 14(5): 611-629(1988)
[Ruskai et al. 1992]: ...
[Salton & Wong 1978]: Gerard Salton, A. Wong: Generation and Search of Clustered Files. ACM Trans. Database Syst. 3(4): 321-346(1978)
[Samet 1989]: Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
[Schroeder 1991]: ...
[Wallace 1991]: Gregory K. Wallace: The JPEG Still Picture Compression Standard. Commun. ACM 34(4): 30-44(1991)