Skip to main content
SpringerLink
Log in

Hierarchical information quadtree: efficient spatial temporal image search for multimedia stream

  • Published:
Multimedia Tools and Applications Aims and scope Submit manuscript

Abstract

Massive amount of multimedia data that contain times- tamps and geographical information are being generated at an unprecedented scale in many emerging applications such as photo sharing web site and social networks applications. Due to their importance, a large body of work has focused on efficiently computing various spatial image queries. In this paper,we study the spatial temporal image query which considers three important constraints during the search including time recency, spatial proximity and visual relevance. A novel index structure, namely Hierarchical Information Quadtree(HI-Quadtree), to efficiently insert/delete spatial temporal images with high arrive rates. Base on HI-Quadtree an efficient algorithm is developed to support spatial temporal image query. We show via extensive experimentation with real spatial databases clearly demonstrate the efficiency of our methods.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8

Similar content being viewed by others

References

  1. Alfarrarjeh A, Shahabi C (2017) Hybrid indexes to expedite spatial-visual search. CoRR arXiv:1702.05200

  2. Amati G, Amodeo G, Gaibisso C (2012) Survival analysis for freshness in microblogging search. In: 21St ACM international conference on information and knowledge management, CIKM’12, Maui, HI, USA, October 29 - November 02, 2012, pp 2483–2486

  3. Aref WG, Samet H (1990) Efficient processing of window queries in the pyramid data structure. In: Proceedings of the Ninth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, April 2-4, 1990, Nashville, Tennessee, USA, pp 265–272

  4. Bay H, Tuytelaars T, Gool LJV (2006) SURF: Speeded up robust features. In: Computer vision - ECCV 2006, 9th European Conference on Computer Vision, Graz, Austria, May 7-13, 2006, Proceedings, Part I, pp 404–417

    Chapter  Google Scholar 

  5. Beckmann N, Kriegel H, Schneider R, Seeger B (1990) The r*-tree: an efficient and robust access method for points and rectangles. In: Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, May 23-25, 1990, pp 322–331

  6. Bunte K, Biehl M, Jonkman MF, Petkov N (2011) Learning effective color features for content based image retrieval in dermatology. Pattern Recogn 44 (9):1892–1902

    Article  Google Scholar 

  7. Cao X, Chen L, Cong G, Jensen CS, Qu Q, Skovsgaard A, Wu D, Yiu ML (2012) Spatial keyword querying. In: Conceptual modeling - 31st international conference ER 2012, Florence, Italy, October 15-18, 2012. Proceedings, pp 16–29

  8. Chen L, Cong G, Cao X, Tan K (2015) Temporal spatial-keyword top-k publish/subscribe. In: 31St IEEE international conference on data engineering, ICDE 2015, Seoul, South Korea, April 13-17, 2015, pp 255–266

  9. Cong G, Jensen CS, Wu D (2009) Efficient retrieval of the top-k most relevant spatial web objects. PVLDB 2(1):337–348

    Google Scholar 

  10. Efron M, Golovchinsky G (2011) Estimation methods for ranking recent information. In: Proceeding of the 34th international ACM SIGIR conference on research and development in information retrieval, SIGIR 2011, Beijing, China, July 25-29, 2011, pp 495–504

  11. Gargantini I (1982) An effective way to represent quadtrees. Commun ACM 25 (12):905–910

    Article  Google Scholar 

  12. Guo L, Shao J, Aung HH, Tan K (2015) Efficient continuous top-k spatial keyword queries on road networks. GeoInformatica 19(1):29–60

    Article  Google Scholar 

  13. Guttman A (1984) R-trees: a dynamic index structure for spatial searching. In: SIGMOD’84, Proceedings of Annual Meeting, Boston, Massachusetts, June 18-21, 1984, pp 47–57

  14. Huang M, Liu A, Xiong N, Wang T, Vasilakos AV (2018) A low-latency communication scheme for mobile wireless sensor control systems. IEEE Trans Systems Man Cybernetics-Systems

  15. Irtaza A, Jaffar MA, Aleisa E, Choi T (2014) Embedding neural networks for semantic association in content based image retrieval. Multimed Tool Appl 72 (2):1911–1931

    Article  Google Scholar 

  16. Jing Y, Baluja S (2008) Visualrank: applying pagerank to large-scale image search. IEEE Trans Pattern Anal Mach Intell 30(11):1877–1890

    Article  Google Scholar 

  17. Lew MS, Sebe N, Djeraba C, Jain R (2006) Content-based multimedia information retrieval: state of the art and challenges. TOMCCAP 2(1):1–19

    Article  Google Scholar 

  18. Li Z, Lee KCK, Zheng B, Lee W, Lee DL, Wang X (2011) Ir-tree: an efficient index for geographic document search. IEEE Trans Knowl Data Eng 23 (4):585–599

    Article  Google Scholar 

  19. Liu X, Liu Y, Liu A, Yang LT (2018) Defending on-off attacks using light probing messages in smart sensors for industrial communication systems. IEEE Trans Industrial Informatics

  20. Lowe DG (1999) Object recognition from local scale-invariant features. In: ICCV, pp 1150–1157

  21. Lowe DG (2004) Distinctive image features from scale-invariant keypoints. Int J Comput Vis 60(2):91–110

    Article  Google Scholar 

  22. Lu J, Lu Y, Cong G (2011) Reverse spatial and textual k nearest neighbor search. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2011, Athens, Greece, June 12-16, 2011, pp 349–360

  23. Mehta P, Skoutas D, Sacharidis D, Voisard A (2016) Coverage and diversity aware top-k query for spatio-temporal posts. In: Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS 2016, Burlingame, California, USA, October 31 - November 3, 2016, pp 37:1–37:10

  24. Nepomnyachiy S, Gelley B, Jiang W, Minkus T (2014) What, where, and when: keyword search with spatio-temporal ranges. In: Proceedings of the 8th Workshop on Geographic Information Retrieval, GIR 2014, Dallas/Fort Worth, TX, USA, November 4-7, 2014, pp 2:1–2:8

  25. Rocha-Junior JB, Gkorgkas O, Jonassen S, Nørvåg K (2011) Efficient processing of top-k spatial keyword queries. In: Advances in spatial and temporal databases - 12th international symposium, SSTD 2011, minneapolis, MN, USA, August 24-26, 2011, Proceedings, pp 205–222

  26. Rocha-Junior JB, Nørvåg K (2012) Top-k spatial keyword queries on road networks. In: 15th international conference on extending database technology, EDBT ’12, Berlin, Germany, March 27-30, 2012, Proceedings, pp 168–179

  27. Sivic J, Zisserman A (2003) Video google: a text retrieval approach to object matching in videos. In: 9th IEEE International Conference on Computer Vision (ICCV 2003), 14-17 October 2003, Nice, France, pp 1470–1477

  28. Sivic J, Russell BC, Efros AA, Zisserman A, Freeman WT (2005) Discovering objects and their localization in images. In: 10th IEEE international conference on computer vision (ICCV 2005), 17-20 October 2005, Beijing, China, pp 370–377

  29. Theodoridis Y, Vazirgiannis M, Sellis TK (1996) Spatio-temporal indexing for large multimedia applications. In: Proceedings of the IEEE International Conference on Multimedia Computing and Systems, ICMCS 1996, Hiroshima, Japan, June 17-23, 1996, pp 441–448

  30. Wan J, Wang D, Hoi SC, Wu P, Zhu J, Zhang Y, Li J (2014) Deep learning for content-based image retrieval: a comprehensive study. In: Proceedings of the ACM International Conference on Multimedia, MM ’14, Orlando, FL, USA, November 03 - 07, 2014, pp 157–166

  31. Wang Y, Wu L (2018) Beyond low-rank representations: Orthogonal clustering basis reconstruction with optimized graph structure for multi-view spectral clustering. Neural Netw 103:1–8

    Article  Google Scholar 

  32. Wang Y, Lin X, Zhang Q (2013) Towards metric fusion on multi-view data: a cross-view based graph random walk approach. In: 22nd ACM international conference on information and knowledge management, CIKM’13, San Francisco, CA, USA, October 27 - November 1, 2013, pp 805–810

  33. Wang Y, Lin X, Zhang Q, Wu L (2014) Shifting hypergraphs by probabilistic voting. In: Advances in knowledge discovery and data mining - 18th pacific-asia conference, PAKDD 2014, tainan, taiwan, may 13-16, 2014. Proceedings, Part II, pp 234–246

    Chapter  Google Scholar 

  34. Wang Y, Lin X, Wu L, Zhang W, Zhang Q (2014) Exploiting correlation consensus: Towards subspace clustering for multi-modal data. In: Proceedings of the ACM International Conference on Multimedia, MM ’14, Orlando, FL, USA, November 03 - 07, 2014, pp 981–984

  35. Wang Y, Lin X, Wu L, Zhang W (2015) Effective multi-query expansions: Robust landmark retrieval. In: Proceedings of the 23rd Annual ACM Conference on Multimedia Conference, MM ’15, Brisbane, Australia, October 26 - 30, 2015, pp 79–88

  36. Wang Y, Lin X, Wu L, Zhang W, Zhang Q (2015) LBMCH: Learning bridging mapping for cross-modal hashing. In: Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, Santiago, Chile, August 9-13, 2015, pp 999–1002

  37. Wang Y, Lin X, Wu L, Zhang W, Zhang Q, Huang X (2015) Robust subspace clustering for multi-view data by exploiting correlation consensus. IEEE Trans Image Processing 24(11):3939–3949

    Article  MathSciNet  Google Scholar 

  38. Wang Y, Zhang W, Wu L, Lin X, Fang M, Pan S (2016) Iterative views agreement: an iterative low-rank based structured optimization method to multi-view spectral clustering. In: Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July 2016, pp 2153–2159

  39. Wang Y, Zhang W, Wu L, Lin X, Zhao X (2017) Unsupervised metric fusion over multiview data by graph random walk-based cross-view diffusion. IEEE Trans Neural Netw Learning Syst 28(1):57–70

    Article  Google Scholar 

  40. Wang Y, Lin X, Wu L, Zhang W (2017) Effective multi-query expansions: Collaborative deep networks for robust landmark retrieval. IEEE Trans Image Processing 26(3):1393–1404

    Article  MathSciNet  Google Scholar 

  41. Wang Y, Wu L, Lin X, Gao J (2018) Multiview spectral clustering via structured low-rank matrix factorization. IEEE Trans Neural Networks and Learning Systems

  42. Wu L, Wang Y (2017) Robust hashing for multi-view data: jointly learning low-rank kernelized similarity consensus and hash functions. Image Vision Comput 57:58–66

    Article  Google Scholar 

  43. Wu L, Wang Y, Shepherd J (2013) Efficient image and tag co-ranking: a bregman divergence optimization method. In: ACM Multimedia Conference, MM ’13, Barcelona, Spain, October 21-25, 2013. https://dblp.org/rec/bib/conf/mm/WuWS13, pp 593–596

  44. Wu L, Wang Y, Gao J, Li X (2018) Deep adaptive feature embedding with local sample distributions for person re-identification. Pattern Recogn 73:275–288

    Article  Google Scholar 

  45. Wu L, Wang Y, Ge Z, Hu Q, Li X (2018) Structured deep hashing with convolutional neural networks for fast person re-identification. Comput Vis Image Underst 167:63–73

    Article  Google Scholar 

  46. Wu L, Wang Y, Li X, Gao J (2018) Deep attention-based spatially recursive networks for fine-grained visual recognition. IEEE Trans Cybernetics

  47. Wu L, Wang Y, Li X, Gao J (2018) What-and-where to match: deep spatially multiplicative integration networks for person re-identification. Pattern Recogn 76:727–738

    Article  Google Scholar 

  48. Xie Y, Yu H, Hu R (2014) Multimodal information joint learning for geotagged image search. In: 2013 IEEE International conference on multimedia and expo workshops, Chengdu, China, July 14-18, 2014, pp 1–6

  49. Zhang C, Zhang Y, Zhang W, Lin X (2013) Inverted linear quadtree: efficient top k spatial keyword search. In: 29th IEEE International Conference on Data Engineering, ICDE 2013, Brisbane, Australia, April 8-12, 2013, pp 901–912

  50. Zhang D, Tan K, Tung AKH (2013) Scalable top-k spatial keyword search. In: Joint 2013 EDBT/ICDT conferences, EDBT ’13 Proceedings, Genoa, Italy, March 18-22, 2013, pp 359–370

  51. Zhang D, Chan C, Tan K (2014) Processing spatial keyword query as a top-k aggregation query. In: The 37th international ACM SIGIR conference on research and development in information retrieval, SIGIR ’14, gold coast, QLD, Australia - July 06 - 11, 2014, pp 355–364

  52. Zhang C, Zhang Y, Zhang W, Lin X (2016) Inverted linear quadtree: efficient top K spatial keyword search. IEEE Trans Knowl Data Eng 28(7):1706–1721

    Article  Google Scholar 

  53. Zhao S, Yao H, Yang Y, Zhang Y (2014) Affective image retrieval via multi-graph learning. In: Proceedings of the ACM International Conference on Multimedia, MM ’14, Orlando, FL, USA, November 03 - 07, 2014, pp 1025–1028

  54. Zheng K, Su H, Zheng B, Shang S, Xu J, Liu J, Zhou X (2015) Interactive top-k spatial keyword queries. In: 31st IEEE International Conference on Data Engineering, ICDE 2015, Seoul, South Korea, April 13-17, 2015, pp 423–434

  55. Zhu L, Shen J, Jin H, Zheng R, Xie L (2015) Content-based visual landmark search via multimodal hypergraph learning. IEEE Trans Cybernetics 45(12):2756–2769

    Article  Google Scholar 

Download references

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China (61379110, 61472450, 61702560), the Key Research Program of Hunan Province (2016JC2018), project 2018JJ3691 of Science and Technology Plan of Hunan Province, and Fundamental Research Funds for Central Universities of Central South University (2018zzts588).

Author information

Authors and Affiliations

  1. School of Information Science and Engineering, Central South University, Changsha, People’s Republic of China

    Chengyuan Zhang, Ruipeng Chen, Lei Zhu, Anfeng Liu, Yunwu Lin & Fang Huang

  2. Big Data and Knowledge Engineering Institute, Central South University, Changsha, People’s Republic of China

    Chengyuan Zhang, Ruipeng Chen, Lei Zhu, Yunwu Lin & Fang Huang

Authors
  1. Chengyuan Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ruipeng Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Lei Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Anfeng Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Yunwu Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Fang Huang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Anfeng Liu.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhang, C., Chen, R., Zhu, L. et al. Hierarchical information quadtree: efficient spatial temporal image search for multimedia stream. Multimed Tools Appl 78, 30561–30583 (2019). https://doi.org/10.1007/s11042-018-6284-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11042-018-6284-y

Keywords

Search

Navigation