Skip to Main content Skip to Navigation

Large-scale data management in real-world graphs

Abstract : In the last few years, we have been witnessing a rapid growth of networks in a wide range of applications such as social networking, bio-informatics, semantic web, road maps, etc. Most of these networks can be naturally modeled as large graphs. Managing, analyzing, and querying such data has become a very important issue, and, has inspired extensive interest within the database community. In this thesis, we address the problem of efficiently answering distance queries in very large graphs. We propose EUQLID, an efficient algorithm to answer distance queries on very large directed graphs. This algorithm exploits some interesting properties that real-world graphs exhibit. It is based on an efficient variant of the seminal 2-hop algorithm. We conducted an extensive set of experiments against state-of-the-art algorithms which show that our approach outperforms existing approaches and that distance queries can be processed within hundreds of milliseconds on very large real-world directed graphs. We also propose an access control model for social networks which can make use of EUQLID to scale on very large graphs. This model allows users to specify fine-grained privacy policies based on their relations with other users in the network. We describe and demonstrate Primates as a prototype which enforces the proposed access control model and allows users to specify their privacy preferences via a graphical user-friendly interface.
Keywords : Security
Complete list of metadata

Cited literature [90 references]  Display  Hide  Download
Contributor : ABES STAR :  Contact
Submitted on : Tuesday, April 26, 2016 - 3:12:07 PM
Last modification on : Friday, July 31, 2020 - 10:44:08 AM
Long-term archiving on: : Wednesday, July 27, 2016 - 2:42:00 PM


Version validated by the jury (STAR)


  • HAL Id : tel-01307470, version 1



Imen Ben Dhia. Large-scale data management in real-world graphs. Data Structures and Algorithms [cs.DS]. Télécom ParisTech, 2013. English. ⟨NNT : 2013ENST0087⟩. ⟨tel-01307470⟩



Record views


Files downloads