Article

Impact of storage technology on the efficiency of cluster-based high-dimensional index creation

Authors:

Gylfi Þór Gudmundsson,

Laurent Amsaleg,

Björn Þór JónssonAuthors Info & Claims

DASFAA'12: Proceedings of the 17th international conference on Database Systems for Advanced Applications

Pages 53 - 64

https://doi.org/10.1007/978-3-642-29023-7_6

Published: 15 April 2012 Publication History

Abstract

The scale of multimedia data collections is expanding at a very fast rate. In order to cope with this growth, the high-dimensional indexing methods used for content-based multimedia retrieval must adapt gracefully to secondary storage. Recent progress in storage technology, however, means that algorithm designers must now cope with a spectrum of secondary storage solutions, ranging from traditional magnetic hard drives to state-of-the-art solid state disks. We study the impact of storage technology on a simple, prototypical high-dimensional indexing method for large scale query processing. We show that while the algorithm implementation deeply impacts the performance of the indexing method, the choice of underlying storage technology is equally important.

References

[1]

Andoni, A., Indyk, P.: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM 51, 117-122 (2008)

Digital Library

[2]

Athanassoulis, M., Ailamaki, A., Chen, S., Gibbons, P. B., Stoica, R.: Flash in a dbms: Where and how? IEEE Data Eng. Bull. 33(4), 28-34 (2010)

[3]

Bonnet, P., Bouganim, L.: Flash device support for database management. In: CIDR, pp. 1-8 (2011), www.crdrdb.org

[4]

Bouganim, L., Jónsson, B. T., Bonnet, P.: uFLIP: Understanding flash IO patterns. In: Proc. CIDR (2009)

[5]

Casey, M., Veltkamp, R., Goto, M., Leman, M., Rhodes, C., Slaney, M.: Contentbased music information retrieval: Current directions and future challenges. Proceedings of the IEEE 96(4), 668-696 (2008)

[6]

Chierichetti, F., Panconesi, A., Raghavan, P., Sozio, M., Tiberi, A., Upfal, E.: Finding near neighbors through cluster pruning. In: Proc. PODS (2007)

Digital Library

[7]

Datta, R., Joshi, D., Li, J., Wang, J. Z.: Image retrieval: Ideas, influences, and trends of the new age. ACM Comput. Surv. 40, 5:1-5:60 (2008)

Digital Library

[8]

Gudmundsson, G., Jónsson, B. T., Amsaleg, L.: A large-scale performance study of cluster-based high-dimensional indexing. In: Proc. ACMMM-Workshop on Very-Large-Scale Multimedia Corpus, Mining and Retrieval (2010)

Digital Library

[9]

Jégou, H., Douze, M., Schmid, C.: Product quantization for nearest neighbor search. IEEE TPAMI 33(1), 117-128 (2011)

Digital Library

[10]

Lejsek, H., Àsmundsson, F. H., Jónsson, B. T., Amsaleg, L.: NV-Tree: An efficient disk-based index for approximate search in very large high-dimensional collections. IEEE Trans. Pattern Anal. Mach. Intell. 31, 869-883 (2009)

Digital Library

[11]

Lew, M. S., Sebe, N., Djeraba, C., Jain, R.: Content-based multimedia information retrieval: State of the art and challenges. ACM Trans. Multimedia Comput. Commun. Appl. 2, 1-19 (2006)

Digital Library

[12]

Lowe, D. G.: Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision 60(2) (2004)

Digital Library

[13]

Paulevé, L., Jégou, H., Amsaleg, L.: Locality sensitive hashing: A comparison of hash function types and querying mechanisms. Pattern Recognition Letters 31(11), 1348-1358 (2010)

Digital Library

[14]

Philbin, J., Chum, O., Isard, M., Sivic, J., Zisserman, A.: Lost in quantization: Improving particular object retrieval in large scale image databases. In: Proc. CVPR (2008)

[15]

Samet, H.: Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann Publishers Inc., San Francisco (2005)

Digital Library

[16]

Shaft, U., Ramakrishnan, R.: Theory of nearest neighbors indexability. ACM TODS 31(3), 814-838 (2006)

Digital Library

[17]

Sivic, J., Zisserman, A.: Video Google: A text retrieval approach to object matching in videos. In: Proc. ICCV (2003)

Digital Library

Cited By

