A cost model for nearest neighbor search in high-dimensional data space

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A cost model for nearest neighbor search in high-dimensional data space

Full text

Pdf (1.21 MB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems table of contents

Tucson, Arizona, United States

Pages: 78 - 86

Year of Publication: 1997

ISBN:0-89791-910-6

Authors

Stefan Berchtold	University of Munich, Germany
Christian Böhm	University of Munich, Germany
Daniel A. Keim	University of Munich, Germany
Hans-Peter Kriegel	University of Munich, Germany

Sponsor

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 120, Citation Count: 91

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/263661.263671 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Altschul S. F., Gish W., Miller W., Myers E. W., Lipman D. J.: 'A Basic Local Alignment Search Tool', Journal of Molecular Biology, Vol. 215, No. 3, 1990, pp. 403-410.
	2	Sunil Arya, Nearest neighbor searching and applications, University of Maryland at College Park, College Park, MD, 1996
	3	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]
	4	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
	5	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
	6	Berehtold S., Keim D., Kriegel H.-P.: 'Fast Searching for Partial Similarity in Polygon Databases', accepted for publication: V LDB Journal, 1996.
	7	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]
	8	Eastman C.M.: 'Optimal Bucket Size for Nearest Neighbor Searching in k-d Trees', Information Processing Letters Vol. 12, No. 4, 1981.
	9	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]
	10	Faloutsos C., Gaede V.: 'Analysis of n-Dimensional Quadtrees Using the Hausdorff Fraetal Dimension', Proe. ACM SIGMOD Int. Conf. on Management of Data, 1996.
	11	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]
	12	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]
	13	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
	14	Malvin H. Kalos , Paula A. Whitlock, Monte Carlo methods. Vol. 1: basics, Wiley-Interscience, New York, NY, 1986
	15	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]
	16	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
	17	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
	18	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
	19	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
	20	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	21	Ramasubramanian V., Paliwal K. K.: 'Fast k-Dimensional Tree Algorithms for Nearest Neighbor Search with Application to Vector Quantization Encoding', IEEE Transactions on Signal Processing, Vol, 40, No. 3, March 1992, pp. 518-531.
	22	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
	23	Shawney H., Hafner L" 'Efficient Color Histogram Indexing', Proe. Int. Conf. on Image Processing, 1994, pp. 66-70.
	24	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]
	25	Sproull R.E: 'Refinements to Nearest Neighbor Searching in k-Dimensional Trees', Algorithmiea 1991, pp, 579-589.
	26	Wallace T., Wintz P.: 'An Efficient Three-Dimensional Aircraft Recognition Algorithm Using Normalized Fourier Descriptors', Computer Graphics and Image Processing, Vol. 13, pp. 99-126, 1980.
	27	T. A. Welch, BOUNDS ON INFORMATION RETRIEVAL EFFICIENCY IN STATIC FILE STRUCTURES., Massachusetts Institute of Technology, Cambridge, MA, 1971
	28	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]

