Search

Knowledge graphs (KGs) have gained prominence for representing real-world facts, with queries of KGs being crucial for their application. Aggregate queries, as one of the most important parts of KG queries (e.g., " What is the average price of cars produced in Germany?"), can provide users with valuable statistical insights. An efficient solution for KG aggregate queries is approximate aggregate queries with semantic-aware sampling (AQS). This balances the query time and result accuracy by estimating an approximate aggregate result based on random samples collected from a KG, ensuring that the relative error of the approximate aggregate result is bounded by a predefined error. However, AQS is tailored for simple aggregate queries and exhibits varying performance for complex aggregate queries. This is because a complex aggregate query usually consists of multiple simple aggregate queries, and each sub-query influences the overall processing time and result quality. Setting a large error bound for each sub-query yields quick results but with a lower quality, while aiming for high-quality results demands a smaller predefined error bound for each sub-query, leading to a longer processing time. Hence, devising efficient and effective methods for executing complex aggregate queries has emerged as a significant research challenge within contemporary KG querying. To tackle this challenge, we first introduced an execution cost model tailored for original AQS (i.e., supporting simple queries) and founded on Taylor's theorem. This model aids in identifying the initial parameters that play a pivotal role in the efficiency and efficacy of AQS. Subsequently, we conducted an in-depth exploration of the intrinsic relationship of the error bounds between a complex aggregate query and its constituent simple queries (i.e., sub-queries), and then we formalized an execution cost model for complex aggregate queries, given the accuracy constraints on the error bounds of all sub-queries. Harnessing the multi-objective optimization genetic algorithm, we refined the error bounds of all sub-queries with moderate values, to achieve a balance of query time and result accuracy for the complex aggregate query. An extensive experimental study on real-world datasets demonstrated our solution's superiority in effectiveness and efficiency. [ABSTRACT FROM AUTHOR]

A knowledge graph (KG) manages large-scale and real-world facts as a big graph in a schema-flexible manner, which has recently attracted considerable attention. It is very common that users deploy some statistical tasks on a KG to achieve the latent information of interest. There are two types of the statistical tasks, that are, topology-oriented and semantic-oriented statistical tasks. Many efforts have been made for the former one (e.g., finding the average degree of a KG). The basic idea is concluded as: estimating an approximate statistical result based on a random sample collected through a topology-aware KG sampling approach. Unfortunately, this method cannot be directly deployed to support semantic-oriented statistical tasks (e.g., achieving the average fuel economy of cars produced in Germany), because the topology-aware sampling does not consider the semantics of a KG (or we say the sample is collected only based on the topological information of a KG, while excluding the semantics of a KG), hence leading to a low-quality random sample and would significantly affect the accuracy. In this paper, we propose a semantic-aware random walk sampling on KGs to quickly and accurately collect samples that match the semantic constraint of the semantic-oriented statistical task, and obtain an approximate statistical result by well-designed unbiased estimators. Moreover, we propose an optimization on our semantic-aware sampling to improve the sampling efficiency. Finally, extensive experiments were conducted on our method, which confirmed the effectiveness and efficiency of our approach. • We propose a semantic-aware sampling method on KG to collect high-quality samples. • We present unbiased estimators to estimate the statistical results based on samples. • We propose an optimized strategy to improve our semantic-aware sampling's efficiency. • We conduct extensive experiments to verify the superiority of our solution. [ABSTRACT FROM AUTHOR]