Enriching many location-based applications, various new skyline queries are proposed and formulated based on the notion of locational dominance, which extends conventional one by taking objects' nearness to query positions into account additional to objects' nonspatial attributes. To answer a representative class of skyline queries for location-based applications efficiently, this paper presents two index-based approaches, namely, augmented R-tree and dominance diagram. Augmented R-tree extends R-tree by including aggregated nonspatial attributes in index nodes to enable dominance checks during index traversal. Dominance diagram is a solution-based approach, by which each object is associated with a precomputed nondominance scope wherein query points should have the corresponding object not locationally dominated by any other. Dominance diagram enables skyline queries to be evaluated via parallel and independent comparisons between nondominance scopes and query points, providing very high search efficiency. The performance of these two approaches is evaluated via empirical studies, in comparison with other possible approaches.

Database-generated dynamic web pages (db-pages, in short), whose contents are created on the fly by web applications and databases, are now prominent in the web. However, many of them cannot be searched by existing search engines. Accordingly, we develop a novel search engine named Dash, which stands for Db-pAge Search, to support db-page search. Dash determines db-pages possibly generated by a target web application and its database through exploring the application code and the related database content and supports keyword search on those db-pages. In this paper, we present its system design and focus on the efficiency issue. To minimize costs incurred for collecting, maintaining, indexing and searching a massive number of db-pages that possibly have overlapped contents, Dash derives and indexes db-page fragments in place of db-pages. Each db-page fragment carries a disjointed part of a db-page. To efficiently compute and index db-page fragments from huge datasets, Dash is equipped with MapReduce based algorithms for database crawling and db-page fragment indexing. Besides, Dash has a top-k search algorithm that can efficiently assemble db-page fragments into db-pages relevant to search keywords and return the k most relevant ones. The performance of Dash is evaluated via extensive experimentation.

In this paper, we present a new system framework called ROAD for spatial object search on road networks. ROAD is extensible to diverse object types and efficient for processing various location-dependent spatial queries (LDSQs), as it maintains objects separately from a given network and adopts an effective search space pruning technique. Based on our analysis on the two essential operations for LDSQ processing, namely, network traversal and object lookup, ROAD organizes a large road network as a hierarchy of interconnected regional subnetworks (called Rnets). Each Rnet is augmented with 1) shortcuts and 2) object abstracts to accelerate network traversals and provide quick object lookups, respectively. To manage those shortcuts and object abstracts, two cooperating indices, namely, Route Overlay and Association Directory are devised. In detail, we present 1) the Rnet hierarchy and several properties useful in constructing and maintaining the Rnet hierarchy, 2) the design and implementation of the ROAD framework, and 3) a suite of efficient search algorithms for single-source LDSQs and multisource LDSQs. We conduct a theoretical performance analysis and carry out a comprehensive empirical study to evaluate ROAD. The analysis and experiment results show the superiority of ROAD over the state-of-the-art approaches.

In this paper, we introduce two types of probabilistic aggregation queries, namely, Probabilistic Minimum Value Queries (PMVQ)s and Probabilistic Minimum Node Queries (PMNQ)s. A PMVQ determines possible minimum values among all imprecise sensed data, while a PMNQ identifies sensor nodes that possibly provide minimum values. However, centralized approaches incur a lot of energy from battery-powered sensor nodes and well-studied in-network aggregation techniques that presume precise sensed data are not practical to inherently imprecise sensed data. Thus, to answer PMVQs and PMNQs energy-efficiently, we devised suites of in-network algorithms. For PMVQs, our in-network minimum value screening algorithm (MVS) filters candidate minimum values; and our in-network minimum value aggregation algorithm (MVA) conducts in-network probability calculation. PMNQs requires possible minimum values to be determined a prior, inevitably consuming more energy to evaluate than PMVQs. Accordingly, our one-phase and two-phase in-network algorithms are devised. We also extend the algorithms to answer PMNQ variants. We evaluate all our proposed approaches through cost analysis and simulations.

