Degree Type

Thesis

Date of Award

2015

Degree Name

Master of Science

Department

Mathematics

First Advisor

Jennifer Newman

Abstract

Given data organized in a tabular form called a cross table, the multi-dimensional relationships in the data are represented by a directed acyclic graph called a formal concept lattice. For large sets of data, drawing the graph is not reasonable. We focus on quantitative characteristics of the lattice structure that lead to decreased computation time in the determination of nodes and edge sets on large lattices from big data.

This work addresses the problem of recovering the covering relations, of a concept lattice, given the set of nodes. We implement one existing algorithm and formally prove that it correctly computes the covering relations of a given concept lattice from its nodes. We also discuss methods for estimating the number of covering relations in a lattice and offer a conjecture for an upper bound for this number. We present experimental results to predict edge frequency distribution for a range of cross table densities. Finally we discuss some open problems.

Copyright Owner

Aaron Michael Rodriguez

Language

en

File Format

application/pdf

File Size

47 pages

Included in

Mathematics Commons

Share

COinS