research-article

Efficient Selection of Geospatial Data on Maps for Interactive and Visualized Exploration

Authors:

Zhifeng BaoAuthors Info & Claims

SIGMOD '18: Proceedings of the 2018 International Conference on Management of Data

Pages 567 - 582

https://doi.org/10.1145/3183713.3183738

Published: 27 May 2018 Publication History

Abstract

With the proliferation of mobile devices, large collections of geospatial data are becoming available, such as geo-tagged photos. Map rendering systems play an important role in presenting such large geospatial datasets to end users. We propose that such systems should support the following desirable features: representativeness, visibility constraint, zooming consistency, and panning consistency. The first two constraints are fundamental challenges to a map exploration system, which aims to efficiently select a small set of representative objects from the current region of user's interest, and any two selected objects should not be too close to each other for users to distinguish in the limited space of a screen. We formalize it as the Spatial Object Selection (SOS) problem, prove that it is an NP-hard problem, and develop a novel approximation algorithm with performance guarantees. % To further support interactive exploration of geospatial data on maps, we propose the Interactive SOS (ISOS) problem, in which we enrich the SOS problem with the zooming consistency and panning consistency constraints. The objective of ISOS is to provide seamless experience for end-users to interactively explore the data by navigating the map. We extend our algorithm for the SOS problem to solve the ISOS problem, and propose a new strategy based on pre-fetching to significantly enhance the efficiency. Finally we have conducted extensive experiments to show the efficiency and scalability of our approach.

References

[1]

S. Acharya, P. B. Gibbons, V. Poosala, and S. Ramaswamy. The aqua approximate query answering system. In ACM Sigmod Record, volume 28, pages 574--576. ACM, 1999.

Digital Library

[2]

S. Agarwal, B. Mozafari, A. Panda, H. Milner, S. Madden, and I. Stoica. Blinkdb: queries with bounded errors and bounded response times on very large data. In Proceedings of the 8th ACM European Conference on Computer Systems, pages 29--42. ACM, 2013.

Digital Library

[3]

A. Angel and N. Koudas. Efficient diversity-aware search. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, pages 781--792. ACM, 2011.

Digital Library

[4]

L. G. Azevedo, G. Zimbr ao, and J. M. De Souza. Approximate query processing in spatial databases using raster signatures. In Advances in Geoinformatics, pages 69--86. Springer, 2007.

[5]

L. Battle, R. Chang, and M. Stonebraker. Dynamic prefetching of data tiles for interactive visualization. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 1363--1375, 2016.

Digital Library

[6]

L. Battle, M. Stonebraker, and R. Chang. Dynamic reduction of query result sets for interactive visualizaton. In Big Data, 2013 IEEE International Conference on, pages 1--8. IEEE, 2013.

[7]

A. Belussi, B. Catania, and S. Migliorini. Approximate queries for spatial data., 2013.

[8]

J. Christensen, J. Marks, and S. Shieber. An empirical study of algorithms for point-feature label placement. ACM Trans. Graph., 14(3):203--232, July 1995.

Digital Library

[9]

W. G. Cochran. Relative accuracy of systematic and stratified random samples for a certain class of populations. The Annals of Mathematical Statistics, pages 164--177, 1946.

[10]

W. G. Cochran. Sampling techniques. John Wiley & Sons, 2007.

[11]

T. Condie, N. Conway, P. Alvaro, J. M. Hellerstein, K. Elmeleegy, and R. Sears. Mapreduce online. In Nsdi, volume 10, page 20, 2010.

Digital Library

[12]

F. Csillag, M. Kertész, and Á. Kummert. Sampling and mapping of heterogeneous surfaces: multi-resolution tiling adjusted to spatial variability. International Journal of Geographical Information Systems, 10(7):851--875, 1996.

[13]

A. Das, J. Gehrke, and M. Riedewald. Approximation techniques for spatial data. In Proceedings of the 2004 ACM SIGMOD international conference on Management of data, pages 695--706. ACM, 2004.

Digital Library

[14]

A. Das Sarma, H. Lee, H. Gonzalez, J. Madhavan, and A. Halevy. Efficient spatial sampling of large geographical tables. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, pages 193--204. ACM, 2012.

Digital Library

[15]