CITED BY 91

	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
	Yasushi Sakurai , Masatoshi Yoshikawa , Shunsuke Uemura , Haruhiko Kojima, The subspace coding method: a new indexing scheme for high-dimensional data, Proceedings of the ninth international conference on Information and knowledge management, p.210-218, November 06-11, 2000, McLean, Virginia, United States
	Yufei Tao , Dimitris Papadias, Time-parameterized queries in spatio-temporal databases, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin
	Thomas Seidl , Hans-Peter Kriegel, Optimal multi-step k-nearest neighbor search, ACM SIGMOD Record, v.27 n.2, p.154-165, June 1998
	Apostolos N. Papadopoulos , Yannis Manolopoulos, Similarity query processing using disk arrays, ACM SIGMOD Record, v.27 n.2, p.225-236, June 1998
	Jae-Woo Chang , Du-Seok Jin, A new cell-based clustering method for large, high-dimensional data in data mining applications, Proceedings of the 2002 ACM symposium on Applied computing, March 11-14, 2002, Madrid, Spain
	Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic subspace clustering of high dimensional data for data mining applications, ACM SIGMOD Record, v.27 n.2, p.94-105, June 1998
	Pankaj K. Agarwal , Lars Arge , Jeff Erickson , Paolo G. Franciosa , Jeffry Scott Vitter, Efficient searching with linear constraints, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.169-178, June 01-04, 1998, Seattle, Washington, United States
	Tolga Bozkaya , Meral Ozsoyoglu, Indexing large metric spaces for similarity search queries, ACM Transactions on Database Systems (TODS), v.24 n.3, p.361-404, Sept. 1999
	Changzhou Wang , X. Sean Wang, Supporting subseries nearest neighbor search via approximation, Proceedings of the ninth international conference on Information and knowledge management, p.314-321, November 06-11, 2000, McLean, Virginia, United States
	Alexander Thomasian , Vittorio Castelli , Chung-Sheng Li, Clustering and singular value decomposition for approximate indexing in high dimensional spaces, Proceedings of the seventh international conference on Information and knowledge management, p.201-207, November 02-07, 1998, Bethesda, Maryland, United States
	Sang-Wook Kim , Charu C. Aggarwal , Philip S. Yu, Effective nearest neighbor indexing with the euclidean metric, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA
	Kaushik Chakrabarti , Sharad Mehrotra, Efficient concurrency control in multidimensional access methods, ACM SIGMOD Record, v.28 n.2, p.25-36, June 1999
	Christian Böhm , Stefan Berchtold , Daniel A. Keim, Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases, ACM Computing Surveys (CSUR), v.33 n.3, p.322-373, September 2001
	Jens-Peter Dittrich , Bernhard Seeger, GESS: a scalable similarity-join algorithm for mining large data sets in high dimensional spaces, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.47-56, August 26-29, 2001, San Francisco, California
	Pankaj K. Agarwal , Cecilia M. Procopiuc, Approximation algorithms for projective clustering, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.538-547, January 09-11, 2000, San Francisco, California, United States
	Agma Traina , Caetano Traina , Spiros Papadimitriou , Christos Faloutsos, Tri-plots: scalable tools for multidimensional data mining, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.184-193, August 26-29, 2001, San Francisco, California
	Stefan Berchtold , Christian Böhm , Hans-Peter Kriegal, The pyramid-technique: towards breaking the curse of dimensionality, ACM SIGMOD Record, v.27 n.2, p.142-153, June 1998
	Dong-Ho Lee , Shin Heu , Hyoung-Joo Kim, An efficient algorithm for hyperspherical range query processing in high-dimensional data space, Information Processing Letters, v.83 n.2, p.115-123, 31 July 2002
	Christian Böhm , Bernhard Braunmüller , Florian Krebs , Hans-Peter Kriegel, Epsilon grid order: an algorithm for the similarity join on massive high-dimensional data, ACM SIGMOD Record, v.30 n.2, p.379-388, June 2001
	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
	Jiyuan An , Hanxiong Chen , Kazutaka Furuse , Masahiro Ishikawa , Nobuo Ohbo, The convex polyhedra technique: an index structure for high-dimensional space, Australian Computer Science Communications, v.24 n.2, p.33-40, January-February 2002
	Stefan Berchtold , Christian Böhm , Bernhard Braunmüller , Daniel A. Keim , Hans-Peter Kriegel, Fast parallel similarity search in multimedia databases, ACM SIGMOD Record, v.26 n.2, p.1-12, June 1997
	Sunil Arya , David M. Mount , Nathan S. Netanyahu , Ruth Silverman , Angela Y. Wu, An optimal algorithm for approximate nearest neighbor searching fixed dimensions, Journal of the ACM (JACM), v.45 n.6, p.891-923, Nov. 1998
	Charu C. Aggarwal , Joel L. Wolf , Philip S. Yu , Cecilia Procopiuc , Jong Soo Park, Fast algorithms for projected clustering, ACM SIGMOD Record, v.28 n.2, p.61-72, June 1999
	Paolo Ciaccia , Marco Patella, Searching in metric spaces with user-defined and approximate distances, ACM Transactions on Database Systems (TODS), v.27 n.4, p.398-437, December 2002
	Ali Saman Tosun , Hakan Ferhatosmanoglu, Vulnerabilities in similarity search based systems, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
	Solomon Atnafu , Lionel Brunie , Harald Kosch, Similarity-based algebra for multimedia database systems, Proceedings of the 12th Australasian database conference, p.115-122, January 29-February 01, 2001, Queensland, Australia
	Changzhou Wang , Xiaoyang Sean Wang, High-dimensional nearest neighbor search with remote data centers, Knowledge and Information Systems, v.4 n.4, p.440-465, October 2002
	Lars Arge, External memory data structures, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Yufei Tao , Dimitris Papadias, Spatial queries in dynamic environments, ACM Transactions on Database Systems (TODS), v.28 n.2, p.101-139, June 2003
	Pankaj K. Agarwal , Cecilia M. Procopiuc, Approximation algorithms for projective clustering, Journal of Algorithms, v.46 n.2, p.115-139, February 2003
	Ümit Y. Ogras , Hakan Ferhatosmanoglu, Dimensionality reduction using magnitude and shape approximations, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA
	Gisli R. Hjaltason , Hanan Samet, Index-driven similarity search in metric spaces, ACM Transactions on Database Systems (TODS), v.28 n.4, p.517-580, December 2003
	Yufei Tao , Jimeng Sun , Dimitris Papadias, Analysis of predictive spatio-temporal queries, ACM Transactions on Database Systems (TODS), v.28 n.4, p.295-336, December 2003
	Gísli R. Hjaltason , Hanan Samet, Distance browsing in spatial databases, ACM Transactions on Database Systems (TODS), v.24 n.2, p.265-318, June 1999
	Ömer Eğecioğlu , Hakan Ferhatosmanoğlu, Dimensionality reduction and similarity computation by inner product approximations, Proceedings of the ninth international conference on Information and knowledge management, p.219-226, November 06-11, 2000, McLean, Virginia, United States
	Hakan Ferhatosmanoglu , Ertem Tuncel , Divyakant Agrawal , Amr El Abbadi, Vector approximation based indexing for non-uniform high dimensional data sets, Proceedings of the ninth international conference on Information and knowledge management, p.202-209, November 06-11, 2000, McLean, Virginia, United States
	Flip Korn , Bernd-Uwe Pagel , Christos Faloutsos, On the 'Dimensionality Curse' and the 'Self-Similarity Blessing', IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.96-111, January 2001
	Jun Zhang , Manli Zhu , Dimitris Papadias , Yufei Tao , Dik Lun Lee, Location-based spatial queries, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California
	Christian A. Lang , Ambuj K. Singh, Modeling high-dimensional index structures using sampling, ACM SIGMOD Record, v.30 n.2, p.389-400, June 2001
	Larry Huston , Rahul Sukthankar , Rajiv Wickremesinghe , M. Satyanarayanan , Gregory R. Ganger , Erik Riedel , Anastassia Ailamaki, Diamond: A Storage Architecture for Early Discard in Interactive Search, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
	Bernhard Braunmüller , Martin Ester , Hans-Peter Kriegel , Jörg Sander, Multiple Similarity Queries: A Basic DBMS Operation for Mining in Metric Databases, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.79-95, January 2001
	Ertem Tuncel , Hakan Ferhatosmanoglu , Kenneth Rose, VQ-index: an index structure for similarity searching in multimedia databases, Proceedings of the tenth ACM international conference on Multimedia, December 01-06, 2002, Juan-les-Pins, France
	Gang Qian , Shamik Sural , Yuelong Gu , Sakti Pramanik, Similarity between Euclidean and cosine angle distance for nearest neighbor queries, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
	Dong-Ho Lee , Hyoung-Joo Kim, An Efficient Technique for Nearest-Neighbor Query Processing on the SPY-TEC, IEEE Transactions on Knowledge and Data Engineering, v.15 n.6, p.1472-1486, November 2003
	Sören Balko , Ingo Schmitt , Gunter Saake, The Active Vertice method: a performant filtering approach to high-dimensional indexing, Data & Knowledge Engineering, v.51 n.3, p.369-397, December 2004
	Mutlu Uysal , Fatos Yarman-Vural, A content based image retrieval system based on the fuzzy ARTMAP architecture, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA
	Christian Böhm , Stefan Berchtold , Hans-Peter Kriegel , Urs Michel, Multidimensional Index Structures in Relational Databases, Journal of Intelligent Information Systems, v.15 n.1, p.51-70, July—Aug. 2000
	C. Traina, Jr. , A. Traina , C. Faloutsos , B. Seeger, Fast Indexing and Visualization of Metric Data Sets using Slim-Trees, IEEE Transactions on Knowledge and Data Engineering, v.14 n.2, p.244-260, March 2002
	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
	Rui Zhang , Panos Kalnis , Beng Chin Ooi , Kian-Lee Tan, Generalized multidimensional data mapping and query processing, ACM Transactions on Database Systems (TODS), v.30 n.3, p.661-697, September 2005
	Yufei Tao , Jun Zhang , Dimitris Papadias , Nikos Mamoulis, An Efficient Cost Model for Optimization of Nearest Neighbor Search in Low and Medium Dimensional Spaces, IEEE Transactions on Knowledge and Data Engineering, v.16 n.10, p.1169-1184, October 2004
	Mihael Ankerst , Hans-Peter Kriegel , Thomas Seidl, A Multistep Approach for Shape Similarity Search in Image Databases, IEEE Transactions on Knowledge and Data Engineering, v.10 n.6, p.996-1004, November 1998
	G. Proietti , C. Faloutsos, Accurate Modeling of Region Data, IEEE Transactions on Knowledge and Data Engineering, v.13 n.6, p.874-883, November 2001
	Christian Böhm , Hans-Peter Kriegel , Thomas Seidl, Combining Approximation Techniques and Vector Quantization for Adaptable Similarity Search, Journal of Intelligent Information Systems, v.19 n.2, p.207-230, September 2002
	Deok-Hwan Kim , Seok-Lyong Lee , Chin-Wan Chung, Heterogeneous image database selection on the web, Journal of Systems and Software, v.64 n.2, p.131-149, 15 November 2002
	Vittorio Castelli , Alexander Thomasian , Chung-Sheng Li, CSVD: Clustering and Singular Value Decomposition for Approximate Similarity Search in High-Dimensional Spaces, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.671-685, March 2003
	Yufei Tao , Reynold Cheng , Xiaokui Xiao , Wang Kay Ngai , Ben Kao , Sunil Prabhakar, Indexing multi-dimensional uncertain data with arbitrary probability density functions, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
	Hakan Ferhatosmanoǧlu , Divyakant Agrawal , Ömer Eǧecioǧlu , Amr El Abbadi, Optimal data-space partitioning of spatial data for parallel I/O, Distributed and Parallel Databases, v.17 n.1, p.75-101, January 2005
	Dimitris Papadias , Yufei Tao , Kyriakos Mouratidis , Chun Kit Hui, Aggregate nearest neighbor queries in spatial databases, ACM Transactions on Database Systems (TODS), v.30 n.2, p.529-576, June 2005
	Antonio Corral , Yannis Manolopoulos , Yannis Theodoridis , Michael Vassilakopoulos, Cost models for distance joins queries using R-trees, Data & Knowledge Engineering, v.57 n.1, p.1-36, April 2006
	Hakan Ferhatosmanoglu , Ertem Tuncel , Divyakant Agrawal , Amr El Abbadi, High dimensional nearest neighbor searching, Information Systems, v.31 n.6, p.512-540, September 2006
	Jiyuan An , Hanxiong Chen , Kazutaka Furuse , Nobuo Ohbo, CVA file: an index structure for high-dimensional datasets, Knowledge and Information Systems, v.7 n.3, p.337-357, March 2005
	Yufei Tao , Vagelis Hristidis , Dimitris Papadias , Yannis Papakonstantinou, Branch-and-bound processing of ranked queries, Information Systems, v.32 n.3, p.424-445, May, 2007
	Xiaobin Ma , Shashi Shekhar , Hui Xiong , Pusheng Zhang, Exploiting a page-level upper bound for multi-type nearest neighbor queries, Proceedings of the 14th annual ACM international symposium on Advances in geographic information systems, November 10-11, 2006, Arlington, Virginia, USA
	Robert Charles Lange , Spiros Mancoridis, Using code metric histograms and genetic algorithms to perform author identification for software forensics, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England
	Hyunjung Shin , Sungzoon Cho, Neighborhood Property--Based Pattern Selection for Support Vector Machines, Neural Computation, v.19 n.3, p.816-855, March 2007
	Panayiotis Bozanis , Panayiotis Foteinos, WeR-trees, Data & Knowledge Engineering, v.63 n.2, p.397-413, November, 2007
	Antonio Corral , Jesús M. Almendros-Jiménez, A performance comparison of distance-based query algorithms using R-trees in spatial databases, Information Sciences: an International Journal, v.177 n.11, p.2207-2237, June, 2007
	Yufei Tao , Dimitris Papadias , Qiongmao Shen, Continuous nearest neighbor search, Proceedings of the 28th international conference on Very Large Data Bases, p.287-298, August 20-23, 2002, Hong Kong, China
	Jagan Sankaranarayanan , Hanan Samet , Amitabh Varshney, A fast all nearest neighbor algorithm for applications involving large point-clouds, Computers and Graphics, v.31 n.2, p.157-174, April, 2007
	Renato Bueno , Agma J. M. Traina , Caetano Traina, Jr., Genetic algorithms for approximate similarity queries, Data & Knowledge Engineering, v.62 n.3, p.459-482, September, 2007
	Changzhou Wang , X. Sean Wang, Indexing very high-dimensional sparse and quasi-sparse vectors for similarity searches, The VLDB Journal — The International Journal on Very Large Data Bases, v.9 n.4, p.344-361, April 2001
	Yasushi Sakurai , Masatoshi Yoshikawa , Shunsuke Uemura , Haruhiko Kojima, Spatial indexing of high-dimensional data based on relative approximation, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.2, p.93-108, October 2002
	Dong-Joo Park , Hyoung-Joo Kim, An Enhanced Technique for k-Nearest Neighbor Queries with Non-Spatial Selection Predicates, Multimedia Tools and Applications, v.19 n.1, p.79-19, January 2003
	Yasushi Sakurai , Masatoshi Yoshikawa , Shunsuke Uemura , Haruhiko Kojima, The A-tree: An Index Structure for High-Dimensional Spaces Using Relative Approximation, Proceedings of the 26th International Conference on Very Large Data Bases, p.516-526, September 10-14, 2000
	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
	Ioana Stanoi , Mirek Riedewald , Divyakant Agrawal , Amr El Abbadi, Discovery of Influence Sets in Frequently Updated Databases, Proceedings of the 27th International Conference on Very Large Data Bases, p.99-108, September 11-14, 2001
	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
	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
	Mihael Ankerst , Bernhard Braunmüller , Hans-Peter Kriegel , Thomas Seidl, Improving Adaptable Similarity Query Processing by Using Approximations, Proceedings of the 24rd International Conference on Very Large Data Bases, p.206-217, August 24-27, 1998
	Rakesh Agrawal , Johannes Gehrke , Dimitrios Gunopulos , Prabhakar Raghavan, Automatic Subspace Clustering of High Dimensional Data, Data Mining and Knowledge Discovery, v.11 n.1, p.5-33, July 2005
	Yi Fang , Marc Friedman , Giri Nair , Michael Rys , Ana-Elisa Schmid, Spatial indexing in microsoft SQL server 2008, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	Michael Gibas , Ning Zheng , Hakan Ferhatosmanoglu, A general framework for modeling and processing optimization queries, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Marco Patella , Paolo Ciaccia, Approximate similarity search: A multi-faceted problem, Journal of Discrete Algorithms, v.7 n.1, p.36-48, March, 2009
	Mario Döller , Harald Kosch, The MPEG-7 Multimedia Database System (MPEG-7 MMDB), Journal of Systems and Software, v.81 n.9, p.1559-1580, September, 2008
	Tan Apaydin , Hakan Ferhatosmanoglu, Access Structures for Angular Similarity Queries, IEEE Transactions on Knowledge and Data Engineering, v.18 n.11, p.1512-1525, November 2006
	Yufei Tao , Xiaokui Xiao, Primal or dual: which promises faster spatiotemporal search?, The VLDB Journal — The International Journal on Very Large Data Bases, v.17 n.5, p.1253-1270, August 2008
	Damien Francois , Vincent Wertz , Michel Verleysen, The Concentration of Fractional Distances, IEEE Transactions on Knowledge and Data Engineering, v.19 n.7, p.873-886, July 2007
	Dragomir Yankov , Eamonn Keogh , Umaa Rebbapragada, Disk aware discord discovery: finding unusual time series in terabyte sized datasets, Knowledge and Information Systems, v.17 n.2, p.241-262, November 2008