Crawling Hidden Objects with kNN Queries

ISCAS OpenIR

	Crawling Hidden Objects with kNN Queries
	Yan, H; Gong, ZG; Zhang, N; Huang, T; Zhong, H; Wei, J
	2016
发表期刊	IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING
ISSN	1041-4347
卷号	28 期号:4 页码:912-924
摘要	Many websites offering Location Based Services (LBS) provide a kNN search interface that returns the top-k nearest-neighbor objects (e.g., nearest restaurants) for a given query location. This paper addresses the problem of crawling all objects efficiently from an LBS website, through the public kNN web search interface it provides. Specifically, we develop crawling algorithm for 2D and higher-dimensional spaces, respectively, and demonstrate through theoretical analysis that the overhead of our algorithms can be bounded by a function of the number of dimensions and the number of crawled objects, regardless of the underlying distributions of the objects. We also extend the algorithms to leverage scenarios where certain auxiliary information about the underlying data distribution, e.g., the population density of an area which is often positively correlated with the density of LBS objects, is available. Extensive experiments on real-world datasets demonstrate the superiority of our algorithms over the state-of-the-art competitors in the literature.; Many websites offering Location Based Services (LBS) provide a kNN search interface that returns the top-k nearest-neighbor objects (e.g., nearest restaurants) for a given query location. This paper addresses the problem of crawling all objects efficiently from an LBS website, through the public kNN web search interface it provides. Specifically, we develop crawling algorithm for 2D and higher-dimensional spaces, respectively, and demonstrate through theoretical analysis that the overhead of our algorithms can be bounded by a function of the number of dimensions and the number of crawled objects, regardless of the underlying distributions of the objects. We also extend the algorithms to leverage scenarios where certain auxiliary information about the underlying data distribution, e.g., the population density of an area which is often positively correlated with the density of LBS objects, is available. Extensive experiments on real-world datasets demonstrate the superiority of our algorithms over the state-of-the-art competitors in the literature.
收录类别	SCI
关键词	Hidden Databases Data Crawling Location Based Services Knn Queries
部门归属	Univ Sci & Technol China, Sch Comp Sci & Technol, Hefei, Peoples R China. Univ Macau, Macau, Peoples R China. Chinese Acad Sci, Inst Software, Beijing, Peoples R China. Univ Macau, Dept Comp & Informat Sci, Macau, Peoples R China. George Washington Univ, Dept Comp Sci, Washington, DC 20052 USA. Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China. Chinese Acad Sci, Inst Software, Technol Ctr Software Engineer, Beijing, Peoples R China.
语种	英语
WOS记录号	WOS:000372543500006
引用统计	被引频次：1[WOS] [WOS记录] [WOS相关记录]
内容类型	期刊论文
URI标识	http://ir.iscas.ac.cn/handle/311060/17340
专题	中国科学院软件研究所
推荐引用方式 GB/T 7714	Yan, H,Gong, ZG,Zhang, N,et al. Crawling Hidden Objects with kNN Queries[J]. IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,2016,28(4):912-924.
APA	Yan, H,Gong, ZG,Zhang, N,Huang, T,Zhong, H,&Wei, J.(2016).Crawling Hidden Objects with kNN Queries.IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,28(4),912-924.
MLA	Yan, H,et al."Crawling Hidden Objects with kNN Queries".IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 28.4(2016):912-924.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
07335622.pdf（864KB）			开放获取	使用许可	请求全文