Search

Abstract: Extracting tuples from HTML pages has been an important issue in various web applications. Commercial tuple extraction systems have enjoyed some success to extract tuples by regarding HTML pages as tree structures and exploiting XPath queries to find attributes of tuples in the HTML pages. However, such systems would be vulnerable to small changes on the web pages. In this paper, we propose a robust tuple extraction system which utilizes spatial relationships among elements rather than the XPath queries. Spatial information (e.g., 2-D coordinates) of elements are maintained in the DOM tree when a web page is rendered in a browser. Our system regards elements in the rendered page as spatial objects in the 2-D space and executes spatial joins to extract target elements. Since humans also identify an element in a web page by its relative spatial location, our system extracting elements by their spatial relationships could possibly be as robust as manual extraction. To specify and execute spatial joins, we propose a new query language, RAQuery, based on topological relationships between any spatial objects in the 2-D space. We then propose spatial join algorithms that efficiently process the RAQuery using novel notions of group match and prunable relation group. We next propose a tuple construction algorithm to build tuples from the extracted elements obtained by the spatial joins, which can construct tuples even when there are no boundary HTML elements specified for the tuples in the web page. Extensive experimental results using real HTML pages confirm that our solutions are far more robust than existing tuple extraction systems without sacrificing performance. [Copyright &y& Elsevier]

Abstract: Shortest path (or least travel time path) identification has been actively studied for direct application to road networks. In addition, the processing of time-dependent shortest-path queries, which use past traffic data to compute the speed variations of road segments, has been investigated in order to incorporate speed variations over time. However, speed information pre-computed from static past traffic data is often invalid because road traffic is inherently dynamic. This paper addresses a new problem in processing a Dynamic Time-Dependent Shortest Path (DTDSP) query, which considers the current road status without assuming pre-determined speed patterns on roads. By dynamically adjusting the speed patterns of roads instead of fixing them based on past traffic data, the recommended paths, which reflect the current road status, are more effective in distributing the road traffic and thus reducing the travel time. To process DTDSP queries, we first propose a Continuous Piece-wise Linear Speed Pattern (CPLSP) model to compute the vehicle speed patterns, which is more flexible and realistic than previously adopted piece-wise constant speed pattern models. Using dynamically computed CPLSPs, we process a DTDSP query in two phases: (1) the least travel time path is found for the query and (2) the speed patterns of the following vehicles, which are affected by the participation of the new vehicle on the road network, are updated. We propose efficient algorithms for finding the least travel time path of a new query (vehicle) and for updating the speed patterns of the existing vehicles. Experiments on real data sets show that our query processing algorithms effectively distribute road traffic, and thus, significantly reduce both global and individual travel times. [Copyright &y& Elsevier]

Abstract: Since recent applications such as XML applications, Geographical Information Systems (GIS), and CAD/CAM systems require highly efficient data management, they are built on Object-Relational DBMS (ORDBMS). The applications are called navigational applications, and they navigate the composite objects connected via the reference and the collection attributes in the ORDBMS. When a navigational application accesses an object, it first checks whether the object is stored in the object cache. If not, the object must be fetched from the database in the server, which is a costly operation. Prefetching identifies the objects that are most likely to be accessed in the near future by the navigational applications and stores them in the object cache in advance. Since prefetching reduces the number of object fetches, it is crucial for improving the application performance. However, the experimental result by Han et al. showed that the improvement ratio of application performance is much lower than the reduction ratio of the number of object fetches. In this paper, we claim that the number of disk accesses in the server also considerably affects the application performance, and we propose a technique for minimizing disk accesses to improve the performance of the prefetch method by Han et al. and hence the navigational application. The contributions of this paper are summarized as follows. (1) For the iterative and the recursive patterns, we propose methods for creating materialized views based on the type-level path access logs proposed in . We refer to the materialized views as the type-level access pattern views. (2) We then present the algorithms for minimizing the number of disk accesses using the type-level access pattern views when prefetching the objects from the database in the server. (3) We present an implementation technique that, given a prefetch request from the client, quickly finds the most efficient type-level access pattern view. (4) We perform a series of experiments using a variety of databases to show that the proposed technique significantly improves the overall performance of the navigational application. Experimental result shows that we reduce the number of disk accesses by up to 33.0 times and improve the performance by up to 21.4 times. [Copyright &y& Elsevier]