E. M. Delmelle. Spatial sampling. In Handbook of Regional Science, pages 1385--1399. Springer, 2014.

[16]

M. Drosou and E. Pitoura. Disc diversity: result diversification based on dissimilarity and coverage. Proceedings of the VLDB Endowment, 6(1):13--24, 2012.

Digital Library

[17]

M. Drosou and E. Pitoura. Diverse set selection over dynamic data. IEEE Transactions on Knowledge and Data Engineering, 26(5):1102--1116, 2014.

Digital Library

[18]

W. Feller. An introduction to probability theory and its applications, volume 2. John Wiley & Sons, 2008.

[19]

A. U. Frank and S. Timpf. Multiple representations for cartographic objects in a multi-scale tree-an intelligent graphical zoom. Computers & Graphics, 18(6):823--829, 1994.

[20]

P. Fraternali, D. Martinenghi, and M. Tagliasacchi. Top-k bounded diversification. In Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data, pages 421--432. ACM, 2012.

Digital Library

[21]

A. Galakatos, A. Crotty, E. Zgraggen, C. Binnig, and T. Kraska. Revisiting reuse for approximate query processing. Proceedings of the VLDB Endowment, 10(10):1142--1153, 2017.

Digital Library

[22]

M. F. Goodchild and R. P. Haining. Gis and spatial data analysis: Converging perspectives. Papers in Regional Science, 83(1):363--385, 2004.

[23]

J. L. Green and J. B. Plotkin. A statistical theory for sampling species abundances. Ecology letters, 10(11):1037--1045, 2007.

[24]

J. M. Hellerstein, R. Avnur, A. Chou, C. Hidber, C. Olston, V. Raman, T. Roth, and P. J. Haas. Interactive data analysis: The control project. Computer, 32(8):51--59, 1999.

Digital Library

[25]

J. M. Hellerstein, P. J. Haas, and H. J. Wang. Online aggregation. In ACM SIGMOD Record, volume 26, pages 171--182. ACM, 1997.

Digital Library

[26]

W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301):13--30, 1963.

[27]

D. G. Horvitz and D. J. Thompson. A generalization of sampling without replacement from a finite universe. Journal of the American statistical Association, 47(260):663--685, 1952.

[28]

S. Idreos, O. Papaemmanouil, and S. Chaudhuri. Overview of data exploration techniques. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pages 277--281. ACM, 2015.

Digital Library

[29]

C. Jermaine, S. Arumugam, A. Pol, and A. Dobra. Scalable approximate query processing with the dbo engine. ACM Transactions on Database Systems (TODS), 33(4):23, 2008.

Digital Library

[30]

N. Kamat, P. Jayachandran, K. Tunga, and A. Nandi. Distributed and interactive cube exploration. In Data Engineering (ICDE), 2014 IEEE 30th International Conference on, pages 472--483. IEEE, 2014.

[31]

P. K. Kefaloukos, M. Vaz Salles, and M. Zachariasen. Declarative cartography: In-database map generalization of geospatial datasets. In Data Engineering (ICDE), 2014 IEEE 30th International Conference on, pages 1024--1035. IEEE, 2014.

[32]

A. Kim, E. Blais, A. Parameswaran, P. Indyk, S. Madden, and R. Rubinfeld. Rapid sampling for visualizations with ordering guarantees. Proceedings of the VLDB Endowment, 8(5):521--532, 2015.

Digital Library

[33]

M. Mahdian, O. Schrijvers, and S. Vassilvitskii. Algorithmic cartography: Placing points of interest and ads on maps. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 755--764. ACM, 2015.

Digital Library

[34]

B. Matérn. Spatial variation, volume 36. Springer Science & Business Media, 2013.

[35]

A. Milne. The centric systematic area-sample treated as a random sample. Biometrics, 15(2):270--297, 1959.

[36]

J. Neyman. On the two different aspects of the representative method: the method of stratified sampling and the method of purposive selection. Journal of the Royal Statistical Society, 97(4):558--625, 1934.

[37]

J. Neyman. Contribution to the theory of sampling human populations. Journal of the American Statistical Association, 33(201):101--116, 1938.

[38]

