11institutetext: National University of Kyiv-Mohyla Academy
11email: {mykhailo.poliakov<EMAIL_ADDRESS>
# Multi-Meta-RAG: Improving RAG for Multi-Hop Queries using Database Filtering
with LLM-Extracted Metadata

Mykhailo Poliakov  0009-0006-5263-762X Nadiya Shvai  0000-0001-8194-6196

###### Abstract

The retrieval-augmented generation (RAG) enables retrieval of relevant
information from an external knowledge source and allows large language models
(LLMs) to answer queries over previously unseen document collections. However,
it was demonstrated that traditional RAG applications perform poorly in
answering multi-hop questions, which require retrieving and reasoning over
multiple elements of supporting evidence. We introduce a new method called
Multi-Meta-RAG, which uses database filtering with LLM-extracted metadata to
improve the RAG selection of the relevant documents from various sources,
relevant to the question. While database filtering is specific to a set of
questions from a particular domain and format, we found out that Multi-Meta-
RAG greatly improves the results on the MultiHop-RAG benchmark. The code is
available on GitHub.

###### Keywords:

large language models retrieval augmented generation multi hop question
answering

##  1 Introduction

Large Language Models (LLMs) have shown remarkable language understanding and
generation abilities [8, 11]. However, there are two main challenges: static
knowledge [6] and generative hallucination [3]. Retrieval-augmented generation
[4] is an established process for answering user questions over entire
datasets. RAG also helps mitigate generative hallucination and provides LLM
with a source of new information on which it was not trained [9]. Real-world
RAG pipelines often need to retrieve evidence from multiple documents
simultaneously, a procedure known as multi-hop querying. Nevertheless,
existing RAG applications face challenges in answering multi-hop queries,
requiring retrieval and reasoning over numerous pieces of evidence [10]. In
this paper, we present Multi-Meta-RAG: an improved RAG using a database
filtering approach with LLM-extracted metadata that significantly improves the
results on the MultiHop-RAG benchmark.

##  2 Related works

MultiHop-RAG [10] is a novel benchmarking dataset focused on multi-hop
queries, including a knowledge base, questions, ground-truth responses, and
supporting evidence. The news articles were selected from September 26, 2023,
to December 26, 2023, extending beyond the knowledge cutoff of
ChatGPT111gpt-3.5-turbo-0613 and GPT-4222gpt4-0613. A trained language model
extracted factual or opinion sentences from each news article. These factual
sentences act as evidence for multi-hop queries. The selection method involves
keeping articles with evidence that overlaps keywords with other articles,
enabling the creation of multi-hop queries with answers drawn from numerous
sources. Given the original evidence and its context, GPT-4 was used to
rephrase the evidence, referred to as claims. Afterward, the bridge entity or
topic is used to generate multi-hop queries.

For example, "Did Engadget report a discount on the 13.6-inch MacBook Air
before The Verge reported a discount on Samsung Galaxy Buds 2?" is a typical
query from the MultiHop-RAG dataset. Answering it requires evidence from
Engadget and The Verge to formulate an answer. Also, it requires LLM to figure
out the temporal ordering of events. MultiHop-RAG also has inference,
comparison, and null (without correct answer) queries, in addition to the
temporal query above.

Figure 1: A naive RAG implementation for MultiHop-RAG queries. RAG selects
chunks from articles not asked in the example query, which leads to LLM giving
a wrong response.

In a typical RAG application, we use an external corpus that comprises
multiple documents and serves as the knowledge base. Each document within this
corpus is segmented into chunks. These chunks are then converted into vector
representations using an embedding model and stored in a vector database.
Given a user query, RAG typically retrieves the top-K chunks that best match
the query. The retrieved chunks, combined with the query are submitted into an
LLM to generate a final response.

For the MultiHop-RAG benchmark, scraped articles act as a knowledge base for
the RAG application tested. The problem is that a naive RAG application fails
to recognize that the query asks for information from specific sources. Top-K
chunks such as RAG retrieves often contain information from sources other than
those mentioned in the query. Retrieved chunks might even miss relevant
sources, leading to a wrong response, as depicted in Figure 1.

##  3 Multi-Meta-RAG

Figure 2: Multi-Meta-RAG: an improved RAG with database filtering using
metadata. Metadata is extracted via secondary LLM. With filtering, we can
ensure top-K chunks are always from relevant sources with better chances of
getting correct overall responses.

###  3.1 Extraction of Relevant Query Metadata with the LLM

Table 1: Examples of extracted metadata filters using a few-shot prompt with
corresponding queries. Correct usage of the $nin operator for the last query
can be noted.

Query |  |  Extracted Filter
---|---|---
Does the TechCrunch article report on new hiring at Starz, while the Engadget article discusses layoffs within the entire video game industry? |  |  ⬇ "source": { "$in": ["TechCrunch", "Engadget"] }
Did The Guardian’s report on December 12, 2023, contradict the Sporting News report regarding the performance and future outlook of Manchester United? |  |  ⬇ "published_at": { "$in": ["December 12, 2023"] }, "source": { "$in": ["The Guardian", "Sporting News"] }
Who is the individual facing a criminal trial on seven counts of fraud and conspiracy, previously likened to a financial icon but not by TechCrunch, and is accused by the prosecution of committing fraud for wealth, power, and influence? |  |  ⬇ "source": { "$nin": [ "TechCrunch" ] }

Each question in the MultiHop-RAG [10] benchmark follows a typical structure.
Every query requests information from one or more sources of news. In
addition, some temporal queries require news articles from a particular date.
We can extract the query filter via helper LLM by constructing a few-shot
prompt [1] with examples of extracted article sources and publishing dates as
a filter. The prompt template is provided in Appendix A. We only run metadata
extraction with ChatGPT333gpt-3.5-turbo-1106 because this additional RAG
pipeline step must be quick and cheap. We found out that this step takes 0.7
seconds on average for one query.

Two query metadata filter fields are extracted: article source and publication
date. The complete filter is a dictionary with two fields combined. Samples of
extracted metadata filters can be found in Table 3.1. The primary filtering
operator is `$in`, the only operator provided in the examples in a few-shot
prompt template. The LLM also correctly chooses a tiny fraction of the `$nin`
operator for some queries without an example. While LLM only used `$in` and
`$nin` for article sources, the model sometimes chooses other operators like
`$lt` or `$gt` for publication date for a fraction of temporal queries.
Because the number of such queries is small, we decided to only use date
filters with `$in` and `$nin` operators and a most frequent date
format444strftime format code %B %-d, %Y for easier matching in the database.
All queries have a source filter extracted, while the publishing date filter
was extracted in 15.57% of queries, while 22.81% of queries of the MultiHop-
RAG dataset are temporal.

###  3.2 Improved Chunk Selection using Metadata Filtering

The extracted metadata could be used to enhance an RAG application (Figure 2).
We split the articles in the MultiHop-RAG [10] knowledge base into chunks,
each containing 256 tokens using LLamaIndex [5] using a sentence splitter as
in the original MultiHop-RAG implementation. We also picked a chunk overlap of
32, finding out that smaller chunk overlap leads to a better variety of unique
chunks in the top-K selection than the original implementation, which used the
LLamaIndex default of 200. We selected LangChain [2] Neo4j [7] vector store as
a vector database as its index implementation recently555April 2024 started to
support metadata filtering. We then convert the chunks using an embedding
model and save the embeddings into a vector database with article metadata
saved as node properties.

Likewise, in the retrieval stage, we transform a query using the same
embedding model and retrieve the top-K most relevant chunks with the highest
cosine similarity with the query embedding. We also filter the chunks with
LLM-extracted metadata in the same stage. Similarly to MultiHop-RAG, we use a
Reranker module (bge-reranker-large [13]) to examine the retrieval
performance. After retrieving 20 corresponding chunks using the embedding
model and metadata filter, we select the top-K chunks using the Reranker.

##  4 Results

###  4.1 Chunk Retrieval Experiment

We selected two best-performing embedding models from original MultiHop-RAG
experiment for testing metadata filtering chunk retrieval performance, bge-
large-en-v1.5 [13] and voyage-02 [12]. The retrieved list of chunks is
compared with the ground truth evidence associated with each query, excluding
the null queries, as they lack corresponding evidence. For evaluation, we
assume the Top-K chunks are retrieved and use metrics such as Mean Average
Precision at K (MAP@K), Mean Reciprocal Rank at K (MRR@K), and Hit Rate at K
(Hit@K). MAP@K measures the average precision of the top-K retrieval across
all queries. MRR@K calculates the average of the reciprocal ranks of the first
relevant chunk within the top-K retrieved set for each query. Hit@K measures
the proportion of evidence that appears in the top-K retrieved set. The
experiment (Table 2) with RAG showed considerable improvement in both
embeddings for all core metrics MRR@10, MAP@10, Hits@10, and Hits@4. Most
notably, for voyage-02 Hits@4 enhanced by 18%. This is important for practical
RAG systems, where the top-K retrieved should as as low as possible to account
for context window limits and cost.

Table 2: Chunk retrieval experiment results. Top-10 chunks are selected with
bge-reranker-large after Top-20 chunks are found via the similarity search and
database metadata filtering. A chunk size of 256 and a chunk overlap of 32 is
used.

Embedding | Baseline RAG [10]
---|---
MRR@10 |  MAP@10 |  Hits@10 |  Hits@4
bge-large-en-v1.5 (reported) |  0.563 |  0.4759 |  0.7183 |  0.6364
voyage-02 (reported) |  0.586 |  0.4795 |  0.7467 |  0.6625
voyage-02 (repository sample) |  0.6152 |  0.2718 a |  0.7315 |  0.6683

Embedding | Multi-Meta-RAG (ours)
---|---
MRR@10 |  MAP@10 |  Hits@10 |  Hits@4
bge-large-en-v1.5 |  0.6574 |  0.3293 |  0.8909 |  0.7672
voyage-02 |  0.6748 |  0.3388 |  0.9042 |  0.792

###### Note a

We found a difference between reported MAP@10 and evaluated MAP@10 on the
baseline voyage-02 retrieval sample file provided in the MultiHop-RAG
repository. We take the evaluated value of 0.2718 for comparisons between
RAGs.

###  4.2 LLM Response Generation Experiment

Table 3: Generation accuracy of LLMs with Metadata Filtering RAG (Top-6 chunks with voyage-02) LLM | Accuracy
---|---
Ground-truth [10] |  Baseline RAG [10] |  Multi-Meta-RAG (ours)
GPT4 (gpt-4-0613) |  0.89 |  0.56 |  0.63 b c
PaLM (text-bison@001) |  0.74 |  0.47 |  0.61 b

As with embeddings, we picked two best-achieving LLMs on ground-truth chunks
based on MultiHop-RAG initial experiments, GPT-4 and Google PaLM. We achieved
substantial improvement in accuracy (Table 3) for both models compared to
baseline RAG implementation. Google PaLM accuracy improved by 26% from 0.47 to
0.61. Preliminary GPT-4 results also show a 12% increase from 0.56 to 0.63.

###### Note b

The accuracy measuring script was not provided in the MultHop-RAG repository.
We were able to recreate our script, which shows similar results for ground-
truth chunks for both models and on experiments with the sample voyage-02
retrieval list provided in the repository. We accept the answer as correct
when the model answer appears in the gold answer or the gold answer appears in
the model answer. Both answers are transformed to lowercase, striped from
leading and trailing whitespace, and have their punctuation removed before
comparison. This script is used for benchmarking Multi-Meta-RAG.

###### Note c

GPT-4 accuracy is a preliminary result based on 50 queries (2% of all
queries). Results on the complete dataset are pending.

##  5 Conclusion

In this paper, we introduce Multi-Meta-RAG, a method of improving RAG for
multi-hop queries using database filtering with LLM-extracted metadata. Multi-
Meta-RAG considerably improves results in both chunk retrieval and LLM
generation experiments, while also being quite straightforward and
explainable. The proposed solution still has some limitations. Firstly,
extracting metadata requires a set of queries from a particular domain and
question format, as well as additional inference time. Secondly, it requires
the manual creation of a prompt template that will extract the metadata from
the query. Thirdly, while the improved results are encouraging, they still
fall considerably below the results achieved by feeding LLM precise ground-
truth facts. Future work may include testing more generic prompt templates for
metadata extraction on a variety of multi-hop datasets from different domains.

## References

  * [1] Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J.D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., Amodei, D.: Language models are few-shot learners. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., Lin, H. (eds.) Advances in Neural Information Processing Systems. vol. 33, pp. 1877–1901. Curran Associates, Inc. (2020)
  * [2] Chase, H.: LangChain (Oct 2022), https://github.com/langchain-ai/langchain
  * [3] Huang, L., Yu, W., Ma, W., Zhong, W., Feng, Z., Wang, H., Chen, Q., Peng, W., Feng, X., Qin, B., Liu, T.: A survey on hallucination in large language models: Principles, taxonomy, challenges, and open questions (2023)
  * [4] Lewis, P., Perez, E., Piktus, A., Petroni, F., Karpukhin, V., Goyal, N., Küttler, H., Lewis, M., Yih, W.t., Rocktäschel, T., Riedel, S., Kiela, D.: Retrieval-augmented generation for knowledge-intensive nlp tasks. In: Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., Lin, H. (eds.) Advances in Neural Information Processing Systems. vol. 33, pp. 9459–9474. Curran Associates, Inc. (2020)
  * [5] Liu, J.: LlamaIndex (Nov 2022). https://doi.org/10.5281/zenodo.1234, https://github.com/jerryjliu/llama{_}index
  * [6] Mialon, G., Dessì, R., Lomeli, M., Nalmpantis, C., Pasunuru, R., Raileanu, R., Rozière, B., Schick, T., Dwivedi-Yu, J., Celikyilmaz, A., Grave, E., LeCun, Y., Scialom, T.: Augmented language models: a survey (2023)
  * [7] Neo4j, Inc.: Neo4j graph database, https://neo4j.com/product/neo4j-graph-database
  * [8] Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P.F., Leike, J., Lowe, R.: Training language models to follow instructions with human feedback. In: Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., Oh, A. (eds.) Advances in Neural Information Processing Systems. vol. 35, pp. 27730–27744. Curran Associates, Inc. (2022)
  * [9] Shuster, K., Poff, S., Chen, M., Kiela, D., Weston, J.: Retrieval augmentation reduces hallucination in conversation. In: Moens, M., Huang, X., Specia, L., Yih, S.W. (eds.) Findings of the Association for Computational Linguistics: EMNLP 2021, Virtual Event / Punta Cana, Dominican Republic, 16-20 November, 2021. pp. 3784–3803. Association for Computational Linguistics (2021). https://doi.org/10.18653/V1/2021.FINDINGS-EMNLP.320, https://doi.org/10.18653/v1/2021.findings-emnlp.320
  * [10] Tang, Y., Yang, Y.: Multihop-rag: Benchmarking retrieval-augmented generation for multi-hop queries (2024)
  * [11] Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., Rodriguez, A., Joulin, A., Grave, E., Lample, G.: Llama: Open and efficient foundation language models (2023)
  * [12] Voyage AI: Voyage ai cutting-edge embedding and rerankers, https://www.voyageai.com
  * [13] Xiao, S., Liu, Z., Zhang, P., Muennighoff, N., Lian, D., Nie, J.Y.: C-pack: Packaged resources to advance general chinese embedding (2024)

##  Appendix A Metadata Extraction Prompt Template

Given the question, extract the metadata to filter the database about article sources. Avoid stopwords.  The sources can only be from the list: [’Yardbarker’, ’The Guardian’, ’Revyuh Media’, ’The Independent - Sports’, ’Wired’, ’Sport Grill’, ’Hacker News’, ’Iot Business News’, ’Insidesport’, ’Sporting News’, ’Seeking Alpha’, ’The Age’, ’CBSSports.com’, ’The Sydney Morning Herald’, ’FOX News - Health’, ’Science News For Students’, ’Polygon’, ’The Independent - Life and Style’, ’FOX News - Entertainment’, ’The Verge’, ’Business Line’, ’The New York Times’, ’The Roar | Sports Writers Blog’, ’Sportskeeda’, ’BBC News - Entertainment & Arts’, ’Business World’, ’BBC News - Technology’, ’Essentially Sports’, ’Mashable’, ’Advanced Science News’, ’TechCrunch’, ’Financial Times’, ’Music Business Worldwide’, ’The Independent - Travel’, ’FOX News - Lifestyle’, ’TalkSport’, ’Yahoo News’, ’Scitechdaily | Science Space And Technology News 2017’, ’Globes English | Israel Business Arena’, ’Wide World Of Sports’, ’Rivals’, ’Fortune’, ’Zee Business’, ’Business Today | Latest Stock Market And Economy News India’, ’Sky Sports’, ’Cnbc | World Business News Leader’, ’Eos: Earth And Space Science News’, ’Live Science: The Most Interesting Articles’, ’Engadget’]  Examples to follow: Question: Who is the individual associated with the cryptocurrency industry facing a criminal trial on fraud and conspiracy charges, as reported by both The Verge and TechCrunch, and is accused by prosecutors of committing fraud for personal gain? Answer: {’source’: {’$in’: [’The Verge’, ’TechCrunch’]}} Question: After the TechCrunch report on October 7, 2023, concerning Dave Clark’s comments on Flexport, and the subsequent TechCrunch article on October 30, 2023, regarding Ryan Petersen’s actions at Flexport, was there a change in the nature of the events reported? Answer: {’source’: {’$in’: [’TechCrunch’]}, ’published_at’: ’$in’: {[’October 7, 2023’, ’October 30, 2023’]}} Question: Which company, known for its dominance in the e-reader space and for offering exclusive invite-only deals during sales events, faced a stock decline due to an antitrust lawsuit reported by ’The Sydney Morning Herald’ and discussed by sellers in a ’Cnbc | World Business News Leader’ article? Answer: {’source’: {’$in’: [’The Sydney Morning Herald’, ’Cnbc | World Business News Leader’]}}  If you detect multiple queries, return the answer for the first. Now it is your turn: Question: <query> Answer:


# WarpGate: A Semantic Join Discovery System
for Cloud Data Warehouses

Tianji Cong∗ University of Michigan Ann Arbor Michigan USA<EMAIL_ADDRESS>,
James Gale  Sigma Computing San Francisco California USA
<EMAIL_ADDRESS>,  Jason Frantz  Sigma Computing San Francisco
California USA<EMAIL_ADDRESS>,  H. V. Jagadish  University of
Michigan Ann Arbor Michigan USA<EMAIL_ADDRESS>and  Çağatay Demiralp  Sigma
Computing San Francisco California USA<EMAIL_ADDRESS>
###### Abstract.

Data discovery is a major challenge in enterprise data analysis: users often
struggle to find data relevant to their analysis goals or even to navigate
through data across data sources, each of which may easily contain thousands
of tables. One common user need is to discover tables joinable with a given
table. This need is particularly critical because join is a ubiquitous
operation in data analysis, and join paths are mostly obscure to users,
especially across databases. Furthermore, users are typically interested in
finding “semantically” joinable tables: with columns that can be transformed
to become joinable even if they are not joinable as currently represented in
the data store.

We present WarpGate, a system prototype for data discovery over cloud data
warehouses. WarpGate implements an embedding-based solution to semantic join
discovery, which encodes columns into high-dimensional vector space such that
joinable columns map to points that are near each other. Through experiments
on several table corpora, we show that WarpGate (i) captures semantic
relationships between tables, especially those across databases, and (ii) is
sample efficient and thus scalable to very large tables of millions of rows.
We also showcase an application of WarpGate within an enterprise product for
cloud data analytics.

∗Work done when Tianji was interning at Sigma Computing

Figure 1. The interface of Sigma Workbooks connecting to a CDW. Consider a
business user Joey who is interested in launching a sales campaign and
identifying ideal customers. She first opens up the ACCOUNT table in their
SALESFORCE database, which lists all customer companies. Next, she wants to
augment the table with relevant columns to help make customer selections.

##  1\. Introduction

Three major correlated forces act on enterprise data analysis today. First,
more and more enterprise data are stored on the cloud. Second, the size and
the diversity of data available to enterprises increase faster than ever as a
growing number of data sources feed into enterprises’ cloud data warehouses
(CDWs). Third, the number of users in enterprises who would like direct access
to cloud data for decision-making is also rapidly growing, boosting the demand
for easy-to-use cloud data analysis systems such as Sigma Workbooks Gale et
al. (2022). Hence enabling easy and effective data discovery is increasingly
more valuable. However, existing commercial solutions such as data catalogs
are typically inaccessible from business intelligence tools, inadequate for
surfacing relationships unknown to users, and inflexible in capturing data
semantics.

Not surprisingly, recent years have seen a rising interest in data discovery,
especially for Open Data Miller et al. (2018); Nargesian et al. (2018); Zhu et
al. (2019); Bogatu et al. (2020). This is a challenging problem due to the
unstructured/semi-structured nature of Open Data and the lack of high-quality
metadata. However, we observe that modern organizations also face data
discovery challenges when dealing with structured data (i.e., databases in
CDWs) for similar reasons: (i) in large CDWs, few people have a good
understanding of data and their relationships; (ii) data is added in a much
less modeled state as cloud computing power and storage become easily
accessible; and (iii) business users who do not have comprehensive knowledge
of underlying schema designs, are usually unaware of relationships between
datasets (e.g., PK/FK relationship between two tables). There is a need for
surfacing such relationships to help users connect related datasets within and
across databases. We also observe that CDW data tends to have more structure
than Open Data, sometimes has high update rates, and usually has far more
stringent requirements for completeness of discovery results.

Consider a business user Joey who has access to a CDW that comprises hundreds
of databases and thousands of tables (Figure 1). In the interest of launching
a sales campaign and finding potential customers, she starts with the ACCOUNT
table in their SALESFORCE database, which contains member and billing data of
their customer companies. To select ideal customers for the campaign, she
wants to augment the ACCOUNT table with additional information such as sectors
in which companies are engaged in their business activities. Now she has two
options to find that complementary information: either she manually browses
tables in the same database (even wanders through the entire data warehouse),
or she can ask internal data teams for support. Either way, her workflow is
significantly delayed. There is also a fair chance that she cannot go through
all databases as it is a tedious and laborious process, and the data team does
not have that particular piece of knowledge.

Despite efforts in prototyping data discovery for real-world applications
Fernandez et al. (2018a); Bharadwaj et al. (2021); Bogatu et al. (2022),
aspects of data discovery pertaining to enterprise settings are overlooked.
For example, previous works assume a full pass of underlying data in the
indexing/profiling phase. However, it is computationally and monetarily
expensive to pull all data out of CDWs. In addition, existing solutions,
including those for Open Data, focus on improving index lookup time for the
scale of Open Data lakes or Web table corpora, which usually consist of a very
large number (million scale) of small tables. In contrast, we observe that
Sigma customers’ CDWs have several thousand tables on average but can have
billions of rows. Due to the relatively smaller number of tables but larger
table sizes, index lookup time becomes less dominant compared to data loading
time and profiling time, both of which can now bottleneck end-to-end query
response time in the pipeline. So, the main challenge in the Sigma scenario
shifts in part from searching over a massive number of small tables to
optimizing the entire pipeline for a fair number of very large tables (e.g.,
reducing data loading time and using efficient profiling methods).

In this work, we introduce a data discovery system WarpGate and share our
progress. WarpGate prototypes semantic join discovery in Sigma, an enterprise
platform for cloud data analytics. Specifically, we make the following
contributions:

  * •

We present WarpGate, a semantic join discovery system, which demonstrates a
real-world usage scenario of data discovery within an enterprise product.

  * •

We identify unique challenges in Sigma and propose an embedding-based solution
to capture semantic relationships between tables, especially those across
databases.

  * •

We evaluate WarpGate on three cross-domain table corpora, including one
collected from a CDW, and show our embedding-based approach is effective and
robust to sampling. We also discuss further optimization opportunities for
deployment and larger-scale discovery.

##  2\. Problem Definition

In this section, we first briefly introduce Sigma and describe the data
discovery needs of Sigma users. Then we formally define our problem.

###  2.1. Data Discovery Need in Sigma

Sigma is a web-based SaaS platform for cloud data analytics and business
intelligence. It features Sigma Workbooks, which provides a spreadsheet-like
interface for business users to perform interactive visual analysis of data in
CDWs.

Among many features familiar to business users who are more skilled in
spreadsheet functions than SQL, Lookup enables users to write a spreadsheet
formula and add a column from another data source (i.e., another table) to
enrich the dataset at hand. Under the hood, Workbooks translates spreadsheet
formulas into SQL queries required to fetch data from cloud databases and
performs cardinality-preserving joins on related tables.

A major limitation of Lookup is that users have to specify the join path in
formulas. In other words, it requires users to have prior knowledge about
relationships between datasets. However, users often lack such knowledge and
have to rely on their data teams for help or manually browse tables in
databases to find a clue. This limitation has become a bottleneck in fully
utilizing the Lookup functionality, significantly delaying their data
exploration and analysis workflows. We believe this sort of data discovery
will be a challenge for all cloud analytics products and hence has to be
addressed.

###  2.2. Semantic Join Discovery

######  Problem Statement (Top-$k$ Semantic Join Discovery).

Given a corpus of tables $\mathcal{S}$, a query column $\mathbf{c_{q}}$ from a
table $\mathbf{Q}$, and a constant $k$, find up to $k$ candidate columns from
$\mathcal{S}$ such that they are most likely to be joinable with
$\mathbf{c_{q}}$.

Traditionally, joinable tables have been discovered through syntactic
analysis, which can miss many join opportunities, particularly when data are
independently sourced. High dimensional embeddings have recently been shown to
capture semantics effectively in many domains Deng et al. (2020); Zhang et al.
(2020). We expect that the semantic similarity of two columns can be
quantified by some similarity measure between their embeddings, which we
expect can serve as a proxy for their join-ability as well.

######  Definition (Semantic Column Join-ability).

Given two columns $A$ and $B$, we define semantic column join-ability
$\mathcal{J}(A,B)$ as

$\mathcal{J}(A,B)=\mathcal{M}(\mathcal{T}(A),\mathcal{T}(B))$

where $\mathcal{T}(\cdot)$ is an embedding function that projects a given
column into a vector space and $\mathcal{M}(\cdot,\cdot)$ is a similarity
measure between two embeddings in the vector space.

Based on this metric, we can attempt to solve the semantic join discovery
problem by returning candidate tables in descending order of semantic column
join-ability $\mathcal{J}$ relative to the query column $\mathbf{c_{q}}$. How
to do this effectively is the central challenge addressed in this paper.

##  3\. WarpGate Overview

Figure 2. WarpGate pipeline.

We discuss key challenges to implementing an embedding-based approach to the
semantic join discovery problem, along with our solutions to these challenges
in Section 3.1. Then we describe our system prototype WarpGate incorporating
these ideas in Section 3.2.

###  3.1. Embedding-Based Solution

Figure 2 gives an overview of the WarpGate architecture, which consists of two
main pipelines: indexing and search, which we consider in turn below. But
first, we discuss the embedding step common to both pipelines.

####  3.1.1. Column Embeddings

We consider embeddings at the column level an effective encapsulation of
semantics for join discovery. Intuitively, embeddings can capture semantic
relationships between columns across databases where value formatting may vary
widely despite semantic proximity.

However, the effectiveness of embeddings depends on the embedding model. We
consider several factors in choosing an embedding model:

  1. (i)

Whether the model is (pre-)trained over tabular data;

  2. (ii)

The size of the training corpus;

  3. (iii)

The efficiency of model inference.

We observe two primary paradigms in applying embeddings for data management
tasks. Early work Bordawekar and Shmueli (2017) leverages off-the-shelf
embedding models from the natural language processing (NLP) field. Recent work
Günther et al. (2021); Deng et al. (2020) adapts NLP model architectures and
training algorithms for tabular data. As demonstrated in their work,
embeddings from models trained on tabular data manifest better performance in
downstream tasks. For instance, using the same training algorithm, Günther et
al. (2021) shows that models trained on sequences extracted from tables
outperform the model trained on an unstructured text corpus. The performance
uplift is attributed to the serialization of tabular data, which considers the
table structure in the embedding process. With this observation, we prefer
embedding models designed for tabular data.

Empirically, more training data usually lead to better model performance and
generalizability, given enough model capacity. In the database community, Web
table corpora Eberius et al. (2015); Lehmberg et al. (2016) extracted from the
Common Crawl contribute the largest publicly accessible relational table
datasets. Efforts exploring representation learning for relational tables
Günther et al. (2021); Deng et al. (2020) have trained embeddings on various
Web table corpus, which also exhibits the impact of Web tables beyond Web
applications. Thus, we favor embedding models derived from those large table
corpora.

The embedding process for tabular data generally involves table serialization,
input encoding (e.g., tokenization and transformation), and model inference.
It is worth noting that although more complex models (in terms of the number
of parameters) give embeddings that tend to yield better results in the
downstream tasks, they also carry a larger inference cost (i.e., longer
inference time, which directly affects query response time) compared to simple
models. For interactive applications such as join discovery and recommendation
in Sigma, we need to choose models that balance the embedding quality and
model inference time.

####  3.1.2. Indexing

We employ locality-sensitive hashing (LSH) Gionis et al. (1999); Charikar
(2014) to turn the high-dimensional embedding similarity search problem into
nearest neighbor search in a low-dimensional space. The basic idea of LSH is
to maximize hash collisions for similar inputs. With respect to a similarity
measure, LSH applies a specific family of hash functions that assign two
similar inputs to the same “buckets” with high probability that is equal to
the similarity score between them.

In our case, we consider the semantic join-ability of two columns to be the
cosine similarity of their embeddings. To approximate the cosine similarity of
two vectors, we rely on SimHash (also known as random projection) Charikar
(2014) that essentially uses hyperplanes in the vector space as hash
functions. We hash all column embeddings from the table corpus into a SimHash
LSH index. When a query comes in, the LSH index hashes the query embedding and
only searches within the sub-universe of embedding vectors (much smaller than
the entire universe) that share the same hash as the query, hence reducing the
search time.

####  3.1.3. Sampling

Existing data discovery systems Fernandez et al. (2018a); Bogatu et al.
(2020); Bogatu et al. (2022) run a one-pass data scanning step to read all
datasets once and retrieve profiling information (e.g., MinHash for each
column). Reading full tables of millions of rows or even billions of rows from
CDWs is expensive in terms of both computation time and monetary cost because
CDW vendors that adopt a usage-based pricing model (i.e., pay-as-you-go)
charge per GB of data scanned. It is then intuitive to use sampling to reduce
the cost. But one side effect of sampling is potential disruptions to column
profiles. For instance, profiling methods like MinHash are shown to be
sensitive to the sample size Chen et al. (2014). It also remains unclear what
a good sample size is for embeddings to preserve the similarity for data
discovery.

Figure 3. WarpGate is integrated into a functionality called Add column via
lookup in Sigma Workbooks.

###  3.2. WarpGate Interface

We have implemented the ideas described above in a prototype system we call
WarpGate. As shown in Figure 3, we integrate WarpGate into Sigma Workbooks as
a functionality called Add column via lookup.

Continuing the example of a business user Joey who wants to identify customers
for a sales campaign, she opens up the Account table and sees a full list of
companies (the Name column highlighted in Step 1 of Figure 3). To help make
the decision, she wants to augment the table with additional information so
that she can know which companies fall into the scope of the sale campaign. In
the current interface, she right-clicks on the Name column and chooses the Add
column via lookup option in the menu. A window shows up (Step 2 in Figure 3)
and displays top-$k$ join path recommendations. Each recommendation gives the
candidate join column, the table, and the database from which the candidate
column comes, as well as a similarity score relative to the Name column (i.e.,
the query column). Although recommendations are ranked in descending order of
the similarity score, Joey can pick one that fits her interest most. Once she
chooses a candidate, the window will display a list of all the columns from
the candidate table. Joey can browse and select the most relevant columns. For
now, the interface will add user-selected columns to the Account table right
at the side of the Name column for information complement and also load the
candidate table into Sigma Workbooks for further inspection. In Step 3, we
simply add and show the first recommended column, which is a foreign key in
the same database.

The current interface design is based on the consideration that it is less
desirable to simply join two wide tables with many columns and overwhelm users
with a display of an even wider table that does not really help users with
their information needs. In this case, Joey can first add the most relevant
columns at first glance based on her domain knowledge while having the
flexibility to see the entire candidate table for more careful examination.

##  4\. Experiments

We evaluate WarpGate on effectiveness and efficiency in comparison with two
existing data discovery systems that support enterprise use cases. We obtain
promising results of our embedding-based approach and show that it is sample-
efficient and scales well to tables of millions of rows.

###  4.1. Datasets

We use three repositories for evaluation. Table 1 gives a summary of dataset
characteristics.

Table 1. Basic statistics of evaluation datasets. XS is shorthand for
testbedXS in the NextiaJD repository, similarly for S, M, and L.

| # Tables | # Columns | Avg. # Rows | # Queries | Avg. # Answers
---|---|---|---|---|---
XS | 28 | 257 | 1,938 | 35 | 2.8
S | 46 | 2,553 | 209,646 | 177 | 3.6
M | 46 | 1,067 | 3,175,904 | 188 | 4.4
L | 19 | 541 | 12,288,165 | 92 | 3.6
Spider | 70 | 429 | 7632 | 60 | 1.1
Sigma | 98 | 1,343 | 2,243,932 | TBD | N/A

NextiaJD. Flores et al. Flores et al. (2021) composes four testbeds of
datasets from open repositories such as Kaggle and OpenML. Datasets are
divided into testbeds according to their file size. For instance, NextiaJD-XS
contains datasets of size smaller than 1 MB while NextiaJD-L consists of
datasets of size larger than 1 GB. They also label the join quality of pairs
of attributes based on a measure that considers both containment and
cardinality proportion with empirically determined thresholds. In experiments,
we use attribute pairs with quality labeled as Good and High by Flores et al.
(2021).

Spider. Released as a large-scale semantic parsing and text-to-SQL dataset,
Spider Yu et al. (2018) includes 5,693 SQL queries on 200 databases across
domains. We parse schema SQL files and retrieve join paths between primary
keys and foreign keys as ground truth. Spider has both the training set and
the development set, and we currently use join paths from the development set
for evaluation.

Sigma. The Sigma Sample Database is a collection of schema and tables that are
accessible to all Sigma Computing accounts for exploration. It is stored in a
Snowflake account managed by Sigma Computing and changes over time. The
datasets in this database vary in origin; some are real, publicly accessible
data, some are real data that has been obfuscated, and some are completely
auto-generated data. The domain of the data ranges includes retail
(transactions, products and stores), financial (daily attributes of many
securities), demographic (census, restaurants and bikes) and usage (cloud
application usage and metering, server logs).

###  4.2. Baselines & Metrics

For comparison, we consider as baselines two system prototypes Aurum Fernandez
et al. (2018a) and D3L Bogatu et al. (2020) that report on real-world data
discovery (see Section 6 for more information). Note that Aurum stores
detected relationships in a graph data structure and does not support top-$k$
search.

When ground truth is available, we report top-$k$ precision and recall with
varying $k$. At each value of $k$, we average the precision and recall numbers
over all the queries. We also limit $k$ to a small range since the average
number of answers to a query is small in evaluation datasets, and we don’t
want to overwhelm users with too many recommendations.

Besides effectiveness, we consider index lookup time and end-to-end query
response time for efficiency measurement. Index lookup time refers to the time
for the index data structure to return top-k candidates, whereas end-to-end
query response time is the total amount of time for a discovery system to
respond to a query, which includes data loading and embedding inference time
in our case. We report both metrics in seconds averaged over all queries in a
dataset. It is crucial in our application scenario that the system responds to
queries at interactive speed.

###  4.3. Experiment Results

Based on considerations in Section 3.1, we choose to use Web Table Embeddings
Günther et al. (2021) as our underlying embedding model. We set the similarity
threshold of the SimHash LSH index to 0.7 and run baselines with their default
setting. All experiments are conducted on an Amazon EC2 p3.8xlarge instance.

####  4.3.1. Join Discovery on nextiaJD Testbeds

(a) testbedS

(b) testbedM

(c) Spider

Figure 4. Top-$k$ precision and recall.

We present discovery results on NextiaJD testbedS and testbedM in Figure 4(a)
and 4(b) respectively (results on four testbeds have similar trends while
these two testbeds contain more tables and queries than the other two). As
shown, WarpGate consistently obtains higher precision and recall compared with
two baselines as $k$ increases.

Table 2. End-to-end query response time in seconds/query (for $k=10$) along
with index lookup time reported in paratheses for WarpGate.

| Aurum | D3L | WarpGate
---|---|---|---
testbedS | 0.18 | 4.77 | 3.12 (1.04)
testbedM | 0.03 | 57.69 | 38.73 (8.39)

Table 2 shows end-to-end query response time. Aurum is significantly faster
because it indexes detected relationships in another graph data structure for
result retrieval. In contrast, D${}^{3}L$ is the slowest since it uses an
ensemble approach and aggregating multiple types of signals takes longer. As
we can also see here, given the equal number of tables in two testbeds, when
the average number of rows increases by an order of magnitude, query response
time increases linearly and becomes unacceptable for interactive purposes.
Moreover, index lookup time accounts for less than 25% of query response time
on testbedS and less than 13% on testbedM. This suggests that there are other
bottlenecks in the pipeline and improving only index lookup time (as many
earlier works focus on) is not enough to reduce overall query response time.
Upon inspection, we found loading large datasets from disk to memory and
embedding inference take most of the time besides index lookup. We show in
Section 4.4 that sampling is an effective mitigation and our embedding
approach is robust to sample size.

####  4.3.2. PK/FK Detection on Spider

Figure 4(c) shows the top-$k$ precision and recall of three systems on the
Spider dataset. We use this dataset mainly to demonstrate that for PK/FK
detection within each independent database, the embedding measure alone
(WarpGate) can compare favorably against the ensemble approach (D3L) and
outperform the syntactic-only approach (Aurum) by a large margin. As to D3L,
the jump of recall from $k=5$ to $k=10$ is attributed to the column name
similarity measure in D3L, and we indeed observe in Spider that many PK/FKs
share syntactically similar column names. Since Spider has a small number of
tables that contain thousands of rows on average, the search time is fast for
all three systems, which is no more than 2 seconds for running all the
queries.

####  4.3.3. Ad-Hoc Discovery in Sigma

Since Sigma Sample Database is a corpus without ground truth, we ask four
colleagues to pick columns of interest as queries. Here we describe one of the
most interesting discoveries. In future work, we plan to conduct a user study
to evaluate the value of WarpGate in a principled manner.

Continuing our running example of the business user Joey, who is interested in
looking for additional information to help make the decision of customer
selection. Figure 3 displays the top-3 recommendations from WarpGate. The
first candidate is the Company column of the LEAD table from the same database
as the query column, which contains information on contact points in each
company (e.g., name, title, and address of each contact point). Upon browsing
columns in the LEAD table, Joey does not find auxiliary information for her
need. She moves to inspect the second candidate, which is the Company Name
column of the INDUSTRIES table from the STOCKS database. In the same table,
the Industry Group column has sector information of US public companies, which
can (partially) enrich the query table. Joey then acts on her customer
selection by filtering companies with their sectors. Even more interestingly,
she can add to the query table the TICKER column from the INDUSTRIES table,
which can be further used as the join key to add columns of stock prices from
the same STOCKS database. This way, Joey can track down high-performing
companies in targeted sectors as her sales campaign customers.

###  4.4. Sample Efficiency

We run WarpGate over NextiaJD-S and NextiaJD-M with sample size 10, 100, and
1000. For all sample sizes, the embedding approach remains as effective as
using full values with $\pm 1\%/2\%$ variation at different $k$ values. In the
meanwhile, index lookup time is reduced by up to two orders of magnitude
(e.g., from about 1 second to about 10 milliseconds on NextiaJD-S), and end-
to-end query response time also comes down to interactive speed (under 35
milliseconds per query on NextiaJD-S and under 65 milliseconds per query on
NextiaJD-M). We discuss further optimization opportunities in Section 5.

To see if sample efficiency is unique to Web Table Embeddings, we also
evaluate BERT Devlin et al. (2019) as our underlying embedding model. We
observe that the effectiveness of BERT Embeddings is robust to sample size as
well. Although BERT is a significantly more complex model, we do not see much
improvement in effectiveness (mostly on par with Web Table Embeddings).
Nevertheless, index lookup time and query response time are 10x slower without
sampling due to more expensive embedding inference costs.

##  5\. Discussion

###  5.1. Sigma Customer Data Scale

The scale of enterprise CDWs is a challenge for any deployment of join
discovery. The median Sigma customer warehouse has 450 tables for analysis,
but the average is over 12,700 tables with an average of 25.7 columns per
table. The size of enterprise tables is also a challenge. The median table in
these warehouses has just 7,700 rows, but the average is 1.7 billion rows.
Actively sampling this large number of tables incurs usage costs in CDWs, so a
passive sampling of user queries is beneficial. Likewise, samples can be
shared across ML applications in Sigma to amortize their cost.

###  5.2. Optimization Opportunities

####  5.2.1. Contextual Embeddings.

Existing approaches generally follow a two-step process: they first build
profiles for each column independently and then determine join-ability of two
columns based on some notion of similarity between their profiles (e.g.,
containment or Jaccard similarity). Typically, the context of a column is not
taken into account when building those profiles. However, context (e.g., other
columns in the same table, user activities, query logs) can potentially
provide auxiliary information that is critical to find semantically related
candidates. We plan to explore the option of incorporating context information
into the underlying embedding model of WarpGate.

####  5.2.2. Data Management for Data Discovery.

CSV is a common file format for tabular data in Open Data Lakes and table
repositories on the Web. Despite the flexibility and human readability of CSV
files, the flat-file format is not ideal for storage and query purposes. We
note that (1) loading giant CSV files and running embedding inference can
incur heavy memory usage and crash programs on small machines; (2) operations
in join discovery like embedding inference are column-oriented; (3) what is
unique in our scenario is that our data are pulled from CDWs, thus more
structured and much better data quality than those in the wild. (1) and (2)
make us think it is more memory and storage efficient to take advantage of
(in-memory) column stores for data pulled out of CDWs, and (3) can make the
process easier. This change will also have significant implications for
deployment as we need to provision CPU and memory usage in Sigma’s Kubernetes
cluster.

####  5.2.3. Efficient Search.

To further improve query response time for Sigma customers with a massive
number of tables in their CDWs, we are considering two directions: (1) a
block-and-verify strategy in Dong et al. (2021), which employs pivot-based
filtering to prune dissimilar vectors; (2) fine-tune off-the-shelf embedding
models in a self-supervised way that pushes embeddings of joinable columns to
have higher cosine similarity so that an index data structure like SimHash can
be better utilized Cong et al. (2022).

##  6\. Related Work

WarpGate builds on earlier work on data discovery for enterprise data systems
and Open Data, which we summarize below. We distinguish WarpGate from this
earlier work mainly in two aspects: (i) we recognize and showcase the value of
data discovery for structured data in enterprise CDWs; (ii) we do not assume a
full pass of data in the indexing/profiling phase and show that the embedding-
based approach is effective and robust to data samples.

Data Discovery Systems for Enterprise. Aurum Fernandez et al. (2018a) models
syntactic relationships between datasets in a graph data structure to support
data discovery. In a two-step process of profiling data and computing the
relationship between data signatures, Aurum builds up a graph with nodes
representing column profiles and weighted edges indicating syntactic
relationships between two nodes (e.g., content similarity). With an in-memory
index of the graph, Aurum can efficiently support various discovery needs,
such as how similar two columns are, which can be used to find joinable
datasets. SemProp Fernandez et al. (2018b) extends Aurum by using word
embeddings to surface semantically related objects in the graph.

Voyager Bogatu et al. (2022) built on top of D3L Bogatu et al. (2020)
formalizes and supports three tasks routinely performed by data scientists
using their platform. It profiles data with a full scan and indexes columns
with MinHash. Voyager also drops the embedding measure in D3L and relies only
on syntactic measures.

Join Discovery over Open Data. JOSIE Zhu et al. (2019) considers the problem
of finding joinable tables in modern data lakes. It formulates the problem as
a top-k overlap set similarity search problem where columns are treated as
sets and matching values as intersections between sets. By using a cost model
for estimating the reading costs of data structures, JOSIE contributes an
exact overlap set similarity search algorithm that can adapt to different data
distributions.

Juneu Zhang and Ives (2020) aims to help users find semantically related
datasets in data lakes to augment data analytics tasks, including finding
joinable tables in interactive data science environments (e.g., Jupyter
Notebook). It combines multiple table-relatedness measures such as column and
row overlap, provenance, and user context and intent for related-table search.
In a similar vein, D3L Bogatu et al. (2020) uses five types of evidence to
determine column proximity: (i) column name similarity; (ii) column extent
overlap; (iii) word-embedding similarity; (iv) format representation
similarity; and (v) domain distribution similarity for numerical attributes.
This ensemble approach is shown to be more effective and efficient than Aurum
on table union search, which is a problem that has significant overlap with
join path discovery.

In contrast to the search paradigm, Nargesian et al. Nargesian et al. (2020)
propose building a navigation graph over data lakes. By leveraging a
probabilistic model, they show that navigation can help users find relevant
tables that cannot be found by keyword search.

##  7\. Conclusion

We present WarpGate, a system prototype for semantic join discovery in Sigma
Workbooks. In future work, we expect to share our experience and lessons of
deploying WarpGate in the production environment and conduct a user study to
further evaluate its value for end users.

We thank Oscar Bashaw, Nipurn Doshior, Qing Feng, Jade Fleishhacker, and Siva
Obulam for their help in WarpGate’s development. This project is supported in
part by NSF grant 1946932.

## References

  * (1)
  * Bharadwaj et al. (2021) Sagar Bharadwaj, Praveen Gupta, Ranjita Bhagwan, and Saikat Guha. 2021.  Discovering Related Data At Scale.  _Proc. VLDB Endow._ (2021), 1392–1400.
  * Bogatu et al. (2020) Alex Bogatu, Alvaro A. A. Fernandes, Norman W. Paton, and Nikolaos Konstantinou. 2020.  Dataset Discovery in Data Lakes. In _ICDE 2020_. IEEE, 709–720.
  * Bogatu et al. (2022) Alex Bogatu, Norman W. Paton, Mark Douthwaite, and André Freitas. 2022.  Voyager: Data Discovery and Integration for Onboarding in Data Science. In _EDBT 2022_. OpenProceedings.org, 2:537–2:548.
  * Bordawekar and Shmueli (2017) Rajesh Bordawekar and Oded Shmueli. 2017.  Using Word Embedding to Enable Semantic Queries in Relational Databases. In _DEEM@SIGMOD 2017_. ACM.
  * Charikar (2014) Moses Charikar. 2014\.  Similarity estimation techniques from rounding algorithms. In _STOC 2014_. ACM, 380–388.
  * Chen et al. (2014) Zhimin Chen, Vivek R. Narasayya, and Surajit Chaudhuri. 2014\.  Fast Foreign-Key Detection in Microsoft SQL Server PowerPivot for Excel.  _Proc. VLDB Endow._ (2014), 1417–1428.
  * Cong et al. (2022) Tianji Cong, Fatemeh Nargesian, and H. V. Jagadish. 2022\.  Pylon: Semantic Table Union Search in Data Lakes.  _Under review_.
  * Deng et al. (2020) Xiang Deng, Huan Sun, Alyssa Lees, You Wu, and Cong Yu. 2020.  TURL: Table Understanding through Representation Learning.  _Proc. VLDB Endow._ (2020), 307–319.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In _NAACL-HLT 2019_. Association for Computational Linguistics, 4171–4186.
  * Dong et al. (2021) Yuyang Dong, Kunihiro Takeoka, Chuan Xiao, and Masafumi Oyamada. 2021.  Efficient Joinable Table Discovery in Data Lakes: A High-Dimensional Similarity-Based Approach. In _ICDE 2021_. IEEE, 456–467.
  * Eberius et al. (2015) Julian Eberius, Maik Thiele, Katrin Braunschweig, and Wolfgang Lehner. 2015.  Top-k entity augmentation using consistent set covering. In _SSDBM 2015_. ACM, 8:1–8:12.
  * Fernandez et al. (2018a) Raul Castro Fernandez, Ziawasch Abedjan, Famien Koko, Gina Yuan, Samuel Madden, and Michael Stonebraker. 2018a.  Aurum: A Data Discovery System. In _ICDE 2018_. IEEE Computer Society, 1001–1012.
  * Fernandez et al. (2018b) Raul Castro Fernandez, Essam Mansour, Abdulhakim Ali Qahtan, Ahmed K. Elmagarmid, Ihab F. Ilyas, Samuel Madden, Mourad Ouzzani, Michael Stonebraker, and Nan Tang. 2018b.  Seeping Semantics: Linking Datasets Using Word Embeddings for Data Discovery. In _ICDE 2018_. IEEE Computer Society, 989–1000.
  * Flores et al. (2021) Javier Flores, Sergi Nadal, and Oscar Romero. 2021\.  Towards Scalable Data Discovery. In _EDBT 2021_. OpenProceedings.org, 433–438.
  * Gale et al. (2022) James Gale, Max Seiden, Deepanshu Utkarsh, Jason Frantz, Rob Woollen, and Çagatay Demiralp. 2022.  Sigma Workbook: A Spreadsheet for Cloud Data Warehouses.  _Proc. VLDB Endow._ (2022), 3670–3673.
  * Gionis et al. (1999) Aristides Gionis, Piotr Indyk, and Rajeev Motwani. 1999\.  Similarity Search in High Dimensions via Hashing. In _VLDB 1999_. 518–529.
  * Günther et al. (2021) Michael Günther, Maik Thiele, Julius Gonsior, and Wolfgang Lehner. 2021.  Pre-Trained Web Table Embeddings for Table Discovery. In _aiDM@SIGMOD 2021_. ACM, 24–31.
  * Lehmberg et al. (2016) Oliver Lehmberg, Dominique Ritze, Robert Meusel, and Christian Bizer. 2016.  A Large Public Corpus of Web Tables containing Time and Context Metadata. In _WWW 2016_. ACM, 75–76.
  * Miller et al. (2018) Renée J. Miller, Fatemeh Nargesian, Erkang Zhu, Christina Christodoulakis, Ken Q. Pu, and Periklis Andritsos. 2018.  Making Open Data Transparent: Data Discovery on Open Data.  _IEEE Data Eng. Bull._ (2018), 59–70.
  * Nargesian et al. (2020) Fatemeh Nargesian, Ken Q. Pu, Erkang Zhu, Bahar Ghadiri Bashardoost, and Renée J. Miller. 2020\.  Organizing Data Lakes for Navigation. In _SIGMOD 2020_. ACM, 1939–1950.
  * Nargesian et al. (2018) Fatemeh Nargesian, Erkang Zhu, Ken Q. Pu, and Renée J. Miller. 2018.  Table Union Search on Open Data.  _Proc. VLDB Endow._ (2018), 813–825.
  * Yu et al. (2018) Tao Yu, Rui Zhang, Kai Yang, Michihiro Yasunaga, Dongxu Wang, Zifan Li, James Ma, Irene Li, Qingning Yao, Shanelle Roman, Zilin Zhang, and Dragomir R. Radev. 2018\.  Spider: A Large-Scale Human-Labeled Dataset for Complex and Cross-Domain Semantic Parsing and Text-to-SQL Task. In _EMNLP 2018_. Association for Computational Linguistics, 3911–3921.
  * Zhang et al. (2020) Dan Zhang, Yoshihiko Suhara, Jinfeng Li, Madelon Hulsebos, Çagatay Demiralp, and Wang-Chiew Tan. 2020.  Sato: Contextual Semantic Type Detection in Tables.  _Proc. VLDB Endow._ (2020), 1835–1848.
  * Zhang and Ives (2020) Yi Zhang and Zachary G. Ives. 2020.  Finding Related Tables in Data Lakes for Interactive Data Science. In _SIGMOD 2020_. ACM, 1951–1966.
  * Zhu et al. (2019) Erkang Zhu, Dong Deng, Fatemeh Nargesian, and Renée J. Miller. 2019.  JOSIE: Overlap Set Similarity Search for Finding Joinable Tables in Data Lakes. In _SIGMOD 2019_. ACM, 847–864.


2 10000 0 7 cm headwidth = ,footwidth = : [chapter]chapter *[section]  Chapter
0 Chapter 0 Section 0 *
0 *
0 [font = , prefixfont = , ] part [font = , afterskip = 20 pt, ] chapter [toc]
]}

