DATA ACQUISITION FOR AI

Fatemeh Nargesian, University of Rochester

OPEN DATA MOVEMENT• AI has become ubiquitous.
• Data-centric AI: focus has shifted from big data to good data.
• Open data repositories and data markets have become prevalent.

• Improving governments• Empowering citizens• Solving big public problem• After Web, open data is the biggest database that citizens have access to.
• Focus of this talk: tabular and structured data

2

DATA LAKES VS. TRADITIONAL DATABASES• Data is stored in raw files (csv, xls, xml, …) and must be extracted.
• Large number of (medium-sized) datasets• No centralized data design or data quality control• Sparse and non-standardized metadata for datasets• Skewed data distribution on size, availability of metadata, etc.

35,675
Canada46,626
FranceNum of Columns• Vast number of topics: makes Canadian
open data
appealing.
OD
Web Tables

51,363
UK

247,074

$$$$$

USA

Data
Marketplaces

Column Size

Column Size

50,820,165
WDC Web Table(English Relational)

3

DATA SEARCH AND DATA ENRICHMENT
Analyzing the driving factors of GHG emission!
Enrich data scientist’s work in progresswith right data!
Geo
Geo? Fuel
Date
Date
Fuel

ttCO2
CO2 Sector
Sector ……

?
Cambridge
electricity
Cambridge 2015
2015
electricity 22

Waste
Waste

…

Worcester?
dieselWorcester 2021
2021
diesel

20
20

Metal
Metal

…

CamdenCamden

?
2014
coal
2014
coal

12
12

Oil&Gas
Oil&Gas …

NYC
NYC

?
2019
electricity
2019
electricity 11
11

Oil&Gas
Oil&Gas …

BostonBoston?
2023
diesel2023
diesel

98

Metal
Metal

…

Rochester

2021 coal

9

Metal

…

…

...

…

…

…

…

Data enrichment requires dataset discovery• Adding novel features: joining the query
dataset with some datasets in the lake.
• Adding samples: unioning the query datasetwith some datasets in the lake.
4

DATASET DISCOVERYTASK OF FINDING RELEVANT DATASETS TO A QUERY

Query Type
keyword-style
distribution requirement
column/table[MZNA, ICDE’23;
ZDNM,SIGMOD’19;
NZPM, VLDB’18; ZNPM, VLDB’17;
ZNPM, VLDB’16][CDNB, SIGMOD’24;
CNAJ, VLDBJ’24;
NAJ, SIGMOD’22;
AN, VLDB’22;
NAJ, VLDB’21]

Distribution Tailoring

Joinable Dataset Discovery
Unionable Dataset Discovery
full dataset

samples

Data Lake Organization[BBKN+, EDBT’24;
BBKN+, SIGMOD’23;
NPZGM, TKDE’23;
OSNB+, VLDB’21;
NPZGM, SIGMOD’20]

metadata

Access Level to Data Lake
5

JOINABLE DATASET DISCOVERYHow to enrich a query dataset with novel columns and features?

OVERVIEW: JOIN IN DATABASES• In databases, we often know which columns to join: join on primary/foreign keys
JOIN

StudentInfo

DepartmentInfo

StudentID Name Department

Department

Pop

Chair …

100

Sue

CS

CS

1500

foo

101

Yi

Data Science

Data Science

2500

bar

102

John

Math

Math

1000

foo

DepartmentInfo

StudentInfo

StudentID Name Department Pop

Chair …

100

Sue

CS

1500 foo101

Yi

Data Science

2500 bar

102

John

Math

1000 foo

7

JOIN IN DATA LAKES• Not obvious which table to join on: makes discovery a search problem• Joins might not be possible on all query’s tuples: smaller result set than query (incomplete
data)
query table
Geo

Date Fuelt CO2Barnet1302015 electricity 13

Sector

Area

…
…

Pop

Avg_age Unemp …

Metal

