Matrix of articles and authors from large JSON dataset

Question

Given the following JSON data containing 4 articles by 4 different authors:

const data = {
  "DataSet": {
    "Article": [
      {
        "Title": 'A',
        "AuthorList": {
          "Author": [{
            "FirstName": "Al",
            "LastName": "Ab",
            "Initials": "A"
          }, {
            "FirstName": "Bi",
            "LastName": "By",
            "Initials": "B"
          }] // Author
        } // AuthorList
      }, // Article
      {
        "Title": 'B',
        "AuthorList": {
          "Author": [{
            "FirstName": "Bi",
            "LastName": "By",
            "Initials": "B"
          }, {
            "FirstName": "Ch",
            "LastName": "Ch",
            "Initials": "C"
          }] // Author
        } // AuthorList
      }, // Article
      {
        "Title": 'C',
        "AuthorList": {
          "Author": [{
            "FirstName": "Ch",
            "LastName": "Ch",
            "Initials": "C"
          }, {
            "FirstName": "Al",
            "LastName": "Ab",
            "Initials": "A"
          }] // Author
        } // AuthorList
      }, // Article
      {
        "Title": 'D',
        "AuthorList": {
          "Author": [{
            "FirstName": "Da",
            "LastName": "Do",
            "Initials": "D"
          }, {
            "FirstName": "Bi",
            "LastName": "By",
            "Initials": "B"
          }] // Author
        } // AuthorList
      } // Article
    ] // Articles
  } // DataSet
};

I need to answer the following query:

Generate a matrix such that each cell (i, j) contains say N the number of articles authored by the author in column and co-authored by author in row. A paper may have more than 2 authors. It may be assumed that JSON is present as a file.

For above example the output would simply look like:

[2, 1, 1, 0]
[1, 3, 1, 1]
[1, 1, 2, 0]
[0, 1, 0, 1]

I have devised the solution below without thinking too much about design and performance:

const fullName = (author) => author["FirstName"] + ' ' + author["LastName"];

const authorMap = {};

const getArticles = (data) =>
  data["DataSet"]["Article"];

const getAuthors = (data) =>
  data["DataSet"]["Article"]
    .reduce((accum, article) => {     
      return [...accum, ...article["AuthorList"]["Author"].map((author) => {
        return fullName(author);
      })];
    }, []);

const matrix = [];

const initializeMatrix = () => {
  const N = Object.keys(authorMap).length;
  for (let i = 0; i < N; i++) {
    matrix[i] = Array(N).fill(0);
  }
};

console.clear();
let authors = getAuthors(data);
authors = Array.from(new Set(authors));
const articles = getArticles(data);
authors.forEach((author, idx) => {
  authorMap[author] = idx;
});

initializeMatrix();

articles.forEach((a) => {
  const authors = a["AuthorList"]["Author"];
  const authorIds = [];
  authors.forEach((author) => {
    authorIds.push(authorMap[fullName(author)]);
  });
  for (let i of authorIds) {
    for (let j of authorIds) {
      matrix[i][j] = matrix[i][j] + 1;
    }
  }
});

const printMatrix = (matrix) => {
  console.log('///////////////');
  for (let i = 0; i < matrix[0].length; i++) {
    console.log(matrix[i]);
  }
};

printMatrix(matrix);

Note:

There can be more than two authors per article.

Questions:

1. How to test the code?
2. What are the edge cases?
3. What if there are millions of articles? how to optimize the code?

Update 1:

The author name is FirstName + LastName

Update 2:

Adding unit tests.

'use strict';
/* eslint-env mocha */
const assert = require('assert');
const m = require('./');

it('should check for invalid data format', () => {
  assert.throws(() => m('fixtures/invalid.json'), /Invalid data/);
});

it('should return matrix of size 1 for single author', () => {
  const expected = {
    'A A': {
      'A A': 1,
    }
  };
  assert.deepEqual(m('fixtures/single-author.json'), expected);
});

it('should return matrix of size 2 for two authors', () => {
  const expected = {
    'A A': {
      'A A': 1,
      'B B': 1,
    },
    'B B': {
      'A A': 1,
      'B B': 1,
    }
  };
  assert.deepEqual(m('fixtures/two-authors.json'), expected);
});

Answer 1

You seem to be taking a very non-optimal approach from a performance standpoint, as you iterate over the data set unnecessarily trying to extra only derive certain pieces from it at a single time. I would think your goal would be to map the data into your data structure with a single iteration over the data.dataSet.article array, resulting in \$O(n)\$ operational complexity to read the data in).

Right now you do:

• Build an array of authors - \$O(n)\$, where n is number of articles
• Cast authors in to a Set - \$O(n)\$, where n is number of authors from previous step
• Get articles into array - \$O(n)\$, where n is # of articles. Note you gain nothing from mapping articles in place into there own array, but double memory usage and add this \$O(n)\$ performance hit. At a minimum you should kill this step.
• You map authors into an object with index position as value - \$O(n)\$ where n i # of authors. Another unnecessary step it seems, as you could iterate the authors set just as you have done here later if needed.
• You initialize the matrix to hold empty 0's - \$O(n)\$ where n is number of authors. This could have been done at any other point where you already iterated author set.
• You iterate the articles array - \$O(n)\$ where n is # of articles.

As you can see that is a lot of unnecessary complexity (and memory consumption).

You should be able to build your matrix in a single pass.

• Initialize your matrix as an empty object which will later be filled in .

The target data structure may look like this:

{
    'ch ch': {
        'ch ch':  *,
        'other author': *,
        ...
    },
    'other author': { ... },
    ...
}

• iterate through data.dataSet.article. On each element populate counters on properties in proposed data structure above.
• populate all authors into a set for use in rendering display.

This all could be as simple as:

const matrix = {};
const authors = new Set();
const articleLen = data.dataSet.article.length;
for (let artIdx = 0; artIdx < articleLen; artIdx++) {
    const len = element[artIdx].authorList.length;
    for (let i = 0; i < len; i++) {
        let author = fullname(element[artIdx].authorList[i]);
        authors.add(author);
        for (let j = 0; j < len; j++) {
            let coauthor = fullname(element[artIdx].authorList[j]);
            matrix[coauthor][author] = (matrix[coauthor][author]++ || 0) + 1;
        }
    }
}

Note: I used for loops for performance optimization rather than array methods. You really could use either. If writing code for real-world system where I did not expect millions of rows and the performance micro-optimization was not necessary I would probably use array methods for cleaner code.

• Fill 0's in matrix on display (or as secondary process if you really need the data structure). You do this by iterating the author set in nested loop.

• This would result in complexity that is \$O(n)\$ (n = articles)for article iteration + \$O(m^2)\$ (m = authors) for matrix display. So, if # of articles are assumed to be >> # of authors, this would likely be a good approach.

Answer 2

I don't see the reasoning for building all the intermediate arrays of articles and authors and stuff. I'm also not sure whether to use a full matrix for the result matrix is the best option. Most likely this matrix would be a very sparse matrix, so to avoid large memory usage you could opt for data structures allowing for sparse matrixes (or possibly use a hashed array where the key is the (i, j) coordinates.

Here is a pseudo-code version for looping through the article set once, the author set once with a double for-loop based on author id's afterwards.

• For each article, article, do the following:

  • Reset currentAuthors list
  • Loop through the author's of the article, and for each author do:
    • Check if author is part of the authorList array.
    • If found keep the authorIndex, and if not found add and keep the new authorIndex
    • Push authorIndex to a sorted list, currentAuthors
  • for i = 0 to currentAuthors.size() - 1
    • for j = i + 1 to currentAuthors.size()
      • A: Only upper right matrix: Increase matrix(currentAuthors[i], currentAuthors[j]) with 1
      • B: To create full matrix: Increase matrix(currentAuthors[j], currentAuthors[i]) with 1

• Print out the final matrix...

This will using only A create the upper right part of the matrix, and if also including B it'll create the full matrix.

To avoid creating a full sparse matrix, you could opt for using a hash array, where the key is like currentAuthors[i]_currentAuthors[j]. When printing you could sort the keys, and print 0 for all non-existent keys, and the actual values for existing entries. The dimension of the full matrix are given by the number of authors in authorList.

The time complexity of this method should be \$O(n*m*log(m))\$, with n as number of articles, and m as a local number of authors for a given article. The space complexity should also be optimal, as you don't store the articles or any extra information besides the global list of authors, and intermediate list of author ids for the current article. I don't think you can do a lot better than this. (The space complexity is somewhat dependent on the storage of the potential sparse matrix)

Your questions

Testing your code

If you make this into a function, and have proper reset functions, it should be rather easy to make a function allowing for multiple input sets, and then match the output towards your expected result.

Depending on test methodology you could opt for making tests which tests that the author matrix is as expected, or just the result matrix. In other words, whether you also want to test the inner parts of your code or not.

The various test set should test for various aspects, like many articles with few authors, or few articles with many authors, or many articles with many authors, or many articles with few authors.

Edge cases

Typical edge cases are a few articles with a lot of authors, or many articles each with a unique author. The latter case would trigger the worst space consumption if not some technique for the sparse matrix issue.

A million articles

As this solution doesn't store the articles, the number of articles is somewhat irrelevant. The author list will increase, but that can't be helped.

If implementing a good handling related to the sparse matrix (and possibly only storing the upper right part), like the hash-keying, you can't reduce the space complexity either.

For exceptionally large cases of multiple authors, you could opt for using databases for the author id list and/or result matrix, but that seems like overkill in most cases.