CD-Tree: A clustering-based dynamic indexing and retrieval approach

Abstract

In the big data era, the efficient indexing of gradually increasing databases is becoming vitally important for information retrieval. To incrementally adapt to changes of databases, in this paper we propose a novel clustering based dynamic indexing and retrieval approach. The tree-like indexing structure, termed as CD-Tree, updates the structure with constant insertion of data, keeping the tree in consistent with the newest database. The nodes in the CD-Tree are fitted by Gaussian Mixture Models, based on which we design the efficient updating algorithm. The similarity retrieval method utilizing the CD-Tree is further presented, combining one-way search and backtracking strategy to gain good retrieval accuracy and efficiency. We applied the CD-Tree to example-based image retrieval. The experimental results confirm that our approach is effective and promising.

Keywords

Information retrieval data stream dynamic indexing tree-like indexing structure Gaussian Mixture Models (GMM)

References

Available at: http://www.image-net.org/challenges/LSVRC/2012/, last accessed: Sep. 25 2015.

Brown

E.W.

, Callan

J.P.

and Croft

W.B.

, Fast incremental indexing for full-text information retrieval, Very Large Data Bases 94(66) (1994).

Büttcher

and Clarke

L.A.

, Indexing time vs. query time: Trade-offs in dynamic information retrieval systems, in: Proceedings of the 14th ACM International Conference on Information and Knowledge Management, Springer (2005), 317-318.

Chiueh

T.C.

and Huang

, Efficient real-time index updates in text retrieval systems, Technical Report, 1999.

Cui

, Ooi

B.C.

, Su

and Tan

K.L.

, Contorting high dimensional data for efficient main memory KNN processing, in: Proceedings of ACM SIGMOD International Conference on Management of Data, ACM (2003), 479-490.

Datta

, Joshi

, Li

and Wang

, Image retrieval: Ideas, influences, and trends of the new age, ACM Computer Survey 40(2) (2008), 1-60.

Deng

, Dong

, Socher

, Li

L.J.

, Li

and Li

, ImageNet: A large-scale hierarchical image database, in: Proceedings of Computer Vision and Pattern Recognition, IEEE (2009), 248-255.

Ferchichi

and Gouider

M.S.

, BSTree: An incremental indexing structure for similarity search and real time monitoring of data streams, Future Information Technology, Springer (2014), 185-190.

Gang

, Zhu

, Xue

and Pramanik

, The ND-Tree: A dynamic indexing technique for multidimensional non-ordered discrete data spaces, in: Proceedings of Very Large Data Base, Morgan Kaufmann (2003).

10.

Gevers

, Weijer

and Stokman

, Color feature detection: an overview, in: Color Image Processing: Methods and Applications, (2006), 203-226.

11.

Guttman

, R-trees: A dynamic index structure for spatial searching, in: Proceedings of ACM SIGMOD International Conference on Management of Data, ACM (1984), 47-57.

12.

Hendra

, Gopalan

R.P.

and Nair

M.G.

, A method for dynamic indexing of large image databases, in: Proceedings of International Conference on Systems, Man, and Cybernetics, IEEE (1999), 302-307.

13.

James

Z.W.

, Jia

and Gio

, SIMPLIcity: Semantics-sensitive integrated matching for picture libraries, IEEE Transactions on Pattern Analysis and Machine Intelligence 23(9), (2001), 947-963.

14.

Karthik

, Pulla

and Jawahar

C.V.

, Incremental on-line semantic indexing for image retrieval in dynamic databases, in: Proceedings of Computer Vision and Pattern Recognition Workshops, (2009), 9-16.

15.

Katayama

and Satoh

, The SR-tree: An index structure for high dimensional nearest neighbor queries, in: Proceedings of ACM SIGMOD International Conference on Management of Data, ACM (1997), 369-380.

16.

Khalid

, Incremental indexing and retrieval mechanism for scalable and robust shape matching, Multimedia Systems 18(4) (2011), 319-336.

17.

Kiranyaz

and Gabbouj

