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

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

Related Work

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).