Source author record

Mingfei Li

Mingfei Li appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Applications

Catalog footprint

What is connected

3works

2topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2012arXiv

(1+epsilon)-Distance Oracle for Planar Labeled Graph

Given a vertex-labeled graph, each vertex $v$ is attached with a label from a set of labels. The vertex-label query desires the length of the shortest path from the given vertex to the set of vertices with the given label. We show how to construct an oracle if the given graph is planar, such that $O(\frac{1}εn\log n)$ storing space is needed, and any vertex-label query could be answered in $O(\frac{1}ε\log n\log ρ)$ time with stretch $1+ε$. $ρ$ is the radius of the given graph, which is half of the diameter. For the case that $ρ= O(\log n)$, we construct an oracle that achieves $O(\log n)$ query time, without changing the order of storing space.

preprint2012arXiv

Incubators vs Zombies: Fault-Tolerant, Short, Thin and Lanky Spanners for Doubling Metrics

Recently Elkin and Solomon gave a construction of spanners for doubling metrics that has constant maximum degree, hop-diameter O(log n) and lightness O(log n) (i.e., weight O(log n)w(MST). This resolves a long standing conjecture proposed by Arya et al. in a seminal STOC 1995 paper. However, Elkin and Solomon's spanner construction is extremely complicated; we offer a simple alternative construction that is very intuitive and is based on the standard technique of net tree with cross edges. Indeed, our approach can be readily applied to our previous construction of k-fault tolerant spanners (ICALP 2012) to achieve k-fault tolerance, maximum degree O(k^2), hop-diameter O(log n) and lightness O(k^3 log n).

preprint2010arXiv

Hierarchical mixture models for assessing fingerprint individuality

The study of fingerprint individuality aims to determine to what extent a fingerprint uniquely identifies an individual. Recent court cases have highlighted the need for measures of fingerprint individuality when a person is identified based on fingerprint evidence. The main challenge in studies of fingerprint individuality is to adequately capture the variability of fingerprint features in a population. In this paper hierarchical mixture models are introduced to infer the extent of individualization. Hierarchical mixtures utilize complementary aspects of mixtures at different levels of the hierarchy. At the first (top) level, a mixture is used to represent homogeneous groups of fingerprints in the population, whereas at the second level, nested mixtures are used as flexible representations of distributions of features from each fingerprint. Inference for hierarchical mixtures is more challenging since the number of unknown mixture components arise in both the first and second levels of the hierarchy. A Bayesian approach based on reversible jump Markov chain Monte Carlo methodology is developed for the inference of all unknown parameters of hierarchical mixtures. The methodology is illustrated on fingerprint images from the NIST database and is used to make inference on fingerprint individuality estimates from this population.