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

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

• 1: 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.
• 2: Rakesh Agrawal , Christos Faloutsos , Arun N. Swami, Efficient Similarity Search In Sequence Databases, Proceedings of the 4th International Conference on Foundations of Data Organization and Algorithms, p.69-84, October 13-15, 1993
• 3: Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.94-105, June 01-04, 1998, Seattle, Washington, United States
• 4: Rakesh Agrawal , King-Ip Lin , Harpreet S. Sawhney , Kyuseok Shim, Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.490-501, September 11-15, 1995
• 5: 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.
• 6: Paul M. Aoki, Generalizing "Search'' in Generalized Search Trees (Extended Abstract), Proceedings of the Fourteenth International Conference on Data Engineering, p.380-389, February 23-27, 1998
• 7: Walid G. Aref , Hanan Samet, Optimization for Spatial Query Processing, Proceedings of the 17th International Conference on Very Large Data Bases, p.81-90, September 03-06, 1991
• 8: Sunil Arya, Nearest neighbor searching and applications, University of Maryland at College Park, College Park, MD, 1996
• 9: Sunil Arya , David M. Mount , Onuttom Narayan, Accounting for boundary effects in nearest neighbor searching, Proceedings of the eleventh annual symposium on Computational geometry, p.336-344, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220315]
• 10: Ricardo A. Baeza-Yates , Walter Cunto , Udi Manber , Sun Wu, Proximity Matching Using Fixed-Queries Trees, Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching, p.198-212, June 05-08, 1994
• 11: BAYER,R.AND MCCREIGHT, E. 1977. Organization and maintenance of large ordered indices. Acta Inf. 1, 3, 173-189.
• 12: Norbert Beckmann , Hans-Peter Kriegel , Ralf Schneider , Bernhard Seeger, The R*-tree: an efficient and robust access method for points and rectangles, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.322-331, May 23-26, 1990, Atlantic City, New Jersey, United States
• 13: Alberto Belussi , Christos Faloutsos, Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension, Proceedings of the 21th International Conference on Very Large Data Bases, p.299-310, September 11-15, 1995
• 14: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 15: BENTLEY, J. 1979. Multidimensional binary search in database applications. IEEE Trans. Softw. Eng. 4, 5, 397-409.
• 16: Stefan Berchtold , Daniel A. Keim, High-dimensional index structures database support for next decade's applications (tutorial), Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.501, June 01-04, 1998, Seattle, Washington, United States
• 17: Stefan Berchtold , Christian Böhm , Bernhard Braunmüller , Daniel A. Keim , Hans-Peter Kriegel, Fast parallel similarity search in multimedia databases, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.1-12, May 11-15, 1997, Tucson, Arizona, United States
• 18: 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.
• 19: Stefan Berchtold , Christian Böhm , Daniel A. Keim , Hans-Peter Kriegel, A cost model for nearest neighbor search in high-dimensional data space, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.78-86, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263671]
• 20: Stefan Berchtold , Christian Böhm , Daniel A. Keim , Florian Krebs , Hans-Peter Kriegel, On Optimizing Nearest Neighbor Queries in High-Dimensional Data Spaces, Proceedings of the 8th International Conference on Database Theory, p.435-449, January 04-06, 2001
• 21: Stefan Berchtold , Christian Böhm , Daniel A. Keim , Hans-Peter Kriegel , Xiaowei Xu, Optimal Multidimensional Query Processing Using Tree Striping, Proceedings of the Second International Conference on Data Warehousing and Knowledge Discovery, p.244-257, September 04-06, 2000
• 22: Stefan Berchtold , Christian Böhm , Hans-Peter Kriegel, Improving the Query Performance of High-Dimensional Index Structures by Bulk-Load Operations, Proceedings of the 6th International Conference on Extending Database Technology: Advances in Database Technology, p.216-230, March 23-27, 1998
• 23: Stefan Berchtold , Christian Böhm , Hans-Peter Kriegal, The pyramid-technique: towards breaking the curse of dimensionality, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.142-153, June 01-04, 1998, Seattle, Washington, United States
• 24: Stefan Berchtold , Bernhard Ertl , Daniel A. Keim , Hans-Peter Kriegel , Thomas Seidl, Fast Nearest Neighbor Search in High-Dimensional Space, Proceedings of the Fourteenth International Conference on Data Engineering, p.209-218, February 23-27, 1998
• 25: 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.
• 26: Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel, The X-tree: An Index Structure for High-Dimensional Data, Proceedings of the 22th International Conference on Very Large Data Bases, p.28-39, September 03-06, 1996
• 27: Stefan Berchtold , Daniel A. Keim , Hans-Peter Kriegel , Thomas Seidl, Indexing the Solution Space: A New Technique for Nearest Neighbor Search in High-Dimensional Space, IEEE Transactions on Knowledge and Data Engineering, v.12 n.1, p.45-57, January 2000 [doi>10.1109/69.842249]
• 28: Kevin S. Beyer , Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, When Is ''Nearest Neighbor'' Meaningful?, Proceeding of the 7th International Conference on Database Theory, p.217-235, January 10-12, 1999
• 29: B~OHM, C. 1998. Efficiently indexing highdimensional databases. PhD thesis, University of Munich, Germany.
• 30: Christian Böhm, A cost model for query processing in high dimensional data spaces, ACM Transactions on Database Systems (TODS), v.25 n.2, p.129-178, June 2000 [doi>10.1145/357775.357776]
• 31: Tolga Bozkaya , Meral Ozsoyoglu, Distance-based indexing for high-dimensional metric spaces, ACM SIGMOD Record, v.26 n.2, p.357-368, June 1997
• 32: Sergey Brin, Near Neighbor Search in Large Metric Spaces, Proceedings of the 21th International Conference on Very Large Data Bases, p.574-584, September 11-15, 1995
• 33: W. A. Burkhard , R. M. Keller, Some approaches to best-match file searching, Communications of the ACM, v.16 n.4, p.230-236, April 1973 [doi>10.1145/362003.362025]
• 34: King Lum Cheung , Ada Wai-Chee Fu, Enhanced nearest neighbour search on the R-tree, ACM SIGMOD Record, v.27 n.3, p.16-21, Sept. 1, 1998 [doi>10.1145/290593.290596]
• 35: Tzi-cker Chiueh, Content-Based Image Indexing, Proceedings of the 20th International Conference on Very Large Data Bases, p.582-593, September 12-15, 1994
• 36: Paolo Ciaccia , Marco Patella , Pavel Zezula, M-tree: An Efficient Access Method for Similarity Search in Metric Spaces, Proceedings of the 23rd International Conference on Very Large Data Bases, p.426-435, August 25-29, 1997
• 37: Paolo Ciaccia , Marco Patella , Pavel Zezula, A cost model for similarity queries in metric spaces, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.59-68, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275495]
• 38: John Gerald Cleary, Analysis of an Algorithm for Finding Nearest Neighbors in Euclidean Space, ACM Transactions on Mathematical Software (TOMS), v.5 n.2, p.183-192, June 1979 [doi>10.1145/355826.355832]
• 39: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 40: Antonio Corral , Yannis Manolopoulos , Yannis Theodoridis , Michael Vassilakopoulos, Closest pair queries in spatial databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.189-200, May 15-18, 2000, Dallas, Texas, United States
• 41: EASTMAN, C. 1981. Optimal bucket size for nearest neighbor searching in kd-trees. Inf. Proc. Lett. 12,4.
• 42: EVANGELIDIS, G. 1994. The hB -tree: A concurrent and recoverable multi-attribute index structure. PhD thesis, Northeastern University, Boston, MA.
• 43: Georgios Evangelidis , David Lomet , Betty Salzberg, The hB $^\Pi$-tree: a multi-attribute index supporting concurrency, recovery and node consolidation, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.1, p.1-25, February 1997 [doi>10.1007/s007780050030]
• 44: Christos Faloutsos, Multiattribute hashing using Gray codes, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.227-238, May 28-30, 1986, Washington, D.C., United States
• 45: C. Faloutsos, Gray Codes for Partial Match and Range Queries, IEEE Transactions on Software Engineering, v.14 n.10, p.1381-1393, October 1988 [doi>10.1109/32.6184]
• 46: Christos Faloutsos , Volker Gaede, Analysis of n-Dimensional Quadtrees using the Hausdorff Fractal Dimension, Proceedings of the 22th International Conference on Very Large Data Bases, p.40-50, September 03-06, 1996
• 47: Christos Faloutsos , Ibrahim Kamel, Beyond uniformity and independence: analysis of R-trees using the concept of fractal dimension, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.4-13, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182593]
• 48: Christos Faloutsos , King-Ip Lin, FastMap: a fast algorithm for indexing, data-mining and visualization of traditional and multimedia datasets, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.163-174, May 22-25, 1995, San Jose, California, United States
• 49: C. Faloutsos , S. Roseman, Fractals for secondary key retrieval, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.247-252, March 1989, Philadelphia, Pennsylvania, United States [doi>10.1145/73721.73746]
• 50: C. Faloutsos , R. Barber , M. Flickner , J. Hafner , W. Niblack , D. Petkovic , W. Equitz, Efficient and effective querying by image content, Journal of Intelligent Information Systems, v.3 n.3-4, p.231-262, July 1994 [doi>10.1007/BF00962238]
• 51: Christos Faloutsos , M. Ranganathan , Yannis Manolopoulos, Fast subsequence matching in time-series databases, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.419-429, May 24-27, 1994, Minneapolis, Minnesota, United States
• 52: Christos Faloutsos , Timos Sellis , Nick Roussopoulos, Analysis of object oriented spatial access methods, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.426-439, May 27-29, 1987, San Francisco, California, United States
• 53: FINKEL,R.AND BENTLEY, J. 1974. Quad trees: A data structure for retrieval of composite trees. Acta Inf. 4, 1, 1-9.
• 54: Michael Freeston, The BANG file: A new kind of grid file, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.260-269, May 27-29, 1987, San Francisco, California, United States
• 55: Jerome H. Freidman , Jon Louis Bentley , Raphael Ari Finkel, An Algorithm for Finding Best Matches in Logarithmic Expected Time, ACM Transactions on Mathematical Software (TOMS), v.3 n.3, p.209-226, Sept. 1977 [doi>10.1145/355744.355745]
• 56: Volker Gaede, Optimal Redundancy in Spatial Database Systems, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.96-116, August 06-09, 1995
• 57: Volker Gaede , Oliver Günther, Multidimensional access methods, ACM Computing Surveys (CSUR), v.30 n.2, p.170-231, June 1998 [doi>10.1145/280277.280279]
• 58: Aristides Gionis , Piotr Indyk , Rajeev Motwani, Similarity Search in High Dimensions via Hashing, Proceedings of the 25th International Conference on Very Large Data Bases, p.518-529, September 07-10, 1999
• 59: Diane Greene, An Implementation and Performance Analysis of Spatial Data Access Methods, Proceedings of the Fifth International Conference on Data Engineering, p.606-615, February 06-10, 1989
• 60: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 61: Joseph M. Hellerstein , Elias Koutsoupias , Christos H. Papadimitriou, On the analysis of indexing schemes, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.249-256, May 11-15, 1997, Tucson, Arizona, United States [doi>10.1145/263661.263688]
• 62: Joseph M. Hellerstein , Jeffrey F. Naughton , Avi Pfeffer, Generalized Search Trees for Database Systems, Proceedings of the 21th International Conference on Very Large Data Bases, p.562-573, September 11-15, 1995
• 63: 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.
• 64: Andreas Henrich, The LSDh-Tree: An Access Structure for Feature Vectors, Proceedings of the Fourteenth International Conference on Data Engineering, p.362-369, February 23-27, 1998
• 65: A. Henrich , H. -W. Six , P. Widmayer, The LSD tree: spatial access to multidimensional and non-point objects, Proceedings of the 15th international conference on Very large data bases, p.45-53, July 1989, Amsterdam, The Netherlands
• 66: 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).
• 67: Klaus Hinrichs, Implementation of the grid file: design concepts and experience, BIT, v.25 n.4, p.569-592, 1985 [doi>10.1007/BF01936137]
• 68: Gisli R. Hjaltason , Hanan Samet, Ranking in Spatial Databases, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.83-95, August 06-09, 1995
• 69: Gísli R. Hjaltason , Hanan Samet, Incremental distance join algorithms for spatial databases, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.237-248, June 01-04, 1998, Seattle, Washington, United States
• 70: Andreas Hutflesz , Hans-Werner Six , Peter Widmayer, Globally Order Preserving Multidimensional Linear Hashing, Proceedings of the Fourth International Conference on Data Engineering, p.572-579, February 01-05, 1988
• 71: Andreas Hutflesz , Hans-Werner Six , Peter Widmayer, Twin grid files: space optimizing access schemes, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.183-190, June 01-03, 1988, Chicago, Illinois, United States
• 72: H. V. Jagadish, Linear clustering of objects with multiple attributes, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.332-342, May 23-26, 1990, Atlantic City, New Jersey, United States
• 73: H. V. Jagadish, A retrieval technique for similar shapes, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.208-217, May 29-31, 1991, Denver, Colorado, United States
• 74: 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.
• 75: Ibrahim Kamel , Christos Faloutsos, Parallel R-trees, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.195-204, June 02-05, 1992, San Diego, California, United States
• 76: Ibrahim Kamel , Christos Faloutsos, On packing R-trees, Proceedings of the second international conference on Information and knowledge management, p.490-499, November 01-05, 1993, Washington, D.C., United States [doi>10.1145/170088.170403]
• 77: Ibrahim Kamel , Christos Faloutsos, Hilbert R-tree: An Improved R-tree using Fractals, Proceedings of the 20th International Conference on Very Large Data Bases, p.500-509, September 12-15, 1994
• 78: Norio Katayama , Shin'ichi Satoh, The SR-tree: an index structure for high-dimensional nearest neighbor queries, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.369-380, May 11-15, 1997, Tucson, Arizona, United States
• 79: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 80: Flip Korn , S. Muthukrishnan, Influence sets based on reverse nearest neighbor queries, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.201-212, May 15-18, 2000, Dallas, Texas, United States
• 81: Flip Korn , Nikolaos Sidiropoulos , Christos Faloutsos , Eliot Siegel , Zenon Protopapas, Fast Nearest Neighbor Search in Medical Image Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.215-226, September 03-06, 1996
• 82: Marcel Kornacker, High-Performance Extensible Indexing, Proceedings of the 25th International Conference on Very Large Data Bases, p.699-708, September 07-10, 1999
• 83: Hans-Peter Kriegel , Bernhard Seeger, Multidimensional order preserving linear hashing with partial expansions, Proceedings on International conference on database theory, p.203-220, December 1986, Rome, Italy
• 84: Hans-Peter Kriegel , Bernhard Seeger, Multidimensional Dynamic Quantile Hashing is Very Efficient for Non-Uniform Record Distributions, Proceedings of the Third International Conference on Data Engineering, p.10-17, February 03-05, 1987
• 85: Hans-Peter Kriegel , Bernhard Seeger, PLOP-Hashing: A Grid File without Directory, Proceedings of the Fourth International Conference on Data Engineering, p.369-376, February 01-05, 1988
• 86: KRISHNAMURTHY,R.AND WHANG, K.-Y. 1985. Multilevel Grid Files. IBM Research Center Report, Yorktown Heights, NY.
• 87: Karen Kukich, Technique for automatically correcting words in text, ACM Computing Surveys (CSUR), v.24 n.4, p.377-439, Dec. 1992 [doi>10.1145/146370.146380]
• 88: King Ip Lin , H. V. Jagadish , Christos Faloutsos, The TV-tree: an index structure for high-dimensional data, The VLDB Journal — The International Journal on Very Large Data Bases, v.3 n.4, October 1994
• 89: David B. Lomet , Betty Salzberg, A Robust Multi-Attribute Search Structure, Proceedings of the Fifth International Conference on Data Engineering, p.296-304, February 06-10, 1989
• 90: David B. Lomet , Betty Salzberg, The hB-tree: a multiattribute indexing method with good guaranteed performance, ACM Transactions on Database Systems (TODS), v.15 n.4, p.625-658, Dec. 1990 [doi>10.1145/99935.99949]
• 91: MANDELBROT, B. 1977. Fractal Geometry of Nature. W.H. Freeman, New York.
• 92: Rajiv Mehrotra , James E. Gary, Feature-Based Retrieval of Similar Shapes, Proceedings of the Ninth International Conference on Data Engineering, p.108-115, April 19-23, 1993
• 93: R. Mehrotra , J. Gary, Feature-index-based similar shape retrieval, Proceedings of the third IFIP WG2.6 working conference on Visual database systems 3 (VDB-3), p.46-65, June 1997
• 94: MORTON, G. 1966. A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing. IBM Ltd., USA.
• 95: MUMFORD, D. 1987. The problem of robust shape descriptors. In Proc. 1st IEEE Int. Conf. on Computer Vision.
• 96: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 97: Jack Orenstein, A comparison of spatial query processing techniques for native and parameter spaces, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.343-352, May 23-26, 1990, Atlantic City, New Jersey, United States
• 98: J. A. Orenstein , T. H. Merrett, A class of data structures for associative searching, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588037]
• 99: Ekow J. Otoo, A Mapping Function for the Directory of a Multidimensional Extendible Hashing, Proceedings of the 10th International Conference on Very Large Data Bases, p.493-506, August 27-31, 1984
• 100: M. Aris Ouksel, The interpolation-based grid file, Proceedings of the fourth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.20-27, March 25-27, 1985, Portland, Oregon, United States [doi>10.1145/325405.325408]
• 101: M. Aris Ouksel , Otto Mayer, A robust and efficient spatial data structure: the nested interpolation-based grid file, Acta Informatica, v.29 n.4, p.335-373, July 1992 [doi>10.1007/BF01178777]
• 102: Bernd-Uwe Pagel , Hans-Werner Six , Heinrich Toben , Peter Widmayer, Towards an analysis of range query performance in spatial data structures, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.214-221, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153878]
• 103: Apostolos Papadopoulos , Yannis Manolopoulos, Nearest Neighbor Queries in Shared-Nothing Environments, Geoinformatica, v.1 n.4, p.369-392, December 1997 [doi>10.1023/A:1009758427967]
• 104: Apostolos Papadopoulos , Yannis Manolopoulos, Performance of Nearest Neighbor Queries in R-Trees, Proceedings of the 6th International Conference on Database Theory, p.394-408, January 08-10, 1997
• 105: Apostolos N. Papadopoulos , Yannis Manolopoulos, Similarity query processing using disk arrays, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.225-236, June 01-04, 1998, Seattle, Washington, United States
• 106: Erik Riedel , Garth A. Gibson , Christos Faloutsos, Active Storage for Large-Scale Data Mining and Multimedia, Proceedings of the 24rd International Conference on Very Large Data Bases, p.62-73, August 24-27, 1998
• 107: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 108: Nick Roussopoulos , Stephen Kelley , Frédéric Vincent, Nearest neighbor queries, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.71-79, May 22-25, 1995, San Jose, California, United States
• 109: SAGAN, H. 1994. Space Filling Curves. Springer- Verlag, New York.
• 110: SCHR~ODER, M. 1991. Fractals, Chaos, Power Laws: Minutes from an Infinite Paradise. W.H. Freeman, New York.
• 111: Bernhard Seeger , Hans-Peter Kriegel, The buddy tree: an efficient and robust access method for spatial data base, Proceedings of the sixteenth international conference on Very large databases, p.590-601, September 1990, Brisbane, Australia
• 112: SEIDL, T. 1997. Adaptable similarity search in 3-d spatial database systems. PhD thesis, University of Munich, Germany.
• 113: Thomas Seidl , Hans-Peter Kriegel, Efficient User-Adaptable Similarity Search in Large Multimedia Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.506-515, August 25-29, 1997
• 114: Timos K. Sellis , Nick Roussopoulos , Christos Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, Proceedings of the 13th International Conference on Very Large Data Bases, p.507-518, September 01-04, 1987
• 115: SHAWNEY,H.AND HAFNER, J. 1994. Efficient color histogram indexing. In Proc. Int. Conf. on Image Processing, 66-70.
• 116: Brian K. Shoichet , Dale L. Bodian , Irwin D. Kuntz, Molecular docking using shape descriptors, Journal of Computational Chemistry, v.13 n.3, p.380-397, April, 1992 [doi>10.1002/jcc.540130311]
• 117: SPROULL, R. 1991. Refinements to nearest neighbor searching in k-dimensional trees. Algorithmica, 579-589.
• 118: 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.
• 119: 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.
• 120: Yannis Theodoridis , Timos Sellis, A model for the prediction of R-tree performance, Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.161-171, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237705]
• 121: UHLMANN, J. 1991. Satisfying general proximity/ similarity queries with metric trees. Inf. Proc. Lett. 145-157.
• 122: Jochen Van den Bercken , Bernhard Seeger , Peter Widmayer, A Generic Approach to Bulk Loading Multidimensional Index Structures, Proceedings of the 23rd International Conference on Very Large Data Bases, p.406-415, August 25-29, 1997
• 123: WALLACE,T.AND WINTZ, P. 1980. An efficient threedimensional aircraft recognition algorithm using normalized Fourier descriptors. Comput. Graph. Image Proc. 13, 99-126.
• 124: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 125: David A. White , Ramesh Jain, Similarity Indexing with the SS-tree, Proceedings of the Twelfth International Conference on Data Engineering, p.516-523, February 26-March 01, 1996
• 126: A C Yao , F F Yao, A general approach to d-dimensional geometric queries, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.163-168, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22163]
• 127: Peter N. Yianilos, Data structures and algorithms for nearest neighbor search in general metric spaces, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.311-321, January 25-27, 1993, Austin, Texas, United States
• 128: YIANILOS, P. 1999. Excluded middle vantage point forests for nearest neighbor search. In Proc. DIMACS Implementation Challenge (Baltimore, MD).

INDEX TERMS

Primary Classification:
  A. General Literature
  A.1 INTRODUCTORY AND SURVEY

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.2 DISCRETE MATHEMATICS

  H. Information Systems
  H.2 DATABASE MANAGEMENT
  H.3 INFORMATION STORAGE AND RETRIEVAL
  H.4 INFORMATION SYSTEMS APPLICATIONS

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
Index structures, indexing high-dimensional data, multimedia databases, similarity search