Efficient Framework for Group Nearest Group Query

Authors(2) :-P. Damodharan, Dr. C. S. Ravichandran

The Efficient Nearest Neighbor group query (ENNGQ) uses group points to provide the optimal solution for the nearest group point in the dataset. The novel type of spatial keyword query called Group Nearest Group (GNG) query will be used to optimize the query. Given a data point set D, a query point set Q and an integer k, the Group Nearest Group query finds a subset of points from D, ω (|ω| ≤ k), such that the total distance from all points in Q to the nearest point in ω is no greater than any other subset of points in D. Each nearest point obtained matches at least one of the query keywords. For processing this query several algorithms are proposed. The processing of ENNGQ query consists of a Data Classifier with De-duplicator Block (DCDB ), Most Frequent Search Cache Engine ( MFSCE ) and Exhaustive Subset Refinement algorithm ( ESRA) . A ENNGQ query returns the location of a meeting place that minimizes the aggregate distance from a spread out group of users. For example, a group of users can look for a restaurant that serves Chinese dishes that minimizes the total travel distance from them. The duplicates in the dataset can be identified to improve the search query from the given data using the DCDB.. The data can also be grouped in such a manner that it can be used for efficient retrieval. The MFSCE is a Deterministic Cache engine which helps to store the most frequently accessed keyword and the location with respect to a reference point. Finally the ESRA is a local search heuristic with the current best value is refined by visiting the child nodes of the block using bounded Priority queues. In order to prune large portion of query objects reducing the number of node accesses, this extensive experiments on spatial databases is effective in reducing group query response time which exhibits good scalability with the query objects and the number of query.

Authors and Affiliations

P. Damodharan
Department of Computer Science and Engineering, Akshaya College of Engineering and Technology, Coimbatore, Tamil Nadu, India
Dr. C. S. Ravichandran
Department of Electrical and Electronics Engineering, Sri Ramakrishna Engineering College, Coimbatore, Tamil Nadu, India

Spatial Data Mining, Boolean spatial keyword query, reverse k Boolean spatial keyword query, Nearest Neighbor group query

  1. YunjunGao,Baihua Zheng and Gang Chen "Efficient Reverse Top-k Boolean Spatial Keyword Queries on Road Networks". Ieee transactions on knowledge and data engineering, VOL. 27, NO. 5, MAY 2015
  2. AlexandrAndoni and Piotr Indyk. “Near-optimal hashing algorithms for approximate nearest Neighbor in high dimensions”. In: Foundations of Computer Science, 2006. FOCS’06. 47th Annual IEEE Symposium on. IEEE. 2006, pp. 459-468.
  3. Sunil Arya et al. “An optimal algorithm for approximate nearest Neighbor searching fixed dimensions”. Journal of the ACM (JACM) 45.6 (1998), pp. 891-923.
  4. Wei Dong, Charikar Moses, and Kai Li. “Efficient k-nearest Neighbor graph construction for generic similarity measures”. In: Proceedings of the 20th international conference on World wide web. ACM. 2011,pp. 577-586.
  5. X. Cao, L. Chen, G. Cong, C. S. Jensen, Q. Qu, A. Skovsgaard, D. Wu, and M. L. Yiu, “Spatial keyword querying,” in Proc. Int.Conf. Conceptual Model., 2012, pp. 16-29.
  6. A. Cary, O. Wolfson, and N. Rishe, “Efficient and scalable method for processing top-k spatial Boolean queries,” in Proc. Int. Conf. Sci. Statistical Database Manage., 2010, pp. 87-95.
  7. Y. Gao, B. Zheng, G. Chen, W.-C. Lee, K. C. Lee, and Q. Li, “Visible reverse k-nearest Neighbor query processing in partial databases,” IEEE Trans. Knowl. Data Eng., vol. 21, no. 9, pp. 1314-1327, Sep. 2009.
  8. F. Korn and S. Muthukrishnan, “Influence sets based on reverse nearest Neighbor queries,” in Proc. ACM SIGMOD Int. Conf.Manage. Data, 2000, pp. 201-212.
  9. M. A. Cheema, W. Zhang, X. Lin, Y. Zhang, and X. Li, “Continuous reverse k nearest Neighbors queries in Euclidean space and in spatial networks,” VLDB J., vol. 21, no. 1, pp. 69-95, Feb. 2012.
  10. G. Li, Y. Li, J. Li, L. Shu, and F. Yang, “Continuous reverse k nearest Neighbor monitoring on moving objects in road networks,” Inf. Syst., vol. 35, no. 8, pp. 860-883, Dec. 2010.
  11. Kiana Hajebi et al. “Fast approximate nearestNeighbor search with k-nearest Neighbor graph”. In: IJCAI Proceedings- International Joint Conference on Artificial Intelligence. Vol. 22. 1. 2011, p. 1312.
  12. KeinosukeFukunaga and Patrenahalli M Narendra. “A branch and bound algorithm for computing knearestNeighbors”. Computers, IEEE Transactions on 100.7 (1975), pp. 750-753.
  13. D. Zhang, K. L. Tan, and A. K. H. Tung, “Scalable top-k spatial keyword search,” in Proc. Int. Conf. Extending Database Technol., 2013, pp. 359-370.
  14. J. Lu, Y. Lu, and G. Cong, “Reverse spatial and textual k nearest Neighbor search,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2011, pp. 349-360.
  15. J. B. Rocha-Junior, O. Gkorgkas, S. Jonassen, and K. Norvag, “Efficient processing of top-k spatial keyword queries,” in Proc. Int. Symp. Advances Spatial Temporal Databases, 2011, pp. 205-222.

Publication Details

Published in : Volume 2 | Issue 1 | January-February 2016
Date of Publication : 2016-01-30
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 649-656
Manuscript Number : IJSRSET1738133
Publisher : Technoscience Academy

Print ISSN : 2395-1990, Online ISSN : 2394-4099

Cite This Article :

P. Damodharan, Dr. C. S. Ravichandran, " Efficient Framework for Group Nearest Group Query, International Journal of Scientific Research in Science, Engineering and Technology(IJSRSET), Print ISSN : 2395-1990, Online ISSN : 2394-4099, Volume 2, Issue 1, pp.649-656, January-February-2016.
Journal URL : http://ijsrset.com/IJSRSET1738133

Follow Us

Contact Us