O2iJoin： An Efficient Index-Based Algorithm for Overlap Interval Join

Time intervals are often associated with tuples to represent their valid time in temporal relations, where overlap join is crucial for various kinds of queries. Many existing overlap join algorithms use indices based on tree structures such as quad-tree, B＋-tree and interval tree. These algorithms usually have high CPU cost since deep path traversals are unavoidable, which makes them not so competitive as data-partition or plane-sweep based algorithms. This paper proposes an efficient overlap join algorithm based on a new two-layer flat index named as Overlap Interval Inverted Index （i.e., O2i Index）. It uses an array to record the end points of intervals and approximates the nesting structures of intervals via two functions in the first layer, and the second layer uses inverted lists to trace all intervals satisfying the approximated nesting structures. With the help of the new index, the join algorithm only visits the must-be-scanned lists and skips all others. Analyses and experiments on both real and synthetic datasets show that the proposed algorithm is as competitive as the state-of-the-art algorithms.

Niche breadth and overlap of spotted deer and domestic cattle with swamp deer in tropical region of Nepal

Background:Knowledge about the niche overlap among wild species and domestic cattle is helpful to conserve and manage wildlife.We assessed the habitat niche breadth and overlap of sympatrically living spotted deer(Axis axis)and domestic cattle with swamp deer(Cervus duvaucelii)in Shuklaphanta National Park,Nepal during the dry season to explore the possibility of interspecific competition by studying the habitat use by these species.The assumption was made that the presence of pellets is proof of habitat used by species.Methods:Grids of 2 km×2 km have four subgrids,each with four sample plots,making a total of 16 plots(20 m×20 m)in each grid.The size of each sub-grid was 200 m×200 m and they were placed randomly inside the grid but at least 1 km apart from one another.The data was collected in a 96 plots in total.Levin’s niche breadth and Morisita’s overlap index were calculated to determine the niche breadth and the habitat overlap,respectively.Results:The Levin’s measure of niche breadth suggested that spotted deer had the highest acclimatization with an index value of 0.94,followed by domestic cattle at 0.50,and swamp deer at 0.33 in our study area.Thus,our findings supported the evidence that spotted deer are habitat generalists,whereas swamp deer are habitat specialists.The swamp deer had lower niche breadth and more overlap with domestic cattle.Conclusion:Our study showed the least niche breadth of swamp deer in comparison to spotted deer and domestic cattle.The domestic cattle had the highest and least niche overlap with spotted deer and swamp deer,respectively,in terms of habitat use.Our study suggests that domestic cattle grazing should be stopped,and grassland management should be carried out for the benefit of ungulates.Similar studies should be conducted,including different seasons and places,prior to appropriate habitat management.In addition,further studies are needed to quantify the extent of interspecific competition by incorporating more species.