A case-study of scoring schemes for the PvS-index

ABSTRACT

Recently we have proposed a new indexing method for high-dimensional data, the PvS-index. It provides fast query processing in constant time and is well suited for doing similarity search in Image Retrieval Systems using local descriptors. It is based on projecting data points onto random lines and uses this information to segment them into appropriately sized buckets, which can be read in just one I/O operation. After this preprocessing step the search queries just three buckets per query descriptor and uses a recent rank aggregation method, OMEDRANK, in order to provide good approximate results for the nearest neighbour problem.We have recently shown that PvS-indexing works well for large collections of real image data. In that work, however, we used a simple scoring scheme and collected few nearest neighbours for each query descriptor. In this study we examine how much the actual number of nearest neighbours, gathered for each local descriptor, influences the final query result, when searching a PvS-index. Based on the results we propose two new alternative scoring schemes, which improve the retrieval quality and stabilise the results, making the search less affected by the actual number of nearest neighbours accumulated.

REFERENCES

• 1: L. Amsaleg and P. Gros. Content-based retrieval using local descriptors: Problems and issues from a database perspective. Pattern Analysis and Applications, 4(2/3), 2001.
• 2: Sid-Ahmed Berrani , Laurent Amsaleg , Patrick Gros, Robust content-based image searches for copyright protection, Proceedings of the 1st ACM international workshop on Multimedia databases, November 07-07, 2003, New Orleans, LA, USA [doi>10.1145/951676.951690]
• 3: Ronald Fagin , Ravi Kumar , D. Sivakumar, Efficient similarity search and classification via rank aggregation, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872795]
• 4: 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
• 5: D. Hinkley. Inference about the change-point from cumulative sum-tests. Biometrika, (58), 1971.
• 6: Y. Ke and R. Sukthankar. PCA-SIFT: A more distinctive representation for local image descriptors. In Proceedings of IEEE Computer Vision and Pattern Recognition, Washington DC, 2004.
• 7: Yan Ke , Rahul Sukthankar , Larry Huston, An efficient parts-based near-duplicate and sub-image retrieval system, Proceedings of the 12th annual ACM international conference on Multimedia, October 10-16, 2004, New York, NY, USA [doi>10.1145/1027527.1027729]
• 8: H. Lejsek and F. H. Ásmundsson. The application of the MEDRANK algorithm to content-based image retrieval using local descriptors. BS project report, Reykjavík University, 2004.
• 9: H. Lejsek, F. H. Ásmundsson, B. Þ. Jónsson, and L. Amsaleg. Efficient and effective image copyright enforcement. Technical Report. Reykjavík University, 2005.
• 10: David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, International Journal of Computer Vision, v.60 n.2, p.91-110, November 2004 [doi>10.1023/B:VISI.0000029664.99615.94]
• 11: F. Petitcolas et al. A public automated web-based evaluation service for watermarking schemes: StirMark benchmark. In Proc. of Electronic Imaging, Security and Watermarking of Multimedia Contents III, San Jose, CA, 2001.