article

Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases

Authors:
Christian Böhm

University of Munich, München, Germany

University of Munich, München, Germany
View Profile

,
Stefan Berchtold

stb ag, Germany, Augsburg, Germany

stb ag, Germany, Augsburg, Germany
View Profile

,
Daniel A. Keim

AT&T Research Labs and University of Constance, Konstanz, Germany

AT&T Research Labs and University of Constance, Konstanz, Germany
View Profile

Authors Info & Claims

ACM Computing Surveys Volume 33 Issue 3pp 322–373https://doi.org/10.1145/502807.502809

Published:01 September 2001Publication History

ACM Computing Surveys

Abstract

During the last decade, multimedia databases have become increasingly important in many application areas such as medicine, CAD, geography, and molecular biology. An important research issue in the field of multimedia databases is the content-based retrieval of similar multimedia objects such as images, text, and videos. However, in contrast to searching data in a relational database, a content-based retrieval requires the search of similar objects as a basic functionality of the database system. Most of the approaches addressing similarity search use a so-called feature transformation that transforms important properties of the multimedia objects into high-dimensional points (feature vectors). Thus, the similarity search is transformed into a search of points in the feature space that are close to a given query point in the high-dimensional feature space. Query processing in high-dimensional spaces has therefore been a very active research area over the last few years. A number of new index structures and algorithms have been proposed. It has been shown that the new index structures considerably improve the performance in querying large multimedia databases. Based on recent tutorials [Berchtold and Keim 1998], in this survey we provide an overview of the current state of the art in querying multimedia databases, describing the index structures and algorithms for an efficient query processing in high-dimensional spaces. We identify the problems of processing queries in high-dimensional space, and we provide an overview of the proposed approaches to overcome these problems.

References

