Computer Science ›› 2015, Vol. 42 ›› Issue (1): 201-205.doi: 10.11896/j.issn.1002-137X.2015.01.045

Previous Articles     Next Articles

Probabilistic Threshold Reverse Nearest Neighbor Queries for Indoor Moving Objects

WANG Li, QIN Xiao-lin and XU Jian-qiu   

  • Online:2018-11-14 Published:2018-11-14

Abstract: Indoor spaces are becoming increasingly large and complex,and more and more demand for initiating indoor spatial queries has emerged.Range queries and nearest neighbor queries specifically for indoor space have been proposed,while there are no studies on reverse nearest neighbor queries.Thus,this paper presented the formal definition of probabilistic threshold reverse nearest neighbor query (IPRNN) for indoor moving objects and a device reachable graph model.The query processing algorithm of IPRNN was proposed based on the graph model.The algorithm consists of four parts:model pruning,indoor distance pruning,probability pruning and probability calculation.The objects that are not likely to appear in the result set are built out through pruning strategy,thereby significantly reducing the search space and improving efficiency.

Key words: Indoor space,Reverse nearest neighbor,Device reachable graph model,Query processing

[1] Jensen C S,Li K J,Winter S.The other 87%:a report on The Second International Workshop on Indoor Spatial Awareness (San Jose,California-November 2,2010)[J].SIGSPATIAL Special,2011,3(1):10-12
[2] http://finance.sina.com.cn/money/consume9/20041025/10361104770.shtml
[3] Yang B,Lu H,Jensen C S.Scalable continuous range monitoring of moving objects in symbolic indoor space[C]∥Proceedings of the 18th ACM Conference on Information and Knowledge Mana-gement.ACM,2009:671-680
[4] Lu H,Yang B,Jensen C S.Spatio-temporal joins on symbolic in-door tracking data[C]∥2011 IEEE 27th International Confe-rence on Data Engineering (ICDE).IEEE,2011:816-827
[5] Yuan W,Schneider M.Supporting continuous range queries in indoor space[C]∥2010 Eleventh International Conference on Mobile Data Management (MDM).IEEE,2010:209-214
[6] Lu H,Cao X,Jensen C S.A foundation for efficient indoor distance-aware query processing[C]∥2012 IEEE 28th InternationalConference on Data Engineering (ICDE).IEEE,2012:438-449
[7] Yu J,Ku W S,Sun M T,et al.An RFID and particle filter-based indoor spatial query evaluation system[C]∥Proceedings of the 16th International Conference on Extending Database Technology.ACM,2013:263-274
[8] Xie X,Lu H,Pedersen T B.Efficient distance-aware query eva-luation on indoor moving objects[C]∥ICDE.2013
[9] 甘早斌,袁永光,赵贻竹,等.基于DR-tree的室内移动对象索引研究 [J].计算机科学,2012,39(10):177-181
[10] Yang B,Lu H,Jensen C S.Probabilistic threshold k nearestneighbor queries over moving objects in symbolic indoor space[C]∥Proceedings of the 13th International Conference on Extending Database Technology.ACM,2010:335-346
[11] Korn F,Muthukrishnan S.Influence sets based on reverse nearest neighbor queries[J].ACM SIGMOD Record,2000,29(2):201-212
[12] Stanoi I,Agrawal D,El Abbadi A.Reverse Nearest NeighborQueries for Dynamic Databases[C]∥ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery.2000:44-53
[13] Tao Y,Papadias D,Lian X.Reverse kNN search in arbitrary dimensionality[C]∥Proceedings of the Thirtieth international conference on Very large data bases-Volume 30.VLDB Endowment,2004:744-755
[14] Lian X,Chen L.Efficient processing of probabilistic reverse nearest neighbor queries over uncertain data[J].The VLDB Journal—The International Journal on Very Large Data Bases,2009,18(3):787-808
[15] Cheema M A,Lin X,Wang W,et al.Probabilistic reverse nearest neighbor queries on uncertain data[J].IEEE Transactions on Knowledge and Data Engineering,2010,22(4):550-564
[16] Bernecker T,Emrich T,Kriegel H P,et al.Efficient probabilistic reverse nearest neighbor query processing on uncertain data[J].Proceedings of the VLDB Endowment,2011,4(10):669-680
[17] Whiting E,Battat J,Teller S.Topology of urban environments[M]∥Computer-Aided Architectural Design Futures (CAADFutures) 2007.Springer Netherlands,2007:114-128
[18] Lee J.3D GIS for geo-coding human activity in micro-scale urban environments[M]∥Geographic Information Science.Springer Berlin Heidelberg,2004:162-178
[19] Jensen C S,Lu H,Yang B.Graph model based indoor tracking[C]∥Tenth International Conference on Mobile Data Management:Systems,Services and Middleware,2009(MDM’09).IEEE,2009:122-131
[20] Stoffel E P,Schoder K,Ohlbach H J.Applying hierarchicalgraphs to pedestrian indoor navigation[C]∥Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems.ACM,2008:54
[21] Lorenz B,Ohlbach H J,Stoffel E P.A hybrid spatial model for representing indoor environments[M]∥Web and Wireless Geographical Information Systems.Springer Berlin Heidelberg,2006:102-112

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!