Advanced Techniques for Orthogonal Skyline Counting Queries
Advanced techniques for orthogonal skyline counting queries discuss optimal planar solutions, dividing and conquering for topmost point identification, efficient vertical slab counting, succinct data structures for prefix sums and range maxima, upper bounds on degree and multi-slab queries, as well as lower bounds on skyline counting with a reduction approach.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Optimal Planar Orthogonal Skyline Counting Queries Gerth St lting Brodal and Kasper Green Larsen Aarhus University 14th Scandinavian Workshop on Algorithm Theory, Copenhagen, Denmark, July 3, 2014
n points k output not dominated = skyline point dominated by 4 points skyline count = 5 orthogonal query range Assumptions coordinates { 0, 1, ... , n-1 } Unit cost RAM with word size w = (log n)
Results Orthogonal range Skyline Query Space (words) Query Space (words) k lg n k (lglg n)2 n new NN12 new NN12 new DGKASK12 { { n lglg n k lg n k + lglg n (k + lglg n) n CLP11 ABR00 PT06 k lglg n + lg n/lglg n k lglg n k + lg n/lglg n k + lg n/lglg n n lg n n lgO(1)n Reporting n lg n n lg n/lglg n n lg n lg n DGKASK12 DGS13 new new n lg3n/lglg n n n lgO(1)n n lg n/lglg n lg n/lglg n JMS04 P07 lg n/lglg n lg n/lglg n (lg n/lglg n) Counting n lgO(1)n
Basic Geometry Divide and Conquer topmost point (x,y) y+1
Basic Counting Vertical Slab 2 2 2 3 topmost 0 12 4 skyline count = 4 - 2 + 1 1 3 rightmost topmost 0 3 1 2 rightmost 0 2 3 1 0 prefix sum = 8 3 Data Structure succinct prefix sum O(n) bits + succinct range maxima O(n) bits 2 2 0 3 0 2 1 1 0 1
Upper Bound degree lg n height lg n / lglg n Data Structure succinct fractional cascading on y O(n lg n) bits
Upper Bound Multi-slab degree lg n Block Btop right 1 4 top 2 lgO( )n points right 5 top 3 Bbottom + tabulation ( blocks have o(lg n) bit signatures ) 3 5 1 4 2 lg2 n multi-slab structures using lglg n bits per block ( succinct prefix sum, range maxima ) + single slab queries ( succinct prefix sum )
Upper Bound Summary + succinct stuff ... O(lg n / lglg n) orthogonal skyline counting Space O(n) words
Lower Bound Skyline Counting Reduction Reachability in the Butterfly Graph Skyline Counting [- , x] [- , y] Word size lgO(1)n bits, space O(n lgO(1)n) (lg n / lglg n) query s 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 Butterfly Graph 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 t
s 000 001 010 011 100 101 110 111 Butterfly Graph dashed edges are deleted s-t paths are unique a 000 001 010 011 100 101 110 111 b 000 001 010 011 100 101 110 111 c 000 001 010 011 100 101 110 111 t 111 c 110 101 a 100 rev(t) 011 b 010 2-sided Skyline Range Counting depth of edge aspect ratio of rectangle edge = 1 point, deleted edge = 2 points 001 000 000 001 s 010 011 100 101 110 111
Results Orthogonal range Skyline Query Space (words) Query Space (words) k lg n k (lglg n)2 n new NN12 new NN12 new DGKASK12 { { n lglg n k lg n k + lglg n (k + lglg n) n CLP11 ABR00 PT06 k lglg n + lg n/lglg n k lglg n k + lg n/lglg n k + lg n/lglg n n lg n n lgO(1)n Reporting n lg n n lg n/lglg n n lg n lg n DGKASK12 DGS13 new new n lg3n/lglg n n n lgO(1)n n lg n/lglg n lg n/lglg n JMS04 P07 lg n/lglg n lg n/lglg n (lg n/lglg n) Counting n lgO(1)n
