Processing spatial skyline queries in both vector spaces and spatial network databases

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Processing spatial skyline queries in both vector spaces and spatial network databases

Full text

Pdf (2.14 MB)

Source

ACM Transactions on Database Systems (TODS) archive
Volume 34 , Issue 3 (August 2009) table of contents

Article No. 14

Year of Publication: 2009

ISSN:0362-5915

Authors

Mehdi Sharifzadeh	University of Southern California, Los Angeles, CA
Cyrus Shahabi	University of Southern California, Los Angeles, CA
Leyla Kazemi	University of Southern California, Los Angeles, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 67, Downloads (12 Months): 138, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1567274.1567276 What is a DOI?

ABSTRACT

In this article, we first introduce the concept of Spatial Skyline Queries (SSQ). Given a set of data points P and a set of query points Q, each data point has a number of derived spatial attributes each of which is the point's distance to a query point. An SSQ retrieves those points of P which are not dominated by any other point in P considering their derived spatial attributes. The main difference with the regular skyline query is that this spatial domination depends on the location of the query points Q. SSQ has application in several domains such as emergency response and online maps. The main intuition and novelty behind our approaches is that we exploit the geometric properties of the SSQ problem space to avoid the exhaustive examination of all the point pairs in P and Q. Consequently, we reduce the complexity of SSQ search from O(|P|²|Q|) to O(|S|²|C| + &sqrt;|P|), where |S| and |C| are the solution size and the number of vertices of the convex hull of Q, respectively.

Considering Euclidean distance, we propose two algorithms, B²S² and VS², for static query points and one algorithm, VCS², for streaming Q whose points change location over time (e.g., are mobile). VCS² exploits the pattern of change in Q to avoid unnecessary recomputation of the skyline and hence efficiently perform updates. We also propose two algorithms, SNS² and VSNS², that compute the spatial skyline with respect to the network distance in a spatial network database. Our extensive experiments using real-world datasets verify that both R-tree-based B²S² and Voronoi-based VS² outperform the best competitor approach in terms of both processing time and I/O cost. Furthermore, their output computed based on Euclidean distance is a good approximation of the spatial skyline in network space. For accurate computation of spatial skylines in network space, our experiments showed the superiority of VSNS² over SNS².

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Barber, C. B., Dobkin, D. P., and Huhdanpaa, H. 1996. The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. 22, 4, 469--483.
	2	Börzsönyi, S., Kossmann, D., and Stocker, K. 2001. The skyline operator. In Proceedings of the International Conference on Data Engineering (ICDE'01). 421--430.
	3	Chomicki, J., Godfrey, P., Gryz, J., and Liang, D. 2003. Skyline with presorting. In Proceedings of the International Conference on Data Engineering (ICDE'03). IEEE Computer Society, 717--816.
	4	de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. 2000. Computational Geometry: Algorithms and Applications 2nd Ed. Springer Verlag.
	5	Huang, X. and Jensen, C. S. 2004. In-route skyline querying for location-based services. In Proceedings of the 4th International Workshop on Web and Wireless Geographical Information Systems (W2GIS'04). Vol. 3428. Springer, 120--135.
	6	Huang, Z., Jensen, C. S., Lu, H., and Ooi, B. C. 2006. Skyline queries against mobile lightweight devices in MANETs. In Proceedings of the International Conference on Data Engineering (ICDE'06). IEEE Computer Society.
	7	Kolahdouzan, M. and Shahabi, C. 2004. Voronoi-based k nearest neighbor search for spatial network databases. In Proceedings of the International Conference on Very Large Databases. Morgan Kaufmann, 840--851.
	8	Kossmann, D., Ramsak, F., and Rost, S. 2002. Shooting stars in the sky: An online algorithm for skyline queries. In Proceedings of the International Conference on Very Large Databases (VLDB'02). 275--286.
	9	Lin, X., Yuan, Y., Wang, W., and Lu, H. 2005. Stabbing the sky: Efficient skyline computation over sliding windows. In Proceedings of the International Conference on Data Engineering (ICDE'05). IEEE Computer Society, 502--513.
	10	Okabe, A., Boots, B., Sugihara, K., and Chiu, S. N. 2000. Spatial Tessellations: Concepts and Applications of Voronoi Diagrams 2nd Ed. Probability and Statistics. Wiley, New York. 671 pages.
	11	Papadias, D., Tao, Y., Fu, G., and Seeger, B. 2005a. Progressive skyline computation in database systems. ACM Trans. Datab. Syst. 30, 1, 41--82.
	12	Papadias, D., Tao, Y., Mouratidis, K., and Hui, C. K. 2005b. Aggregate nearest neighbor queries in spatial databases. ACM Trans. Datab. Syst. 30, 2, 529--576.
	13	Sharifzadeh, M. and Shahabi, C. 2006. The spatial skyline queries. In Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB'06). 751--762.
	14	Tan, K.-L., Eng, P.-K., and Ooi, B. C. 2001. Efficient progressive skyline computation. In Proceedings of the International Conference on Very Large Databases (VLDB'01). 301--310.
	15	Theodoridis, Y. and Nascimento, M. A. 2000. Generating spatiotemporal datasets on the WWW. SIGMOD Rec. 29, 3, 39--43.