Efficient sampling methods for characterizing POIs on maps based on road networks

Abstract

With the rapid development of location-based services, a particularly important aspect of start-up marketing research is to explore and characterize points of interest (PoIs) such as restaurants and hotels on maps. However, due to the lack of direct access to PoI databases, it is necessary to rely on existing APIs to query PoIs within a region and calculate PoI statistics. Unfortunately, public APIs generally impose a limit on the maximum number of queries. Therefore, we propose effective and efficient sampling methods based on road networks to sample PoIs on maps and provide unbiased estimators for calculating PoI statistics. In general, the more intense the roads, the denser the distribution of PoIs is within a region. Experimental results show that compared with state-of-the-art methods, our sampling methods improve the efficiency of aggregate statistical estimations.

Keywords

sampling / aggregate statistical estimation / road networks

References

[1] Dalvi N, Kumar R, Machanavajjhala A, Rastogi V. Sampling hidden objects using nearest-neighbor oracles. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2011, 1325–1333

[2] Li Y H, Steiner M, Wang L M, Zhang Z L, Bao J. Dissecting foursquare venue popularity via random region sampling. In: Proceedings of ACM Conference on CoNEXT Student Workshop. 2012, 21–22

[3] Wang P H, He W B, Liu X. An efficient sampling method for characterizing points of interests on maps. In: Proceeding of the 30th IEEE International Conference on Data Engineering. 2014, 1012–1023

[4] Bar-Yossef Z, Gurevich M. Efficient search engine measurements. In: Proceedings of the 16th International Conference onWorld Wide Web. 2007, 401–410

[5] Bar-Yossef Z, Gurevich M. Mining search engine query logs via suggestion sampling. Proceedings of the VLDB Endowment, 2008, 1(1): 54–65

[6] Bar-Yossef Z, Gurevich M. Random sampling from a search engine’s index. Journal of the ACM, 2008, 55(5): 24

[7] Brin S, Page L. Reprint of: the anatomy of a large-scale hypertextual Web search engine. Computer Networks, 2012, 56(18): 3825–3833

[8] Gulli A, Signorini A. The indexable Web is more than 11.5 billion pages. In: Proceeding of the 14th International Conference on World Wide Web. 2005, 902–903

[9] Henzinger M R, Heydon A, Mitzenmacher M, Najork M. On nearuniform URL sampling. Computer Networks, 2000, 33(1): 295–308

[10] Rusmevichientong P, Pennock D M, Lawrence S, Giles C L. Methods for sampling pages uniformly from the World Wide Web. In: Proceeding of AAAI Fall Symposium on Using Uncertainty Within Computation. 2001, 121–128

[11] Zhang M Y, Zhang N, Das G. Mining a search engine’s corpus: efficient yet unbiased sampling and aggregate estimation. In: Proceedings of ACM SIGMOD International Conference on Management of data. 2011, 793–804

[12] Agichtein E, Ipeirotis P, Gravano L. Modeling query-based access to text databases. In: Proceeding of WebDB. 2003

[13] Barbosa L, Freire J. Siphoning hidden-Web data through keywordbased interfaces. Journal of Information and Data Management, 2010, 1(1): 133

[14] Barbosa L, Freire J. Searching for hidden-Web databases. In: Proceeding of WebDB. 2005

[15] Callan J, Connell M. Query-based sampling of text databases. ACM Transactions on Information Systems, 2001, 19(2): 97–130

[16] Ipeirotis P G, Gravano L. Distributed search over the hidden Web: hierarchical database sampling and selection. In: Proceedings of the 28th International Conference on Very Large Data Bases. 2002, 394–405

[17] Jin X, Zhang N, Das G. Attribute domain discovery for hidden Web databases. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2011, 553–564

[18] Lu J G. Ranking bias in deep Web size estimation using capture recapture method. Data & Knowledge Engineering, 2010, 69(8): 866–879

[19] Zerfos P, Cho J, Ntoulas A. Downloading textual hidden Web content through keyword queries. In: Proceedings of the 5th ACM/IEEE-CS Joint Conference on Digital Libraries. 2005, 100–109

[20] ĺćlvarez M, Raposo J, Pan A, Cacheda F, Bellas F, Carneiro V. Crawling the content hidden behind Web forms. In: Proceeding of International Conference on Computational Science and Its Applications. 2007, 322–333

[21] Bruno N, Gravano L, Marian A. Evaluating top-k queries over Webaccessible databases. In: Proceedings of the 18th International Conference on Data Engineering. 2002, 369–380

[22] Chang K C C, He B, Li C K, Patel M, Zhang Z. Structured databases on the Web: observations and implications. ACM SIGMOD Record, 2004, 33(3): 61–70

[23] Raghavan S, Garcia-Molina H. Crawling the hidden Web. In: Proceedings of the 27th International Conference on Very Large Data Bases. 2001

[24] Sheng C, Zhang N, Tao Y F, Jin X. Optimal algorithms for crawling a hidden database in the Web. Proceedings of the VLDB Endowment, 2012, 5(11): 1112–1123

[25] Thirumuruganathan S, Zhang N, Das G. Digging deeper into deep Web databases by breaking through the top-k barrier. 2012, ArXiv Preprint ArXiv: 1208.3876

[26] Hedley Y L, Younas M, James A, Sanderson M. A two-phase sampling technique for information extraction from hidden Web databases. In: Proceedings of the 6th Annual ACM International Workshop on Web Information and Data Management. 2004, 1–8

[27] Hedley Y L, Younas M, James A, Sanderson M. Sampling, information extraction and summarisation of hidden Web databases. Data & Knowledge Engineering, 2006, 59(2): 213–230

[28] Shokouhi M, Zobel J, Scholer F, Tahaghoghi S M. Capturing collection size for distributed non-cooperative retrieval. In: Proceedings of the 29th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. 2006, 316–323

[29] Dasgupta A, Zhang N, Das G. Leveraging count information in sampling hidden databases. In: Proceeding of the 25th IEEE International Conference on Data Engineering. 2009, 329–340

[30] Dasgupta A, Jin X, Jewell B, Zhang N, Das G. Unbiased estimation of size and other aggregates over hidden Web databases. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2010, 855–866

[31] Dasgupta A, Das G, Mannila H. A random walk approach to sampling hidden databases. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2007, 629–640

[32] Dasgupta A, Zhang N, Das G. Turbo-charging hidden database samplers with overflowing queries and skew reduction. In: Proceedings of the 13th International Conference on Extending Database Technology. 2010, 51–62

[33] Drummond A J, Rambaut A. BEAST: Bayesian evolutionary analysis by sampling trees. BMC Evolutionary Biology, 2007, 7(1): 1

[34] Wang F, Agrawal G. Effective and efficient sampling methods for deep Web aggregation queries. In: Proceedings of the 14th International Conference on Extending Database Technology. 2011, 425–436

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag GmbH Germany, part of Springer Nature