Given a geographic query that is composed of query keywords and a location, a geographic search engine retrieves documents that are the most textually and spatially relevant to the query keywords and the location, respectively, and ranks the retrieved documents according to their joint textual and spatial relevances to the query. The lack of an efficient index that can simultaneously handle both the textual and spatial aspects of the documents makes existing geographic search engines inefficient in answering geographic queries. In this paper, we propose an efficient index, called IR-tree, that together with a top-k document search algorithm facilitates four major tasks in document searches, namely, 1) spatial filtering, 2) textual filtering, 3) relevance computation, and 4) document ranking in a fully integrated manner. In addition, IR-tree allows searches to adopt different weights on textual and spatial relevance of documents at the runtime and thus caters for a wide variety of applications. A set of comprehensive experiments over a wide range of scenarios has been conducted and the experiment results demonstrate that IR-tree outperforms the state-of-the-art approaches for geographic document searches.

To enhance the quality of document search, recent research studies have started to exploit the social networks of users by considering social influence (SI), measurement of the affinity between a query user and the publisher of a retrieved document, in addition to the commonly used textual relevance (TR). We refer to such document search that considers social networks as social web search. In this paper, we focus on efficient top-k social web search and propose two search strategies: (i) TR-based search and (ii) SI-based search that tailor document examination orders upon TR and SI, respectively. We evaluate the proposed strategies through experimentation.

This paper presents DISQO, a DIStributed Framework for Spatial Queries over Moving Objects. Distinguished from existing work, DISQO aims at achieving high scalability and system performance in support of both snapshot and continuous spatial queries over moving objects. The design of DISQO is based on our observation that exchanging object location information and query information between the location server and moving objects can reduce communication cost and facilitate scalable query processing. Thus, DISQO is built upon the notions of roaming regions and query maps in correspondence with object location information and query information. A comprehensive performance evaluation has been conducted to demonstrate the superiority of DISQO design, compared with existing state-of-the-art frameworks for monitoring moving objects.

In this paper, we present a new type of spatial queries called Nearest Surrounder (NS) queries. An NS query determines the nearest polygon-shaped spatial objects (referred to as nearest surrounder objects) and their orientations with respect to a query point from an object set. Besides, we derive two NS query variants, namely, multitier NS (m-NS) queries and angle-constrained NS (ANS) queries. An m-NS query searches multiple layers of NS objects for the same range of angles from a query point. An ANS query searches for NS objects within a specified range of angles. To evaluate NS queries and their variants, we explore angle-based and distance-based bound properties of polygons, and devise two efficient algorithms, namely, Sweep and Ripple, based on R-tree. The algorithms access objects in an order according to their orientations and distances with respect to a given query point, respectively. They are efficient as they can finish a search with one index lookup. Besides, they can progressively deliver a query result. Through empirical studies, we evaluate the proposed algorithms and report their performance for both synthetic and real object sets.

Navigational path query, one of the most popular location-based services (LBSs), determines a route from a source to a destination on a road network. However, issuing path queries to some non-trustworthy service providers may pose privacy threats to the users. For instance, given a query requesting for a path from a residential address to a psychiatrist, some adversaries may deduce "who is related to what disease". In this paper, we present an obfuscator framework that reduces the likelihood of path queries being revealed, while supporting different user privacy protection needs and retaining query evaluation efficiency. The framework consists of two major components, namely, an obfuscator and an obfuscated path query processor. The former formulates obfuscated path queries by intermixing true and fake sources and destinations and the latter facilitates efficient evaluation of the obfuscated path queries in an LBS server. The framework supports three types of obfuscated path queries, namely, independent obfuscated path query, shared obfuscated path query, and anti-collusion obfuscated path query. Our proposal strikes a balance between privacy protection strength and query processing overheads, while enhancing privacy protection against collusion attacks. Finally, we validate the proposed ideas and evaluate the performance of our framework based on an extensive set of empirical experiments.

