Proxies for shortest path and distance queries (Extended abstract)

Shuai Ma; Kaiyu Feng; Jianxin Li; Haixun Wang; Gao Cong; Jinpeng Huai

doi:10.1109/ICDE.2017.37

Proxies for shortest path and distance queries (Extended abstract)

Shuai Ma
, Kaiyu Feng
, Jianxin Li
, Haixun Wang
, Gao Cong
, Jinpeng Huai

School of Computer Science and Engineering

Beijing Advanced Innovation Center for Big Data and Brain Computing
Nanyang Technological University
Meta

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

This study investigates a light-weight data reduction technique for speeding-up shortest path and distance queries on large graphs. We propose a notion of routing proxies (or simply proxies), each of which represents a small subgraph, referred to as deterministic routing areas (DRAs). We show that routing proxies hold good properties for speeding-up shortest path and distance queries, and there exists a linear-Time algorithm to compute routing proxies and their corresponding DRAs. Finally, we discuss the experimental results, and verify that our solution is a general technique for reducing graph sizes and speeding-up shortest path and distance queries, using real-life large graphs.

Original language	English
Title of host publication	Proceedings - 2017 IEEE 33rd International Conference on Data Engineering, ICDE 2017
Publisher	IEEE Computer Society
Pages	61-62
Number of pages	2
ISBN (Electronic)	9781509065431
DOIs	https://doi.org/10.1109/ICDE.2017.37
State	Published - 16 May 2017
Event	33rd IEEE International Conference on Data Engineering, ICDE 2017 - San Diego, United States Duration: 19 Apr 2017 → 22 Apr 2017

Publication series

Name	Proceedings - International Conference on Data Engineering
ISSN (Print)	1084-4627

Conference

Conference	33rd IEEE International Conference on Data Engineering, ICDE 2017
Country/Territory	United States
City	San Diego
Period	19/04/17 → 22/04/17

Access to Document

10.1109/ICDE.2017.37

Cite this

Ma, S., Feng, K., Li, J., Wang, H., Cong, G., & Huai, J. (2017). Proxies for shortest path and distance queries (Extended abstract). In Proceedings - 2017 IEEE 33rd International Conference on Data Engineering, ICDE 2017 (pp. 61-62). Article 7929933 (Proceedings - International Conference on Data Engineering). IEEE Computer Society. https://doi.org/10.1109/ICDE.2017.37

@inproceedings{bbe203edc82e45f7b2628af6f7e450ce,

title = "Proxies for shortest path and distance queries (Extended abstract)",

abstract = "This study investigates a light-weight data reduction technique for speeding-up shortest path and distance queries on large graphs. We propose a notion of routing proxies (or simply proxies), each of which represents a small subgraph, referred to as deterministic routing areas (DRAs). We show that routing proxies hold good properties for speeding-up shortest path and distance queries, and there exists a linear-Time algorithm to compute routing proxies and their corresponding DRAs. Finally, we discuss the experimental results, and verify that our solution is a general technique for reducing graph sizes and speeding-up shortest path and distance queries, using real-life large graphs.",

author = "Shuai Ma and Kaiyu Feng and Jianxin Li and Haixun Wang and Gao Cong and Jinpeng Huai",

note = "Publisher Copyright: {\textcopyright} 2017 IEEE.; 33rd IEEE International Conference on Data Engineering, ICDE 2017 ; Conference date: 19-04-2017 Through 22-04-2017",

year = "2017",

month = may,

day = "16",

doi = "10.1109/ICDE.2017.37",

language = "英语",

series = "Proceedings - International Conference on Data Engineering",

publisher = "IEEE Computer Society",

pages = "61--62",

booktitle = "Proceedings - 2017 IEEE 33rd International Conference on Data Engineering, ICDE 2017",

address = "美国",

}

Ma, S, Feng, K, Li, J, Wang, H, Cong, G & Huai, J 2017, Proxies for shortest path and distance queries (Extended abstract). in Proceedings - 2017 IEEE 33rd International Conference on Data Engineering, ICDE 2017., 7929933, Proceedings - International Conference on Data Engineering, IEEE Computer Society, pp. 61-62, 33rd IEEE International Conference on Data Engineering, ICDE 2017, San Diego, United States, 19/04/17. https://doi.org/10.1109/ICDE.2017.37

Proxies for shortest path and distance queries (Extended abstract). / Ma, Shuai; Feng, Kaiyu; Li, Jianxin et al.
Proceedings - 2017 IEEE 33rd International Conference on Data Engineering, ICDE 2017. IEEE Computer Society, 2017. p. 61-62 7929933 (Proceedings - International Conference on Data Engineering).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Proxies for shortest path and distance queries (Extended abstract)

AU - Ma, Shuai

AU - Feng, Kaiyu

AU - Li, Jianxin

AU - Wang, Haixun

AU - Cong, Gao

AU - Huai, Jinpeng

PY - 2017/5/16

Y1 - 2017/5/16

N2 - This study investigates a light-weight data reduction technique for speeding-up shortest path and distance queries on large graphs. We propose a notion of routing proxies (or simply proxies), each of which represents a small subgraph, referred to as deterministic routing areas (DRAs). We show that routing proxies hold good properties for speeding-up shortest path and distance queries, and there exists a linear-Time algorithm to compute routing proxies and their corresponding DRAs. Finally, we discuss the experimental results, and verify that our solution is a general technique for reducing graph sizes and speeding-up shortest path and distance queries, using real-life large graphs.

AB - This study investigates a light-weight data reduction technique for speeding-up shortest path and distance queries on large graphs. We propose a notion of routing proxies (or simply proxies), each of which represents a small subgraph, referred to as deterministic routing areas (DRAs). We show that routing proxies hold good properties for speeding-up shortest path and distance queries, and there exists a linear-Time algorithm to compute routing proxies and their corresponding DRAs. Finally, we discuss the experimental results, and verify that our solution is a general technique for reducing graph sizes and speeding-up shortest path and distance queries, using real-life large graphs.

UR - https://www.scopus.com/pages/publications/85021237833

U2 - 10.1109/ICDE.2017.37

DO - 10.1109/ICDE.2017.37

M3 - 会议稿件

AN - SCOPUS:85021237833

T3 - Proceedings - International Conference on Data Engineering

SP - 61

EP - 62

BT - Proceedings - 2017 IEEE 33rd International Conference on Data Engineering, ICDE 2017

PB - IEEE Computer Society

T2 - 33rd IEEE International Conference on Data Engineering, ICDE 2017

Y2 - 19 April 2017 through 22 April 2017

ER -

Proxies for shortest path and distance queries (Extended abstract)

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this