Computer Science

Computer Science ›› 2021, Vol. 48 ›› Issue (6): 57-62.doi: 10.11896/jsjkx.200700016

• Database & Big Data & Data Science • Previous Articles     Next Articles

Study on Why-not Problem in Skyline Query of Road Network Based on Query Object

ZHU Run-ze, QIN Xiao-lin, LIU Jia-chen   

  1. College of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 211106,China
  • Received:2020-07-02 Revised:2020-11-10 Online:2021-06-15 Published:2021-06-03
  • About author:ZHU Run-ze,born in 1996,postgra-duate.His main research interests include skyline query and so on.(1165248566@qq.com)
    QIN Xiao-lin,born in 1953,Ph.D,professor,is a senior member of China Computer Federation.His main research interests include spatial and spatio-temporal database,data management and security in distributed environment,etc.
  • Supported by:
    National Natural Science Foundation of China(61728204).

PDF (PC)

570

Abstract: With the rapid development of information technology,data becomes an important strategic resource.How to use big data to query is the research content of many scholars.At the same time,when the queried objects are not selected,how to use big data to meet the query requirements of users has also become an important research direction.Based on the analysis of the shortcomings of the existing algorithms,according to the characteristics of the real life queries,this paper studies the why-not problem in the Skyline query of the road network based on the query object,and puts forward the attribute optimization algorithm for this problem.The algorithm includes modifying the spatial and non spatial attributes of why-not point,as well as modifying the location of query center.Considering the actual situation,the time attribute is considered separately rather than simply as one dimension of non spatial attribute.The algorithm adopts pruning strategy to improve the efficiency.Finally,the real road network data and the generated interest point data set are used for comparative experiments.The results show that the method of modifying the spatial and non spatial attributes at the same time in a specific period of time can effectively solve this problem.

Key words: Prune, Road network, Skyline query, Spatiotemporal attribute, Why-not problem

CLC Number: 

  • TP311
