Giter VIP home page Giter VIP logo

greatsky13's Projects

csrankings icon csrankings

A web app for ranking computer science departments according to their research output in selective venues, and for finding active faculty across a wide range of areas.

mgtag icon mgtag

Reachability query asks whether a vertex can reach another vertex on large directed graphs. It is one of the most fundamental graph operators and has attracted many researchers to study it. Although there are many approaches solving this problem, it still remains a challenging problem when it comes to leverage the three main costs: the index construction time, the index size, and the query time on large and dense graphs. In this paper, we propose a High Dimension Graph Labeling approach to answer reachability queries. First, we recursively partition a graph into disjoint non-shared graphs, among which there are no common vertices, and cross edges. Second, we build a four dimensional label - one dimension of layer, one dimension of sub-graph and two dimensions of interval for each vertex. With the layer label and the sub-graph label, we can determine the positions (non-shared graphs) of any two vertices. Two dimensional interval label is used to assist to answer the reachability queries for vertex pair in those non-shared graphs. Finally, we design algorithms to answer researchability queries efficiently. In order to speed up query answering, we also build two directional labels: up and down labels to filter vertices quickly. The extensive experiments on 28 large/small and dense/sparse graphs show that building the high dimensional index is quickly and the index size is also competitive compared with most of the state of the art approaches. The results also show that our approach is more scalable and efficient than the state-of-the-art approaches in answering reachability queries.

pathgraph icon pathgraph

PathGraph, a path-centric graph processing system for fast iterative computation on large graphs with billions of edges.

triplebit icon triplebit

TripleBit, a fast and compact system for large scale RDF graph.

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.