Knudsen EQvortrup TKhan OJónsson BGurrin CSchoeffmann KJónsson BDang-Nguyen DLokoč JTran MHürst WRossetto LHealy G(2021)XQC at the Lifelog Search Challenge 2021: Interactive Learning on a Mobile DeviceProceedings of the 4th Annual on Lifelog Search Challenge10.1145/3463948.3469063(89-93)Online publication date: 21-Aug-2021
https://dl.acm.org/doi/10.1145/3463948.3469063
Khan OGurrin CÞór Jónsson BKando NSchoeffmann KChen PO'Connor N(2020)An Interactive Learning System for Large-Scale Multimedia AnalyticsProceedings of the 2020 International Conference on Multimedia Retrieval10.1145/3372278.3391935(368-372)Online publication date: 8-Jun-2020
https://dl.acm.org/doi/10.1145/3372278.3391935
Khan OJónsson BRudinac SZahálka JRagnarsdóttir HÞorleiksdóttir ÞGuðmundsson GAmsaleg LWorring M(2020)Interactive Learning for Multimedia at LargeAdvances in Information Retrieval10.1007/978-3-030-45439-5_33(495-510)Online publication date: 14-Apr-2020
https://dl.acm.org/doi/10.1007/978-3-030-45439-5_33
Show More Cited By

Index Terms

Impact of storage technology on the efficiency of cluster-based high-dimensional index creation
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        File systems management

Index terms have been assigned to the content through auto-classification.

Recommendations

Storage management in large distributed object-based storage systems
Storage Space Reclaim Based on Cluster Bitmap in the New Technology File System
ISCC-C '13: Proceedings of the 2013 International Conference on Information Science and Cloud Computing Companion

Thin provisioning is widely used to improve the utilization ratio of storage space in the storage area network (SAN) environment. However, most of file systems only use the logical volume offered by iSCSI protocol and does not support automatic ...
SSD Technology Enables Dynamic Maintenance of Persistent High-Dimensional Indexes
ICMR '16: Proceedings of the 2016 ACM on International Conference on Multimedia Retrieval

In today's world of ever-increasing multimedia collections, dynamically and persistently maintaining high-dimensional indexes is imperative for industrial applications. Since HDD performance is the main bottleneck in index maintenance, we investigate ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

DASFAA'12: Proceedings of the 17th international conference on Database Systems for Advanced Applications

April 2012

334 pages

ISBN:9783642290220

Editors:
Hwanjo Yu
Department of Computer Science and Engineering, Pohang University of Science and Technology, 77 Cheongam-ro, Nam-gu, Pohang, Gyeongbuk, South Korea
,
Ge Yu
Schoolf of Information Science and Engineering, Northeastern University, No. 11 Lane 3 WenHua Road, HePing District, Shenyang, Liaoning Province, China
,
Wynne Hsu
Department of Computer Science, National University of Singapore, 21 Lower Kent ridge Road, Singapore, Liaoning Province, Singapore
,
Yang-Sae Moon
Department of Computer Science, Kangwon National University, 192-1, Hyoja2-Dong, Kangwon, Chuncheon, South Korea
,
Rainer Unland
Institute for Computer Science and Business Information, University of Duisburg-Essen, Schützenbahn 70, Essen, Chuncheon, Germany

Sponsors

Pusan National Univ.: Pusan National University
Onion Software: Onion Software
BBMC: BBMC
KIISE Database Society of Korea
Consortium of Cloud Computing Research: Consortium of Cloud Computing Research

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 15 April 2012

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Knudsen EQvortrup TKhan OJónsson BGurrin CSchoeffmann KJónsson BDang-Nguyen DLokoč JTran MHürst WRossetto LHealy G(2021)XQC at the Lifelog Search Challenge 2021: Interactive Learning on a Mobile DeviceProceedings of the 4th Annual on Lifelog Search Challenge10.1145/3463948.3469063(89-93)Online publication date: 21-Aug-2021
https://dl.acm.org/doi/10.1145/3463948.3469063
Khan OGurrin CÞór Jónsson BKando NSchoeffmann KChen PO'Connor N(2020)An Interactive Learning System for Large-Scale Multimedia AnalyticsProceedings of the 2020 International Conference on Multimedia Retrieval10.1145/3372278.3391935(368-372)Online publication date: 8-Jun-2020
https://dl.acm.org/doi/10.1145/3372278.3391935
Khan OJónsson BRudinac SZahálka JRagnarsdóttir HÞorleiksdóttir ÞGuðmundsson GAmsaleg LWorring M(2020)Interactive Learning for Multimedia at LargeAdvances in Information Retrieval10.1007/978-3-030-45439-5_33(495-510)Online publication date: 14-Apr-2020
https://dl.acm.org/doi/10.1007/978-3-030-45439-5_33
Khan OJónsson BZahálka JRudinac SWorring MGurrin CSchoeffmann KJoho HDang-Nguyen DRiegler MPiras L(2019)Exquisitor at the Lifelog Search Challenge 2019Proceedings of the ACM Workshop on Lifelog Search Challenge10.1145/3326460.3329156(7-11)Online publication date: 5-Jun-2019
https://dl.acm.org/doi/10.1145/3326460.3329156

View Options

View options

Media

Figures

Other

Tables

View Table of Contents