2023

[1]Wenjun Zhang

[1]College of Engineering, University of Saskatchewan, 57 Camous Dr,
Saskatoon, S7N 5A9, SK, Canada

2]College of Science, Thompson Rivers University, 835 University Dr, Kamloops,
V2C 0C8, BC, Canada

# Context-based Ontology Modelling for Database: Enabling ChatGPT for Semantic
Database Management

Wenjun Lin<EMAIL_ADDRESS>Paul Babyn<EMAIL_ADDRESS>Yan Yan
<EMAIL_ADDRESS><EMAIL_ADDRESS>*  [

###### Abstract

This research paper explores the use of ChatGPT in database management.
ChatGPT, an AI-powered chatbot, has limitations in performing tasks related to
database management due to the lack of standardized vocabulary and grammar for
representing database semantics. To address this limitation, the paper
proposes a solution that involves developing a set of syntaxes that can
represent database semantics in natural language. The syntax is used to
convert database schemas into natural language formats, providing a new
application of ChatGPT in database management.

The proposed solution is demonstrated through a case study where ChatGPT is
used to perform two tasks, semantic integration, and tables joining. Results
demonstrate that the use of semantic database representations produces more
precise outcomes and avoids common mistakes compared to cases with no semantic
representation.

The proposed method has the potential to speed up the database management
process, reduce the level of understanding required for database domain
knowledge, and enable automatic database operations without accessing the
actual data, thus illuminating privacy protection concerns when using AI. This
paper provides a promising new direction for research in the field of AI-based
database management.

###### keywords:

ChatGPT, Database management, Semantic database representation, Semantic
integration, Tables joining

##  1 Introduction

ChatGPT is a conversational chatbot that uses artificial intelligence (AI) and
machine learning (ML) techniques, combined with natural language processing
(NLP) methods, to produce human-like text. It was launched in November 2022
and quickly gained popularity, reaching over one million users within just
five days thorp2023chatgpt . ChatGPT’s ability to produce human-like text and
perform a wide range of tasks has made it a popular tool for many users,
including answering questions, writing short stories, composing music, solving
math problems, performing language translations, and even computer
programming.

Database operation involves the manipulation of data and information using
specific syntax or commands, similar to computer programming. In database
operations, these commands are known as database queries, which are used to
retrieve, update, and manipulate data stored in a database. Similarly, in
computer programming, instructions are written in a programming language, such
as C or Python, in order to specify the desired behaviour of a computer
program.

There has been an expectation that ChatGPT could assist in creating database
queries, just as it can assist in creating computer programs. However,
creating database queries requires an understanding of the database itself,
and there is no conventional way to represent database semantics. This problem
limits ChatGPT’s ability to perform tasks related to database management.

In this paper, we present a solution to this problem by developing a set of
syntax that can represent database semantics, such as table structure and
relationships, in natural language. This allows for the creation of semantic
representations of databases that can be understood by ChatGPT and enable it
to perform database management tasks. Our work is demonstrated through a case
study, where ChatGPT is used to perform two tasks: semantic integration and
table joining. Our results show that the use of semantic database
representations produces more precise outcomes and avoids common mistakes
compared to cases with no semantic representation.

The proposed method transforms database schemas into natural language formats,
providing a new application of ChatGPT in database management. This study has
the potential to speed up the database management process, reduce the level of
understanding required for database domain knowledge, and enable automatic
database operations without accessing the actual data, thus illuminating
privacy protection concerns when using AI.

The rest of the paper is organized as follows: In Section 2, we provide a
review of related work in the area of database management using AI. Then, we
describe our proposed solution in Section 3. Section 4 presents the results
and discussion of our case study. Finally, we discuss the potential benefits
and limitations of our work and conclude with future directions for research.

##  2 Literature review

###  2.1 AI-based database queries generation

The use of AI models for generating database queries through natural language
has been the focus of several research studies. One such model proposed by
Bais et al. bais2016model  utilizes NLP techniques to analyze and interpret
user queries by performing morphological, syntactic, and semantic analysis,
resulting in a valid database query in SQL. Similarly, Sawant et al.
sawant2022ai  implemented a system that can generate SQL queries from text and
speech input using NLP and deep learning techniques such as Long Short Term
Memory (LSTM).

Other studies, such as Ghosh et al. ghosh2014automatic , Nagare et al.
nagare2017automatic , and Kombade et al. kombade2020natural  , have also
utilized techniques such as lexical analysis, syntax analysis, and semantic
analysis to extract SQL queries from natural language input. Kombade et al.
kombade2020natural  even considered the use of abbreviations in NLP to
generate SQL queries. The implementation of these studies used python with a
GUI for input and output, and the user could provide input through speech or
text.

Despite the progress made in this field, limitations still exist in the
ability of AI models to accurately generate database queries from natural
language due to the complexity and ambiguity of natural language, as well as
the lack of standardized vocabulary and grammar for representing database
structures. For instance, Nagare et al. nagare2017automatic  mentions that the
system checks the validity of the user’s query, but it is unclear how the
query’s validity is determined. Moreover, the studies only consider basic
database operations such as select, delete, and update. Complex operations,
such as joining multiple tables and semantic integration, have not been
investigated.

###  2.2 Semantic integration

Semantic integration is crucial for resolving mismatches in data
representation between related databases. In today’s digital world,
organizations are generating and storing vast amounts of data in various
databases, which often leads to inconsistencies in the data representation.
For instance, one database may use the attribute ”Social Security Number” to
identify individuals, while another database may use the attribute ”SSN”. In
such cases, it is crucial to determine the relationships between these
attributes in order to accurately compare and combine the data from these
databases.

Several approaches for semantic integration have been developed in recent
years. Tools like Silk volz2009silk , LIMES ngomo2011limes , and PARIS
suchanek2011paris  use string similarity metrics, functional properties, and
manual configuration to detect matching attributes. WebPie urbani2012webpie
and LINDA bohm2012linda  are fully automatic systems that use techniques such
as neighborhood checks and block placement. MateTee morales2017matetee  and
RDF2VEC ristoski2016rdf2vec  are more recent approaches that utilize
embeddings and machine learning to find similarities. However, the task of
matching entities can become complicated with the presence of entities in
abbreviates lantzaki2017radius .

The existing approaches are heavily relying on domain expertise and require
complex preparations. For example, dataset-based approaches morales2017matetee
; ristoski2016rdf2vec  require determining the relationships among attributes.
Keyword-based approaches volz2009silk ; ngomo2011limes  depend on the accuracy
of metadata, while URI-based approaches urbani2012webpie  strongly depend on
dereferencing HTTP URIs.

##  3 Methodology

###  3.1 ChatGPT

ChatGPT is a language model developed by OpenAI van2023chatgpt . It is a type
of AI algorithm trained to predict the likelihood of a given sequence of words
based on the context of the words that come before it. This technology is
based on self-attention mechanisms humphreys2016attentional  and has been
trained on a massive dataset of text, allowing it to generate sophisticated
and seemingly intelligent writing. ChatGPT is designed to converse with users
in English and other languages on a wide range of topics, making it ideal for
use in chatbots, customer service, content creation, and language translation
tasks.

One of the applications of ChatGPT is to assist in programming, which can be
achieved in two ways. Firstly, ChatGPT can serve as a programming assistant or
tool. For instance, developers can ask ChatGPT programming-related questions
and obtain recommendations and suggestions about general workflows and steps.
Secondly, ChatGPT can generate code snippets directly, resulting in enhanced
productivity and time-saving benefits for developers.

Despite its advanced natural language processing capability and successes in
assisting programming, ChatGPT has not yet been able to generate queries for
databases because database schemas, which contain vital information about
database structures, are frequently written in the form of a graph rather than
natural language.

###  3.2 Context-based Ontology Modelling for Database

This study presents a new method, Context-based Ontology Modelling for
Database (COM-DB), which is aimed at converting database schemas into natural
language. COM-DB is built upon our previous research on ontology modelling
lin2023ontology , which utilizes constructs like context-of, monodirectional
relationship, and bi-directional relationship to describe the relationship of
concepts in databases.

In this study, we focus on the usage of the “context-of” construct for
describing database schema, especially at the conceptual data model level. A
conceptual schema or conceptual data model is a map of concepts and their
relationships used for databases. The key feature of COM-DB is the ability to
convert these relationships into natural language, which makes it more
accessible to ChatGPT. To demonstrate the effectiveness of COM-DB, we provide
two examples that illustrate how the “context-of” construct can be used to
describe the relationship of headers within one table and the relationship of
tables within one database.

Figure 1: Describing relationships of headers within one table using COM-DB

The example in Figure 1 demonstrates how COM-DB can be used to describe the
relationships between headers within a database table. The left side of the
figure shows a typical database table schema, which includes the name of the
table and the names of its headers.

COM-DB converts this schema into two parts: the base schema, which describes
the names of the headers in the table, and the contextual schema, which uses
the “context-of” construct to describe relationships among headers. In this
example, the headers ”ADDRESS”, ”CITY”, ”STATE”, and ”COUNTY” are related and
are used to store information about patients’ addresses.

The contextual schema condenses this information into a single sentence by
using the “context-of” construct to describe the relationship between these
headers and the patients’ addresses. Specifically, it states that ”ADDRESS,
CITY, STATE, COUNTY are in the context of patients’ address”. This represents
four relationships in one sentence, making the information more easily
understandable and less verbose.

Figure 2: Entity-Relationship schema of a hospital database
walonoski2018synthea

Figure 2 is an Entity-Relationship schema of a hospital database. Similar to
the first example, COM-DB represents the database in two parts. The first
part, basic schema, explain headers in each table. Some basic schemas are as
follows:

⬇

Given a table ’allergies’ with headers: Id, START, STOP, PATIENT, ENCOUNTER,
CODE, DESCRIPTION.

And a table ’careplans’ with headers: Id, START, STOP, PATIENT, ENCOUNTER,
CODE, DESCRIPTION.

And a table ’conditions’ with headers: START, STOP, PATIENT, ENCOUNTER, CODE,
DESCRIPTION.

And a table ’devices’ with headers: START, STOP, PATIENT, ENCOUNTER, CODE,
DESCRIPTION, UDI.

And a table ’encounters’ with headers: Id, START, STOP, PATIENT, ORGANIZATION,
PROVIDER, PAYER, ENCOUNTERCLASS, CODE, DESCRIPTION, BASE_ENCOUNTER_COST,
TOTAL_CLAIM_COST, PAYER_COVERAGE.

And a table ’imaging_studies’ with headers: Id, DATE, PATIENT, ENCOUNTER,
BODYSITE_CODE, BODYSITE_DESCRIPTION, MODALITY_CODE, MODALITY_DESCRIPTION,
SOP_CODE, SOP_DESCRIPTION.

And a table ’immunizations’ with headers: DATE, PATIENT, ENCOUNTER, CODE,
DESCRIPTION, BASE_COST.

And a table ’medications’ with headers: START, STOP, PATIENT, PAYER,
ENCOUNTER, CODE, DESCRIPTION, BASE_COST, PAYER_COVERAGE, DISPENSES, TOTALCOST.

And a table ’observations’ with headers: DATE, PATIENT, ENCOUNTER, CODE,
DESCRIPTION, VALUE, UNITS, TYPE.

And a table ’organizations’ with headers: Id, NAME, ADDRESS, CITY, STATE, ZIP,
LAT, LON, PHONE, REVENUE, UTILIZATION.

And a table ’patients’ with headers: Id, BIRTHDATE, DEATHDATE, SSN, PREFIX,
FIRST, LAST, SUFFIX, MAIDEN, MARITAL, RACE, ETHNICITY, GENDER, BIRTHPLACE,
ADDRESS, CITY, STATE, COUNTY.

And a table ’payers’ with headers: Id, NAME, ADDRESS, CITY,
STATE_HEADQUARTERED, ZIP, PHONE, AMOUNT_COVERED, AMOUNT_UNCOVERED, REVENUE,
COVERED_ENCOUNTERS, UNCOVERED_ENCOUNTERS, COVERED_MEDICATIONS,
UNCOVERED_MEDICATIONS, COVERED_PROCEDURES, UNCOVERED_PROCEDURES,
COVERED_IMMUNIZATIONS, UNCOVERED_IMMUNIZATIONS, UNIQUE_CUSTOMERS, QOLS_AVG,
MEMBER_MONTHS.

And a table ’procedures’ with headers: DATE, PATIENT, ENCOUNTER, CODE,
DESCRIPTION, BASE_COST.

And a table ’providers’ with headers: Id, ORGANIZATION, NAME, GENDER,
SPECIALITY, ADDRESS, CITY, STATE, ZIP.

In addition, the second part, contextual schema, is as follows:

⬇

allergies, careplans, conditions, devices, immunizations, observations,
procedures, imaging_studies are in the context of patients, encounters.

encounters are in the context of patients, organizations, providers, payers.

medications are in the context of patients, encounters, payers.

providers are in the context of organizations.

Note that the contextual schema is shown in a condensed form. For example,
“allergies, careplans, conditions, devices, immunizations, observations,
procedures, imaging_studies are in the context of patients, encounters.”
represents 8 × 2 = 16 relationships. These relationships are between 8 tables
“allergies, careplans, conditions, devices, immunizations, observations,
procedures, imaging_studies” and 2 tables “patients, encounters”.

We use these examples to show practical applications of COM-DB and how it can
be used to generate natural language descriptions of complex database schemas.
Overall, the methodology of this study involves designing and implementing the
COM-DB method, which includes utilizing the “context-of” construct and other
ontology modelling constructs to convert database schema into natural
language. The effectiveness of this method is demonstrated through the use of
two examples, which show how it can be used to complete two sophisticated
database management tasks. The effectiveness of the method is demonstrated in
the case study.

##  4 Case study

The case study aims to showcase the efficacy of the proposed COM-DB system.
The system’s primary feature is the “context-of” construct, which utilizes
natural language to capture database semantics like table structure and
relationships. The primary objective of the system is to create semantic
representations of databases that can be easily comprehended by ChatGPT,
enabling it to perform various database management tasks.

The case study provides empirical evidence to support the effectiveness of
COM-DB. Two sample databases are collected from the literature,
Synthea_Alabama walonoski2018synthea  and BDA_EHR silvestri2019big . Based on
those databases, two experiments are conducted that represent typical tasks
conducted during database integration: semantic integration and tables
joining. In both experiments, ChatGPT is used to perform tasks with and
without the COM-DB-based schema. The study repeats each experiment 10 times to
ensure reliability and eliminate the potential inconsistency in ChatGPT’s
performance. Results demonstrated illustrate an average result from the
repeated experiments.

###  4.1 Experiment 1: Semantic Integration

Semantic integration involves merging two tables with the same category of
information. Different headers’ names among different tables often cause
incompatibility issues. ’patients_A’ and ’patients_B’ are tables of patient
information from BDA_EHR and Synthea_Alabama, respectively. ’patients_A’
contains headers: Id_patients, Name, Surname, Date of Birth, Place of Birth,
Address, Gender, Blood Type, Job. And ’patients_B’ contains headers: Id,
BIRTHDATE, DEATHDATE, SSN, PREFIX, FIRST, LAST, SUFFIX, MAIDEN, MARITAL, RACE,
ETHNICITY, GENDER, BIRTHPLACE, ADDRESS, CITY, STATE, COUNTY.

The goal of this experiment is to identify headers from table ’patients_A’ and
table ’patients_B’ which contain the same information, knowing that some
headers may need to be combined or split for the mapping. The ideal mapping is
illustrated in Table 1.

Table 1: The ideal header mapping results of table ’patients_A’ and table ’patients_B’ patients_A | patients_B
---|---
Name | FIRST
Surname | LAST
Date of Birth | BIRTHDATE
Place of Birth | BIRTHPLACE
Address | ADDRESS CITY STATE COUNTY
Gender | GENDER
|

Figure 3 shows the input and output of using ChatGPT without COM-DB based
schema. The message from the icon ’FF’ is the input, while the message from
the graphical icon is the output from ChatGPT. The input contains two parts of
information. The first part is to explain the situation, which contains the
names of headers in each table. Note that only the headers are provided here,
without any sample data or data type. The second part “Identify the headers
from table ’patients_A’ and table ’patients_B’ which contain the same
information. Some headers may need to be combined or split.” is an explanation
of the task to be completed by ChatGPT.

Figure 3: Experiment 1, header mapping without COM-DB based schema

The output in Figure 3 shows that ChatGPT can understand the task and perform
it to a degree. It matches Date of Birth and BIRTHDATE, Place of Birth and
BIRTHPLACE, Gender and GENDER, correctly. However, it failed to match Name
with FIRST, and Surname with LAST. In addition, ADDRESS in ’patients_B’ should
be used with other headers CITY, STATE, COUNTY. This was not noticed by
ChatGPT.

Figure 4 shows the input and output of using ChatGPT with COM-DB based schema.
In addition to the inputs used in Figure 3, the ontology model information is
described as “In table ’patients_A’, headers Name and Surname are in the
context of patients’ name. In table ’patients_B’, headers ADDRESS, CITY,
STATE, and COUNTY are in the context of patients’ address.”

Figure 4: Experiment 1, header mapping with COM-DB based schema

Figure 4 illustrates a typical result from ChaGPT and demonstrates the COM-DB
based schema improves the performance of semantic integration as ChatGPT has
successfully identified all mappings as expected.

###  4.2 Experiment 2: Tables Joining

Tables joining involves generating a new table or view that combines data from
multiple tables. This process requires an Entity Relationship schema which
doesn’t have a conventional way to be represented in natural language. To
demonstrate the effectiveness of COM-DB based schema in representing the
Entity Relationship, Synthea_Alabama is used in this experiment. The database
contains 14 tables as shown in Figure 2. The goal of the experiment is to
create a SQL query that generates a list of careplans, with corresponding
providers’ and patients’ identity information. The careplans are advices from
providers (such as physicians) to patients. A SQL query needs to properly join
four tables: careplans, providers, patients, and encounters. The encounters
table plays a critical role here as it connects the patients table with the
careplans table. This information is typically contained in an Entity
Relationship schema.

Figure 5 shows the input and output of using ChatGPT without COM-DB based
schema. The input contains two parts of information. The first part is to
explain all tables with their contained headers in alphabetical order. Similar
to Experiment 1, only the headers are provided here without any sample data or
data type. The second part, “To create a SQL query that generates a list of
careplans, with corresponding providers’ and patients’ identity information.”
is an explanation of the task to be completed by ChatGPT.

Figure 5: Experiment 2 Generate a new view from multiple tables without COM-DB
based schema. The conversation is split into two columns, from left to right.

The output from ChatGPT is verified by executing the SQL query in the hospital
database. The result is shown in Figure 6. From the result, it was found the
query doesn’t work due to the error “no such column: careplans.PROVIDER”. The
root cause of this error is the missing the encounters table as explained
earlier.

Figure 6: Experiment 2, SQL query results without COM-DB based schema

Figure 7 shows the input and output of using ChatGPT with COM-DB based schema
that explains the context information of each table. In this case, the COM-DB
based schema describes relations between tables. Figure 8 verifies the SQL
query by executing it in the hospital database. It shows that ChatGPT has
successfully generated the query that results in a correct view.

Figure 7: Experiment 2 Generate a new view from multiple tables with COM-DB
based schema. The conversation is split into two columns, from left to right.
Figure 8: Experiment 2, SQL query results with COM-DB based schema

##  5 Discussions

The results of the experiments indicate that ChatGPT performs better in both
semantic integration and tables joining tasks when using the COM-DB-based
schema. The context information provided by the ontology models helps ChatGPT
to better complete the tasks. The study demonstrates that the “context-of”
construct in COM-DB captures certain context information which may not be
included in a conventional ontology model. This context information determines
the relations between concepts, which helps to eliminate ambiguities between
concepts and increases the chances of success during database integration.

In addition, COM-DB enables automatic database operations without compromising
privacy protections. Unlike existing AI-enabled database operations, which
require the AI algorithm to access all data in the database, COM-DB only
generates a schema from the table structure, instead of its content. This
schema does not contain any privacy information, making it safe to share with
third-party services such as ChatGPT. By sending the schema to ChatGPT, the
risk of privacy breach is significantly reduced, as ChatGPT can perform
automated database operations without ever accessing sensitive data. This
allows businesses and organizations to leverage the power of AI and automation
to streamline their operations and improve efficiency, without sacrificing the
privacy and security of their customers’ data. With COM-DB, businesses can
have peace of mind knowing that their data is secure and protected, while
still enjoying the benefits of automated database operations.

##  6 Conclusion

This paper explores the use of ChatGPT in the area of database management,
highlighting the challenges of using natural language processing to perform
database queries. Our research presents a solution by developing a set of
syntaxes to represent database semantics in natural language. These syntaxes,
called COM-DB, enable ChatGPT to perform tasks related to database management,
such as semantic integration and tables joining. Our case study shows that the
use of semantic representations in database management leads to more precise
outcomes and reduces common mistakes compared to cases without such
representations.

Our research aims to contribute to the field of database management by
introducing a novel approach for converting database schemas into natural
language format, thereby opening up new applications for ChatGPT. This
approach has the potential to deliver significant benefits, including faster
database management, reduced domain knowledge requirements, and enhanced
privacy protection through automated database operations that do not require
access to actual data.

Future work involves expanding the scope of our method to include more complex
database operations and testing it on larger databases. Furthermore, we intend
to investigate the feasibility of incorporating other natural language
processing models into database management and explore the possibilities of
combining various models to enhance their capabilities.

In conclusion, our research demonstrates the potential of natural language
processing models to be employed in the field of database management,
providing a new way to interact with and manipulate databases. By leveraging
the power of ChatGPT alongside our COM-DB syntaxes, we have demonstrated that
complex database operations can be executed using natural language, offering a
new approach to simplify database management and enhance productivity.

Acknowledgments

This study is supported by Natural Sciences and Engineering Research Council
of Canada, Alliance grant #ALLRP 555161 - 20.

## References

  *   * (1) Thorp, H.H.: ChatGPT is fun, but not an author. American Association for the Advancement of Science (2023)
  * (2) Bais, H., Machkour, M., Koutti, L.: A model of a generic natural language interface for querying database. international journal of intelligent systems and applications 8(2), 35 (2016)
  * (3) Sawant, A., Raina, R., Patil, A., Pardeshi, A.: Ai model to generate sql queries from natural language instructions through voice. In: Journal of Physics: Conference Series, vol. 2273, p. 012014 (2022). IOP Publishing
  * (4) Ghosh, P.K., Dey, S., Sengupta, S.: Automatic sql query formation from natural language query. International Journal of Computer Applications 975, 8887 (2014)
  * (5) Nagare, P., Indhe, S., Sabale, D., Thorat, G., Chaturvedi, P.: Automatic sql query formation from natural language query. Int. Res. J. Eng. Technol 4, 1589–1591 (2017)
  * (6) Kombade, C., More, M., Pujari, A., Patil, S.: Natural language processing with some abbreviation to sql. International journal for research in applied science and engineering technology 8(5), 1046–1048 (2020)
  * (7) Volz, J., Bizer, C., Gaedke, M., Kobilarov, G.: Silk-a link discovery framework for the web of data. Ldow 538, 53 (2009)
  * (8) Ngomo, A.-C.N., Auer, S.: Limes-a time-efficient approach for large-scale link discovery on the web of data. integration 15(3) (2011)
  * (9) Suchanek, F.M., Abiteboul, S., Senellart, P.: Paris: Probabilistic alignment of relations, instances, and schema. arXiv preprint arXiv:1111.7164 (2011)
  * (10) Urbani, J., Kotoulas, S., Maassen, J., Van Harmelen, F., Bal, H.: Webpie: A web-scale parallel inference engine using mapreduce. Journal of Web Semantics 10, 59–75 (2012)
  * (11) Böhm, C., De Melo, G., Naumann, F., Weikum, G.: Linda: distributed web-of-data-scale entity matching. In: Proceedings of the 21st ACM International Conference on Information and Knowledge Management, pp. 2104–2108 (2012)
  * (12) Morales, C., Collarana, D., Vidal, M.-E., Auer, S.: Matetee: A semantic similarity metric based on translation embeddings for knowledge graphs. In: Web Engineering: 17th International Conference, ICWE 2017, Rome, Italy, June 5-8, 2017, Proceedings 17, pp. 246–263 (2017). Springer
  * (13) Ristoski, P., Paulheim, H.: Rdf2vec: Rdf graph embeddings for data mining. In: The Semantic Web–ISWC 2016: 15th International Semantic Web Conference, Kobe, Japan, October 17–21, 2016, Proceedings, Part I 15, pp. 498–514 (2016). Springer
  * (14) Lantzaki, C., Papadakos, P., Analyti, A., Tzitzikas, Y.: Radius-aware approximate blank node matching using signatures. Knowledge and Information Systems 50, 505–542 (2017)
  * (15) van Dis, E.A., Bollen, J., Zuidema, W., van Rooij, R., Bockting, C.L.: Chatgpt: five priorities for research. Nature 614(7947), 224–226 (2023)
  * (16) Humphreys, G.W., Sui, J.: Attentional control and the self: the self-attention network (san). Cognitive neuroscience 7(1-4), 5–17 (2016)
  * (17) Lin, W., Babyn, P., Yan, Y., Zhang, W.: Ontology in the modern computer era. Enterprise Information Systems (2023, submitted)
  * (18) Walonoski, J., Kramer, M., Nichols, J., Quina, A., Moesel, C., Hall, D., Duffett, C., Dube, K., Gallagher, T., McLachlan, S.: Synthea: An approach, method, and software mechanism for generating synthetic patients and the synthetic electronic health care record. Journal of the American Medical Informatics Association 25(3), 230–238 (2018)
  * (19) Silvestri, S., Esposito, A., Gargiulo, F., Sicuranza, M., Ciampi, M., De Pietro, G.: A big data architecture for the extraction and analysis of ehr data. In: 2019 IEEE World Congress on Services (SERVICES), vol. 2642, pp. 283–288 (2019). IEEE


# Random Sampling Plus Fake Data: Multidimensional Frequency Estimates With
Local Differential Privacy

Héber H. Arcolezi<EMAIL_ADDRESS>0000-0001-8059-7094
Femto-ST Institute, Univ. Bourg. Franche-Comté, CNRSBelfortFrance ,  Jean-
François Couchot<EMAIL_ADDRESS>0000-0001-6437-5598
Femto-ST Institute, Univ. Bourg. Franche-Comté, CNRSBelfortFrance ,  Bechara
Al Bouna<EMAIL_ADDRESS>0000-0002-7741-9905 TICKET Lab., Antonine
UniversityHadat-BaabdaLebanon and  Xiaokui Xiao<EMAIL_ADDRESS>0000-0003-0914-4580 School of Computing, National University of
SingaporeSingaporeSingapore

(2021)

###### Abstract.

With local differential privacy (LDP), users can privatize their data and thus
guarantee privacy properties before transmitting it to the server (a.k.a. the
aggregator). One primary objective of LDP is frequency (or histogram)
estimation, in which the aggregator estimates the number of users for each
possible value. In practice, when a study with rich content on a population is
desired, the interest is in the multiple attributes of the population, that is
to say, in multidimensional data ($d\geq 2$). However, contrary to the problem
of frequency estimation of a single attribute (the majority of the works), the
multidimensional aspect imposes to pay particular attention to the privacy
budget. This one can indeed grow extremely quickly due to the composition
theorem. To the authors’ knowledge, two solutions seem to stand out for this
task: 1) splitting the privacy budget for each attribute, i.e., send each
value with $\frac{\epsilon}{d}$-LDP (Spl), and 2) random sampling a single
attribute and spend all the privacy budget to send it with $\epsilon$-LDP
(Smp). Although Smp adds additional sampling error, it has proven to provide
higher data utility than the former Spl solution. However, we argue that
aggregators (who are also seen as attackers) are aware of the sampled
attribute and its LDP value, which is protected by a ”less strict”
$e^{\epsilon}$ probability bound (rather than $e^{\epsilon/d}$). This way, we
propose a solution named Random Sampling plus Fake Data (RS+FD), which allows
creating uncertainty over the sampled attribute by generating fake data for
each non-sampled attribute; RS+FD further benefits from amplification by
sampling. We theoretically and experimentally validate our proposed solution
on both synthetic and real-world datasets to show that RS+FD achieves nearly
the same or better utility than the state-of-the-art Smp solution.

