{"ID":2852037,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.18285","arxiv_id":"2510.18285","title":"Revisiting RFID Missing Tag Identification","abstract":"We revisit the problem of missing tag identification in RFID networks by making three contributions. Firstly, we quantitatively compare and gauge the existing propositions spanning over a decade on missing tag identification. We show that the expected execution time of the best solution in the literature is $Θ\\left(N+\\frac{(1-α)^2(1-δ)^2}{ ε^2}\\right)$, where $δ$ and $ε$ are parameters quantifying the required identification accuracy, $N$ denotes the number of tags in the system, among which $αN$ tags are missing. Secondly, we analytically establish the expected execution time lower-bound for any missing tag identification algorithm as $Θ\\left(\\frac{N}{\\log N}+\\frac{(1-δ)^2(1-α)^2}{ε^2 \\log \\frac{(1-δ)(1-α)}ε}\\right)$, thus giving the theoretical performance limit. Thirdly, we develop a novel missing tag identification algorithm by leveraging a tree structure with the expected execution time of $Θ\\left(\\frac{\\log\\log N}{\\log N}N+\\frac{(1-α)^2(1-δ)^2}{ ε^2}\\right)$, reducing the time overhead by a factor of up to $\\log N$ over the best algorithm in the literature. The key technicality in our design is a novel data structure termed as collision-partition tree (CPT), built on a subset of bits in tag pseudo-IDs, leading to more balanced tree structure and reducing the time complexity in parsing the entire tree.","short_abstract":"We revisit the problem of missing tag identification in RFID networks by making three contributions. Firstly, we quantitatively compare and gauge the existing propositions spanning over a decade on missing tag identification. We show that the expected execution time of the best solution in the literature is $Θ\\left(N+\\...","url_abs":"https://arxiv.org/abs/2510.18285","url_pdf":"https://arxiv.org/pdf/2510.18285v1","authors":"[\"Kanghuai Liu\",\"Lin Chen\",\"Jihong Yu\",\"Junyi Huang\",\"Shiyuan Liu\"]","published":"2025-10-21T04:19:20Z","proceeding":"cs.NI","tasks":"[\"cs.NI\",\"cs.DS\"]","methods":"[]","has_code":false}