In this paper, we present ROAD, a general framework to evaluate Location-Dependent Spatial Queries (LDSQ)s that searches for spatial objects on road networks. By exploiting search space pruning technique and providing a dynamic object mapping mechanism, ROAD is very efficient and flexible for various types of queries, namely, range search and nearest neighbor search, on objects over large-scale networks. ROAD is named after its two components, namely, Route Overlay and Association Directory, designed to address the network traversal and object access aspects of the framework. In ROAD, a large road network is organized as a hierarchy of interconnected regional sub-networks (called Rnets) augmented with 1) shortcuts for accelerating network traversals; and 2) object abstracts for guiding traversals. In this paper, we present (i) the Rnet hierarchy and several properties useful to construct Rnet hierarchy, (ii) the design and implementation of the ROAD framework, (iii) efficient object search algorithms for various queries, and (iv) incremental update techniques for framework maintenance in presence of object and network changes. We conducted extensive experiments with real road networks to evaluate ROAD. The experiment result shows the superiority of ROAD over the state-of-the-art approaches.

On a road network, the minimum cost path (or min-cost path for short) from a source location to a destination is a path with the smallest travel cost among all possible paths. Despite that min-cost path queries on static networks have been well studied, the problem of monitoring min-cost paths on a road network in presence of updates is not fully explored. In this paper, we present PathMon, an efficient system for monitoring min-cost paths in dynamic road networks. PathMon addresses two important issues of the min-cost path monitoring problem, namely, (i) path invalidation that identifies min-cost paths returned to path queries affected by network changes, and (ii) path update that replaces invalid paths with new ones for those affected path queries. For (i), we introduce the notion of query scope, based on which a query scope index (QSI) is developed to identify affected path queries. For (ii), we devise a partial path computation algorithm (PPCA) to quickly recompute the updated paths. Through a comprehensive performance evaluation by simulation, QSI and PPCA are demonstrated to be effective on the path invalidation and path update issues.

This paper presents a research study on skyline path queries. Given a source s and a destination d on a road network and multiple path search criteria (e.g., short distance and short travel time), a skyline query returns a set of non-dominated paths from s to d. These non-dominated paths are called skyline paths. Efficient computation of skyline path queries is very challenging due to expensive network traversals and extensive path comparisons in dominance tests. In this paper, we explore the characteristics of skyline paths, based on which a novel skyline path search algorithm called SkyPath is proposed. To narrow down the search scope for result skyline paths, partial dominance test and full path dominance test are devised as two components of SkyPath. Evaluation results show the superiority of the SkyPath algorithm over the state-of-the-art approaches.

Reverse nearest neighbor (RNN) queries have a broad application base such as decision support, profile-based marketing, resource allocation, data mining, etc. Previous work on RNN search does not take obstacles into consideration. In the real world, however, there are many physical obstacles (e.g., buildings, blindages, etc.), and their presence may affect the visibility/distance between two objects. In this paper, we introduce a novel variant of RNN queries, namely visible reverse nearest neighbor (VRNN) search, which considers the obstacle influence on the visibility of objects. Given a data set P, an obstacle set O, and a query point q, a VRNN query retrieves the points in P that have q as their nearest neighbor and are visible to q. We propose an efficient algorithm for VRNN query processing, assuming that both P and O are indexed by R-trees. Our method does not require any pre-processing, and employs half-plane property and visibility check to prune the search space.

Directions search returns the shortest path from a source to a destination on a road network. However, the search interests of users may be exposed to the service providers, thus raising privacy concerns. For instance, a path query that finds a path from a resident address to a clinic may lead to a deduction about "who is related to what disease". To protect user privacy from accessing directions search services, we introduce the OPAQUE system, which consists of two major components: (1) an obfuscator that formulates obfuscated path queries by mixing true and fake sources/destinations; and (2) an obfuscated path query processor installed in the server for obfuscated path query processing. OPAQUE reduces the likelihood of path queries being revealed and allows retrieval of requested paths. We propose two types of obfuscated path queries, namely, independently obfuscated path query and shared obfuscated path query to strike a balance between privacy protection strength and query processing overhead, and to enhance privacy protection against collusion attacks.

