Summarizing level-two topological relations in large spatial datasets

Summarizing topological relations is fundamental to many spatial applications including spatial query optimization. In this article, we present several novel techniques to effectively construct cell density based spatial histograms for range (window) summarizations restricted to the four most important level-two topological relations: contains, contained, overlap, and disjoint. We first present a novel framework to construct a multiscale Euler histogram in 2D space with the guarantee of the exact summarization results for aligned windows in constant time. To minimize the storage space in such a multiscale Euler histogram, an approximate algorithm with the approximate ratio 19/12 is presented, while the problem is shown NP-hard generally. To conform to a limited storage space where a multiscale histogram may be allowed to have only k Euler histograms, an effective algorithm is presented to construct multiscale histograms to achieve high accuracy in approximately summarizing aligned windows. Then, we present a new approximate algorithm to query an Euler histogram that cannot guarantee the exact answers; it runs in constant time. We also investigate the problem of nonaligned windows and the problem of effectively partitioning the data space to support nonaligned window queries. Finally, we extend our techniques to 3D space. Our extensive experiments against both synthetic and real world datasets demonstrate that the approximate multiscale histogram techniques may improve the accuracy of the existing techniques by several orders of magnitude while retaining the cost efficiency, and the exact multiscale histogram technique requires only a storage space linearly proportional to the number of cells for many popular real datasets.

Are echo techniques comparable for measurement of left ventricular dysynchrony? Comparison of real time 3D and tissue Doppler echocardiography in patients with ischaemic cardiomyopathy

Tissue Doppler (TD) assessment of dysynchrony (DYS) is established in evaluation for bi-ventricular pacing. Time to regional minimal volume by real-time 3D echo (3D) has been applied to DYS. 3D offers simultaneous assessment of all segments and may limit errors in localization of maximum delay due to off-axis images.We compared TD and 3D for assessment of DYS. 27 patients with ischaemic cardiomyopathy (aged 60±11 years, 85% male) underwent TD with generation of regional velocity curves. The interval between QRS onset and maximal systolic velocity (TTV) was measured in 6 basal and 6 mid-cavity segments. Onthe same day,3Dwas performed and data analysed offline with Q-Lab software (Philips, Andover, MA). Using 12 analogous regional time-volume curves time to minimal volume (T3D)was calculated. The standard deviation (S.D.) between segments in TTV and T3D was calculated as a measure ofDYS. In 7 patients itwas not possible to measureT3D due to poor images. In the remaining 20, LV diastolic volume, systolic volume and EF were 128±35 ml, 68±23 ml and 46±13%, respectively. Mean TTV was less than mean T3D (150±33ms versus 348±54 ms; p < 0.01). The intrapatient range was 20–210ms for TTV and 0–410ms for T3D. Of 9 patients (45%) with significantDYS (S.D. TTV > 32 ms), S.D. T3D was 69±37ms compared to 48±34ms in those without DYS (p = ns). In DYS patients there was concordance of the most delayed segment in 4 (44%) cases.Therefore, different techniques for assessing DYS are not directly comparable. Specific cut-offs for DYS are needed for each technique.