ABSTRACT
STUN is an extension of social networks in which the edges are characterized by spatio-temporal annotations, as well as uncertainty allowing us to express not only relationships between vertices, but when and where these relationships were true, and how certain we are that the relationships hold. We propose a STUN query language that consists of sub graphs with spatio-temporal constraints and uncertainty requirements. We then develop an index structure to store STUN graphs, together with an algorithm to answer such queries. We describe experiments with a real-world YouTube social network data set and show that our algorithm performs well on graphs with over a million edges.
- M. Bröcheler, A. Pugliese, and V. S. Subrahmanian, "DOGMA: A disk-oriented graph matching algorithm for RDF databases," in ISWC, 2009. Google ScholarDigital Library
- G. Karypis and V. Kumar, "A fast and high quality multilevel scheme for partitioning irregular graphs," SIAM J. on Scientific Computing, 1998. Google ScholarDigital Library
- O. Udrea, D. R. Recupero, and V. S. Subrahmanian, "Annotated RDF," ACM Trans. Comput. Log., vol. 11, no. 2, 2010. Google ScholarDigital Library
- Y. Theoharis, V. Christophides, and G. Karvounarakis, Benchmarking database representations of RDF/S Stores, 2005, pp. 685-701. Google ScholarDigital Library
- M. Sintek and M. Kiesel, "RDFBroker: A signature-based high-performance RDF store," in ESWC, 2006, pp. 363-377. Google ScholarDigital Library
- K. Wilkinson, C. Sayers, H. Kuno, and D. Reynolds, "Efficient RDF storage and retrieval in Jena2," SWDB Conf., vol. 3, pp. 7-8, 2003.Google Scholar
- A. Harth and S. Decker, "Optimized index structures for querying RDF from the Web," in Proceedings of the 3rd Latin American Web Congress, 2005, pp. 71-80. Google ScholarDigital Library
- S. Zhang, S. Li, and J. Yang, "SUMMA: subgraph matching in massive graphs," in CIKM Conf., 2010, pp. 1285-1288. Google ScholarDigital Library
- K. Zhu, Y. Zhang, X. Lin, G. Zhu, and W. W. 0011, "NOVA: A novel and efficient framework for finding subgraph isomorphism mappings in large graphs," in DASFAA Conf., 2010, pp. 140-154. Google ScholarDigital Library
- L. Zou, L. Chen, and M. T. Özsu, "Distancejoin: Pattern match query in a large graph database," VLDB Conf., vol. 2, no. 1, pp. 886-897, 2009. Google ScholarDigital Library
- J. Cheng, J. X. Yu, B. Ding, P. S. Yu, and H. Wang, "Fast graph pattern matching," in ICDE Conf., 2008, pp. 913-922. Google ScholarDigital Library
- S. Zhang, S. Li, and J. Yang, "GADDI: distance index based subgraph matching in biological networks," in EDBT Conf., 2009, pp. 192-203. Google ScholarDigital Library
- R. D. Natale, A. Ferro, R. Giugno, M. Mongiovì, A. Pulvirenti, and D. Shasha, "SING: Subgraph search in non-homogeneous graphs," BMC Bioinformatics, vol. 11, p. 96, 2010.Google ScholarCross Ref
- STUN: Spatio-Temporal Uncertain (Social) Networks
Recommendations
KSQ: Top-$(k)$ Similarity Query on Uncertain Trajectories
Similarity search on spatiotemporal trajectories has a wide range of applications. Most of existing research focuses on certain trajectories. However, trajectories often are uncertain due to various factors, for example, hardware limitations and privacy ...
Building social capital with Facebook: Type of network, availability of other media, and social self-efficacy matter#
Highlights- Type of friends affects building social capital via Facebook and traditional media.
AbstractFindings about Facebook's effect on relationships are mixed, possibly due to lack of models that acknowledge differences across users, types of their friends, and use of competing media. To address this, we proposed and tested how ...
An Empirical Study of a Chinese Online Social Network--Renren
Deeper knowledge of social networks' structure and temporal evolution enhances data mining for both research and education purposes. An empirical analysis of a Chinese social network, Renren, shows that it follows an exponentially truncated power law in ...
Comments