Local differential privacy, Multidimensional data, Frequency estimation,
Sampling

††journalyear: 2021††copyright: acmcopyright††conference: Proceedings of the
30th ACM International Conference on Information and Knowledge Management;
November 1–5, 2021; Virtual Event, QLD, Australia††booktitle: Proceedings of
the 30th ACM International Conference on Information and Knowledge Management
(CIKM ’21), November 1–5, 2021, Virtual Event, QLD, Australia††price:
15.00††doi: 10.1145/3459637.3482467††isbn: 978-1-4503-8446-9/21/11††ccs:
Security and privacy Privacy-preserving protocols

##  1\. Introduction

###  1.1. Background

In recent years, differential privacy (DP) (Dwork et al., 2006; Dwork, 2006)
has been increasingly accepted as the current standard for data privacy (Dwork
et al., 2014; Abadi et al., 2016; Aktay et al., 2020; Rogers et al., 2020). In
the centralized model of DP, a trusted curator has access to compute on the
entire raw data of users (e.g., the Census Bureau (Abowd, 2018; Garfinkel,
2021)). By ‘trusted’, we mean that curators do not misuse or leak private
information from individuals. However, this assumption does not always hold in
real life (McCandless et al., 2021). To address non-trusted services, with the
local model of DP (LDP) (Kasiviswanathan et al., 2008), each user applies a DP
mechanism to their own data before sending it to an untrusted curator (a.k.a.
the aggregator). The LDP model allows collecting data in unprecedented ways
and, therefore, has led to several adoptions by industry. For instance, big
tech companies like Google, Apple, and Microsoft, reported the implementation
of LDP mechanisms to gather statistics in well-known systems (i.e., Google
Chrome browser (Erlingsson et al., 2014), Apple iOS and macOS (Team, 2017),
and Windows 10 operation system (Ding et al., 2017)).

