TY - JOUR
T1 - Efficient Algorithms for Kernel Aggregation Queries
AU - Chan, Tsz Nam
AU - U, Leong Hou
AU - Cheng, Reynold
AU - Yiu, Man Lung
AU - Mittal, Shivansh
N1 - Funding Information:
This work was supported by the National Key Research and Development Plan of China (No.2019YFB2102100). Tsz Nam Chan and Reynold Cheng were supported by the Research Grants Council of Hong Kong (RGC Projects HKU 17229116, 106150091, and 17205115), the University of Hong Kong (Projects 104004572, 102009508, and 104004129), and the Innovation and Technology Commission of Hong Kong (ITF project MRP/029/18). Leong Hou U was supported by the Science and Technology Development Fund, Macau SAR (File no. 0015/2019/AKP and SKL-IOTSC-2018-2020) and University of Macau (File no. MYRG2019-00119-FST). Man Lung Yiu was supported by grant GRF 152050/19E from the Hong Kong RGC
Publisher Copyright:
© 1989-2012 IEEE.
PY - 2022/6/1
Y1 - 2022/6/1
N2 - Kernel functions support a broad range of applications that require tasks like density estimation, classification, regression or outlier detection. For these tasks, a common online operation is to compute the weighted aggregation of kernel function values with respect to a set of points. However, scalable aggregation methods are still unknown for typical kernel functions (e.g., Gaussian kernel, polynomial kernel, sigmoid kernel and additive kernels) and weighting schemes. In this paper, we propose a novel and effective bounding technique, by leveraging index structures, to speed up the computation of kernel aggregation. In addition, we extend our technique to additive kernel functions, including $\chi ^2$χ2, intersection, JS and Hellinger kernels, which are widely used in different communities, e.g., computer vision, medical science, Geoscience etc. To handle the additive kernel functions, we further develop the novel and effective bound functions to efficiently evaluate the kernel aggregation. Experimental studies on many real datasets reveal that our proposed solution KARL achieves at least one order of magnitude speedup over the state-of-the-art for different types of kernel functions.
AB - Kernel functions support a broad range of applications that require tasks like density estimation, classification, regression or outlier detection. For these tasks, a common online operation is to compute the weighted aggregation of kernel function values with respect to a set of points. However, scalable aggregation methods are still unknown for typical kernel functions (e.g., Gaussian kernel, polynomial kernel, sigmoid kernel and additive kernels) and weighting schemes. In this paper, we propose a novel and effective bounding technique, by leveraging index structures, to speed up the computation of kernel aggregation. In addition, we extend our technique to additive kernel functions, including $\chi ^2$χ2, intersection, JS and Hellinger kernels, which are widely used in different communities, e.g., computer vision, medical science, Geoscience etc. To handle the additive kernel functions, we further develop the novel and effective bound functions to efficiently evaluate the kernel aggregation. Experimental studies on many real datasets reveal that our proposed solution KARL achieves at least one order of magnitude speedup over the state-of-the-art for different types of kernel functions.
KW - KARL
KW - Kernel functions
KW - lower and upper bounds
UR - http://www.scopus.com/inward/record.url?scp=85129504212&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2020.3018376
DO - 10.1109/TKDE.2020.3018376
M3 - Journal article
SN - 1041-4347
VL - 34
SP - 2726
EP - 2739
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 6
ER -