Fast Error-Bounded Distance Distribution Computation (Extended Abstract)

Jiahao Zhang1; Man Lung Yiu1; Bo Tang2; Qing Li1

10.1109/ICDE53745.2022.00140

2022

38th IEEE International Conference on Data Engineering (ICDE)

1063-6382

978-1-6654-0884-4

2022 IEEE 38th International Conference on Data Engineering (ICDE)

1527-1528

9-12 May 2022

Kuala Lumpur, Malaysia

10662 LOS VAQUEROS CIRCLE, PO BOX 3014, LOS ALAMITOS, CA 90720-1264 USA

IEEE COMPUTER SOC

Distance distributions have been widely applied in many real-world applications, e.g., graph analysis. Unfortunately, due to the large data volume and expensive distance computation, the exact distance distribution computation is excessively slow. Motivated by this, we present a novel approximate solution in this paper that (i) achieves error-bound guarantees and (ii) is generic to various distance measures. Our proposed method outperforms the baseline in terms of accuracy and efficiency when evaluating on three widely used distance measures with real-world datasets.

cumulative distance distribution, error-bound guaranteed approximation, lower and upper bounds

Others

English

CPCI-S

GRF PolyU from the Hong Kong RGC["152050/19E","112114/17E"]

Computer Science

Computer Science, Artificial Intelligence ; Computer Science, Information Systems ; Computer Science, Theory & Methods

WOS:000855078401064

Web of Science

1.Department of Computing, Hong Kong Polytechnic University
2.Department of Computer Science and Engineering, Southern University of Science and Technology

Jiahao Zhang,Man Lung Yiu,Bo Tang,et al. Fast Error-Bounded Distance Distribution Computation (Extended Abstract)[C]. 10662 LOS VAQUEROS CIRCLE, PO BOX 3014, LOS ALAMITOS, CA 90720-1264 USA:IEEE COMPUTER SOC,2022:1527-1528.