City of London 242500 43.2

2142500 36.44389600 37.3

8.5

City of London 2015 diesel

200
20

Oil&GasCamdenCamden2014 coal

125
12Domestic

Cambridge

Hackney2021 Electricity 100

Metal

…

?

JOIN

query column
Geo

Date Fuel

SectorPop

Avg_age Unemp …

City of London 2015 diesel 20

Oil&Gas24250043.2

4CamdenDomestic

14250036.4

22014 Coal

t CO2

12

8

JOINABILITY MEASURE• If columns and query are considered as sets of values,
maximize set overlap of query and candidate.
Overlap Q, X = 𝑄𝑄 ∩ 𝑋𝑋
𝑄𝑄 ∩ 𝑋𝑋
Containment Q, X =|𝑄𝑄|• Another popular set similarity measure is
Jaccard Q, X =candidate col X
from a data lake
query col Q

maximizejoin result

joinresult𝑄𝑄 ∩ 𝑋𝑋|𝑄𝑄 ∪ 𝑋𝑋|[ZDNPM,SIGMOD’19; ZNPM,VLDB’16]

9

SEMANTIC JOINABILITY• Syntactic measures become ineffective for joining dirty and heterogenous data in the wild.
query table… Date Fuel

Overlap(Geo,Area) = 1
t CO2 Sector

Geo

Area

Pop

Avg_age F.Unemp Unemp …

2015 electricity 130

Domestic Blaine

LA

8800

43.2

-

-

2015 diesel

200

Transport LA

Big Apple

242500

36.4

62.9

4

2014 coal

125

Domestic NYC

Blain

389600

37.3

66

8.5

…

• Semantic overlap extends syntactic overlap for effective search despite semantic andsyntactic heterogeneity of tuples.

KOIOS: Top-K Semantic Overlap Set Search, P. Mundra, J. Zhang, F. Nargesian, N. Augsten, ICDE, 2023.

10

SEMANTIC OVERLAP MEASURE…

Q
LABlaineBigApple

SEMA-JOIN[He,Gunjam+VLDB’15]

Q = {LA, Seattle, Columbia, Blaine, BigApple, Charleston}C = {LA, Blain, Appleton, Tacoma, Lexington, WestCoast}

…

Q
…

C
LA
Blain

LA
1

C

Seattle
.99

LA

Blain

Columbia

BlaineBigApple
.3

.75

.8
TacomaMtPleasantCharleston.7

Lexington.7
WestCost

Tacoma…

Greedymatching
providesa lower-boundsemantic
overlap.
Semantic
overlapof twocolumns
Q andanyC, subgraphi.e., for
SO(Q,C):
Maximummatching
scoretoofatthe• Bipartite
graph
matching:
M s.t.
eachnode
is adjacentEdgeweights
bipartite graphof Q
andC witha user-specified tuple similarity function and threshold.
most
one
other
node.
• Semantic similarity: Cosine on embeddings of col. values, etc.
• Join with• semantic
results
in oflargerresult than syntactic join.
Score of overlap
a matching:sum
edgejoinweights• Syntactic similarity: Jaccard on n-grams of col. values• 𝑄𝑄 ∩ 𝐶𝐶 ≤ 𝑆𝑆𝑆𝑆 𝑄𝑄, 𝐶𝐶
score(M) = 4.14
• Pruned by similarity threshold 𝛼𝛼• Discovery requires finding joinable columns and the best way of joining them.

11TOP-K SEMANTIC OVERLAP SEARCH• Semantic overlap can be expensive• Bipartite graph matching: O(n3), n is col. size [Kuhn’1995]• Bipartite graph construction: O(n2)• Problem. Given a column Q and parameter K, find the top-K columns based on
the semantic overlap measure.
• Search complexity: O(mn3), n is the size of cols. and m is the number of sets
• Linear scan over all datasets and computing graph matching is infeasible inpractice for data lakes of tens of thousands of datasets.
• Solution. KOIOS is an exact and efficient top-K join search algorithm with semantic
overlap.
12

