Participating in ACM Sigmod 2013 EGN Team

ACM Sigmod Programming Contest is a programming contest launched 2013 , mainly focused on implementing a program used to match large documents indexed by the tool in runtime.

This was my first worldwide online contest and it was an exciting experience for me and for my colleagues with EGN Team.

Task Details

Our team should implement 4 major functions that will be called by a testing machine on a set of large documents on Kaust server StartQuery(), EndQuery(), MatchDocument(), and GetNextAvailRes().

• StartQuery() => adds a query to the set of active queries .
• EndQuery() => removes it from that set.
• MatchDocument() => matches a document with the current set of active queries and saves the result somewhere in the main memory, until it is requested by GetNextAvailRes()

Technical Details

Under the supervision and guidance of our Professor Mohamed Khalefa, we started implementing a trie used to index the documents and on addition of active queries using the trie to get the matched document.

Using only the trie was not enough to match against large documents in Realtime, so we made multi-threading.

To avoid forking new threads more than the number of virtual cores in the testing machine we wrote a thread pool class in C++ taking the number of threads when initializing and it will handle the pool of threads to keep them under the maximum number passed to the class.

Our team was able to get 17 position on the leaderboard.

Colleagues

• Muhammad Negm
• Mohamed Ghannam
• Mohamed Refaat

Twitter  facebook  LinkedIn