S. Nutanong, M. D. Adelfio, and H. Samet. Multiresolution select-distinct queries on large geographic point sets. In Proceedings of the 20th International Conference on Advances in Geographic Information Systems, pages 159--168. ACM, 2012.

Digital Library

[39]

S. Peng, H. Samet, and M. D. Adelfio. Viewing streaming spatially-referenced data at interactive rates. In Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 409--412. ACM, 2014.

Digital Library

[40]

E. Puppo and G. Dettori. Towards a formal model for multiresolution spatial maps. In International Symposium on Spatial Databases, pages 152--169. Springer, 1995.

Digital Library

[41]

L. Qin, J. X. Yu, and L. Chang. Diversifying top-k results. Proceedings of the VLDB Endowment, 5(11):1124--1135, 2012.

Digital Library

[42]

R. Royall. An old approach to finite population sampling theory. Journal of the American Statistical Association, 63(324):1269--1279, 1968.

[43]

E. Scudiero, R. Deiana, P. Teatini, G. Cassiani, and F. Morari. Constrained optimization of spatial sampling in salt contaminated coastal farmland using emi and continuous simulated annealing. Procedia Environmental Sciences, 7:234--239, 2011.

[44]

R. J. Serfling. Probability inequalities for the sum in sampling without replacement. The Annals of Statistics, pages 39--48, 1974.

[45]

K. S. Shea and R. B. McMaster. Cartographic generalization in a digital environment: When and how to generalize. In Proceedings of AutoCarto, volume 9, pages 56--67, 1989.

[46]

J. W. Van Groenigen. The influence of variogram parameters on optimal sampling schemes for mapping by kriging. Geoderma, 97(3):223--236, 2000.

[47]

J.-F. Wang, A. Stein, B.-B. Gao, and Y. Ge. A review of spatial sampling. Spatial Statistics, 2:1--14, 2012.

[48]

L. Wang, R. Christensen, F. Li, and K. Yi. Spatial online sampling and aggregation. Proceedings of the VLDB Endowment, 9(3):84--95, 2015.

Digital Library

[49]

P. Wang, W. He, and X. Liu. An efficient sampling method for characterizing points of interests on maps. In Data Engineering (ICDE), 2014 IEEE 30th International Conference on, pages 1012--1023. IEEE, 2014.

[50]

J. M. Ware, C. B. Jones, and N. Thomas. Automated map generalization with multiple operators: a simulated annealing approach. International Journal of Geographical Information Science, 17(8):743--769, 2003.

[51]

K. Zeng, S. Agarwal, A. Dave, M. Armbrust, and I. Stoica. G-ola: Generalized on-line aggregation for interactive analysis on big data. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pages 913--918. ACM, 2015.

Digital Library

Cited By

Chen JHuang HYe HPeng ZLi CWang C(2024)SalienTime: User-driven Selection of Salient Time Steps for Large-Scale Geospatial Data VisualizationProceedings of the 2024 CHI Conference on Human Factors in Computing Systems10.1145/3613904.3642944(1-19)Online publication date: 11-May-2024
https://dl.acm.org/doi/10.1145/3613904.3642944
Shen QZhang CYan XYang CZeng DZeng WTang B(2024)CheetahTraj: Efficient Visualization for Large Trajectory Dataset With Quality GuaranteeIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.338748036:11(5737-5752)Online publication date: Nov-2024
https://doi.org/10.1109/TKDE.2024.3387480
Qiao YJing YZhang HHe ZZhang KWang X(2023)BlinkViz: Fast and Scalable Approximate Visualization on Very Large Datasets using Neural-Enhanced Mixed Sum-Product NetworksProceedings of the ACM Web Conference 202310.1145/3543507.3583411(1734-1742)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543507.3583411
Show More Cited By

Index Terms

Efficient Selection of Geospatial Data on Maps for Interactive and Visualized Exploration

Recommendations

POIsam: a System for Efficient Selection of Large-scale Geospatial Data on Maps
SIGMOD '18: Proceedings of the 2018 International Conference on Management of Data

In this demonstration we present POIsam, a visualization system supporting the following desirable features: representativeness, visibility constraint, zooming consistency, and panning consistency. The first two constraints aim to efficiently select a ...
Interactive exploration of geospatial network visualization
CHI EA '12: CHI '12 Extended Abstracts on Human Factors in Computing Systems

