Catálogo de publicaciones - libros

Although a number of methods have been proposed to process exact match or range queries in P2P network, very few attention has been paid on spatial query process. In this paper, we propose a triangular topology of P2P network and spatial query processing methods on this topology. Each node maintains a set of pointers to neighbor nodes determined by delaunay triangulation. This triangular network topology provides us with an efficient way to find a path from any source node to the destination node or area, and to process spatial queries. We compare two spatial query processing methods based on the triangular network by experiments.

Finding single pair shortest paths on surface is a fundamental problem in various domains, like Geographic Information Systems (GIS) 3D applications, robotic path planning system, and surface nearest neighbor query in spatial database, etc. Currently, to solve the problem, existing algorithms must traverse the entire polyhedral surface. With the rapid advance in areas like Global Positioning System (GPS), Computer Aided Design (CAD) systems and laser range scanner, surface models are becoming more and more complex. It is not uncommon that a surface model contains millions of polygons. The single pair shortest path problem is getting harder and harder to solve. Based on the observation that the single pair shortest path is in the locality, we propose in this paper efficient methods by excluding part of the surface model without considering them in the search process. Three novel expansion-based algorithms are proposed, namely, Naïve algorithm, Rectangle-based Algorithm and Ellipse-based Algorithm. Each algorithm uses a two-step approach to find the shortest path. (1) compute an initial local path. (2) use the value of this initial path to select a search region, in which the global shortest path exists. The search process terminates once the global optimum criteria are satisfied. By reducing the searching region, the performance is improved dramatically in most cases.

As random access memory chips get cheaper, it becomes affordable to realize main memory-based database systems. The most important issues in main memory database indexing techniques for mobile GIS applications are to improve update performances – since numerous update operations can arise for tracking continuously moving objects – and to reduce cache misses for improving search performances. In this paper, we propose MR-tree, a cache-conscious version of the R-tree for main memory databases. To increase fan-out, the MR-tree applies a novel compression scheme to entry MBRs (Minimum Bounding Rectangles). This scheme represents entry MBRs by relative coordinates in a node. To improve update performance, the MR-tree can become an unbalanced tree as follows: it propagates node splits upward only if one of the internal nodes on the insertion path has empty space, or all height differences between the consecutive nodes on the insertion path are 1 and one of the height differences among its subtrees is equal to some unbalance parameter. Because of this feature, the MR-tree can reduce the number of internal nodes splits and reinsertions significantly. In the case where all internal nodes on the insertion path do not meet the above conditions, a newly created leaf node simply becomes the child of the split leaf, when a leaf node split occurs. This split leaf is called the half-leaf node. Our experimental result shows that the search speed of the proposed two-dimensional MR-tree increases by almost a factor of two compared to the CR-tree and the R-tree variant, which are also main memory based R-trees, while maintaining better update performance.

When looking for specific detail within the context of spatial information, users are often faced with the problem of information overload. Moreover, research efforts in responding to such needs, and in general, are impeded by a lack of non-proprietary platforms for development. Personalization is a powerful concept for providing users with precise information that satisfies their current requirements. Personalization techniques are currently in widespread use across the World Wide Web. However, existing Web map servers do not offer much support for personalization in terms of map content. Furthermore, these systems are heavily reliant on proprietary software. We propose a solution to these problems by outlining a prototype system that presents the user with personalized maps containing condensed content. Such a system has been developed using non-proprietary software for both the Web and mobile environments.

Spatial information is often presented as maps in location-based services, which makes it necessary to label cartographic features in real time. Features may be dense all over the map, or in certain areas. Owing to the limited free spaces, it is always difficult to label dense features. Aiming to utilize free spaces efficiently, this paper proposed a density-based method of labelling dense features. The method placed labels of dense features earlier than sparse ones, so that free spaces were allotted to dense features before consumed by sparse features. An efficient algorithm was developed for map labelling in real time. We implemented this method in a Java environment. A case study shows sound cartographic results and acceptable efficiency of the labelling.

We developed a regional information retrieval system for the mobile environment, called “Mobile SeoulSearch”. This system provides regional information related to the specific position where a mobile user is located. Here the regional information is derived from the Web space. For utilizing the features of mobile environment, and coping with limitations of user interface in mobile devices, several methods are proposed: Firstly, using user’s location information which is obtained in real-time, a method that regional information related to the mobile user’s specific location is provided in real-time to mobile devices, is proposed. Using this method, the mobility of mobile devices is maximized, and the limitation of input methods on the devices is coped with. Secondly, a layered and reconfigurable graphical user interface similar to CardLayout in Java, is proposed so that lots of regional information is displayed efficiently in spite of very poor user interface in mobile devices. Finally, methods for gathering Web pages and indexing regional terms, are proposed to provide mobile users with the regional information effectively. The efficiency of these methods are verified through the development of “Mobile SeoulSearch”.

This paper presents a novel indexing method for digital video contents. The method automatically identifies city buildings captured by digital video camera. This is done by extracting the objects from candidate objects using GPS location-and-time data of the video shooter, video camera posture data taken by a Gyro attached to the camera, and a 3-dimensional city map stored in a database. The automatic calculation identifies the start and end video frames for each building object captured in a video unit. An index is created to refer to the set of all video units in which a specified building is really captured. A concrete experiment implementing the proposed algorithm in Ginza Area, Tokyo demonstrated that the algorithm works as designed.

Recent advance of technology has made it possible to view and simply manipulate 3D representations of spatial information over the Internet. 3D visualization, however, imposes many unique requirements to software design and implementation, as well as supporting data. Furthermore, current development of 3D modelling and visualization of spatial information mostly focus on single user platform. This paper presents our discussion on the design and development of an Internet-based 3D collaborative GIS system, which support real-time multi-user collaboration. While the prototype development is ongoing, some design issues are discussed based on our preliminary work. ...

Arrival time dependent shortest path finding is an important function in the field of traffic information systems or telematics. However large number of mobile objects on the road network results in a scalability problem for frequently updating and handling their real-time location. In this paper, we propose a query processing method in MANET(Mobile Ad-hoc Network) environment to find an arrival time dependent shortest path with a consideration of both traffic and location in real time. Since our method does not need a centralized server, time dependent shortest path query is processed by in-network way. In order to reduce the number of messages to forward and nodes to relay, we introduce an , where messages are forwarded to neighboring nodes on the same or adjacent road segments. This routing method allows to collect traffic information in real time and to reduce the number of routing messages. Experiments show that the number of forwarded messages is reduced in an order of magnitude with our method compared to LAR-like method. At best, our method reduces about 57 times less messages.