###  1.2. Problem statement

On collecting data, in practice, one is often interested in multiple
attributes of a population, i.e., multidimensional data. For instance, in
cloud services, demographic information (e.g., age, gender) and user habits
could provide several insights to further develop solutions to specific
groups. Similarly, in digital patient records, users might be linked with both
their demographic and clinical information.

In this paper, we focus on the problem of private frequency (or histogram)
estimation on multiple attributes with LDP. This is a primary objective of
LDP, in which the data collector decodes all the privatized data of the users
and can then estimate the number of users for each possible value. The single
attribute frequency estimation task has received considerable attention in the
literature (Wang et al., 2017; Kairouz et al., 2016; Acharya et al., 2019;
Alvim et al., 2018; Erlingsson et al., 2014; Ding et al., 2017; Xiong et al.,
2020; Zhao et al., 2019; Li et al., 2020) as it is a building block for more
complex tasks (e.g., heavy hitter estimation (Bassily and Smith, 2015; Wang et
al., 2021a; Bassily et al., 2017), estimating marginals (Peng et al., 2019;
Zhang et al., 2018; Ren et al., 2018; Fanti et al., 2016), frequent itemset
mining (Wang et al., 2018; Qin et al., 2016)).

In the LDP setting, the aggregator already knows the users’ identifiers, but
not their private data. We assume there are $d$ attributes
$A=\\{A_{1},A_{2},...,A_{d}\\}$, where each attribute $A_{j}$ with a discrete
domain $\mathcal{D}_{j}$ has a specific number of values $|A_{j}|=k_{j}$. Each
user $u_{i}$ for $i\in\\{1,2,...,n\\}$ has a tuple
$\textbf{v}^{(i)}=(v^{(i)}_{1},v^{(i)}_{2},...,v^{(i)}_{d})$, where
$v^{(i)}_{j}$ represents the value of attribute $A_{j}$ in record
$\textbf{v}^{(i)}$. Thus, for each attribute $A_{j}$, the analyzer’s goal is
to estimate a $k_{j}$-bins histogram, including the frequency of all values in
$\mathcal{D}_{j}$.

###  1.3. Context of the problem

Regarding multiple attributes, as also noticed in the recent survey work on
LDP in (Xiong et al., 2020), most studies for collecting multidimensional data
with LDP mainly focused on numerical data (e.g., (Nguyên et al., 2016; Wang et
al., 2019; Duchi et al., 2018; Wang et al., 2021b)). Unlike the single
attribute frequency estimation problem (the majority of the works), the
multidimensional setting needs to consider the allocation of the privacy
budget. To the authors’ knowledge, there are mainly two solutions for
satisfying LDP by randomizing v. We will simply omit the index notation
$\textbf{v}^{(i)}$ in the analysis as we focus on one arbitrary user $u_{i}$
here. On the one hand, due to the composition theorem (Dwork et al., 2014),
users can split the privacy budget for each attribute and send all randomized
values with $\frac{\epsilon}{d}$-LDP to the aggregator (Spl). The other
solution is based on random sampling a single attribute and spend all the
privacy budget to send it (Smp). More precisely, each user tells the
aggregator which attribute is sampled, and what is the perturbed value for it
ensuring $\epsilon$-LDP; the aggregator would not receive any information
about the remaining $d-1$ attributes.

Although the later Smp solution adds sampling error, in the literature (Wang
et al., 2019; Nguyên et al., 2016; Wang et al., 2017; Arcolezi et al., 2021;
Wang et al., 2021b), it has proven to provide higher data utility than the
former Spl solution. However, aggregators (who are also seen as attackers) are
aware of the sampled attribute and its LDP value, which is protected by a
”less strict” $e^{\epsilon}$ probability bound (rather than $e^{\epsilon/d}$).
In other words, while both solutions provide $\epsilon$-LDP, we argue that
using the Smp solution may be unfair with some users. For instance, on
collecting multidimensional health records (i.e., demographic and clinical
data), users that randomly sample a demographic attribute (e.g., gender) might
be less concerned to report their data than those whose sampled attribute is
”disease” (e.g., if positive for human immunodeficiency viruses - HIV).

This way, there is a privacy-utility trade-off between the Spl and Smp
solutions. With these elements in mind, we formulate the problematic of this
paper as: For the same privacy budget $\epsilon$, is there a solution for
multidimensional frequency estimates that provides better data utility than
Spl and more protection than Smp?

###  1.4. Purpose and contributions

In this paper, we intend to solve the aforementioned problematic by answering
the following question: What if the sampling result (i.e., the selected
attribute) was not disclosed with the aggregator? Since the sampling step
randomly selects an attribute $j\in[1,d]$ (we slightly abuse the notation and
use $j$ for $A_{j}$), we propose that users add uncertainty about the sampled
attribute through generating $d-1$ fake data, i.e., one for each non-sampled
attribute.

We call our solution Random Sampling plus Fake Data (RS+FD). Fig. 1
illustrates the overview of RS+FD in comparison with the aforementioned known
solutions, namely, Spl and Smp. More precisely, with RS+FD, the client-side
has two steps: local randomization and fake data generation. First, an LDP
mechanism preserves privacy for the data of the sampled attribute. Second, the
fake data generator provides fake data for each $d-1$ non-sampled attribute.
This way, the privatized data is ”hidden” among fake data and, hence, the
sampling result is not disclosed along with the users’ report (and
statistics).

Figure 1. Overview of our random sampling plus fake data (RS+FD) solution in
comparison with two known solutions, namely, Spl and Smp, where
$Uni(d)=Uniform(\\{1,2,...,d\\})$.

What is more, we notice that RS+FD can enjoy privacy amplification by sampling
(Chaudhuri and Mishra, 2006; Li et al., 2012; Balle et al., 2018, 2020;
Kasiviswanathan et al., 2008). That is, if one randomly sample a dataset
without replacement using a sampling rate $\beta<1$, it suffices to use a
privacy budget $\epsilon^{\prime}>\epsilon$ to satisfy $\epsilon$-DP, where
$\frac{e^{\epsilon^{\prime}}-1}{e^{\epsilon}-1}=\frac{1}{\beta}$ (Li et al.,
2012). This way, given that the sampled dataset for each attribute has non-
overlapping users, i.e., each user selects an attribute with sampling
probability $\beta=\frac{1}{d}$, to satisfy $\epsilon$-LDP, each user can
apply an LDP mechanism with
$\epsilon^{\prime}=\ln{\left(d\cdot(e^{\epsilon}-1)+1\right)}\geq\epsilon$.

To summarize, this paper makes the following contributions:

  * •

We propose a novel solution, namely, RS+FD for multidimensional frequency
estimates under LDP, which is generic to be used with any existing LDP
mechanism developed for single-frequency estimation.

  * •

Using state-of-the-art LDP mechanisms, we develop four protocols within RS+FD
and analyze them analytically and experimentally.

  * •

We conducted a comprehensive and extensive set of experiments on both
synthetic and real-world datasets. Under the same privacy guarantee, results
show that our proposed protocols with RS+FD achieve similar or better utility
than using the state-of-the-art Smp solution.

Paper’s outline: The remainder of this paper is organized as follows. In
Section 2, we revise the privacy notions that we are considering, i.e., LDP,
the LDP mechanisms we further analyze in this paper, and amplification by
sampling. In Section 3, we introduce our RS+FD solution, the integration of
state-of-the-art LDP mechanisms within RS+FD, and their analysis. In Section
4, we present experimental results. In Section 5, we discuss our results and
review related work. Lastly, in Section 6, we present the concluding remarks
and future directions.