ABEL, D. AND SMITH, J. 1983. A data structure and algorithm based on a linear key for a rectangle retrieval problem. Comput. Vis. 24, 1-13.]]Google Scholar
AGRAWAL, R., FALOUTSOS,C.,AND SWAMI, A. 1993. Efficient similarity search in sequence databases. In Proc. 4th Int. Conf. on Foundations of Data Organization and Algorithms, LNCS 730, 69-84.]] Google ScholarDigital Library
AGRAWAL, R., GEHRKE, J., GUNOPULOS,D.,AND RAGHAVAN, P. 1998. Automatic subspace clustering of high-dimensional data for data mining applications. In Proc. ACM SIGMOD Int. Conf. on Management of Data (Seattle), 94-105.]] Google ScholarDigital Library
AGRAWAL, R., LIN, K., SAWHNEY, H., AND SHIM,K. 1995. Fast similarity search in the presence of noise, scaling, and translation in time-series databases. In Proc. 21st Int. Conf. on Very Large Databases, 490-501.]] Google ScholarDigital Library
ALTSCHUL, S., GISH, W., MILLER, W., MYERS, E., AND LIPMAN, D. 1990. A basic local alignment search tool. J. Molecular Biol. 215, 3, 403-410.]]Google ScholarCross Ref
AOKI, P. 1998. Generalizing "search" in generalized search trees. In Proc. 14th Int. Conf. on Data Engineering (Orlando, FL), 380-389.]] Google ScholarDigital Library
AREF,W.AND SAMET, H. 1991. Optimization strategies for spatial query processing. In Proc. 17th Int. Conf. on Very Large Databases (Barcelona), 81-90.]] Google ScholarDigital Library
ARYA, S. 1995. Nearest neighbor searching and applications. PhD thesis, University of Maryland, College Park, MD.]] Google ScholarDigital Library
ARYA, S., MOUNT,D.,AND NARAYAN, O. 1995. Accounting for boundary effects in nearest neighbor searching. In Proc. 11th Symp. on Computational Geometry (Vancouver, Canada), 336-344.]] Google ScholarDigital Library
BAEZA-YATES, R., CUNTO, W., MANBER,U.,AND WU,S. 1994. Proximity matching using fixed-queries trees. In Proc. Combinatorial Pattern Matching, LNCS 807, 198-212.]] Google ScholarDigital Library
BAYER,R.AND MCCREIGHT, E. 1977. Organization and maintenance of large ordered indices. Acta Inf. 1, 3, 173-189.]]Google ScholarDigital Library
BECKMANN, N., KRIEGEL, H.-P., SCHNEIDER, R., AND SEEGER, B. 1990. The r*-tree: An efficient and robust access method for points and rectangles. In Proc. ACM SIGMOD Int. Conf. on Management of Data (Atlantic City, NJ), 322-331.]] Google ScholarDigital Library
BELUSSI,A.AND FALOUTSOS, C. 1995. Estimating the selectivity of spatial queries using the correlation fractal dimension. In Proc. 21st Int. Conf. on Very Large Databases (Zurich), 299- 310.]] Google ScholarDigital Library
BENTLEY, J. 1975. Multidimensional search trees used for associative searching. Commun. ACM 18, 9, 509-517.]] Google ScholarDigital Library
BENTLEY, J. 1979. Multidimensional binary search in database applications. IEEE Trans. Softw. Eng. 4, 5, 397-409.]]Google Scholar
BERCHTOLD,S.AND KEIM, D. 1998. High-dimensional index structures-Database support for next decades's applications. In Tutorial ACM SIGMOD Int. Conf. on Management of Data (Seattle, NJ).]] Google ScholarDigital Library
BERCHTOLD, S., B~HM, C., BRAUNM~ ULLER, B., KEIM,D., AND KRIEGEL, H.-P. 1997a. Fast parallel similarity search in multimedia databases. In Proc. ACM SIGMOD Int. Conf. on Management of Data.]] Google ScholarDigital Library
BERCHTOLD, S., B~OHM, C., JAGADISH, H., KRIEGEL, H.-P., AND SANDER, J. 2000a. Independent quantization: An index compression technique for highdimensional data spaces. In Proc. 16th Int. Conf. on Data Engineering.]]Google Scholar
BERCHTOLD, S., B~OHM, C., KEIM,D.,AND KRIEGEL, H.-P. 1997b. A cost model for nearest neighbor search in high-dimensional data space. In Proc. ACM PODS Symp. on Principles of Database Systems (Tucson, AZ).]] Google ScholarDigital Library
BERCHTOLD, S., B~OHM, C., KEIM,D.,AND KRIEGEL, H.-P. 2001. On optimizing processing of nearest neighbor queries in high-dimensional data space. Proc. Conf. on Database Theory, 435-449.]] Google ScholarDigital Library
BERCHTOLD, S., B~OHM, C., KEIM, D., KRIEGEL, H.-P., AND XU, X. 2000c. Optimal multidimensional query processing using tree striping. Dawak, 244-257.]] Google ScholarDigital Library
BERCHTOLD, S., B~OHM,C.,AND KRIEGEL, H.-P. 1998a. Improving the query performance of high-dimensional index structures using bulk-load operations. In Proc. 6th Int. Conf. on Extending Database Technology (Valencia, Spain).]] Google ScholarDigital Library
BERCHTOLD, S., B~OHM,C.,AND KRIEGEL, H.-P. 1998b. The pyramid-technique: Towards indexing beyond the curse of dimensionality. In Proc. ACM SIGMOD Int. Conf. on Management of Data (Seattle, NJ), 142-153.]] Google ScholarDigital Library
BERCHTOLD, S., ERTL, B., KEIM, D., KRIEGEL, H.-P., AND SEIDL, T. 1998c. Fast nearest neighbor search in high-dimensional spaces. In Proc. 14th Int. Conf. on Data Engineering (Orlando, FL).]] Google ScholarDigital Library
BERCHTOLD, S., JAGADISH, H., AND ROSS, K. 1998d. Independence diagrams: A technique for visual data mining. In Proc. 4th Int. Conf. on Knowledge Discovery and Data Mining (New York), 139- 143.]]Google Scholar
BERCHTOLD, S., KEIM,D.,AND KRIEGEL, H.-P. 1996. The x-tree: An index structure for high-dimensional data. In Proc. 22nd Int. Conf. on Very Large Databases (Bombay), 28-39.]] Google ScholarDigital Library
BERCHTOLD, S., KEIM, D., KRIEGEL, H.-P., AND SEIDL, T. 2000d. Indexing the solution space: A new technique for nearest neighbor search in high-dimensional space. IEEE Trans. Knowl. Data Eng., 45-57.]] Google ScholarDigital Library
BEYER, K., GOLDSTEIN, J., RAMAKRISHNAN, R., AND SHAFT, U. 1999. When is "nearest neighbor" mean-ingful? In Proc. Int. Conf. on Database Theory, 217-235.]] Google ScholarDigital Library
B~OHM, C. 1998. Efficiently indexing highdimensional databases. PhD thesis, University of Munich, Germany.]]Google Scholar
B~OHM, C. 2000. A cost model for query processing in high-dimensional data spaces. To appear in: ACM Trans. Database Syst.]] Google ScholarDigital Library
BOZKAYA,T.AND OZSOYOGLU, M. 1997. Distancebased indexing for high-dimensional metric spaces. SIGMOD Rec. 26, 2, 357-368.]] Google ScholarDigital Library
BRIN, S. 1995. Near neighbor search in large metric spaces. In Proc. 21st Int. Conf. on Very Large Databases (Switzerland), 574-584.]] Google ScholarDigital Library
BURKHARD,W.AND KELLER, R. 1973. Some approaches to best-match file searching. Commun. ACM 16, 4, 230-236.]] Google ScholarDigital Library
CHEUNG,K.AND FU, A. 1998. Enhanced nearest neighbour search on the r-tree. SIGMOD Rec. 27, 3, 16-21.]] Google ScholarDigital Library
CHIUEH, T. 1994. Content-based image indexing. In Proc. 20th Int. Conf. on Very Large Databases (Chile), 582-593.]] Google ScholarDigital Library
CIACCIA, P., PATELLA, M., AND ZEZULA, P. 1997. M- tree: An efficient access method for similarity search in metric spaces. In Proc. 23rd Int. Conf. on Very Large Databases (Greece), 426- 435.]] Google ScholarDigital Library
CIACCIA, P., PATELLA, M., AND ZEZULA, P. 1998. A cost model for similarity queries in metric spaces. In Proc. 17th ACMSymp. on Principles of Database Systems (Seattle), 59-67.]] Google ScholarDigital Library
CLEARY, J. 1979. Analysis of an algorithm for finding nearest neighbors in Euclidean space. ACM Trans. Math. Softw. 5, 2, 183-192.]] Google ScholarDigital Library
COMER, D. 1979. The ubiquitous b-tree. ACMComput. Surv. 11, 2, 121-138.]] Google ScholarDigital Library
CORRAL, A., MANOLOPOULOS, Y., THEODORIDIS,Y., AND VASSILAKOPOULOS, M. 2000. Closest pair queries in spatial databases. In Proc. ACM SIG-MOD Int. Conf. on Management of Data, 189- 200.]] Google ScholarDigital Library
EASTMAN, C. 1981. Optimal bucket size for nearest neighbor searching in kd-trees. Inf. Proc. Lett. 12,4.]]Google ScholarCross Ref
EVANGELIDIS, G. 1994. The hB -tree: A concurrent and recoverable multi-attribute index structure. PhD thesis, Northeastern University, Boston, MA.]]Google Scholar
EVANGELIDIS, G., LOMET,D.,AND SALZBERG, B. 1997. The hB-tree: A multiattribute index supporting concurrency, recovery and node consolidation. VLDB J. 6, 1, 1-25.]] Google ScholarDigital Library
FALOUTSOS, C. 1985. Multiattribute hashing using gray codes. In Proc. ACM SIGMOD Int. Conf. on Management of Data, 227-238.]] Google ScholarDigital Library
FALOUTSOS, C. 1988. Gray codes for partial match and range queries. IEEE Trans. Softw. Eng. 14, 1381-1393.]] Google ScholarDigital Library
FALOUTSOS,C.AND GAEDE, V. 1996. Analysis of ndimensional quadtrees using the Hausdorff fractal dimension. In Proc. 22nd Int. Conf. on Very Large Databases (Mumbai, India), 40-50.]] Google ScholarDigital Library
FALOUTSOS,C.AND KAMEL, I. 1994. Beyond uniformity and independence: Analysis of r-trees using the concept of fractal dimension. In Proc. 13th ACMSIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems (Minneapolis, MN), 4-13.]] Google ScholarDigital Library
FALOUTSOS,C.AND LIN, K.-I. 1995. Fast map: A fast algorithm for indexing, data-mining and visualization of traditional and multimedia data. In Proc. ACM SIGMOD Int. Conf. on Management of Data (San Jose, CA), 163-174.]] Google ScholarDigital Library
FALOUTSOS,C.AND ROSEMAN, S. 1989. Fractals for secondary key retrieval. In Proc. 8th ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, 247-252.]] Google ScholarDigital Library
FALOUTSOS, C., BARBER, R., FLICKNER, M., AND HAFNER, J. 1994a. Efficient and effective querying by image content. J. Intell. Inf. Syst. 3, 231-262.]] Google ScholarDigital Library
FALOUTSOS, C., RANGANATHAN, M., AND MANOLOPOULOS, Y. 1994b. Fast subsequence matching in time-series databases. In Proc. ACM SIGMOD Int. Conf. on Management of Data, 419-429.]] Google ScholarDigital Library
FALOUTSOS, C., SELLIS,T.,AND ROUSSOPOULOS, N. 1987. Analysis of object-oriented spatial access methods. In Proc. ACM SIGMOD Int. Conf. on Management of Data.]] Google ScholarDigital Library
FINKEL,R.AND BENTLEY, J. 1974. Quad trees: A data structure for retrieval of composite trees. Acta Inf. 4, 1, 1-9.]]Google ScholarDigital Library
FREESTON, M. 1987. The bang file: A new kind of grid file. In Proc. ACM SIGMOD Int. Conf. on Management of Data (San Francisco), 260-269.]] Google ScholarDigital Library
FRIEDMAN, J., BENTLEY,J.,AND FINKEL, R. 1977. An algorithm for finding best matches in logarithmic expected time. ACMTrans. Math. Softw. 3,3, 209-226.]] Google ScholarDigital Library
GAEDE, V. 1995. Optimal redundancy in spatial database systems. In Proc. 4th Int. Symp. on Advances in Spatial Databases (Portland, ME), 96- 116.]] Google ScholarDigital Library
GAEDE,V.AND G~UNTHER, O. 1998. Multidimensional access methods. ACMComput. Surv. 30,2, 170-231.]] Google ScholarDigital Library
GIONIS, A., INDYK,P.,AND MOTWANI, R. 1999. Similarity search in high dimensions via hashing. In Proc. 25th Int. Conf. on Very Large Databases (Edinburgh), 518-529.]] Google ScholarDigital Library
GREENE, D. 1989. An implementation and performance analysis of spatial data access methods. In Proc. 5th IEEE Int. Conf. on Data Engineering.]] Google ScholarDigital Library
GUTTMAN, A. 1984. R-trees: Adynamic index structure for spatial searching. In Proc. ACM SIG-MODInt. Conf. on Management of Data (Boston), 47-57.]] Google ScholarDigital Library
HELLERSTEIN, J., KOUTSOUPIAS, E., AND PAPADIMITRIOU, C. 1997. On the analysis of indexing schemes. In Proc. 16th SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems (Tucson, AZ), 249-256.]] Google ScholarDigital Library
HELLERSTEIN, J., NAUGHTON,J.,AND PFEFFER, A. 1995. Generalized search trees for database systems. In Proc. 21st Int. Conf. on Very Large Databases (Zurich), 562-573.]] Google ScholarDigital Library
HENRICH, A. 1994. A distance-scan algorithm for spatial access strucures. In Proc. 2nd ACM Workshop on Advances in Geographic Information Systems (Gaithersburg, MD), 136-143.]]Google Scholar
HENRICH, A. 1998. The lsd h -tree: An access structure for feature vectors. In Proc. 14th Int. Conf. on Data Engineering (Orlando, FL).]] Google ScholarDigital Library
HENRICH, A., SIX, H.-W., AND WIDMAYER, P. 1989. The lsd-tree: Spatial access to multidimensional point and non-point objects. In Proc. 15th Int. Conf. on Very Large Databases (Amsterdam, The Netherlands), 45-53.]] Google ScholarDigital Library
HINNEBURG,A.AND KEIM, D. 1998. An efficient approach to clustering in large multimedia databases with noise. In Proc. Int. Conf. on Knowledge Discovery in Databases (New York).]]Google Scholar
HINRICHS, K. 1985. Implementation of the grid file: Design concepts and experience. BIT 25, 569- 592.]] Google ScholarDigital Library
HJALTASON,G.AND SAMET, H. 1995. Ranking in spatial databases. In Proc. 4th Int. Symp. on Large Spatial Databases (Portland, ME), 83-95.]] Google ScholarDigital Library
HJALTASON,G.AND SAMET, H. 1998. Incremental distance join algorithms for spatial databases. In Proc. ACM SIGMOD Int. Conf. on Management of Data, 237-248.]] Google ScholarDigital Library
HUTFLESZ, A., SIX, H.-W., AND WIDMAYER, P. 1988a. Globally order preserving multidimensional linear hashing. In Proc. 4th IEEE Int. Conf. on Data Engineering, 572-579.]] Google ScholarDigital Library
HUTFLESZ, A., SIX, H.-W., AND WIDMAYER, P. 1988b. Twin grid files: Space optimizing access schemes. In Proc. ACM SIGMOD Int. Conf. on Management of Data.]] Google ScholarDigital Library
JAGADISH, H. 1990. Linear clustering of objects with multiple attributes. In Proc. ACMSIGMOD Int. Conf. on Management of Data (Atlantic City, NJ), 332-342.]] Google ScholarDigital Library
JAGADISH, H. 1991. A retrieval technique for similar shapes. In Proc. ACM SIGMOD Int. Conf. on Management of Data, 208-217.]] Google ScholarDigital Library
JAIN,R.AND WHITE, D. 1996. Similarity indexing: Algorithms and performance. In Proc. SPIE Storage and Retrieval for Image and Video Databases IV (San Jose, CA), 62-75.]]Google Scholar
KAMEL,I.AND FALOUTSOS, C. 1992. Parallel rtrees. In Proc. ACM SIGMOD Int. Conf. on Management of Data, 195-204.]] Google ScholarDigital Library
KAMEL,I.AND FALOUTSOS, C. 1993. On packing rtrees. CIKM, 490-499.]] Google ScholarDigital Library
KAMEL,I.AND FALOUTSOS, C. 1994. Hilbert rtree: An improved r-tree using fractals. In Proc. 20th Int. Conf. on Very Large Databases, 500- 509.]] Google ScholarDigital Library
KATAYAMA,N.AND SATOH, S. 1997. The sr-tree: An index structure for high-dimensional nearest neighbor queries. In Proc. ACM SIGMOD Int. Conf. on Management of Data, 369-380.]] Google ScholarDigital Library
KNUTH, D. 1975. The Art of Computer Programming "Volume 3: Sorting and Searching. Addison-Wesley, Reading, Mass.]] Google ScholarDigital Library
KORN,F.AND MUTHUKRISHNAN, S. 2000. Influence sets based on reverse nearest neighbor queries. In Proc. ACM SIGMOD Int. Conf. on Management of Data, 201-212.]] Google ScholarDigital Library
KORN, F., SIDIROPOULOS, N., FALOUTSOS, C., SIEGEL, E., AND PROTOPAPAS, Z. 1996. Fast nearest neighbour search in medical image databases. In Proc. 22nd Int. Conf. on Very Large Databases (Mumbai, India), 215-226.]] Google ScholarDigital Library
KORNACKER, M. 1999. High-performance generalized search trees. In Proc. 24th Int. Conf. on Very Large Databases (Edinburgh).]] Google ScholarDigital Library
KRIEGEL, H.-P. AND SEEGER, B. 1986. Multidimensional order preserving linear hashing with partial extensions. In Proc. Int. Conf. on Database Theory, Lecture Notes in Computer Science, vol. 243, Springer-Verlag, New York.]] Google ScholarDigital Library
KRIEGEL, H.-P. AND SEEGER, B. 1987. Multidimensional dynamic quantile hashing is very efficient for non-uniform record distributions. In Proc. 3rd Int. Conf. on Data Engineering, 10-17.]] Google ScholarDigital Library
KRIEGEL, H.-P. AND SEEGER, B. 1988. Plophashing: A grid file without directory. In Proc. 4th Int. Conf. on Data Engineering, 369-376.]] Google ScholarDigital Library
KRISHNAMURTHY,R.AND WHANG, K.-Y. 1985. Multilevel Grid Files. IBM Research Center Report, Yorktown Heights, NY.]]Google Scholar
KUKICH, K. 1992. Techniques for automatically correcting words in text. ACM Comput. Surv. 24, 4, 377-440.]] Google ScholarDigital Library
LIN, K., JAGADISH, H., AND FALOUTSOS, C. 1995. The tv-tree: An index structure for high-dimensional data. VLDB J. 3, 517-542.]] Google ScholarDigital Library
LOMET,D.AND SALZBERG, B. 1989. The hb-tree: A robust multiattribute search structure. In Proc. 5th IEEE Int. Conf. on Data Engineering, 296- 304.]] Google ScholarDigital Library
LOMET,D.AND SALZBERG, B. 1990. The hb-tree: A multiattribute indexing method with good guaranteed performance. ACM Trans. Database Syst. 15, 4, 625-658.]] Google ScholarDigital Library
MANDELBROT, B. 1977. Fractal Geometry of Nature. W.H. Freeman, New York.]]Google Scholar
MEHROTRA,R.AND GARY, J. 1993. Feature-based retrieval of similar shapes. In Proc. 9th Int. Conf. on Data Engineering.]] Google ScholarDigital Library
MEHROTRA,R.AND GARY, J. 1995. Feature-indexbased similar shape retrieval. In Proc. 3rd Working Conf. on Visual Database Systems.]] Google ScholarDigital Library
MORTON, G. 1966. A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing. IBM Ltd., USA.]]Google Scholar
MUMFORD, D. 1987. The problem of robust shape descriptors. In Proc. 1st IEEE Int. Conf. on Computer Vision.]]Google Scholar
NIEVERGELT, J., HINTERBERGER, H., AND SEVCIK,K. 1984. The grid file: An adaptable, symmetric multikey file structure. ACM Trans. Database Syst. 9, 1, 38-71.]] Google ScholarDigital Library
ORENSTEIN, J. 1990. A comparison of spatial query processing techniques for native and parameter spaces. In Proc. ACM SIGMOD Int. Conf. on Management of Data, 326-336.]] Google ScholarDigital Library
ORENSTEIN,J.AND MERRET, T. 1984. A class of data structures for associative searching. In Proc. 3rd ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, 181-190.]] Google ScholarDigital Library
OTOO, E. 1984. A mapping function for the directory of a multidimensional extendible hashing. In Proc. 10th Int. Conf. on Very Large Databases, 493-506.]] Google ScholarDigital Library
OUKSEL, M. 1985. The interpolation based grid file. In Proc. 4th ACM SIGACT-SIGMOD Symp. on Principles of Database Systems, 20-27.]] Google ScholarDigital Library
OUSKEL,A.AND MAYES, O. 1992. The nested interpolation-based Grid File. Acta Informatika 29, 335-373.]] Google ScholarDigital Library
PAGEL, B.-U., SIX, H.-W., TOBEN, H., AND WIDMAYER, P. 1993. Towards an analysis of range query performance in spatial data structures. In Proc. 12th ACMSIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems (Washington, DC), 214-221.]] Google ScholarDigital Library
PAPADOPOULOS,A.AND MANOLOPOULOS, Y. 1997a. Nearest neighbor queries in shared-nothing environments. Geoinf. 1, 1, 1-26.]] Google ScholarDigital Library
PAPADOPOULOS,A.AND MANOLOPOULOS, Y. 1997b. Performance of nearest neighbor queries in r-trees. In Proc. 6th Int. Conf. on Database Theory, Lecture Notes in Computer Science, vol. 1186, Springer-Verlag, New York, 394-408.]] Google ScholarDigital Library
PAPADOPOULOS,A.AND MANOLOPOULOS, Y. 1998. Similarity query processing using disk arrays. In Proc. ACM SIGMOD Int. Conf. on Management of Data.]] Google ScholarDigital Library
RIEDEL, E., GIBSON,G.,AND FALOUTSOS, C. 1998. Actice storage for large-scale data mining and multimedia. In Proc. 24th Int. Conf. on Very Large Databases, 62-73.]] Google ScholarDigital Library
ROBINSON, J. 1981. The k-d-b-tree: A search structure for large multidimensional dynamic indexes. In Proc. ACMSIGMOD Int. Conf. on Management of Data, 10-18.]] Google ScholarDigital Library
ROUSSOPOULOS, N., KELLEY,S.,AND VINCENT, F. 1995. Nearest neighbor queries. In Proc. ACM SIG-MOD Int. Conf. on Management of Data, 71-79.]] Google ScholarDigital Library
SAGAN, H. 1994. Space Filling Curves. Springer- Verlag, New York.]]Google Scholar
SCHR~ODER, M. 1991. Fractals, Chaos, Power Laws: Minutes from an Infinite Paradise. W.H. Freeman, New York.]]Google Scholar
SEEGER,B.AND KRIEGEL, H.-P. 1990. The buddy tree: An efficient and robust access method for spatial data base systems. In Proc. 16th Int. Conf. on Very Large Databases (Brisbane), 590- 601.]] Google ScholarDigital Library
SEIDL, T. 1997. Adaptable similarity search in 3-d spatial database systems. PhD thesis, University of Munich, Germany.]]Google Scholar
SEIDL,T.AND KRIEGEL, H.-P. 1997. Efficient useradaptable similarity search in large multimedia databases. In Proc. 23rd Int. Conf. on Very Large Databases (Athens).]] Google ScholarDigital Library
SELLIS, T., ROUSSOPOULOS,N.,AND FALOUTSOS,C. 1987. The rC-tree: A dynamic index for multidimensional objects. In Proc. 13th Int. Conf. on Very Large Databases (Brighton, GB), 507-518.]] Google ScholarDigital Library
SHAWNEY,H.AND HAFNER, J. 1994. Efficient color histogram indexing. In Proc. Int. Conf. on Image Processing, 66-70.]]Google ScholarCross Ref
SHOICHET, B., BODIAN,D.,AND KUNTZ, I. 1992. Molecular docking using shape descriptors. J. Comput. Chem. 13, 3, 380-397.]] Google ScholarDigital Library
SPROULL, R. 1991. Refinements to nearest neighbor searching in k-dimensional trees. Algorithmica, 579-589.]]Google ScholarDigital Library
STANOI, I., AGRAWAL,D.,AND ABBADI, A. 2000. Reverse nearest neighbor queries for dynamic databases. In Proc. ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 44-53.]]Google Scholar
STONEBRAKER, M., SELLIS,T.,AND HANSON, E. 1986. An analysis of rule indexing implementations in data base systems. In Proc. Int. Conf. on Expert Database Systems.]]Google Scholar
THEODORIDIS,Y.AND SELLIS, T. 1996. A model for the prediction of r-tree performance. In Proc. 15th ACMSIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems (Montreal), 161- 171.]] Google ScholarDigital Library
UHLMANN, J. 1991. Satisfying general proximity/ similarity queries with metric trees. Inf. Proc. Lett. 145-157.]]Google Scholar
VAN DEN BERCKEN, J., SEEGER,B.,AND WIDMAYER, P. 1997. A general approach to bulk loading multidimensional index structures. In Proc. 23rd Int. Conf. on Very Large Databases (Athens).]] Google ScholarDigital Library
WALLACE,T.AND WINTZ, P. 1980. An efficient threedimensional aircraft recognition algorithm using normalized Fourier descriptors. Comput. Graph. Image Proc. 13, 99-126.]]Google ScholarCross Ref
WEBER, R., SCHEK, H.-J., AND BLOTT, S. 1998. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In Proc. Int. Conf. on Very Large Databases (New York).]] Google ScholarDigital Library
WHITE,D.AND JAIN, R. 1996. Similarity indexing with the ss-tree. In Proc. 12th Int. Conf. on Data Engineering (New Orleans).]] Google ScholarDigital Library
YAO,A.AND YAO, F. 1985. A general approach to d-dimensional geometric queries. In Proc. ACM Symp. on Theory of Computing.]] Google ScholarDigital Library
YIANILOS, P. 1993. Data structures and algorithms for nearest neighbor search in general metric spaces. In Proc. 4th ACM-SIAM Symp. on Discrete Algorithms, 311-321.]] Google ScholarDigital Library
YIANILOS, P. 1999. Excluded middle vantage point forests for nearest neighbor search. In Proc. DIMACS Implementation Challenge (Baltimore, MD).]]Google Scholar

