Skip to content

Graph Matching

Copy this iframe to your website:

1
<iframe src="https://dmccreary.github.io/graph-algorithms/sims/matching/custom-curve-percent.html" width="100%" height="500px" scrolling="no"></iframe>

Run Matching Demo in Fullscreen

Description

Many people don't list matching problems as simply graph problems. Perhaps this is because people try to use spreadsheets to attack matching problems. However, as we will see, graphs are ideal at helping people optimize matching problems.

Types of Matching Problems

  1. Schema Matching - Occurs when importing new data into a database and mapping new data elements to existing elements. The schema matching problem is a key cost factor when building data warehouse systems.

  2. Resource Matching - Matching things like people to positions, students to mentors, or people to projects within constraints. For example, matching students with five preferences to 20 potential projects.

  3. Entity Resolution - Adding new records to an existing database where they must be linked to the correct record. Also known as Record Linkage or data matching.

How to Use

  1. Observe how curved lines connect matched elements
  2. Notice how the visualization shows relationships between source and target items
  3. Consider how this approach could visualize different matching scenarios

Sample p5.js Matching Examples

Vis.js Matching Examples

Lesson Plan

Learning Objectives

After completing this lesson, students will be able to:

  • Identify different types of matching problems (schema, resource, entity)
  • Explain how graphs can represent matching relationships
  • Understand the role of constraints in matching optimization
  • Visualize bipartite matching problems

Target Audience

  • Data engineers and software developers
  • Prerequisites: Basic understanding of graphs and data integration

Activities

  1. Exploration Activity: Identify which type of matching problem applies to a given scenario
  2. Guided Investigation: Compare spreadsheet-based matching to graph-based approaches
  3. Extension Activity: Design a matching visualization for student-project assignment

Assessment

  • What makes schema matching different from entity resolution?
  • Why are graphs well-suited for matching problems?
  • What constraints might exist in a student-mentor matching problem?

References