Reach Me If You Can: Reachability Query in Uncertain Contact Networks

ABSTRACT

With the advent of reliable positioning technologies and prevalence of location-based services, it is now feasible to accurately study the propagation of items such as infectious viruses, sensitive information pieces, and malwares through a population of moving objects, e.g., individuals, vehicles, and mobile devices. In such application scenarios, an item passes between two objects when the objects are sufficiently close (i.e., when they are, so-called, in contact), and hence once an item is initiated, it can propagate in the object population through the evolving network of contacts among objects, termed contact network. In this paper, for the first time we define and study probabilistic reachability queries in large uncertain contact networks, where propagation of items through contacts are uncertain. A probabilistic reachability query verifies whether two objects are "reachable" through the evolving uncertain contact network with a probability greater than a threshold η. For efficient processing of probabilistic queries, we propose a novel index structure, termed spatiotemporal tree cover (STC), which leverages the spatiotemporal properties of the contact network for efficient processing of the queries. Our experiments with real data demonstrate superiority of our proposed solution versus the only other existing solution (based on Monte Carlo sampling) for processing probabilistic reachability queries in generic uncertain graphs, with 300% improvement in query processing time on average.

References

1. 2018 (accessed March 10, 2018). DSRC communicatio. https://www.its.dot.gov/factsheets/dsrc_factsheet.htm. (2018 (accessed March 10, 2018)).
2. R. Agrawal, A. Borgida, and H. V. Jagadish. 1989. Efficient Management of Transitive Relationships in Large Data and Knowledge Bases. SIGMOD Rec. 18, 2 (June 1989), 253--262.
3. Ramadhana Bramandia, Byron Choi, and Wee Keong Ng. 2008. On Incremental Maintenance of 2-hop Labeling of Graphs (WWW '08). ACM, New York, NY, USA, 845--854.
4. G. S. Fishman. 1986. A Comparison of Four Monte Carlo Methods for Estimating the Probability of s-t Connectedness. IEEE Transactions on Reliability 35, 2 (June 1986), 145--155.
5. H. V. Jagadish. 1990. A Compression Technique to Materialize Transitive Closure. ACM Trans. Database Syst. 15, 4 (Dec. 1990), 558--598.
6. Ruoming Jin, Yang Xiang, Ning Ruan, and David Fuhry. 2009. 3HOPP: A High-compression Indexing Scheme for Reachability Query (SIGMOD '09). ACM, New York, NY, USA, 813--826.
7. Michalis Potamias, Francesco Bonchi, Aristides Gionis, and George Kollios. 2010. K-nearest Neighbors in Uncertain Graphs. Proc. VLDB Endow. 3, 1--2 (Sept. 2010), 997--1008.
8. S. Seufert, A. Anand, S. Bedathur, and G. Weikum. 2013. FERRARI: Flexible and efficient reachability range assignment for graph indexing. In (ICDE'13 2013). 1009--1020.
9. Shashi Shekhar and Hui Xiong. 2007. Encyclopedia of GIS (1st ed.). Springer Publishing Company, Incorporated.
10. Houtan Shirani-Mehr, Farnoush Banaei-Kashani, and Cyrus Shahabi. 2012. Efficient Reachability Query Evaluation in Large Spatiotemporal Contact Datasets. Proc. VLDB Endow. 5, 9 (May 2012), 848--859.
11. Elena V. Strzheletska and Vassilis J. Tsotras. 2015. RICC: Fast Reachability Query Processing on Large Spatiotemporal Datasets. In Advances in Spatial and Temporal Databases, Christophe Claramunt, Markus Schneider, Raymond Chi-Wing Wong, Li Xiong, Woong-Kee Loh, Cyrus Shahabi, and Ki-Joune Li (Eds.). Springer International Publishing, Cham, 3--21.
12. Elena V. Strzheletska and Vassilis J. Tsotras. 2017. Efficient Processing of Reachability Queries with Meetings. In Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL'17). ACM, New York, NY, USA, Article 22, 10 pages.
13. Hilmi Yildirim, Vineet Chaoji, and Mohammed J. Zaki. 2010. GRAIL: Scalable Reachability Index for Large Graphs. Proc. VLDB Endow. 3, 1--2 (Sept. 2010), 276--284.
14. Ke Zhu, Wenjie Zhang, Gaoping Zhu, Ying Zhang, and Xuemin Lin. 2011. BMC: An Efficient Method to Evaluate Probabilistic Reachability Queries. In Proceedings of the 16th International Conference on Database Systems for Advanced Applications - Volume Part I (DASFAA'11). Springer-Verlag, Berlin, Heidelberg, 434--449.