In prefetching, the objects that are expected to be accessed in the future are fetched from the server to the client in advance. Prefetching reduces the number of round-trips and increases the system performance. To prefetch object effectively, we need to correctly predict the future navigational patterns. In this paper, we propose the PrefetchGuide, a novel data structure that captures the navigational access patterns. We also formally define the notion of the attribute access log set and analyze the navigational access patterns that can be captured by the PrefetchGuide. We then present an prefetching algorithm using the PrefetchGuide. To show effectiveness of our algorithm, we have conducted extensive experiments in a prototype object-relational database management systems (DBMS). The results show that our method significantly outperforms the state-of-the-art prefetching method. These results indicate that our approach provides a practical method that can be implemented in commercial object-oriented/object-relational DBMSs. We believe our method is practically usable for object-oriented programmers and DBMS implementors. [Copyright &y& Elsevier]

Abstract: SVM (Support Vector Machine) is a well-established machine learning methodology popularly used for learning classification, regression, and ranking functions. Especially, SVM for rank learning has been applied to various applications including search engines or relevance feedback systems. A ranking function F learned by SVM becomes the query in some search engines: A relevance function F is learned from the user’s feedback which expresses the user’s search intention, and top-k results are found by evaluating the entire database by F. This paper proposes an exact indexing solution for the SVM function queries, which is to find top-k results without evaluating the entire database. Indexing for SVM faces new challenges, that is, an index must be built on the kernel space (SVM feature space) where (1) data points are invisible and (2) the distance function changes with queries. Because of that, existing top-k query processing algorithms, or existing metric-based or reference-based indexing methods are not applicable. We first propose key geometric properties of the kernel space – ranking instability and ordering stability – which is crucial for building indices in the kernel space. Based on them, we develop an index structure iKernel and processing algorithms. We then present clustering techniques in the kernel space to enhance the pruning effectiveness of the index. According to our experiments, iKernel is highly effective overall producing 1–5% of evaluation ratio on large data sets. [Copyright &y& Elsevier]

As social networking services become a large part of modern life, interest in applications using social networks has rapidly increased. One interesting application is viral marketing , which can be formulated in graph theory as the influence maximization problem. Specifically, the goal of the influence maximization problem is to find a set of k nodes(corresponding to individuals in social network) whose influence spread is maximum. Several methods have been proposed to tackle this problem but to select the k most influential nodes, they suffer from the high computational cost of approximating the influence spread of every individual node. In this paper, we propose an effective pruning method for the influence maximization problem based on Random Walk and Rank Merge. The key idea is to efficiently find and prune out uninfluential nodes in order to dramatically reduce the amount of computation for evaluating influence spread. Our experimental results demonstrate the efficiency of the proposed method compared to previous state-of-the-art methods. Additionally, our method is easily parallelizable, resulting in further speed up. [ABSTRACT FROM AUTHOR]

Influence maximization is the problem of selecting the most influential nodes in a given graph. The problem is applicable to viral marketing and is actively researched as social networks become the media of information propagation. To solve the challenges of influence maximization, previous works approximate the influence evaluations to reduce the running time and to simultaneously guarantee the quality of those evaluations. We propose a new influence maximization algorithm that overcomes the limitations of the state of the art algorithms. We also devise our algorithm to process update operations of dynamic graphs. Our algorithm outperforms the state of the art algorithms TIM + and SKIM in running time, and its influence spread is also comparable to the others. Our experiments show that processing update operations is faster than executing baselines each time. Additional experiments with synthetic graphs show that the process preserves the quality of influence spread. [ABSTRACT FROM AUTHOR]