##  2\. Preliminaries

In this section, we briefly recall LDP (Subsection 2.1), the LDP mechanisms we
will apply in this paper (Subsection 2.2), and amplification by sampling
(Subsection 2.3).

###  2.1. Local differential privacy

Local differential privacy, initially formalized in (Kasiviswanathan et al.,
2008), protects an individual’s privacy during the data collection process. A
formal definition of LDP is given in the following:

###### Definition 0 ($\epsilon$-Local Differential Privacy).

A randomized algorithm ${\mathcal{A}}$ satisfies $\epsilon$-LDP if, for any
pair of input values $v_{1},v_{2}\in Domain(\mathcal{A})$ and any possible
output $y$ of ${\mathcal{A}}$:

$\Pr[{\mathcal{A}}(v_{1})=y]\leq
e^{\epsilon}\cdot\Pr[{\mathcal{A}}(v_{2})=y]\textrm{.}$

Similar to the centralized model of DP, LDP also enjoys several important
properties, e.g., immunity to post-processing ($F(\mathcal{A})$ is
$\epsilon$-LDP for any function $F$) and composability (Dwork et al., 2014).
That is, combining the results from $m$ differentially private mechanisms also
satisfies DP. If these mechanisms are applied separately in disjointed subsets
of the dataset, $\epsilon=max(\epsilon_{1}$-, …, $\epsilon_{m})$-LDP (parallel
composition). On the other hand, if these mechanisms are sequentially applied
to the same dataset, $\epsilon=\sum_{i=1}^{m}\epsilon_{i}$-LDP (sequential
composition).

###  2.2. LDP mechanisms

Randomized response (RR), a surveying technique proposed by Warner (Warner,
1965), has been the building block for many LDP mechanisms. Let
$A_{j}=\\{v_{1},v_{2},...,v_{k_{j}}\\}$ be a set of $k_{j}=|A_{j}|$ values of
a given attribute and let $\epsilon$ be the privacy budget, we review two
state-of-the-art LDP mechanisms for single-frequency estimation (a.k.a.
frequency oracles) that will be used in this paper.

####  2.2.1. Generalized randomized response (GRR)

The k-Ary RR (Kairouz et al., 2016) mechanism extends RR to the case of
$k_{j}\geq 2$ and is also referred to as direct encoding (Wang et al., 2017)
or generalized RR (GRR) (Wang et al., 2018, 2020b; Zhang et al., 2018).
Throughout this paper, we use the term GRR for this LDP mechanism. Given a
value $B=v_{i}$, GRR($v_{i}$) outputs the true value $v_{i}$ with probability
$p=\frac{e^{\epsilon}}{e^{\epsilon}+k_{j}-1}$, and any other value $v_{l}$ for
$l\neq i$ with probability
$q=\frac{1-p}{k_{j}-1}=\frac{1}{e^{\epsilon}+k_{j}-1}$. GRR satisfies
$\epsilon$-LDP since $\frac{p}{q}=e^{\epsilon}$.

The estimated frequency $\hat{f}(v_{i})$ that a value $v_{i}$ occurs, for
$i\in[1,k_{j}]$, is calculated as (Wang et al., 2017; Wang et al., 2018):

(1) $\hat{f}(v_{i})=\frac{N_{i}-nq}{n(p-q)}\textrm{,}$

in which $N_{i}$ is the number of times the value $v_{i}$ has been reported
and $n$ is the total number of users. In (Wang et al., 2017), it is shown that
this is an unbiased estimation of the true frequency, and the variance of this
estimation is
$Var[\hat{f}(v_{i})]=\frac{q(1-q)}{n(p-q)^{2}}+\frac{f(v_{i})(1-p-q)}{n(p-q)}$.
In the case of small $f(v_{i})\sim 0$, this variance is dominated by the first
term. Thus, the approximate variance of this estimation for GRR is (Wang et
al., 2017):

(2)
$Var[\hat{f}_{GRR}(v_{i})]=\frac{e^{\epsilon}+k_{j}-2}{n(e^{\epsilon}-1)^{2}}\textrm{.}$

####  2.2.2. Optimized unary encoding (OUE)

For a given value $v$, $B=Encode(v)$, where $B=[0,0,...,1,0,...0]$, a
$k_{j}$-bit array in which only the $v$-th position is set to one.
Subsequently, the bits from $B$ are flipped, depending on two parameters $p$
and $q$, to generate a privatized vector $B^{\prime}$. More precisely,
$Pr[B^{\prime}[i]=1]=$ p if $B[i]=1$ and $Pr[B^{\prime}[i]=1]=$ q if $B[i]=0$.
This unary-encoding (UE) mechanism satisfies $\epsilon$-LDP for
$\epsilon=ln\left(\frac{p(1-q)}{(1-p)q}\right)$ (Erlingsson et al., 2014).
Wang et al. (Wang et al., 2017) propose optimized UE (OUE), which selects
”optimized” parameters ($p=\frac{1}{2}$ and $q=\frac{1}{e^{\epsilon}+1}$) to
minimize the approximate variance of UE-based mechanisms while still
satisfying $\epsilon$-LDP. The estimation method used in (1) equally applies
to OUE. As shown in (Wang et al., 2017), the OUE approximate variance is
calculated as:

(3)
$Var[\hat{f}_{OUE}(v_{i})]=\frac{4e^{\epsilon}}{n(e^{\epsilon}-1)^{2}}\textrm{.}$

####  2.2.3. Adaptive LDP mechanism

Comparing (2) with (3), elements $k_{j}-2+e^{\epsilon}$ is replaced by
$4e^{\epsilon}$. Thus, as highlighted in (Wang et al., 2017), when
$k_{j}<3e^{\epsilon}+2$, the utility loss with GRR is lower than the one of
OUE. Throughout this paper, we will use the term adaptive (ADP) to denote this
best-effort and dynamic selection of LDP mechanism.

###  2.3. Privacy amplification by sampling

One well-known approach for increasing the privacy of a DP mechanism is to
apply the mechanism to a random subsample of the dataset (Chaudhuri and
Mishra, 2006; Li et al., 2012; Balle et al., 2018, 2020; Kasiviswanathan et
al., 2008). The intuition is that an attacker is unable to distinguish which
data samples were used in the analysis. Li et al. (Li et al., 2012, Theorem 1)
theoretically prove this effect.

###### Theorem 2.

Amplification by Sampling (Li et al., 2012). Let $\mathcal{A}$ be an
$\epsilon^{\prime}$-DP mechanism and $\mathcal{S}$ to be a sampling algorithm
with sampling rate $\beta$. Then, if $\mathcal{S}$ is first applied to a
dataset $\mathbb{D}$, which is later privatized with $\mathcal{A}$, the
derived result satisfies DP with
$\epsilon=\ln{\left(1+\beta(e^{\epsilon^{\prime}}+1)\right)}$.

##  3\. Random Sampling Plus Fake Data

In this section, we present the overview of our RS+FD solution (Subsection
3.1), and the integration of the local randomizers presented in Subsection 2.2
within RS+FD (Subsections 3.2, 3.3, and 3.4).

###  3.1. Overview of RS+FD

We consider the local DP model, in which there are two entities, namely, users
and the aggregator (an untrusted curator). Let $n$ be the total number of
users, $d$ be the total number of attributes,
$\textbf{k}=[k_{1},k_{2},...,k_{d}]$ be the domain size of each attribute,
$\mathcal{A}$ be a local randomizer, and $\epsilon$ be the privacy budget.
Each user holds a tuple $\textbf{v}=(v_{1},v_{2},...,v_{d})$, i.e., a private
value per attribute.

Client-Side. The client-side is split into two steps, namely, local
randomization and fake data generation (cf. Fig. 1). Initially, each user
samples a unique attribute $j$ uniformly at random and applies an LDP
mechanism to its value $v_{j}$. Indeed, RS+FD is generic to be applied with
any existing LDP mechanisms (e.g., GRR (Kairouz et al., 2016), UE-based
protocols (Erlingsson et al., 2014; Wang et al., 2017), Hadamard Response
(Acharya et al., 2019)). Next, for each $d-1$ non-sampled attribute $i$, the
user generates one random fake data. Finally, each user sends the (LDP or
fake) value of each attribute to the aggregator, i.e., a tuple
$\textbf{y}=(y_{1},y_{2},...,y_{d})$. This way, the sampling result is not
disclosed with the aggregator. In summary, Alg. 1 exhibits the pseudocode of
our RS+FD solution.

Aggregator. For each attribute $j\in[1,d]$, the aggregator performs frequency
(or histogram) estimation on the collected data by removing bias introduced by
the local randomizer and fake data.

Algorithm 1 Random Sampling plus Fake Data (RS+FD)

1:Input : tuple $\textbf{v}=(v_{1},v_{2},...,v_{d})$, domain size of
attributes $\textbf{k}=[k_{1},k_{2},...,k_{d}]$, privacy parameter $\epsilon$,
local randomizer $\mathcal{A}$.

2:Output : privatized tuple $\textbf{y}=(y_{1},y_{2},...,y_{d})$.

3:$\epsilon^{\prime}=\ln{\left(d\cdot(e^{\epsilon}-1)+1\right)}$
$\triangleright$ amplification by sampling (Li et al., 2012)

4:$j\leftarrow Uniform(\\{1,2,...,d\\})$ $\triangleright$ Selection of
attribute to privatize

5:$B_{j}\leftarrow v_{j}$

6:$y_{j}\leftarrow\mathcal{A}(B_{j},k_{j},\epsilon^{\prime})$ $\triangleright$
privatize data of the sampled attribute

7:for $i\in\\{1,2,...,d\\}/j$ do$\triangleright$ non-sampled attributes

8: $y_{i}\leftarrow\textit{Uniform}(\\{1,...,k_{i}\\})$ $\triangleright$
generate fake data

9:end for

10:return : $\textbf{y}=(y_{1},y_{2},...,y_{d})$ $\triangleright$ sampling
result is not disclosed

Privacy analysis. Let $\mathcal{A}$ be any existing LDP mechanism, Algorithm 1
satisfies $\epsilon$-LDP, in a way that
$\epsilon^{\prime}=\ln{\left(d\cdot(e^{\epsilon}-1)+1\right)}$. Indeed, we
observe that our scenario is equivalent to sampling a dataset $\mathbb{D}$
without replacement with sampling rate $\beta=\frac{1}{d}$ in the centralized
setting of DP, which enjoys privacy amplification (cf. Subsection 2.3). With
the local model, users privatize their data locally with a DP model. This way,
to satisfy $\epsilon$-LDP, an amplified privacy parameter
$\epsilon^{\prime}>\epsilon$ can be used.

Limitations. Similar to other sampling-based methods for collecting
multidimensional data under LDP (Duchi et al., 2018; Nguyên et al., 2016; Wang
et al., 2019; Wang et al., 2021b), our RS+FD solution also entails sampling
error, which is due to observing a sample instead of the entire population. In
addition, in comparison with the Smp solution, RS+FD requires more computation
on the user side because of the fake data generation part. Yet, communication
cost is still equal to the Spl solution, i.e., each user sends one message per
attribute. Lastly, while RS+FD utilizes an amplified
$\epsilon^{\prime}\geq\epsilon$, there is also bias generated from uniform
fake data that may require a sufficient number of users $n$ to eliminate the
noise.

###  3.2. RS+FD with GRR

Client side. Integrating GRR as the local randomizer $\mathcal{A}$ into Alg. 1
(RS+FD[GRR]) requires no modification. Initially, on the client-side, each
user randomly samples an attribute $j$. Next, the value $v_{j}$ is privatized
with GRR (cf. Subsection 2.2.1) using the size of the domain $k_{j}$ and the
privacy parameter $\epsilon^{\prime}$. In addition, for each non-sampled $d-1$
attribute $i$, the user also generates fake data uniformly at random according
to the domain size $k_{i}$. Lastly, the user transmits the privatize tuple y,
which includes the LDP value of the true data ”hidden” among fake data.

Aggregator RS+FD[GRR]. On the server-side, for each attribute $j\in[1,d]$, the
aggregator estimates $\hat{f}(v_{i})$ for the frequency of each value
$i\in[1,k_{j}]$ as:

(4) $\hat{f}(v_{i})=\frac{N_{i}dk_{j}-n(d-1+qk_{j})}{nk_{j}(p-q)}\textrm{,}$