KOIOS: FILTER-VERIFICATION FRAMEWORK
candidate poolθlbθlbD1

index

Top-2 search
DD2 2

D1

D3

D2

data lake
index

.
.
.

Query Q
order cols X based on
upper bound of
sem-overlap(X,Q)

Filter• Upper- and lower-bound filters• A partitioning scheme for efficient filtering

D6

Verification

D6D6

D4

D5
SO

top-K columns X• Early termination of bipartite graph matching

13

Getting edges of a bipartite
graph requires |C|x|Q|
tuple similarity calculations.
Idea. No need to build
matchings for all candidate
cols. Build partial greedy
matches incrementally.

FILTER: INCREMENTAL BOUNDS
smallest seen edge weights1min⩾...4⩾...
⩾s
2
3
2⩾s
3⩾s
4⩾s
4⩾...

ANN
index

Q
.65smin

1

.75

.99
smin

.8

.7
smin .7

C

𝑆𝑆𝑆𝑆 𝑄𝑄, 𝐶𝐶 = 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠

stream of edges orderedbased on row similarity
scores descendingly: e.g.,simhash LSH for Cosine ofrow/cell emb vectors.

𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖_𝐿𝐿𝐿𝐿 𝐶𝐶 = � 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 𝑤𝑤𝑤𝑤𝑤𝑤𝑤𝑤𝑤𝑤𝑤 𝑖𝑖𝑖𝑖 𝑎𝑎 𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔 “𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚

𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖𝑖_𝑈𝑈𝑈𝑈 𝐶𝐶 = � 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 𝑤𝑤𝑤𝑤𝑤𝑤𝑤𝑤𝑤𝑤𝑤 𝑖𝑖𝑖𝑖 𝑎𝑎 𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔 “𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚+ smallest seen edge weight . (max matching size - partial matching size)
14

VERIFICATION: EARLY TERMINATION OF MATCHING
θlb
D1

D5

1

D2

0.99

D3
D4

1

q

.99

.75

1

SO

0.9

.8

1

0.8

.7

.7

c
1

1

0.8

1

0.99

0.99

• Hungarian algorithm assigns a valid labeling function label: nodes→R, s.t. for two nodes q and c,label q + label c ≥ edge_weight q, c

• The algorithm improves on the labeling function iteratively. At each iteration:

bipartite matching score Q, C ≤ � node lables
upper bound(Q, C) = � node lables• Terminate matching prematurely.

15

EVALUATION
datasets statistics

comparison to SOTA

Dataset

#Sets

Max
Card.

Avg.
Card.

#Unique
Elements

DBLP

4,246

514

178.7

25,159OpenData

15,63631,901

86.4

179,830

Twitter

27,204151

22.6

72,910WDC

1,014,369

10,24030.6

328,357

Dataset

KOIOS
Response
Time (s)SOTA
Response
Time (s)KOIOS Mem
(MB)

SOTA
Mem
(MB)

DBLP

0.83

211

0.83

11

OpenData

18.6

101

18.6

102.5

Twitter

0.7

518

0.7

10

WDC

147

1062

147

885

• KOIOS achieves at least 5X speed up over the SOTA on massive data lakes.
• Even better speedup for medium and large queries compared to the SOTA.
16

DATASET DISCOVERY
Query Type
keyword-style

Data Lake Organization
Distribution Tailoring

distribution requirement
column/table

Joinable Dataset Discovery
Unionable Dataset Discovery
full dataset

samples

metadata

Access Level to Data Lake

17

DISCOVERY + DISTRIBUTION REQUIREMENT•••

Scenarios with distribution requirements•••

Representation in test data
Seeking data with a sufficient representation to avoid overfitting
Selection bias leads to flawed and unreliable outcomes.

Nearest neighbor search index on histograms of groups in datasets [Mao+,AAAI’17]••

