Hierarchical graph indexing

James Abello, Yannis Kotidis

Research output: Contribution to conferencePaper

5 Citations (Scopus)

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
StatePublished - Dec 1 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

Fingerprint

Indexing
Graph
Decomposition
World Wide Web
Telecommunications
Query
Navigation
Visualization
Response time

All Science Journal Classification (ASJC) codes

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

Keywords

  • Graph
  • Index
  • Navigation
  • Visualization

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.
Abello, James ; Kotidis, Yannis. / Hierarchical graph indexing. Paper presented at CIKM 2003: Proceedings of the Twelfth ACM International Conference on Information and Knowledge Management, New Orleans, LA, United States.8 p.
@conference{6671d66bf60a455f9af16da111a3dcf0,
title = "Hierarchical graph indexing",
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.",
keywords = "Graph, Index, Navigation, Visualization",
author = "James Abello and Yannis Kotidis",
year = "2003",
month = "12",
day = "1",
language = "English (US)",
pages = "453--460",
note = "CIKM 2003: Proceedings of the Twelfth ACM International Conference on Information and Knowledge Management ; Conference date: 03-11-2003 Through 08-11-2003",

}

Abello, J & Kotidis, Y 2003, 'Hierarchical graph indexing', Paper presented at CIKM 2003: Proceedings of the Twelfth ACM International Conference on Information and Knowledge Management, New Orleans, LA, United States, 11/3/03 - 11/8/03 pp. 453-460.

Hierarchical graph indexing. / Abello, James; Kotidis, Yannis.

2003. 453-460 Paper presented at CIKM 2003: Proceedings of the Twelfth ACM International Conference on Information and Knowledge Management, New Orleans, LA, United States.

Research output: Contribution to conferencePaper

TY - CONF

T1 - Hierarchical graph indexing

AU - Abello, James

AU - Kotidis, Yannis

PY - 2003/12/1

Y1 - 2003/12/1

N2 - 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.

AB - 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.

KW - Graph

KW - Index

KW - Navigation

KW - Visualization

UR - http://www.scopus.com/inward/record.url?scp=16244369007&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=16244369007&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:16244369007

SP - 453

EP - 460

ER -

Abello J, Kotidis Y. Hierarchical graph indexing. 2003. Paper presented at CIKM 2003: Proceedings of the Twelfth ACM International Conference on Information and Knowledge Management, New Orleans, LA, United States.