Reverse nearest neighbor (RNN) queries have a broad application base such as decision support, profile-based marketing, resource allocation, etc. Previous work on RNN search does not take obstacles into consideration. In the real world, however, there are many physical obstacles (e.g., buildings) and their presence may affect the visibility between objects. In this paper, we introduce a novel variant of RNN queries, namely, visible reverse nearest neighbor (VRNN) search, which considers the impact of obstacles on the visibility of objects. Given a data set P, an obstacle set O, and a query point q in a 2D space, a VRNN query retrieves the points in P that have q as their visible nearest neighbor. We propose an efficient algorithm for VRNN query processing, assuming that P and O are indexed by R-trees. Our techniques do not require any preprocessing and employ half-plane property and visibility check to prune the search space. In addition, we extend our solution to several variations of VRNN queries, including: 1) visible reverse k-nearest neighbor (VRkNN) search, which finds the points in P that have q as one of their k visible nearest neighbors; 2) \delta-VRkNN search, which handles VRkNN retrieval with the maximum visible distance \delta constraint; and 3) constrained VRkNN (CVRkNN) search, which tackles the VRkNN query with region constraint. Extensive experiments on both real and synthetic data sets have been conducted to demonstrate the efficiency and effectiveness of our proposed algorithms under various experimental settings.

In this research, we develop ROAD, a system framework for processing location dependent spatial queries (LDSQs) that search for spatial objects of interest on road networks. By exploiting search space pruning, ROAD is very efficient and flexible for various LDSQs on different types of objects over large-scale networks. In ROAD, a large road network is organized as a set of interconnected regional sub-networks (called Rnets) augmented with 1) shortcuts for accelerating search traversals; and 2) object abstracts for guiding object search. In this poster, we outline this framework and explain how it can support efficient location-dependent nearest neighbor search.

Wireless data broadcast is an efficient and scalable means to provide information access for a large population of clients in mobile environments. With Location-Based Services (LBSs) deployed upon a broadcast channel, mobile clients can collect data from the channel to answer their location-dependent spatial queries (LDSQs). Since the results of LDSQs would become invalid when mobile client moves to new locations, the knowledge of valid scopes for LDSQ results is necessary to assist clients to determine if their previous LDSQ results can be reused after they moved. This effectively improves query response time and client energy consumption. In this paper, we devise efficient algorithms to determine valid scopes for various LDSQs including range, window and nearest neighbor queries along with LDSQ processing over a broadcast channel. We conduct an extensive set of experiments to evaluate the performance of our proposed algorithms. While the proposed valid scope algorithm incurs only little extra processing overhead, unnecessary LDSQ reevaluation is significantly eliminated, thus providing faster query response and saving client energy.

Given a set of data points with both spatial coordinates and non-spatial attributes, point a location-dependently dominates point b with respect to a query point q if a is closer to q than b and meanwhile a dominates b. A location- dependent skyline query (LDSQ) issued at point q is to retrieve all the points that are not location-dependently dominated by other points with regard to q. In this paper, we focus on the query processing and result validation of LDSQ over static objects. Two algorithms, namely brute-forth and delta-scanning, are proposed. The former serves as the baseline algorithm while the latter significantly improves the performance via space pruning. We further conduct a comprehensive simulation to demonstrate the performance of proposed algorithms.

Given a set of data points P and a query point q in a multidimensional space, reverse nearest neighbor (RNN) query finds data points in P whose nearest neighbors are q. Reverse k-nearest neighbor (RkNN) query (where k ges 1) generalizes RNN query to find data points whose kNNs include q. For RkNN query semantics, q is said to have influence to all those answer data points. The degree of q's influence on a data point p (isin P) is denoted by kappap where q is the kappap-th NN of p. We introduce a new variant of RNN query, namely, ranked reverse nearest neighbor (RRNN) query, that retrieves t data points most influenced by q, i.e., the t data points having the smallest kappa's with respect to q. To answer this RRNN query efficiently, we propose two novel algorithms, kappa-counting and kappa-browsing that are applicable to both monochromatic and bichromatic scenarios and are able to deliver results progressively. Through an extensive performance evaluation, we validate that the two proposed RRNN algorithms are superior to solutions derived from algorithms designed for RkNN query.