Non-existent results
Need to know the group of each tuple apriori at index time.

Combine multiple datasets to get the distribution we want!
bank loan
decision making
test

At least 30% African American
female employees from Texas w/
salary>=55K and at least 30% whitemale employees w/ salary>=55K

on histograms oftarget groups
Index

Responsible Data Integration: Next-generation Challenges, F. Nargesian, A.
Asudeh, H. V. Jagadish, SIGMOD, 2022.

18

DISTRIBUTION-AWARE DISCOVERYHow to construct a dataset that satisfies group distribution requirements frommultiple sources in a cost-effective manner?

QUERY/DATA/COST MODELS• Target dataset: schema + count requirements specified over groups• Schema: description of columns• Data sources• Data lake tables with the same schema as target schema• Project-join views over a database/data lake: join is expensive to execute, resort to tuple samplingfrom joins [Zhao+,SIGMOD’18; Li+,SIGMOD’16; Haas+, SIGMOD’99]• Other sources: crowd-sources, data providers – data market setting [AN,VLDB’22]: monetary cost forpurchasing data

sensitive
attribute
col.
SELECT??
FROM ?? JOIN ??
ON ?? = ??
UNION
SELECT ??
FROM ?? JOIN ??
UNION…

Source 1
group classified
by a model orSource2annotators$

Distribution
Tailoring

schema: (emp_id, dept, location,
gender, race, salary, loan_return)
distribution: 2K samples for eachdemographic grouptarget dataset

data sources
20

DATA DISTRIBUTION TAILORING (DT)Group Count
Requirements$$• Problem. Given sources with their costs, and minimum countrequirements on the groups, select samples from sources s.t.
the union of samples fulfills the count requirements, while
the expected total query cost is minimized.

source selection
sampling and group
identification
updating target
datasettargetdataset• Solution. Iterative sampling: find a sequence of sources tosample, until distribution requirement is satisfied.
• The cost optimality depends on how much DT knows aboutgroup distributions in sources.

21

DT STRATEGIES FOR (UN)KNOWNGROUP DISTRIBUTIONS• Known distributions• Dynamic programming solution• Pseudo-polynomial time and space complexity• Not practical for large number of groups and count requirements• Optimal strategy for binary groups and sources with equal costs• Practical strategy for m-ary groups and sources with arbitrary costs• Unknown distributions• Budget allocation strategy based on multi-armed bandit

Tailoring Data Source Distributions for Fairness-aware Data Integration. F. Nargesian, A.
Asudeh, H. V. Jagadish, VLDB, 2021.
Data Distribution Tailoring Revisited: Cost-Efficient Integration of Representative Data.
J. Chang, B. Cui, F. Nargesian, A. Asudeh. H. V. Jagadish, VLDBJ, 2024.

22

UR PhD
student

UNKOWN DISTRIBUTIONSUR Undergrad
student

No information about group distribution
?

?

?

…

?

?

targetdataset• Learning group distribution and source goodness as we sample.
• Solution. Applying Multi-armed Bandit (MAB)23total reward

OVERVIEW: MULTI-ARMED BANDIT
R1
ak• Given k arms a time horizon (budget) T, at eachtimestep t=1,...,T, we choose an arm,and receive a real-valued reward Rt.
• Reward depends on the arm and is iid.

R2
ai

…

R3
a2

a1

observed rewards for a1: 3, 10, 2
arm-value(a1) = 5• Distributions of rewards are unknown.
• Nevertheless, we must maximize our total reward.
• As selecting arms, form estimates for an arm’s value: e.g., the average of sample
rewards from the arm.
[Sutton&Barto, 1998]
24

OVERVIEW: MULTI-ARMED BANDIT• Maximize the total reward.

ak

ai

…

a2

a1

• Both try arms to learn their values (explore) and prefer those that appear best (exploit).

