Abstract
Recent research has focused on density queries for moving objects in highly dynamic scenarios. An area is dense if the number of moving objects it contains is above some threshold. Monitoring dense areas has applications in traffic control systems, bandwidth management, collision probability evaluation, etc. All existing methods, however, assume the objects moving in the Euclidean space. In this paper, we study the density queries in road networks, where density computation is determined by the length of the road segment and the number of objects on it. We define an effective road-network density query guaranteeing to obtain useful answers. We then propose the cluster-based algorithm for the efficient computation of density queries for objects moving in road networks. Extensive experimental results show that our methods achieve high efficiency and accuracy for finding the dense areas in road networks.
This research was partially supported by the grants from the Natural Science Foundation of China under grant number 60573091; Program for New Century Excellent Talents in University (NCET).
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
Cho, H.-J., Chung, C.-W.: An Efficient and Scalable Approach to CNN Queries in a Road Network. In: VLDB 2005, pp. 865–876 (2005)
Hadjieleftheriou, M., Kollios, G., Gunopulos, D., Tsotras, V.J.: On-Line Discovery of Dense Areas in Spatio-temporal Databases. In: Hadzilacos, T., Manolopoulos, Y., Roddick, J.F., Theodoridis, Y. (eds.) SSTD 2003. LNCS, vol. 2750, pp. 306–324. Springer, Heidelberg (2003)
Jain, A.K., Dubes, R.C.: Algorithms for Clustering Data. Prentice-Hall, Englewood Cliffs (1988)
Jensen, C.S., Lin, D., Ooi, B.C., Zhang, R.: Effective Density Queries on Continuously Moving Objects. In: ICDE 2006, p. 71 (2006)
Karypis, G., Han, E.-H., Kumar, V.: Chameleon: Hierarchical clustering using dynamic modeling. IEEE Computer 32(8), 68–75 (1999)
Li, Y., Han, J., Yang, J.: Clustering moving objects. In: KDD, pp. 617–622 (2004)
Mouratidis, K., Yiu, M.L., Papadias, D., Mamoulis, N.: Continuous Nearest Neighbor Monitoring in Road Networks. In: VLDB 2006, pp. 43–54 (2006)
Papadias, D., Zhang, J., Mamoulis, N., Tao, Y.: Query Processing in Spatial Network Databases. In: VLDB, pp. 802–813 (2003)
Stojanovic, D., Djordjevic-Kajan, S., Papadopoulos, A.N., Nanopoulos, A.: Continuous Range Query Processing for Network Constrained Mobile Objects. In: ICEIS, vol. 1, pp. 63–70 (2006)
Yiu, M.L., Mamoulis, N.: Clustering Objects on a Spatial Network. In: SIGMOD, pp. 443–454 (2004)
Yiu, M.L., Mamoulis, N., Papadias, D.: Aggregate Nearest Neighbor Queries in Road Networks. IEEE Trans. Knowl. Data Eng. 17(6), 820–833 (2005)
Yiu, M.L., Papadias, D., Mamoulis, N., Tao, Y.: Reverse Nearest Neighbors in Large Graphs. IEEE Trans. Knowl. Data Eng. 18(4), 540–553 (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer Berlin Heidelberg
About this paper
Cite this paper
Lai, C., Wang, L., Chen, J., Meng, X., Zeitouni, K. (2007). Effective Density Queries for Moving Objects in Road Networks. In: Dong, G., Lin, X., Wang, W., Yang, Y., Yu, J.X. (eds) Advances in Data and Web Management. APWeb WAIM 2007 2007. Lecture Notes in Computer Science, vol 4505. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72524-4_23
Download citation
DOI: https://doi.org/10.1007/978-3-540-72524-4_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72483-4
Online ISBN: 978-3-540-72524-4
eBook Packages: Computer ScienceComputer Science (R0)