The Experts below are selected from a list of 6237 Experts worldwide ranked by ideXlab platform
Xuemin Lin - One of the best experts on this subject based on the ideXlab platform.
-
inverted linear Quadtree efficient top k spatial keyword search
IEEE Transactions on Knowledge and Data Engineering, 2016Co-Authors: Chengyuan Zhang, Ying Zhang, Wenjie Zhang, Xuemin LinAbstract:With advances in geo-positioning technologies and geo-location services, there are a rapidly growing amount of spatio-textual objects collected in many applications such as location based services and social networks, in which an object is described by its spatial location and a set of keywords (terms). Consequently, the study of spatial keyword search which explores both location and textual description of the objects has attracted great attention from the commercial organizations and research communities. In the paper, we study two fundamental problems in the spatial keyword queries: top $k$ spatial keyword search (TOPK-SK), and batch top $k$ spatial keyword search (BTOPK-SK). Given a set of spatio-textual objects, a query location and a set of query keywords, the TOPK-SK retrieves the closest $k$ objects each of which contains all keywords in the query. BTOPK-SK is the batch processing of sets of TOPK-SK queries. Based on the inverted index and the linear Quadtree, we propose a novel index structure, called inverted linear Quadtree (IL-Quadtree), which is carefully designed to exploit both spatial and keyword based pruning techniques to effectively reduce the search space. An efficient algorithm is then developed to tackle top $k$ spatial keyword search. To further enhance the filtering capability of the signature of linear Quadtree, we propose a partition based method. In addition, to deal with BTOPK-SK, we design a new computing paradigm which partition the queries into groups based on both spatial proximity and the textual relevance between queries. We show that the IL-Quadtree technique can also efficiently support BTOPK-SK. Comprehensive experiments on real and synthetic data clearly demonstrate the efficiency of our methods.
-
inverted linear Quadtree efficient top k spatial keyword search
International Conference on Data Engineering, 2013Co-Authors: Chengyuan Zhang, Ying Zhang, Wenjie Zhang, Xuemin LinAbstract:With advances in geo-positioning technologies and geo-location services, there are a rapidly growing amount of spatio-textual objects collected in many applications such as location based services and social networks, in which an object is described by its spatial location and a set of keywords (terms). Consequently, the study of spatial keyword search which explores both location and textual description of the objects has attracted great attention from the commercial organizations and research communities. In the paper, we study the problem of top k spatial keyword search (TOPK-SK), which is fundamental in the spatial keyword queries. Given a set of spatio-textual objects, a query location and a set of query keywords, the top k spatial keyword search retrieves the closest k objects each of which contains all keywords in the query. Based on the inverted index and the linear Quadtree, we propose a novel index structure, called inverted linear Quadtree (IL-Quadtree), which is carefully designed to exploit both spatial and keyword based pruning techniques to effectively reduce the search space. An efficient algorithm is then developed to tackle top k spatial keyword search. In addition, we show that the IL-Quadtree technique can also be applied to improve the performance of other spatial keyword queries such as the direction-aware top k spatial keyword search and the spatio-textual ranking query. Comprehensive experiments on real and synthetic data clearly demonstrate the efficiency of our methods.
Beatrice Pesquetpopescu - One of the best experts on this subject based on the ideXlab platform.
-
initialization limitation and predictive coding of the depth and texture Quadtree in 3d hevc
IEEE Transactions on Circuits and Systems for Video Technology, 2014Co-Authors: Elie Gabriel Mora, Joel Jung, Marco Cagnazzo, Beatrice PesquetpopescuAbstract:The 3D video extension of High Efficiency Video Coding (3D-HEVC) exploits texture-depth redundancies in 3D videos using intercomponent coding tools. It also inherits the same Quadtree coding structure as HEVC for both components. The current software implementation of 3D-HEVC includes encoder shortcuts that speed up the Quadtree construction process, but those are always accompanied by coding losses. Furthermore, since the texture and its associated depth represent the same scene, at the same time instant and view point, their Quadtrees are closely linked. In this paper, an intercomponent tool is proposed in which this link is exploited to save both runtime and bits through a joint coding of the Quadtrees. If depth is coded before the texture, the texture Quadtree is initialized from the coded depth Quadtree. Otherwise, the depth Quadtree is limited to the coded texture Quadtree. A 31% encoder runtime saving, a -0.3% gain for coded and synthesized views and a -1.8% gain for coded views are reported for the second method.
-
initialization limitation and predictive coding of the depth and texture Quadtree in 3d hevc
IEEE Transactions on Circuits and Systems for Video Technology, 2014Co-Authors: Elie Gabriel Mora, Joel Jung, Marco Cagnazzo, Beatrice PesquetpopescuAbstract:The 3D video extension of High Efficiency Video Coding (3D-HEVC) exploits texture-depth redundancies in 3D videos using intercomponent coding tools. It also inherits the same Quadtree coding structure as HEVC for both components. The current software implementation of 3D-HEVC includes encoder shortcuts that speed up the Quadtree construction process, but those are always accompanied by coding losses. Furthermore, since the texture and its associated depth represent the same scene, at the same time instant and view point, their Quadtrees are closely linked. In this paper, an intercomponent tool is proposed in which this link is exploited to save both runtime and bits through a joint coding of the Quadtrees. If depth is coded before the texture, the texture Quadtree is initialized from the coded depth Quadtree. Otherwise, the depth Quadtree is limited to the coded texture Quadtree. A 31% encoder runtime saving, a -0.3% gain for coded and synthesized views and a -1.8% gain for coded views are reported for the second method.
Joel Jung - One of the best experts on this subject based on the ideXlab platform.
-
initialization limitation and predictive coding of the depth and texture Quadtree in 3d hevc
IEEE Transactions on Circuits and Systems for Video Technology, 2014Co-Authors: Elie Gabriel Mora, Joel Jung, Marco Cagnazzo, Beatrice PesquetpopescuAbstract:The 3D video extension of High Efficiency Video Coding (3D-HEVC) exploits texture-depth redundancies in 3D videos using intercomponent coding tools. It also inherits the same Quadtree coding structure as HEVC for both components. The current software implementation of 3D-HEVC includes encoder shortcuts that speed up the Quadtree construction process, but those are always accompanied by coding losses. Furthermore, since the texture and its associated depth represent the same scene, at the same time instant and view point, their Quadtrees are closely linked. In this paper, an intercomponent tool is proposed in which this link is exploited to save both runtime and bits through a joint coding of the Quadtrees. If depth is coded before the texture, the texture Quadtree is initialized from the coded depth Quadtree. Otherwise, the depth Quadtree is limited to the coded texture Quadtree. A 31% encoder runtime saving, a -0.3% gain for coded and synthesized views and a -1.8% gain for coded views are reported for the second method.
-
initialization limitation and predictive coding of the depth and texture Quadtree in 3d hevc
IEEE Transactions on Circuits and Systems for Video Technology, 2014Co-Authors: Elie Gabriel Mora, Joel Jung, Marco Cagnazzo, Beatrice PesquetpopescuAbstract:The 3D video extension of High Efficiency Video Coding (3D-HEVC) exploits texture-depth redundancies in 3D videos using intercomponent coding tools. It also inherits the same Quadtree coding structure as HEVC for both components. The current software implementation of 3D-HEVC includes encoder shortcuts that speed up the Quadtree construction process, but those are always accompanied by coding losses. Furthermore, since the texture and its associated depth represent the same scene, at the same time instant and view point, their Quadtrees are closely linked. In this paper, an intercomponent tool is proposed in which this link is exploited to save both runtime and bits through a joint coding of the Quadtrees. If depth is coded before the texture, the texture Quadtree is initialized from the coded depth Quadtree. Otherwise, the depth Quadtree is limited to the coded texture Quadtree. A 31% encoder runtime saving, a -0.3% gain for coded and synthesized views and a -1.8% gain for coded views are reported for the second method.
-
block merging for Quadtree based partitioning in hevc
IEEE Transactions on Circuits and Systems for Video Technology, 2012Co-Authors: Philipp Helle, Benjamin Bross, Oudin Simon, Detlev Marpe, M O Bici, Kemal Ugur, Joel Jung, G Clare, Thomas WiegandAbstract:The joint development of the upcoming High Efficiency Video Coding (HEVC) standard by ITU-T Video Coding Experts Group and ISO/IEC Moving Picture Experts Group marks a new step in video compression capability. In technical terms, HEVC is a hybrid video-coding approach using Quadtree-based block partitioning together with motion-compensated prediction. Even though a high degree of adaptability is achieved by Quadtree-based block partitioning, this approach has certain intrinsic drawbacks, which may result in redundant sets of motion parameters being transmitted. Previous work has shown that those redundancies can effectively be removed by merging the leafs of a particular Quadtree structure. Following this concept, a block merging algorithm for HEVC is now proposed. This algorithm generates a single motion parameter set for a whole region of contiguous motion-compensated blocks. In this paper, we describe the various components of the proposed block merging algorithm and, using experimental evidence, demonstrate their benefits in terms of coding efficiency.
Chengyuan Zhang - One of the best experts on this subject based on the ideXlab platform.
-
hierarchical information Quadtree efficient spatial temporal image search for multimedia stream
Multimedia Tools and Applications, 2019Co-Authors: Chengyuan Zhang, Ruipeng Chen, Fang HuangAbstract:Massive amount of multimedia data that contain times- tamps and geographical information are being generated at an unprecedented scale in many emerging applications such as photo sharing web site and social networks applications. Due to their importance, a large body of work has focused on efficiently computing various spatial image queries. In this paper,we study the spatial temporal image query which considers three important constraints during the search including time recency, spatial proximity and visual relevance. A novel index structure, namely Hierarchical Information Quadtree(HI-Quadtree), to efficiently insert/delete spatial temporal images with high arrive rates. Base on HI-Quadtree an efficient algorithm is developed to support spatial temporal image query. We show via extensive experimentation with real spatial databases clearly demonstrate the efficiency of our methods.
-
inverted linear Quadtree efficient top k spatial keyword search
IEEE Transactions on Knowledge and Data Engineering, 2016Co-Authors: Chengyuan Zhang, Ying Zhang, Wenjie Zhang, Xuemin LinAbstract:With advances in geo-positioning technologies and geo-location services, there are a rapidly growing amount of spatio-textual objects collected in many applications such as location based services and social networks, in which an object is described by its spatial location and a set of keywords (terms). Consequently, the study of spatial keyword search which explores both location and textual description of the objects has attracted great attention from the commercial organizations and research communities. In the paper, we study two fundamental problems in the spatial keyword queries: top $k$ spatial keyword search (TOPK-SK), and batch top $k$ spatial keyword search (BTOPK-SK). Given a set of spatio-textual objects, a query location and a set of query keywords, the TOPK-SK retrieves the closest $k$ objects each of which contains all keywords in the query. BTOPK-SK is the batch processing of sets of TOPK-SK queries. Based on the inverted index and the linear Quadtree, we propose a novel index structure, called inverted linear Quadtree (IL-Quadtree), which is carefully designed to exploit both spatial and keyword based pruning techniques to effectively reduce the search space. An efficient algorithm is then developed to tackle top $k$ spatial keyword search. To further enhance the filtering capability of the signature of linear Quadtree, we propose a partition based method. In addition, to deal with BTOPK-SK, we design a new computing paradigm which partition the queries into groups based on both spatial proximity and the textual relevance between queries. We show that the IL-Quadtree technique can also efficiently support BTOPK-SK. Comprehensive experiments on real and synthetic data clearly demonstrate the efficiency of our methods.
-
inverted linear Quadtree efficient top k spatial keyword search
International Conference on Data Engineering, 2013Co-Authors: Chengyuan Zhang, Ying Zhang, Wenjie Zhang, Xuemin LinAbstract:With advances in geo-positioning technologies and geo-location services, there are a rapidly growing amount of spatio-textual objects collected in many applications such as location based services and social networks, in which an object is described by its spatial location and a set of keywords (terms). Consequently, the study of spatial keyword search which explores both location and textual description of the objects has attracted great attention from the commercial organizations and research communities. In the paper, we study the problem of top k spatial keyword search (TOPK-SK), which is fundamental in the spatial keyword queries. Given a set of spatio-textual objects, a query location and a set of query keywords, the top k spatial keyword search retrieves the closest k objects each of which contains all keywords in the query. Based on the inverted index and the linear Quadtree, we propose a novel index structure, called inverted linear Quadtree (IL-Quadtree), which is carefully designed to exploit both spatial and keyword based pruning techniques to effectively reduce the search space. An efficient algorithm is then developed to tackle top k spatial keyword search. In addition, we show that the IL-Quadtree technique can also be applied to improve the performance of other spatial keyword queries such as the direction-aware top k spatial keyword search and the spatio-textual ranking query. Comprehensive experiments on real and synthetic data clearly demonstrate the efficiency of our methods.
Hanan Samet - One of the best experts on this subject based on the ideXlab platform.
-
sorting in space multidimensional data structures for computer graphics and vision applications
International Conference on Computer Graphics and Interactive Techniques, 2016Co-Authors: Hanan SametAbstract:The representation of spatial data is important in game programming, computer graphics, visualization, solid modeling, computer vision and geographic information systems (GIS). They are rooted in the intersection of computer vision and graphics. Recently, there has been much interest in hierarchical representations such as Quadtrees, octrees, and pyramids which are based on image hierarchies, as well methods that use bounding boxes which are based on object hierarchies. Their advantage is that they provide a way to index into space. In fact, they are little more than multidimensional sorts. They save space as well as time and also facilitate operations such as search. In addition, we introduce methods for dealing with recognizing textual specifications of spatial data such as locations in news articles. This course provides a brief overview of hierarchical spatial data structures and related algorithms that make use of them. We describe hierarchical representations of points, lines, collections of small rectangles, regions, surfaces, and volumes. For region data, we point out the dimension-reduction property of the region Quadtree and octree, as how to navigate between nodes in the same tree, thereby leading to the popularity of these representations in ray tracing applications. We also demonstrate how to use these representations for both raster and vector data. We also In the case of nonregion data, we show how these data structures can be used to find nearest neighbors which is critical when using machine learning techniques. We also show how to do it in an incremental fashion so that the number of objects need not be known in advance. In addition, the SAND spatial browser based on the SAND spatial database system, the VASCO JAVA applet illustrating these methods (www.cs.umd.edu/ hjs/Quadtree/index.html), and the NewsStand system (newsstand.umiacs.umd.edu) will be demonstrated.
-
indexing methods for moving object databases games and other applications
International Conference on Management of Data, 2013Co-Authors: Hanan Samet, Jagan Sankaranarayanan, Michael AuerbachAbstract:Moving object databases arise in numerous applications such as traffic monitoring, crowd tracking, and games. They all require keeping track of objects that move and thus the database of objects must be constantly updated. The cover fieldtree (more commonly known as the loose Quadtree and the loose octree, depending on the dimension of the underlying space) is designed to overcome the drawback of spatial data structures that associate objects with their minimum enclosing Quadtree (octree) cells which is that the size of these cells depends more on the position of the objects and less on their size. In fact, the size of these cells may be as large as the entire space from which the objects are drawn. The loose Quadtree (octree) overcomes this drawback by expanding the size of the space that is spanned by each Quadtree (octree) cell c of width w by a cell expansion factor p (p>0) so that the expanded cell is of width (1+p)*w and an object is associated with its minimum enclosing expanded Quadtree (octree) cell. It is shown that for an object o with minimum bounding hypercube box b of radius r (i.e., half the length of a side of the hypercube), the maximum possible width w of the minimum enclosing expanded Quadtree cell c is just a function of r and p, and is independent of the position of o. Normalizing w via division by 2r enables calculating the range of possible expanded Quadtree cell sizes as a function of p. For p >= 0.5 the range consists of just two values and usually just one value for p >= 1. This makes updating very simple and fast as for p >= 0.5, there are at most two possible new cells associated with the moved object and thus the update can be done in O(1) time. Experiments with random data showed that the update time to support motion in such an environment is minimized when p is infinitesimally less than 1, with as much as a one order of magnitude increase in the number of updates that can be handled vis-a-vis the p=0 case in a given unit of time. Similar results for updates were obtained for an N-body simulation where improved query performance and scalability were also observed. Finally, in order amplify the paper, a video tiled "Crates and Barrels" was produced which is an N-body simulation of 14,000 objects. The video is available from the following URL: http://www.youtube.com/watch?v=Sokq3FRGc0s. An applet to illustrate the behavior of the loose Quadtree was developed and is available from http://donar.umiacs.umd. edu/Quadtree/rectangles/loosequad.html.
-
Using a distributed Quadtree index in peer-to-peer networks
The VLDB Journal, 2007Co-Authors: Egemen Tanin, Aaron Harwood, Hanan SametAbstract:Peer-to-peer (P2P) networks have become a powerful means for online data exchange. Currently, users are primarily utilizing these networks to perform exact-match queries and retrieve complete files. However, future more data intensive applications, such as P2P auction networks, P2P job-search networks, P2P multiplayer games, will require the capability to respond to more complex queries such as range queries involving numerous data types including those that have a spatial component. In this paper, a distributed Quadtree index that adapts the MX-CIF Quadtree is described that enables more powerful accesses to data in P2P networks. This index has been implemented for various prototype P2P applications and results of experiments are presented. Our index is easy to use, scalable, and exhibits good load-balancing properties. Similar indices can be constructed for various multidimensional data types with both spatial and non-spatial components.
-
navigating through triangle meshes implemented as linear Quadtrees
ACM Transactions on Graphics, 2000Co-Authors: Michael Lee, Hanan SametAbstract:Techniques are presented for navigating between adjacent triangles of greater or equal size in a hierarchical triangle mesh where the triangles are obtained by a recursive Quadtree-like subdivision of the underlying space into four equilateral triangles. These techniques are useful in a number of applications, including finite element analysis, ray tracing, and the modeling of spherical data. The operations are implemented in a manner analogous to that used in a Quadtree representation of data on the two-dimensional plane where the underlying space is tessellated into a square mesh. A new technique is described for labeling the triangles, which is useful in implementing the Quadtree triangle mesh as a linear Quadtree (i.e., a pointer-less Quadtree); the navigation can then take place in this linear Quadtree. When the neighbors are of equal size, the algorithms have a worst-case constant time complexity. The algorithms are very efficient, as they make use of just a few bit manipulation operations, and can be implemented in hardware using just a few machine language instructions. The use of these techniques when modeling spherical data by projecting it onto the faces of a regular solid whose faces are equilateral triangles, which are represented as Quadtree triangle meshes, is discussed in detail. The methods are applicable to the icosahedron, octahedron, and tetrahedron. The difference lies in the way transitions are made between the faces of the polyhedron. However, regardless of the type of polyhedron, the computational complexity of the methods is the same.
