Gregory Todd Williams SPARQL BGP Optimization Presentation Joshua Taylor 3

Question is for the Presentation: Gregory Todd Williams SPARQL BGP Optimization Presentation
Question is asked by: Joshua Taylor
The Question is: The authors state in 1. INTRODUCTION that "We focus on the evaluation of the presented optimization techniques without comparing the figures with the performance of alternative implementations." What value then ought we to ascribe to the work the authors performed? If I were to start with an exponential-time algorithm, and invent an optimization that yields an polynomial-time algorithm, and it will seem impressive, but if someone else has recognized that the problem can be solved in linear or constant time, it would be somewhat suspicious if I was not "comparing the figures with the performance of 'alternative implementations'" (single/scare quotes added for emphasis).
Answer: The presented algorithm is applicable to other implementations, but the evaluation was only performed on ARQ. I believe similar results would be seen with other implementations. As for the exp-polynomial-linear issue, all implementations require similar query execution plans to join results for the BGP's triple patterns. As such, all implementations and algorithms likely share the same complexity class.

Answer	The presented algorithm is applicable to o … The presented algorithm is applicable to other implementations, but the evaluation was only performed on ARQ. I believe similar results would be seen with other implementations. As for the exp-polynomial-linear issue, all implementations require similar query execution plans to join results for the BGP's triple patterns. As such, all implementations and algorithms likely share the same complexity class. ms likely share the same complexity class.
Question asked	The authors state in 1. INTRODUCTION … The authors state in 1. INTRODUCTION that "We focus on the evaluation of the presented optimization techniques without comparing the figures with the performance of alternative implementations." What value then ought we to ascribe to the work the authors performed? If I were to start with an exponential-time algorithm, and invent an optimization that yields an polynomial-time algorithm, and it will seem impressive, but if someone else has recognized that the problem can be solved in linear or constant time, it would be somewhat suspicious if I was not "comparing the figures with the performance of 'alternative implementations'" (single/scare quotes added for emphasis). (single/scare quotes added for emphasis).
Question asked by	Joshua Taylor +
Question for the Presentation	Gregory Todd Williams SPARQL BGP Optimization Presentation +