Universidad de Antofagasta
Facultad de Ciencias Básicas

Doctorado en Física Mención Física – Matemática

Design of optimization tools for quantum information theory

Daniel Uzcátegui Contreras

Profesor Tutor: Dardo Miguel Goyeneche

Antofagasta, Chile, enero 2022

Universidad de Antofagasta
Facultad de Ciencias Básicas

Doctorado en Física Mención Física – Matemática

Design of optimization tools for quantum information theory

Daniel Uzcátegui Contreras

Tesis presentada ante la ilustre Universidad de Antofagasta para
optar al grado académico de Doctor en Física
Mención Física – Matemática

Profesor Tutor: | Dardo Miguel Goyeneche
---|---
Comité de Evaluación: |
Alvaro Restuccia |
Freddy Lastra |
Algo Delgado |
Leonardo Neves |
Gustavo Cañas |

Antofagasta, Chile, enero 2022

*

Dedicated to my parents: María and Mario.

Acknowledgements

Here, I would like to thank many people who has helped me to make this thesis
possible.

First and foremost, I would like to thank my advisor, Prof. Dardo Goyeneche,
for all his guidance, encouragement and continuous support on both academic
and personal level. I greatly appreciate his patience to help me go through
this journey.

I would also like to thank all my professors in the program, for their support
and for providing me with many tools for my further development.

