BigDataIntegration Flashcards
1
Q
What is the main objective of Big Data integration?
A
To make heterogeneous data from different sources accessible and usable by combining traditional data integration principles with Big Data characteristics (4 Vs)
2
Q
What are the 4 Vs that characterize Big Data?
A
Volume Velocity Variety and Value
3
Q
What is an example of Big Data integration in company mergers?
A
Customer database integration dealing with differences in schemas entity duplication and data inconsistencies
4
Q
Why are traditional ETL approaches less effective for Big Data?
A
1) Schema rigidity limits flexibility 2) Duplicate detection is computationally expensive 3) Choosing a single true representation may not work for all applications
5
Q
What is the main difference between ETL and ELT?
A
ELT loads data before transformation while ETL transforms data before loading making it better suited for big data due to cheaper storage and on-demand analysis
6
Q
What is a Data Lake?
A
A large centralized repository allowing storage of raw structured semi-structured and unstructured data from various sources in one place
7
Q
What are the three main challenges in Big Data Integration?
A
1) Data Discovery 2) Schema Alignment 3) Entity Resolution
8
Q
What is Schema Alignment?
A
The process of aligning schemas from different data sources to enable integration
9
Q
What is Entity Resolution (ER)?
A
The process of identifying and merging records from different data sources that refer to the same real-world entity
10
Q
What are probabilistic mediated schemas?
A
Schemas that use weighted attribute correspondences to model uncertainty about the semantics of attributes in the sources
11
Q
What are the two main types of similarity used in schema alignment?
A
1) Metadata similarity (attribute names documentation table captions) 2) Instance similarity (attribute cell values entities columns)
12
Q
What are the four main phases of Entity Resolution?
A
1) Candidate Generation 2) Matching 3) Clustering 4) Merging
13
Q
What is Candidate Generation in ER?
A
The phase where pairs of records that might refer to the same entity are identified based on attribute similarity or group membership
14
Q
What is the Matching phase in ER?
A
The phase where a matching function evaluates the probability that candidate record pairs refer to the same entity
15
Q
What is the purpose of the Clustering phase in ER?
A
To group matching records into clusters where each cluster represents a single real-world entity
16
Q
What is the Merging phase in ER?
A
The phase where a single record representing the entity is created from each cluster by choosing a standard format and resolving conflicts
17
Q
What are the three main challenges in Entity Resolution?
A
1) Real-world Ambiguity 2) Data Errors 3) Scalability
18
Q
What is Blocking in ER?
A
A technique to reduce comparisons by grouping similar records into blocks and only comparing within each block
19
Q
What are the three main types of text similarity measures?
A
1) Character-based 2) Token-based 3) Vector-based
20
Q
What is Hamming distance?
A
Number of positions in which two strings of equal length differ
21
Q
What is Levenshtein distance?
A
Minimum number of character insertions deletions and replacements needed to transform one string into another
22
Q
What is Jaccard similarity?
A
The size of the intersection divided by the size of the union of two sets
23
Q
What is Jaccard containment?
A
The size of the intersection divided by the minimum size of the two sets
24
Q
What are the three subtasks of Entity Resolution?
A
1) Clean-Clean ER (Record Linkage) 2) Dirty-Clean ER 3) Dirty-Dirty ER
25
What is Clean-Clean ER?
Finding matches between two clean collections (collections free of duplicates)
26
What is Dirty-Clean ER?
Finding duplicates within a single dirty collection
27
What is Dirty-Dirty ER?
Finding matches between more than two collections (Deduplication)
28
What is Schema-agnostic Token Blocking?
A blocking technique that uses every token in every attribute value as a blocking key regardless of the attribute
29
What is the main advantage of Schema-agnostic Token Blocking?
It is very robust and has high precision as it's unlikely to miss a match and doesn't require schema knowledge
30
What is Meta-blocking?
A technique that uses block-entity relationships to identify and maintain the most promising comparisons reducing superfluous comparisons
31
What is ARCS weighting scheme in Meta-blocking?
Aggregate Reciprocal Comparisons Scheme - sums the reciprocal of the number of comparisons from each shared block
32
What is CBS weighting scheme in Meta-blocking?
Common Blocks Scheme - uses the number of blocks shared between profiles
33
What is JS weighting scheme in Meta-blocking?
Jaccard Scheme - uses the Jaccard similarity of the blocks shared between profiles
34
What are the four pruning methods in Meta-blocking?
1) Weighted Edge Pruning 2) Cardinality Edge Pruning 3) Weighted Node Pruning 4) Cardinality Node Pruning
35
What is Block Filtering?
A technique that retains each entity in a percentage of its smallest blocks since larger blocks are less likely to contain unique duplicates
36
What is Block Purging?
A technique that removes oversized blocks by setting an upper limit on block cardinality
37
What is Pay-as-you-go ER?
A strategy that focuses on generating candidate pairs in a specific order to maximize progressive recall with limited resources
38
What are the three levels of ordering in Pay-as-you-go ER?
1) Comparisons level 2) Block level 3) Entity level
39
What is Progressive Sorted Neighborhood (PSN)?
A method that sorts records by a key and uses a sliding window to compare nearby records assuming higher matching probability for proximity
40
What is LS-PSN?
Local Schema-agnostic PSN - uses similarity principle and token sorting without schema knowledge
41
What is GS-PSN?
Global Schema-agnostic PSN - defines global execution order for all pairs within a predefined range of window sizes
42
What is PBS in Progressive ER?
Progressive Block Scheduling - orders blocks by weight assuming smaller blocks are more informative
43
What are the two main types of related tables?
1) Unionable tables 2) Joinable tables
44
What are Unionable tables?
Tables that are entity complements sharing the same schema but different records
45
What are Joinable tables?
Tables that are schema complements sharing some key attributes but having different additional attributes
46
What is Similarity Join?
An operation that retrieves all pairs of records whose similarity exceeds a threshold
47
What are the three main filters used in Similarity Joins?
1) Prefix filter 2) Length filter 3) Positional filter
48
What is the Prefix filter?
Filter that requires matching records to share at least one token in their prefixes
49
What is shingling in document similarity?
Representing documents as sets of k-length substrings found within them
50
What is minhashing?
A technique that compresses sets into small signatures while preserving their Jaccard similarity
51
What is the connection between minhashing and Jaccard similarity?
The probability that the minhash function produces the same value for two sets equals their Jaccard similarity
52
What is Locality-Sensitive Hashing (LSH)?
A technique to reduce comparisons by hashing similar items to the same buckets
53
What is the banding technique in LSH?
Dividing the signature matrix into bands and hashing each band to find candidate pairs that match in at least one band
54
What is the basic LSH method for cosine similarity?
Using random projections where the probability of hash collision is proportional to the cosine of the angle between vectors
55
What are examples of clean-clean entity resolution?
Finding matches between two databases without duplicates like merging customer records from two different companies
56
What is a real-world example of dirty-dirty entity resolution?
Finding matches across multiple product catalogs that may each contain duplicates
57
What is a use case for schema complement tables?
Finding tables that contain additional attributes for existing entities like adding demographic data to customer records
58
What are common real-world applications of similarity joins?
Record linkage data cleaning and deduplication tasks
59
How does shingling help with document similarity?
It creates a set-based representation that captures local text structure and enables set similarity comparisons
60
Why is minhashing more efficient than direct set comparison?
It creates small fixed-size signatures that preserve similarity while reducing storage and comparison costs
61
What problem does LSH solve in similarity search?
It reduces the number of necessary comparisons by only comparing items likely to be similar based on their hash values
62
What are key considerations in choosing shingle size?
Balance between discriminative power and computational cost larger k gives more precision but requires more processing
63
What makes Meta-blocking more accurate than basic blocking?
It uses block relationships and weights to identify promising comparisons rather than just shared blocking keys
64
How does Pay-as-you-go ER handle resource constraints?
It prioritizes likely matches to identify as many matches as possible early with limited time/computation
65
What is the main trade-off in choosing LSH bands and rows?
More bands increase recall but also false positives while more rows per band increase precision but may miss matches
66
How do you choose blocking keys for traditional blocking?
Select attributes that are unlikely to contain errors and have good discriminative power
67
Why might you choose GS-PSN over LS-PSN?
GS-PSN avoids repeated pair comparisons and has better matching probability estimation
68
What advantage does Block Filtering offer over Block Purging?
It retains some utility from larger blocks while still reducing comparisons rather than completely removing them
69
Why use multiple minhash functions rather than just one?
Multiple functions provide better similarity estimation by sampling more permutations
70
How does the prefix filter guarantee completeness?
If records don't share any prefix tokens they cannot meet the similarity threshold
71
What role does transitivity play in entity clustering?
It helps group related pairs into clusters assuming if A=B and B=C then A=C
72
Why might you choose supervised over unsupervised meta-blocking?
Supervised methods can learn better weighting schemes if labeled training data is available
73
What makes schema-agnostic methods valuable for big data?
They don't require schema alignment or domain knowledge making them more flexible and scalable
74
How do you handle multi-valued attributes in similarity computation?
Use set-based similarity measures like Jaccard similarity rather than exact matching
75
What is the purpose of the triangle inequality in similarity metrics?
It ensures consistent distance relationships between multiple items
76
Why are character-based similarities good for catching typos?
They can detect small character-level differences that indicate typing errors
77
How do token-based similarities handle word rearrangement?
They treat text as bags of words so word order doesn't affect similarity
78
What role do thresholds play in similarity matching?
They determine the minimum similarity required to consider items as matching
79
Why use progressive techniques for entity resolution?
They allow useful partial results with limited resources by prioritizing likely matches
80
What makes blocking key selection challenging?
Keys must balance discriminative power error tolerance and computational efficiency
81
How do you evaluate the quality of blocking results?
Measure pair completeness (recall) and pair quality (precision) of the generated blocks
82
What is the relationship between block size and matching probability?
Smaller blocks generally have higher matching probability but may miss some matches
83
What factors affect the choice of similarity measure?
Data type expected error patterns and computational requirements
84
Why might you combine multiple similarity measures?
Different measures catch different types of variations and errors
85
What makes some blocking methods more scalable than others?
Efficient indexing structures and filtering techniques that reduce necessary comparisons
86
How do you handle evolving data in entity resolution?
Use incremental techniques that can process updates without full recomputation
87
What role does data cleaning play in entity resolution?
It reduces noise and standardizes formats improving matching accuracy
88
Why is entity resolution an ongoing challenge?
Data volumes variety and velocity keep increasing while quality requirements remain high
89
What makes schema alignment particularly challenging for big data?
Scale heterogeneity and lack of schema information in many data sources
90
How do probabilistic approaches help with uncertainty?
They model and propagate uncertainty rather than forcing early decisions
91
What role does human feedback play in entity resolution?
It helps validate matches train models and resolve difficult cases
92
How do you balance precision and recall in blocking?
Adjust blocking key selection and filtering parameters based on application needs
93
What makes some entity resolution tasks harder than others?
Factors like data quality schema heterogeneity and scale affect difficulty
94
How do you handle missing values in similarity computation?
Use similarity measures that can handle missing data or impute values
95
What role does domain knowledge play in entity resolution?
It helps select features blocking keys and similarity measures
96
What makes incremental entity resolution challenging?
New data may affect existing clusters requiring efficient updates
97
How do you handle temporal aspects in entity resolution?
Consider time-stamped values and evolution of entities over time
98
What role does data profiling play in entity resolution?
It helps understand data characteristics to choose appropriate methods
99
How do you handle multi-source entity resolution?
Consider source reliability and potential conflicts between sources
100
What makes real-time entity resolution challenging?
Need for quick decisions with limited information and resources
101
How do you evaluate entity resolution results?
Measure precision recall and clustering quality against ground truth
102
What role does scalability play in choosing ER methods?
Methods must handle data volume while maintaining acceptable accuracy
103
How do you handle privacy in entity resolution?
Use privacy-preserving techniques while maintaining matching ability
104
What makes some entity pairs harder to resolve than others?
Factors like data quality conflicting information and ambiguity
105
How do you handle hierarchical relationships in ER?
Consider entity relationships and dependencies during matching
106
What role does data standardization play in ER?
It reduces superficial differences improving matching accuracy
107
How do you handle multi-lingual entity resolution?
Use language-independent features or cross-lingual matching techniques
108
What makes schema evolution challenging for ER?
Changes in data structure require updating matching rules and models
109
How do you maintain entity resolution results over time?
Track changes updates and maintain cluster consistency
110
What role does data governance play in entity resolution?
It ensures consistent policies for matching and merging entities
111
How do you handle entity resolution in distributed systems?
Use distributed algorithms and maintain consistency across nodes
112
What makes reference data important for entity resolution?
It provides authoritative information for matching and validation
113
How do you handle streaming entity resolution?
Process updates incrementally with limited historical information
114
What role does metadata play in entity resolution?
It provides context and constraints for matching decisions
115
How do you handle uncertainty in entity resolution?
Model and propagate uncertainty through the resolution process
116
What makes entity resolution important for data quality?
It identifies and resolves duplicate and conflicting entity information
117
How do you handle scale in entity resolution?
Use efficient indexing blocking and filtering techniques
118
What role does automation play in entity resolution?
It reduces manual effort while maintaining acceptable accuracy
119
How do you handle complex matching rules in ER?
Break down into simpler components and combine results
120
What makes online entity resolution different from batch?
Need for immediate decisions with partial information
121
How do you handle data quality issues in ER?
Use robust matching methods and clean data when possible
122
What role does monitoring play in entity resolution?
Track quality and performance to maintain effectiveness
123
How do you handle updates to resolved entities?
Efficiently propagate changes while maintaining consistency
124
What makes some data sources better for ER than others?
Factors like completeness accuracy and structure
125
How do you handle schema mapping in entity resolution?
Align schemas while handling uncertainty and variations
126
What role does testing play in entity resolution?
Validate matching rules and measure effectiveness
127
How do you handle large-scale entity resolution?
Use distributed processing and efficient algorithms
128
What makes incremental updates challenging for ER?
Need to maintain consistency while processing changes
129
How do you handle entity resolution across domains?
Consider domain-specific features and matching rules
130
What role does documentation play in entity resolution?
Track decisions rules and processes for maintenance
131
How do you handle entity resolution in real time?
Use efficient methods that can make quick decisions
132
What makes data preparation important for ER?
Good preparation improves matching accuracy
133
How do you handle entity resolution failure cases?
Analyze failures to improve matching rules
134
What role does optimization play in entity resolution?
Improve efficiency while maintaining accuracy
135
What is JOSIE and what problem does it solve?
JOSIE (JOining Search using Intersection Estimation) is an algorithm that finds the k sets in a data lake with the largest intersections with a query set, where sets represent columns in tables
136
What basic data structures does JOSIE use to handle large sets?
1. Inverted index (containing posting lists) 2. Dictionary (storing tokens, frequencies, and pointers to posting lists)
137
What information does each posting list entry contain in JOSIE?
A tuple containing: (SetID, Position, SetSize)
138
What is the main limitation of the MergeList algorithm in JOSIE?
Its read time is linear to the number of matched tokens, making it inefficient for sets with thousands or millions of tokens
139
How does Prefix Filter optimize JOSIE's performance?
It reduces the number of posting lists that need to be read by using the k-th candidate's intersection size as a threshold, making a prefix of |Q| − |Q ∩ Xk| + 1 lists
140
What two requirements must be met to use Position filter in JOSIE?
1. Global ordering for all tokens (e.g., lexicographic, length) 2. Posting lists must contain token positions and set sizes
141
What are the two benefits of using Position filter in JOSIE?
1. Prunes candidates whose intersection sizes are less than threshold before reading them 2. Reduces time of reading individual candidates by only reading from first matching position
142
How does the Position filter calculate the upper bound of intersection size?
Using the equation: |Q ∩ X| ≤ |Q ∩ X|ub = 1 + min, where jX,0 is the position of the first matching token
143
What is the key difference between ProbeSet and MergeList in JOSIE?
ProbeSet probes candidates as it encounters them and can stop early, while MergeList reads all posting lists completely
144
When does JOSIE stop reading new posting lists?
When the number of lists read equals |Q| − |Q ∩ Xk| + 1, where Xk is the k-th candidate
145
What is MATE in contrast to JOSIE?
A system for detecting top k n-ary joinable tables from large table corpora, using XASH hash function and super keys
146
What makes XASH unique compared to other hash functions?
It encodes distinctive properties: less frequent characters, their positions, and value length, rather than relying on uniform distribution