, A dynamic content-based indexing method for multimedia databases: hierarchical cellular tree, in: Proceedings of IEEE International Conference on IEEE Image Processing, IEEE (2005), 533-536.

18.

Lew

, Sebe

, Djeraba

and Jain

, Content-based multimedia information retrieval: State of the art and challenges, Transactions on Multimedia Computing , Communications, and Applications 2(1) (2006), 1-19.

19.

and Yuan

, Incremental hybrid Bayesian network in content-based image retrieval, in: Proceedings of the Canadian Conference on Electrical and Computer Engineering, (2005), 2025-2028.

20.

Mahdi

S.T.

and Abrishami

M.H.

, A novel evolutionary approach for optimizing content-based image indexing algorithms, IEEE Transactions on System Man & Cybernetics Part B 37(1) (2007), 139-153.

21.

Moerland

, A comparison of mixture models for density estimation, in: Proceedings of International Conference on Artificial Neural Networks, (1999), 25-30.

22.

Mohammed

S.I.

, Omara

F.A.

and Sharaf

H.M.

, Information retrieval using dynamic indexing, in: Proceedings of IEEE International Conference on Informatics and Systems, IEEE (2014), 93-101.

23.

Nikzad

and Moghaddam

H.A.

, An incremental evolutionary learning method for optimizing content-based image indexing algorithms, International Journal of Multimedia Information Retrieval 3(1) (2013), 41-52.

24.

Petraki

, Holistic indexing: Offline, online and adaptive indexing in the same kernel, in: Proceedings of 2012 PhD Symposium of SIGMOD/PODS, ACM (2012), 15-20.

25.

Priya

R.V.

and Vadivel

, Incremental indexing for high-dimensional data using tree structure, Procedia Technology 1(4) (2012), 540-547.

26.

Priya

R.V.

, Vadivel

and Thakur

R.S.

, Maximal pattern mining using fast CP-Tree for knowledge discovery, International Journal on Information Systems and Social Change 3(1) (2012), 62-80.

27.

Ramadan

, Christen

, Liang

, Gayler

R.W.

and Hawking

, Dynamic similarity-aware inverted indexing for real-time entity resolution, Trends and Applications in Knowledge Discovery and Data Mining, Springer (2013), 47-58

28.

Rao

, Medeiros

and Kak

, An incremental update framework for efficient retrieval from software libraries for bug localization, in: Proceedings of Working Conference on Reverse Engineering, (2013), 62-71.

29.

Schettini

, Ciocca

and Zuffi

, A survey on methods for color image indexing and retrieval in image databases, Color Imaging Science: Exploiting Digital Media, (2001), 183-211.

30.

Tao

, Yi

, Sheng

and Kalnis

, Efficient and accurate nearest neighbor and closest pair search in high-dimensional space, ACM Transactions on Database Systems 35(3) (2010), 53-56.

31.

Tao

, Jin

, Luo

and Wu

, Integrating image clustering and memory indexing for large scale content-based image retrieval, in: Proceedings of Sixth International Symposium on Multispectral Image Processing and Pattern Recognition, (2009).

32.

Vlassis

and Likas

, A kurtosis-based dynamic approach to Gaussian mixture modeling, IEEE Transactions on Systems, Man and Cybernetics 29(4) (1999), 393-399.

33.

Wan

, Liu

, Tong

, Wei

, Wu

and Guan

, GMM-ClusterForest: A novel indexing approach for multi-features based similarity search in high-dimensional spaces, in: Proceedings of International Conference on Neural Information Processing, Springer, (2012), 210-217.

34.

Wang

and Gan

, Integration of projected clusters and principal axis trees for high-dimensional data indexing and query, in: Proceeding of Intelligent Data Engineering and Automated Learning, Springer (2004), 191-196.

35.

, Rahman

M.K.

and Chow

T.W.

, Content-based image retrieval using growing hierarchical self-organizing quad tree map, Pattern Recognition 38(5) (2005), 707-722.

36.

You

and Li

, On Hierarchical content-based image retrieval by dynamic indexing and guided search, International Journal of Cognitive Informatics & Natural Intelligence 4(4) (2010), 188-195.