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 language | American English |
|---|---|
| Pages | 453-460 |
| Number of pages | 8 |
| DOIs | |
| State | Published - 2003 |
| Event | CIKM 2003: Proceedings of the Twelfth ACM International Conference on Information and Knowledge Management - New Orleans, LA, United States Duration: Nov 3 2003 → Nov 8 2003 |
Conference
| Conference | CIKM 2003: Proceedings of the Twelfth ACM International Conference on Information and Knowledge Management |
|---|---|
| Country/Territory | United States |
| City | New Orleans, LA |
| Period | 11/3/03 → 11/8/03 |
ASJC Scopus subject areas
- Decision Sciences(all)
- Business, Management and Accounting(all)
Keywords
- Graph
- Index
- Navigation
- Visualization