Abstract
Processing sum k-Nearest Neighbor (NN) queries on remote spatial databases suffers from a large amount of communication. In this paper, we propose RQP-M search algorithm for efficiently searching sum k-NN query results to overcome the difficulty. It refines query results originally searched by RQP-S algorithm with subsequent k-NN queries, whose query points are chosen among vertices of a regular polygon inscribed in a before-searched circle. Experimental results show that Precision is over 0.99 for uniformly distributed data, over 0.95 for skew-distributed data, and over 0.97 for real data. Also, NOR (Number of Requests) ranges between 3.2 and 4.0, between 3.1 to 3.8, and between 2.9 and 3.5, respectively. Precision of RQP-M increases by 0.04-0.20 for uniformly distributed data, in comparison with that of RQP-S.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Guttman, A.: R-trees: A Dynamic Index Structure for Spatial Searching. In: Proc. ACM SIGMOD Int’l Conf. on Management of Data, pp. 47–57 (1984)
Sato, H.: Approximately Solving Aggregate k-Nearest Neighbor Queries over Web Services. In: Phillips-Wren, G., Jain, L.C., Nakamatsu, K., Howlett, R.J. (eds.) IDT 2010. SIST, vol. 4, pp. 445–454. Springer, Heidelberg (2010)
Sato, H.: Approximately Searching Aggregate k-Nearest Neighbors on Remote Spatial Databases Using Representative Query Points. In: Watanabe, T., Jain, L.C. (eds.) Innovations in Intelligent Machines – 2. SCI, vol. 376, pp. 91–102. Springer, Heidelberg (2012)
Ilarri, S., Menna, E., Illarramendi, A.: Location-Dependent Query Processing: Where We Are and Where We Are Heading. ACM Computing Survey 42(3), Article 12 (2010)
Roussopoulos, N., Kelly, S., Vincent, F.: Nearest Neighbor Queries. In: Proc. ACM SIGMOD Int’l Conf. on Management of Data, pp. 71–79 (1995)
Hjaltason, G.R., Samet, H.: Distance Browsing in Spatial Databases. ACM Trans. Database Systems 24(2), 265–318 (1999)
Korn, F., Muthukrishnan, S.: Influence Sets Based on Reverse Nearest Neighbor Queries. In: Proc. ACM SIGMOD Int’l Conf. on Management of Data, pp. 201–212 (2000)
Ferhatosmanoglu, H., Stanoi, I., Agrawal, D.P., El Abbadi, A.: Constrained Nearest Neighbor Queries. In: Jensen, C.S., Schneider, M., Seeger, B., Tsotras, V.J. (eds.) SSTD 2001. LNCS, vol. 2121, pp. 257–276. Springer, Heidelberg (2001)
Papadias, D., Shen, Q., Tao, Y., Mouratidis, K.: Group Nearest Neighbor Queries. In: Proc. Int’l Conf. Data Eng., pp. 301–312 (2004)
Yiu, M.L., Mamoulis, M., Papadias, D.: Aggregate Nearest Neighbor Queries in Road Networks. IEEE Trans. on Knowledge and Data Engineering 17(6), 820–833 (2005)
Nutanong, S., Tanin, E., Zhang, R.: Visible Nearest Neighbor Queries. In: Kotagiri, R., Radha Krishna, P., Mohania, M., Nantajeewarawat, E. (eds.) DASFAA 2007. LNCS, vol. 4443, pp. 876–883. Springer, Heidelberg (2007)
Liu, D., Lim, E., Ng, W.: Efficient k-Nearest Neighbor Queries on Remote Spatial Databases Using Range Estimation. In: Proc. SSDBM, pp. 121–130 (2002)
Bae, W.D., Alkobaisi, S., Kim, S.H., Narayanappa, S., Shahabi, C.: Supporting Range Queries on Web Data Using k-Nearest Neighbor Search. In: Ware, J.M., Taylor, G.E. (eds.) W2GIS 2007. LNCS, vol. 4857, pp. 61–75. Springer, Heidelberg (2007)
Xu, B., Wolfson, O.: Time-Series Prediction with Applications to Traffic and Moving Objects Databases. In: Proc. Third ACM Int’l Workshop on MobiDE, pp. 56–60 (2003)
Trajcevski, G., Wolfson, O., Xu, B., Nelson, P.: Managing Uncertainty in Moving Objects Databases. ACM Trans. Database Systems 29(3), 463–507 (2004)
Yu, P.S., Chen, S.K., Wu, K.L.: Incremental Processing of Continual Range Queries over Moving Objects. IEEE Trans. Knowl. Data Eng. 18(11), 1560–1575 (2006)
Nelder, J.A., Mead, R.: A Simplex Method for Function Minimization. Computational Journal, 308–313 (1965)
Trajcevski, G., Scheuermann, P.: Triggers and Continuous Queries in Moving Objects Database. In: Proc. 6th Int’l DEXA Workshop on Mobility in Databases and Distributed Systems, pp. 905–910 (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sato, H., Narita, R. (2012). Multistep Search Algorithm for Sum k-Nearest Neighbor Queries on Remote Spatial Databases. In: Watanabe, T., Watada, J., Takahashi, N., Howlett, R., Jain, L. (eds) Intelligent Interactive Multimedia: Systems and Services. Smart Innovation, Systems and Technologies, vol 14. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29934-6_37
Download citation
DOI: https://doi.org/10.1007/978-3-642-29934-6_37
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-29933-9
Online ISBN: 978-3-642-29934-6
eBook Packages: EngineeringEngineering (R0)