CoChat

PrivTrie: Effective Frequent Term Discovery under Local Differential Privacy

Wang, Ning, Xiao, Xiaokui, Yang, Yin, Hoang, Ta Duy, Shin, Hyejin, Shin, Junbum, Yu, Ge · 2018 · 2018 IEEE 34th International Conference on Data Engineering (ICDE)
Cited by 88

The DOI matches its Crossref record; 2 of the 2 references it cites were found in a registry or an index.

Abstract

A mobile operating system often needs to collect frequent new terms from users in order to build and maintain a comprehensive dictionary. Collecting keyboard usage data, however, raises privacy concerns. Local differential privacy (LDP) has been established as a strong privacy standard for collecting sensitive information from users. Currently, the best known solution for LDP-compliant frequent term discovery transforms the problem into collecting n-grams under LDP, and subsequently reconstructs terms from the collected n-grams by modelling the latter into a graph, and identifying cliques on this graph. Because the transformed problem (i.e., collecting n-grams) is very different from the original one (discovering frequent terms), the end result has poor utility. Further, this method is also rather expensive due to clique computation on a large graph. In this paper we tackle the problem head on: our proposal, PrivTrie, directly collects frequent terms from users by iteratively constructing a trie under LDP. While the methodology of building a trie is an obvious choice, obtaining an accurate trie under LDP is highly challenging. PrivTrie achieves this with a novel adaptive approach that conserves privacy budget by building internal nodes of the trie with the lowest level of accuracy necessary. Experiments using real datasets confirm that PrivTrie achieves high accuracy on common privacy levels, and consistently outperforms all previous methods.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1109/icde.2018.00079

Cites

2 of 2 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Cited by

See all 88

Metadata

Authors
Wang, N., Xiao, X., Yang, Y., Hoang, T. D., Shin, H., Shin, J., & Yu, G.
Venue
2018 IEEE 34th International Conference on Data Engineering (ICDE)
Publisher
IEEE
Published
2018-04
Pages
821-832
ISSN
1084-4627 (ISSN-L)
OpenAlex
W2794566778
Cited by
88
References
2
FWCI
4.79
Type
conference paper
Language
en
Open access
closed

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.