A Novel Multi Scale Index for Exact and Approximate NKS Query Processing

Petta Susmita, K V V Ramana, M. Veerabhadra Rao


Keyword based search in content rich multi-dimensional datasets encourages numerous novel applications and devices. In this paper, we consider objects that are labeled with Keywords and are implanted in a vector space. For these datasets, we consider questions that request the most impenetrable gatherings of focuses fulfilling a given arrangement of Keywords. We propose a novel strategy called ProMiSH (Projection and Multi Scale Hashing) that utilizations arbitrary projection and hash-based list structures, and accomplishes high versatility and speedup. We introduce a correct and an inexact variant of the algorithm.


W. Li and C. X. Chen, “Efficient data modeling and querying system for multi-dimensional spatial data,” in Proc. 16th ACM SIGSPATIAL Int. Conf. Adv. Geographic Inf. Syst., 2008, pp. 58:1– 58:4.

D. Zhang, B. C. Ooi, and A. K. H. Tung, “Locating mapped resources in web 2.0,” in Proc. IEEE 26th Int. Conf. Data Eng., 2010, pp. 521–532.

V. Singh, S. Venkatesha, and A. K. Singh, “Geo-clustering of images with missing geotags,” in Proc. IEEE Int. Conf. Granular Comput., 2010, pp. 420–425.

V. Singh, A. Bhattacharya, and A. K. Singh, “Querying spatial patterns,” in Proc. 13th Int. Conf. Extending Database Technol.: Adv.

Database Technol., 2010, pp. 418–429.

J. Bourgain, “On lipschitz embedding of finite metric spaces in hilbert space,” Israel J. Math., vol. 52, pp. 46–52, 1985.

H. He and A. K. Singh, “GraphRank: Statistical modeling and mining of significant subgraphs in the feature space,” in Proc. 6th Int. Conf. Data Mining, 2006, pp. 885–890.

X. Cao, G. Cong, C. S. Jensen, and B. C. Ooi, “Collective spatial keyword querying,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2011, pp. 373–384.

C. Long, R. C.-W. Wong, K. Wang, and A. W.-C. Fu, “Collective spatial keyword queries: A distance owner-driven approach,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2013, pp. 689–700.

D. Zhang, Y. M. Chee, A. Mondal, A. K. H. Tung, and M. Kitsuregawa, “Keyword search in spatial databases: Towards searching by document,” in Proc. IEEE 25th Int. Conf. Data Eng., 2009, pp. 688–699.

M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni, “Localitysensitive hashing scheme based on p-stable distributions,” in Proc. 20th Annu.Symp.Comput. Geometry, 2004, pp. 253–262.

Y. Zhou, X. Xie, C. Wang, Y. Gong, and W.-Y.Ma, “Hybrid index structures for location-based web search,” in Proc. 14th ACM Int. Conf. Inf. Knowl.Manage., 2005, pp. 155–162.

R. Hariharan, B. Hore, C. Li, and S. Mehrotra, “Processing spatialkeyword (SK) queries in geographic information retrieval (GIR) systems,” in Proc. 19th Int. Conf. Sci. Statistical Database Manage., 2007, p. 16.

S. Vaid, C. B. Jones, H. Joho, and M. Sanderson, “Spati o-textualindexing for geographical search on the web,” in Proc. 9th Int. Conf. Adv. Spatial Temporal Databases, 2005, pp. 218–235.

A. Khodaei, C. Shahabi, and C. Li, “Hybrid indexing and seamless ranking of spatial and textual features of web documents,” in Proc. 21st Int. Conf. Database Expert Syst. Appl., 2010, pp. 450–466.

A. Guttman, “R-trees: A dynamic index structure for spatial searching,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 1984, pp. 47–57.

Full Text: PDF [Full Text]


  • There are currently no refbacks.

Copyright © 2013, All rights reserved.| ijseat.com

Creative Commons License
International Journal of Science Engineering and Advance Technology is licensed under a Creative Commons Attribution 3.0 Unported License.Based on a work at IJSEat , Permissions beyond the scope of this license may be available at http://creativecommons.org/licenses/by/3.0/deed.en_GB.