Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2019, Vol. 13 Issue (5) : 1062-1071    https://doi.org/10.1007/s11704-018-7074-4
RESEARCH ARTICLE
Answering why-not questions on KNN queries
Zhefan ZHONG(), Xin LIN(), Liang HE(), Jing YANG()
Shanghai Key Laboratory of Multidimensional Information Processing, East China Normal University, Shanghai 200062, China
 Download: PDF(511 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
Abstract

Being decades of study, the usability of database systems have received more attention in recent years. Now it is especially able to explain missing objects in a query result, which is called “why-not” questions, and is the focus of concern. This paper studies the problem of answering whynot questions on KNN queries. In our real life, many users would like to use KNN queries to investigate the surrounding circumstances. Nevertheless, they often feel disappointed when finding the result not including their expected objects. In this paper, we use the query refinement approach to resolve the problem. Given the original KNN query and a set of missing objects as input, our algorithm offer a refined KNN query that includes the missing objects to the user. The experimental results demonstrate the efficiency of our proposed optimizations and algorithms.

Keywords why-not queries      spatio queries      KNN queries      location-based services     
Corresponding Author(s): Jing YANG   
Just Accepted Date: 09 February 2018   Online First Date: 04 September 2018    Issue Date: 25 June 2019
 Cite this article:   
Zhefan ZHONG,Xin LIN,Liang HE, et al. Answering why-not questions on KNN queries[J]. Front. Comput. Sci., 2019, 13(5): 1062-1071.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-018-7074-4
https://academic.hep.com.cn/fcs/EN/Y2019/V13/I5/1062
1 H V Jagadish, A Chapman, A Elkiss, M Jayapandian, Y Li, A Nandi, C Yu. Making database systems usable. In: Proceedings of the 2007 ACM SIGMOD International Conference on Management of Data. 2007, 13–24
https://doi.org/10.1145/1247480.1247483
2 Q T Tran, C Y Chan. How to conquer why-not questions. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data. 2010, 15–26
https://doi.org/10.1145/1807167.1807172
3 Z He, E Lo. Answering why-not questions on top-k queries. In: Proceedings of the 28th IEEE International Conference on Data Engineering. 2012, 750–761
https://doi.org/10.1109/ICDE.2012.8
4 A Chapman, H V Jagadish. Why not? In: Proceedings of Special Interest Group on Management of Data. 2009, 523–534
https://doi.org/10.1145/1559845.1559901
5 M S Islam, R Zhou, C Liu. On answering why-not questions in reverse skyline queries. In: Proceedings of the 29th IEEE International Conference on Data Engineering. 2013, 973–984
https://doi.org/10.1109/ICDE.2013.6544890
6 Y Gao, Q Liu, G Chen, B Zheng, L Zhou. Answering why-not questions on reverse top-k queries. Proceedings of the VLDB Endowment, 2015, 8(7): 738–749
https://doi.org/10.14778/2752939.2752943
7 L Chen, Y Gao, K Wang, C S Jensen, G Chen. Answering why-not questions on metric probabilistic range queries. In: Proceedings of the 32nd IEEE International Conference on Data Engineering. 2016, 767–778
https://doi.org/10.1109/ICDE.2016.7498288
8 A J Ko, B A Myers. Designing the whyline: a debugging interface for asking questions about program behavior. In: Proceedings of the SIGCHI Conference on Human Factors in Computer Systems. 2004, 151–158
https://doi.org/10.1145/985692.985712
9 A M Brad, A W David, J K Andrew, H C Duen. Answering why and why not questions in user interfaces. In: Proceedings of the SIGCHI Conference on Human Factors in Computer Systems. 2006, 397–406
10 J Huang, T Chen, A Doan, J F Naughton. On the provenance of nonanswers to queries over extracted data. Proceedings of the VLDB Endowment, 2008, 1(1): 736–747
https://doi.org/10.14778/1453856.1453936
11 M Herschel, M A Hernandez. Explaining missing answers to spjua queries. Proceedings of the VLDB Endowment, 2010, 3(1): 185–196
https://doi.org/10.14778/1920841.1920869
12 S Borzsonyi, D Kossmann, K Stockek. The skyline operator. Transactions on Database Systems, 2000, 25(2): 129–178
13 N Beckmann, H P Kriegel, R Schneider, B Seeger. The R*-tree: an efficient and robust access method for points and rectangles. In: Proceedings of Special Interest Group on Management of Data. 1990, 322–331
[1] Huiping LIU, Cheqing JIN, Aoying ZHOU. Popular route planning with travel cost estimation from trajectories[J]. Front. Comput. Sci., 2020, 14(1): 191-207.
[2] Jingwei ZHANG, Chao YANG, Qing YANG, Yuming LIN, Yanchun ZHANG. HGeoHashBase: an optimized storage model of spatial objects for location-based services[J]. Front. Comput. Sci., 2020, 14(1): 208-218.
[3] Xiao PAN, Xiaofeng MENG. Preserving location privacy without exact locations in mobile services[J]. Front Comput Sci, 2013, 7(3): 317-340.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed