Estimation of the accuracy of a large-scale knowledge graph (KG) often
requires humans to annotate samples from the graph. How to obtain statistically
meaningful estimates for accuracy evaluation while keeping human annotation
costs low is a problem critical to the development cycle of a KG and its
practical applications. Surprisingly, this challenging problem has largely been
ignored in prior research. To address the problem, this paper proposes an
efficient sampling and evaluation framework, which aims to provide quality
accuracy evaluation with strong statistical guarantee while minimizing human
efforts. Motivated by the properties of the annotation cost function observed
in practice, we propose the use of cluster sampling to reduce the overall cost.
We further apply weighted and two-stage sampling as well as stratification for
better sampling designs. We also extend our framework to enable efficient
incremental evaluation on evolving KG, introducing two solutions based on
stratified sampling and a weighted variant of reservoir sampling. Extensive
experiments on real-world datasets demonstrate the effectiveness and efficiency
of our proposed solution. Compared to baseline approaches, our best solutions
can provide up to 60% cost reduction on static KG evaluation and up to 80% cost
reduction on evolving KG evaluation, without loss of evaluation quality.

通过使用簇抽样、加权和两阶段抽样，以及分层的抽样设计，提出了一种有效的抽样和评估框架，该框架旨在在最小化人力成本的同时提供具有强大统计保证的高质量的准确性评估。

高效知识图谱准确率评估

Efficient Knowledge Graph Accuracy Evaluation

This paper aims at a newly raising task in visual surveillance:
re-identifying people at a distance by matching body information, given several
reference examples. Most of existing works solve this task by matching a
reference template with the target individual, but often suffer from large
human appearance variability (e.g. different poses/views, illumination) and
high false positives in matching caused by conjunctions, occlusions or
surrounding clutters. Addressing these problems, we construct a simple yet
expressive template from a few reference images of a certain individual, which
represents the body as an articulated assembly of compositional and alternative
parts, and propose an effective matching algorithm with cluster sampling. This
algorithm is designed within a candidacy graph whose vertices are matching
candidates (i.e. a pair of source and target body parts), and iterates in two
steps for convergence. (i) It generates possible partial matches based on
compatible and competitive relations among body parts. (ii) It confirms the
partial matches to generate a new matching solution, which is accepted by the
Markov Chain Monte Carlo (MCMC) mechanism. In the experiments, we demonstrate
the superior performance of our approach on three public databases compared to
existing methods.

本文针对视觉监控中的一项新兴任务，通过匹配人体信息在距离上重新识别人的问题进行了研究，并提出了一种基于部件和替代组成的简单而富有表现力的模板，以及一种带有聚类抽样的有效匹配算法，实验表明该方法在三个公共数据库上具有更优秀的性能。