障碍空间中不确定对象的组k最近邻查询方法
|
摘要
针对障碍空间中不确定对象的组k最近邻查询问题,提出了Pk OGNN(probabilistic k obstructed group nearest neighbor query)查询方法。Pk OGNN查询方法主要包括4个子算法:Compadist_o(),SpatialPru(),PruInterEnt()和PkOGNN(),这些子算法分别是集总障碍距离的计算方法、空间修剪方法、根据空间修剪方法进行R树中间结点修剪、最终精炼查询方法。所提Pk OGNN查询方法通过集成有效的修剪策略以便减少Pk OGNN的搜索空间,得到正确的k GNNs。理论研究和实验结果表明,所提方法具有较好的性能。
To deal with the problem of group k-nearest neighbor query method for uncertainty data in obstructed spaces,this paper presents the method of the Pk OGNN( probabilistic k obstructed group nearest neighbor) query.The Pk OGNN query method mainly includes four sub-algorithms: Compadist _o(),SpatialPru(),PruInterEnt()and PkOGNN(),These algorithms are respectively the calculation of the aggregate obstructed distance,the spatial pruning method,the pruning of the R-tree intermediate items according to the spatial pruning method,the final refined query method. It integrates the effective pruning methods to reduce the search space of Pk OGNN and get the correct k GNNs. The theoretical research and experimental results show that the proposed method has good efficiency.
To deal with the problem of group k-nearest neighbor query method for uncertainty data in obstructed spaces,this paper presents the method of the Pk OGNN( probabilistic k obstructed group nearest neighbor) query.The Pk OGNN query method mainly includes four sub-algorithms: Compadist _o(),SpatialPru(),PruInterEnt()and PkOGNN(),These algorithms are respectively the calculation of the aggregate obstructed distance,the spatial pruning method,the pruning of the R-tree intermediate items according to the spatial pruning method,the final refined query method. It integrates the effective pruning methods to reduce the search space of Pk OGNN and get the correct k GNNs. The theoretical research and experimental results show that the proposed method has good efficiency.
引文
[1]SUN W,CHEN C,ZHENG B,et al.Merged Aggregate Nearest Neighbor Query Processing in Road Networks[C]//CIKM,2013:2243.
[2]陈舒,蒋志会,陆恒,等.路网环境中关于模糊组最近邻问题的研究[J].计算机应用研究,2016,33(2):333.
[3]HASHEM T,KULIK L,ZHANG R.Privacy Preserving Group Nearest Neighbor Queries[C]//EDBT,2010:489.
[4]刘晓乐,李博.隐私保护下的组最近邻查询算法研究[J].计算机应用与软件.2016,33(5):302.
[5]GAO Yunjun,ZHENG Baihua.Continuous Obstructed Nearest Neighbor Queries in Spatial Databases[C]//Proceedings of the28th ACM SIGMOD International Conference of Management of Data,2009,9(4):577.
[6]SULTANA N,HASHEM T,KULIK L.Group Nearest Neighbor Queries in the Presence of Obstacles[C]//International Conference on Advances in GIS,2014:481.
[7]MOKBEL MF,CHOW CY,AREF WG.The Newcasper:Query Processing for Location Services Without Compromising Privacy[C]//International Conference on Very Large Data Bases,2009,34(4):763.
[8]HUANG Yuan-Ko,CHEN Chao-Chun,LEE Chiang.Continuous k-nearest Neighbor Query for Moving Objects with Uncertain Velocity[J].Geoinformatica,2009,13(1):1.
[9]孙冬璞,郝晓红,高爽,等.概率可视最近邻查询算法[J].哈尔滨理工大学学报,2013,18(6):58.
[10]SACK JUJR.Handbook of Computational Geometry[M].Ottawa:Elsevier Science,2000:829.
[11]李传文,谷峪,李芳芳,等.一种障碍空间中不确定对象的连续最近邻查询方法[J].计算机学报,2010,33(8):1359.
[12]PAPADIAS D,SHEN Qiongmao,TAO Yufei,et al.Group Nearest Neighbor Queries[C]//ICDE,2004,312.
[13]SULTANA Nusrat,HASHEM Tanzima,KULIK Lars.Group Nearest Neighbor Queries in the Presence of Obstacles[J].International Conference on Advances in GIS,2014:481.
[14]LIAN X,CHEN L.Probabilistic Group Nearest Neighbor Queries in Uncertain Databases[J].IEEE Transactions on Knowledge&Data Engineering,2008,20(6):809.
[2]陈舒,蒋志会,陆恒,等.路网环境中关于模糊组最近邻问题的研究[J].计算机应用研究,2016,33(2):333.
[3]HASHEM T,KULIK L,ZHANG R.Privacy Preserving Group Nearest Neighbor Queries[C]//EDBT,2010:489.
[4]刘晓乐,李博.隐私保护下的组最近邻查询算法研究[J].计算机应用与软件.2016,33(5):302.
[5]GAO Yunjun,ZHENG Baihua.Continuous Obstructed Nearest Neighbor Queries in Spatial Databases[C]//Proceedings of the28th ACM SIGMOD International Conference of Management of Data,2009,9(4):577.
[6]SULTANA N,HASHEM T,KULIK L.Group Nearest Neighbor Queries in the Presence of Obstacles[C]//International Conference on Advances in GIS,2014:481.
[7]MOKBEL MF,CHOW CY,AREF WG.The Newcasper:Query Processing for Location Services Without Compromising Privacy[C]//International Conference on Very Large Data Bases,2009,34(4):763.
[8]HUANG Yuan-Ko,CHEN Chao-Chun,LEE Chiang.Continuous k-nearest Neighbor Query for Moving Objects with Uncertain Velocity[J].Geoinformatica,2009,13(1):1.
[9]孙冬璞,郝晓红,高爽,等.概率可视最近邻查询算法[J].哈尔滨理工大学学报,2013,18(6):58.
[10]SACK JUJR.Handbook of Computational Geometry[M].Ottawa:Elsevier Science,2000:829.
[11]李传文,谷峪,李芳芳,等.一种障碍空间中不确定对象的连续最近邻查询方法[J].计算机学报,2010,33(8):1359.
[12]PAPADIAS D,SHEN Qiongmao,TAO Yufei,et al.Group Nearest Neighbor Queries[C]//ICDE,2004,312.
[13]SULTANA Nusrat,HASHEM Tanzima,KULIK Lars.Group Nearest Neighbor Queries in the Presence of Obstacles[J].International Conference on Advances in GIS,2014:481.
[14]LIAN X,CHEN L.Probabilistic Group Nearest Neighbor Queries in Uncertain Databases[J].IEEE Transactions on Knowledge&Data Engineering,2008,20(6):809.