Before revision:  All of our data structures are work-efficient to build in theory (all need O(n log n) work) and achieve a low parallel depth (poly-logarithmic for the multi-level tree structures, and O(n?) for sweepline algorithms) .
After revision:  All of our data structures are work-efficient to build in theory (all need O(n log n) work) and achieve a low parallel depth . The query time is almost linear to the output size .