For analyzing token frequencies, I have implemented two different designs.Design A: For different data sources, create specific data readers that convert your data into Records. For frequency analysis, operate on the abstraction of RecordAdvantage:

• Easy to maintain, implement once and for all
• Reduces complexity of the project

Disadvantage:

• Poor performance
• High memory requirement, since you are doing analysis record by record, instead of column by column, you need to keep frequency data for ALL columns at the same time

Design B: For each type of data source (database, character delimited file etc.) we implement a specific analyzer in addition to a data readerAdvantage:

• Better performance in some data sources since you are operating on a lower level of abstraction
• Possibility of doing analysis column by column, the way it is supposed to be

Disadvantage:

• Each data source needs a different analyzer, increases complexity
• Could be tiresome to implement

Performance difference becomes apparent in analyzing databases. Instead of loading our data into memory, processing it and writing it back, we can just ask MySQL to tell us token frequencies with a query, and store this information for later use. Below is the result for a data source of 5000 records (fileA_5000) consisting of 19 columns. Token frequency analysis of one column takes:Design B: 1843 millisecondsDesign A: 4035 millisecondsDesign A does not improve much even if we reduce column count to one. This could mean that execution time consists of mostly overhead from iterating over all records and numerous function calls it brings.Last word:Even though there is significant performance difference for database data, I wouldn’t argue passionately for design B. This decision depends on how many different data sources we are planning to support, their nature (possibility of performance gain or not) and whether execution time stays within reasonable limits in design A or not.

As many of you know, we are working on a patient matching module for OpenMRS that will allow users to identify records that belong to the same patient among different data sources.In the first part of SoC, I’ve completed adding weight scaling functionality to the existing record linkage framework.Matching records are determined by assigning a score to each possible record pair. Weight scaling improves the accuracy of patient matching because fields that match on a common value, for instance James for first name, will be scaled down, and they will contribute less to the overall score for the given pair.In order to introduce weight scaling, we first analyze data sources (could be database or character delimited file) that will be used in linkage for token frequencies. We store this data in a relational database and use it later during calculating scores for possible pairs. We have the ability to use different lookup tables for token frequencies (top N most/least frequent tokens, top N% most/least frequent tokens and frequencies above/below N).There are other possible improvements for scoring, therefore we’re currently working on refactoring the framework to make it easier to adjust matching scores.

I’d like to read a text file and store the frequency of each word in it into a database. Memory is fast, database is slow. At the two extremes, we have:1) I don’t use any memory, for each word I read, I query the database to learn it’s frequency, and update it in the database.Problem: Very Inefficient2) Everything is stored in the memory, I keep a hashtable in which I store frequencies of words. After reading the whole file, I write all entries to the database.Problem: Very fast, but I may have so many words that they won’t fit into memory.Solution:I keep part of the words in a hashtable, for those entries that are not in the hashtable, I query the database.SubProblem: How do I decide if I’ll put a word in the hashtable or not? I’d like to store the most frequent words in the hashtable so that I will minimize the number of queries to the database. But I don’t know frequencies of words in advance, they change as I read the file. My hashtable has to organize itself as I read the text file.Solution: If the next word I read is not in the hashtable, and is more frequent than the *least* frequent word in the hashtable, I put the new word into the table and remove the least frequent one. The reasoning is that if a word has high frequency, it is likely that I will see more of the same word.SubProblem: I need a way to efficiently determine the least frequent word in the hash table. Further more, after I replace the least frequent one, which word will be the least frequent one now? What about next round?Solution: Along with the hashtable, I also keep a data structure called PriorityQueue. If implemented using a heap, it provides insert, remove and findMin operations in O(logN) time.Here are some experimental results for analyzing one column of 10,000 records:

• Without a lookup table, only using database: 16 seconds
• With a lookup table of 250 records (covers 60% of data): 8 seconds
• With a lookup table of 500 records (covers 80% of data): 5 seconds

Any ideas or comments on this approach will be appreciated

Google was cool enough to send out Karl Fogel’s Producing Open Source Software book as a suprise gift to all Summer of Code ‘07 participants. I have already read that book at our local library after getting accepted, therefore I was hoping to receive another book, Open Sources 2.0: The Continuing Evolution Nevertheless, the book we received is more suitable in terms of the goals of this program, so there is nothing to complain :)Karl Fogel was one of the developers of Subversion, and a past Google employee. In his book, he shares his experience about different aspects of open-source software development, from setting up the technical infrastucture to licensing and copyright issues. This book is worth reading because it contains specific examples and good advice.Fogel mentions a developer named Greg Stein, who decided to set an example by reviewing every line of every single commit that went into the code repository and eventually started a tradition of code reviews among developers of Subversion project.As a young developer, code reviews would be a great way to get useful feedback and improve my coding abilities. Fogel argues that one could contribute as much to the project by reviewing others’ changes as by writing new code because bugs and non-optimal coding practices that would go unnoticed would be caught on the fly.I agree with him, and would love to receive some reviews after my first few commits