Hierarchical graph indexing

James Abello, Yannis Kotidis

Research output: Contribution to conferencePaper

5 Scopus citations

Abstract

Traffic analysis, in the context of Telecommunications or Internet and Web data, is crucial for large network operations. Data in such networks is often provided as large graphs with hundreds of millions of vertices and edges. We propose efficient techniques for managing such graphs at the storage level in order to facilitate its processing at the interface level(visualization). The methods are based on a hierarchical decomposition of the graph edge set that is inherited from a hierarchical decomposition of the vertex set. Real time navigation is provided by an efficient two level indexing schema called the gkd*-tree. The first level is a variation of a kd-tree index that partitions the edge set in a way that conforms to the hierarchical decomposition and the data distribution (the gkd-tree). The second level is a redundant R*-tree that indexes the leaf pages of the gkd-tree. We provide computational results that illustrate the superiority of the gkd*-tree against conventional indexes like the kd-tree and the R*-tree both in creation as well as query response times.

Original languageEnglish (US)
Pages453-460
Number of pages8
DOIs
StatePublished - 2003
EventCIKM 2003: Proceedings of the Twelfth ACM International Conference on Information and Knowledge Management - New Orleans, LA, United States
Duration: Nov 3 2003Nov 8 2003

Conference

ConferenceCIKM 2003: Proceedings of the Twelfth ACM International Conference on Information and Knowledge Management
CountryUnited States
CityNew Orleans, LA
Period11/3/0311/8/03

All Science Journal Classification (ASJC) codes

  • Decision Sciences(all)
  • Business, Management and Accounting(all)

Keywords

  • Graph
  • Index
  • Navigation
  • Visualization

Fingerprint Dive into the research topics of 'Hierarchical graph indexing'. Together they form a unique fingerprint.

  • Cite this

    Abello, J., & Kotidis, Y. (2003). Hierarchical graph indexing. 453-460. Paper presented at CIKM 2003: Proceedings of the Twelfth ACM International Conference on Information and Knowledge Management, New Orleans, LA, United States. https://doi.org/10.1145/956947.956948