Abstract
In this paper, we propose a procedure for solving aggregate k-nearest neighbor (k-ANN) queries, which is effective in building location-based services (LBSs) by mashing up several Web services. In order to get the exact results of a k-ANN query, the Cartesian product has to be computed toward data of information sources, each of which is located at a different Web site. However, this requires a large amount of communication, because the entire data of at least one information source are sent to the other site. To reduce the cost, representative query point (RQP) is introduced to represent a set of query points and a k-nearest neighbor (k-NN) query with RQP as a key is requested to disseminate information of data objects. Although it computes an approximate result, the experimental results with synthetic data on precision and recall length ratio show that a k-NN query result with the minimal point of sum distance as RQP is allowable for a sum k-NN query result and a k-NN query result with the minimal point of max distance as RQP is allowable for a max k-NN query result regarding some combinations of k and the number of query points.
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
Nutanong, S., Zhang, R., Tanin, E., Kulik, L.: The V*-Diagram: A query-dependent approach to moving kNN queries. In: Proc. Int’l Conf. VLDB, pp. 1095–1106 (2008)
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)
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)
Fagin, R., Lotem, A., Naor, M.: Optimal Aggregation Algorithms for Middleware. In: Proc. Symp. Principles of Database Systems, pp. 102–113 (2001)
Ilyas, H.F., Beskales, G., Soliman, M.A.: A Survey of Top-k Query Processing Techniques in Relational Database Systems. ACM Computing Survey 40(4), Article 11 (2008)
Berg, M.D., Kreveld, M.V., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications. Springer, Heidelberg (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer Berlin Heidelberg
About this paper
Cite this paper
Sato, H. (2010). Approximately Solving Aggregate k-Nearest Neighbor Queries over Web Services. In: Phillips-Wren, G., Jain, L.C., Nakamatsu, K., Howlett, R.J. (eds) Advances in Intelligent Decision Technologies. Smart Innovation, Systems and Technologies, vol 4. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14616-9_43
Download citation
DOI: https://doi.org/10.1007/978-3-642-14616-9_43
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-14615-2
Online ISBN: 978-3-642-14616-9
eBook Packages: EngineeringEngineering (R0)