Index Terms

Recommendations

MKL-tree: an index structure for high-dimensional vector spaces
Abstract
In this work, a novel hierarchical data structure for high dimensional data indexing is proposed. MKL-tree is based on dimensionality reduction operated by means of the MKL transform, a multi-space generalization of the KL transform. A local ...
Read More
Efficient Near Neighbor Searching Using Multi-Indexes for Content-Based Multimedia Data Retrieval

Many content-based multimedia data retrieval problems can be transformed into the near neighbor searching problem in multidimensional feature space. An efficient near neighbor searching algorithm is needed when developing a multimedia database system. ...
Read More
Efficient k-nearest neighbor searching in nonordered discrete data spaces

Numerous techniques have been proposed in the past for supporting efficient k-nearest neighbor (k-NN) queries in continuous data spaces. Limited work has been reported in the literature for k-NN queries in a nonordered discrete data space (NDDS). ...
Read More

Comments

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Published in

ACM Computing Surveys Volume 33, Issue 3
September 2001
153 pages
ISSN:0360-0300
EISSN:1557-7341
DOI:10.1145/502807
Issue’s Table of Contents

Copyright © 2001 ACM
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
- Published: 1 September 2001
Published in csur Volume 33, Issue 3

Permissions
Request permissions about this article.
Request Permissions

