Blinks

Le traitement des requêtes sur des données structurées en graphes connaît un nombre croissant d'applications. Une requête de recherche de mots-clés top-k sur un graphe trouve les k meilleures réponses selon certains critères de classement, où chaque réponse est une sous-structure du graphe contenant tous les mots-clés de la requête. Les techniques actuelles pour soutenir de telles requêtes sur des graphes généraux souffrent de plusieurs inconvénients, par exemple, une mauvaise performance dans le pire des cas, le fait de ne pas tirer pleinement parti des index, et des exigences mémoire élevées. Pour remédier à ces problèmes, nous proposons BLINKS, un schéma d'indexation et de traitement de requêtes à deux niveaux pour la recherche de mots-clés top-k sur des graphes. BLINKS suit une stratégie de recherche avec des limites de performance prouvables, tout en exploitant également un index à deux niveaux pour élaguer et accélérer la recherche. Pour réduire l'espace d'index, BLINKS partitionne un graphe de données en blocs : L'index à deux niveaux stocke des informations sommaires au niveau des blocs pour initier et guider la recherche parmi les blocs, et des informations plus détaillées pour chaque bloc afin d'accélérer la recherche à l'intérieur des blocs. Nos expériences montrent que BLINKS offre des améliorations de performance de plusieurs ordres de grandeur par rapport aux approches existantes.