in which $N_{i}$ is the number of times the value $v_{i}$ has been reported,
$p=\frac{e^{\epsilon^{\prime}}}{e^{\epsilon^{\prime}}+k_{j}-1}$, and
$q=\frac{1-p}{k_{j}-1}$.

###### Theorem 1.

For $j\in[1,d]$, the estimation result $\hat{f}(v_{i})$ in (4) is an unbiased
estimation of $f(v_{i})$ for any value $v_{i}\in\mathcal{D}_{j}$.

Proof 1

$\displaystyle E[\hat{f}(v_{i})]$
$\displaystyle=E\left[\frac{N_{i}dk_{j}-n(d-1+qk_{j})}{nk_{j}(p-q)}\right]$
$\displaystyle=\frac{d}{n(p-q)}E[Ni]-\frac{d-1+qk_{j}}{k_{j}(p-q)}\textrm{.}$

Let us focus on

$\displaystyle E[N_{i}]$
$\displaystyle=\frac{1}{d}\left(pnf(v_{i})+q(n-nf(v_{i}))\right)+\frac{d-1}{dk_{j}}n$
$\displaystyle=\frac{n}{d}\left(f(v_{i})(p-q)+q+\frac{d-1}{k_{j}}\right)\textrm{.}$

Thus,

$E[\hat{f}(v_{i})]=f(v_{i})\textrm{.}$

###### Theorem 2.

The variance of the estimation in (4) is:

(5)
$\begin{gathered}\operatorname{VAR}(\hat{f}(v_{i}))=\frac{d^{2}\delta(1-\delta)}{n(p-q)^{2}}\textrm{,
where}\\\
\delta=\frac{1}{d}\left(q+f(v_{i})(p-q)+\frac{(d-1)}{k_{j}}\right)\textrm{.}\end{gathered}$

Proof 2

Thanks to (4) we have

(6)
$\operatorname{VAR}(\hat{f}(v_{i}))=\frac{\operatorname{VAR}(N_{i})d^{2}}{n^{2}(p-q)^{2}}\textrm{.}$

Since $N_{i}$ is the number of times value $v_{i}$ is observed, it can be
defined as $N_{i}=\sum_{z=1}^{n}X_{z}$ where $X_{z}$ is equal to 1 if the user
$z$, $1\leq z\leq n$ reports value $v_{i}$, and 0 otherwise. We thus have
$\operatorname{VAR}(N_{i})=\sum_{z=1}^{n}\operatorname{VAR}(X_{z})=n\operatorname{VAR}(X)$,
since all the users are independent. According to the probability tree in Fig.
2,

$P(X=1)=P(X^{2}=1)=\delta=\frac{1}{d}\left(q+f(v_{i})(p-q)+\frac{(d-1)}{k_{j}}\right)\textrm{.}$

We thus have $\operatorname{VAR}(X)=\delta-\delta^{2}=\delta(1-\delta)$ and,
finally,

(7)
$\operatorname{VAR}(\hat{f}(v_{i}))=\frac{d^{2}\delta(1-\delta)}{n(p-q)^{2}}.$

ptRS+FDptFake datapt$B^{\prime}=v_{l\neq
i}$$1-1/k_{j}$pt$B^{\prime}=v_{i}$$1/k_{j}$$1-1/d$ptTrue datapt$B=v_{l\neq
i}$pt$B^{\prime}=v_{i}$$q$pt$B^{\prime}=v_{i}$$p$pt$B=v_{i}$pt$B^{\prime}=v_{l\neq
i}$$q$pt$B^{\prime}=v_{i}$$p$$1/d$ Figure 2. Probability tree for Eq. (4)
(RS+FD[GRR]).

###  3.3. RS+FD with OUE

Client side. To use UE-based protocols (OUE in our work) as local randomizer
$\mathcal{A}$ in Alg. 1, there is, first, a need to define the fake data
generation procedure. We propose two solutions: (i) RS+FD[OUE-z] in Alg. 2,
which applies OUE to $d-1$ zero-vectors, and (ii) RS+FD[OUE-r] in Alg. 3,
which applies OUE to $d-1$ one-hot-encoded fake data (uniform at random). We
note that, on the one hand, introducing fake data through privatizing zero-
vectors introduces less noise as there is only one parameter to perturb each
bit, i.e., $Pr[0\rightarrow 1]=q$. On the other hand, starting with zero-
vectors may not suffice to ”hide” the sampled attribute if the perturbation
probability $q$ is too small. Studying this effect is out of the scope of this
paper and is left as future work.

Algorithm 2 RS+FD[OUE-z]

1:Input : tuple $\textbf{v}=(v_{1},v_{2},...,v_{d})$, domain size of
attributes $\textbf{k}=[k_{1},k_{2},...,k_{d}]$, privacy parameter $\epsilon$,
local randomizer OUE.

2:Output : privatized tuple
$\textbf{B}^{\prime}=(B_{1}^{\prime},B_{2}^{\prime},...,B_{d}^{\prime})$.

3:$\epsilon^{\prime}=\ln{\left(d\cdot(e^{\epsilon}-1)+1\right)}$
$\triangleright$ amplification by sampling (Li et al., 2012)

4:$j\leftarrow Uniform(\\{1,2,...,d\\})$ $\triangleright$ Selection of
attribute to privatize

5:$B_{j}=Encode(v_{j})=[0,0,...,1,0,...0]$ $\triangleright$ one-hot-encoding

6:$B_{j}^{\prime}\leftarrow OUE(B_{j},\epsilon^{\prime})$ $\triangleright$
privatize real data with OUE

7:for $i\in\\{1,2,...,d\\}/j$ do$\triangleright$ non-sampled attributes

8: $B_{i}\leftarrow[0,0,...,0]$ $\triangleright$ initialize zero-vectors

9: $B_{i}^{\prime}\leftarrow OUE(B_{i},\epsilon^{\prime})$ $\triangleright$
randomize zero-vector with OUE

10:end for

11:return :
$\textbf{B}^{\prime}=(B_{1}^{\prime},B_{2}^{\prime},...,B_{d}^{\prime})$
$\triangleright$ sampling result is not disclosed

Algorithm 3 RS+FD[OUE-r]

1:Input : tuple $\textbf{v}=(v_{1},v_{2},...,v_{d})$, domain size of
attributes $\textbf{k}=[k_{1},k_{2},...,k_{d}]$, privacy parameter $\epsilon$,
local randomizer OUE.

2:Output : privatized tuple
$\textbf{B}^{\prime}=(B_{1}^{\prime},B_{2}^{\prime},...,B_{d}^{\prime})$.

3:$\epsilon^{\prime}=\ln{\left(d\cdot(e^{\epsilon}-1)+1\right)}$
$\triangleright$ amplification by sampling (Li et al., 2012)

4:$j\leftarrow Uniform(\\{1,2,...,d\\})$ $\triangleright$ Selection of
attribute to privatize

5:$B_{j}=Encode(v_{j})=[0,0,...,1,0,...0]$ $\triangleright$ one-hot-encoding

6:$B_{j}^{\prime}\leftarrow OUE(B_{j},\epsilon^{\prime})$ $\triangleright$
privatize real data with OUE

7:for $i\in\\{1,2,...,d\\}/j$ do$\triangleright$ non-sampled attributes

8: $y_{i}\leftarrow\textit{Uniform}(\\{1,...,k_{i}\\})$ $\triangleright$
generate fake data

9: $B_{i}\leftarrow Encode(y_{i})$ $\triangleright$ one-hot-encoding

10: $B_{i}^{\prime}\leftarrow OUE(B_{i},\epsilon^{\prime})$ $\triangleright$
randomize fake data with OUE

11:end for

12:return :
$\textbf{B}^{\prime}=(B_{1}^{\prime},B_{2}^{\prime},...,B_{d}^{\prime})$
$\triangleright$ sampling result is not disclosed

Aggregator RS+FD[OUE-z]. On the server-side, if fake data are generated with
OUE applied to zero-vectors, as in Alg. 2, for each attribute $j\in[1,d]$, the
aggregator estimates $\hat{f}(v_{i})$ for the frequency of each value
$i\in[1,k_{j}]$ as:

(8) $\hat{f}(v_{i})=\frac{d(N_{i}-nq)}{n(p-q)}\textrm{,}$

in which $N_{i}$ is the number of times the value $v_{i}$ has been reported,
$n$ is the total number of users, $p=\frac{1}{2}$, and
$q=\frac{1}{e^{\epsilon^{\prime}}+1}$.

###### Theorem 3.

For $j\in[1,d]$, the estimation result $\hat{f}(v_{i})$ in (8) is an unbiased
estimation of $f(v_{i})$ for any value $v_{i}\in\mathcal{D}_{j}$.

Proof 3

$\displaystyle E[\hat{f}(v_{i})]$
$\displaystyle=E\left[\frac{d(N_{i}-nq)}{n(p-q)}\right]=\frac{d(E[N_{i}]-nq)}{n(p-q)}$
$\displaystyle=\frac{d}{n(p-q)}E[N_{i}]-\dfrac{dq}{p-q}.$

We have successively

$\displaystyle E[N_{i}]$
$\displaystyle=\frac{n}{d}\left(pf(v_{i})+q(1-f(v_{i}))\right)+\frac{(d-1)nq}{d}$
$\displaystyle=\frac{n}{d}\left(f(v_{i})(p-q)+dq\right)\textrm{.}$

Thus,

$E[\hat{f}(v_{i})]=f(v_{i})\textrm{.}$

###### Theorem 4.

The variance of the estimation in (8) is:

(9)
$\begin{gathered}\operatorname{VAR}(\hat{f}(v_{i}))=\frac{d^{2}\delta(1-\delta)}{n(p-q)^{2}}\textrm{,
where}\\\
\delta=\frac{1}{d}\left(dq+f(v_{i})(p-q)\right)\textrm{.}\end{gathered}$

The proof for Theorem 4 follows Proof 3 and is omitted here. In this case,
$\delta$ follows the probability tree in Fig. 3.

ptRS+FDptFake
datapt$B_{i}=0$pt$B_{i}^{\prime}=0$$1-q$pt$B_{i}^{\prime}=1$$q$$1-1/d$ptTrue
datapt$B_{i}=0$pt$B_{i}^{\prime}=0$$1-q$pt$B_{i}^{\prime}=1$$q$pt$B_{i}=1$pt$B_{i}^{\prime}=0$$1-p$pt$B_{i}^{\prime}=1$$p$$1/d$
Figure 3. Probability tree for Eq. (8) (RS+FD[OUE-z]).

Aggregator RS+FD[OUE-r]. Otherwise, if fake data are generated with OUE
applied to one-hot-encoded random data, as in Alg. 3, for each attribute
$j\in[1,d]$, the aggregator estimates $\hat{f}(v_{i})$ for the frequency of
each value $i\in[1,k_{j}]$ as:

(10)
$\hat{f}(v_{i})=\frac{N_{i}dk_{j}-n\left[qk_{j}+(p-q)(d-1)+qk_{j}(d-1))\right]}{nk_{j}(p-q)}\textrm{,}$

in which $N_{i}$ is the number of times the value $v_{i}$ has been reported,
$p=\frac{1}{2}$, and $q=\frac{1}{e^{\epsilon^{\prime}}+1}$.

###### Theorem 5.

For $j\in[1,d]$, the estimation result $\hat{f}(v_{i})$ in (10) is an unbiased
estimation of $f(v_{i})$ for any value $v_{i}\in\mathcal{D}_{j}$.

Proof 5

$\displaystyle E[\hat{f}(v_{i})]$
$\displaystyle=E\left[\frac{N_{i}dk_{j}-n\left[qk_{j}+(p-q)(d-1)+qk_{j}(d-1))\right]}{nk_{j}(p-q)}\right]$
$\displaystyle=\frac{dE[N_{i}]}{n(p-q)}-\frac{(p-q)(d-1)+qdk_{j}}{k_{j}(p-q)}.$

We have successively

$\displaystyle E[N_{i}]$
$\displaystyle=\frac{n}{d}\left(pf(v_{i})+q(1-f(v_{i}))\right)+\frac{n(d-1)}{d}(\frac{p}{k_{j}}+\frac{k_{j}-1}{k_{j}}q)$
$\displaystyle=\frac{n}{d}\left(f(v_{i})(p-q)+q)\right)+\frac{n(d-1)}{dk_{j}}(p-q+k_{j}q)\textrm{.}$

Thus,

$E[\hat{f}(v_{i})]=f(v_{i})\textrm{.}$

###### Theorem 6.

The variance of the estimation in (10) is:

(11)
$\begin{gathered}\operatorname{VAR}(\hat{f}(v_{i}))=\frac{d^{2}\delta(1-\delta)}{n(p-q)^{2}}\textrm{,
where}\\\
\delta=\frac{1}{d}\left(q+f(v_{i})(p-q)+\frac{(d-1)}{k_{j}}\left(p+(k_{j}-1)q\right)\right)\textrm{.}\end{gathered}$

The proof for Theorem 6 follows Proof 3 and is omitted here. In this case,
$\delta$ follows the probability tree in Fig. 4.

ptRS+FDptFake
datapt$B_{i}=0$pt$B_{i}^{\prime}=0$$1-q$pt$B_{i}^{\prime}=1$$q$$1-1/k_{j}$pt$B_{i}=1$pt$B_{i}^{\prime}=0$$1-p$pt$B_{i}^{\prime}=1$$p$$1/k_{j}$$1-1/d$ptTrue
datapt$B_{i}=0$pt$B_{i}^{\prime}=0$$1-q$pt$B_{i}^{\prime}=1$$q$pt$B_{i}=1$pt$B_{i}^{\prime}=0$$1-p$pt$B_{i}^{\prime}=1$$p$$1/d$
Figure 4. Probability tree for Eq. (10) (RS+FD[OUE-r]).

###  3.4. Analytical analysis: RS+FD with ADP

In a multidimensional setting with different domain sizes for each attribute,
a dynamic selection of LDP mechanisms is preferred (as in Subsection 2.2.3).
Because our estimators in (4), (8), and (10) are unbiased, their variance is
equal to the mean squared error (MSE) that is commonly used in practice as an
accuracy metric (Wang et al., 2020a, b; Wang et al., 2021b). In this work, we
analyze the approximate variances $\operatorname{VAR}_{1}$ for RS+FD[GRR] in
(5) and $\operatorname{VAR}_{2}$ for RS+FD[OUE-z] in (9), in which
$f(v_{i})=0$. This is, first, because under the local model of DP, the real
frequency $f(v_{i})$ is unknown and, second, because in real life the vast
majority of values appear very infrequently. Notice that this is common
practice in the literature (e.g., cf. (Wang et al., 2017, 2021b)), which
provides an approximation for the variance of the protocols.

Assume there are $d\geq 2$ attributes with domain size
$\textbf{k}=[k_{1},k_{2},...,k_{d}]$ and a privacy budget $\epsilon^{\prime}$.
For each attribute $j$ with domain size $k_{j}$, to select RS+FD[GRR], we are
then left to evaluate if $\operatorname{VAR}_{1}\leq\operatorname{VAR}_{2}$.
This is equivalent to check whether,

(12)
$\frac{d^{2}\delta_{1}(1-\delta_{1})}{n(p_{1}-q_{1})^{2}}-\frac{d^{2}\delta_{2}(1-\delta_{2})}{n(p_{2}-q_{2})^{2}}\leq
0\textrm{,}$

in which $p_{1}=\frac{e^{\epsilon^{\prime}}}{e^{\epsilon^{\prime}}+k_{j}-1}$,
$q_{1}=\frac{1-p_{1}}{k_{j}-1}$, $p_{2}=\frac{1}{2}$,
$q_{2}=\frac{1}{e^{\epsilon^{\prime}}+1}$,
$\delta_{1}=\frac{1}{d}\left(q_{1}+\frac{d-1}{k_{j}}\right)$, and
$\delta_{2}=q_{2}$. In other words, if (12) is less than or equal to zero, the
utility loss is lower with RS+FD[GRR]; otherwise, if (12) is positive,
RS+FD[OUE-z] should be selected. Throughout this paper, we will refer to this
dynamic selection of our protocols as RS+FD[ADP].

For the sake of illustration, Fig. 5 illustrates a 3D visualization of (12) by
fixing $\epsilon^{\prime}=\ln(3)$ and $n=20000$, and by varying $d\in[2,10]$
and $k_{j}\in[2,20]$, which are common values for real-world datasets (cf.
Subsection 4.1). In this case, one can notice in Fig. 5 that neither
RS+FD[GRR] nor RS+FD[OUE-z] will always provide the lowest variance value,
which reinforces the need for an adaptive mechanism. For instance, with the
selected parameters, for lower values of $k_{j}$, RS+FD[GRR] can provide lower
estimation errors even if $d$ is large. On the other hand, as soon as the
domain size starts to grow, e.g., $k_{j}\geq 10$, one is better off with
RS+FD[OUE-z] even for small values of $d\geq 3$, as its variance in (9) does
not depend on $k_{j}$.

Figure 5. Analytical evaluation of (12) that allows a dynamic selection
between RS+FD[GRR] with variance $\operatorname{VAR}_{1}$ and RS+FD[OUE-z]
with variance $\operatorname{VAR}_{2}$. Parameters were set as
$\epsilon^{\prime}=\ln(3)$, $n=20000$, $d\in[2,10]$, and $k_{j}\in[2,20]$.

##  4\. Experimental Validation

In this section, we present the setup of our experiments in Subsection 4.1,
the results with synthetic data in Subsection 4.2, and the results with real-
world data in Subsection 4.3.

###  4.1. Setup of experiments

Environment. All algorithms were implemented in Python 3.8.5 with NumPy 1.19.5
and Numba 0.53.1 libraries. The codes we developed and used for all
experiments are available in a Github
repository111https://github.com/hharcolezi/ldp-protocols-mobility-cdrs. In all
experiments, we report average results over 100 runs as LDP algorithms are
randomized.

Synthetic datasets. Our first set of experiments are conducted on six
synthetic datasets. The distribution of values in each attribute follows an
uniform distribution, for all synthetic datasets.

  * •

For the first two synthetic datasets, we fix the number of attributes $d=5$
and the domain size of each attribute as $\textbf{k}=[10,10,...,10]$
(uniform), and vary the number of users as $n=50000$ and $n=500000$.

  * •

Similarly, for the third and fourth synthetic datasets, we fix the number of
attributes $d=10$ and the domain size of each attribute as
$\textbf{k}=[10,10,...,10]$ (uniform), and vary the number of users as
$n=50000$ and $n=500000$.

  * •

Lastly, for the fifth and sixth synthetic datasets, we fix the number of users
as $n=500000$. Next, we set the number of attributes $d=10$ with domain size
of each attribute as $\textbf{k}=[10,20,...,90,100]$ for one dataset, and we
set the number of attributes $d=20$ with domain size of each attribute as
$\textbf{k}=[10,10,20,20,...,100,100]$ for the other.

Real-world datasets. In addition, we also conduct experiments on four real-
world datasets with non-uniform distributions.

  * •

Nursery. A dataset from the UCI machine learning repository (Dua and Graff,
2017) with $d=9$ categorical attributes and $n=12960$ samples. The domain size
of each attribute is $\textbf{k}=[3,5,4,4,3,2,3,3,5]$, respectively.

  * •

Adult. A dataset from the UCI machine learning repository (Dua and Graff,
2017) with $d=9$ categorical attributes and $n=45222$ samples after cleaning
the data. The domain size of each attribute is
$\textbf{k}=[7,16,7,14,6,5,2,41,2]$, respectively.

  * •

MS-FIMU. An open dataset from (Arcolezi et al., 2020a) with $d=6$ categorical
attributes and $n=88935$ samples. The domain size of each attribute is
$\textbf{k}=[3,3,8,12,37,11]$, respectively.

  * •

Census-Income. A dataset from the UCI machine learning repository (Dua and
Graff, 2017) with $d=33$ categorical attributes and $n=299285$ samples. The
domain size of each attribute is
$\textbf{k}=[9,52,47,17,3,...,43,43,43,5,3,3,3,2]$, respectively.

Evaluation and metrics. We vary the privacy parameter in a logarithmic range
as $\epsilon=[\ln(2),\ln(3),...,\ln(7)]$, which is within range of values
experimented in the literature for multidimensional data (e.g., in (Wang et
al., 2019) the range is $\epsilon=[0.5,...,4]$ and in (Wang et al., 2021b) the
range is $\epsilon=[0.1,...,10]$).

We use the MSE metric averaged per the number of attributes $d$ to evaluate
our results. Thus, for each attribute $j$, we compute for each value
$v(i)\in\mathcal{D}_{j}$ the estimated frequency $\hat{f}(v_{i})$ and the real
one $f(v_{i})$ and calculate their differences. More precisely,

(13)
$MSE_{avg}=\frac{1}{d}\sum_{j\in[1,d]}\frac{1}{|\mathcal{D}_{j}|}\sum_{v\in\mathcal{D}_{j}}(f(v_{i})-\hat{f}(v_{i}))^{2}\textrm{.}$

Methods evaluated. We consider for evaluation the following solutions (cf.
Fig. 1) and protocols:

  * •

Solution Spl, which splits the privacy budget per attribute $\epsilon/d$ with
a best-effort approach using the adaptive mechanism presented in Subsection
2.2.3, i.e., Spl[ADP].

  * •

Solution Smp, which randomly samples a single attribute and use all the
privacy budget $\epsilon$ also with the adaptive mechanism, i.e., Smp[ADP].

  * •

Our solution RS+FD, which randomly samples a single attribute and uses an
amplified privacy budget $\epsilon^{\prime}\geq\epsilon$ while generating fake
data for each $d-1$ non-sampled attribute:

    * –

RS+FD[GRR] (Alg. 1 with GRR as local randomizer $\mathcal{A}$);

    * –

RS+FD[OUE-z] (Alg. 2);

    * –

RS+FD[OUE-r] (Alg. 3);

    * –

RS+FD[ADP] presented in Subsection 3.4 (i.e., adaptive choice between
RS+FD[GRR] and RS+FD[OUE-z]).

###  4.2. Results on synthetic data

Our first set of experiments were conducted on six synthetic datasets. Fig. 8
(first two synthetic datsets), Fig. 8 (third and fourth synthetic datsets),
and Fig. 8 (last two synthetic datasets) illustrate for all methods, the
averaged $MSE_{avg}$ (y-axis) according to the privacy parameter $\epsilon$
(x-axis).

Impact of the number of users. In both Fig. 8 and Fig. 8, one can notice that
the $MSE_{avg}$ is inversely proportional to the number of users $n$. With the
datasets we experimented, the $MSE_{avg}$ decreases one order of magnitude by
increasing $n$ in one order of magnitude too. In comparison with Smp, the
noise in our RS+FD solution comes mainly from fake data as it uses an
amplified $\epsilon^{\prime}\geq\epsilon$. This suggests that, in some cases,
with appropriately high number of user $n$, our solutions may always provide
higher data utility than the state-of-the-art Smp solution (e.g., cf. Fig. 8).

Impact of the number of attributes. One can notice the effect on increasing
$d$ comparing the results of Fig. 8 ($d=5$) and Fig. 8 ($d=10$) while fixing
$n$ and k (uniform number of values). For instance, even though there are
twice the number of attributes, the accuracy (measured with the averaged MSE
metric) does not suffer much. This is because the amplification by sampling
($\frac{e^{\epsilon^{\prime}}-1}{e^{\epsilon}-1}=\frac{1}{\beta}$ (Li et al.,
2012)) depends on the sampling rate $\beta=\frac{1}{d}$, which means that the
more attributes one collects, the more the $\epsilon^{\prime}$ is amplified,
i.e., $\epsilon^{\prime}=\ln{\left(d\cdot(e^{\epsilon}-1)+1\right)}$; thus
balancing data utility.

Besides, in Fig. 8, one can notice a similar pattern, i.e., increasing the
number of attributes from $d=10$ (left-side plot) to $d=20$ (right-hand plot),
with varied domain size k, resulted in only a slightly loss of performance.
This, however, is not true for the Spl solution, for example, in which the
$MSE_{avg}$ increased much more in order of magnitude than our RS+FD solution.

Comparison with existing solutions. From our experiments, one can notice that
the Spl solution always resulted in more estimation error than our RS+FD
solution and than the Smp solution, which is in accordance with other works
(Wang et al., 2019; Nguyên et al., 2016; Wang et al., 2017; Arcolezi et al.,
2021; Wang et al., 2021b). Besides, our RS+FD[GRR], RS+FD[OUE-z], and
RS+FD[ADP] protocols achieve better or nearly the same performance than the
Smp solution with a best-effort adaptive mechanism Smp[ADP], which uses GRR
for small domain sizes $k$ and OUE for large ones. Although this is not true
with RS+FD[OUE-r], it still provides more accurate results than Spl[ADP] while
”hiding” the sampled attribute from the aggregator.