I would like to express my appreciation to my fellow students, for all their
help and support, and for all the special moments we shared.

My gratitude to the Universidad de Antofagasta, to the Departamento de Física
of the Universidad de Antofagasta and to all the people who works to make our
PhD program possible.

List of publications and ongoing projects This thesis is based on the
following publications and projects:

  * [A]

S. Gómez, D. Uzcátegui, I. Machuca, E. S. Gómez, S. P. Walborn, G. Lima, and
D. Goyeneche., Optimal strategy to certify quantum nonlocality, Sci Rep 11,
20489 (2021).

  * [B]

D. Uzcátegui, G. Senno and D. Goyeneche., Fast and simple quantum state
estimation, 2021 J. Phys. A: Math. Theor. 54 085302.

  * [C]

D. Uzcátegui, G. Senno and D. Goyeneche., An algorithm for the Quantum
Marginal Problem. In preparation.

Other related publications during my PhD studies:

  * [D]

Contreras, Daniel Uzcátegui; Goyeneche, Dardo; Turek, Ondřej and Václavíková,
Zuzana., Circulant matrices with orthogonal rows and off-diagonal entries of
absolute value 1, Communications in Mathematics, vol.29, no.1, 2021, pp.15-34.

Abstract

In this thesis, we present optimization tools for different problems in
quantum information theory. First, we introduce an algorithm for quantum
estate estimation. The algorithm consists of orthogonal projections on
intersecting hyperplanes, which are determined by the probability
distributions and the measurement operators. We show its performance, in both
runtime and fidelity, considering realistic errors. Second, we present a
technique for certifying quantum non-locality. Given a set of bipartite
measurement frequencies, this technique finds a Bell inequality that maximizes
the gap between the local hidden variable and the quantum value of a Bell
inequality. Lastly, to study the quantum marginal problem, we introduce an
operator and develop an algorithm, which takes as inputs a set of quantum
marginals and eigenvalues, and outputs a density matrix, if exists, compatible
with the prescribed data.

toc*totoc