Abstract The rapid advance of wireless and portable computing technology has brought a lot of research interests and momentum to the area of mobile computing. One of the research focus is onpervasive data access. With wireless connections, users can access information at any place at any time. However, various constraints such as limited client capability, limited bandwidth, weak connectivity, and client mobility impose many challenging technical issues. In the past years, tremendous research efforts have been put forth to address the issues related to pervasive data access. A number of interesting research results were reported in the literature. This survey paper reviews important works in two important dimensions of pervasive data access:data broadcastandclient caching. In addition, data access techniques aiming at various application requirements (such astime,location,semanticsandreliability) are covered. Copyright © 2006 John Wiley & Sons, Ltd.

In distance-based location update schemes with a predefined distance threshold d, an object reports its location to the location server, whenever it is located more than a distance of d away from the location expected of by the server. Adopting a small threshold can keep locations maintained in the location server close to exact object locations, but that incurs high location update costs. In this paper, we address the important issue of finding an optimal distance threshold. Our approach exploits a costfunction that takes into account location update and query processing costs, the two key performance costs, based on which an optimal threshold that minimizes the overall cost is derived. In dynamic environments, costs may vary over time, so a threshold good at one moment could become bad at another. To determine an optimal threshold adaptively, we propose two optimization algorithms, namely, conjectural algorithm and progressive algorithm. Conjectural optimization algorithm " guesses" the current system conditions, based on which it directly determines the most probable optimal value. Progressive optimization algorithm starts with a certain threshold value and adjusts it gradually towards the optimal point. To evaluate our proposed algorithms, various simulation studies are conducted and significant performance gain is observed with our algorithms.

In this paper, we study a new type of spatial query, Nearest Surrounder (NS), which searches the nearest surrounding spatial objects around a query point. NS query can be more useful than conventional nearest neighbor (NN) query as NS query takes the object orientation into consideration. To address this new type of query, we identify angle-based bounding properties and distance-bound properties of Rtree index. The former has not been explored for conventional spatial queries. With these identified properties, we propose two algorithms, namely, Sweep and Ripple. Sweep searches surrounders according to their orientation, while Ripple searches surrounders ordered by their distances to the query point. Both algorithms can deliver result incrementally with a single dataset lookup. We also consider the multiple-tier NS (mNS) query that searches multiple layers of NSs. We evaluate the algorithms and report their performance on both synthetic and real datasets.

Moving object databases (MODs), the core component of location server to support location-related applications, keep track of the locations of moving objects which submit location update reports to the centralized server. In resource-limited wireless environments, the frequency and conditions for generating location update messages exert a strong impact on system performance in terms of update message cost and object location accuracy, hence the query result precision. Conceptually, moving objects are the sources of the location data while the MOD caches recently reported object locations for query processing. Owing to the inherent imprecision of the cached values, we impose a bounded level of inconsistency for the cached values, realized in the form of a "safe range" for a moving object. The cached value needs not be invalidated so long as the deviation of the object's current location from its reported location is within the safe range. A smaller safe range results in a higher accuracy of the cached value and hence more accurate query result at the expense of higher update cost, and vice versa. Since the size of the safe range is the key to system performance, we derive a system cost model to determine its appropriate value. Furthermore, to cater for highly dynamic environments in which object movement, query access pattern and system workload always change, we propose two adaptive safe range adjustment algorithms. Through extensive simulation experiments, the benefits brought about by our algorithms are evidenced

Location-based services (LBS) have emerged as one of the killer applications for mobile and pervasive computing environments. Due to limited bandwidth and scarce client resources, client-side data caching plays an important role of enhancing the data availability and improving the response time. In this demonstration, we present CS Cache Engine suitable for LBS. The underlying caching model is Complementary Space Caching (CS caching) scheme that we have recently presented in [citation]. Different from conventional data caching schemes, CS caching preserves a global view of the database by maintaining physical objects and capturing those objects in the server but not in the cache as Complementary Regions (CRs) in the cache. As a result, with the CS Cache Engine implementing CS caching, client assertiveness on their own answered queries is enhanced so that unnecessary requests over the wireless channel can be avoided; various kinds of location-based queries are naturally supported; and the client's ability to prefetch objects is introduced such that the response time can be further improved. In this demonstration paper, we discuss the architecture and the functionality of the CS Caching Engine that adopts CS caching. Specifically, for this demonstration, a tourist information named TravelGuide is prototyped with the support of this cache engine.