Globally, on high privacy regimes (i.e., low values of $\epsilon$), our RS+FD
solution consistently outperforms the other two solutions Spl and Smp. By
increasing $\epsilon$, Smp[ADP] starts to outperform RS+FD[OUE-r] while
achieving similar performance than our RS+FD[GRR], RS+FD[OUE-z], and
RS+FD[ADP] solutions. In addition, one can notice in Fig. 8, for example, the
advantage of RS+FD[ADP] over our protocols RS+FD[GRR] and RS+FD[OUE-z] applied
individually, as it adaptively selects the protocol with the smallest
approximate variance value.

Figure 6. Averaged MSE varying $\epsilon$ on the synthetic datasets with
$d=5$, uniform domain size $\textbf{k}=[10,10,...,10]$, and $n=50000$ (left-
side plot) and $n=500000$ (right-side plot).

Figure 7. Averaged MSE varying $\epsilon$ on the synthetic datasets with
$d=10$, uniform domain size $\textbf{k}=[10,10,...,10]$, and $n=50000$ (left-
side plot) and $n=500000$ (right-side plot).

Figure 8. Averaged MSE varying $\epsilon$ on the synthetic datasets with
$n=500000$: the first with $d=10$ and domain size
$\textbf{k}=[10,20,...,90,100]$ (left-side plot), and the other with $d=20$
and domain size $\textbf{k}=[10,10,20,...,100,100]$ (right-side plot).

###  4.3. Results on real world data

Our second set of experiments were conducted on four real-world datasets with
varied parameters for $n$, $d$, and k. Fig. 12 (Nursery), Fig. 12 (Adult),
Fig. 12 (MS-FIMU), and Fig. 12 (Census-Income) illustrate for all methods,
averaged $MSE_{avg}$ (y-axis) according to the privacy parameter $\epsilon$
(x-axis).

The results with real-world datasets follow similar behavior than with
synthetic ones. For all tested datasets, one can observe that the $MSE_{avg}$
of our proposed protocols with RS+FD is still smaller than the Spl solution
with a best-effort adaptive mechanism Spl[ADP]. As also highlighted in the
literature (Wang et al., 2019; Nguyên et al., 2016; Wang et al., 2017;
Arcolezi et al., 2021; Wang et al., 2021b), privacy budget splitting is sub-
optimal, which leads to higher estimation error.

On the other hand, for both Adult and MS-FIMU datasets, our solutions
RS+FD[GRR], RS+FD[OUE-z], and RS+FD[ADP] achieve nearly the same performance
(sometimes better on high privacy regimes, i.e., low $\epsilon$) than the Smp
solution with the best-effort adaptive mechanism Smp[ADP]. For the Nursery
dataset, with small number of users $n$, only RS+FD[OUE-z] and RS+FD[ADP] are
competitive with Smp[ADP]. Lastly, for the Census dataset, with a large number
of attributes $d=33$, increasing the privacy parameter $\epsilon$ resulted in
a small gain on data utility for our solutions RS+FD[GRR] and RS+FD[OUE-r]. On
the other hand, both of our solutions RS+FD[OUE-z] and RS+FD[ADP] achieve
nearly the same or better performance than Smp[ADP].

Moreover, one can notice that using the approximate variance in (12) led
RS+FD[ADP] to achieve similar or improved performance over our RS+FD[GRR] and
RS+FD[OUE-z] protocols applied individually. For instance, for the Adult
dataset, with RS+FD[ADP] it was possible to outperform Smp[ADP] 3x more than
with RS+FD[GRR] or RS+FD[OUE-z] (similarly, 1x more for the MS-FIMU dataset).
Besides, for the Census-Income dataset, RS+FD[ADP] improves the performance of
the other protocols applied individually on high privacy regimes while
accompanying the RS+FD[OUE-z] curve on the lower privacy regime cases.

In general, these results help us answering the problematic of this paper (cf.
Subsection 1.3) that for the same privacy parameter $\epsilon$, one can
achieve nearly the same or better data utility with our RS+FD solution than
when using the state-of-the-art Smp solution. Besides, RS+FD enhances users’
privacy by ”hiding” the sampled attribute and its $\epsilon$-LDP value among
fake data. On the other hand, there is a price to pay on computation, in the
generation of fake data, and on communication cost, which is similar to the
Spl solution, i.e., send a value per attribute.

Figure 9. Averaged MSE varying $\epsilon$ on the Nursery dataset with
$n=12960$, $d=9$, and domain size $\textbf{k}=[3,5,4,4,3,2,3,3,5]$.

Figure 10. Averaged MSE varying $\epsilon$ on the Adult dataset with
$n=45222$, $d=9$, and domain size $\textbf{k}=[7,16,7,14,6,5,2,41,2]$.

Figure 11. Averaged MSE varying $\epsilon$ on the MS-FIMU dataset with
$n=88935$, $d=6$, and domain size $\textbf{k}=[3,3,8,12,37,11]$.

Figure 12. Averaged MSE varying $\epsilon$ on the Census-Income dataset with
$n=299285$, $d=33$, and domain size
$\textbf{k}=[9,52,47,17,3,...,43,43,43,5,3,3,3,2]$.

##  5\. Literature Review and Discussion

In recent times, there have been several works on the local DP setting in both
academia (Wang et al., 2019; Nguyên et al., 2016; Kasiviswanathan et al.,
2008; Wang et al., 2017; Alvim et al., 2018; Acharya et al., 2019; Bassily and
Smith, 2015; Xiong et al., 2020; Kairouz et al., 2016; Wang et al., 2021b) and
practical deployment (Erlingsson et al., 2014; Ding et al., 2017; Team, 2017;
Kessler et al., 2019). Among many other complex tasks (e.g., heavy hitter
estimation (Bassily and Smith, 2015; Wang et al., 2021a; Bassily et al.,
2017), marginal estimation (Peng et al., 2019; Zhang et al., 2018; Ren et al.,
2018; Fanti et al., 2016), frequent itemset mining (Wang et al., 2018; Qin et
al., 2016)), frequency estimation is a fundamental primitive in LDP and has
received considerable attention for a single attribute (Acharya et al., 2019;
Wang et al., 2021b, 2017; Kairouz et al., 2016; Alvim et al., 2018; Erlingsson
et al., 2014; Ding et al., 2017; Xiong et al., 2020; Kim et al., 2018;
Arcolezi et al., 2020b; Zhao et al., 2019; Li et al., 2020). However,
concerning multiple attributes, as also noticed in the survey work on LDP in
(Xiong et al., 2020), most studies for collecting multidimensional data with
LDP mainly focused on numerical data (Nguyên et al., 2016; Duchi et al., 2018;
Wang et al., 2019; Wang et al., 2021b). For instance, in (Nguyên et al., 2016;
Wang et al., 2019), the authors propose sampling-based LDP mechanisms for
real-valued data (named Harmony and Piecewise Mechanism) and applied these
protocols in a multidimensional setting using state-of-the-art LDP mechanisms
from (Bassily and Smith, 2015; Wang et al., 2017) for categorical data. On the
other hand, regarding categorical attributes, in (Wang et al., 2017), the
authors prove for OUE (as well as to optimal local hashing - OLH) that sending
$1$ attribute with the whole privacy budget $\epsilon$ results in less
variance than splitting the privacy budget $\epsilon/d$ for all attributes.
The authors in (Arcolezi et al., 2021) prove and validate experimentally that
reporting a single attribute with $\epsilon$-LDP resulted in less estimation
error than splitting the privacy budget when using GRR.

However, in the aforementioned works (Nguyên et al., 2016; Wang et al., 2019;
Wang et al., 2017; Arcolezi et al., 2021; Wang et al., 2021b), the sampling
result is known by the aggregator. That is, each user samples a single
attribute $j$, applies a local randomizer to $v_{j}$, and sends to the
aggregator the tuple $y=\langle j,LDP(v_{j})\rangle$ (i.e., Smp). While one
can achieve higher data utility (cf. Figs. 8\- 12) with Smp than splitting the
privacy budget among $d$ attributes (Spl), we argue that Smp might be ”unfair”
with some users. More precisely, users whose sampled attribute is socially
”more” sensitive (e.g., disease or location), might hesitate to share their
data as the probability bound $e^{\epsilon}$ is ”less” restrictive than
$e^{\epsilon/d}$. For instance, assume that GRR is used with k=2 (HIV positive
or negative) and the privacy budget is $\epsilon=ln(7)\sim 2$, the user will
report the true value with probability as high as $p\sim 87\%$ (even with
$\epsilon=1$, this probability is still high $p\sim 73\%$). On the other hand,
if there are $d=10$ attributes (e.g., nine demographic and HIV test), with
Spl, the probability bound is now $e^{\epsilon/10}$ and $p\sim 55\%$.

Motivated by this privacy-utility trade-off between the solutions Spl and Smp,
we proposed a solution named random sampling plus fake data (RS+FD), which
generates uncertainty over the sampled attribute in the view of the
aggregator. In this context, since the sampling step randomly selects an
attribute with sampling probability $\beta=\frac{1}{d}$, there is an
amplification effect in terms of privacy, a.k.a. amplification by sampling
(Chaudhuri and Mishra, 2006; Li et al., 2012; Balle et al., 2018, 2020;
Kasiviswanathan et al., 2008). A similar privacy amplification for sampling a
random item of a single attribute has been noticed in (Wang et al., 2018) for
frequent itemset mining in the LDP model too. Indeed, amplification is an
active research field on DP literature, which aims at finding ways to measure
the privacy introduced by non-compositional sources of randomness, e.g.,
sampling (Chaudhuri and Mishra, 2006; Li et al., 2012; Balle et al., 2018,
2020; Kasiviswanathan et al., 2008), iteration (Feldman et al., 2018), and
shuffling (Balle et al., 2019; Erlingsson et al., 2019, 2020; Wang et al.,
2020a).

##  6\. Conclusion and Perspectives

This paper investigates the problem of collecting multidimensional data under
$\epsilon$-LDP for the fundamental task of frequency estimation. As shown in
the results, our proposed RS+FD solution achieves nearly the same or better
performance than the state-of-the-art Smp solution. In addition, RS+FD
generates uncertainty over the sampled attribute in the view of the
aggregator, which enhances users’ privacy. For future work, we suggest and
intend to investigate if given a reported tuple y one can state which
attribute value is ”fake” or not by seeing the estimated frequencies. Indeed,
we intend to investigate this phenomenon in both single-time collection and
longitudinal studies (i.e., throughout time) by extending RS+FD with two
rounds of privatization, i.e., using memoization (Erlingsson et al., 2014;
Ding et al., 2017).

###### Acknowledgements.

This work was supported by the Region of Bourgogne Franche-Comté CADRAN
Project and by the EIPHI-BFC Graduate School (contract “ANR-17-EURE-0002”).
All computations have been performed on the ”Mésocentre de Calcul de Franche-
Comté”.