This paper presents a tabletop visualization of relations between geo-positioned locations. We developed an interactive visualization, which enables users to visually explore a geospatial network of actors. The multitouch tabletop, and the large size of ...
Interactive Exploration of Data Traffic with Hierarchical Network Maps

Network communication has become indispensable in business, education, and government. With the pervasive role of the Internet as a means of sharing information across networks, its misuse for destructive purposes, such as spreading malicious code, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '18: Proceedings of the 2018 International Conference on Management of Data

May 2018

1874 pages

ISBN:9781450347037

DOI:10.1145/3183713

General Chairs:
Gautam Das
University of Texas at Arlington, USA
,
Christopher Jermaine
Rice University, USA
,
Philip Bernstein
Microsoft Research, USA

Copyright © 2018 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 May 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

DP170102726
NSFC 91646204
NSFC 61728204
DP180102050

Conference

SIGMOD/PODS '18

Sponsor:

SIGMOD

SIGMOD/PODS '18: International Conference on Management of Data

June 10 - 15, 2018

TX, Houston, USA

Acceptance Rates

SIGMOD '18 Paper Acceptance Rate 90 of 461 submissions, 20%;

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
1,039
Total Downloads

Downloads (Last 12 months)47
Downloads (Last 6 weeks)9

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen JHuang HYe HPeng ZLi CWang C(2024)SalienTime: User-driven Selection of Salient Time Steps for Large-Scale Geospatial Data VisualizationProceedings of the 2024 CHI Conference on Human Factors in Computing Systems10.1145/3613904.3642944(1-19)Online publication date: 11-May-2024
https://dl.acm.org/doi/10.1145/3613904.3642944
Shen QZhang CYan XYang CZeng DZeng WTang B(2024)CheetahTraj: Efficient Visualization for Large Trajectory Dataset With Quality GuaranteeIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.338748036:11(5737-5752)Online publication date: Nov-2024
https://doi.org/10.1109/TKDE.2024.3387480
Qiao YJing YZhang HHe ZZhang KWang X(2023)BlinkViz: Fast and Scalable Approximate Visualization on Very Large Datasets using Neural-Enhanced Mixed Sum-Product NetworksProceedings of the ACM Web Conference 202310.1145/3543507.3583411(1734-1742)Online publication date: 30-Apr-2023
https://dl.acm.org/doi/10.1145/3543507.3583411
Patil ARand ZBranch TBattle L(2023)WhaleVis: Visualizing the History of Commercial Whaling2023 IEEE Visualization and Visual Analytics (VIS)10.1109/VIS54172.2023.00028(96-100)Online publication date: 21-Oct-2023
https://doi.org/10.1109/VIS54172.2023.00028
Cao YXie XHuang K(2023)Learn to Explore: on Bootstrapping Interactive Data Exploration with Meta-learning2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00135(1720-1733)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00135
Liu ZChen LMa MYang AZhong ZJing N(2023)An efficient visual exploration approach of geospatial vector big data on the web mapInformation Systems10.1016/j.is.2023.102333(102333)Online publication date: Dec-2023
https://doi.org/10.1016/j.is.2023.102333
Chan TIp PU LChoi BXu J(2022)SAFEProceedings of the VLDB Endowment10.14778/3494124.349413515:3(513-526)Online publication date: 4-Feb-2022
https://dl.acm.org/doi/10.14778/3494124.3494135
Chen YLi XCong GLong CBao ZLiu SGu WZhang F(2022)Points-of-interest relationship inference with spatial-enriched graph neural networksProceedings of the VLDB Endowment10.14778/3494124.349413415:3(504-512)Online publication date: 4-Feb-2022
https://dl.acm.org/doi/10.14778/3494124.3494134
Li CBaciu GWang YChen JWang C(2022)DDLVis: Real-time Visual Query of Spatiotemporal Data Distribution via Density Dictionary LearningIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.311476228:1(1062-1072)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1109/TVCG.2021.3114762
Haldar NLi JAli MCai TChen YSellis TReynolds M(2022)Top-k Socio-Spatial Co-engaged Location Selection for Social UsersIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.3151095(1-1)Online publication date: 2022
https://doi.org/10.1109/TKDE.2022.3151095
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents