Approximate searches: k-neighbors + precision

ABSTRACT

It is known that all multi-dimensional index structures fail to accelerate content-based similarity searches when the feature vectors describing images are high-dimensional. It is possible to circumvent this problem by relying on approximate search-schemes trading-off result quality for reduced query execution time. Most approximate schemes, however, provide none or only complex control on the precision of the searches, especially when retrieving the k nearest neighbors (NNs) of query points.In contrast, this paper describes an approximate search scheme for high-dimensional databases where the precision of the search can be probabilistically controlled when retrieving the k NNs of query points. It allows a fine and intuitive control over this precision by setting at run time the maximum probability for a vector that would be in the exact answer set to be missed in the approximate set of answers eventually returned. This paper also presents a performance study of the implementation using real datasets showing its reliability and efficiency. It shows, for example, that our method is 6.72 times faster than the sequential scan when it handles more than 5 10₆ 24-dimensional vectors, even when the probability of missing one of the true nearest neighbors is below 0.01.

REFERENCES

• 1: L. Amsaleg and P. Gros. Content-based retrieval using local descriptors: Problems and issues from a database perspective. Pattern Analysis and Applications, Special Issue on Image Indexation, 4:108--124, 2001.
• 2: L. Amsaleg, P. Gros, and S.-A. Berrani. A robust technique to recognize objects in images, and the db problems it raises. In Proceedings of the 7th International Workshop on Multimedia Information Systems, Capri, Italy, November 2001.
• 3: Laurent Amsaleg , Patrick Gros , Sid-Ahmed Berrani, Robust Object Recognition in Images and the Related Database Problems, Multimedia Tools and Applications, v.23 n.3, p.221-235, August 2004 [doi>10.1023/B:MTAP.0000031758.46389.00]
• 4: Kristin P. Bennett , Usama Fayyad , Dan Geiger, Density-based indexing for approximate nearest-neighbor queries, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.233-243, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312236]
• 5: 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
• 6: 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 [doi>10.1145/502807.502809]
• 7: G. Brown. Modern Mathematics for the Engineer. 1956.
• 8: PAC Nearest Neighbor Queries: Approximate and Controlled Search in High-Dimensional and Metric Spaces, Proceedings of the 16th International Conference on Data Engineering, p.244, February 28-March 03, 2000
• 9: Christos Faloutsos, Searching Multimedia Databases by Content, Kluwer Academic Publishers, Norwell, MA, 1996
• 10: Hakan Ferhatosmanoglu , Ertem Tuncel , Divyakant Agrawal , Amr El Abbadi, Approximate Nearest Neighbor Searching in Multimedia Databases, Proceedings of the 17th International Conference on Data Engineering, p.503-511, April 02-06, 2001
• 11: L. Florack, B. ter Haar Romeny, J. Koenderink, and M. Viergever. General intensity transformation and differential invariants. Journal of Mathematical Imaging and Vision , 4(2):171--187, 1994.
• 12: 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
• 13: Jonathan Goldstein , Raghu Ramakrishnan, Contrast Plots and P-Sphere Trees: Space vs. Time in Nearest Neighbour Searches, Proceedings of the 26th International Conference on Very Large Data Bases, p.429-440, September 10-14, 2000
• 14: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 15: Chen Li , Edward Chang , Hector Garcia-Molina , Gio Wiederhold, Clustering for Approximate Similarity Search in High-Dimensional Spaces, IEEE Transactions on Knowledge and Data Engineering, v.14 n.4, p.792-808, July 2002 [doi>10.1109/TKDE.2002.1019214]
• 16: Deflating the Dimensionality Curse Using Multiple Fractal Dimensions, Proceedings of the 16th International Conference on Data Engineering, p.589, February 28-March 03, 2000
• 17: Cordelia Schmid , Roger Mohr, Local Grayvalue Invariants for Image Retrieval, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.5, p.530-535, May 1997 [doi>10.1109/34.589215]
• 18: Roger Weber , Klemens Böhm, Trading Quality for Time with Nearest Neighbor Search, Proceedings of the 7th International Conference on Extending Database Technology: Advances in Database Technology, p.21-35, March 27-31, 2000
• 19: 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
• 20: 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
• 21: Tian Zhang , Raghu Ramakrishnan , Miron Livny, BIRCH: an efficient data clustering method for very large databases, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.103-114, June 04-06, 1996, Montreal, Quebec, Canada

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Experimentation, Performance

Keywords:
approximate nearest-neighbor searches, multimedia databases, similarity searches