R1
R3• Never stop exploring; maybe explore less with time; or not!

• Regret is the opportunity loss for one step: difference of obtained reward and optimal
reward• Goal. Minimize total regret ~ maximize cumulative reward
Regret T = OPT reward @T − Planner reward @T
observed rewards so far for t=1,..,4: 3, 10, 5, 10
should have pulled the arm with reward 10 all along
regret: (10-3)+(10-10)+(10-5)+(10-10) = 12

[Sutton&Barto, 1998]
25

R2

OVERVIEW: EXPLORATION, EXPLOITATION,
AND REGRET• Explore at time t: select a random arm.

estimated action-values: 2
ak

10
ai

…

5

7

a2

a1

• Exploit at time t: select the arm with the best estimated value so far (greedy).
• ε-greedy. At each step explore with prob. ε (exploration rate) and exploit with prob. (1-ε)• Linear regret• Assume perfect estimates. We potentially pull imperfect arm with ε prob., resulting
in expected ε.T regret.
• Decaying exploration rate. More exploration at the beginning.
• E.g., if new to a city, extensively explore restaurants at the beginning, explore less later.
• Regret O(T2/3log T1/3)• Can be brought down by Upper Confidence Bound (UCB) to O(T1/2log T1/2)[Sutton&Barto, 1998]

26

MAB FOR UNKNOWN DISTRIBUTION DT
?

?

…

?

?

• Each source is an arm.
• Apply ε-greedy.
• With each sample from a source, we learn about the distribution of groups inthat source.
• Greedy strategy at time t.
ε-greedytargetdataset• First, select a hard-to-find group (rare group,totalgroup with large count requirement)
decaying ε-greedy
ratio(hard to findregretgroup): cheap source with potentially a lot• Greedy action. argmax𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠of samples of hard-to-find-group. source costtimestamp• Regret is a proxy for cost overhead.
3• Regret.
DT1with ε-greedy strategy with exploration rate ln 𝑡𝑡 /𝑡𝑡 at time t has regret of2
𝑂𝑂 t 3 log t 3 -- for sources with equal costs and strategy ratiocoll.
Data Distribution Tailoring Revisited: Cost-Efficient Integration of Representative Data.
J. Chang, B. Cui, F. Nargesian, A. Asudeh. H. V. Jagadish, VLDBJ, 2024.

27

PRACTICAL STRATEGY• Explore-then-Exploit• Crudely approximate budget T ≈ ∑ group_count_requirements• Randomly sample sources for ⍺T iterations• Performing all explorations at the beginning allows sampling to be done inbatches and in parallel!
• Be greedy in the rest of time steps.

28

EVALUATION: KNOWN AND UNKNOWNDISTRIBUTIONS
Known/Unknown DT on Flights dataset
strategy for known DT• ε-greedy outperforms random sampling and is incompetition with strategy for. Known distribution.
29

PLUTUS: UNDERSTANDING DT FOR ML• DT is available in Apache SystemDS (open-source SystemML from IBM: declarative
ML system on Spark)

Understanding Distribution Tailoring for Machine Learning.
J. Chang, C. Dionysio, F. Nargesian, M. Boehm, SIGMOD, 2024.

30

KNOWN DISTRIBUTIONS:BINARY GROUPS AND EQUI-COST• Given. The ratio of each group in each source. Same cost for all sources.
• Algorithm. At each iteration until all requirements are satisfied:• From unsatisfied groups, pick a group to prioritize.
• For that group pick the cheapest sources for acquiring samplesof that group.
• Sample from that source; update target dataset;
update remaining group requirements.

Gi

G5

G4

G3

…

G2

G1

• Cheapest source for a group: source that has the highest ratio of that group• Group to prioritize/sample for: group that is minority in its best source

Tailoring Data Source Distributions for Fairness-aware Data Integration. F. Nargesian, A. Asudeh, H. V. Jagadish, VLDB, 2021.

31

