Abstract
We describe a Big Data-practical, SQL-implementable algorithm for efficiently determining connected components for graph data stored in a Massively Parallel Processing (MPP) relational database. The algorithm described is a linear-space, randomised algorithm, always terminating with the correct answer but subject to a stochastic running time, such that for any ϵ>0 and any input graph G = (V, E) the algorithm terminates after O(log|V |) SQL queries with probability of at least, which we show empirically to translate to a quasi-linear runtime in practice.
| Original language | English |
|---|---|
| Title of host publication | Proceedings - 2020 IEEE 36th International Conference on Data Engineering, ICDE 2020 |
| Editors | Shu-Ching Chen, Karuna Joshi |
| Place of Publication | Piscataway NJ USA |
| Publisher | IEEE, Institute of Electrical and Electronics Engineers |
| Pages | 1525-1536 |
| Number of pages | 12 |
| ISBN (Electronic) | 9781728129037 |
| ISBN (Print) | 9781728129044 |
| DOIs | |
| Publication status | Published - 2020 |
| Event | IEEE International Conference on Data Engineering 2020 - Online, Dallas, United States of America Duration: 20 Apr 2020 → 24 Apr 2020 Conference number: 36th https://ieeexplore.ieee.org/xpl/conhome/9093725/proceeding (Proceedings) https://www.utdallas.edu/icde/ (Website) |
Publication series
| Name | Proceedings - International Conference on Data Engineering |
|---|---|
| Publisher | The Institute of Electrical and Electronics Engineers, Inc. |
| Volume | 2020-April |
| ISSN (Print) | 1084-4627 |
| ISSN (Electronic) | 2375-026X |
Conference
| Conference | IEEE International Conference on Data Engineering 2020 |
|---|---|
| Abbreviated title | ICDE 2020 |
| Country/Territory | United States of America |
| City | Dallas |
| Period | 20/04/20 → 24/04/20 |
| Internet address |
|
Keywords
- Big Data
- Blockchain
- Data science
- Distributed algorithms
- Distributed databases
- Graph theory
- Relational databases
- SQL