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 metadatas

Cited literature [90 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/tel-01307470
Contributor : Abes Star <>
Submitted on : Tuesday, April 26, 2016 - 3:12:07 PM
Last modification on : Thursday, October 17, 2019 - 12:36:09 PM
Long-term archiving on : Wednesday, July 27, 2016 - 2:42:00 PM

File

TheseBenDhiaV2.pdf
Version validated by the jury (STAR)

Identifiers

  • HAL Id : tel-01307470, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

302

Files downloads

202