EQUI-COST BINARY DT:SAMPLE FOR MINORITY GROUP

cost=1S1 20% of G1 and 80% of G2

cost=1
S2

sample from S1 until
got one tuple of G1

5% of G1 and 95% of G2• Requirement. Collect at least one tuple of each group.
• Expected cost of getting one sample of G1 from S1 is 100/20=5
and from S2 is 100/5=20.

• Best source for getting G1 is S1. Similarly, best source for G2 is S2.

No need to separately
sample for G2, req.
satisfiedsample from S2 until
got one tuple of G2• G1 is minority in its best source (S1 has 20% of G1, S2 only has 95%
of G2) → Pick G1• Piggybacking: as we are sampling for G1, we can fulfill the
Need to sample
count requirements of G2 with no cost.
another source to get G1• Proof by contradiction.
32

OUTLOOK

Query Type• Open Data for AI• Open Data for Users• Data Systems for Open Data Science

keyword-style

Data Lake Organization
Distribution Tailoring

distribution requirement
column/table

Joinable Dataset Discovery
Unionable Dataset Discovery
full dataset

samples

metadata

Access Level to Data Lake
33

OPEN DATA AND AI• Sample discovery• Discovering novel samples by unionable dataset discovery [NZPM, VLDB’18]• Feature discovery• Pushing down feature selection measures into join discovery• More interesting (and rare) relationships: causal dataset discovery• LLMs and dataset discovery• Dataset understanding and training data generation• Dataset discovery for LLMs

• Semantic/query-based nearest neighbor search indexes for vector DBs

34

CAUSAL DATASET DISCOVERY• Consider tables Q and T. Candidate columns 𝑋𝑋∈Q and 𝑌𝑌∈T have a correlation link overQ ⋈K=K’ T, if their correlation after the join is higher than a threshold 𝜃𝜃.
• A correlation link can potentially be• X causes Y over join Q ⋈K=K’ T• Y causes X over join Q ⋈K=K’ T• No causal relation exists between X and Y

correlation/causation• Problem. Given a query table Q and a data lake of tables L, find all tables C∈L such that
Q and C have at least one causal link over their join.
• Challenges. Sparsity of causal relation and limited training data for fine-tuning• Results.
• Role prompting + CoT + Socratic prompting + fine tuning performs the best.
• LLMs have potential to learn and generalize causality.
Causal Dataset Discovery with Large Language Models. J. Liu, S. Sun, F. Nargesian HILDA@SIGMOD, 2024.

35

OPEN DATA AND USERS• Metadata, search, query writing• Metadata standardization and taxonomy induction in domains such as social sciences• User interfaces for search• Constructing abstract structures for navigation and exploration [NZGPM, SIGMOD’20&TKDE’24]• Assisting users with debugging results and consequently their own information needs
Health• Dealing with heterogenous data by creating abstractions over data
Water

• Discovery with private queries on openFood
data
Resilience
Food Safety
Food Production, …
Energy…
Climate36

ACKNOWLEDGEMENT• Abolfazl Asudeh (UIC)• Leon Bornemann (HPI, PhD student)• Nikolaus Augsten (U. Salzburg)• Jiwon Chang (UR, PhD student)• Matthias Boehm (TU Berlin)• Tianji Cong (U. Michigan, PhD student)• H. V. Jagadish (U. Michigan)• Yurong Liu (UR, undergrad)• Renée J. Miller (NEU)• Pranay Mundra (UR, MSc.)• Felix Naumann (HPI)• Aidan Sciortino (UR, undergrad)• Ken PU (UOIT)• Zhengbin Tao (UR, PhD student)• Divesh Srivastava (AT&T)• Draco Xu (UR, undergrad)• Eric Zhu (MSR)• Mengqi Zhang (UR, PhD student)• Jianhao Zhang (UR, MSc.)

Code and data: github.com/DataIntelligenceCrew
37

THANKS.

38

41