[1]LIN X,XU J,HU H.Range-based skyline queries in mobile environment[J].IEEE Transactions on Knowledge and Data Engineering,2013,25(4):835-849.
[2]BORZSONY S,KOSSMANN D,STOCKER K.The skylineoperator[C]//IEEE International Conference on Data Enginee-ring.2001:421-430.
[3]HUANG X,JENSEN C S.In-route skyline querying for location-based services[C]//Web and Wireless Geographical Information Systems.2004:120-135.
[4]DENG K,ZHOU X,TAO H.Multi-source skyline query pro-cessingin road networks[C]//IEEE International Conference on Data Engineering.2007:796-805.
[5]HUANG Y K,CHANG C H,LEE C.Continuous distance-based skyline queries in road networks[J].Information Systems,2012,37(7):611-633.
[6]SHI C,QIN X,WANG L.Continuous skyline queries for movingobjects in road networks[J].Journal of Software-Evolution and Process,2015,10(2):190-200.
[7]JIANG S,ZHENG J,CHEN J,et al.Efficient computation ofcontinuous range skyline queries in road networks[C]//International Conference on Intelligent Computing.Springer International Publi-shing,2016:520-532.
[8]SHANG S,CHEN L,WEI Z,et al.Collective travel planning in spatial networks[J].IEEE Transactions on Know-ledge and Data Engineering,2016,28(5):1132-1146.
[9]SHANG S,ZHENG K,JENSEN C S,et al.Discovery of Path Nearby Clusters in Spatial Networks[J].IEEE Transactions on Know-ledge & Data Engineering,2015,27(6):1505-1518.
[10]SHANG S,DING R,ZHENG K,et al.Personalized trajectory matching in spatial networks[J].Very LargeData Bases Journal,2014,23(3):449-468.
[11]XIE K,DENG K E,SHANG S,et al.Finding Alternative Shortest Paths in Spatial Networks[J].ACM Transactions on Database Systems,2012,37(4):1-31.
[12]WANG M,FU W,HAO S,et al.Scalable semi-supervised lear-ning by efficient anchor graph regularization [J].IEEE Transactions on Knowledge & Data Engineering,2016,28(7):1864-1877.
[13]WANG M,FU W,HAO S,et al.Learning on big graph:Label infe-rence and regularization with anchor hierarchy[J].IEEE Transactions on Knowledge & Data Engineering,2017,29(5):1101-1114.
[14]SHANG S,CHEN L,WEI Z,et al.Trajectory similarity join in spatial networks[J].Proceedings of the Vldb Endowment,2017,10(11):1178-1189.
[15]FU X,MIAO X,XU J,et al.Continuous range-based sky-line queries in road networks[J].World Wide Web Journal,2017,20:1443-1467.
[16]CHAPMAN A,JAGADISH H V.Why not?[C]//Proc.ACM SIGMODInt.Conf.Manag.Data.2009:523-534.
[17]BIDOIT N,HERSCHEL M,TZOMPANAKI K.Query-basedwhy-not provenance with Ned Explain[C]//Proceeding of the 17th International Conferenece on Extending Database Techno-logy.2014:145-156.
[18]HUANG J,CHEN T,DOAN A H,et al.On the provenance of non-answers to queries over extracted data[J].Proceedings of the Endowment,2008,1(1):736-747.
[19]HERSCHEL M,HERNÁNDEZ M A,TAN W C.Artemis:Asystem for analyzing missing answers [J].Proceedings of the Endowment,2009,2(2):1550-1553.
[20]HERSCHEL M,HERNÁNDEZ M A.Explaining missing an-swersto SPJUA queries [J].Proceedings of the VLDB Endowment,2010,3(1/2):185-196.
[21]ZONG C,YANG X,WANG B,et al.Minimizing explanations for missing answers to queries on databases[C]//Database Systems for Advanced Applications.2013:254-268.
[22]HERSCHEL M.Wondering why data are missing from queryresults:Ask conseil why-not[C]//Proceedings of the 22nd ACM International Conference on Information & Knowledge Management.2013:2213-2218.
[23]HERSCHEL M.A hybrid approach to answering why-not questions on relational query results[J].Data and InformationQua-lity,2015,5(3):1-29.
[24]CATE B T,CIVILI C,SHERKHONOV E,et al.High-levelwhy-not explanations using ontologies[J].arXiv:1412.2332,2015.
[25]CALVANESE D,ORTIZ M,SIMKUS M,et al.Reasoningabout explanations for negative query answers in DL-lite[J].Journal of Artificial Intelligence Research,2013,48:635-669.
[26]BIDOIT N,HERSCHEL M,TZOMPANAKI A.Efficient computationof polynomial explanations of why-not questions[C]//Proceedings of the18th ACM International Conference on Information & Knowledge Management.2015:713-722.
[27]XIAO Y M,GAO Y J.On Efficiently Answering Why-NotRange-Based Skyline Queries in Road Networks[J].IEEE Transactions on Knowledge and Data Engineering,2018,30(9):1697-1711.
[28]DELLIS E,SEEGER B.Efficient Computation of Reverse Skyline Queries[C]//Proceeding of the International Conference on Very Large Data Bases.2007:291-302.
[29]LIAN X,CHEN L.Reverse Skyline Search in Uncertain Databases[J].ACM Transactions on Database Systems(TODS),2010,35(1):1-49.
[30]GUO W,GUO J,HU Z Y.Spatial database index technology[M].Shanghai:Shanghai Jiaotong University Press,2006.
[31]GAO Y,LIU Q,ZHENG B,et al.On efficient reverse skyline query processing[J].Expert Systems with Applications,2014,41(7):3237-3249.
[32]ISLAM M S,ZHOU R,LIU C F.On answering why-not questions in reverse skyline queries[C]//IEEE ICDE.2013:973-984.
[33]BAGUS J S,TOSCA Y C.Answering why-not questions on reverse Skyline queries over incomplete data[J].JUTI,2019,17(1):84-93.
[34]LEE K C,LEE W C,ZHENG B,et al.ROAD:A new spatialobject search framework for road networks[J].IEEE Transactions on Knowledge and Data Engineering,2012,24(3):547-560.
[1] LIU Ze-bang, CHEN Luo, YANG An-ran, LI Si-jie. Space Retrieval Method to Retrieve Straight Line for Vector Line Data [J]. Computer Science, 2021, 48(11A): 117-123.
[2] XIONG Ting, QI Yong, ZHANG Wei-bin. Short-term Traffic Flow Prediction Based on DCGRU-RF Model for Road Network [J]. Computer Science, 2020, 47(5): 84-89.
[3] WANG Yan, HAN Xiao, ZENG Hui, LIU Jing-xin, XIA Chang-qing. Task Migration Node Selection with Reliable Service Quality in Edge Computing Environment [J]. Computer Science, 2020, 47(10): 240-246.
[4] RUAN Zi-rui,RUAN Zhong-yuan,SHEN Guo-jiang. Study of TASEP Model Based on Road Networks [J]. Computer Science, 2020, 47(1): 265-269.
[5] ZHANG Tong,QIN Xiao-lin. K Nearest Neighbors Queries of Moving Objects in Time-dependent Road Networks [J]. Computer Science, 2020, 47(1): 79-86.
[6] ZHOU Jian-gang, QIN Xiao-lin, ZHANG Ke-heng, XU Jian-qiu. Dynamic Skyline Query for Multiple Mobile Users Based on Road Network [J]. Computer Science, 2019, 46(9): 73-78.
[7] LI Jia-jia, SHEN Pan-pan, XIA Xiu-feng, LIU Xiang-yu. Reverse k Nearest Neighbor Queries in Time-dependent Road Networks [J]. Computer Science, 2019, 46(1): 232-237.
[8] MAO Ying-chi and CHEN Yang. Uncertain Vehicle Intersection Trajectory Prediction [J]. Computer Science, 2018, 45(3): 235-240.
[9] DONG Tian-yang, SHANG Yue-hui, CHENG Qiang. Direction-aware Moving Object Range Query Algorithm in Road Network [J]. Computer Science, 2018, 45(11): 210-219.
[10] YU Wei, ZHENG Ji-ping, WANG Hai-xiang, WANG Yong-ge, CHEN Jia-liang and JIANG Shun-qing. Spatial Skyline Queries:Applications,Research and Challenges [J]. Computer Science, 2017, 44(2): 1-16.
[11] LI Qing, XIAO Ying-yuan, WANG Xiao-ye and LI Yu-kun. Clustering Architecture-based Skyline Query Processing in Wireless Sensor Networks [J]. Computer Science, 2017, 44(10): 177-181.
[12] DAI Jia-zhu and HUA Liang. Method of Anonymous Area Generation for Sensitive Location Protection under Road Networks [J]. Computer Science, 2016, 43(3): 137-144.
[13] YANG Xu-hua and ZHOU Shi-jie. Double Layers Routing Algorithm on Large Road Networks Based on Overlapping Communities Detecting [J]. Computer Science, 2015, 42(Z6): 285-289.
[14] ZHANG Li-ping, JING Hai-dong, LI Song and CUI Huan-yu. Reverse Nearest Neighbor Query Based on Voronoi Diagram for Road Network [J]. Computer Science, 2015, 42(8): 231-235.
[15] XUE Ming XU De-gang. Anti Congestion Vehicle Path Planning Algorithm Based on Cloud Grid Integrated Scheduling [J]. Computer Science, 2015, 42(7): 295-299.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.