A Distributed M-Tree for Similarity Search in Large Multimedia Database on Spark

A Distributed M-Tree for Similarity Search in Large Multimedia Database on Spark

Phuc Do (University of Information Techonology (VNU-HCM), Vietnam) and Trung Hong Phan (University of Information Techonology (VNU-HCM), Vietnam)
Copyright: © 2020 |Pages: 19
DOI: 10.4018/978-1-7998-2701-6.ch007

Abstract

In this chapter, Image2vec or Video2vector are used to convert images and video clips to vectors in large multimedia database. The M-tree is an index structure that can be used for the efficient resolution of similarity queries on complex objects. M-tree can be profitably used for content-based retrieval on multimedia databases provided relevant features have been extracted from the objects. In a large multimedia database, to search for similarities such as k-NN queries and Range queries, distances from the query object to all remaining objects (images or video clips) are calculated. The calculation between query and entities in a large multimedia database is not feasible. This chapter proposes a solution to distribute the M-Tree structure on the Apache Spark framework to solve the Range Query and kNN Query problems in large multimedia database with a lot of images and video clips.
Chapter Preview
Top

Introduction

Multimedia databases contain images and video clips (Guo, 2013; Riaz, Ashraf, & Aslam, 2014). Today, the volume of multimedia database contains a huge number of objects. In this we use Image2vec (Garcia-Gasulla, Béjar, Cortés, Ayguadé, & Labarta, 2015) or Video2vec (Hu, Li, & Li, 2016) to convert images and videos to vectors and store these vectors for more convenience in processing. To search for similarities such as kNN queries and Range queries in vector spaces (representing images and video clips), we need to calculate distances from the query vector to all remaining vectors. In a large multimedia database, the vector space with millions to billions of vectors. The calculation of distances as above is not feasible. Therefore, we need a method to reduce the number of distance calculations in these problems. The M-Tree structure, which is a distance-based vector space indexing method, can effectively solve the Range queries and kNN queries (Ciaccia, Patella, & Zezula, 1997; Kouahla, 2011). Because the M-Tree structure is implemented on a local system, it only solves problems in small vector spaces, in which the set of vectors can fit into a computer. However, very large multimedia databases contain millions of vectors of image or video clip are very popular. The local M-Tree structure cannot meet the new needs to solve problems of similarity searching in large vector spaces, in which vectors must be stored distributedly across multiple computers. Therefore, in this article, we propose a solution to distribute the M-Tree structure on the Apache Spark framework (Assefi, Behravesh, Liu, & Tafti, 2018; Shanahan & Dai, 2019; Zecevic & Bonaci, 2017) to solve the kNN and Range Query problems in large vector spaces. In addition, we also present experimental results on creating both local and distributed M-Tree structures built from 64-dimentional vector sets with different scales. Finally, we present the experimental results on the kNN and Range queries on the built M-Tree structures of a multimedia database of image and video clips;

The main contributions of this article are as follows:

  • Converting a multimedia objects as images and video clips to vectors using Image2vec and Video2vec.

  • Proposing a solution to distribute the M-Tree structure to meet new needs in the era of big data.

  • Solving kNN and Range Query problems based on the distributed M-Tree structure.

  • Providing relevant experimental results.

The rest of this article is organized as follows. Section 2 is the related works. Section 3 introduces the knowledge base we use in this article. Section 4 is the methodology. Section 5 is the experiments. The final is the conclusion and future work

Top

Beginning with a paper proposing the M-Tree structure as an effective method to search similarities (Ciaccia et al., 1997), there were many works to implement and develop the M-Tree structure, as well as develop similar indexing structures.

In 2010, Akrivi Vlachou proposed a framework for distributed similarity search, where each participating peer stored its own data that indexed locally by using M-Tree structures. In order to scalability and efficiency of search, they used a super-peer architecture, where super-peers were responsible for query routing. They also proposed the construction of metric routing indices suitable for distributed similarity search in metric spaces (Vlachou, Doulkeridis, & Kotidis, 2010).

In 2011, Z. Kouahla studied a variant of a metric tree data structure for indexing and querying data, and conducted experiments to compare his solution with techniques: MM-Tree and SliM-Tree. The author also provided the taxonomy of indexing techniques in metric spaces as shown in Figure 1 (Kouahla, 2011).

Complete Chapter List

Search this Book:
Reset