Check for updates
Author Tags
Index structures
indexing high-dimensional data
multimedia databases
similarity search
Qualifiers
- article
Conference
Funding Sources
Other Metrics
View Article Metrics

Article Metrics
- 630
  Total Citations
  View Citations
- 8,070
  Total Downloads
- Downloads (Last 12 months)108
- Downloads (Last 6 weeks)15
Other Metrics
View Author Metrics
Cited By
View all

PDF Format

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases

ACM Computing Surveys

Abstract

References

Cited By

Index Terms

Recommendations

MKL-tree: an index structure for high-dimensional vector spaces

Efficient Near Neighbor Searching Using Multi-Indexes for Content-Based Multimedia Data Retrieval

Efficient k-nearest neighbor searching in nonordered discrete data spaces

Comments

Login options

Full Access

Published in

Sponsors

In-Cooperation

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Funding Sources

Other Metrics

Article Metrics

Other Metrics

Cited By

PDF Format

eReader

Digital Edition

Caption

Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases

ACM Computing Surveys

Abstract

References

Cited By

Index Terms

Recommendations

MKL-tree: an index structure for high-dimensional vector spaces

Efficient Near Neighbor Searching Using Multi-Indexes for Content-Based Multimedia Data Retrieval

Efficient k-nearest neighbor searching in nonordered discrete data spaces

Comments

Login options

Full Access

Published in

Sponsors

In-Cooperation

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Funding Sources

Article Metrics

Other Metrics

PDF Format

eReader

Digital Edition

Share this Publication link

Share on Social Media