On Projection Based Operators in l_p Space for Exact Similarity Search

• Autorzy: Wichert A. , Moreira C.

Identyfikatory

DOI

10.3233/FI-2015-1166

• Języki publikacji: EN

Abstrakty

EN

We investigate exact indexing for high dimensional l_p norms based on the 1-Lipschitz property and projection operators. The orthogonal projection that satisfies the 1-Lipschitz property for the l_p norm is described. The adaptive projection defined by the first principal component is introduced.

Słowa kluczowe

EN

1-Lipschitz property; curse of dimensionality; nearest neighbour; high-dimensional indexing; Lp-norm

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 136, nr 4
• Strony: 461--474
• Opis fizyczny: Bibliogr. 14 poz., tab.

Twórcy

autor

Wichert A.

• Department of Informatics INESC-ID / IST - University of Lisboa Lisboa, Portugal

autor

Moreira C.

• Department of Informatics INESC-ID / IST - University of Lisboa Lisboa, Portugal

Bibliografia

• [1] Baeza-Yates, R., Ribeiro-Neto, B.: Modeling, in: Modern Information Retrieval (R. Baeza-Yates, B. Ribeiro-Neto, Eds.), chapter 2, Addison-Wesley, 1999, 19–71.
• [2] Böhm, C., Berchtold, S., Kei, D., A. K.: Searching in High-Dimensional Spaces—Index Structures for Improving the Performance of Multimedia Databases, ACM Computing Surveys, 33(3), 2001, 322–373.
• [3] Burt, P. J., Adelson, E. H.: The Laplacian Pyramidas a Compact Image Code, IEEE Trans. Commin, COM-31(4), 1983, 532–540.
• [4] Faloutsos, C.: Modern Information Retrieval, in: Modern Information Retrieval (R. Baeza-Yates, B. Ribeiro-Neto, Eds.), chapter 12, Addison-Wesley, 1999, 345–365.
• [5] Faloutsos, C., Barber, R., Flickner, M., Hafner, J., Niblack, W., Petkovic, D., Equitz, W.: Efficient and Effective Querying by Image Content, Journal of Intelligent Information Systems, 3(3/4), 1994, 231–262.
• [6] Gonzales, R. C., Woods, E. W.: Digital Image Processing, second edition, Prentice Hall, 2001.
• [7] Indyk, P.: Nearest neighbours in high-dimensional spaces, in: Handbook of Discrete and Computational Geometry (J. Goodman, J. O’Rourke, Eds.), Boca Raton–London–New York–Wahington, 2004.
• [8] Indyk, P., Motwani, R.: Approximate nearest neighbours: towards removing the curse of dimensionality, Proc. 30th ACM Symp. Theory of Computing, 1998.
• [9] Jegou, H., Douze, M., Schmid, S.: Product quantization for nearest neighbor search, IEEE Transactions on Pattern Analysis and Machine Intelligence, 33(1), 2011, 117–128.
• [10] Pestov, V.: Lower bounds on performance of metric tree indexing schemes for exact similarity search in high dimensions, Proceedings of the 4th International Conference on Similarity Search and Applications (A. Ferro, Ed.), 2011.
• [11] Pestov, V.: Indexability, concentration, and VC theory, Journal of Discrete Algorithms, 13, 2012, 2–18.
• [12] Wichert, A.: Content-based image retrieval by hierarchical linear subspace method, Journal of Intelligent Information Systems, 31(1), 2008, 85–107.
• [13] Wichert, A., Teixeira, P., Santos, P., Galhardas, H.: Subspace tree: High dimensional multimedia indexing with logarithmic temporal complexity, Journal of Intelligent Information Systems, 35(3), 2010, 495–516.
• [14] Wichert, A., Verissimo, A.: CBIR with a Subspacee-tree: Principal Component Analysis versus Averaging, Multimedia Systems, 18(4), 2012, 283–293.