Abstract
With the emergence of an infrastructure for location-aware mobile services, the processing of advanced, location-based queries that are expected to underlie such services is gaining in relevance. While much work has assumed that users move in Euclidean space, this paper assumes that movement is constrained to a road network and that points of interest can be reached via the network. More specifically, the paper assumes that the queries are issued by users moving along routes towards destinations. The paper defines in-route nearest-neighbor skyline queries in this setting and considers their efficient computation. The queries take into account several spatial preferences, and they intuitively return a set of most interesting results for each result returned by the corresponding non-skyline queries. The paper also covers a performance study of the proposed techniques based on real point-of-interest and road network data.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Benetis, R., Jensen, C.S., Karciauskas, G., Šaltenis, S.: Nearest Neighbor and Reverse Nearest Neighbor Queries for Moving Objects. In: Proc. IDEAS, pp. 44–53 (2002)
Borzsonyi, S., Kossmann, D., Stocker, K.: The Skyline Operator. In: Proc. ICDE, pp. 421–430 (2001)
Brilingaitė, A., Jensen, C.S., Zokaitė, N.: Enabling Routes as Context in Mobile Services. In: Proc. ACM GIS, pp. 127–136 (2004)
Chomicki, J., Godfrey, P., Gryz, J., Liang, D.: Skyline with Presorting. In: Proc. ICDE, pp. 717–816 (2003)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. The MIT Press, Cambridge (2001)
Frentzos, E.: Indexing Objects Moving on Fixed Networks. In: Hadzilacos, T., Manolopoulos, Y., Roddick, J., Theodoridis, Y. (eds.) SSTD 2003. LNCS, vol. 2750, pp. 289–305. Springer, Heidelberg (2003)
Guttman, A.: R-Trees: A Dynamic Index Structure for Spatial Searching. In: Proc. SIGMOD, pp. 47–57 (1984)
Hage, C., Jensen, C.S., Pedersen, T.B., Speičys, L., Timko, I.: Integrated Data Management for Mobile Services in the Real World. In: Proc. VLDB, pp. 1019–1030 (2003)
Jensen, C.S., Kolář, J., Pedersen, T.B., Timko, I.: Nearest Neighbor Queries in Road Networks. In: Proc. ACMGIS, pp. 1–8 (2003)
Knuth, D.E.: Art of Computer Programming. Sorting and Searching, vol. 3. Addison-Wesley Pub. Co., Reading (1998)
Kossmann, D., Ramsak, F., Rost, S.: Shooting Stars in the Sky: an Online Algorithm for Skyline Queries. In: Proc. VLDB, pp. 275–286 (2002)
Lu, H.X., Luo, Y., Lin, X.: An Optimal Divide-Conquer Algorithm for 2D Skyline Queries. In: Kalinichenko, L.A., Manthey, R., Thalheim, B., Wloka, U. (eds.) ADBIS 2003. LNCS, vol. 2798, pp. 46–60. Springer, Heidelberg (2003)
Pfoser, D., Jensen, C.S.: Indexing of Network Constrained Moving Objects. In: Proc. ACMGIS, pp. 25–32 (2003)
Papadias, D., Tao, Y., Fu, G., Seeger, B.: An Optimal and Progressive Algorithm for Skyline Queries. In: Proc. SIGMOD Conf., pp. 467–478 (2003)
Papadias, D., Zhang, J., Mamoulis, N., Tao, Y.: Query Processing in Spatial Network Databases. In: Proc. VLDB, pp. 802–813 (2003)
Roussopoulos, N., Kelley, S., Vincent, F.: Nearest Neighbor Queries. In: Proc. SIGMOD, pp. 71–79 (1995)
Speičys, L., Jensen, C.S., Kligys, A.: Computational Data Modeling for Network Constrained Moving Objects. In: Proc. ACMGIS, pp. 118–125 (2003)
Shahabi, C., Kolahdouzan, M.R., Sharifzadeh, M.: A Road Network Embedding Technique for K-Nearest Neighbor Search in Moving Object Databases. GeoInformatica 7(3), 255–273 (2003)
Song, Z., Roussopoulos, N.: K-Nearest Neighbor Search for Moving Query Point. In: Jensen, C.S., Schneider, M., Seeger, B., Tsotras, V.J. (eds.) SSTD 2001. LNCS, vol. 2121, pp. 79–96. Springer, Heidelberg (2001)
Shekhar, S., Yoo, J.S.: Processing In-Route Nearest Neighbor Queries: A Comparison of Alternative Approaches. In: Proc. ACMGIS, pp. 9–16 (2003)
Tan, K.L., Eng, P.K., Ooi, B.C.: Efficient Progressive Skyline Computation. In: Proc. VLDB, pp. 301–310 (2001)
Tao, Y., Papadias, D., Shen, Q.: Continuous Nearest Neighbor Search. In: Proc. VLDB, pp. 287–298 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Huang, X., Jensen, C.S. (2005). In-Route Skyline Querying for Location-Based Services. In: Kwon, YJ., Bouju, A., Claramunt, C. (eds) Web and Wireless Geographical Information Systems. W2GIS 2004. Lecture Notes in Computer Science, vol 3428. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11427865_10
Download citation
DOI: https://doi.org/10.1007/11427865_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26004-2
Online ISBN: 978-3-540-31964-1
eBook Packages: Computer ScienceComputer Science (R0)