## References

  * (1)
  * Abadi et al. (2016) Martin Abadi, Andy Chu, Ian Goodfellow, H. Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. 2016.  Deep Learning with Differential Privacy _(CCS ’16)_. Association for Computing Machinery, New York, NY, USA, 308–318.  https://doi.org/10.1145/2976749.2978318
  * Abowd (2018) John M. Abowd. 2018\.  The U.S. Census Bureau Adopts Differential Privacy. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. ACM.  https://doi.org/10.1145/3219819.3226070
  * Acharya et al. (2019) Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. 2019.  Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication. In _Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics_ _(Proceedings of Machine Learning Research, Vol. 89)_ , Kamalika Chaudhuri and Masashi Sugiyama (Eds.). PMLR, 1120–1129.
  * Aktay et al. (2020) Ahmet Aktay et al. 2020\.  Google COVID-19 community mobility reports: Anonymization process description (version 1.0).  _arXiv preprint arXiv:2004.04145_ (2020).
  * Alvim et al. (2018) Mario Alvim, Konstantinos Chatzikokolakis, Catuscia Palamidessi, and Anna Pazii. 2018.  Invited Paper: Local Differential Privacy on Metric Spaces: Optimizing the Trade-Off with Utility. In _2018 IEEE 31st Computer Security Foundations Symposium (CSF)_. IEEE.  https://doi.org/10.1109/csf.2018.00026
  * Arcolezi et al. (2020a) Héber H. Arcolezi, Jean-François Couchot, Oumaya Baala, Jean-Michel Contet, Bechara Al Bouna, and Xiaokui Xiao. 2020a.  Mobility modeling through mobile data: generating an optimized and open dataset respecting privacy. In _2020 International Wireless Communications and Mobile Computing (IWCMC)_. IEEE.  https://doi.org/10.1109/iwcmc48107.2020.9148138
  * Arcolezi et al. (2021) Héber H. Arcolezi, Jean-François Couchot, Bechara Al Bouna, and Xiaokui Xiao. 2021\.  Longitudinal Collection and Analysis of Mobile Phone Data with Local Differential Privacy.  In _IFIP Advances in Information and Communication Technology_. Springer International Publishing, 40–57.  https://doi.org/10.1007/978-3-030-72465-8_3
  * Arcolezi et al. (2020b) Héber H. Arcolezi, Jean-François Couchot, Selene Cerna, Christophe Guyeux, Guillaume Royer, Béchara Al Bouna, and Xiaokui Xiao. 2020b.  Forecasting the number of firefighter interventions per region with local-differential-privacy-based data.  _Computers & Security_ 96 (Sept. 2020), 101888\.  https://doi.org/10.1016/j.cose.2020.101888
  * Balle et al. (2018) Borja Balle, Gilles Barthe, and Marco Gaboardi. 2018\.  Privacy amplification by subsampling: tight analyses via couplings and divergences. In _Proceedings of the 32nd International Conference on Neural Information Processing Systems_. 6280–6290.
  * Balle et al. (2020) Borja Balle, Gilles Barthe, and Marco Gaboardi. 2020\.  Privacy profiles and amplification by subsampling.  _Journal of Privacy and Confidentiality_ 10, 1 (2020).
  * Balle et al. (2019) Borja Balle, James Bell, Adrià Gascón, and Kobbi Nissim. 2019.  The Privacy Blanket of the Shuffle Model.  In _Advances in Cryptology – CRYPTO 2019_. Springer International Publishing, 638–667.  https://doi.org/10.1007/978-3-030-26951-7_22
  * Bassily et al. (2017) Raef Bassily, Kobbi Nissim, Uri Stemmer, and Abhradeep Thakurta. 2017.  Practical locally private heavy hitters.  _arXiv preprint arXiv:1707.04982_ (2017).
  * Bassily and Smith (2015) Raef Bassily and Adam Smith. 2015.  Local, Private, Efficient Protocols for Succinct Histograms. In _Proceedings of the forty-seventh annual ACM symposium on Theory of Computing_. ACM.  https://doi.org/10.1145/2746539.2746632
  * Chaudhuri and Mishra (2006) Kamalika Chaudhuri and Nina Mishra. 2006.  When Random Sampling Preserves Privacy.  In _Lecture Notes in Computer Science_. Springer Berlin Heidelberg, 198–213.  https://doi.org/10.1007/11818175_12
  * Ding et al. (2017) Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017\.  Collecting Telemetry Data Privately.  In _Advances in Neural Information Processing Systems 30_ , I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.). Curran Associates, Inc., 3571–3580.
  * Dua and Graff (2017) Dheeru Dua and Casey Graff. 2017.  UCI Machine Learning Repository.  http://archive.ics.uci.edu/ml
  * Duchi et al. (2018) John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. 2018\.  Minimax Optimal Procedures for Locally Private Estimation.  _J. Amer. Statist. Assoc._ 113, 521 (Jan. 2018), 182–201.  https://doi.org/10.1080/01621459.2017.1389735
  * Dwork (2006) Cynthia Dwork. 2006\.  Differential Privacy.  In _Automata, Languages and Programming_. Springer Berlin Heidelberg, 1–12.  https://doi.org/10.1007/11787006_1
  * Dwork et al. (2006) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006.  Calibrating Noise to Sensitivity in Private Data Analysis.  In _Theory of Cryptography_. Springer Berlin Heidelberg, 265–284.  https://doi.org/10.1007/11681878_14
  * Dwork et al. (2014) Cynthia Dwork, Aaron Roth, et al. 2014\.  The algorithmic foundations of differential privacy.  _Foundations and Trends® in Theoretical Computer Science_ 9, 3–4 (2014), 211–407.
  * Erlingsson et al. (2020) Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Shuang Song, Kunal Talwar, and Abhradeep Thakurta. 2020\.  Encode, shuffle, analyze privacy revisited: Formalizations and empirical evaluation.  _arXiv preprint arXiv:2001.03618_ (2020).
  * Erlingsson et al. (2019) Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. 2019.  Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity.  In _Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms_. Society for Industrial and Applied Mathematics, 2468–2479.  https://doi.org/10.1137/1.9781611975482.151
  * Erlingsson et al. (2014) Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. 2014\.  RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. In _Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security_ (Scottsdale, Arizona, USA). ACM, New York, NY, USA, 1054–1067.  https://doi.org/10.1145/2660267.2660348
  * Fanti et al. (2016) Giulia Fanti, Vasyl Pihur, and Úlfar Erlingsson. 2016\.  Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionaries.  _Proceedings on Privacy Enhancing Technologies_ 2016, 3 (May 2016), 41–61.  https://doi.org/10.1515/popets-2016-0015
  * Feldman et al. (2018) Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. 2018.  Privacy Amplification by Iteration. In _2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)_. 521–532.  https://doi.org/10.1109/FOCS.2018.00056
  * Garfinkel (2021) Simson Garfinkel. 2021\.  Implementing Differential Privacy for the 2020 Census. USENIX Association.
  * Kairouz et al. (2016) Peter Kairouz, Keith Bonawitz, and Daniel Ramage. 2016\.  Discrete distribution estimation under local privacy. In _International Conference on Machine Learning_. PMLR, 2436–2444.
  * Kasiviswanathan et al. (2008) Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. 2008\.  What Can We Learn Privately?. In _2008 49th Annual IEEE Symposium on Foundations of Computer Science_. IEEE.  https://doi.org/10.1109/focs.2008.27
  * Kessler et al. (2019) Stephan Kessler, Jens Hoff, and Johann-Christoph Freytag. 2019\.  SAP HANA goes private.  _Proceedings of the VLDB Endowment_ 12, 12 (Aug. 2019), 1998–2009.  https://doi.org/10.14778/3352063.3352119
  * Kim et al. (2018) Jong Wook Kim, Dae-Ho Kim, and Beakcheol Jang. 2018\.  Application of Local Differential Privacy to Collection of Indoor Positioning Data.  _IEEE Access_ 6 (2018), 4276–4286.  https://doi.org/10.1109/access.2018.2791588
  * Li et al. (2012) Ninghui Li, Wahbeh Qardaji, and Dong Su. 2012.  On sampling, anonymization, and differential privacy or, k-anonymization meets differential privacy. In _Proceedings of the 7th ACM Symposium on Information, Computer and Communications Security - ASIACCS '12_. ACM Press.  https://doi.org/10.1145/2414456.2414474
  * Li et al. (2020) Zitao Li, Tianhao Wang, Milan Lopuhaä-Zwakenberg, Ninghui Li, and Boris Škoric. 2020.  Estimating Numerical Distributions under Local Differential Privacy. In _Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data_. ACM.  https://doi.org/10.1145/3318464.3389700
  * McCandless et al. (2021) David McCandless, Tom Evans, Miriam Quick, Ella Hollowood, Christian Miles, Dan Hampson, and Duncan Geere. 2021.  World’s Biggest Data Breaches & Hacks.  https://www.informationisbeautiful.net/visualizations/worlds-biggest-data-breaches-hacks/.  Online; accessed 11 March 2021.
  * Nguyên et al. (2016) Thông T. Nguyên, Xiaokui Xiao, Yin Yang, Siu Cheung Hui, Hyejin Shin, and Junbum Shin. 2016\.  Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy.  _ArXiv_ abs/1606.05053 (2016).
  * Peng et al. (2019) Fan Peng, Shaohua Tang, Bowen Zhao, and Yuxian Liu. 2019\.  A privacy-preserving data aggregation of mobile crowdsensing based on local differential privacy. In _Proceedings of the ACM Turing Celebration Conference - China_. ACM.  https://doi.org/10.1145/3321408.3321602
  * Qin et al. (2016) Zhan Qin, Yin Yang, Ting Yu, Issa Khalil, Xiaokui Xiao, and Kui Ren. 2016\.  Heavy Hitter Estimation over Set-Valued Data with Local Differential Privacy. In _Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security_. ACM.  https://doi.org/10.1145/2976749.2978409
  * Ren et al. (2018) Xuebin Ren, Chia-mu Yu, Weiren Yu, Shusen Yang, Senior Member, Xinyu Yang, Julie A Mccann, Philip S Yu, and Life Fellow. 2018.  LoPub : High-Dimensional Crowdsourced Data.  13, 9 (2018), 2151–2166.  https://doi.org/10.1109/TIFS.2018.2812146
  * Rogers et al. (2020) Ryan Rogers, Subbu Subramaniam, Sean Peng, David Durfee, Seunghyun Lee, Santosh Kumar Kancha, Shraddha Sahay, and Parvez Ahammad. 2020\.  LinkedIn’s Audience Engagements API: A privacy preserving data analytics system at scale.  _arXiv preprint arXiv:2002.05839_ (2020).
  * Team (2017) Apple Differential Privacy Team. 2017\.  Learning with privacy at scale.  https://docs-assets.developer.apple.com/ml-research/papers/learning-with-privacy-at-scale.pdf.  Online; accessed 11 March 2021.
  * Wang et al. (2019) Ning Wang, Xiaokui Xiao, Yin Yang, Jun Zhao, Siu Cheung Hui, Hyejin Shin, Junbum Shin, and Ge Yu. 2019\.  Collecting and Analyzing Multidimensional Data with Local Differential Privacy. In _2019 IEEE 35th International Conference on Data Engineering (ICDE)_. IEEE.  https://doi.org/10.1109/icde.2019.00063
  * Wang et al. (2017) Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. 2017\.  Locally Differentially Private Protocols for Frequency Estimation. In _26th USENIX Security Symposium (USENIX Security 17)_. USENIX Association, Vancouver, BC, 729–745.
  * Wang et al. (2020a) Tianhao Wang, Bolin Ding, Min Xu, Zhicong Huang, Cheng Hong, Jingren Zhou, Ninghui Li, and Somesh Jha. 2020a.  Improving utility and security of the shuffler-based differential privacy.  _Proceedings of the VLDB Endowment_ 13, 13 (Sept. 2020), 3545–3558.  https://doi.org/10.14778/3424573.3424576
  * Wang et al. (2018) Tianhao Wang, Ninghui Li, and Somesh Jha. 2018.  Locally Differentially Private Frequent Itemset Mining. In _2018 IEEE Symposium on Security and Privacy (SP)_. IEEE.  https://doi.org/10.1109/sp.2018.00035
  * Wang et al. (2021a) Tianhao Wang, Ninghui Li, and Somesh Jha. 2021a.  Locally Differentially Private Heavy Hitter Identification.  _IEEE Transactions on Dependable and Secure Computing_ 18, 2 (March 2021), 982–993.  https://doi.org/10.1109/tdsc.2019.2927695
  * Wang et al. (2020b) Tianhao Wang, Milan Lopuhaa-Zwakenberg, Zitao Li, Boris Skoric, and Ninghui Li. 2020b.  Locally Differentially Private Frequency Estimation with Consistency. In _Proceedings 2020 Network and Distributed System Security Symposium_. Internet Society.  https://doi.org/10.14722/ndss.2020.24157
  * Wang et al. (2021b) Teng Wang, Jun Zhao, Zhi Hu, Xinyu Yang, Xuebin Ren, and Kwok-Yan Lam. 2021b.  Local Differential Privacy for data collection and analysis.  _Neurocomputing_ 426 (Feb. 2021), 114–133.  https://doi.org/10.1016/j.neucom.2020.09.073
  * Warner (1965) Stanley L. Warner. 1965\.  Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias.  _J. Amer. Statist. Assoc._ 60, 309 (March 1965), 63–69.  https://doi.org/10.1080/01621459.1965.10480775
  * Xiong et al. (2020) Xingxing Xiong, Shubo Liu, Dan Li, Zhaohui Cai, and Xiaoguang Niu. 2020.  A Comprehensive Survey on Local Differential Privacy.  _Security and Communication Networks_ 2020 (Oct. 2020), 1–29.  https://doi.org/10.1155/2020/8829523
  * Zhang et al. (2018) Zhikun Zhang, Tianhao Wang, Ninghui Li, Shibo He, and Jiming Chen. 2018.  CALM: Consistent adaptive local marginal for marginal release under local differential privacy.  _Proceedings of the ACM Conference on Computer and Communications Security_ (2018), 212–229.  https://doi.org/10.1145/3243734.3243742
  * Zhao et al. (2019) Dan Zhao, Hong Chen, Suyun Zhao, Xiaoying Zhang, Cuiping Li, and Ruixuan Liu. 2019\.  Local Differential Privacy with K-anonymous for Frequency Estimation. In _2019 IEEE International Conference on Big Data (Big Data)_. IEEE.  https://doi.org/10.1109/bigdata47090.2019.9006022