Browsing by Author "Shi, Qingmin"
Now showing 1 - 9 of 9
Results Per Page
Sort Options
Item Efficient Isosurface Extraction for Large Scale Time-Varying Data Using the Persistent Hyperoctree (PHOT)(2006-01-13T20:31:09Z) Shi, Qingmin; JaJa, JosephWe introduce the Persistent HyperOcTree (PHOT) to handle the 4D isocontouring problem for large scale time-varying data sets. This novel data structure is provably space efficient and optimal in retrieving active cells. More importantly, the set of active cells for any possible isovalue are already organized in a Compact Hyperoctree, which enables very efficient slicing of the isocontour along spatial and temporal dimensions. Experimental results based on the very large Richtmyer-Meshkov instability data set demonstrate the effectiveness of our approach. This technique can also be used for other isosurfacing schemes such as view-dependent isosurfacing and ray-tracing, which will benefit from the inherent hierarchical structure associated with the active cells.Item Efficient Techniques for Range Search Queries on Earth Science Data(2002-02-25) Shi, Qingmin; JaJa, Joseph F.Also UMIACS-TR-2002-19Item Fast Algorithms for 3-D Dominance Reporting and Counting(2003-02-05) Shi, Qingmin; JaJa, JosephWe present in this paper fast algorithms for the 3-D dominance reporting and counting problems, and generalize the results to the d-dimensional case. Our 3-D dominance reporting algorithm achieves $O(\log n/\log\log n +f)$ query time using $O(n\log^{\epsilon}n)$ space, where $f$ is the number of points satisfying the query and $\epsilon>0$ is an arbitrary small constant. For the 3-D dominance counting problem (which is equivalent to the 3-D range counting problem), our algorithm runs in $O((\log n/\log\log n)^2)$ time using $O(nlog^{1+\epsilon}n/\log\log n)$ space. Also UMIACS-TR-2003-06Item Fast Fractional Cascading and Its Applications(2003-08-01) Shi, Qingmin; JaJa, JosephUsing the notions of Q-heaps and fusion trees developed by Fredman and Willard, we develop a faster version of the fractional cascading technique while maintaining the linear space structure. The new version enables sublogarithmic iterative search in the case when we have a search tree and the degree of each node is bounded by $O(\log^{\epsilon}n)$, for some constant $\epsilon >0$, where $n$ is the total size of all the lists stored in the tree. The fast fractional cascading technique is used in combination with other techniques to derive sublogarithmic time algorithms for the geometric retrieval problems: orthogonal segment intersection and rectangular point enclosure. The new algorithms use $O(n)$ space and achieve a query time of $O(\log n/\log\log n + f)$, where $f$ is the number of objects satisfying the query. All our algorithms assume the version of the RAM model used by Fredman and Willard. (UMIACS-TR-2003-71)Item A New Framework for Addressing Temporal Range Queries and Some Preliminary Results(2003-02-05) Shi, Qingmin; JaJa, JosephGiven a set of $n$ objects, each characterized by $d$ attributes specified at $m$ fixed time instances, we are interested in the problem of designing space efficient indexing structures such that arbitrary temporal range search queries can be handled efficiently. When $m=1$, our problem reduces to the $d$-dimensional orthogonal search problem. We establish efficient data structures to handle several classes of the general problem. Our results include a linear size data structure that enables a query time of $O( \log n\log m/\log\log n + f)$ for one-sided queries when $d=1$, where $f$ is the number of objects satisfying the query. A similar result is shown for counting queries. We also show that the most general problem can results include a linear size data structure that enables a query time of $O( \log n\log m/\log\log n + f)$ for one-sided queries when $d=1$, where $f$ is the number of objects satisfying the query. A similar result is shown for counting queries. We also show that the most general problem can be solved with a polylogarithmic query time using nonlinear space data structures. Also UMIACS-TR-2003-08Item An O(n)-Space O(log n/log log n + f)-Query Time Algorithm for 3-D Dominance Reporting(2003-08-01) Shi, Qingmin; JaJa, JosephWe present a linear-space algorithm for handling the {\em three-dimensional dominance reporting problem}: given a set $S$ of $n$ three-dimensional points, design a data structure for $S$ so that the points in $S$ which dominate a given query point can be reported quickly. Under the variation of the RAM model introduced by Fredman and Willard~\cite{Fredman94}, our algorithm achieves $O(\log n/\log\log n+f)$ query time, where $f$ is the number of points reported. Extensions to higher dimensions are also reported. (UMIACS-TR-2003-77)Item Optimal and Near-Optimal Algorithms for Generalized Intersection Reporting on Pointer Machines(2003-11-25) Shi, Qingmin; JaJa, JosephWe develop efficient algorithms for a number of generalized intersection reporting problems, including orthogonal and general segment intersection, 2-D range searching, rectangular point enclosure, and rectangle intersection search. Our results for orthogonal and general segment intersection, 3-sided 2-D range searching, and rectangular pointer enclosure problems match the lower bounds for their corresponding standard versions under the pointer machine model. Our results for the remaining problems improve upon the best known previous algorithms. (UMIACS-TR-2003-110)Item Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Range Counting(2003-11-25) Shi, Qingmin; JaJa, Joseph; Mortensen, ChristianWe present linear-space sublogarithmic algorithms for handling the {\em three-dimensional dominance reporting problem} and the {\em two-dimensional range counting problem}. Under the RAM model as described in~[M.~L. Fredman and D.~E. Willard. ``Surpassing the information theoretic bound with fusion trees'', {\em Journal of Computer and System Sciences}, 47:424--436, 1993], our algorithms achieve $O(\log n/\log\log n+f)$ query time for 3-D dominance reporting, where $f$ is the number of points reported, and $O(\log n/\log\log n)$ query time for 2-D range counting case. We extend these results to any constant dimension $d$ achieving $O(n(\log n/\log\log n)^{d-3})$-space and $O((\log n/\log\log )^{d-2}+f)$-query time for the reporting case and $O(n(\log n/\log\log n)^{d-2})$-space and $O((\log n/\log\log n)^{d-1})$ query time for the counting case. (UMIACS-TR-2003-101)Item Techniques for Indexing and Querying Temporal Observations for a Collection of Objects(2003-08-01) Shi, Qingmin; JaJa, JosephWe consider the problem of dynamically indexing temporal observations about a collection of objects, each observation consisting of a key identifying the object, a list of attribute values and a timestamp indicating the time at which these values were recorded. We make no assumptions about the rates at which these observations are collected, nor do we assume that the various objects have about the same number of observations. We develop indexing structures that are almost linear in the total number of observations available at any given time instant, and that support dynamic insertions in polylogarithmic time. Moreover, these structures allow the quick handling of queries to identify objects whose attribute values fall within a certain range at every time instance of a specified time interval. Provably good bounds are established. (UMIACS-TR-2003-72)