See-to-retrieve: efficient processing of spatio-visual keyword queries

ABSTRACT

The wide proliferation of powerful smart phones equipped with multiple sensors, 3D graphical engine, and 3G connection has nurtured the creation of a new spectrum of visual mobile applications. These applications require novel data retrieval techniques which we call What-You-Retrieve-Is-What-You-See (WYRIWYS). However, state-of-the-art spatial retrieval methods are mostly distance-based and thus inapplicable for supporting WYRIWYS. Motivated by this problem, we propose a novel query called spatio-visual keyword (SVK) query, to support retrieving spatial Web objects that are both visually conspicuous and semantically relevant to the user. To capture the visual features of spatial Web objects with extents, we introduce a novel visibility metric which computes object visibility in a cumulative manner. We propose an incremental method called Complete Occlusion-map based Retrieval (COR) to answer SVK queries. This method exploits effective heuristics to prune the search space and construct a data structure called Occlusion-Map. Then the method adopts the best-first strategy to return relevant objects incrementally. Extensive experiments on real and synthetic data sets suggest that our method is effective and efficient when processing SVK queries.

References

1. X. Cao, G. Cong, and C. S. Jensen. Retrieving top-k prestige-based relevant spatial web objects. PVLDB, 3(1):373--384, 2010.
2. X. Cao, G. Cong, C. S. Jensen, and B. C. Ooi. Collective spatial keyword querying. In SIGMOD Conference, pages 373--384, 2011.
3. Y.-Y. Chen, T. Suel, and A. Markowetz. Efficient query processing in geographic web search engines. In SIGMOD Conference, pages 277--288, 2006.
4. D. Cohen-Or, Y. Chrysanthou, C. T. Silva, and F. Durand. A survey of visibility for walkthrough applications. IEEE Trans. Vis. Comput. Graph., 9(3):412--431, 2003.
5. G. Cong, C. S. Jensen, and D. Wu. Efficient retrieval of the top-k most relevant spatial web objects. PVLDB, 2(1):337--348, 2009.
6. M. de Berg, M. van Kreveld, M. Overmars, and O. Cheong. Computational Geometry: Algorithms and Applications. Springer, second edition, 2000.
7. R. Fagin, A. Lotem, and M. Naor. Optimal aggregation algorithms for middleware. In PODS, 2001.
8. I. D. Felipe, V. Hristidis, and N. Rishe. Keyword search on spatial databases. In ICDE, pages 656--665, 2008.
9. Y. Gao, B. Zheng, G. Chen, W.-C. Lee, K. C. K. Lee, and Q. Li. Visible reverse k-nearest neighbor queries. In ICDE, pages 1203--1206, 2009.
10. Y. Gao, B. Zheng, W.-C. Lee, and G. Chen. Continuous visible nearest neighbor queries. In EDBT, pages 144--155, 2009.
11. A. Guttman. R-trees: a dynamic index structure for spatial searching. In SIGMOD, pages 47--57, 1984.
12. R. Hariharan, B. Hore, C. Li, and S. Mehrotra. Processing spatial-keyword (sk) queries in geographic information retrieval (gir) systems. In SSDBM, page 16, 2007.
13. M. Kofler, M. Gervautz, and M. Gruber. R-trees for organizing and visualizing 3d gis databases. Journal of Visualization and Computer Animation, 11(3):129--143, 2000.
14. K. C. K. Lee, W.-C. Lee, and H. V. Leong. Nearest surrounder queries. IEEE Trans. Knowl. Data Eng., 22(10):1444--1458, 2010.
15. S. Nutanong, E. Tanin, and R. Zhang. Incremental evaluation of visible nearest neighbor queries. IEEE Trans. Knowl. Data Eng., 22(5):665--681, 2010.
16. L. Shou, K. Chen, G. Chen, C. Zhang, Y. Ma, and X. Zhang. What-you-retrieve-is-what-you-see: a preliminary cyber-physical search engine. In SIGIR, pages 1273--1274, 2011.
17. L. Shou, Z. Huang, and K.-L. Tan. Hdov-tree: The structure, the storage, the speed. In ICDE, pages 557--568, 2003.
18. B. Yao, F. Li, M. Hadjieleftheriou, and K. Hou. Approximate string search in spatial databases. In ICDE, pages 545--556, 2010.
19. D. Zhang, Y. M. Chee, A. Mondal, A. K. H. Tung, and M. Kitsuregawa. Keyword search in spatial databases: Towards searching by document. In ICDE, pages 688--699, 2009.

Index Terms

• Information systems

  • Information retrieval

    • Information retrieval query processing