An efficient approach for continuous density queries  

作　　者：Jie WEN Xiaofeng MENG Xing HAO Jianliang XU 

机构地区：[1]School of Information,Renmin University of China,Beijing 100872,China [2]Department of Computer Science,Hong Kong Baptist University,Hong Kong,China

出　　处：《Frontiers of Computer Science》2012年第5期581-595,共15页中国计算机科学前沿（英文版）

摘　　要：In location-based services, a density query re- turns the regions with high concentrations of moving objects （MOs）. The use of density queries can help users identify crowded regions so as to avoid congestion. Most of the exist- ing methods try very hard to improve the accuracy of query results, but ignore query efficiency. However, response time is also an important concern in query processing and may have an impact on user experience. In order to address this issue, we present a new definition of continuous density queries. Our approach for processing continuous density queries is based on the new notion of a safe interval, using which the states of both dense and sparse regions are dynamically main- tained. Two indexing structures are also used to index candi- date regions for accelerating query processing and improving the quality of results. The efficiency and accuracy of our approach are shown through an experimental comparison with snapshot density queries.In location-based services, a density query re- turns the regions with high concentrations of moving objects （MOs）. The use of density queries can help users identify crowded regions so as to avoid congestion. Most of the exist- ing methods try very hard to improve the accuracy of query results, but ignore query efficiency. However, response time is also an important concern in query processing and may have an impact on user experience. In order to address this issue, we present a new definition of continuous density queries. Our approach for processing continuous density queries is based on the new notion of a safe interval, using which the states of both dense and sparse regions are dynamically main- tained. Two indexing structures are also used to index candi- date regions for accelerating query processing and improving the quality of results. The efficiency and accuracy of our approach are shown through an experimental comparison with snapshot density queries.

关 键 词：continuous density queries safe interval query efficiency 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论] TP311[自动化与计算机技术—计算机科学与技术]