When I was in the graduate school of ASU, I worked with my Ph.D adviser, Dr. K. Selçuk Candan on data integration. One goal of my work was to develop efficient algorithms to capture conflicts in the data integration and provide effective schemes to resolve them. In our proposal^{1}, we represent the integration result as a loop-less weighted directed graph, thus a set of resolutions can be collected by searching for the top-k shortest paths.
Clearly finding the top-k shortest paths is a classical graph problem, and Yen’s algorithm provides the commonly-known solution. A recent and elegant discussion is proposed in ^{2}. However, I needed an implementation of this algorithm in C++ or Java. After searching Google, I could find neither. So I decided to do it myself. The initial implementation was in Java, used in our SIGMOD demo^{3}.
Afterwards, I created a Google project^{4} to share my implementation as I believe it is great if anyone can benefit from my work. Later on I added its C++ implementation per people’s requests. Actually I was surprised as so many people were interested in the project. Many of them did really apply the code to their work. More importantly, they gave me quite a few good feedbacks.
Up to this point, the project became not only my own work, but one involving many minds. I realized that the core of open source is sharing, but it should not be limited to the code only. It is more about the human minds, such as the developer experience and the user feedback. On the other hand, the sharing should be bi-directional, thus the roles of the user and the contributor are interchangeable. Additionally sharing can draw people together as a community, which in turn will definitely lead sharing up to a higher level. In the sense, the philosophy advocated by open source, I believe, can be summarized as open minds.
FICSR: feedback-based inconsistency resolution and query processing on misaligned data sources. SIGMOD Conference 2007 ↩
A new implementation of Yen’s ranking loopless paths algorithm ↩ ↩^{2}
Integrating and querying taxonomies with quest in the presence of conflicts. SIGMOD Conference 2007 ↩
GitHub Project: An implementation of K-Shortest Path Algorithm ↩