Predictive continuous nearest neighbor queries are concerned with finding the nearest neighbor objects for some future time period according to the current object and query locations and their motion information. Existing continuous query processing algorithms are not efficient enough, requiring multiple dataset lookups to evaluate the query results throughout the duration of a continuous query. More importantly, the complete result for the whole query time interval is only available at the moment when all object motion updates have been examined, based on which adjustment of the query result is made. In this paper, we propose an algorithm which requires only one dataset lookup to deliver a complete predictive result. We then apply a differential update technique to maintain the query results incrementally in the presence of object location and motion updates.

The mobile environment is inherently asymmetric. To utilize the downstream bandwidth effectively, hot data items should be disseminated over the broadcast channel to the mobile clients. To equip clients with the ability to identify the nature of the broadcast and to determine the answerability of their queries, semantic descriptions are associated with information units in the broadcast, organized into data chunks. Based on the nature of data items received over the broadcast, clients can initiate appropriate requests to make up for the remaining items over the back channels in an on-demand basis. We investigation into several semantic-based algorithms to organize data chunks and compare their performance with traditional data item-based organization in the asymmetric environment.

Database broadcast is an effective and scalable approach to disseminate information of high affinity to a large collection of mobile clients. A common problem of existing broadcast approaches is the lack of knowledge for a client to determine if all data items satisfying its query could be obtained from the broadcast. We therefore propose a semantic-based broadcast approach. A semantic descriptor is attached to each broadcast unit, called a data chunk. This semantic descriptor allows a client to determine if a query can be answered entirely based on broadcast items and, if needed, identify the precise definition of the remaining items in the form of a "supplementary" query. Data chunks can be of static or dynamic sizes and organized hierarchically. Their boundary can be determined on-the-fly, adaptive to the nature of client queries. We investigate different ways of organizing the data chunks over a broadcast channel to improve access performance. We introduce the data affinity index metric, which more accurately reflects client-perceived performance. A simulation model is built to evaluate our semantic-based broadcast schemes.

Data broadcast is an effective approach to disseminate information from a database server to numerous mobile clients in a mobile environment. Since a broadcast session contains only a subset of the database items, a client might not be able to obtain all its items from the broadcast and is forced to request additional ones from the server on demand. We describe a semantic-based broadcast approach which attaches a semantic description to each broadcast unit, called a chunk, which is a cluster of data items. This allows a client to determine if a query can be answered entirely using a broadcast as well as defining the precise nature of the remaining items in the form of a "supplementary" query. Chunks could be of different sizes and are hierarchically organized. We propose a heuristic to schedule the broadcast order of the chunks to improve the tuning time, access time, and a new metric called a data affinity index. The performances are evaluated via experiments based on a simulation model.

Article Free Access Share on Incremental maintenance for dynamic database-derived HTML pages in digital libraries Authors: Ken C. K. Lee Department of Computing, the Hong Kong Polytechnic University, Hung Hom, Hong kong Department of Computing, the Hong Kong Polytechnic University, Hung Hom, Hong kongView Profile , Hong V. Leong Department of Computing, the Hong Kong Polytechnic University, Hung Hom, Hong kong Department of Computing, the Hong Kong Polytechnic University, Hung Hom, Hong kongView Profile , Antonio Si Sun Microsystems Inc., Palo Alto, CA Sun Microsystems Inc., Palo Alto, CAView Profile Authors Info & Claims CIKM '98: Proceedings of the seventh international conference on Information and knowledge managementNovember 1998 Pages 20–29https://doi.org/10.1145/288627.288637Online:01 November 1998Publication History 2citation619DownloadsMetricsTotal Citations2Total Downloads619Last 12 Months3Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF